多架無人作戰飛機緊急任務分配奇異值分解算法

陳 琛

(空軍工程大學 信息與導航學院，西安 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