航空学报 > 2022, Vol. 43 Issue (12): 326011-326011   doi: 10.7527/S1000-6893.2021.26011

多无人机协同任务分配混合粒子群算法

张瑞鹏, 冯彦翔, 杨宜康   

  1. 西安交通大学 自动化科学与工程学院, 西安 710049
  • 收稿日期:2021-06-23 修回日期:2021-07-12 发布日期:2021-09-06
  • 通讯作者: 杨宜康,E-mail:yangyk74@xjtu.edu.cn E-mail:yangyk74@xjtu.edu.cn
  • 基金资助:
    2020年度科技创新2030-"新一代人工智能"重大项目(2020AAA0108203);国家自然科学基金(62003258)

Hybrid particle swarm algorithm for multi-UAV cooperative task allocation

ZHANG Ruipeng, FENG Yanxiang, YANG Yikang   

  1. School of Automation Science and Engineering, Xi'an Jiaotong University, Xi'an 710049, China
  • Received:2021-06-23 Revised:2021-07-12 Published:2021-09-06
  • Supported by:
    2020 Science and Technology Innovation 2030-Key Project of "New Generation Artificial Intelligence" under Grant (2020AAA0108203); National Natural Science Foundation of China (62003258)

摘要: 针对多无人机协同任务分配问题(MTAP),设计了一种综合考虑飞行航程、任务收益以及任务完成时间窗口的混合粒子群任务分配算法。首先,将粒子位置编码为一组任务分配向量,针对同时打击场景可能存在的死锁问题,设计了一种基于多打击任务有向图的死锁检测和修复算法,解码出对应一组可行的任务分配解或方案,实现粒子群算法解的离散化。另外,对于传统粒子群算法(PSO)容易陷入局部收敛的缺点,提出一种基于变邻域搜索算法的跳出局部收敛策略,并建立局部搜索启动概率准则,实现跳出局部收敛和计算开销的平衡。最后,将跳出局部收敛的策略嵌入到粒子群算法中,得到协同任务分配的混合粒子群算法(HPSO)。另外,针对新目标发现导致的初始计划失效问题,设计了一种基于匹配策略的局部任务重分配方法。仿真实验证明,所提出的混合粒子群算法能够有效解决异构多无人机同时打击场景中的任务分配问题。

关键词: 多无人机, 协同任务分配, 同时打击, 粒子群算法, 局部收敛, 变邻域搜索, 任务重分配

Abstract: 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.

Key words: multi-unmanned-aerial-vehicle, task assignment problem, simultaneous strike, particle swarm optimization algorithm, local convergence, variable neighborhood search, task rescheduling

中图分类号: