arXiv:2608.15884cs.RO2026-08

提出分组拍卖共识算法,让多机器人系统更高效分配任务。

Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot Systems

论文配图:Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot Systems
图 1 · 摘自论文原文
  • 将任务按空间邻近性分组,以群体为单位进行竞标
  • 在4000个测试场景中,任务分配效率达97%接近最优解
  • 适合大规模、空间分布的多机器人协同任务场景

去中心化多机器人任务分配(MRTA)对可扩展、鲁棒的自主系统至关重要。共识基打包算法(CBBA)是广泛采用的去中心化基准,但其基于任务级别的独立竞标与最小总行程距离的优化目标不匹配,在空间分散环境中表现不佳。本文提出分组拍卖共识算法(GACA),保留了CBBA的两阶段拍卖-共识架构,但从根本上重构了竞标机制,转而对空间邻近的任务组进行推理。通过最近邻预处理步骤,将任务划分为空间连贯的组。各智能体迭代提出结构化组级动作:申领未分配组、获取部分组或争夺他人持有的组。竞争动作通过共识阶段解决。在MT-SR-IA问题类别中,以混合整数线性规划作为最优参考,对四种群规模和4000个测试世界评估显示,GACA相比CBBA(81–84%中位最优率)达到约97%的中位最优率,且收敛步数相等或更少。对3280个额外实例的可扩展性评估表明,这些性能优势在5至20个智能体、10至50个任务的广泛配置下均具鲁棒性。

原文摘要 · Abstract (English)

Decentralized multi-robot task allocation (MRTA) is essential for scalable and resilient autonomous systems. The Consensus-Based Bundle Algorithm (CBBA) is a widely adopted decentralized baseline. However, its individual task-level bidding is poorly aligned with the min-sum objective of minimizing total team travel distance, leading to suboptimal allocations in spatially distributed environments. This paper introduces the Grouping Auction-Consensus Algorithm (GACA). This decentralized MRTA framework adopts the two-phase auction-consensus architecture of CBBA while fundamentally redesigning its bidding mechanism to reason over groups of spatially proximate tasks. A nearest-neighbor preprocessing step partitions tasks into spatially coherent groups before allocation. Agents then iteratively propose structured group-level actions: claiming unassigned groups, acquiring partial groups, or contesting groups held by other agents. Competing actions are resolved through a consensus phase. Operating in the MT-SR-IA problem class, GACA is evaluated against CBBA using a Mixed-Integer Linear Program as the ground-truth optimality reference. Across four swarm sizes and 4,000 test worlds, GACA achieves a median percent optimality of approximately 97% compared to 81--84% for CBBA, while converging in equal or fewer iterations. A scalability evaluation over 3,280 additional problem instances spanning swarm sizes of 5 to 20 agents and task counts of 10 to 50 confirms that these gains generalize robustly across a wide range of problem configurations.

多机器人任务分配去中心化优化算法

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