# Learning Heuristic Search via Imitation

arXiv: https://arxiv.org/abs/1707.03034 · HTML: https://mlsanity.com/paper/1707.03034/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2017.

## Built on by (most cited first, 30 of 34)

- [Imitating Task and Motion Planning with Visuomotor Transformers](https://mlsanity.com/paper/2305.16309/) (2023)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers](https://mlsanity.com/paper/2212.11730/) (2022)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [Continuous Relaxation of Symbolic Planner for One-Shot Imitation Learning](https://mlsanity.com/paper/1908.06769/) (2019)
- [Polygrammar: Grammar for Digital Polymer Representation and Generation](https://mlsanity.com/paper/2105.05278/) (2021)
- [Learning Graph Search Heuristics](https://mlsanity.com/paper/2212.03978/) (2022)
- [Learning Forward Dynamics Model and Informed Trajectory Sampler for Safe Quadruped Navigation](https://mlsanity.com/paper/2204.08647/) (2022)
- [Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search](https://mlsanity.com/paper/2205.09963/) (2022)
- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [Experience-Based Heuristic Search: Robust Motion Planning with Deep Q-Learning](https://mlsanity.com/paper/2102.03127/) (2021)
- [LRGNet: Learnable Region Growing for Class-Agnostic Point Cloud Segmentation](https://mlsanity.com/paper/2103.09160/) (2021)
- [Embeddings and labeling schemes for A*](https://mlsanity.com/paper/2111.10041/) (2021)
- [Cascaded Diffusion Models for Neural Motion Planning](https://mlsanity.com/paper/2505.15157/) (2025)
- [Guided Policy Optimization under Partial Observability](https://mlsanity.com/paper/2505.15418/) (2025)
- [A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks](https://mlsanity.com/paper/2102.04518/) (2021)
- [A Differentiable Loss Function for Learning Heuristics in A*](https://mlsanity.com/paper/2209.05206/) (2022)
- [Evaluating Guiding Spaces for Motion Planning](https://mlsanity.com/paper/2210.08640/) (2022)
- [A Framework for Guided Motion Planning](https://mlsanity.com/paper/2404.03133/) (2024)
- [SLOPE: Search with Learned Optimal Pruning-based Expansion](https://mlsanity.com/paper/2406.04935/) (2024)
- [DAA*: Deep Angular A Star for Image-based Path Planning](https://mlsanity.com/paper/2507.09305/) (2025)
- [Pheromone-Focused Ant Colony Optimization algorithm for path planning](https://mlsanity.com/paper/2601.07597/) (2026)
- [UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding](https://mlsanity.com/paper/2602.23789/) (2026)
- [Learning Neural Parsers with Deterministic Differentiable Imitation Learning](https://mlsanity.com/paper/1806.07822/) (2018)
- [Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding](https://mlsanity.com/paper/2109.14695/) (2021)
- [Leveraging Experience in Lazy Search](https://mlsanity.com/paper/2110.04669/) (2021)
- [See What the Robot Can't See: Learning Cooperative Perception for Visual Navigation](https://mlsanity.com/paper/2208.00759/) (2022)
- [[Reproducibility Report] Path Planning using Neural A* Search](https://mlsanity.com/paper/2208.04153/) (2022)
- [Multi-Robot Path Planning Combining Heuristics and Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.01270/) (2023)

## Abstract (arXiv)

Robotic motion planning problems are typically solved by constructing a search tree of valid maneuvers from a start to a goal configuration. Limited onboard computation and real-time planning constraints impose a limit on how large this search tree can grow. Heuristics play a crucial role in such situations by guiding the search towards potentially good directions and consequently minimizing search effort. Moreover, it must infer such directions in an efficient manner using only the information uncovered by the search up until that time. However, state of the art methods do not address the problem of computing a heuristic that explicitly minimizes search effort. In this paper, we do so by training a heuristic policy that maps the partial information from the search to decide which node of the search tree to expand. Unfortunately, naively training such policies leads to slow convergence and poor local minima. We present SaIL, an efficient algorithm that trains heuristic policies by imitating "clairvoyant oracles" - oracles that have full information about the world and demonstrate decisions that minimize search effort. We leverage the fact that such oracles can be efficiently computed using dynamic programming and derive performance guarantees for the learnt heuristic. We validate the approach on a spectrum of environments which show that SaIL consistently outperforms state of the art algorithms. Our approach paves the way forward for learning heuristics that demonstrate an anytime nature - finding feasible solutions quickly and incrementally refining it over time.