Expected Shortest Paths for Landmark-Based Robot Navigation

Amy J. Briggs
Carrick Detweiler
Daniel Scharstein
Alexander Vandenberg-Rodes

Abstract

In this paper we address the problem of planning reliable landmark-based robot navigation strategies in the presence of significant sensor uncertainty. The navigation environments are modeled with directed weighted graphs in which edges can be traversed with given probabilities. To construct robust and efficient navigation plans, we compute expected shortest paths in such graphs. We formulate the expected shortest paths problem as a Markov decision process and provide two algorithms for its solution. We demonstrate the practicality of our approach using an extensive experimental analysis using graphs with varying sizes and parameters.
This paper appeared in The International Journal of Robotics Research, Vol. 23, No. 7-8, July-Auguest 2004, pp. 717-728.

Back to Amy Briggs' home page