Multi-robot Task Allocation Based On Modified Ant Colony Algorithm

With the development of Robotics, robots can solve more and more problems for humans. It becomes a trend to use the robots to work in the dangerous, tedious and complicated situations. When the tasks cannot be finished by just single robot, multi-robot cooperative working system is needed. So the perfect teamwork of the robots is essential, and how to realize this goal is an issue has yet to be resolved. The key to the question is assigning the tasks to each robot reasonably. That’s the reason why the multi-robot task allocation (MRTA) has become an important issue, which attracts more and more experts and scholars. Because of it also has certain association with multiple traveling salesmen problem, logistics problem and path planning problem. The multi-robot task allocation problem has a lot of extensive areas of research.Ant colony algorithm, a method generally used to solve the multi-robot task allocation problem, has the advantages of positive feedback, parallel and distributed computing. But in the process of problem solving, the circumstances of running into partial optimization and stagnation behavior will appear with a certain probability.In reaction to the phenomenon, a method of improved ant colony algorithm which could overcome the disadvantages is presented in this thesis. The improved ant colony algorithm can obtain a satisfactory result and provides a new way to the aspect of solving the multi-robot task allocation problem.The research of this thesis involve the several aspects as follows:Firstly, the choice of the tasks is randomly selected by using the basic ant colony algorithm. To some degree, the results will have the differences. While this approach can increase the algorithm search randomicity, it reduces rate of convergence. Therefore, the initial task point selection and the uninitialized task point selection is combined. And the return optimization strategy is introduced in the latter selection. These will develop the searching effciency and rate of convergence.Secondly, there is a common problem in the way of updating pheromone. Before the appearance of the new optimal path, the signal intensity of the current path would be enhanced so much that leads to the stagnation behavior. In order to avoid this situation, dynamic update is presented in this thesis. It is a method which can finish the updating pheromone by considering the selection of tasks.Thirdly, ant colony algorithm as a global search algorithm has a certain limitation in local search. That’s also the reason why it may run into partial optimization. Hence, in local search, the strategy of eliminating the crossing is introduced. By optimizing the sequence of each robot, the quality of the solution is improved.Finally, with an effective integration of the three methods, an improved ant colony algorithm is presented and used in solving the multi-robot task allocation problem. The process design of the method is introduced and the algorithm implementation is received. A large number of simulation experiments prove that the improved algorithm of this thesis is valid in multi-robot task allocation. Comparing the results with the circumstances of using one of the three methods individually or using the method based on two of them, the improved ant colony algorithm can obtain the more optimal solution. It also has the higher rate of convergence and the lower probability of stagnation behavior. It’s a method which has practical value.