Concurrent Localization, Mapping and Exploration using Manifold Representations

We are investigating the use of mobile robot teams to autonomously explore and map abitrary indoor environments. Central to our approach is a novel map representation based on the notion of a *manifold*; the manifold is an arbitrary two-dimensional surface embedded in a higher dimensional space.

Our motivation for creating this representation flows from the desire to perform autonomous tasks, such as exploration and retro-traverse, in an environment that is only partially mapped; moreover, these tasks must be carried out concurrently with the simultaneous localization and mapping process. We therefore require a map representation that is at all times self-consistent (for autonomous behaviors, we are primariliy concerned with self-consistency with respect to path-planning). Standard planar maps are ill-suited for this purpose, due their tendancy to become confused in environments containing loops. Consider, for example, the situation shown below:

Click on the link below to view an animation of manifold map creation; this animation was generated with real data, using incremental scan matching, and no loop closure.

manifold-sal200.mov (QuickTime, 10Mb)

The manifold representation facilitates a number of interesting capabilities, including lazy loop closure. Loop closure is the most difficult part of the simultaneous localization and mapping process: in order to close a loop, one must decide that two points in the map correspond to the same point in the world (this is the data-association problem). In the manifold representation, such decisions can be indefinitely delayed, without risking map consistency. In the multi-robot context, one may take this one step further, and use active steps to discover correspondance points. Thus, for example, pairs of robots may organize to rendezvous at potential loop closure locations (if the robots can detect each other, the loop is closed).

Shown below is a sequence of snap-shots taken from a two-robot exploration experiment, illustrating the active loop closure process.

Animations of this and other exploration experiments are available here:

• Dual robot exploration (manual)
• Quad robot exploration (autonomous)

Some results from the final DARPA SDR experiments (Fort AP Hill):

• Quad robot, autonomous exploration, single entry point ap_hill_05b_640x480_1.mov (QuickTime, 48Mb)
• Quad robot, autonomous exploration, multiple entry points ap_hill_07a_640x480_1.mov (QuickTime, 27Mb)

References

[howard_iser04a] Andrew Howard, Lynne E. Parker and Gaurav S. Sukhatme, "The SDR Experience: Experiments with a Large-Scale Heterogeneous Mobile Robot Team", 9th International Symposium on Experimental Robotics 2004 (ISER-04), pages , Singapore, Jun 2004 (details)

[howard_icra04a] Andrew Howard, "Multi-Robot Mapping using Manifold Representations", IEEE International Conference on Robotics and Automation, pages 4198--4203, New Orleans, Louisiana, Apr 2004 (details)

Acknowledgements