無人機多目標(biāo)偵察航跡規(guī)劃方法

劉志陽， 江 濤

(1.空軍工程大學(xué)航空機務(wù)士官學(xué)校，河南 信陽 464000； 2.陸軍工程大學(xué)石家莊校區(qū)，石家莊 050003)

0 引言

無人機航跡規(guī)劃是任務(wù)規(guī)劃的重要內(nèi)容，可以有效地提升無人機的作戰(zhàn)效能。偵察型無人機執(zhí)行任務(wù)時通常不會針對單一目標(biāo)，往往是單次任務(wù)包含多個目標(biāo)，這就涉及到任務(wù)分配問題中的多目標(biāo)時序分配問題[1]。

一般任務(wù)分配問題可以轉(zhuǎn)化為典型的組合優(yōu)化問題模型，然后利用與之相關(guān)的理論求解。目前典型的任務(wù)分配模型有：旅行商問題(TSP)模型[2]、車輛路由問題(VRP)模型[3]、混合整數(shù)線性規(guī)劃(MILP)模型[4]、動態(tài)網(wǎng)絡(luò)流優(yōu)化(DNFO)模型[5]等。

本文的研究背景選定為偵察型無人機在任務(wù)區(qū)域?qū)Χ囝愋偷亩鄠€目標(biāo)進行偵察,因此選擇TSP模型。

目前用于無人機航跡規(guī)劃的尋優(yōu)方法有很多，本文選擇的航跡規(guī)劃方法為改進智能單粒子優(yōu)化(ISPO)算法，該算法在筆者前一階段的研究中已充分論證了其可靠性和優(yōu)越性。在本文中對航跡初始化方法和航跡編碼方式進行了調(diào)整和優(yōu)化，并通過Matlab仿真實驗比較了改進ISPO算法、帶動態(tài)變化慣性權(quán)系數(shù)的PSO算法及具備反向?qū)W習(xí)和局部學(xué)習(xí)能力的粒子群(RLPSO)算法[6]的性能。結(jié)果表明，3種算法能有效完成航跡規(guī)劃的尋優(yōu)計算，規(guī)劃結(jié)果的質(zhì)量、穩(wěn)定性和計算效率由高到低的順序為改進ISPO算法、RLPSO算法和帶動態(tài)變化慣性權(quán)系數(shù)的PSO算法。在后文中提到的PSO算法都是帶動態(tài)變化慣性權(quán)系數(shù)的PSO算法。

針對TSP問題，文獻(xiàn)[7]提出了一種改進帝國競爭算法(ICA)，該算法在求解TSP問題時有較高的求解質(zhì)量和效率。本文參考該文獻(xiàn)采用改進ICA算法求解，并在帝國增強階段加入了帝國合并策略，并以與航跡長度和航跡復(fù)雜程度有關(guān)的函數(shù)為目標(biāo)函數(shù)。

針對本文的研究背景，把目標(biāo)劃分為點目標(biāo)、線目標(biāo)和面目標(biāo)，在任務(wù)區(qū)域中可以把相對比較集中的點目標(biāo)轉(zhuǎn)化為線目標(biāo)或者面目標(biāo)，因此，在有界的區(qū)域中目標(biāo)個數(shù)不會很多，所以本文研究的是小規(guī)模的TSP問題。通過Matlab分別計算了所有5個、6個和7個目標(biāo)的航跡，對比ICA算法和離散型螢火蟲群優(yōu)化(DGSO)算法[8]計算的航跡，發(fā)現(xiàn)ICA算法能夠有效地完成無人機任務(wù)區(qū)域航跡規(guī)劃任務(wù)并準(zhǔn)確找到最優(yōu)解，其計算結(jié)果優(yōu)于DGSO算法的計算結(jié)果。

1 TSP模型

在本文中采用的偵察手段為照相偵察，使用的偵察設(shè)備為可見光照相機。研究中，假設(shè)目標(biāo)處在拍攝范圍內(nèi)即可完成偵察，因而將目標(biāo)分為點目標(biāo)、線目標(biāo)和面目標(biāo)。

點目標(biāo)的尺寸需小于照相機在地面的拍攝范圍。假設(shè)照相機的拍攝范圍為l0×l0。為保證偵察效果，需要無人機在目標(biāo)進入拍攝范圍到離開拍攝范圍期間保持平飛直飛。考慮到無人機機動的需要，假設(shè)無人機的最小轉(zhuǎn)彎半徑為rmin，因此直飛的距離為2L0。

(1)

圖1所示為點目標(biāo)的偵察模式示意圖。

