TY - GEN
T1 - Belief roadmap search
T2 - 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017
AU - Shan, Tixiao
AU - Englot, Brendan
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/12/13
Y1 - 2017/12/13
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85041951315&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041951315&partnerID=8YFLogxK
U2 - 10.1109/IROS.2017.8206425
DO - 10.1109/IROS.2017.8206425
M3 - Conference contribution
AN - SCOPUS:85041951315
T3 - IEEE International Conference on Intelligent Robots and Systems
SP - 5318
EP - 5325
BT - IROS 2017 - IEEE/RSJ International Conference on Intelligent Robots and Systems
Y2 - 24 September 2017 through 28 September 2017
ER -