ACD~3GPSO: automatic clustering-based algorithm for multi-robot task allocation using dynamic distributed double-guided particle swarm optimization

摘要

Purpose-The multi-robot task allocation (MRTA) problem is a challenging issue in the robotics area with plentiful practical applications. Expanding the number of tasks and robots increases the size of the state space significantly and influences the performance of the MRTA. As this process requires high computational time, this paper aims to describe a technique that minimizes the size of the explored state space, by partitioning the tasks into clusters. In this paper, the authors address the problem of MRTA by putting forward a new automatic clustering algorithm of the robots' tasks based on a dynamic-distributed double-guided particle swarm optimization, namely, ACD~3GPSO. Design/methodology/approach - This approach is made out of two phases: phase I groups the tasks into clusters using the ACD~3GPS0 algorithm and phase Ⅱ allocates the robots to the clusters. Four factors are introduced in ACD~3GPSO for better results. First, ACD~3GPS0 uses the k-means algorithm as a means to improve the initial generation of particles. The second factor is the distribution using the multi-agent approach to reduce the run time. The third one is the diversification introduced by two local optimum detectors LODpBest and LODgBest. The last one is based on the concept of templates and guidance probability Pguid. Findings - Computational experiments were carried out to prove the effectiveness of this approach. It is compared against two state-of-the-art solutions of the MRTA and against two evolutionary methods under five different numerical simulations. The simulation results confirm that the proposed method is highly competitive in terms of the clustering time, clustering cost and MRTA time. Practical implications - The proposed algorithm is quite useful for real-world applications, especially the scenarios involving a high number of robots and tasks. Originality/value - In this methodology, owing to the ACD~3GPSO algorithm, task allocation's run time has diminished. Therefore, the proposed method can be considered as a vital alternative in the field of MRTA with growing numbers of both robots and tasks. In PSO, stagnation and local optima issues are avoided by adding assorted variety to the population, without losing its fast convergence.