Path Planning using Neural A* Search

  • 2020-09-16 05:22:44
  • Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, Asako Kanezaki
  • 25

Abstract

We present Neural A*, a novel data-driven search algorithm for path planningproblems. Although data-driven planning has received much attention in recentyears, little work has focused on how search-based methods can learn fromdemonstrations to plan better. In this work, we reformulate a canonical A*search algorithm to be differentiable and couple it with a convolutionalencoder to form an end-to-end trainable neural network planner. Neural A*solves a path planning problem by (1) encoding a visual representation of theproblem to estimate a movement cost map and (2) performing the A* search on thecost map to output a solution path. By minimizing the difference between thesearch results and ground-truth paths in demonstrations, the encoder learns tocapture a variety of visual planning cues in input images, such as shapes ofdead-end obstacles, bypasses, and shortcuts, which makes estimated cost mapsinformative. Our extensive experiments confirmed that Neural A* (a)outperformed state-of-the-art data-driven planners in terms of the searchoptimality and efficiency trade-off and (b) predicted realistic pedestrianpaths by directly performing a search on raw image inputs.

 

Quick Read (beta)

loading the full paper ...