Research on Task Allocation of Heterogeneous Multi-Robot Based on Cluster Grouping Algorithm

Abstract

In the urban combat environments, multiple heterogeneous air-to-ground robots need to process large-scale task targets with time window constraints. In order to ensure fast and effective strategic execution, an acceptable suboptimal task allocation strategy needs to be quickly calculated. This paper proposes a cluster grouping consensus-based bundle algorithm (C-CBBA) for large-scale task assignment problems with time window constraints. Firstly, the task target points and robots are grouped, and the large-scale problems are tranformed into small-scale problems. The grouping algorithm includes three stages: the K-Means algorithm is used to preliminarily classify the task points accor-ding to the principle of nearest distance, the task point group of each group is adjusted so that it does not exceed the upper load limit of each pre-assigned robot group, and the delay acceptance algorithm (DA) is used to assign the nearest robot to each group. Finally, the improved consensus-based bundle algorithm (CBBA) is used to solve each sub-pro-blem. Simulation results show that the proposed algorithm has high task completion and effectively reduces communication between robots.