Abstract
Conventional multi-agent path planners typically determine a path that optimizes a single objective, such as path length. Many applications, however, may require multiple objectives, say time-to-completion and fuel use, to be simultaneously optimized in the planning process. Often, these criteria may not be readily compared and sometimes lie in competition with each other. Simply applying standard multi-objective search algorithms to multi-agent path finding may prove to be inefficient because the size of the space of possible solutions, i.e., the Pareto-optimal set, can grow exponentially with the number of agents (the dimension of the search space). This paper presents an approach that bypasses this so-called curse of dimensionality by leveraging our prior multi-agent work with a framework called subdimensional expansion. One example of subdimensional expansion, when applied to A, is called M and M was limited to a single objective function. We combine principles of dominance and subdimensional expansion to create a new algorithm named multi-objective M (MOM), which dynamically couples agents for planning only when those agents have to "interact" with each other. MOM computes the complete Pareto-optimal set for multiple agents efficiently and naturally trades off sub-optimal approximations of the Pareto-optimal set and computational efficiency. Our approach is able to find the complete Pareto-optimal set for problem instances with hundreds of solutions which the standard multi-objective A* algorithms could not find within a bounded time.
Introduction
Multi-Agent Path Finding (MAPF) is a critical challenge in robotics, requiring the coordination of multiple agents to reach their respective goals without collisions. While traditional solvers focus on a single metric like total travel time, real-world scenarios often demand the simultaneous optimization of multiple, often conflicting, objectives—such as minimizing energy consumption while maximizing speed.
In such multi-objective settings, there is rarely a single "best" solution. Instead, planners seek the Pareto-optimal set: a collection of solutions where no single objective can be improved without degrading another. However, finding this set is computationally expensive, as the search space expands exponentially with both the number of agents and the number of objectives. Standard multi-objective search algorithms, such as NAMOA*, often fail to scale to multi-robot systems due to this "curse of dimensionality."
Methodology: Multi-Objective M (MOM)
To address these scalability issues, we propose MOM, an algorithm that integrates multi-objective dominance rules with the efficiency of subdimensional expansion*.
Subdimensional Expansion
The core innovation of MOM is its ability to dynamically adjust the dimensionality of the search space. Rather than planning in a massive joint-configuration space from the start, MOM initially treats each agent as an independent entity following its own individual "Pareto policy." The algorithm only "couples" agents—increasing the search dimensionality—in local regions where collisions are detected.
Key Components
- Pareto Policies: Optimal multi-objective paths are pre-computed for each agent individually to serve as high-quality heuristics.
- Dominance Pruning: The search space is kept manageable by immediately discarding partial paths that are strictly inferior to existing solutions.
- Back-propagation of Conflicts: When a collision is identified, conflict information is back-propagated to ensure the search explores the necessary joint-space to find a globally optimal resolution.
- Bounded Sub-optimality: An "Inflated MOM*" variant allows for trading off solution quality for significant speed gains, providing a guaranteed bound on the distance from the true Pareto front.
Experimental Evaluation
MOM* was evaluated against standard benchmarks, including empty grids, room maps, and complex mazes. Edge costs were randomized to simulate conflicting objectives like distance versus risk.
Key Results
- Scalability: In complex "Room" maps with 8 agents, MOM achieved a success rate of 12% for finding the entire Pareto set, whereas the baseline NAMOA failed completely (0%).
- Efficiency: MOM consistently expanded fewer states and demonstrated faster runtimes than NAMOA across all tested environments.
- Inflated Performance: The inflated variant (w=2.0) successfully solved instances with up to 20 agents in environments where exact solvers failed at 4 or 8 agents.
- Algorithm Suitability: While MOM* excelled in "Room" maps, MO-CBS (Multi-Objective Conflict-Based Search) performed better in larger, cluttered maps like
den312d, suggesting that algorithm choice should be informed by map topology.
Conclusion and Future Work
MOM* effectively bypasses the curse of dimensionality in multi-objective MAPF by leveraging the sparsity of agent interactions. While highly effective for additive costs, future work will focus on extending the framework to handle "bottleneck" objectives like makespan. Additionally, reducing the pre-processing overhead for individual Pareto policies remains a key area for improvement to support problems with a higher number of objectives.
Summary updated