閉ループ多エージェント経路探索のための適応ホライズン競合ベース探索

- 大規模ロボット群の協調問題である Multi-Agent Path Finding (MAPF) 向けの閉ループアルゴリズム。 - 名称は Anytime Closed-Loop Conflict-Based Search (ACCBS)。 - 有限ホライズンの Conflict-Based Search (CBS) を基盤とし、Model Predictive Control (MPC) の iterative horizon-deepening に着想を得たホライズン変更機構を備える。 - 計算予算に応じて計画ホライズンを動的に調整し、単一の constraint tree を再利用してホライズン間をシームレスに遷移する。 - 予算増加に伴い漸近最適性を持ち、anytime 挙動を示す。

- 既存手法は open-loop planner か、信頼できる性能保証のない closed-loop heuristic に大別される。 - open-loop planner は実行前に完全な軌道を計算する必要があり、行動開始までに大きな planning latency が生じうる。 - closed-loop heuristic は性能保証が不十分で、安全-critical な展開が制限される。 - ACCBS は closed-loop でありながら、予算増加に伴う漸近最適性という性能保証を備える点が異なる。 - 計算効率・解品質・実行柔軟性のバランスを実現し、オンライン外乱にも自然に対応する。

- 有限ホライズン版の Conflict-Based Search (CBS) を基盤とする。 - Model Predictive Control (MPC) の iterative horizon-deepening に着想を得た horizon-changing mechanism を導入。 - 利用可能な計算予算に基づき計画ホライズンを動的に調整する。 - 単一の constraint tree を再利用し、ホライズン間の遷移をシームレスに行う。 - これにより、迅速に高品質な実行可能解を生成しつつ、予算増加に伴い漸近最適性を達成する anytime 挙動を実現。

- Extensive case studies を実施。 - ACCBS が計算効率・解品質・実行柔軟性の間で好ましいバランスを達成することを示す。 - 閉ループ定式化によりオンライン外乱に自然に対応できることを示す。 - 具体的なベンチマークや評価指標、比較手法の詳細は要旨からは不明。

- 要旨からは不明。 - 想定される議論点としては、horizon 調整のオーバーヘッド、constraint tree 再利用の有効性、外乱の種類や規模に対する頑健性、他手法との定量的比較などが考えられるが、要旨には明記されていない。

- Conflict-Based Search (CBS) の原論文。 - Model Predictive Control (MPC) における iterative horizon-deepening の関連研究。 - 閉ループ MAPF や anytime MAPF の既存手法。 - 具体的な参照論文は要旨からは不明のため、上記の関連手法を挙げる。