Research On Multi-Agent Task Allocation Based On Ant Colony Optimization

The Task allocation problem is a typical combinatorial optimization problem. However, due to the continuous changes of the system in the environment both inside and outside, and the dynamic changes of capacity of the members within the system, all of this make the task allocation problem difficult to solve. In theory, the task allocation problem is recognized as NP-hard problem, so how to construct an effective heuristic algorithm or approximation algorithm is a hot area of research.Ant colony optimization is a novel biomimetic evolutionary algorithm inspired by the foraging behavior of ants in nature for solving complicated combinatorial optimization problem.In this paper, I propose an idea of a reversal of distribution to solve this limit of ant colony optimization in the application that the ant represent the task, and then select the task for each task holders, so that ant colony algorithm can solve the large-scale agent-based loosely coupled task allocation problem. Multi Agent System (MAS) study how to make one or more entities to complete the complex or tedious tasks commissioned by the user, without human guidance and through mutual cooperation and mutual coordination and consultation service.The main contents include:First, the paper establish a task allocation model UTAM based on utility, give the definition of the task allocation problem based on utility, and then analyze UTAM task allocation model, and made a specific mathematical description. Then the paper discusses the UTAM model and shows how to apply this model and shows the architecture of the UTAM model.Second, due to the defects of the basic ant colony algorithm of taking a long time and prone to stagnation, the paper design a random disturbance ant colony algorithm (ant system with random perturbation behavior, RPAS). Compare RPAS and the basic ant colony algorithm and the results of the simulation of both.Third, build task allocation mechanisms RPASTA based on RPAS. Describe the basic task allocation problem mathematically. Then the paper foucus on the description of RPASTA the ant colony algorithm based on multi-agent coordination mechanisms. Then study the RPASTA specific allocation process, functional design and workflow. And then compare the ant colony algorithm and other heuristic algorithms, and finally using the simulation, the paper makes the conclusion that the performance of ant colony optimization is superior to other heuristic algorithm according to the simulation result.Fourth, study the application of RPASTA task allocation mechanism. Give in detail the overall system analysis and design, including instances of introduction, system design, implementation steps and development environment.