We are developing algorithms to create large, high-resolution three-dimensional representations of unstructured terrain. Such maps are useful for a number of robotic applications such as navigation (What is the best route from A to B?), localization (Where is the robot now?), and teleoperation (viewing the environment while controlling a robot remotely).
Using our current approach, we have built maps as large as 260 x 166 meters from sequences of range data. The algorithm is built upon an earlier surface matching system developed by Andrew Johnson. The input to our algorithm is a sequence of range images obtained from different viewpoints. For example, we generated several sequences while driving down a dirt road, stopping periodically to record the surroundings with a laser scanner mounted on the roof. First, we convert each range image in the sequence into a triangular surface mesh. Then, in the registration step, we determine the transformation that aligns each mesh with the next one in the sequence. Finally, we transform all the meshes into a single coordinate system and integrate them into a single 3D map.
Our map building algorithm provides three capabilities not found together in any previous terrain modeling algorithm. First, we have no requirement for an initial approximation of the transform between views or the orientation of the sensor. Second, there is no need to detect explicit features in the environment because we rely on local shape signatures over the entire sensed surface. Finally, it is unnecessary to reduce the sensed data to the more limited elevation map representation.
Our initial work demonstrated that automatically building terrain maps of this size is possible. We concentrated on the aspects specific to map building using ground-based sensors, including widely varying resolution, range shadows, absence of reliably detectable features, and very large data sets. Now, we are extending the basic algorithm and testing the limits of its performance. We are currently addressing the problem of globally consistent registration. When building a map from sequential views of the environment, error can accumulate in the registration between the pairs in the sequence. When a sequence of views forms a loop, the last view will be misaligned with the first. In general, the overlapping regions of a set of views can form many loops, and a global registration algorithm is needed to ensure that all the views are consistent.
