群分散計画を用いた並列生涯MAPFの理論的枠組み

本論文は、Lifelong Multi-Agent Path Finding (L-MAPF) 問題に対する高性能フレームワークである Rolling-Horizon Collision Resolution (RHCR) の理論的解析と、その拡張である Group Decentralized RHCR (GD-RHCR) を提案している。L-MAPF では、エージェントが障害物や相互衝突を避けながら繰り返し目的地へ移動する。RHCR は高品質な解を生成するが計算コストが高く、エージェント数が増えると適用が困難になる。本論文では、Locally Interdependent Multi-Agent MDP の理論を用いて、割引 MDP として定式化した L-MAPF における RHCR の準最適性を理論的に証明し、その結果に基づいて、エージェントを推移的通信スキームに基づいて分割し、各分割を並列に計画する GD-RHCR を提案する。

先行研究である RHCR は高い性能を持つが、計算コストが高くエージェント数が限られる。本論文の貢献は、RHCR の理論的保証を初めて提供し、さらに並列化によるスケーラビリティ向上を実現する GD-RHCR を提案した点である。GD-RHCR は、時間的制限（RHCR の horizon）と空間的分割（グループ化）の間に理論的双対性があることを示し、RHCR と同様の指数関数的に最適に近い保証を維持しつつ、より高いエージェント数に対応できる。

手法の核は、L-MAPF を割引 MDP として定式化し、Locally Interdependent Multi-Agent MDP の理論を適用して RHCR の準最適性を証明すること。次に、この理論的結果を用いて、エージェントを推移的通信スキームに基づいてグループに分割し、各グループを並列に計画する GD-RHCR を設計。時間的制限（RHCR の replanning horizon）と空間的分割（グループサイズ）の間の双対性を理論的に示し、両者が同様の性能保証を提供することを証明する。

検証方法は、理論的証明に加えて、様々なマップ上での実験を行い、GD-RHCR が高いスループットを達成し、より多くのエージェント数にスケールすることを示した。また、プランあたりの計算コストが大幅に低減されることを実証した。具体的な数値や比較対象は要旨からは不明。

議論としては、RHCR と GD-RHCR が同様の理論的保証を持つことが示されたが、実際のトレードオフ（時間的制限と空間的分割のバランス）や、通信スキームの設計が性能に与える影響などが考えられる。また、理論的保証は割引 MDP に基づくため、実問題との乖離がある可能性がある。しかし、要旨からはこれらの詳細は不明。

要旨で参照されている研究は、Locally Interdependent Multi-Agent MDP の文献と、Rolling-Horizon Collision Resolution (RHCR) の元論文である。次に読むべき論文としては、RHCR の原著論文（Lifelong MAPF のための rolling horizon 手法）や、Locally Interdependent Multi-Agent MDP の理論を扱った論文が挙げられる。