陳 琛

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安 710077)

?

【信息科學(xué)與控制工程】

多架無(wú)人作戰(zhàn)飛機(jī)緊急任務(wù)分配奇異值分解算法

陳 琛

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安 710077)

從戰(zhàn)場(chǎng)實(shí)際需求出發(fā)，在動(dòng)態(tài)條件下對(duì)多無(wú)人機(jī)緊急任務(wù)分配問(wèn)題提出了一種可行穩(wěn)健算法；將無(wú)人機(jī)與任務(wù)相關(guān)的狀態(tài)參數(shù)提取為多維特征向量，構(gòu)造控制單元范圍內(nèi)所有無(wú)人機(jī)狀態(tài)參數(shù)矩陣，通過(guò)計(jì)算特征向量方向余弦值并利用矩陣奇異值分解后的右奇異值矩陣優(yōu)選分配緊急任務(wù)，進(jìn)行了算例驗(yàn)證并分析了算法復(fù)雜度。算法簡(jiǎn)潔、計(jì)算耗時(shí)少，符合作戰(zhàn)流程中對(duì)該問(wèn)題求解的可靠性、迅速性要求。

多無(wú)人機(jī)；任務(wù)分配；特征向量；奇異值分解

無(wú)人作戰(zhàn)飛機(jī)(UCAV)近年來(lái)得到了廣泛的應(yīng)用。在現(xiàn)代戰(zhàn)場(chǎng)復(fù)雜環(huán)境中，根據(jù)任務(wù)的不同約束條件并進(jìn)行有效的策略控制，實(shí)現(xiàn)多架UCAV協(xié)同作戰(zhàn)達(dá)到整體最優(yōu)作戰(zhàn)效能是目前研究的熱點(diǎn)。但對(duì)多無(wú)人機(jī)任務(wù)分配研究多集中在初始條件下預(yù)先規(guī)劃[1-4]，而對(duì)任務(wù)執(zhí)行過(guò)程中的動(dòng)態(tài)分配缺少深入研究。本研究針對(duì)戰(zhàn)場(chǎng)出現(xiàn)狀況突發(fā)的緊急任務(wù)條件下，根據(jù)首長(zhǎng)決心需要對(duì)協(xié)同作戰(zhàn)的多UCAV進(jìn)行緊急調(diào)度，優(yōu)選出若干架次UCAV進(jìn)行動(dòng)態(tài)任務(wù)分配問(wèn)題研究，提出一種實(shí)用高效的穩(wěn)健算法。

1 問(wèn)題描述

在地面/空中任務(wù)單元的控制下，由多種類型的UCAV對(duì)給定區(qū)域內(nèi)預(yù)先偵察確定的目標(biāo)集合進(jìn)行協(xié)同打擊，是UCAV的主要作戰(zhàn)模式之一[1]。典型的作戰(zhàn)模式如圖1所示。

在此場(chǎng)景下，如出現(xiàn)突發(fā)緊急任務(wù)，該控制單元范圍內(nèi)能否優(yōu)選出任務(wù)所需架次的UCAV主要取決于UCAV平臺(tái)配置和基本限定條件兩個(gè)方面的約束條件。

UCAV平臺(tái)配置約束主要指UCAV可分為攻擊型無(wú)人機(jī)、偵察型無(wú)人機(jī)和察打一體無(wú)人機(jī)，緊急任務(wù)的性質(zhì)不同決定了UCAV平臺(tái)配置約束為強(qiáng)約束。

基本限定條件約束主要是指當(dāng)前各UCAV狀態(tài)與任務(wù)要求的契合度，主要包括：與目標(biāo)點(diǎn)之間的飛行距離、彈藥戰(zhàn)斗部類型、配備傳感器類型等因素，這些約束在一些情況下也可以轉(zhuǎn)變?yōu)閺?qiáng)約束，例如到達(dá)目標(biāo)點(diǎn)飛行距離如果超出了該UCAV剩余的最大續(xù)航能力，即無(wú)人機(jī)無(wú)法飛抵目標(biāo)，則該約束必然為強(qiáng)約束。

