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