Sampling-based min-max uncertainty path planning

Brendan Englot, Tixiao Shan, Shaunak D. Bopardikar, Alberto Speranzon

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

We propose a new sampling-based path planning algorithm, the Min-Max Rapidly Exploring Random Tree (MM-RRT∗), for robot path planning under localization uncertainty. The projected growth of error in a robot's state estimate is curbed by minimizing the maximum state estimate uncertainty encountered on a path. The algorithm builds and maintains a tree that is shared in state space and belief space, with a single belief per robot state. Due to the fact that many states will share the same maximum uncertainty, resulting from a shared parent node, the algorithm uses secondary objective functions to break ties among neighboring nodes with identical maximum uncertainty. The algorithm offers a compelling alternative to sampling-based algorithms with additive cost representations of uncertainty, which will penalize high-precision navigation routes that are longer in duration.

Original languageEnglish
Title of host publication2016 IEEE 55th Conference on Decision and Control, CDC 2016
Pages6863-6870
Number of pages8
ISBN (Electronic)9781509018376
DOIs
StatePublished - 27 Dec 2016
Event55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States
Duration: 12 Dec 201614 Dec 2016

Publication series

Name2016 IEEE 55th Conference on Decision and Control, CDC 2016

Conference

Conference55th IEEE Conference on Decision and Control, CDC 2016
Country/TerritoryUnited States
CityLas Vegas
Period12/12/1614/12/16

Fingerprint

Dive into the research topics of 'Sampling-based min-max uncertainty path planning'. Together they form a unique fingerprint.

Cite this