Abstract
In various scenarios such as multi-drone surveillance and search-and-rescue operations, deploying multiple robots is essential to accomplish multiple tasks at once. Due to the limited communication range of these vehicles, a decentralised task allocation algorithm is crucial for effective task distribution among robots. The consensus-based bundle algorithm (CBBA) has been promising for multi-robot operation, offering theoretical guarantees. However, CBBA demands continuous communication, leading to potential congestion and packet loss that can hinder performance. In this study, we introduce an event-driven communication mechanism designed to address these communication challenges while maintaining the convergence and performance bounds of CBBA. We demonstrate theoretically that the solution quality matches that of CBBA and validate the approach with Monte-Carlo simulations across varying targets, agents, and bundles. Results indicate that the proposed algorithm (ED-CBBA) can reduce message transmissions by up to 52%.
Abstract (translated)
在诸如多无人机监控和搜救操作等场景中,部署多个机器人以同时完成多项任务是至关重要的。由于这些车辆的通信范围有限,因此对于有效分配任务而言,去中心化的任务分配算法至关重要。基于共识的捆绑算法(CBBA)已被证明适用于多机器人作业,并提供了理论保障。然而,CBBA需要持续通信,这可能导致潜在的通信拥塞和数据包丢失,从而影响性能。在这项研究中,我们引入了一种事件驱动的通信机制,旨在解决这些通信挑战,同时保持CBBA的收敛性和性能界限。从理论上证明了所提出解决方案的质量与CBBA相匹配,并通过蒙特卡洛模拟在不同目标、代理和捆绑下的情况验证了该方法的有效性。结果表明,所提出的算法(ED-CBBA)可以将消息传输减少多达52%。
URL
https://arxiv.org/abs/2509.06481