マルチロボット計画実行のためのリアルタイム再スケジューリングアルゴリズム
A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution
マルチエージェント経路計画において、実行中の遅延に対処するため、エージェントの通過順序を再スケジュールするA*スタイルのアルゴリズム（Switchable-Edge Search）を提案し、その最適性を証明するとともに、シミュレーションで効率性を評価した。
著者: Ying Feng, Adittyo Paul, Zhe Chen, Jiaoyang Li
分類: cs.AI, cs.MA, cs.RO
原文アブストラクト
One area of research in multi-agent path finding is to determine how replanning can be efficiently achieved in the case of agents being delayed during execution. One option is to reschedule the passing order of agents, i.e., the sequence in which agents visit the same location. In response, we propose Switchable-Edge Search (SES), an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations. The best variant of SES takes less than 1 second for small- and medium-sized problems and runs up to 4 times faster than baselines for large-sized problems.
