情報処理学会 第80回全国大会講演要旨
2Q-05
時間拡張グラフ上のナンバーリンクパズルとしてのマルチエージェント経路発見
マルチエージェント経路発見(Multi-Agent Path
Finding(MAPF))とは,グリッド平面上に配置された複数のエージェントに対して,互いの衝突を回避しつつ,それぞれのエージェントを初期状態から目標状態へ移動させる最短経路を求める問題である.本研究では,MAPFを時間拡張グラフ上のナンバーリンクパズルと見なし,制約最適化問題に基づくMAPFの新しい定式化を提案する.また,既存の制約最適化アルゴリズムを用いた簡単な実験結果を報告する.
Finding(MAPF))とは,グリッド平面上に配置された複数のエージェントに対して,互いの衝突を回避しつつ,それぞれのエージェントを初期状態から目標状態へ移動させる最短経路を求める問題である.本研究では,MAPFを時間拡張グラフ上のナンバーリンクパズルと見なし,制約最適化問題に基づくMAPFの新しい定式化を提案する.また,既存の制約最適化アルゴリズムを用いた簡単な実験結果を報告する.
