優先度付き計画における計算時間削減のためのグラフ彩色
Graph Coloring to Reduce Computation Time in Prioritized Planning
マルチエージェント経路探索の優先度付き計画において、結合DAGの最長経路長をグラフ彩色問題に帰着させ、分散彩色アルゴリズムで優先度を決定することで計算時間を削減する手法を提案した。
著者: Patrick Scheffe, Julius Kahle, Bassam Alrifaee
分類: cs.MA, cs.AI, cs.RO
原文アブストラクト
Distributing computations among agents in large networks reduces computational effort in multi-agent path finding (MAPF). One distribution strategy is prioritized planning (PP). In PP, we couple and prioritize interacting agents to achieve a desired behavior across all agents in the network. We characterize the interaction with a directed acyclic graph (DAG). The computation time for solving MAPF problem using PP is mainly determined through the longest path in this DAG. The longest path depends on the fixed undirected coupling graph and the variable prioritization. The approaches from literature to prioritize agents are numerous and pursue various goals. This article presents an approach for prioritization in PP to reduce the longest path length in the coupling DAG and thus the computation time for MAPF using PP. We prove that this problem can be mapped to a graph-coloring problem, in which the number of colors required corresponds to the longest path length in the coupling DAG. We propose a decentralized graph-coloring algorithm to determine priorities for the agents. We evaluate the approach by applying it to multi-agent motion planning (MAMP) for connected and automated vehicles (CAVs) on roads using, a variant of MAPF.
