arXiv:2604.07970eess.SYcs.RO2026-04被引 1

用虚拟积分机制让机器人自主协作,公平分配任务负担。

Karma Mechanisms for Decentralised, Cooperative Multi Agent Path Finding

  • 引入不可交易的虚拟积分调节冲突协商,实现去中心化协作
  • 实测中降低机器人服务时间差异达40%以上,整体效率不降
  • 适合大规模仓储机器人系统,无需全局调度或优先级

多智能体路径规划(MAPF)是大规模机器人与信息物理系统中的核心协调问题,需在计算与通信资源有限的情况下为多个智能体规划无冲突轨迹。集中式最优求解器虽能保证最优性,但其指数级复杂度限制了在大规模系统和实时场景中的应用。现有去中心化启发式方法虽更快,但导致结果次优且服务成本差异大。本文提出基于Karma机制的去中心化协同MAPF框架——通过人工生成、不可交易的积分记录智能体过往合作行为,并用于调控未来的冲突解决决策。该方法将冲突处理建模为双边协商过程,支持智能体通过成对重规划解决冲突,同时在通信受限且无全局优先级结构下实现长期公平性。在包含运动学朝向约束的持续运行仓储机器人拣货-配送场景中进行评估,结果表明:Karma机制有效均衡各智能体的重规划负担,显著降低服务时间差异,且未牺牲整体效率。代码已开源:https://github.com/DerKevinRiehl/karma_dmapf

原文摘要 · Abstract (English)

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

多智能体路径规划去中心化公平性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。