Learning Heuristic Search via Imitation

Mohak Bhardwaj, Sanjiban Choudhury, Sebastian A. Scherer

Abstract

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 make efficient search critical. We present SAIL (Search as Imitation Learning), an algorithm that trains a heuristic policy to minimize planning effort by imitating a clairvoyant oracle. By leveraging full environment knowledge during training to provide perfect labels, SAIL learns to adapt to complex obstacle configurations, significantly reducing the number of node expansions compared to traditional distance-based heuristics.

Introduction

In robotic motion planning, finding a path from a start to a goal configuration often involves building a search tree. For robots with complex geometries or limited onboard power, the primary cost of planning is the computational effort required to find a valid path, particularly the expensive process of 'edge evaluation' (collision checking).

Standard search algorithms like A use heuristics such as Euclidean distance to guide the search. However, these heuristics are 'blind' to obstacles, leading to the 'bug trap' problem. In such scenarios, a robot may become stuck in U-shaped obstacles because the heuristic continuously directs it toward the goal, which lies behind an impassable wall. This paper argues that an effective heuristic should explicitly minimize search effort* by adapting to the environment's structure rather than merely estimating distance.

The 'bug trap' problem: standard heuristics often lead search algorithms into dead ends (top) or cause excessive node expansions (bottom) due to a lack of environmental awareness.

The SAIL Framework

The authors frame heuristic search as a sequential decision-making problem under uncertainty and introduce SAIL, an imitation learning framework. The approach relies on three key components:

  1. The Clairvoyant Oracle: During training, the algorithm has access to the full map. It uses dynamic programming to compute the true 'cost-to-go' from every state, representing a perfect decision-maker that knows the most efficient path to the goal.
  2. Interactive Imitation Learning: SAIL uses a mixture policy—partly following its current learned heuristic and partly following the oracle. This ensures the learner encounters states it is likely to see at test time when the full map is unavailable.
  3. Regression Model: The heuristic is represented by a neural network that takes a 17-dimensional feature vector (including distances, tree depth, and local obstacle data) and learns to regress the oracle’s cost-to-go values. This allows the model to 'hallucinate' likely global structures from local information.

Experimental Setup

SAIL was evaluated on 2D navigation tasks using 200x200 8-connected grids. The researchers created several distinct environment distributions to test adaptability, including 'Bug Traps' (U-shaped obstacles), 'Forests' (randomly scattered obstacles), and 'Mazes'.

A typical 'bug trap' environment used for evaluating search efficiency. The white squares represent node expansions during the search process.

The model was trained on 200 maps and tested on 100 held-out maps to ensure generalization across different obstacle configurations.

Results and Discussion

  • Superior Efficiency: SAIL consistently outperformed baselines, including standard Euclidean heuristics and advanced multi-heuristic search (MHA*). In many cases, it reduced node expansions by orders of magnitude.
  • Robustness to Traps: While traditional heuristics failed in 'bug trap' environments by expanding nearly every possible state, SAIL learned to explore peripheries and escape traps efficiently.
  • Fast Convergence: The algorithm converged to a high-performing policy within 6–8 iterations, significantly faster than Reinforcement Learning alternatives like Q-Learning.
  • Distributional Adaptation: A key insight is that the same architecture learns different behaviors based on training data—becoming cautious in trap-heavy environments and greedy in open forests.

Conclusion

SAIL demonstrates that learning from a clairvoyant oracle can produce heuristics that are significantly more efficient than traditional distance-based metrics. While the current implementation focuses on search effort over path optimality, future work could integrate SAIL into 'anytime' planning frameworks to provide rapid initial solutions. Additionally, the authors propose scaling the approach to high-dimensional robot arm planning using Random Geometric Graphs.

Summary updated

Abstract

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 const...
BibTeX
@inproceedings{bhardwaj2017learning,
  author = {Mohak Bhardwaj and Sanjiban Choudhury and Sebastian A. Scherer},
  title = {{Learning Heuristic Search via Imitation}},
  booktitle = {Conference on Robot Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=FemzP2S-Yc8},
}
Figure