Learning Local Heuristics for Search-Based Navigation Planning


  • Rishi Veerapaneni Carnegie Mellon University
  • Muhammad Suhail Saleem Carnegie Mellon University
  • Maxim Likhachev Carnegie Mellon University




Heuristic Learning, Optimal Planning, Supervised Learning


Graph search planning algorithms for navigation typically rely heavily on heuristics to efficiently plan paths. As a result, while such approaches require no training phase and can directly plan long horizon paths, they often require careful hand designing of informative heuristic functions. Recent works have started bypassing hand designed heuristics by using machine learning to learn heuristic functions that guide the search algorithm. While these methods can learn complex heuristic functions from raw input, they i) require significant training and ii) do not generalize well to new maps and longer horizon paths. Our contribution is showing that instead of learning a global heuristic estimate, we can define and learn local heuristics which results in a significantly smaller learning problem and improves generalization. We show that using such local heuristics can reduce node expansions by 2-20x while maintaining bounded suboptimality, are easy to train, and generalize to new maps & long horizon plans.




How to Cite

Veerapaneni, R., Saleem, M. S., & Likhachev, M. (2023). Learning Local Heuristics for Search-Based Navigation Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 634-638. https://doi.org/10.1609/icaps.v33i1.27245