Frontier-Based Exploration


Laser-Limited Sonar

The standard evidence grid formulation assumes that each sensor reading is independent of every other sensor reading. In reality, this is not the case -- and we take advantage of this to eliminate specular reflections from our evidence grids.


Sonar sensors send out pulses of ultrasonic sound which reflect off objects and bounce back to the sensor. By measuring the amount of time between the emission of the pulse and the receipt of the echo, the sensor can determine its distance from nearby obstacles.


The main problem with sonar sensors is that instead of bouncing back toward the sensor, the sound pulse can hit a flat surface and bounce away from the sensor. Then either the sonar senses nothing, or it senses objects that, like reflections in a mirror, appear to be much farther away than the nearest surface.


We deal with these reflections using a technique we call laser-limited sonar. We use a laser rangefinder in combination with the sonar sensors, and if the laser returns a range reading less than the sonar reading, we update the evidence grid as if the sonar had returned the range indicated by the laser.


Why not just use the laser? Because the laser operates in a two-dimensional plane, while the sonar projects a three-dimensional cone. So, any object that is above or below the laser plane will be invisible to the laser, but still detectable by the sonar. Another alternative would be to use a three-dimensional laser rangefinder, but at present, such devices are too large, too expensive, and too power-hungry to be commonly available on mobile robots.

 Laser-limited sonar isn't perfect -- it's still possible to get specular reflections from obstacles undetected by the laser -- but in practice, we've found that it drastically reduces the number of specular reflections from walls and other large obstacles, which tend to be the major source of errors in evidence grids built using sonar.

 The images below show evidence grids built by the robot using sonar alone (top) and laser-limited sonar (bottom). In these images, cells known to be unoccupied are represented by white space. Cells known to be occupied are represented by large dots. Cells with unknown occupancy probability are represented by small dots.




The robot was located in a small alcove at one corner of a larger room. The wide open space in the lower right portion of the map corresponds to open space in the larger room, while the other wedges of apparently open space in the upper image correspond to specular reflections. Laser-limited sonar was able to eliminate all of the specular reflections present in the initial grid.

Frontier-Based Exploration