Abstract

Abstract: 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 O(|V|^3/2) to O(|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.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.