マルチエージェント経路計画の紹介グラフ上の複数エージェントに対し, 互いに衝突のない経路を計算する問題は マルチエージェント経路計画 (Multi-Agent Path Finding; MAPF) と呼ばれる. MAPF はロボット群による倉庫内での荷物搬送など, 多数の魅力的な応用があり, 2010年代前半から人工知能・ロボティクス分野で盛んに研究が行われている. 本記事は日本語のチュートリアルを提供する. お断り: 正確な話をすることが目的ではないので, 多少の不備には目を瞑ってほしい. 問題定義# まずは, どのような問題が対象か, はっきりさせておこう. 文献によってバリエーションがあるのだが, 基本的なフォームは次の通り. MAPF 問題はグラフ $G=(V, E)$, エージェントのチーム $A= \lbrace 1, 2, \ldots, n\rbrace $, 各エージェント $i \in A$ に対し
