概要: 協調的タスク順序付けおよびマルチエージェント経路探索（CTS-MAPF）問題では、エージェントが衝突を回避しながらタスクの連なり（シーケンス）を達成する必要があり、組合せ的な複雑さにより大きな課題が生じます。本研究では、構成（コンフィギュレーション）ベースのCTS-MAPF計画パラダイムを拡張する階層型フレームワークCTS-PLLを提案します。主な拡張点は2つで、1つ目は、局所再計画のために完全計画法を活用する、ロックエージェントの検出と解放のメカニズムです。2つ目は、Large Neighborhood Search（LNS）に基づくいつでも改良（anytime refinement）手続きです。これらの追加により、高密度な環境において頑健性が確保され、解の質を継続的に向上させられます。疎なベンチマークおよび密なベンチマークの双方にわたる大規模な評価の結果、CTS-PLLは既存手法と比べてより高い成功率と解の質を達成しつつ、競争力のある計算時間効率も維持することが示されました。さらに、実世界のロボット実験により、本アプローチが実際の運用において実現可能であることが確認されています。
CTS-PLL：協調タスク順序付けとマルチエージェント経路探索のための堅牢でいつでも動作可能なフレームワーク
arXiv cs.RO / 2026/3/27
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、タスク順序を計画しつつエージェント間の衝突を回避する、協調タスク順序付けとマルチエージェント経路探索（CTS-MAPF）問題のための階層型フレームワークCTS-PLLを提案する。
- CTS-PLLは、ロックエージェントの検出・解放メカニズムを追加することで、混雑した環境における堅牢性を向上させる。このメカニズムは、計画のデッドロックを解消するために完全な局所再計画を引き起こす。
- また、計算時間が許す限り解の品質を継続的に改善するための、Large Neighborhood Search（LNS）を用いたいつでも動作可能な改良手続きを導入する。
- 疎および密の両方のベンチマークでの実験により、従来手法よりも成功率と解の品質が高く、かつ計算時間効率も競争力を維持することが示される。
- 実環境でのロボット実験により、この手法がシミュレーションの範囲を超えて実現可能であることを実証する。
