Expected Shortest Paths for Landmark-Based Robot Navigation
Authors:
- Amy J. BriggsABAmy J. Briggs
- Carrick DetweilerCDCarrick Detweiler
- 1 August 2004
- journal article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 23 (7-8) , 717-728
Abstract
In this paper we address the problem of planning reliable landmarkbased 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.Keywords
This publication has 26 references indexed in Scilit:
- On the undecidability of probabilistic planning and related stochastic optimization problemsArtificial Intelligence, 2003
- Dynamic shortest paths minimizing travel times and costsNetworks, 2003
- Real-time recognition of self-similar landmarksImage and Vision Computing, 2001
- Probabilistic Algorithms and the Interactive Museum Tour-Guide Robot MinervaThe International Journal of Robotics Research, 2000
- Lessons learned from XavierIEEE Robotics & Automation Magazine, 2000
- The ARK project: Autonomous mobile robots for known industrial environmentsRobotics and Autonomous Systems, 1998
- Landmark-Based Robot NavigationAlgorithmica, 1995
- Model-directed mobile robot navigationIEEE Transactions on Systems, Man, and Cybernetics, 1990
- Probabilistic shortest path problems with budgetary constraintsComputers & Operations Research, 1989
- Optimal paths in graphs with stochastic or multidimensional weightsCommunications of the ACM, 1983