  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.
