[1N1-GS-5] エージェント：基礎

[1N1-GS-5-03] マルチエージェント経路探索のための厳密アルゴリズムの改良

〇柴田 航志¹、木村 慧¹、東藤 大樹¹、横尾 真¹ (1. 九州大学)

キーワード：マルチエージェントシステム、マルチエージェント経路探索

マルチエージェント経路探索 (Multi-agent Pathfinding, MAPF) 問題は，それぞれ相異なるスタートとゴールが定められたエージェントの集合を入力とし，エージェント同士の衝突が発生しない経路の割当を解とする問題である．NP困難であることが知られている，各エージェントがゴールに到達するまでに要する時間の総和の最小化について，Meta-Agent Conflict Based Search (MA-CBS) と呼ばれる有力な厳密アルゴリズムが存在する．MA-CBS の動作は，マージポリシーと呼ばれる条件に応じて変化するが，従来用いられてきた静的なマージポリシーのもとでは，一部のMAPFインスタンスにおいて膨大な実行時間を要することが知られている．そこで本論文では，アルゴリズムの性質を動的に変化させる新たなマージポリシーを提案する．また，提案したマージポリシーを実装したアルゴリズムが，従来と比較して多様なインスタンスで効率的に動作することを計算機実験で示す．