葉家君， 劉學(xué)文， 蔣 莎

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院 重慶 401331)

近年來(lái)，由于地震、洪水等的頻繁發(fā)生使得無(wú)人機(jī)的研究成為國(guó)內(nèi)外的一種新潮。如何規(guī)劃無(wú)人機(jī)的路線，快速探測(cè)生命跡象以及對(duì)災(zāi)區(qū)的信號(hào)傳輸是無(wú)人機(jī)的一個(gè)重要使命。目前國(guó)內(nèi)外學(xué)者對(duì)無(wú)人機(jī)的航跡規(guī)劃進(jìn)行了大量的研究。孫小雷等[1]研究了多無(wú)人機(jī)交會(huì)過(guò)程的協(xié)同航跡規(guī)劃，提出了沿Dubins路徑飛行，建立了以最小化執(zhí)行時(shí)間降低風(fēng)險(xiǎn)的雙目標(biāo)規(guī)劃方法，實(shí)現(xiàn)了無(wú)人機(jī)可攻擊范圍的交會(huì)。李牧等[2]提出了基于3層決策模型的平滑航跡規(guī)劃方法，在不同場(chǎng)景地形的仿真，得到了較高的可執(zhí)行性、安全、平滑的飛行路徑。Wen等[3]建立了規(guī)劃成本最低、路徑搜索最快和路徑威脅最小的多目標(biāo)優(yōu)化模型，引入RH方法解決了動(dòng)態(tài)未知局部環(huán)境下的航跡規(guī)劃，用蒙特卡洛進(jìn)行結(jié)果仿真，證明了該算法在實(shí)際路徑規(guī)劃中具有突防可能性。Chen等[4]提出了改進(jìn)的狼群搜索算法，計(jì)算了三維真實(shí)空間和虛擬空間中無(wú)人機(jī)的最優(yōu)航跡，構(gòu)建了多目標(biāo)成本優(yōu)化模型，仿真結(jié)果證明，改進(jìn)后的WPS算法生成軌跡優(yōu)于原算法和隨機(jī)搜索方式。周青等[5]分析了無(wú)人機(jī)航跡規(guī)劃的路徑有效性和到達(dá)時(shí)間約束，并將遺傳算法應(yīng)用到動(dòng)態(tài)環(huán)境中，通過(guò)編碼，明確適應(yīng)度函數(shù)和進(jìn)化操作，實(shí)現(xiàn)了針對(duì)移動(dòng)目標(biāo)的規(guī)劃和突然出現(xiàn)威脅的局部重規(guī)劃。傅陽(yáng)光等[6]在分析時(shí)間誤差分配基礎(chǔ)上，研究了起飛時(shí)間誤差、速度調(diào)節(jié)能力以及飛行速度誤差3個(gè)因素對(duì)目標(biāo)點(diǎn)時(shí)間誤差的不同影響。張延松[7]指出了無(wú)人機(jī)航跡規(guī)劃的定義，根據(jù)威脅及障礙分布情況，構(gòu)造了無(wú)人機(jī)可能飛行的航路集voronoi圖，采用Dijkstra算法搜索威脅及障礙分布圖，最后通過(guò)遺傳算法優(yōu)化初始路徑，并進(jìn)行仿真實(shí)驗(yàn)。馬華偉等[8]建立了UAV流模型，提出了一種兩階段啟發(fā)式算法。第一階段提出了一種基于“最遲完成服務(wù)優(yōu)先”規(guī)劃的航跡，第二階段利用模擬退火算法對(duì)初始值進(jìn)行改進(jìn)，表明了該算法能有效求解帶有時(shí)間窗的UAV航跡問(wèn)題。

本文以總路程最少和時(shí)間均衡度最小為目標(biāo)，在無(wú)人機(jī)飛行約束條件下，建立了雙目標(biāo)優(yōu)化模型。在模型求解時(shí)，通過(guò)引入混沌序列遺傳算法對(duì)模型進(jìn)行求解，充分對(duì)雙目標(biāo)進(jìn)行平衡，得到更合適的航跡優(yōu)化路線。

