Multi-target assignment hunting strategy of UAV swarm based on improved K-means algorithm and shortest time mechanism

基于改进K-means算法和总时最短机制的无人机群多目标分配围猎策略

¹ School of Automation, Northwestern Polytechnical University, Xi'an 710072, China
² School of Mathematics and Statistics, Shaanxi Xueqian Normal University, Xi'an 710061, China
³ School of Mechanical Engineering, Northwestern Polytechnical University, Xi'an 710072, China
⁴ Department of Satellite Communication, China Transport Telecommunication Information Group Co., Ltd, Beijing 100011, China
⁵ School of Air Defense and Anti-Missile, Air Force Engineering University, Xi'an 710043, China

Received: 1 April 2022

Abstract

Multi-target hunting of UAV swarm is an important tactical means. This paper proposes a hunting strategy based on improved K-means and the shortest time mechanism. The large-scale task assignment problem is complex in structure and difficult to solve. To obtain higher hunting efficiency and reduce the amount of calculation on the single UAV, the hybrid architecture is used to decompose the complex multi-target hunting problem into a set of tasks that the UAV need to perform, which reduces the coupling of the system and the complexity of problem. Firstly, the multi-target hunting problem is stratified by the improved K-means algorithm to form multiple independent single target hunting subsystems. In the subsystem, the single target hunting task is decomposed into multiple subtasks that are easy to be executed by UAVs, and a one-to-one matching relationship between subtasks and UAVs is established by using the shortest time mechanism. UAV swarm can achieve multi-target hunting only by executing subtasks. The simulation results show that the UAV swarm can effectively allocate the multi-target hunting problem, which proves the effectiveness of the allocation strategy is proved.

摘要

无人机(UAV)群多目标围猎是一种重要的战术手段, 提出了一种基于改进K-means和总时最短机制的围猎策略。大规模的任务分配问题结构复杂、解算难度大, 为了得到较高的围猎效率, 减少单机计算量, 采用混合式的体系结构将复杂的多目标围猎问题逐步分解为UAV个体需要执行的任务集合, 降低了系统的耦合性和任务解算的复杂度。该策略利用改进的K-means算法将多目标围猎问题分层, 形成多个独立的单目标围猎子系统。在子系统内部将单目标围猎任务分解为多个UAV容易执行的子任务, 并以总时最短机制在子任务和UAV之间建立一一对应的匹配关系, 各UAV只需执行待执行的子任务即可达到多目标围猎的目的。仿真实验表明, 多无人机群可以有效地对多个目标的围捕任务进行合理分配, 证明了该分配策略的有效性。