Expected shortest paths for landmark-based robot navigation

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

doi:10.1007/978-3-540-45058-0_23

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 proceeding › Conference contribution

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 language	English (US)
Title of host publication	Algorithmic Foundations of Robotics V
Pages	381-398
Number of pages	18
DOIs	https://doi.org/10.1007/978-3-540-45058-0_23
State	Published - 2004
Externally published	Yes
Event	5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002 - Nice, France Duration: Dec 15 2002 → Dec 17 2002

Publication series

Name	Springer Tracts in Advanced Robotics
Volume	7 STAR
ISSN (Print)	1610-7438
ISSN (Electronic)	1610-742X

Conference

Conference	5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002
Country/Territory	France
City	Nice
Period	12/15/02 → 12/17/02

ASJC Scopus subject areas

Electrical and Electronic Engineering
Artificial Intelligence

Access to Document

10.1007/978-3-540-45058-0_23

Cite this

Briggs, AJ, Detweiler, C, Scharstein, D & Vandenberg-Rodes, A 2004, Expected shortest paths for landmark-based robot navigation. in Algorithmic Foundations of Robotics V. Springer Tracts in Advanced Robotics, vol. 7 STAR, pp. 381-398, 5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002, Nice, France, 12/15/02. https://doi.org/10.1007/978-3-540-45058-0_23

@inproceedings{1f22180b71b94976999fd604d3ee50f4,

title = "Expected shortest paths for landmark-based robot navigation",

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.",

author = "Briggs, {Amy J.} and Carrick Detweiler and Daniel Scharstein and Alexander Vandenberg-Rodes",

year = "2004",

doi = "10.1007/978-3-540-45058-0_23",

language = "English (US)",

isbn = "3540404767",

series = "Springer Tracts in Advanced Robotics",

pages = "381--398",

booktitle = "Algorithmic Foundations of Robotics V",

note = "5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002 ; Conference date: 15-12-2002 Through 17-12-2002",

}

TY - GEN

T1 - Expected shortest paths for landmark-based robot navigation

AU - Briggs, Amy J.

AU - Detweiler, Carrick

AU - Scharstein, Daniel

AU - Vandenberg-Rodes, Alexander

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84864719229&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864719229&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-45058-0_23

DO - 10.1007/978-3-540-45058-0_23

M3 - Conference contribution

AN - SCOPUS:84864719229

SN - 3540404767

SN - 9783540404767

T3 - Springer Tracts in Advanced Robotics

SP - 381

EP - 398

BT - Algorithmic Foundations of Robotics V

T2 - 5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002

Y2 - 15 December 2002 through 17 December 2002

ER -

Expected shortest paths for landmark-based robot navigation

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this