Official implementation of "Path Planning using Neural A* Search" (ICML-21)

Path Planning using Neural A* Search (ICML 2021)

This is a repository for the following paper:

Ryo Yonetani*, Tatsunori Taniai*, Mohammadamin Barekatain, Mai Nishimura, Asako Kanezaki, "Path Planning using Neural A* Search", ICML, 2021 [paper] [project page]

TL;DR

Neural A* is a novel data-driven search-based planner that consists of a trainable encoder and a differentiable version of A* search algorithm called differentiable A* module. Neural A* learns from demonstrations to improve the trade-off between search optimality and efficiency in path planning and also to enable the planning directly on raw image inputs.

A* search	Neural A* search

Overview

This branch presents a minimal example for training and evaluating Neural A* on shortest path problems.
For reproducing experiments in our ICML'21 paper, please refer to icml2021 branch.
For creating datasets used in our experiments, please visit planning datasets repository.

Getting started

The code has been tested on Ubuntu 18.04.5 LTS.
Try Neural A* on Google Colab!
See also docker-compose.yml and docker/Dockerfile to reproduce our environment.

FAQs

Data format (c.f. #1 (comment))

The datafile mazes_032_moore_c8.npz was created using our data generation script in a separate repository https://github.com/omron-sinicx/planning-datasets.

In the data, arr_0 - arr_3 are 800 training, arr_4 - arr_7 are 100 validation, and arr_8 - arr_11 are 100 test data, which contain the following information (see also https://github.com/omron-sinicx/planning-datasets/blob/68e182801fd8cbc4c25ccdc1b14b8dd99d9bbc73/generate_spp_instances.py#L50-L61):

arr_0, arr_4, arr_8: binary input maps
arr_1, arr_5, arr_9: one-hot goal maps
arr_2, arr_6, arr_10: optimal directions (among eight directions) to reach the goal
arr_3, arr_7, arr_11: shortest distances to the goal

For each problem instance, the start location is generated randomly when __getitem__ is called:

neural-astar/neural_astar/utils/data.py

Line 114 in e6e626c

start_map = self.get_random_start_map(opt_dist)

Citation

# ICML2021 version
@InProceedings{pmlr-v139-yonetani21a,
  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 =      {http://proceedings.mlr.press/v139/yonetani21a/yonetani21a.pdf},
  url =      {http://proceedings.mlr.press/v139/yonetani21a.html},
}

# arXiv version
@article{DBLP:journals/corr/abs-2009-07476,
  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       = {https://arxiv.org/abs/2009.07476},
  archivePrefix = {arXiv},
  eprint    = {2009.07476},
  timestamp = {Wed, 23 Sep 2020 15:51:46 +0200},
  biburl    = {https://dblp.org/rec/journals/corr/abs-2009-07476.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

Acknowledgments

This repository includes some code from RLAgent/gated-path-planning-networks [1] with permission of the authors and from martius-lab/blackbox-backprop [2].

References

Hi, I have a some confusions regarding understanding the role of guidance map.

the paper says

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; The differentiable A* module then performs a search with the guidance map to output a search history and a resulting path.

Guidance map is U-NET encoder and It is performing segmentation right 1-)What I understand is that initially, on the raw or binary image it outputs the the segmented regions containing blocked and unblocked areas right?

2-)scalar-valued map representation: Does it also outputs the A* path when we backpropagate by taking start and goal nodes? and then later on we update these scalar values termed as guidance cost using differentiable A module* to find the best optimal path as Figure 2 shows.

Add a simple working example on learning neural astar on raw image inputs, maybe using warcraft maps provided at https://edmond.mpdl.mpg.de/dataset.xhtml?persistentId=doi:10.17617/3.YJCQ5S

Untitled

I opened the .npz file that is given.

Can you please tell me what dataset it is and how did you create it?

Also the what are these dimensions that are highlighted. I assume 800 is the training size and 32 * 32 is the size of image that is mentioned in the paper

800 is the input map 800 * 1 is 1 hot matrix representing start position and other 800 * 1 representing the goal position? What is 800 * 8 * 1 representing?

and the rest 100 represents the validation and test split?