Multi-agent cooperative task allocation(MACTA)is the foundation of heterogeneous multi-agent system applications.To minimize the maximum completion time of all tasks,MACTA needs to reduce both the execution time of each task and the travel time of each agent at the same time,which brings two important challenges to optimization algorithms.First,heterogeneous agents have different speeds and task execution efficiencies,and the cooperation of multiple agents can shorten the task execution time,but at the same time increase the travel time of agents between tasks.The conflict between the task execution time and the agent travel time makes it difficult to solve MACTA efficiently with existing single-objective optimization methods.Second,the number of alliances of agents that can be assigned to each task in MACTA increases exponentially with the number of agents,which is a typical large-scale combinatorial optimization problem,and there are many locally optimal solutions.Existing algorithms are easy to fall into local optimum.To address the above problems,an objective-assisted probabilistic strength learning particle swarm optimization(OA-PSLPSO)is proposed.The contributions of this paper are mainly in three aspects.First,an objective-assisted optimization framework is proposed,with an assisted objective designed based on the total travel time of all agents to model MACTA as a multi-objective problem,so as to use multi-objective optimization algorithms to synergistically optimize the travel time of agents and the completion time of tasks,and to improve the optimization efficiency.Second,a probabilistic strength learning strategy is proposed to select objectives for particles based on probability for strength learning,which improves the search diversity of the algorithm and avoids falling into local optimum.Third,based on the above proposed framework and strategy,OA-PSLPSO is proposed to solve MACTA efficiently.By comparing the proposed algorithm with five state-of-the-art algorithms on 30 test instances that contain millions of candidate solutions,it is verified that the proposed method can better minimize the maximum completion time of all the tasks and obtain solutions of MACTA more efficiently.
万方数据
