分散型協調マルチエージェント経路探索のためのカルマメカニズム
Karma Mechanisms for Decentralised, Cooperative Multi Agent Path Finding
分散型の協調マルチエージェント経路探索において、人工的な非取引可能なクレジット(カルマ)を用いてエージェント間の公平性を保ちつつ、ペアワイズ再計画による衝突解決を実現する枠組みを提案した。倉庫のピックアップ・デリバリーシナリオで評価し、サービス時間の格差を減らしつつ効率を維持できることを示した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Kevin Riehl, Julius Schlapbach, Anastasios Kouvelas, Michail A. Makridis
分類: eess.SY, cs.RO, cs.SY
原文アブストラクト
Multi-Agent Path Finding (MAPF) is a fundamental coordination problem in large-scale robotic and cyber-physical systems, where multiple agents must compute conflict-free trajectories with limited computational and communication resources. While centralised optimal solvers provide guarantees on solution optimality, their exponential computational complexity limits scalability to large-scale systems and real-time applicability. Existing decentralised heuristics are faster, but result in suboptimal outcomes and high cost disparities. This paper proposes a decentralised coordination framework for cooperative MAPF based on Karma mechanisms - artificial, non-tradeable credits that account for agents' past cooperative behaviour and regulate future conflict resolution decisions. The approach formulates conflict resolution as a bilateral negotiation process that enables agents to resolve conflicts through pairwise replanning while promoting long-term fairness under limited communication and without global priority structures. The mechanism is evaluated in a lifelong robotic warehouse multi-agent pickup-and-delivery scenario with kinematic orientation constraints. The results highlight that the Karma mechanism balances replanning effort across agents, reducing disparity in service times without sacrificing overall efficiency. Code: https://github.com/DerKevinRiehl/karma_dmapf
