Expected shortest paths for landmark-based robot navigation

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

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


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)
Pages (from-to)717-728
Number of pages12
JournalInternational Journal of Robotics Research
Issue number7-8
StatePublished - Jul 2004
Externally publishedYes


  • Expected shortest paths
  • Mobile robot navigation
  • Probabilistic graphs
  • Visual landmarks

ASJC Scopus subject areas

  • Software
  • Mechanical Engineering
  • Artificial Intelligence
  • Applied Mathematics
  • Electrical and Electronic Engineering
  • Modeling and Simulation


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

Cite this