Path Planning using Neural A* Search
Authors: Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, Asako Kanezaki
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. In this section, we first conduct an extensive experiment to evaluate the effect of Neural A* on the search optimality and efficiency trade-off, i.e., how efficiently Neural A* search can find near-optimal paths for point-to-point shortest path problems. |
| Researcher Affiliation | Collaboration | Ryo Yonetani * 1 Tatsunori Taniai * 1 Mohammadamin Barekatain 1 2 Mai Nishimura 1 Asako Kanezaki 3 *Equal contribution 1OMRON SINIC X, Tokyo, Japan 2Now at Deep Mind, London, UK. 3Tokyo Institute of Technology, Tokyo, Japan. Correspondence to: Ryo Yonetani <ryo.yonetani@sinicx.com>. |
| Pseudocode | Yes | Algorithm 1 A* Search Input: Graph G, movement cost c, start vs, and goal vg Output: Shortest path P. The complete algorithm of Neural A* is summarized in Algorithm 2. |
| Open Source Code | Yes | 1Project page: https://omron-sinicx.github.io/ neural-astar/. The project page states: "The code for Neural A* is available at GitHub!" linking to https://github.com/omron-sinicx/neural-astar |
| Open Datasets | Yes | Motion Planning (MP) Dataset: A collection of eight types of grid-world environments with distinctive obstacle shapes, created by Bhardwaj et al. (2017). City/Street Map (CSM) Dataset: A collection of 30 city maps with explicit obstacle annotations as binary images, organized by Sturtevant (2012). We used Stanford Drone Dataset (SDD) (Robicquet et al., 2016). |
| Dataset Splits | Yes | For each map, we created problem instances by randomly picking out a single goal from one of the four corner regions of the map as well as one, six, and fifteen start locations for training, validation, and test splits, respectively, from areas sufficiently distant from the goal. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., exact GPU/CPU models, memory amounts, or detailed computer specifications) used for running its experiments. |
| Software Dependencies | No | As the encoder, we adopted U-Net (Ronneberger et al., 2015) with the VGG-16 backbone (Simonyan & Zisserman, 2015) implemented by Yakubovskiy (2020)... All the models were trained using the RMSProp optimizer... While specific software components are named, explicit version numbers for frameworks or libraries are not provided. |
| Experiment Setup | Yes | As the encoder, we adopted U-Net (Ronneberger et al., 2015) with the VGG-16 backbone (Simonyan & Zisserman, 2015) implemented by Yakubovskiy (2020), where the final layer was activated by the sigmoid function to constrain guidance maps to be Φ [0, 1]V. For the differentiable A* module, we used the Chebyshev distance as the heuristic function H suitable for the eightneighbor grid-world (Patel, 1997). The Euclidean distance multiplied by a small constant (0.001) was further added to H for tie-breaking. The temperature τ in Eq. (3) was empirically set to the square root of the map width. All the models were trained using the RMSProp optimizer, with the mini-batch size, the number of epochs, and the learning rate set to (100, 100, 0.001) for the MP dataset and (100, 400, 0.001) for the Tiled MP and CSM datasets. |