Expected shortest paths for landmark-based robot navigation

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics V
Number of pages18
StatePublished - 2004
Externally publishedYes
Event5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002 - Nice, France
Duration: Dec 15 2002Dec 17 2002

Publication series

NameSpringer Tracts in Advanced Robotics
Volume7 STAR
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Conference5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Expected shortest paths for landmark-based robot navigation'. Together they form a unique fingerprint.

Cite this