圖1 多UCAV協(xié)同作戰(zhàn)場(chǎng)景

為了減少人工處理的工作量，對(duì)所有的約束條件不區(qū)分強(qiáng)弱約束，將同一UCAV的所有狀態(tài)參數(shù)對(duì)應(yīng)一個(gè)向量的不同維度，生成一個(gè)n維向量X。

每個(gè)向量對(duì)應(yīng)一架UCAV，假設(shè)該控制單元范圍內(nèi)共有M架UCAV，則可以用一個(gè)N×M的矩陣A來(lái)表示范圍內(nèi)所有無(wú)人機(jī)的狀態(tài)。

2 最優(yōu)UCAV聚類

b和c為兩個(gè)以A為起點(diǎn)的向量，那么∠A的余弦值計(jì)算公式：

(1)

其中分母表示兩個(gè)向量b和c的長(zhǎng)度，分子表示的是兩個(gè)向量的內(nèi)積，將其擴(kuò)展到n維的情況，利用下式可以得到更為一般的計(jì)算公式。

(2)

3 奇異值分解算法

采用向假設(shè)的最優(yōu)UCAV向量聚類的方法易于算法實(shí)現(xiàn)，但在計(jì)算過(guò)程中需要一一計(jì)算所有的余弦值，當(dāng)問(wèn)題規(guī)模擴(kuò)大時(shí)，遍歷所有的向量耗時(shí)較長(zhǎng)[6-8]。對(duì)于規(guī)模擴(kuò)大后的同一問(wèn)題，可以稍加處理后采用奇異值分解的方法一次性計(jì)算與最優(yōu)UCAV的契合度[9-10]。

其中，每一列代表一架UCAV，每一行代表與任務(wù)相關(guān)的一個(gè)約束項(xiàng)，第一列代表虛擬最優(yōu)UCAV，對(duì)該矩陣進(jìn)行奇異值分解可得：

其中B為對(duì)角陣，由于矩陣奇異值在大小上遞減非?？?，即矩陣B中很多對(duì)角元素非常小或?yàn)?，可以省略，因此可進(jìn)一步簡(jiǎn)化為

其中r是遠(yuǎn)小于m、n的數(shù)，極大減少了算法實(shí)現(xiàn)過(guò)程中的存儲(chǔ)量。X、B、Y3個(gè)矩陣具有非常明顯的物理意義，矩陣X中的每一行表示任務(wù)相關(guān)的一個(gè)約束項(xiàng)，矩陣Y中的每一列表示一架UCAV與緊急任務(wù)的相關(guān)性，矩陣B則表示各約束項(xiàng)與任務(wù)的相關(guān)性。顯然只要對(duì)于矩陣Y中的各列向量進(jìn)行分析，即可一次性的得出與最優(yōu)UCAV的聚類結(jié)果。

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

表1 矩陣Y奇異值分解值

由于L1所代表的無(wú)人機(jī)為完全契合緊急任務(wù)而假設(shè)的最優(yōu)UCAV，將其投影到后2維數(shù)據(jù)代表的平面上，如圖2所示。

圖2 右奇異矩陣Y二維投影

很明顯可以看到與最優(yōu)UCAV代表的L1較為接近的為無(wú)人機(jī)L8和L3，說(shuō)明適合執(zhí)行當(dāng)前任務(wù)，而L6、L9等無(wú)人機(jī)則與當(dāng)前任務(wù)要求相差較遠(yuǎn)。

4 算法復(fù)雜度

