多架无人作战飞机紧急任务分配奇异值分解算法

陈 琛

(空军工程大学 信息与导航学院，西安 710077)



【信息科学与控制工程】

多架无人作战飞机紧急任务分配奇异值分解算法

陈 琛

(空军工程大学 信息与导航学院，西安 710077)

从战场实际需求出发，在动态条件下对多无人机紧急任务分配问题提出了一种可行稳健算法；将无人机与任务相关的状态参数提取为多维特征向量，构造控制单元范围内所有无人机状态参数矩阵，通过计算特征向量方向余弦值并利用矩阵奇异值分解后的右奇异值矩阵优选分配紧急任务，进行了算例验证并分析了算法复杂度。算法简洁、计算耗时少，符合作战流程中对该问题求解的可靠性、迅速性要求。

多无人机；任务分配；特征向量；奇异值分解

无人作战飞机(UCAV)近年来得到了广泛的应用。在现代战场复杂环境中，根据任务的不同约束条件并进行有效的策略控制，实现多架UCAV协同作战达到整体最优作战效能是目前研究的热点。但对多无人机任务分配研究多集中在初始条件下预先规划[1-4]，而对任务执行过程中的动态分配缺少深入研究。本研究针对战场出现状况突发的紧急任务条件下，根据首长决心需要对协同作战的多UCAV进行紧急调度，优选出若干架次UCAV进行动态任务分配问题研究，提出一种实用高效的稳健算法。

1 问题描述

在地面/空中任务单元的控制下，由多种类型的UCAV对给定区域内预先侦察确定的目标集合进行协同打击，是UCAV的主要作战模式之一[1]。典型的作战模式如图1所示。

在此场景下，如出现突发紧急任务，该控制单元范围内能否优选出任务所需架次的UCAV主要取决于UCAV平台配置和基本限定条件两个方面的约束条件。

UCAV平台配置约束主要指UCAV可分为攻击型无人机、侦察型无人机和察打一体无人机，紧急任务的性质不同决定了UCAV平台配置约束为强约束。

基本限定条件约束主要是指当前各UCAV状态与任务要求的契合度，主要包括：与目标点之间的飞行距离、弹药战斗部类型、配备传感器类型等因素，这些约束在一些情况下也可以转变为强约束，例如到达目标点飞行距离如果超出了该UCAV剩余的最大续航能力，即无人机无法飞抵目标，则该约束必然为强约束。

图1 多UCAV协同作战场景

为了减少人工处理的工作量，对所有的约束条件不区分强弱约束，将同一UCAV的所有状态参数对应一个向量的不同维度，生成一个n维向量X。

每个向量对应一架UCAV，假设该控制单元范围内共有M架UCAV，则可以用一个N×M的矩阵A来表示范围内所有无人机的状态。

2 最优UCAV聚类

b和c为两个以A为起点的向量，那么∠A的余弦值计算公式：

(1)

其中分母表示两个向量b和c的长度，分子表示的是两个向量的内积，将其扩展到n维的情况，利用下式可以得到更为一般的计算公式。

(2)

3 奇异值分解算法

采用向假设的最优UCAV向量聚类的方法易于算法实现，但在计算过程中需要一一计算所有的余弦值，当问题规模扩大时，遍历所有的向量耗时较长[6-8]。对于规模扩大后的同一问题，可以稍加处理后采用奇异值分解的方法一次性计算与最优UCAV的契合度[9-10]。

其中，每一列代表一架UCAV，每一行代表与任务相关的一个约束项，第一列代表虚拟最优UCAV，对该矩阵进行奇异值分解可得：

其中B为对角阵，由于矩阵奇异值在大小上递减非常快，即矩阵B中很多对角元素非常小或为0，可以省略，因此可进一步简化为

其中r是远小于m、n的数，极大减少了算法实现过程中的存储量。X、B、Y3个矩阵具有非常明显的物理意义，矩阵X中的每一行表示任务相关的一个约束项，矩阵Y中的每一列表示一架UCAV与紧急任务的相关性，矩阵B则表示各约束项与任务的相关性。显然只要对于矩阵Y中的各列向量进行分析，即可一次性的得出与最优UCAV的聚类结果。

例如，某奇异值分解后矩阵Y的值如表1所示。

表1 矩阵Y奇异值分解值