圖1 點目標(biāo)的偵察模式示意圖Fig.1 Reconnaissance mode to point target

線目標(biāo)和面目標(biāo)的尺寸通常大于照相機的拍攝范圍，需要采用廣域搜索模式[9]。線目標(biāo)偵察模式如圖2所示，和點目標(biāo)一樣進入前后各增加L0的飛行距離，無人機沿線目標(biāo)方向飛行。面目標(biāo)偵察模式如圖3所示，面目標(biāo)可以用一個矩形來表示，同理，進入前后各增加L0的飛行距離。

圖2 線目標(biāo)的偵察模式示意圖Fig.2 Reconnaissance mode to linear target

圖3 面目標(biāo)的偵察模式示意圖Fig.3 Reconnaissance mode to area target

對有n個目標(biāo)的TSP問題，本文采取如下的編碼方式：每種可能的編碼都是從1～n的全排列序列(a1,…,ai,…,an)，其中，ai為[1,n]之間的整數(shù)，表示目標(biāo)的序號，i表示ai在序列中的位置，每一個序列在ICA中表示一個國家。

2 改進ISPO航跡算法

2.1 航跡編碼和初始化

在基于改進ISPO算法的航跡規(guī)劃方法中，沒有種群的概念，整個迭代過程只有一個粒子，也就是只對一條航跡進行優(yōu)化。在傳統(tǒng)的TSP問題中，點與點之間的路徑通常以連接前后兩點的直線表示。但是，這樣的路徑并不能滿足無人機的偵察和機動性能的要求。因此，在目標(biāo)與下一個目標(biāo)之間加入一個航跡點，對點目標(biāo)的偵察可以從任意方向進入，也可以在允許的范圍內(nèi)偏離點目標(biāo)。改進ISPO算法中的粒子向量為

X=[x1,…,xn,y1,…,yn,θ1,…,θnp,ll1,…,llnp]

式中：[x1,…,xn]為目標(biāo)與目標(biāo)之間航跡點的橫坐標(biāo)；[y1,…,yn]為其縱坐標(biāo)；n為目標(biāo)個數(shù)；[θ1,…,θnp]為點目標(biāo)的進入方向；[ll1,…,llnp]為偏離點目標(biāo)的距離；np為點目標(biāo)個數(shù)。

航跡初始化分為航跡點初始化和點目標(biāo)初始化。航跡點初始化時，航跡點位于連接前一目標(biāo)和后一目標(biāo)的航跡的中點；點目標(biāo)初始化時，采用在允許的范圍內(nèi)取隨機值的方法。圖4為航跡初始化示意圖，圖中紅色部分為目標(biāo)。

圖4 航跡初始化Fig.4 Route initialization

2.2 航跡代價函數(shù)

航跡代價函數(shù)所求得的航跡代價是評判航跡優(yōu)劣的標(biāo)準(zhǔn)，在本文的研究中只考慮時效性和機動性限制。

時效性取決于航跡的長度，偵察每個目標(biāo)的航跡長度是一定的，所以可不予考慮，只需要考慮目標(biāo)以外的航跡長度，計算可得

(2)

式中：L表示總的時效性指標(biāo)；kL為一常數(shù)；n為航跡點的個數(shù)，與目標(biāo)點的個數(shù)相同；l1i表示第i個航跡點與前一個目標(biāo)偵察結(jié)束點的航跡段長度；l2i表示第i個航跡點與后一個目標(biāo)偵察開始點的航跡段長度。

在本文中，機動性主要考慮無人機的機動性能約束，在目標(biāo)前后分別增加一個最小轉(zhuǎn)彎半徑的直飛距離，可以保證無人機在偵察完畢后或者開始前進行充分的機動。機動性指標(biāo)為

(3)

本文所采用的無人機機動性能限制方法為：把半徑為無人機最小轉(zhuǎn)彎半徑的圓放入前一個拐角的凹側(cè)并與該拐角的兩條航跡段相切，計算下一條航跡與該圓相切時的角度θ2imax。因采用arccos(·)函數(shù)求夾角，所以不論向量相對前一向量的方向向左或者向右偏，所求得的結(jié)果都相同。如圖5所示，如果l2i向左偏，θ2i超過θ2imax，那么l1i的長度將滿足不了飛行器機動的需求。

圖5 無人機機動性能限制Fig.5 UAV maneuverability limit

綜上所述，航跡代價函數(shù)可由以上兩個指標(biāo)加權(quán)求和得到

J(X)=w1L+w2D

(4)

式中：J為航跡代價；X為一條完整的航跡；w1，w2為兩個權(quán)系數(shù)，分別表示其所對應(yīng)的指標(biāo)的重要程度，在本文中假設(shè)它們同等重要，w1=w2=0.5。

改進ISPO算法這里就不做過多的介紹。通過改進ISPO算法計算最終得到的最優(yōu)航跡代價可以計算ICA中的每個國家的權(quán)力。

社會醫(yī)療保險作為社會保障制度的一個子系統(tǒng)，要減少慢性病患者的疾病經(jīng)濟風(fēng)險，離不開其他貧困資助政策、養(yǎng)老保險、大病保險等社會保障制度的支持。國家衛(wèi)計委已于2017年再啟動實施“三個一批”行動計劃(按大病集中救治一批、慢病簽約服務(wù)管理一批、重病兜底保障一批)，截止到2017年5月已分類救治貧困患者260多萬人[22]。當(dāng)然，對低收入患者的托底政策需進一步制度化。

3 改進ICA

文獻(xiàn)[10]于2007年提出了一種社會政治進化算法，并將其命名為帝國競爭算法(ICA)，該算法是對人類帝國的殖民與競爭過程的模擬。

3.1 改進ICA算法流程

1) 建立初始帝國。按照前文中提到的TSP問題的編碼方式隨機生成Npop個初始國家，并選擇權(quán)力由大到小排列的前Nimp個國家作為殖民國家，其余Ncol個國家作為殖民地。同時根據(jù)殖民國家權(quán)力的大小按比例分配殖民地個數(shù)，殖民國家和其所屬的殖民地國家共同構(gòu)成了一個帝國。

2) 殖民地同化。根據(jù)一定的同化規(guī)則，殖民國家對其所屬的殖民地國家進行同化，使殖民地國家逐漸趨同于殖民國家。

3) 殖民地革命。以一定的概率對殖民地進行革命操作，革命操作會隨機改變原殖民地國家的編碼序列，這樣可以增強殖民地國家的多樣性。在同化和革命完成后，計算帝國內(nèi)所有國家的權(quán)力，選擇權(quán)力最大的國家作為帝國的殖民國家。

4) 帝國增強。按照一定的規(guī)則對每個帝國的殖民國家進行帝國增強操作,這樣可以增強殖民國家的多樣性，避免算法早熟收斂。

5) 殖民競爭。該步驟是算法收斂的關(guān)鍵。在完成上述步驟以后，每個帝國的結(jié)構(gòu)都有了改變，按照一定的規(guī)則計算整個帝國的權(quán)力,并以這個權(quán)力為標(biāo)準(zhǔn)，把權(quán)力最小的帝國中的最小權(quán)力殖民地重新分配給權(quán)力最大的帝國。如果某個帝國中沒有殖民地國家，那么這個帝國將會消失。

改進ICA算法的流程就是不斷循環(huán)步驟2)～5)，直到滿足迭代次數(shù)要求或者僅剩一個帝國。算法的詳細(xì)內(nèi)容可參考文獻(xiàn)[7]，本文不做過多描述。

3.2 算法改進

因此，本文提出了帝國合并的策略。在帝國增強完成后，把殖民國家相同的帝國進行合并，新帝國的殖民國家不變，所有相同殖民國家的殖民地歸于新帝國。這樣的操作不會影響原來的運算步驟，還大大加強了算法收斂的速率。實驗結(jié)果表明，算法改進后計算耗時大大縮短,同時，兩種算法所得到的最優(yōu)結(jié)果一致。

4 算法實驗與分析

本文仿真計算是在Intel(R)Core(TM)i7- 6700 CPU@3.40 GHz,8 GB內(nèi)存的計算機上進行的，計算機系統(tǒng)為Windows7，仿真計算軟件為Matlab R2014b。目標(biāo)區(qū)域設(shè)定為以(185 km,185 km)為頂點的15 km×15 km的方形區(qū)域。

4.1 改進ISPO算法實驗

本實驗所涉及的一系列參數(shù)：無人機的最小轉(zhuǎn)彎半徑rmin=1 km，l0=500 m；PSO算法中，最大慣性權(quán)系數(shù)ωmax為1.4，最小慣性權(quán)系數(shù)ωmin為0.8；學(xué)習(xí)因子c1=c2=2；在RLPSO算法中，反向?qū)W習(xí)因子c3=0.7，c4=0.3；反向?qū)W習(xí)代數(shù)s0=10；反向?qū)W習(xí)種群規(guī)模m=28；擾動系數(shù)初始值d0=40；反向?qū)W習(xí)條件為種群最優(yōu)解連續(xù)10代沒有變化；在改進ISPO算法中，當(dāng)確定多樣性因子時，A為[15，15，0.5]；下降因子p為1.55；收縮因子s為4；加速度因子b為2；kG取0.3；飛行的起點為(185 km,200 km)。

