# Subdimensional Expansion for Multi-objective Multi-agent Path Finding

arXiv: https://arxiv.org/abs/2102.01353 · HTML: https://mlsanity.com/paper/2102.01353/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 38 references that are in the map.
- First posted on arXiv 2 Feb 2021.

## Builds on (most cited first, 5 of 5)

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Modifying Optimal SAT-based Approach to Multi-agent Path-finding Problem to Suboptimal Variants](https://mlsanity.com/paper/1707.00228/) (2017)

## Built on by (most cited first, 9 of 9)

- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Multi-Objective Path-Based D* Lite](https://mlsanity.com/paper/2108.00710/) (2021)
- [Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2103.04516/) (2021)
- [Enhanced Multi-Objective A* Using Balanced Binary Search Trees](https://mlsanity.com/paper/2202.08992/) (2022)
- [Multi-objective Conflict-based Search Using Safe-interval Path Planning](https://mlsanity.com/paper/2108.00745/) (2021)
- [Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding](https://mlsanity.com/paper/2109.14695/) (2021)
- [Cost Splitting for Multi-Objective Conflict-Based Search](https://mlsanity.com/paper/2211.12885/) (2022)
- [VBMO: Voting-Based Multi-Objective Path Planning](https://mlsanity.com/paper/2308.11755/) (2023)
- [SPARC: Spatial-Aware Path Planning via Attentive Agent Communication](https://mlsanity.com/paper/2603.02845/) (2026)

## Abstract (arXiv)

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.