# A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 51 references that are in the map.
- First posted on arXiv 11 Jan 2021.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/1812.06355/) (2018)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier](https://mlsanity.com/paper/2006.10302/) (2020)
- [Scalable Many-Objective Pathfinding Benchmark Suite](https://mlsanity.com/paper/2010.04501/) (2020)

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

- [Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree](https://mlsanity.com/paper/2307.00663/) (2023)
- [Enhanced Multi-Objective A* with Partial Expansion](https://mlsanity.com/paper/2212.03712/) (2022)
- [Search-Based Path Planning in Interactive Environments among Movable Obstacles](https://mlsanity.com/paper/2410.18333/) (2024)
- [Multi-Objective Search: Algorithms, Applications, and Emerging Directions](https://mlsanity.com/paper/2510.25504/) (2025)

## Abstract (arXiv)

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. The goal of the problem is thus to find a Pareto-optimal set of solutions instead of a single optimal solution. Naively applying existing multi-objective search algorithms, such as multi-objective A* (MOA*), to multi-agent path finding may prove to be inefficient as the dimensionality of the search space grows exponentially with the number of agents. This article presents an approach named Multi-Objective Conflict-Based Search (MO-CBS) that attempts to address this so-called curse of dimensionality by leveraging prior Conflict-Based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We also develop several variants of MO-CBS to improve its performance. We prove that MO-CBS and its variants can compute the entire Pareto-optimal set. Numerical results show that MO-CBS outperforms MOM*, a recently developed state-of-the-art multi-objective multi-agent planner.