论文标题
基于多目标冲突的搜索成本分配
Cost Splitting for Multi-Objective Conflict-Based Search
论文作者
论文摘要
多目标多试路径发现（MO-MAPF）问题是为一组代理团队找到无碰撞路径的帕累托最佳前沿的问题，同时最大程度地减少了多个成本指标。此类成本指标的示例包括到达时间，旅行距离和能源消耗。在本文中，我们专注于基于冲突的搜索（MO-CBS）算法，这是一种最先进的MO-MAPF算法。我们表明，MO-CB使用的标准分裂策略可以导致重复的搜索节点，因此可以复制Mo-CBS所需的搜索工作。为了解决这个问题，我们提出了针对MO-CB的两种新的拆分策略，即成本分裂和分离成本分裂。我们的理论结果表明，与这两种新的分裂策略中的任何一个相结合，Mo-CBS都保持其完整性和最佳保证。我们的实验结果表明，脱节成本分裂，我们最好的分裂策略，将MO-CBS加快了多达两个数量级，并在各种环境中大大提高了其成功率。
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 consumption.In 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.