由于L1所代表的无人机为完全契合紧急任务而假设的最优UCAV，将其投影到后2维数据代表的平面上，如图2所示。

图2 右奇异矩阵Y二维投影

很明显可以看到与最优UCAV代表的L1较为接近的为无人机L8和L3，说明适合执行当前任务，而L6、L9等无人机则与当前任务要求相差较远。

4 算法复杂度

利用式(2)计算两个向量夹角时，其计算量为O(|a|+|b|)，不失一般性的可以认为计算量为O(|a|)，如果存在n个紧急任务则需要，则计算复杂度为O(N·|a)，但在算法实现过程中仍有许多可简化的部分，如式(2)分母部分不需重复计算，在计算向量a和向量b的余弦时，向量长度可以存储进数据结构供后续使用过程中直接使用，可以减少总计算量的2/3；同样式(2)的分子，两个向量的内积计算时只需考虑向量中的非零元素，此时复杂度取决于两个向量中非零元素个数的最小值，如果存在一半的零元素，计算的复杂度大约可以下降到原来的1%。

奇异值分解算法复杂度主要存在于矩阵变换为双对角阵，其计算量为O(MN2)，实际计算中也可以利用矩阵的稀疏性进一步缩短计算时间。

5 结束语

对于紧急任务多UCAV优选任务分配采用奇异值分解算法可以一次性得到结果，但是分类结果稍显粗糙，可以在分类后进一步使用最优UCAV聚类的方法细分，两种方法交替使用，得到较精确的结果。

[1] 李远.多UAV协同任务资源分配与编队轨迹优化方法研究[D].长沙：国防科学技术大学,2011.

[2] 王强.UAV集群自主协同决策控制关键技术研究[D].西安：西北工业大学,2015.

[3] 龙涛.多UCAV协同任务控制中分布式任务分配与任务协调技术研究[D].长沙：国防科学技术大学,2006.

[4] 田箐.多无人机协同侦察任务规划问题建模与优化技术研究[D].长沙：国防科学技术大学,2007.

[5] 吴军.数学之美[M].北京：人民邮电出版社,2012:137-143.

[6] 戴定川，盛怀洁，赵域.无人机任务规划系统需求分析[J].飞航导弹,2011(3):66-70.

[7] 姚敏，王绪芝，赵敏.无人机群协同作战任务分配方法研究[J].电子科技大学学报,2010,42(5):723-727.

[8] 刘跃峰，张安.有人机/无人机编队协同任务分配方法[J].系统工程与电子技术,2010,32(3):584-588.

[9] 王勋，姚佩阳.文化算法在有人/无人机协同作战目标分配中的应用[J].空军工程大学学报(自然科学版),2016,17(2):22-25.

[10]叶文，朱爱红，潘长鹏，等.多UCAV协同目标分配算法研究[J].系统工程与电子技术,2010,32(1):104-108.

[11]陈卫，汤超君．基于状态的某型无人机系统维修研究[J].重庆理工大学学报(自然科学)，2014(1)：102-104．

(责任编辑 杨继森)

SVD Algorithm for Multiple Unmanned Combat Air Vehicles Emergent Task Allocation

CHEN Chen

(College of Information and Navigation, Air Force Engineering University, Xi’an 710077, China)

A stable algorithm for multiple Unmanned Combat Air Vehicles(UCAV) dynamic emergent task allocation with the practical battlefield requirement was proposed. We extracted the task related parameters to be a multi-dimensional feature vector and constructed UCAV parameters matrix in the whole control range, and then calculated the cosine between different multi-dimensional feature vector and the right singular matrix to allocate emergent task. At last, we verified the applicability and analyzed the complexity of the algorithm. The algorithm is concise which is in line with the operational flow requirement of stability and rapidly.

multiple UCAV; task allocation; feature vector; singular value decomposition

2016-06-12；

2016-07-05

陈琛(1982—)，男，硕士，讲师，主要从事飞行器任务规划研究。

10.11809/scbgxb2016.10.019

陈琛.多架无人作战飞机紧急任务分配奇异值分解算法[J].兵器装备工程学报，2016(10):93-95.

format:CHEN Chen.SVD Algorithm for Multiple Unmanned Combat Air Vehicles Emergent Task Allocation[J].Journal of Ordnance Equipment Engineering,2016(10):93-95.

TP391

A

2096-2304(2016)10-0093-03