時空間協調経路探索のための非同期分散アルゴリズム
Asynchronous Decentralized Algorithm for Space-Time Cooperative Pathfinding
優先度付き計画を分散環境向けに非同期化したADPPと中断可能版IADPPを提案し、各エージェントが他者の経路更新に即応して局所計画を再実行できるようにした。正しさを証明し合成領域で評価した。
著者: Michal Čáp, Peter Novák, Jiří Vokřínek, Michal Pěchouček
分類: cs.AI, cs.DC, cs.RO
原文アブストラクト
Cooperative pathfinding is a multi-agent path planning problem where a group of vehicles searches for a corresponding set of non-conflicting space-time trajectories. Many of the practical methods for centralized solving of cooperative pathfinding problems are based on the prioritized planning strategy. However, in some domains (e.g., multi-robot teams of unmanned aerial vehicles, autonomous underwater vehicles, or unmanned ground vehicles) a decentralized approach may be more desirable than a centralized one due to communication limitations imposed by the domain and/or privacy concerns. In this paper we present an asynchronous decentralized variant of prioritized planning ADPP and its interruptible version IADPP. The algorithm exploits the inherent parallelism of distributed systems and allows for a speed up of the computation process. Unlike the synchronized planning approaches, the algorithm allows an agent to react to updates about other agents' paths immediately and invoke its local spatio-temporal path planner to find the best trajectory, as response to the other agents' choices. We provide a proof of correctness of the algorithms and experimentally evaluate them on synthetic domains.
