Improved analysis of greedy mapping

We analyze greedy mapping, a simple mapping method that has successfully been used on mobile robots. Greedy mapping moves the robot from its current location on a shortest path towards a closest unvisited, unscanned or informative location, until the terrain is mapped. Previous work has resulted in upper and lower bounds on its worst-case travel distance but there was a large gap between the bounds. In this paper, we reduce the gap substantially by decreasing the upper bound from /spl Oscr/; (|V|/sup 3/2/) to /spl Oscr/; (|V|ln|V|) edge traversals, where |V| is the number of vertices of the graph. This upper bound demonstrates that the travel distance of greedy mapping is guaranteed to be small and thus suggests that greedy mapping is indeed a reasonable mapping method. The guaranteed good performance of greedy mapping is robust in that it holds for different versions of greedy mapping, regardless of sensor type and sensor range.

Authors

• Craig A. Tovey
• Sven Koenig

Keywords

• Terrain mapping
• Robot sensing systems
• Mobile robots
• Upper bound
• Robustness
• Educational institutions
• Search methods
• Lower Bound
• Mapping Method
• Current Position
• Shortest Path
• Vertices
• Mobile Robot
• Range Of Sensors
• Mapping Performance
• Effective Properties
• Functional Identification
• Triangle Inequality
• Alternative Sequences
• Depth-first
• Breadth-first Search
• Robot Localization
• Finite Graph