  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.
