Map-based navigation is a crucial task for any mobile robot. Usually, in an unknown environment this problem is addressed by applying metric grid-maps. However, such maps are in general rather computational expensive and do not scale well. The Landmark-Tree Map (LT-Map) has been designed to enable efficient and unrestricted long-distance navigation also for resource-limited systems, like our mobile robots.

We want to stress the importance of a scalable navigation concept, where different navigation strategies are used to fulfill the various requirements of each navigation task, like local navigation, obstacle avoidance, and global navigation. Hence, metric maps should be used to model small workspaces, where a high localization accuracy is required, e.g., for manipulation tasks. Rolling maps surrounding the robot should be used for obstacle avoidance. Long distance navigation does not require accurate localization capabilities or metric information, but actually only the heading direction is required to find the next goal. This concept is illustrated in the next figure.

Mapping Concept 

Insects are able to cover large distances and reliably find back to their nests, although they are quite limited in their resources. Inspired by theories on insect navigation, we developed a data structure which is highly scalable and efficiently adapts to the available memory during run-time. Positions in space are memorized as snapshots, which are unique configurations of landmarks. The actual landmark location in 3D space is not required, because the robot consecutively moves through the different landmark configurations along a specific road, as illustrated in the next figure.

Unlike conventional snapshot or visual map approaches, we do not simply store the landmarks as a set, but we arrange them in a tree-like structure according to the relevance of their information. The resulting roadmap navigation solely relies on the direction measurements of arbitrary landmarks. The following figure illustrates an LT-Map, showing how the landmarks are implicitly split into translation-invariant and stable features with long visibility and close and unstable features. The x-axis denotes the time, where each branch (one is exemplary highlighted in blue) represents a location on the traversed path.

 

 Tree Example

Currently, we are still working on the LT-Map and evaluate its performance, strengths, and limitations on the Pioneer platforms, equipped with omnidirectional and projective cameras. Experimental results and a detailed description of the algorithm is available in our publications.

 

Systems

 

References

Elmar Mair, Marcus Augustine, Bastian Jäger, Annett Stelzer, Christoph Brand, Darius Burschka, and Michael Suppa. "A biologically inspired navigation concept based on the landmark-tree map for efficient long-distance robot navigation". RSJ International Journal of Advanced Robotics, to appear.

Bastian Jäger, Elmar Mair, Christoph Brand, Wolfgang Stürzl, and Michael Suppa. "Efficient Navigation Based on the Landmark-Tree Map and the Zinf Algorithm Using an Omnidirectional Camera". Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'13), November 2013.

Marcus Augustine, Elmar Mair, Annett Stelzer, Frank Ortmeier, Darius Burschka, and Michael Suppa. "Landmark-Tree Map: a Biologically Inspired Topological Map for Long-Distance Robot Navigation". Proceedings of the IEEE International Conference on Robotics and Biomimetics (ROBIO'12), December 2012

 

Contact

Annett Stelzer

Copyright © 2017 German Aerospace Center (DLR). All rights reserved.