Expected shortest paths for landmark-based robot navigation

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

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)717-728
Number of pages12
JournalInternational Journal of Robotics Research
Volume23
Issue number7-8
DOIs
StatePublished - Jul 2004
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

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

Fingerprint

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

Cite this