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

Overview

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
astar neural_astar

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! Open In 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:

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

You might also like...
implementation of the KNN algorithm on crab biometrics dataset for CS16

crab-knn implementation of the KNN algorithm in Python applied to biometrics data of purple rock crabs (leptograpsus variegatus) to classify the sex o

A simple python implementation of A* and bfs algorithm solving Eight-Puzzle

A simple python implementation of A* and bfs algorithm solving Eight-Puzzle

A fast, pure python implementation of the MuyGPs Gaussian process realization and training algorithm.
A fast, pure python implementation of the MuyGPs Gaussian process realization and training algorithm.

Fast implementation of the MuyGPs Gaussian process hyperparameter estimation algorithm MuyGPs is a GP estimation method that affords fast hyperparamet

Implementation of core NuPIC algorithms in C++
Implementation of core NuPIC algorithms in C++

NuPIC Core This repository contains the C++ source code for the Numenta Platform for Intelligent Computing (NuPIC)

Implementation for Evolution of Strategies for Cooperation
Implementation for Evolution of Strategies for Cooperation

Moraliser Implementation for Evolution of Strategies for Cooperation Dependencies You will need a python3 (= 3.8) environment to run the code. Before

Machine Learning algorithms implementation.

Machine Learning Algorithms Machine Learning algorithms implementation. What can I find here? ML Algorithms KNN K-Means-Clustering SVM (MultiClass) Pe

This is an implementation of the QuickHull algorithm in Python. I

QuickHull This is an implementation of the QuickHull algorithm in Python. It randomly generates a set of points and finds the convex hull of this set

Python implementation of Aho-Corasick algorithm for string searching

Python implementation of Aho-Corasick algorithm for string searching

Our implementation of Gillespie's Stochastic Simulation Algorithm (SSA)

SSA Our implementation of Gillespie's Stochastic Simulation Algorithm (SSA) Requirements python =3.7 numpy pandas matplotlib pyyaml Command line usag

Comments
  • Role of guidance map

    Role of guidance map

    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.

    opened by qitop 4
  • could you please elaborate the mazes_032_moore_c8.npz file

    could you please elaborate the mazes_032_moore_c8.npz file

    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?

    opened by qitop 1
A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches

A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches. This module only provides the algorithm that infers a channel mask from some spectral statistic that measures the level of RFI contamination in a time-frequency data block. It should be useful as a reference implementation to developers who wish to integrate IQRM into an existing pipeline / search code.

Vincent Morello 7 Aug 22, 2022
An implementation of ordered dithering algorithm in python as multimedia course project

One way of minimizing the size of an image is to simply reduce the number of bits you use to represent each pixel.

null 8 Jan 15, 2022
A custom prime algorithm, implementation, and performance code & review

Colander A custom prime algorithm, implementation, and performance code & review Pseudocode Algorithm 1. given a number of primes to find, the followi

Finn Lancaster 3 Dec 17, 2021
This project is an implementation of a simple K-means algorithm

Simple-Kmeans-Clustering-Algorithm Abstract K-means is a centroid-based algorithm, or a distance-based algorithm, where we calculate the distances to

Saman Khamesian 7 Aug 9, 2022
A raw implementation of the nearest insertion algorithm to resolve TSP problems in a TXT format.

TSP-Nearest-Insertion A raw implementation of the nearest insertion algorithm to resolve TSP problems in a TXT format. Instructions Load a txt file wi

sjas_Phantom 1 Dec 2, 2021
A python implementation of the Basic Photometric Stereo Algorithm

Photometric-Stereo A python implementation of the Basic Photometric Stereo Algorithm Result Usage run Photometric_Stereo.py Code Tree |data #原始数据,tga格

null 16 Oct 11, 2022
Implementation of Apriori algorithms via Python

Installing run bellow command for installing all packages pip install -r requirements.txt Data Put csv data under this directory "infrastructure/data

Mahdi Rezaei 0 Jul 25, 2022
Implementation of an ordered dithering algorithm used in computer graphics

Ordered Dithering Project In this project, we use an ordered dithering method to turn an RGB image, first to a gray scale image and then, turn the gra

null 1 Oct 26, 2021
Implementation of Apriori Algorithm for Association Analysis

Implementation of Apriori Algorithm for Association Analysis

null 3 Nov 14, 2021
This is a Python implementation of the HMRF algorithm on networks with categorial variables.

Salad Salad is an Open Source Python library to segment tissues into different biologically relevant regions based on Hidden Markov Random Fields. The

null 1 Nov 16, 2021