Abstract
Planning optimal paths for multi-agent systems is computationally intensive, often requiring a trade-off between speed and solution quality. This paper presents a novel framework that integrates deep learning "intuition" with the formal guarantees of classical search. By training a convolutional neural network (CNN) via imitation learning to serve as a heuristic for Focal Search ($A^*_\omega$), the authors achieve planning speeds orders of magnitude faster than traditional $A^*$ while maintaining bounded suboptimality. The approach is validated in a complex Autonomous Valet Parking (AVP) domain, demonstrating superior success rates and efficiency compared to standard baselines.
Introduction
Multi-agent pathfinding in complex environments, such as crowded parking garages, faces the challenge of state-space explosion. While classical algorithms like $A^*$ provide optimal solutions, they rely on manually engineered "admissible" heuristics and scale poorly as the number of agents increases. Conversely, deep neural networks (DNNs) can rapidly predict paths but lack the safety and completeness guarantees required for critical applications. This research addresses the gap by using learned neural heuristics to guide a bounded suboptimal search, combining the predictive power of DNNs with the rigorous framework of Focal Search.
Methodology
The proposed framework consists of two primary components: a Policy DNN and a Focal Search algorithm.
Multi-Agent Imitation Learning
A Deep Convolutional Neural Network (CNN) is trained to mimic an expert optimal $A^*$ planner. The network processes grid-map observations and produces two outputs:
- Action Probabilities ($p$): The likelihood of a specific move being part of an optimal path.
- Value Function ($V$): An estimate of the remaining distance to the goal.
To ensure scalability, the model employs a "windowing" technique, extracting local observations around each agent. This makes the policy invariant to the total number of agents in the environment.
Focal Search ($A^*_\omega$)
The learned DNN is integrated into Focal Search, a variation of $A^*$ that maintains a "Focal Set" of nodes whose costs are within a factor $\omega$ of the best known lower bound. The search uses the DNN's potentially non-admissible heuristics to prioritize node expansion within this set. Two specific heuristics are introduced: $h_{F,len}$ (based on the value function) and $h_{F,log}$ (based on path log-likelihood).
Experimental Evaluation
The framework was evaluated in the Autonomous Valet Parking (AVP) domain. In this task, multiple robots must coordinate to escort a car through a $20 \times 20$ grid. A safety constraint requires the car's "monitor region" (the area in front of it) to be fully observed by at least one robot for movement to occur.
Training data was generated using an $A^*$ expert, and the system was tested on 100 unseen environments with varying obstacle configurations.
Key Results and Insights
- Search as a Safety Net: While "greedy" execution of the DNN policy often fails in complex scenarios, using it to guide Focal Search ensures completeness and safety.
- Coordination through Joint Learning: Centralized policies that control all robots simultaneously (MPMW) significantly outperformed individual robot policies (SPMW), highlighting the importance of baked-in coordination.
- Performance Gains: In 2-robot scenarios, the proposed $A^*_{\omega,log}$ achieved a 100% success rate, whereas vanilla $A^*$ solved only 90% within a 5-minute limit.
- Efficiency: The method found initial solutions in under 1 second on average. While the first solution was approximately 3.1x the optimal cost, an anytime version of the algorithm refined this to 2.0x the optimum within the time limit.
Conclusion
By leveraging deep learning to provide "intuition" for classical search, this framework offers a robust solution for multi-agent planning. It provides the speed necessary for real-time applications without sacrificing the mathematical guarantees of bounded suboptimality. Future work will explore Reinforcement Learning to remove the dependency on an $A^*$ expert and extend the approach to continuous dynamics.
Summary updated