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