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