A Multi-Robot Task Allocation Method Based on the Synergy of the K-Means++ Algorithm and the Particle Swarm Algorithm

Abstract

Addressing challenges in the traditional K-means algorithm, such as the challenge of selecting initial clustering center points and the lack of a maximum limit on the number of clusters, and where the set of tasks in the clusters is not reasonably sorted after the task assignment, which makes the cooperative operation of multiple robots inefficient, this paper puts forward a multi-robot task assignment method based on the synergy of the K-means++ algorithm and the particle swarm optimization (PSO) algorithm. According to the processing capability of the robots, the K-means++ algorithm that limits the maximum number of clusters is used to cluster the target points of the task. The clustering results are assigned to the multi-robot system using the PSO algorithm based on the distances between the robots and the centers of the clusters, which divides the multi-robot task assignment problem into a multiple traveling salesmen problem. Then, the PSO algorithm is used to optimize the ordering of the task sets in each cluster for the multiple traveling salesmen problem. An experimental verification platform is established by building a simulation and physical experiment platform utilizing the Robot Operating System (ROS). The findings indicate that the proposed algorithm outperforms both the clustering-based market auction algorithm and the non-clustering particle swarm algorithm, enhancing the efficiency of collaborative operations among multiple robots.

Keywords

• multi-robot
• particle swarm algorithm
• task allocation
• K-means++ clustering