Automatic Map Generation

Robotic vehicles operating in confining spaces, such as coal mines, can benefit from a three-dimensional map or model of the environment. The map can be used for planning and executing operations such as coal cutting or navigation between different locations in a mine. The maps can serve as a visual aid to a remote operator or supplant a manual survey of the environment.

Our approach to constructing maps is to fuse data from a laser rangefinder taken from several locations in the environment into a single, consistent map. The figure below shows a range image taken from the Typhoon scanner. An image from this scanner consists of 409,600 range points acquired by scanning 360 degrees in azimuth and 40 degrees in elevation over a 20 second period. The range values are encoded by gray scales. White is near the scanner, and black is far away. The first half of the scan (180 degrees in azimuth) is shown in the first row, and the last half in the second row.

The task of fusing the data is straightforward if the location of the sensor is known for all images taken. This is an unrealistic assumption for some applications. For example, in coal mining, measuring the sensor's location using standard surveyor's instruments is undesirable due to the threat of roof collapse, fire, explosion, or carbon monoxide. Satellite-based GPS are useless underground and inertial-based systems drift over the time they are in motion. One of my postdocs, Gary Shaffer, has developed an algorithm for constructing two-dimensional maps from multiple range images given only approximate sensor locations. This technique simultaneously adjusts the sensor locations and model contours to minimize total error in the data. The algorithm not only produces a useful map but also computes all of the sensor locations. A map constructed by this algorithm is shown in the figure below. Gary is currently extending this approach to build three-dimensional maps.

Back to home page.