分散型・協調型マルチエージェント経路探索のためのカルマ機構

Abstract

マルチエージェント経路探索（MAPF）は、大規模なロボティクスおよびサイバーフィジカルシステムにおける基本的な協調問題であり、複数のエージェントが限られた計算資源と通信資源のもとで、衝突のない軌道を計算する必要があります。集中型の最適解ソルバは解の最適性に関する保証を提供しますが、その指数関数的な計算複雑性のため、大規模システムへのスケーラビリティやリアルタイム適用が制限されます。既存の分散型ヒューリスティクスはより高速ですが、結果が劣ったものになり、コストの不均衡が大きくなります。本論文は、協調型MAPFのための分散型協調フレームワークを提案します。この枠組みは、Karmaメカニズム（エージェントの過去の協調行動を勘案し、将来の衝突解決の意思決定を調整する、人工的で取引不能なクレジット）に基づいています。本アプローチでは、衝突解決を二者間交渉プロセスとして定式化し、グローバルな優先順位構造を用いず、限られた通信のもとで長期的な公平性を促進しながら、エージェントがペアごとの再計画によって衝突を解決できるようにします。このメカニズムは、運動学的な姿勢制約を伴う、生涯運用型のロボティクス倉庫におけるマルチエージェントのピックアップ・アンド・デリバリー（荷物の受け取りと配送）シナリオで評価されます。結果は、Karmaメカニズムが、全体の効率を損なうことなく、エージェント間での再計画の負担をバランスさせ、サービス時間の格差を低減することを示しています。コード: https://github.com/DerKevinRiehl/karma_dmapf