Improved analysis of greedy mapping

Improved analysis of greedy mapping,10.1109/IROS.2003.1249657,Craig Tovey,Sven Koenig

Improved analysis of greedy mapping   (Citations: 20)
BibTex | RIS | RefWorks Download
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 𝒪;(|V|32/) to 𝒪;(|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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: