PSO-based Dynamic Distributed Algorithm for Automatic Task Clustering in a Robotic Swarm

摘要

The Multi-Robot Task Allocation (MRTA) problem has recently become a key research topic. Task allocation is the problem of mapping tasks to robots, such that the most appropriate robot is selected to perform the most fitting task, leading to all tasks being optimally accomplished. Expanding the number of tasks and robots may cause the collaboration among the robots to become tougher. Since this process requires high computational time, this paper describes a technique that reduces the size of the explored state space, by partitioning the tasks into clusters. In real-world problems, the absence of information regarding the number of clusters is ordinarily occurring. Hence, a dynamic clustering is auspicious for partitioning the tasks to an appropriate number of clusters. In this paper, we address the problem of MRTA by putting forward a new simple, automatic and efficient clustering algorithm of the robots’ tasks based on a dynamic distributed particle swarm optimization, namely, ACD2PSO. Our approach is made out of two stages: stage I groups the tasks into clusters using the dynamic distributed particle swarm optimization (D2PSO) algorithm and stage II allocates the robots to the clusters. The assignment of robots to the clusters is represented as multiple traveling salesman problems (MTSP). Computational experiments were carried out to prove the effectiveness of our approach in term of clustering time, cost, and the MRTA time, compared to the distributed particle swarm optimization (dPSO) and genetic algorithm (GA). Thanks to the D2PSO algorithm, stagnation and local optima issues are avoided by adding assorted variety to the population, without losing the fast convergence of PSO.