Outline

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

Focused on local maps, not global maps.

Segbot:

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

Applications

• 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.

Demo

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.

Conclusions

• 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.