Speeding Up Search-Based Motion Planning via Conservative Heuristics

Ishani Chatterjee, Maxim Likhachev, Ashwin Khadke and Manuela Veloso
Conference Paper, (ICAPS) International Conference on Automated Planning and Scheduling 2019, July, 2019

View Publication

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.


Weighted A* search (wA*) is a popular tool for robot motion-planning. Its efficiency however depends on the quality of heuristic function used. In fact, it has been shown that the correlation between the heuristic function and the true cost-to-goal significantly affects the efficiency of the search, when used with a large weight on the heuristics. Motivated by this observation, we investigate the problem of computing heuristics that explicitly aim to minimize the amount of search efforts in finding a feasible plan. The key observation we exploit is that while heuristics tries to guide the search along what looks like an optimal path towards the goal, there are other paths that are clearly sub-optimal yet are much easier to compute. For example, in motion planning domains like footstep-planning for humanoids, a heuristic that guides the search along a path away from obstacles is less likely to encounter local minima compared with the heuristics that guides the search along an optimal but close-to-obstacles path. We utilize this observation to define the concept of conservative heuristics and propose a simple algorithm for computing such a heuristic function. Experimental analysis on (1) humanoid footstep planning (simulation), (2) path planning for a UAV (simulation), and a real-world experiment in footstep-planning for a NAO robot shows the utility of the approach.

author = {Ishani Chatterjee and Maxim Likhachev and Ashwin Khadke and Manuela Veloso},
title = {Speeding Up Search-Based Motion Planning via Conservative Heuristics},
booktitle = {(ICAPS) International Conference on Automated Planning and Scheduling 2019},
year = {2019},
month = {July},
} 2019-09-30T07:55:37-04:00