面向多运动体协同任务分配的目标辅助概率强势学习粒子群优化算法  

Objective-assisted probabilistic strength learning particle swarm optimization for multi-agent cooperative task allocation

作　　者：钱通 黎建宇 刘晓芳 詹志辉 张军 QIAN Tong;LI JianYu;LIU XiaoFang;ZHAN ZhiHui;ZHANG Jun(College of Artificial Intelligence,Nankai University,Tianjin 300350,China)

机构地区：[1]南开大学人工智能学院,天津300350

出　　处：《中国科学：技术科学》2024年第9期1720-1735,共16页Scientia Sinica(Technologica)

基　　金：科技创新2030-“新一代人工智能”重大科技项目(编号:2022ZD0120001);国家自然科学基金项目(批准号:62103202,62176094);天津市科技计划项目(编号:24JRRCRC00030)资助。

摘　　要：多运动体协同任务分配(multi-agent cooperative task allocation, MACTA)是异构多运动体系统应用的基础.为了最小化所有任务的最大完成时间, MACTA需要同时最小化各个任务的执行时间和运动体在任务点间的移动时间,这给已有优化算法带来两个新挑战.首先,由于异构运动体具有不同的移动速度与任务执行效率,多个运动体协作虽然可以缩短任务执行时间,但同时会增加运动体在任务点间的移动时间,因此任务执行时间与运动体移动时间之间存在一定的冲突,导致现有单目标优化方法难以高效求解MACTA.其次, MACTA中任务可分配的运动体协作组合数量随着运动体数量的增加呈指数增加,是典型的大规模组合优化问题,且存在众多的局部最优解,已有算法容易落入局部最优.针对上述问题,本文提出目标辅助概率强势学习粒子群优化(objective-assisted probabilistic strength learning particle swarm optimization, OA-PSLPSO)算法.本文的贡献主要有三个方面.第一,提出目标辅助优化框架,将多运动体总移动时间作为辅助目标,对问题进行多目标建模,从而使用多目标优化算法对运动体移动时间和任务完成时间进行协同优化,提高优化效率.第二,提出概率强势学习策略,根据概率为粒子选择目标进行强势学习,提高算法的搜索多样性,避免落入局部最优.第三,基于上述框架和策略,提出OAPSLPSO,对MACTA进行高效求解.通过将所提算法与5种前沿算法在包括百万级候选解规模的30个测试用例上进行对比实验,验证了所提方法能更好地最小化所有任务的最大完成时间,实现对MACTA的高效求解.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 multiobjective 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 mi

关 键 词：多运动体系统 协同任务分配 粒子群优化算法 概率强势学习 目标辅助 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]