3D Grid Maps for Mobile Robot Perception

Hans Moravec
Principal Research Scientist
Robotics Institute
School of Computer Science
Carnegie Mellon University

Time and Place

1305 Newell-Simon Hall
Refreshments 3:15 pm
Talk 3:30 pm

Abstract

Vector lists offer a compact representation of simple diagrams, and all early computer displays drew point-to-point vectors. The size of vector lists grows unboundedly with image complexity, however. Today, all computer displays are raster based. A raster represents any image at all at fixed, albeit high, cost. Rasters became compelling when computer memories grew large enough to hold them and speeds high enough to fill them rapidly.

Most sonar-based research robots of the 1980s built 2D vector maps of their world. Walls, doors and major obstacles were compactly represented, but maps became unwieldy and unreliable in cluttered regions. Today most mapping robots use 2D grids, which can represent arbitrary layouts in shades of occupancy at fixed cost.

Recent computer speed and memory gains enable robot mapping in 3D. Surface-based descriptions dominate, and are efficient for simple scenes, but strained in clutter. Since 1992 we've been developing a 3D grid approach that loves clutter. Our latest maps, with 16mm grid cells filled with occupancy evidence weights from trinocular stereoscopy, occupy hundreds of megabytes. 1,000 MIPS produces them in near real time. They acquire the original scene's colors as a side effect of a learning process. Simulated run throughs of the color grids can be mistaken for camera imagery of the real scene. We think the technique can guide commercial robots this decade.

Speaker Biography

Hans Moravec received his degree from Stanford in 1980, but still works on his robot mapping and navigation thesis. The maps were sparse 3D point lists in the 1970s, coarse 2D grids in the 1980s, plain 3D grids in the 1990s and colored 3D grids in the 2000s.

Speaker Appointments

For appointments, please contact Yanxi Liu (yanxi@cs.cmu.edu).