Introduction
Multi-Agent Pathfinding (MAPF) is a fundamental challenge in robotics and logistics, requiring a group of agents to reach their destinations without collisions. While finding optimal solutions is computationally expensive (NP-hard), Prioritized Planning (PP) offers a scalable alternative. In PP, agents are assigned priorities and plan their paths sequentially, treating higher-priority agents as moving obstacles. However, the effectiveness of PP is highly sensitive to the agent ordering; a suboptimal priority list can lead to significant delays or failure to find a solution.
Methodology: Program Synthesis via Genetic Search
To address the limitations of manual heuristics (which are often too simple) and machine learning models (which are often "black boxes"), this research proposes an automated method for synthesizing human-readable priority formulae.
The Evolutionary Framework
The authors utilize Genetic Programming (GP) to evolve arithmetic expressions from a context-free grammar. This grammar includes basic operators ($+$, $-$, $\times$, $\div$, $\sqrt{}$), constants, and 26 specific agent features, such as distance to goal and potential conflict counts. The synthesis process involves:
- Genetic Algorithm: Evolving a population of formulae through selection, mutation, and crossover based on their pathfinding performance (success rate and solution quality).
- Regularization: Applying a penalty for formula length to ensure the resulting rules remain compact and interpretable.
- Parallel Synthesis: Running multiple independent trials across computing clusters to identify the most robust expressions.
Performance and Scalability
The synthesized formulae (FML) were evaluated against standard benchmarks, including random grids, rooms, mazes, and large-scale warehouse maps with up to 900 agents.
As shown in the performance plots, FML consistently matches or exceeds the performance of state-of-the-art machine learning models (ML-T, ML-P) and significantly outperforms traditional manual heuristics like Longest Highway (LH) or Shortest Highway (SH). Notably, FML maintains high success rates even as the number of agents increases, demonstrating superior scalability in dense environments.
Interpretability and Insights
A core advantage of this approach is the transparency of the generated rules. Unlike deep learning models, the synthesized formulae are compact mathematical expressions that can be audited by human experts.
Key Findings
- Compactness: The evolved formulae average only 7 nodes, making them computationally efficient to evaluate during real-time planning.
- Feature Importance: The feature $x_7$ (mean graph distance between an agent’s goal and others' goals) appeared frequently. This indicates that successful priority logic often accounts for "goal crowding," a nuance frequently overlooked by manual rules.
- Generalization: Formulae evolved for specific scenarios often performed well on different maps, suggesting they capture fundamental geometric truths of the MAPF problem rather than over-fitting to specific data.
Conclusion
By bridging the gap between performance and interpretability, program synthesis provides a powerful tool for multi-agent coordination. The resulting formulae are not only competitive with complex ML models but also offer clear logic that can be trusted in safety-critical deployments. Future work will focus on evolving "universal" formulae capable of generalizing across all map types and further reducing the computational cost of the synthesis process itself.
Summary updated