1 多目標(biāo)優(yōu)化模型

1.1 問(wèn)題描述與假設(shè)

無(wú)人機(jī)航跡優(yōu)化路線是一個(gè)動(dòng)態(tài)的過(guò)程，航跡過(guò)程中最顯著的特點(diǎn)表現(xiàn)在路線的最短化。以往的無(wú)人機(jī)航跡優(yōu)化路線局限于把“路線最短”作為優(yōu)化目標(biāo)，容易導(dǎo)致不同無(wú)人機(jī)航跡時(shí)間間隔較大。因此，考慮“路線最短”和“時(shí)間均衡度最小”，在巡查有效區(qū)域內(nèi)，構(gòu)建綜合可靠性高的優(yōu)化路線。為了更好地分析問(wèn)題，設(shè)立6個(gè)假設(shè)如下。

假設(shè)1 無(wú)人機(jī)在執(zhí)行任務(wù)時(shí)不存在強(qiáng)風(fēng)、暴雨等天氣問(wèn)題影響。

假設(shè)2 無(wú)人機(jī)在拐點(diǎn)處均以其最小轉(zhuǎn)彎半徑進(jìn)行方向轉(zhuǎn)變，且行駛距離不變。

假設(shè)3 不同無(wú)人機(jī)飛行狀態(tài)不影響飛行速度。

假設(shè)4 無(wú)人機(jī)的位置始終處于最大有效探測(cè)距離內(nèi)。

假設(shè)5 無(wú)人機(jī)看成質(zhì)點(diǎn)，忽視無(wú)人機(jī)大小、質(zhì)量。

假設(shè)6 所有無(wú)人機(jī)同時(shí)起飛。

1.2 多目標(biāo)優(yōu)化模型

由以上問(wèn)題和分析可知，在無(wú)人機(jī)飛行高度及巡查范圍受到限制的情況下，構(gòu)建的目標(biāo)優(yōu)化模型如下。

(1) 目標(biāo)函數(shù)。首先考慮無(wú)人機(jī)航跡路線最短化，即無(wú)人機(jī)從各基地出發(fā)到最后返回各基地距離的加權(quán)值最小。子目標(biāo)如下：

考慮到無(wú)人機(jī)航跡時(shí)間間隔最小化，即第一架無(wú)人機(jī)飛出時(shí)間與最后一架無(wú)人機(jī)返回時(shí)間的間隔最小。子目標(biāo)如下：

保證同一架無(wú)人飛機(jī)pk受到燃油消耗的限制，其航行時(shí)間不超過(guò)8小時(shí)，即

根據(jù)上述分析，構(gòu)建多目標(biāo)優(yōu)化模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

在本文中，將采用參數(shù)規(guī)劃方法中的加權(quán)法來(lái)求解上述兩個(gè)目標(biāo)的航跡規(guī)劃模型。通過(guò)調(diào)節(jié)兩個(gè)目標(biāo)賦值的權(quán)數(shù)，可以得出較為理想的結(jié)果。例如若α=1時(shí)，不再考慮均衡度，則所得結(jié)果將會(huì)出現(xiàn)第一架飛機(jī)飛出到最后一架飛機(jī)完成任務(wù)飛回到基地的時(shí)間間隔較長(zhǎng)。若β=1，將不再考慮無(wú)人機(jī)飛行的總路程，則無(wú)人機(jī)可能在規(guī)定的時(shí)間無(wú)法完成任務(wù)。所以通過(guò)調(diào)整α和β的不同取值，將獲得一組權(quán)衡節(jié)解。

2 遺傳算法

顯然，無(wú)人機(jī)航跡規(guī)劃問(wèn)題是一個(gè)NP問(wèn)題，由于其解空間不連續(xù)，解空間表達(dá)困難，所以運(yùn)用傳統(tǒng)的運(yùn)籌學(xué)優(yōu)化方法不能滿足其需求[9]。那么，結(jié)合模型特點(diǎn)及實(shí)際應(yīng)用，將采用收斂性強(qiáng)，收斂速度快的遺傳算法。

