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