Path Planning using Neural A* Search

1OMRON SINIC X2Now at DeepMind3Tokyo Institute of Technology* denotes equal contribution.


We present Neural A*, a novel data-driven search method for path planning problems. Despite the recent increasing attention to data-driven path planning, machine learning approaches to search-based planning are still challenging due to the discrete nature of search algorithms. In this work, we reformulate a canonical A* search algorithm to be differentiable and couple it with a convolutional encoder to form an end-to-end trainable neural network planner. Neural A* solves a path planning problem by encoding a problem instance to a guidance map and then performing the differentiable A* search with the guidance map. By learning to match the search results with ground-truth paths provided by experts, Neural A* can produce a path consistent with the ground truth accurately and efficiently. Our extensive experiments confirmed that Neural A* outperformed state-of-the-art data-driven planners in terms of the search optimality and efficiency trade-off. Furthermore, Neural A* successfully predicted realistic human trajectories by directly performing search-based planning on natural image inputs.

Neural A*

We reformulate a canonical A* search algorithm to be differentiable as a module referred to as the differentiable A*, by combining a discretized activation technique with basic matrix operations. This module enables us to perform an A* search in the forward pass of a neural network and back-propagate losses through every search step to other trainable backbone modules.

As illustrated in the figure above, Neural A* consists of the combination of a fully-convolutional encoder and the differentiable A* module, and is trained as follows: (1) Given a problem instance (i.e., an environmental map annotated with start and goal points), the encoder transforms it into a scalar-valued map representation referred to as a guidance map; (2) The differentiable A* module then performs a search with the guidance map to output a search history and a resulting path; (3) The search history is compared against the ground-truth path of the input instance to derive a loss, which is back-propagated to train the encoder.


Point-to-Point Shortest Path Problems

We conducted an extensive experiment to evaluate the effectiveness of Neural A* for point-to-point shortest path problems. By learning from optimal planners, Neural A* outperformed state-of-the-art data-driven search-based planners in terms of the trade-off between search optimality and efficiency.

Comparisons with SAIL [Choudhury+, 2018] and Black-box differentiation (BB-A*) [Vlastelica+, 2020]. Black pixels indicate obstacles. Start nodes (indicated by "S"), goal nodes (indicated by "G"), and found paths are annotated in red. Other explored nodes are colored in green. In the rightmost column, guidance maps learned by Neural A* are overlaid on the input maps where regions with lower costs are visualized in white.

Path Planning on Raw Image Inputs

We also address the task of planning paths directly on raw image inputs. Suppose a video of an outdoor scene taken by a stationary surveillance camera. Given planning demonstrations consisting of color images of the scene and actual trajectories of pedestrians, Neural A* can predict realistic trajectories consistent with those of pedestrians when start and goal locations are provided.

Comparisons with Black-box differentiation (BB-A*) [Vlastelica+, 2020].


# ICML2021 version
  title =      {Path Planning using Neural A* Search},
  author    = {Ryo Yonetani and
               Tatsunori Taniai and
               Mohammadamin Barekatain and
               Mai Nishimura and
               Asako Kanezaki},
  booktitle =      {Proceedings of the 38th International Conference on Machine Learning},
  pages =      {12029--12039},
  year =      {2021},
  editor =      {Meila, Marina and Zhang, Tong},
  volume =      {139},
  series =      {Proceedings of Machine Learning Research},
  month =      {18--24 Jul},
  publisher =    {PMLR},
  pdf =      {},
  url =      {},

# arXiv version
  author    = {Ryo Yonetani and
               Tatsunori Taniai and
               Mohammadamin Barekatain and
               Mai Nishimura and
               Asako Kanezaki},
  title     = {Path Planning using Neural A* Search},
  journal   = {CoRR},
  volume    = {abs/2009.07476},
  year      = {2020},
  url       = {},
  archivePrefix = {arXiv},
  eprint    = {2009.07476},
  timestamp = {Wed, 23 Sep 2020 15:51:46 +0200},
  biburl    = {},
  bibsource = {dblp computer science bibliography,}