利用式(2)計(jì)算兩個(gè)向量夾角時(shí)，其計(jì)算量為O(|a|+|b|)，不失一般性的可以認(rèn)為計(jì)算量為O(|a|)，如果存在n個(gè)緊急任務(wù)則需要，則計(jì)算復(fù)雜度為O(N·|a)，但在算法實(shí)現(xiàn)過(guò)程中仍有許多可簡(jiǎn)化的部分，如式(2)分母部分不需重復(fù)計(jì)算，在計(jì)算向量a和向量b的余弦時(shí)，向量長(zhǎng)度可以存儲(chǔ)進(jìn)數(shù)據(jù)結(jié)構(gòu)供后續(xù)使用過(guò)程中直接使用，可以減少總計(jì)算量的2/3；同樣式(2)的分子，兩個(gè)向量的內(nèi)積計(jì)算時(shí)只需考慮向量中的非零元素，此時(shí)復(fù)雜度取決于兩個(gè)向量中非零元素個(gè)數(shù)的最小值，如果存在一半的零元素，計(jì)算的復(fù)雜度大約可以下降到原來(lái)的1%。

奇異值分解算法復(fù)雜度主要存在于矩陣變換為雙對(duì)角陣，其計(jì)算量為O(MN2)，實(shí)際計(jì)算中也可以利用矩陣的稀疏性進(jìn)一步縮短計(jì)算時(shí)間。

5 結(jié)束語(yǔ)

對(duì)于緊急任務(wù)多UCAV優(yōu)選任務(wù)分配采用奇異值分解算法可以一次性得到結(jié)果，但是分類結(jié)果稍顯粗糙，可以在分類后進(jìn)一步使用最優(yōu)UCAV聚類的方法細(xì)分，兩種方法交替使用，得到較精確的結(jié)果。

[1] 李遠(yuǎn).多UAV協(xié)同任務(wù)資源分配與編隊(duì)軌跡優(yōu)化方法研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué),2011.

[2] 王強(qiáng).UAV集群自主協(xié)同決策控制關(guān)鍵技術(shù)研究[D].西安：西北工業(yè)大學(xué),2015.

[3] 龍濤.多UCAV協(xié)同任務(wù)控制中分布式任務(wù)分配與任務(wù)協(xié)調(diào)技術(shù)研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué),2006.

[4] 田箐.多無(wú)人機(jī)協(xié)同偵察任務(wù)規(guī)劃問(wèn)題建模與優(yōu)化技術(shù)研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué),2007.

[5] 吳軍.數(shù)學(xué)之美[M].北京：人民郵電出版社,2012:137-143.

[6] 戴定川，盛懷潔，趙域.無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)需求分析[J].飛航導(dǎo)彈,2011(3):66-70.

[7] 姚敏，王緒芝，趙敏.無(wú)人機(jī)群協(xié)同作戰(zhàn)任務(wù)分配方法研究[J].電子科技大學(xué)學(xué)報(bào),2010,42(5):723-727.

[8] 劉躍峰，張安.有人機(jī)/無(wú)人機(jī)編隊(duì)協(xié)同任務(wù)分配方法[J].系統(tǒng)工程與電子技術(shù),2010,32(3):584-588.

[9] 王勛，姚佩陽(yáng).文化算法在有人/無(wú)人機(jī)協(xié)同作戰(zhàn)目標(biāo)分配中的應(yīng)用[J].空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,17(2):22-25.

[10]葉文，朱愛(ài)紅，潘長(zhǎng)鵬，等.多UCAV協(xié)同目標(biāo)分配算法研究[J].系統(tǒng)工程與電子技術(shù),2010,32(1):104-108.

[11]陳衛(wèi)，湯超君．基于狀態(tài)的某型無(wú)人機(jī)系統(tǒng)維修研究[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2014(1)：102-104．

(責(zé)任編輯 楊繼森)

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—)，男，碩士，講師，主要從事飛行器任務(wù)規(guī)劃研究。

10.11809/scbgxb2016.10.019

陳琛.多架無(wú)人作戰(zhàn)飛機(jī)緊急任務(wù)分配奇異值分解算法[J].兵器裝備工程學(xué)報(bào)，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