(1) 染色體編碼。無(wú)人機(jī)航跡優(yōu)化模型轉(zhuǎn)換為遺傳算法問(wèn)題，在編碼過(guò)程中將采用二進(jìn)制串。根據(jù)無(wú)人機(jī)的架數(shù)將整個(gè)解空間分解為N個(gè)子種群，設(shè)每架無(wú)人機(jī)的航跡優(yōu)化路線是一條染色體，將染色體分為I段，I表示無(wú)人機(jī)飛過(guò)的有效區(qū)域點(diǎn)的位置。

(2) 初始種群的產(chǎn)生。遺傳算法盡可能獲取全局最優(yōu)解，與初始種群的選取有很大的聯(lián)系，子種群生成n條染色體作為無(wú)人機(jī)航跡路線。

(4) 染色體輪盤選擇。根據(jù)染色體的適應(yīng)度，計(jì)算出每條染色體的選擇概率以及累計(jì)概率pi，生成[0,1]間的隨機(jī)數(shù)ri，若ri≥pi，則選擇該染色體，重復(fù)這樣n次操作，將得到n條染色體。

(5) 改進(jìn)的交叉操作。傳統(tǒng)的遺傳算法交叉操作通常采用斷點(diǎn)交叉法、多點(diǎn)交叉法和均勻交叉。根據(jù)本文的數(shù)學(xué)模型將采用改進(jìn)型交叉。首先以“門當(dāng)戶對(duì)”為原則，對(duì)父代的適應(yīng)度函數(shù)值進(jìn)行排序，然后將父代目標(biāo)函數(shù)值小的與小的配對(duì)，大的與大的配對(duì)。將采用Logistic混沌序列xn+1=4xn(1-xn)，隨機(jī)產(chǎn)生一個(gè)數(shù)Q，從而確定交叉點(diǎn)的位置，最后對(duì)確定的交叉項(xiàng)進(jìn)行交叉。

(6) 改進(jìn)的變異操作。同樣采用Logistic混沌序列xn+1=4xn(1-xn)，隨機(jī)產(chǎn)生一個(gè)數(shù)Q，對(duì)選定的染色體Q處選擇變異點(diǎn)進(jìn)行變異。

(7) 終止。若滿足則算法終止，計(jì)算結(jié)束，輸出最佳適應(yīng)值和染色體編碼。根據(jù)染色體編碼繪制出相應(yīng)的無(wú)人機(jī)航跡路線。

3 實(shí)例分析

3.1 實(shí)例描述

為驗(yàn)證上述改進(jìn)算法的有效性，以2017年全國(guó)研究生數(shù)學(xué)建模競(jìng)賽A題“無(wú)人機(jī)在搶險(xiǎn)救災(zāi)中的優(yōu)化應(yīng)用”實(shí)例來(lái)驗(yàn)證。為了及時(shí)探測(cè)生命跡象，提供準(zhǔn)確的目標(biāo)定位，欲使無(wú)人機(jī)攜帶生命探測(cè)儀從基地H(110，0)和J(110，55)(單位：km)處總共派出30架無(wú)人機(jī)(各15架)對(duì)生命跡象進(jìn)行探測(cè)。其中無(wú)人機(jī)探測(cè)儀的有效探測(cè)距離不超過(guò)1 000 m，最大側(cè)視角為60°，最大續(xù)航時(shí)間為8 h，飛行時(shí)的轉(zhuǎn)彎半徑不小于100 m。在滿足無(wú)人機(jī)的飛行條件和生命探測(cè)儀的工作條件下，規(guī)劃合理路線，使得全區(qū)域內(nèi)海拔3 000 m以下部分能被探測(cè)到的面積盡可能大，且使從第一架無(wú)人機(jī)飛出到最后一架完成任務(wù)的無(wú)人機(jī)回到基地的時(shí)間間隔盡量短。

3.2 柵格分區(qū)

