/Asymptotically-optimal Motion Planning using lower bounds on cost

Asymptotically-optimal Motion Planning using lower bounds on cost

Oren Salzman and Dan Halperin
Conference Paper, 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 4167-4172, May, 2017

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply similar techniques to speed up sampling-based motion-planning algorithms, we use effective lower bounds on the cost between configurations to tightly estimate the cost-to-go. We then use these estimates in an anytime asymptotically-optimal algorithm which we call Motion Planning using Lower Bounds (MPLB). MPLB is based on the Fast Marching Trees (FMT*) algorithm [1] recently presented by Janson and Pavone. An advantage of our approach is that in many cases (especially as the number of samples grows) the weight of collision detection in the computation is almost negligible compared to the weight of nearest-neighbor queries. We prove that MPLB performs no more collision-detection calls than an anytime version of FMT*. Additionally, we demonstrate in simulations that for certain scenarios, the algorithmic tools presented here enable efficiently producing low-cost paths while spending only a small fraction of the running time on collision detection.

BibTeX Reference
author = {Oren Salzman and Dan Halperin},
title = {Asymptotically-optimal Motion Planning using lower bounds on cost},
booktitle = {2017 IEEE International Conference on Robotics and Automation (ICRA)},
year = {2017},
month = {May},
pages = {4167-4172},