多目的衝突ベース探索のためのコスト分割
Cost Splitting for Multi-Objective Conflict-Based Search
多目的マルチエージェント経路探索アルゴリズムMO-CBSの探索効率を改善するため、コスト分割と非交差コスト分割という2つの新しい分割戦略を提案し、最大2桁の高速化を実現した。
著者: Cheng Ge, Han Zhang, Jiaoyang Li, Sven Koenig
分類: cs.AI, cs.MA, cs.RO
原文アブストラクト
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.
