マルチエージェント経路探索のための厳密アルゴリズムの改良

DOI

書誌事項

タイトル別名
  • An improved exact algorithm for multi-agent pathfinding problems

説明

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

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