通過(guò)無(wú)人機(jī)探測(cè)儀的有效探測(cè)距離以及最大側(cè)視角，可知無(wú)人機(jī)可探測(cè)的最大面積以及無(wú)人機(jī)與地面的最大飛行高度。其次，分析哪些區(qū)域需要被巡查，可以利用“網(wǎng)絡(luò)取點(diǎn)”的方法確定有效的巡查點(diǎn)。由于有效巡查點(diǎn)是由兩個(gè)不同基地的無(wú)人機(jī)分別巡查。所以，將所有有效巡查點(diǎn)分成兩個(gè)區(qū)域，分別由兩個(gè)基地的無(wú)人機(jī)進(jìn)行巡查，分區(qū)原則是兩個(gè)基地分別到區(qū)域各點(diǎn)并且最后返回各基地的用時(shí)基本相等，并且最長(zhǎng)航跡與最短航跡路線距離相差較短。通過(guò)分區(qū)將兩個(gè)基地問(wèn)題轉(zhuǎn)化成了單個(gè)基地問(wèn)題，分別對(duì)兩個(gè)基地的無(wú)人機(jī)進(jìn)行航跡規(guī)劃，如圖1所示。

圖1 H，J基地航跡有效區(qū)域

3.3 路線優(yōu)化

根據(jù)以上的有效巡查的分區(qū)，基于混沌遺傳算法和構(gòu)建的雙目標(biāo)模型，用MATLAB進(jìn)行編程，得到無(wú)人機(jī)從H,J基地出發(fā)的航跡路線(圖2)以及每架無(wú)人機(jī)的航跡路程和時(shí)間(表1)。

圖2 H，J基地航跡路線

在仿真實(shí)驗(yàn)中，無(wú)人機(jī)航跡優(yōu)化問(wèn)題分別利用了單點(diǎn)交叉和換位變異結(jié)合的遺傳算法，多點(diǎn)交叉和均勻變異結(jié)合的遺傳算法以及本文中的混沌序列遺傳算法進(jìn)行求解比較(表2)，且都是以種群規(guī)模60，交配概率0.85，變異概率0.1和迭代次數(shù)500求解的無(wú)人航跡優(yōu)化路程。

表1 H，J基地的無(wú)人機(jī)航跡路程及時(shí)間Table.1 Flight path and time of H，J base UAV

表2 遺傳算法路程優(yōu)化比較Table.2 Distance optimization comparison of genetic algorithms

〗 最后，通過(guò)對(duì)H基地和J基地計(jì)算時(shí)間對(duì)比，來(lái)說(shuō)明改進(jìn)遺傳算法的時(shí)間性能(表3)。

表3 遺傳算法時(shí)間性能比較Table.3 Time performance comparison of genetic algorithms

利用改進(jìn)后強(qiáng)度最弱的單點(diǎn)交叉，保證了算法的收斂精度，削弱了算法因交叉強(qiáng)度大而產(chǎn)生的尋優(yōu)抖振問(wèn)題，而且文中采用了強(qiáng)度較大的多個(gè)基因變異解決了早熟問(wèn)題。從表2可以看出改進(jìn)后的算法效果更明顯，減少了無(wú)人機(jī)航跡路程。通過(guò)以上的圖和表格，可以得出以下的結(jié)論：

(1) 目標(biāo)最小化模型可以有效處理無(wú)人機(jī)航跡問(wèn)題，對(duì)于時(shí)間的均衡性可以有效調(diào)節(jié)無(wú)人機(jī)之間的時(shí)間間隔，能盡快完成全部任務(wù)。

(2) 從圖1和圖2可以看出，柵格分割以及將不同基地出發(fā)的無(wú)人機(jī)進(jìn)行分區(qū)，更能避免無(wú)人機(jī)在執(zhí)行任務(wù)時(shí)發(fā)生碰撞。

(3) 由表1數(shù)據(jù)可知，無(wú)人機(jī)最少花費(fèi)時(shí)間2.456h，最多花費(fèi)時(shí)間3.950h，則時(shí)間間隔為1.494h。所以本文所給的航跡優(yōu)化模型以及混沌遺傳算法是具有一定的可行性。

