TL;DR
MOM* (Multi-Objective M*) is a new algorithm that solves the complex problem of finding conflict-free paths for multiple robots when there are several conflicting goals, such as minimizing both travel time and energy use. By leveraging "subdimensional expansion"—only coordinating robots when they actually collide—MOM* avoids the exponential explosion of the search space and finds the full set of Pareto-optimal solutions much faster than traditional methods.
What Problem Does This Paper Address?
In Multi-Agent Path Finding (MAPF), the goal is to move a fleet of robots to their destinations without collisions. Most existing solvers focus on a single objective, like minimizing the total arrival time. However, real-world missions often involve trade-offs: a drone might need to balance speed against battery consumption or avoid high-risk areas.
When you have multiple objectives, there isn't just one "best" path; instead, there is a Pareto-optimal set—a collection of solutions where you cannot improve one objective (e.g., time) without making another (e.g., fuel) worse. Finding this set is notoriously difficult because the search space grows exponentially with both the number of agents and the number of objectives. Standard multi-objective search algorithms (like NAMOA*) quickly become overwhelmed when applied to multi-robot systems.
Methods
The authors introduce MOM*, which combines the efficiency of the M* algorithm with multi-objective dominance rules. Its core components include:
- Subdimensional Expansion: Instead of planning in a massive joint-configuration space for all robots at once, MOM* starts by letting each robot follow its own individual multi-objective "Pareto policy." The algorithm only "couples" robots (increasing the search dimensionality) in local areas where collisions are detected.
- Pareto Policies: Before the main search, the algorithm pre-computes optimal multi-objective paths for each robot individually. These serve as high-quality heuristics to guide the multi-agent search.
- Dominance Pruning: To keep the search manageable, MOM* uses dominance rules to immediately discard any partial path that is strictly worse than another path already discovered.
- Bounded Sub-optimality (Inflated MOM*): For very large problems, the authors provide a version that uses "inflated" heuristics. This allows the user to trade off a bit of solution quality for a massive boost in speed, providing a guaranteed bound on how far the results are from the true Pareto front.
Datasets
The researchers evaluated MOM* using standard benchmarks from the MAPF community (movingai.com), specifically:
- Empty Grids: A simple 16x16 open space.
- Room Maps: A 32x32 grid with internal walls and doorways.
- Maze Maps: A 32x32 complex maze.
- Large-scale Maps: The
den312dmap (65x81), representing a more realistic, cluttered environment. Edge costs were generated as random vectors to simulate conflicting objectives (e.g., distance vs. risk).
Key Insights and Ideas
- Sparsity of Interaction: The "aha moment" is the realization that in most multi-robot tasks, robots only interfere with each other occasionally. By treating them as independent until a conflict occurs, you can bypass the "curse of dimensionality" for most of the planning process.
- Back-propagation of Conflicts: When a collision is found at a specific location, MOM* doesn't just fix it there; it "back-propagates" that conflict information to earlier states. This ensures that the search explores the necessary joint-space to find a globally optimal, conflict-free resolution.
- Heuristic Bottlenecks: The paper highlights that as the number of objectives ($M$) increases, the pre-processing time to compute individual Pareto policies becomes a significant bottleneck, jumping from fractions of a second ($M=2$) to nearly two minutes ($M=4$).
Key Results
- Superior Scalability: In the "Room" map with 8 agents, MOM* achieved a success rate of 12% for finding the entire Pareto set, whereas the baseline NAMOA* failed to solve a single instance (0%).
- Speedup: MOM* consistently expanded fewer states and ran faster than NAMOA* across all tested maps.
- Inflated Performance: The "Inflated MOM*" variant showed impressive scalability. With a weight of $w=2.0$, it successfully solved instances with up to 20 agents in complex environments where exact solvers failed at just 4 or 8 agents.
- No Universal Winner: Interestingly, MOM* outperformed MO-CBS (Multi-Objective Conflict-Based Search) in "Room" maps, but MO-CBS performed better in the
den312dmap, suggesting that the choice of algorithm should depend on the map's topology.
Limitations and Future Work
- Additive Costs Only: The current framework assumes costs are additive (like total fuel). It does not yet handle "bottleneck" objectives like makespan (the time the last robot arrives), which is a common requirement in robotics.
- Pre-processing Overhead: The time required to compute Pareto policies for individual agents grows rapidly with the number of objectives, limiting the approach for problems with many (e.g., >5) objectives.
- Future Directions: The authors suggest extending the method to other cost types, exploring SAT-based multi-objective methods, and investigating evolutionary algorithms for approximating the Pareto set in even larger systems.
Summary updated