Research And Implementation Of Large-scale Multi-robot Task Allocation Based On Ant Colony Optimization

Multi-robot task allocation is a basic problem of multi-robot system, which reflects the high-level forms of organization and operating mechanism. It is the basic goal of multi-robot system implementation. With the increasing of the number and the difficulty of the task, task allocation has become more and more important. Swarm Intelligence method is particularly suited to large-scale distributed multi-robot systems because of its high robustness, scalability, and individuals cooperating through implicit communication. A typical representative is Ant colony optimization. Currently, its application is limited to allocate loosely-coupled tasks, which a single robot can independently achieve. For this limitation, we proposed LMRTA_ACO( Large-scale Multi-Robot Task Allocation based on Ant Colony Optimizations) in this paper, which can solve large-scale multi-robot loosely and tightly-coupled task allocation problem based on reversion allocation thought.The LMRTA_ACO adopts hierarchical architecture. In the high level, we employ Ant Colony Algorithm to find optimal allocations. Namely, each ant forms a task allocation so as to choose an undertaker for every task. In the low level, the coalition formation algorithms based on Ant Colony Optimizations (ACO), Particle Swarm Optimization Ant Colony Optimization (PSOACO) and Quantum-Inspired Ant Colony Optimization (QACO) is proposed respectively for performing a tightly-coupled task.Based on the algorithm proposed above, we have developed a task allocation system-- LMRTA_ACO, which implemented on TeamBots simulation platform with Java. Simulation results show that PSOACO can get best solution, but its running time is the longest. On the other hand, QACO is little inferior to PSOACO on the solution quality, however, its running time is only a half of two other methods. Therefore, QACO is more suitable for the large-scale multi-robot system.