This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Web of Science (1) Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Briggs, A. J. Articles by Vandenberg-Rodes, A. Search for Related Content Social Bookmarking                         What's this?

Expected Shortest Paths for Landmark-Based Robot Navigation

Carrick Detweiler

Daniel Scharstein

Middlebury College, Middlebury, VT 05753, USA

Alexander Vandenberg-Rodes

Princeton University, Princeton, NJ 08544, USA

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.

Key Words: mobile robot navigation • visual landmarks • probabilistic graphs • expected shortest paths

The International Journal of Robotics Research, Vol. 23, No. 7-8, 717-728 (2004)
DOI: 10.1177/0278364904045467


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?