(4) 根據(jù)表2和表3可知，混沌遺傳算法在求解無(wú)人機(jī)航跡優(yōu)化模型時(shí)有較好的性能。

4 結(jié) 論

針對(duì)無(wú)人機(jī)探測(cè)生命跡象這一難題，構(gòu)建了路程最短和時(shí)間均衡度最少的數(shù)學(xué)模型，設(shè)計(jì)了一種基于混沌遺傳算法的求解。但是，本文僅對(duì)無(wú)人機(jī)探測(cè)生命跡象做了一個(gè)初步探索，旨在能探測(cè)到更多的有效區(qū)域。因此，今后的研究工作將進(jìn)一步推廣數(shù)學(xué)模型，希望無(wú)人機(jī)更廣泛地應(yīng)用在災(zāi)情巡查、災(zāi)區(qū)通信終端以及對(duì)地的數(shù)據(jù)傳輸。

參考文獻(xiàn)(References)：

[1] 孫小雷，孟宇麟，齊乃明，等. 多無(wú)人機(jī)交會(huì)過(guò)程的協(xié)同航跡規(guī)劃方法[J]. 機(jī)器人，2015，37(5)：621-627

SUN X L，MENG Y L，QI N M，et al. Cooperative Path Planning for Rendezvous of Unmanned Aerial Vehicles[J]. Robot,2015，37(5)：621-627

[2] 李牧東，趙輝，黃漢橋，等. 基于TLD模型的UAV三維實(shí)時(shí)平滑航跡規(guī)劃[J]. 系統(tǒng)工程與電子技術(shù)，2017，39(1)：93-100

LI M D，ZHAO H，HUANG H Q，et al.3-D Real-Time Smooth Path Planning for UAV Based on TLD Model[J]. Systems Engineering and Electronics,2017，39(1)：93-100

[3] WEN N,ZHAO L L,SU X H,et al. UAV Online Path Planning Algorithm in a Low Altitude Dangerous Environment[J]. IEEE/CAA Journal of Automatica Sinica,2015，2(2)：173-185

[4] CHEN Y B,MEI Y S,YU J Q,et al. Three Dimensional Unmanned Aerial Vehicle Path Planning Using Modified Pack Search Algorithm[J]. Neurocomputing, 2017，266(29)：445-457

[5] 周青，張銳，索曉潔，等. 具有時(shí)間約束的無(wú)人機(jī)遺傳算法航跡規(guī)劃[J]. 航空計(jì)算技術(shù)，2016，46(2)：93-96，101

ZHOU Q，ZHANG R，SUO X J，et al. Genetic Algorithm for UAV Trajectory Planning with Timing Constraints[J]. Aeronautical Computing Technique,2016，46(2)：93-96，101

[6] 傅陽(yáng)光，周成平，王長(zhǎng)青，等. 考慮時(shí)間約束的無(wú)人機(jī)飛行器航跡規(guī)劃[J]. 宇航學(xué)報(bào)，2011，32(4)：749-755

FU Y G，ZHOU C P，WANG C Q，et al. Path Planning for UAV Considering Time Constraint[J]. Journal of Astronautics,2011，32(4)：749-755

[7] 張延松.基于遺傳算法的無(wú)人機(jī)航跡規(guī)劃研究[J]. 中國(guó)西部科技，2010，9(11)：44-45

ZHANG Y S. Study on a Path Planning for UAV with Genetic Algorithm[J]. Science and Technology of West China,2010，9(11)：44-45

[8] 馬華偉，王天曉，胡笑旋. 帶有時(shí)間窗的無(wú)人機(jī)航跡規(guī)劃兩階段啟發(fā)式算法[J]. 火力與指揮控制，2014，39(8)：12-16，21

MA H W，WANG T X，HU X X. A Two-Stage Heuristic Method for UAV Path Planning with Time Windows[J]. Fire Control & Command Control,2014，39(8)：12-16，21

[9] 司守奎，孫璽菁. 數(shù)學(xué)建模算法與應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2011

SI S K，SUN X J. Mathematical Modeling and Application[M]. Beijing：National Defense Industry Press,2011