摘要
针对多无人机协同任务分配问题(MTAP),设计了一种综合考虑飞行航程、任务收益以及任务完成时间窗口的混合粒子群任务分配算法。首先,将粒子位置编码为一组任务分配向量,针对同时打击场景可能存在的死锁问题,设计了一种基于多打击任务有向图的死锁检测和修复算法,解码出对应一组可行的任务分配解或方案,实现粒子群算法解的离散化。另外,对于传统粒子群算法(PSO)容易陷入局部收敛的缺点,提出一种基于变邻域搜索算法的跳出局部收敛策略,并建立局部搜索启动概率准则,实现跳出局部收敛和计算开销的平衡。最后,将跳出局部收敛的策略嵌入到粒子群算法中,得到协同任务分配的混合粒子群算法(HPSO)。另外,针对新目标发现导致的初始计划失效问题,设计了一种基于匹配策略的局部任务重分配方法。仿真实验证明,所提出的混合粒子群算法能够有效解决异构多无人机同时打击场景中的任务分配问题。
This paper proposes a hybrid particle swarm optimization algorithm for solving the Multi-UAV Task Allocation Problem(MTAP),which takes flight range,task revenue,and task completion time window into consideration.First,particle positions are encoded as a set of task assignment vectors,and a deadlock detection and repair algorithm based on digraphs of multi-strike tasks is designed for the possible deadlock problem of simultaneous strike scenarios,decoding the corresponding set of feasible task assignment solutions or schemes to realize the discretization of particle swarm algorithm solutions.Then,to overcome the drawback of premature convergence for traditional Particle Swarm Optimization(PSO),a policy of jumping local optimum is proposed based on variable neighborhood search,so that the balance between jumping local convergence and computational cost is achieved.Finally,an Hybrid Partide Swarm Optimization(HPSO)is obtained by embedding the proposed strategy into traditional PSO,which can be used to solve the underlying MTAP.A local task reassignment method based on the matching strategy is also designed for failure of the initial plan caused by new target discovery.Simulation experiments show that the proposed HPSO algorithm can effectively solve the task assignment problem in heterogeneous multi-UAV simultaneous strike scenarios.
作者
张瑞鹏
冯彦翔
杨宜康
ZHANG Ruipeng;FENG Yanxiang;YANG Yikang(School of Automation Science and Engineering,Xi'an Jiaotong University,Xi'an 710049,China)
出处
《航空学报》
EI
CAS
CSCD
北大核心
2022年第12期412-427,共16页
Acta Aeronautica et Astronautica Sinica
基金
2020年度科技创新2030-“新一代人工智能”重大项目(2020AAA0108203)
国家自然科学基金(62003258)。
关键词
多无人机
协同任务分配
同时打击
粒子群算法
局部收敛
变邻域搜索
任务重分配
multi-unmanned-aerial-vehicle
task assignment problem
simultaneous strike
particle swarm optimization algorithm
local convergence
variable neighborhood search
task rescheduling
