Belief roadmap search: Advances in optimal and efficient planning under uncertainty

Tixiao Shan, Brendan Englot

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

11 Scopus citations

Abstract

We characterize and propose advances in the technique of Belief Roadmap Search (BRMS), the process of searching a roadmap in belief space for robot motion planning under localization uncertainty. We discuss the conditions required for optimal substructure in the single-source search of a roadmap in belief space, demonstrating that there are several desirable cost functions for which this property cannot be achieved. Practical performance issues of BRMS are discussed, including the implications of a commonly-used anti-cycling rule, and the computational complexity realized in practical applications of the technique. We propose a best-first implementation of BRMS, in contrast to the standard breadth-first implementation, which we show to improve the computational cost of search by up to 49% by eliminating unnecessary node expansions - the mechanics of both approaches are compared in detail. A variety of motion planning examples are explored.

Original languageEnglish
Title of host publicationIROS 2017 - IEEE/RSJ International Conference on Intelligent Robots and Systems
Pages5318-5325
Number of pages8
ISBN (Electronic)9781538626825
DOIs
StatePublished - 13 Dec 2017
Event2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017 - Vancouver, Canada
Duration: 24 Sep 201728 Sep 2017

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
Volume2017-September
ISSN (Print)2153-0858
ISSN (Electronic)2153-0866

Conference

Conference2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017
Country/TerritoryCanada
CityVancouver
Period24/09/1728/09/17

Fingerprint

Dive into the research topics of 'Belief roadmap search: Advances in optimal and efficient planning under uncertainty'. Together they form a unique fingerprint.

Cite this