Learning Heuristic Search via Imitation

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 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.

14 pages

References in corpus (11)

• Continuous control with deep reinforcement learning
• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Playing Atari with Deep Reinforcement Learning
• Prioritized Experience Replay
• The FF Planning System: Fast Plan Generation Through Heuristic Search
• Dueling Network Architectures for Deep Reinforcement Learning
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• Reinforcement and Imitation Learning via Interactive No-Regret Learning
• High-speed Flight in an Ergodic Forest
• A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors
• Adaptive Information Gathering via Imitation Learning

Cited by in corpus (5)

• The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation
• Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding
• A novel approach to model exploration for value function learning
• Auxiliary Heuristics for Frontier Based Planners
• Learning Neural Parsers with Deterministic Differentiable Imitation Learning