Search

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.

Path planning problem for large number of robots is a quite challenging problem in mobile robotics since their control and coordination becomes unreliable and sometimes unfeasible. Particle Swarm Optimization (PSO) has been demonstrated to be a useful technique in the field of robotic research. This paper discusses an optimal path planning algorithm based on a Dynamic Distributed Particle Swarm Optimization Algorithm (D2PSO). The purpose of this approach is to find collision free optimal paths using two local optima detectors. This would add diversity to the population and hence avoid stagnation problem. The results show that the D2PSO has a better ability to get away from local optimums than the distributed PSO (dPSO). Simulations prove that this methodology is effective for every robot in multi-robot framework to discover its own proper path from the start to the destination position with minimum distance and no collision with obstacles.

Particle swarm optimization (PSO) has been considered as a very efficient swarm intelligence technique used to solve many problems, such as those related to Constraint reasoning in particular Constraint Satisfaction Problems (CSPs). In this paper, we introduce a new PSO method for solving Maximal Satisfaction Problems Max-CSPs, which belong to CSPs extensions. Our approach is based on a combination between two concepts: double guidance by both template concept and min-conflict heuristic, and the Triggered mutation proposed by Zhou and Tan. This new proposed approach avoids premature stagnation process in order to improve Max-CSPs solution quality. We resort to the high parallel computing insofar as it has shown high performances in several fields, using GPU architecture as a parallel computing framework. The experimental results, presented at the end, show the efficiency of the introduced technique in the resolution of large size Max-CSPs.

This paper presents a new generation of algorithms obtained by successive improvements of the initial version of the genetic algorithm guided by the templates (GGA) (Tsang, 1999). These improvements are experimentally validated and this separately and jointly. They go from the distribution of the individuals by species to the control of the crossover and the mutation sub processes. Our objective is to maximize the number of satisfied constraints. For this we use the multiagent approach, the min-conflict heuristic and the diversification as well as the intensification locally on the level of the agents. Each agent is, indeed, responsible for a given species; namely a subset of individuals violating the same number of constraints.