/Learning Heuristic Search via Imitation

Learning Heuristic Search via Imitation

Mohak Bhardwaj, Sanjiban Choudhury and Sebastian Scherer
Proceedings of the 1st Annual Conference on Robot Learning, Vol. 78, pp. 271-280, October, 2017

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


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. Open-source code and details can be found here: https://goo.gl/YXkQAC.

BibTeX Reference
author = {Mohak Bhardwaj and Sanjiban Choudhury and Sebastian Scherer},
title = {Learning Heuristic Search via Imitation},
booktitle = {Proceedings of the 1st Annual Conference on Robot Learning},
sponsor = {ONR and NASA},
publisher = {Proceedings of Machine Learning Research},
grantID = {N000141310821 and NNX17CS56C},
month = {October},
year = {2017},
volume = {78},
pages = {271-280},
keywords = {learning, heuristic, search, imitation, reinforcement learning, planning},