Photos Spare Cycles MythBusters

Talk: A Multi-Resolution Pyramid for Outdoor Robot Terrain Perception

Michael Montemerlo and Sebastian Thrun, Stanford

Elegant solution for managing short-range and long-range mapping data for robot navigation.


  • Terrain perception in 3D
  • Difficulties with evidence grids
  • Evidence grid pyramids
  • Multi-resolution evidence grid pyramids
  • Results

Focused on local maps, not global maps.


Robot platform-based on the Segway scooter * GPS, laser rangefinder, pan-tilt unit, IMU * ability to navigate long distances in urban settings

Carmen robot navigation toolkit

Demo * records laser data according to inertial position and GPS data * builds 3D environment * have to have memory because laser sweeps back and forth * classifies navigability in real-time


  • Campus mapping: 800m map of Stanford Campus around Memorial Church
  • DARPA Grand Challenge: exploring terrain in real time and avoid obstacles. have to deal with data at different ranges in reasonable way

General approach:

Collapse 3D world into 2D traversability map (cost map)

Obstacle detection: look at points in the current scan, a large change in elevation over a small change in range indicates and obstacle

Evidence grids: Project obstacle data into 2D grid. integrate multiple measurements in a grid cell using Bayes Rule. In log-odds form turns into simple summation problem (add or subtract based on current evidence)

Problem #1: Range effects

Accuracy of sensors vary with range but evidence grid treats all observation equally. Systematic error at long range (observe long range targets for a long time, so large summation based on error can accumulate and is hard to remove).

Problem #2: Undersampling

Environment at long range is undersampled, creates holes in evidence grid which confuses planner

Solution: Evidence grid pyramids

  • Maintain N evidence grids, each one sensitive to a range of sensor readings.
  • solves range effects problem. systematic error in long range maps does not effect short range map
  • sub-map ranges may overlap: uses a smooth weighting function
  • Downside: divides the amount of evidence incorporated into any map by a factor of N. As N scales, lose some benefit as each gathers data more slowly

Multi-resolution grids

Each of the grids can and should have a different resolution. Much better sensor coverage

3 effects contribute to grid cell resolution: measurement error, limited horizontal resolution, limited vertical resolution. Minimum detectable obstacle increases linearly with range => suggests pyramid with linearly increasing resolution.


Without multi-resolution pyramid a lot more holes in grid. Get better approximate idea of stuff far off but maintain good local accuracy.

Running with three evidence grids.


  • Approach to terrain perception that accounts for systematic effect of range on obstacle detection.
  • Extended to multi-resolution pyramids
  • derivation of bound on grid resolution over a given range
  • real-world robot implementation and demonstration

Q and A:

  • bounding likelihoods improves problem, but it penalizes the short-range.
  • weighting likelihood by range lessens accumulation, but problem is still there
  • more elegant solution for eliminating systematic effects.
  • always believe closest map that gives you information about obstacle being encountered.

Post a comment

related entries.

what is this?

This page contains a single entry from kwc blog posted on July 27, 2004 3:03 PM.

The previous post was Talk: AI Characters and Directors for Interactive Computer Games.

The next post is Talk: Identifying Terrorist Activity with AI Plan Recognition Technology.

Current entries can be found on the main page.