綜合考慮航跡計算精度與航跡表示精度，通過大量的實驗，設(shè)定PSO算法和RLPSO算法的種群數(shù)量N為40，目標(biāo)點數(shù)量為5，最大迭代次數(shù)為50。改進ISPO算法的航跡迭代次數(shù)Nx為15，航跡點迭代次數(shù)為10。每種算法進行200次運算。實驗數(shù)據(jù)如表1所示。

表1 3種算法的航跡代價比較

模型1的航跡規(guī)劃結(jié)果如圖6所示，航跡代價變化如圖7所示。

圖6 模型1的航跡規(guī)劃結(jié)果Fig.6 The result of route planning of Model 1

圖7 航跡代價變化曲線Fig.7 The curve of route cost

改進ISPO算法、RLPSO算法和PSO算法平均總耗時分別為0.65 s，1.22 s和0.85 s。

4.2 改進ICA算法實驗

為了驗證改進ICA算法針對本文的研究背景所設(shè)定的問題的有效性，設(shè)計了5種本文研究背景可能涉及到的TSP模型進行算法驗證，分別為5個目標(biāo)的1種、6個目標(biāo)和7個目標(biāo)各2種，同目標(biāo)個數(shù)的不同情況之間目標(biāo)類型與位置不同。

本文實驗所涉及的一系列參數(shù)：改進ICA算法初始國家個數(shù)與DGSO算法初始種群數(shù)量均設(shè)置為50，迭代次數(shù)均為250。帝國個數(shù)約占國家總數(shù)的10%～20%時,改進ICA算法的求解質(zhì)量較為理想，因此帝國個數(shù)取15。其余參數(shù)的選擇均與原文獻(xiàn)中算法的參數(shù)一致。為了客觀比較算法的優(yōu)劣性，每種情況的每條航跡采用相同的航跡代價，該航跡代價采用改進ISPO算法進行3次重復(fù)的計算，取最小值。表2為5種不同的情況2種算法實驗結(jié)果的對比，每種模型的最優(yōu)解是通過計算所有可能的情況得到的。

表2 2種算法的航跡代價比較

沒有引入帝國合并策略的ICA算法同樣計算上述5種模型，所花的時間分別為1 440.21 s,2 052.25 s,2 153.15 s,7 854.82 s,7 556.36 s，改進ICA算法與ICA算法偏差率一致。由此可以說明，帝國合并策略的引入在不改變算法運算品質(zhì)的前提下提高了計算效率。

模型2～5的航跡規(guī)劃結(jié)果如圖8所示。

圖8 模型2～5的航跡規(guī)劃結(jié)果Fig.8 Route planning results of Model 2～5

4.3 算法分析比較

從表1中可以看出，航跡代價平均值、方差和極差從小到大排列的順序都為改進ISPO算法、RLPSO算法和PSO算法，這說明改進ISPO算法具有更強的尋優(yōu)能力，計算的穩(wěn)定性也更好，可以把最終的尋優(yōu)結(jié)果控制在一個較小的范圍內(nèi)，這樣有利于TSP問題的求解，避免產(chǎn)生較大的偏差。

計算耗時由短到長排列為改進ISPO算法、PSO算法和RLPSO算法。由圖7可知，收斂速率由大到小排列為改進ISPO算法、RLPSO算法和PSO算法。因此可以看出，改進ISPO算法具有較高的計算效率，能夠大大提高求解TSP問題的效率。

從表2的偏差率結(jié)果可以得出結(jié)論，改進ICA算法能夠有效解決針對本文所設(shè)定的背景的TSP問題。

在模型3和模型4中，2種算法的偏差率比較可以說明，改進ICA算法在較為復(fù)雜的情況下求解精度上具有明顯的優(yōu)勢。

從計算耗時上來看，當(dāng)TSP問題規(guī)模較小時，改進ICA算法和DGSO算法接近，但是，隨著問題規(guī)模的擴大，改進ICA算法的計算效率相較于DGSO算法越來越高。

5 結(jié)論

本文把無人機多目標(biāo)偵察航跡規(guī)劃問題轉(zhuǎn)化為TSP問題，并通過改進ICA算法對其進行求解，求解時采用改進ISPO算法進行航跡優(yōu)化和航跡代價求取。通過仿真實驗驗證了該方法能夠有效解決無人機目標(biāo)區(qū)域航跡規(guī)劃問題，同時具有較高的計算精度。