[4D1-OS-1] OS-1

10:15 AM - 10:30 AM JST(1:15 AM - 1:30 AM UTC)

[4D1-OS-1-06] Configuration-constrained Unlabeled Multi-Agent Pathfinding

〇Takahiro Suzuki^1,2, Yuma Tamura¹, Keisuke Okumura² (1. Tohoku University, 2. National Institute of Advanced Industrial Science and Technology)

Keywords:

Multi-Agent Pathfinding,Combinatorial search

マルチエージェント経路計画（Multi-Agent Pathfinding; MAPF）は複数エージェントの衝突を避けつつ経路を求める問題であり，自動化需要の拡大を背景に近年注目を集めている．厳密解を求める手法や，大規模インスタンスに対する準最適手法など多様な解法が提案され，実用化も進む一方，現実の運用条件を扱うには既存モデルの抽象化に起因するギャップが残る．これらの課題に対して既存のアルゴリズムの直接的な適用は困難であり，対応する手法の整備が求められる．本稿では，この中でも配置制約を課したunlabeled MAPFを対象に二つの問題を取り上げ，ケーススタディを行う．各問題に対し，厳密解が必要な場合の整数計画法（ILP）に基づくアプローチと，大規模オートメーションに不可欠な高速に動作する準最適アルゴリズムを提案し，実験で計算時間と得られる解の質を評価する．