Speeding Up Search-Based Motion Planning using Expansion Delay Heuristics


  • Jasmeet Kaur Carnegie Mellon University
  • Ishani Chatterjee Carnegie Mellon University
  • Maxim Likhachev Carnegie Mellon University




Learning Effective Heuristics And Other Forms Of Control Knowledge


Suboptimal search algorithms are a popular way to find solutions to planning problems faster by trading off solution optimality for search time. This is often achieved with the help of inadmissible heuristics. Prior work has explored ways to learn such inadmissible heuristics. However, it has focused on learning the heuristic value as an estimate of the cost to reach a goal. In this paper, we present a different approach that computes inadmissible heuristics by learning Expansion Delay for transitions in the state space. Expansion Delay is defined as the number of states expanded during the search between two consecutive states. Expansion Delay can be used as a measure of the depth of local minima regions i.e., regions where the heuristic(s) are weakly correlated with the true cost-to-goal (Vats, Narayanan and Likhachev 2017). Our key idea is to learn this measure in order to guide the search such that it reduces the total Expansion delay for reaching the goal and hence, avoid local minima regions in the state space. We analyze our method on 3D (x, y, theta) planning and Humanoid footstep planning. We find that the heuristics computed using our technique result in finding feasible plans faster.




How to Cite

Kaur, J., Chatterjee, I., & Likhachev, M. (2021). Speeding Up Search-Based Motion Planning using Expansion Delay Heuristics. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 528-532. https://doi.org/10.1609/icaps.v31i1.16000