マルチエージェントRRT*:サンプリングベースの協調経路計画
Multi-agent RRT*: Sampling-based Cooperative Pathfinding (Extended Abstract)
RRT*を拡張し、複数エージェントの衝突しない経路を計画するMA-RRT*を提案。大規模で疎な環境では従来のA*系よりスケールしやすいことを実験で示した。
著者: Michal Čáp, Peter Novák, Jiří Vokřínek, Michal Pěchouček
分類: cs.RO, cs.AI, cs.MA
原文アブストラクト
Cooperative pathfinding is a problem of finding a set of non-conflicting trajectories for a number of mobile agents. Its applications include planning for teams of mobile robots, such as autonomous aircrafts, cars, or underwater vehicles. The state-of-the-art algorithms for cooperative pathfinding typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. Here, we propose MA-RRT*, a novel algorithm for multi-agent path planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm for finding single-agent shortest path called RRT*. We experimentally evaluate the performance of the algorithm and show that the sampling-based approach offers better scalability than the classical forward-search approach in relatively large, but sparse environments, which are typical in real-world applications such as multi-aircraft collision avoidance.
