Source-linked AI summary
Path Planning using Neural A* Search
Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, Asako Kanezaki
TL;DR
Search-based planning is difficult to train because its incremental decisions are discrete. Neural A* makes A* differentiable, combines it with an encoder that produces guidance maps, and outperforms state-of-the-art data-driven planners while also predicting trajectories from raw images.
Problem
Search-based planning remains difficult to train end-to-end because discrete incremental search steps make back-propagation non-trivial and can require rich expert annotations.
Method
Neural A* combines a fully convolutional encoder that produces guidance maps with a differentiable A* module supporting back-propagation through search.
Results
Neural A* outperformed state-of-the-art data-driven planners on the search optimality–efficiency trade-off and more accurately predicted pedestrian trajectories from raw surveillance images.
Takeaways & Limitations
The approach provides a unified search-based planner for near-optimal map planning and planning directly from raw image inputs.
Takeaways & Limitations
The current implementation assumes grid-world environments with unit node costs and does not yet extend to high-dimensional or continuous state spaces.
Abstract
from arXiv · showhide
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. Project page: https://omron-sinicx.github.io/neural-astar/
1. Introduction
Neural A* addresses the difficulty of training search-based planners by making A* differentiable and coupling it with an encoder. It unifies efficient near-optimal search and planning directly from raw images, outperforming prior data-driven planners in reported evaluations.
- Scope: The method targets both near-optimal point-to-point search and path planning directly on raw images.The two scenarios use optimal-planner paths or human-annotated trajectories as ground truth, respectively.
- Motivation: Search-based planning is difficult to train with back-propagation because incremental search steps are discrete.Existing alternatives may require fine-grained expert annotations or exhaustive heuristic pre-computation.
- Approach: A convolutional encoder transforms each planning instance into a guidance map, while differentiable A* produces a search history and resulting path.Training minimizes the discrepancy between search histories and ground-truth paths, teaching the encoder to capture useful visual cues.
- Approach: Neural A* addresses this challenge by reformulating canonical A* as a differentiable module within a neural planner.The module supports forward-pass search and back-propagation through search steps to train other components.
- Results: Neural A* outperformed state-of-the-art data-driven search-based planners on the trade-off between search optimality and efficiency.It also predicted pedestrian trajectories from raw surveillance images more accurately than the cited baselines and imitation learners.
2. Preliminaries
The paper formulates point-to-point path planning on a graph and describes standard A* as iterative candidate selection and neighbor expansion. Its setup represents either explicit binary costs or raw images and learns from corresponding optimal or human paths.
- Path planning problem: A path-planning problem seeks the lowest-cost connected path between designated start and goal nodes in an environmental graph.Nodes represent locations, edges represent potentially valid movements, and node-dependent movement costs determine path cost.
- Experimental setup: The study focuses on an eight-neighbor grid world with unit costs for passable nodes and infinite costs for obstacles.This setting guarantees that the objective is the lowest-cost path under the specified grid and obstacle assumptions.
- A* search: Standard A* repeatedly selects the most promising candidate, expands its neighbors, and stops when the goal enters the closed list.The solution path is then recovered by backtracking through stored parent nodes.
- A* search: A* selects nodes using the sum of accumulated path cost g(v) and heuristic estimate h(v) to the goal.The open list stores candidates, while selected nodes are recorded in the closed-list search history.
- A* search: Neighbor expansion considers nodes adjacent to the selected node that are absent from both open and closed lists.These neighbors become candidates for subsequent iterations.
- Data-driven setup: The data-driven setup represents movement costs either explicitly as a binary passability map or implicitly through a raw colored image.Ground-truth paths come from an optimal planner for binary maps and human annotators for raw images.
3. Neural A* Search
Neural A* combines an encoder-generated guidance map with a differentiable A* module, enabling end-to-end learning from search outputs and ground-truth paths. Matrix-based search updates, path-based loss supervision, and gradient detachment support accurate and efficient planning.
- Neural A* overview: Neural A* transforms each problem instance into a guidance map whose costs steer differentiable A* toward efficient paths.The encoder produces node-wise guidance costs, and the search minimizes their accumulated cost.
- Differentiable A* module: Binary matrices represent open, closed, neighbor, start, goal, and selected-node states, while cost matrices encode accumulated, heuristic, and guidance values.These representations allow A* operations to be executed with matrix operations over the map.
- Node selection: A discretized activation makes node selection differentiable by using argmax behavior during the forward pass and identity behavior during back-propagation.The open-list mask restricts selection to currently candidate nodes, while the temperature parameter controls the exponential weighting.
- Node expansion: Convolution with a fixed neighborhood kernel expands adjacent passable nodes while masking obstacles and nodes already in the open or closed lists.Preserving the obstacle mask retains the original graph topology and keeps the differentiable search complete.
- Cost updates: Guidance costs are updated by assigning new costs to newly opened neighbors and retaining the lower cost for neighbors already in the open list.The update combines the selected node’s accumulated cost with one-step guidance costs.
- Training: Mean L1 loss between the closed-list search output and the ground-truth path penalizes both missed and excessive node selections.Detaching selected recurrent variables simplifies back-propagation, stabilizes training, and reduces memory consumption; fully enabling gradients caused out-of-memory failures with 16GB GPU RAM.
- Encoder and batching: A fully convolutional encoder learns visual cues conditioned on start and goal positions, while goal-verification flags let mini-batch samples stop updating after reaching their goals.The encoder can use map geometry or visual appearance, including dead ends, bypasses, road colors, and textures.
4. Experiments
Experiments evaluate Neural A* on synthetic and real-world path-planning settings, including shortest-path search, adaptive guidance, and raw-image planning. The method generally improves the optimality–efficiency trade-off, while remaining limited to grid worlds with unit node costs.
- Experimental setup: Experiments assess search optimality and efficiency on public path-planning datasets with obstacle annotations.The study includes MP, Tiled MP, and CSM environments, with additional complexity and runtime analyses described for Neural A*.
- Experimental setup: Neural A* combines an encoder with differentiable A* search to produce closed-list matrices and solution paths.The encoder generates guidance maps, while the search module iteratively selects nodes and updates search state.
- Quantitative results: Neural A* outperformed baseline methods on both path optimality and the efficiency trade-off measured by Opt and Hmean.SAIL and SAIL-SL sometimes explored fewer nodes but often had lower optimality, while BB-A* was consistently outperformed by Neural A*.
- Qualitative results: Guidance maps assigned high costs to dead ends and low costs to bypasses, adapting the search when start and goal locations changed.The entrance to a U-shaped dead end was blocked when the dead end lay between start and goal, but opened when the goal was inside it.
- Ablation study: Removing start and goal inputs degraded performance, especially optimality, while straight-through Gumbel-softmax caused complete planning failure.Using mean squared loss instead of mean L1 loss produced comparable performance.
- Limitations: The current implementation assumes grid-world environments with unit node costs.Extending Neural A* to high-dimensional or continuous state spaces is left for future work.
5. Path Planning on Raw-Image Inputs
Neural A* is also evaluated as a planner that predicts pedestrian trajectories directly from raw surveillance images. It produces paths closer to observed trajectories than BB-A*, although both methods can fail when multiple routes are plausible.
- Task and dataset: The raw-image task predicts pedestrian trajectories from color surveillance images when start and goal locations are provided.Training demonstrations pair local video-frame patches with actual pedestrian trajectories from the Stanford Drone Dataset.
- Evaluation: Table 3 evaluates predicted and ground-truth trajectories using chamfer distance with bootstrap means and 95% confidence bounds.The metric measures dissimilarity between predicted and observed pedestrian paths.
- Results: Neural A* significantly outperformed BB-A* on trajectory prediction.Qualitative examples show Neural A* often followed roads and produced paths closer to ground-truth trajectories.
- Results: Both methods sometimes failed when destinations admitted multiple possible routes.A generative framework that samples multiple paths is suggested as a possible extension.
6. Related Work
Related path-planning work includes sampling-based, reactive, and search-based approaches, each addressing different planning settings. Neural A* positions differentiable search as a unified approach to efficient near-optimal planning and planning directly from raw images.
- Sampling-based planning: Sampling-based planners explore high-dimensional state spaces but must identify regions worth sampling efficiently.Learning-based methods have been used to learn important regions or exploration strategies from demonstrations and prior planning experiences.
- Reactive planning: Reactive planners learn next actions from current states using supervised learning or inverse reinforcement learning.These approaches determine local movements rather than performing explicit search over paths.
- Search-based planning: Search-based planning is advantageous for finding valid paths in fine grid maps and has supported both efficient near-optimal search and raw-image planning.Prior data-driven methods extended heuristic planners for these two scenarios, while Neural A* combines them through differentiable search.
7. Conclusion
Neural A* is a data-driven search-based planner with a differentiable A* algorithm. It learns from demonstrations to improve the trade-off between search optimality and efficiency while enabling planning from raw image inputs.
- Neural A* combines data-driven planning with a differentiable A* algorithm.
- The planner learns from demonstrations to improve the trade-off between search optimality and efficiency.
- Neural A* also enables path planning directly from raw image inputs.
- Experiments on multiple public datasets demonstrated Neural A*'s effectiveness over state-of-the-art planners.
A.1. Dataset Creation
The supplementary experiments used reproducible dataset-generation procedures, varied start and goal locations, and selected hyper-parameters using validation performance. Dataset construction covered map-based path planning and pedestrian trajectories.
- Dataset generation: Dataset generation used fixed random seeds to ensure reproducibility.The authors direct readers to the project code for the generation procedures.
- Map datasets: MP, Tiled-MP, and CSM experiments randomized start and goal locations instead of using consistent predefined locations.
- Map datasets: Training starts were sampled from regions above the 55th cost percentile, while validation and test maps used six and 15 fixed starts, respectively.Validation used 2 × 3 = 6 starts and testing used 5 × 3 = 15 starts per map.
- Pedestrian trajectories: SDD trajectories were randomly trimmed to 300–600 timesteps at 2.5fps, and path simplicity was measured using straight-line distance divided by trajectory length.
- Hyper-parameters: Final hyper-parameters were selected using MP validation Hmean scores, with each experiment run once using fixed random seeds.
- Hyper-parameters: A* tie-breaking added 0.001 times Euclidean distance to the heuristic and was used for all A*-based methods.
- Hyper-parameters: Weighted A* used the criterion (1 −w) · g(v) + w · h(v) with w = 0.8 throughout the experiments.
A.3. Computing Infrastructure and Training Time
Experiments ran on V100 GPU servers with a 48-core Xeon CPU and 768GB memory. Training took approximately 50 minutes on MP and 35 hours on Tiled MP and CSM for Neural A* and Neural BF.
- Infrastructure: Experiments used Ubuntu 18.04.3, NVIDIA V100 GPUs, a 48-core Intel Xeon Gold 6252 CPU, and 768GB memory.
- Training time: Neural A* and Neural BF training took approximately 50 minutes on MP and 35 hours on Tiled MP and CSM.MP used 100 epochs over 800 maps; Tiled MP and CSM used 400 epochs over 3,200 maps.
- Additional analysis: Additional qualitative results and performance analyses were reported for Neural A* and related planners.
B.1. Comparisons with Imitation Learning Methods
Compared with imitation-learning planners, Neural A* generally achieved stronger planning performance. MMP preserved guaranteed success but was outperformed on key metrics, while GPPN and VIN showed failures under some settings.
- Compared methods: The comparison included Maximum Margin Planning, Value Iteration Network, and Gated Path Planning Network.These methods were selected as imitation-learning approaches relevant to path planning.
- Compared methods: MMP used A* search with an estimated cost function, whereas VIN and GPPN were evaluated as reactive planners.
- Results: MMP ensured 100% planning success but was consistently outperformed by Neural A* on Opt, Exp, and Hmean.
- Results: GPPN achieved a higher Opt score than Neural A* on Tiled MP but did not always find valid paths.
- Results: GPPN and VIN completely failed to learn on SDD under large-map and limited-demonstration conditions.
B.2. Path Length Optimality Evaluation
Neural A* is evaluated by comparing optimal path length with produced path length, using a ratio maximized at 100% for optimal paths. It produced the most nearly optimal paths across all datasets.
- The path-length ratio is |P̄|/|P| × 100, where higher values indicate greater path optimality.The metric compares optimal path length P̄ with predicted path length P and reaches 100% when the path is optimal.
- Neural A* produced the most nearly optimal paths across all evaluated datasets.
- The evaluation follows prior work by introducing a path-optimality metric alongside other metrics.
B.3. Computational Complexity and Runtime Analysis
Differentiable A* is the main training-time computational bottleneck because its matrix operations involve all nodes, while standard A* can replace it at test time. Runtime experiments used tiled maps of increasing size and found reduced runtimes with guidance maps, including on larger maps.
- Computational complexity: Training-phase differentiable A* complexity is O(k|V|) in space and time, where k is the number of search steps.In terms of true path length d, best- and worst-case complexities are O(d|V|) and O(bd|V|), respectively.
- Computational complexity: After training, replacing differentiable A* with standard A* yields O(d) best-case and O(bd) worst-case planning complexity without changing testing behavior.
- Runtime evaluation: Runtime measurements used a standard A* implementation on a single CPU core and Neural A* on a single GPU, with repeated trials after warm-up.
- Runtime evaluation: Neural A* reduced A* runtimes with guidance maps and generalized from 64 × 64 training maps to larger map sizes.Runtime experiments used 50-map sets at 64 × 64, 128 × 128, and 256 × 256 resolutions.