A Distributed Algorithm for Multi-Robot Task Allocation via Weighted Buffered Voronoi Partition

Abstract

This article proposes a distributed bundle algorithm for task allocation problems for multirobot systems. Specifically, in the developed formulation of the vehicle routing problem with time windows (VRPTW), the robots are assigned to dispatch necessities for the survivors. The utility of each robot is evaluated by the preference index, composed of the distance cost and the task reward. Considering the requirements of the distributed structure and real-time computing, we propose the weighted buffered Voronoi partition-based bundle algorithm. The proposed algorithm dynamically updates the weighted buffered Voronoi partition (WBVP) and calculates the bundle construction once the subtask set changes. The former divides the task area into several disjoint partitions, and the latter ensures that the robot determines the scheduling for tasks according to its preference. Finally, experiment results are presented to demonstrate the effectiveness and feasibility of the proposed distributed framework.