Distributed Task Assignment for Multiple Robots Under Limited Communication Range
研究了多个分散机器人在有限通信范围下访问目标位置以最小化总旅行距离的问题，提出了一种分布式拍卖算法，并发现通信范围增大时总旅行距离可能反而增加。
This article investigates the task assignment problem in which multiple dispersed robots need to visit a set of target locations while trying to minimize the robots’ total travel distance. Each robot initially has the position information of all the targets and of those robots that are within its limited communication range, and each target demands a robot with some specified capability to visit it. We propose a decentralized auction algorithm which first employs an information consensus procedure to merge the local information carried by each communication-connected (CC) robot subnetwork. Then, we apply a marginal-cost-based strategy to construct conflict-free target assignments for the CC robots. When the communication network of the robots is not connected, we demonstrate that the robots’ total travel distance might in fact increase when their communication range grows, and more importantly, such a somewhat counterintuitive fact holds for a range of algorithms. Furthermore, the proposed algorithm guarantees that the total travel distance of the robots is at most twice of the optimal when the communication network is initially connected. Finally, Monte Carlo simulation results demonstrate the satisfying performance of the proposed algorithm.