The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem
of finding the Pareto-optimal frontier of collision-free paths for a team of
agents while minimizing multiple cost metrics. Examples of such cost metrics
include arrival times, travel distances, and energy this http URL this paper,
we focus on the Multi-Objective Conflict-Based Search (MO-CBS) algorithm, a
state-of-the-art MO-MAPF algorithm. We show that the standard splitting
strategy used by MO-CBS can lead to duplicate search nodes and hence can
duplicate the search effort that MO-CBS needs to make. To address this issue,
we propose two new splitting strategies for MO-CBS, namely cost splitting and
disjoint cost splitting. Our theoretical results show that, when combined with
either of these two new splitting strategies, MO-CBS maintains its completeness
and optimality guarantees. Our experimental results show that disjoint cost
splitting, our best splitting strategy, speeds up MO-CBS by up to two orders of
magnitude and substantially improves its success rates in various settings.

本文提出了两种新的拆分策略 (cost splitting 和 disjoint cost splitting)，用于解决 Multi-Objective Conflict-Based Search (MO-CBS) 算法中的重复搜索问题，并证明了这些拆分策略与 MO-CBS 既完整又最优。实验结果表明，disjoint cost splitting 是最佳的拆分策略，可将 MO-CBS 加速两个数量级并在各种情景下显著提高其成功率。