基于優化粒子群算法的無人機航路規劃*

張建南， 劉以安， 王 剛

(1.江南大學 物聯網工程學院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

基于優化粒子群算法的無人機航路規劃*

張建南1， 劉以安1， 王 剛2

(1.江南大學 物聯網工程學院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

針對粒子群優化(PSO)算法的無人機(UAV)航路規劃問題，引入慣性權重和自然選擇對粒子群算法進行優化，以提高基本粒子群算法收斂速度，防止陷入局部最優。算法分析慣性權重對粒子群算法的影響，進而調整慣性因子，提高算法的搜索能力；利用自然選擇的便利性和規律性等特點,更新粒子群算法的粒子；同時通過對無人機的可行航向進行限定，縮小搜索范圍。仿真實驗表明:基于粒子群優化算法的無人機航路規劃不僅縮短了最優航路，而且提高了搜索速度。

無人機航路規劃； 粒子群優化算法； 慣性權重； 自然選擇

0 引 言

近年來，隨著科學技術的不斷發展，無人機(unmanned aerial vehicle，UAV)作為控制偵察和作戰的重要手段，正逐漸受到世界各國軍方的關注，這促使科研人員對無人機的各個方面展開更深入的研究。無人機的航路規劃是無人機任務規劃的重要內容之一，目的是在滿足燃料消耗、威脅以及飛行區域等約束條件下，為無人機規劃出一條從初始點到目標點航路評價達到最優的飛行路線，以保證飛行任務的圓滿完成[1]。

航路規劃是一個空間搜索問題，受到國內外大量學者的研究，它主要分為兩類：啟發式算法和進化算法。啟發式算法作為逐點搜索算法，其搜索空間龐大，計算量大，并且規劃效果對啟發函數的依賴性較強；進化算法是一種基于種群的優化算法，常用的進化算法有A*算法[2]、蟻群算-法[3]和遺傳算法[4]等。這些算法自身都存在一定的缺陷，使得路徑搜索存在搜索量大，效率不高等問題，不能保證航路規劃設計的效率和要求。粒子群算法是智能算法的代表方法之一，是一種以隨機搜索為特征的智能算法，通過群體粒子之間的合作與競爭產生的群體智能指導優化搜索，具有實現容易、精度高、方便調整參數等優點，因而在航路規劃問題中得到了廣泛的應用[5]。

粒子群算法思路清晰、運算簡單、易于實現，廣泛用于解決各種優化問題，但是也存在著早熟現象、收斂速度慢，過早陷入局部最優等缺點[6]。針對粒子群算法存在的問題，對粒子群算法進行了優化，使之適用于無人機航路規劃。

1 無人機航路規劃

1.1 飛行環境和任務規劃

無人機航路規劃問題實質屬于最優化問題，它的數學描述由航路優化指標和航路約束條件兩部分組成。求解航路規劃問題，就是在滿足約束條件的前提下，求出航路優化指標函數的全局最優解。航路規劃的目的是要根據任務要求，威脅分布，燃料限制以及無人機自身的機動性能選擇一條使無人機回避威脅，安全完成預定任務的飛行路徑[7]，無人機在空中飛行區域如圖1所示，其飛行任務是從O點飛行到A點，O點和A點之間存在威脅區，這些威脅可能是島嶼、陸地或者雷達，飛行航路就是搜索出一條從O點到A點的既短又安全的航路。

圖1 無人機任務規劃

1.2 編碼方式

假設無人機在某一巡航高度勻速飛行，則航路規劃可以簡化為建立在二維平面環境的基礎上[8]。先建立飛行高度相應的威脅平面分布，然后進行航路規劃。建立笛卡爾坐標系，定義航路初始點和目標點，將起始點到目標點進行n+1等分，令航路點在各個邊界上，這樣每一維的次序表示了粒子在x方向上的位置，每一維的數據表示粒子在y方向上的位置。通過這樣的方式，使每個粒子與起始點和目標點結合，這樣就構成了無人機的一條航路[9]。

1.3 無人機航路規劃代價模型

無人機的航路規劃不僅要使無人機避開可能影響飛行的地形和威脅區域等不利因素，且要求規劃出的航路優化指標最優，通常根據優化指標不同，航路優化分為不同的類型，包括以燃料消耗為指標的最大航程規劃、以無人機飛行距離為指標的最短航程規劃和以戰術效果為指標的最優戰術效果規劃。本文主要考慮無人機的航程代價和威脅代價，其描述為

(1)

航路代價為各個航路段代價之和，設整個航路有n個航路段組成，j為威脅源的數量，li表示第i個航路段的長度，航程代價的作用是使飛機在降低油耗和縮短飛行時間的同時保證航路最短。在雷達參數保持一致的情況下，無人機在任務區域內的x處受到的第j個威脅源的威脅代價為[10]

(2)

在飛機飛行高度的水平截面上，雷達及區域威脅范圍可近似看作一個圓，Rj表示無人機到區域中心的距離，Kj為第j個威脅的強度參數。采用如下方法處理：在每個航路段上取其兩端點和中點三個點，分別求此三點受到的威脅體的威脅概率，則此航路段受到的威脅概率用這兩點受到的威脅概率之和來表示。航路的威脅代價為各航路段威脅代價之和。式(1)中的w1，w2為權重系數，用以調整不同代價在航路代價中的權重。

2 基于粒子群算法的無人機航路規劃

2.1 標準粒子群算法

粒子群算法是模擬鳥群隨機搜尋食物的捕食行為，用于解決優化問題。在粒子群算法中每個優化問題的潛在解都可以想象成搜索空間的一只鳥，稱之為“粒子”。所有的粒子都有一個由被優化的函數決定的適應度值，每個粒子還有一個速度決定它們的飛行的方向和距離。然后粒子就追隨當前的最優粒子在解空間中搜索[11]。

粒子群算法初始化一群隨機粒子，然后通過迭代找到最優解[12]。在每一次迭代過程中，粒子通過跟蹤兩個極值來跟新自己：第一個就是粒子本身所找到的最優解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優解，這個極值是全局極值。假設在一個d維的目標搜索空間中，有n個粒子組成一個群落，其中，第i個粒子為一個d維向量

Xi=(xi1,xi2,…,xid),i=1,2,…,n

第i個粒子的飛行速度也是一個d維向量，記為

Vi=(vi1,vi2,…,vid),i=1,2,…,n

第i個粒子迄今為止搜索到的最優位置稱為個體極值，記為

Pbest=(pi1,pi2,…,pid),i=1,2,…,n

整個粒子群迄今為止搜索到的最優位置為全局極值，記為

gbest=(pg1,pg2,…,pgd)

在找到這兩個最優值時，粒子根據式(3)、式(4)來更新自己的速度和位置

vid=w·vid+c1r1(pid-xid)+c2r2(pgd-xid)

(3)

xid=xid+vid

(4)

式中w為慣性權重，c1，c2為加速度因子，r1，r2為[0,1]中的均勻隨機數[13]。

2.2 粒子群算法的改進

2.2.1 線性遞減權重法

針對基本粒子群算法容易早熟及容易在全局最優解附近產生振蕩現象，本文提出線性遞減權重法，使慣性權重依照從大到小遞減[14]，其變化公式為

(5)

式中wi為慣性權重最大值，wf為慣性權重最小值，t為當前迭代步數，tmax為最大迭代次數。

2.2.2 自然選擇法

基于自然選擇法是借鑒自然選擇的原理，以提高粒子群算法的收斂速度，防止陷入局部最優，在每次迭代中，根據粒子群適應值將粒子排序，用群體中最好的一半粒子替換最差的一半粒子，同時保留每個個體所記憶的歷史最優值。

2.3 路徑優化

由于自身性能限制及使用條件，要求無人機在飛行過程中滿足相應的約束，進行路徑優化[15]。基本路徑優化流程：限制航路長度必須小于預設的最大距離，減小搜索范圍，規劃不能超出搜索空間的范圍，提高粒子群算法收斂速度；當無人機從某一個航路段向下一個航路段飛行時，受到無人機機動能力的限制，給無人機設置最大的拐彎角，規定其航向角不能超過45°，直到找到適合的航路[16]。

2.4 算法流程

1)任務區初始化，建立地形信息，初始化粒子群算法參數，包括群體規模n、每個粒子的位置Xi和速度vi，以及各項參數。

2)計算粒子適應度值，求全局最優粒子gbest，并將Pbest設置為每個粒子的當前位置。

3)根據速度和位置更新公式，更新每個粒子的速度和位置。

4)將每個粒子的適應值與粒子的最好位置比較，如果相近，則將當前值作為粒子最好的位置。比較當前所有的Pbest和gbest，更新gbest。

5)根據適應值對粒子群排序，用群體中最好的一半粒子替換最差的一半粒子，同時保留原來每個個體所記憶的歷史最優值。

6)當算法達到其停止條件，則停止搜索并輸出結果，否則,返回到步驟(3)繼續搜索。

3 仿真驗證

本文在Matlab 7.6環境下對無人機航路規劃進行仿真，驗證所提出的方法的有效性。任務區如圖2,無人機起始位置(0,0)，目標點位置(500,0)，任務區有4處威脅區，如圖中圓形區域所示。令終止迭代次數為1 000，粒子個數為200，粒子維數為10，加速度因子r1=r2=0.8，w=0.8，航程和威脅代價權重系數w1=w2=0.5，如圖2所示,無人機需要從起始點繞過威脅區飛行到目標點。

圖2 無人機航路規劃任務區

圖3和圖4為基本粒子群算法航路規劃圖，如圖所示，仿真結果最后收斂為286.92。圖5和圖6為優化粒子群算法航路規劃圖，根據式(5)更新慣性權重因子,設置w1=0.9，wj=0.4，在每次迭代結束時采用自然選擇更新粒子，按照適應度值對所有粒子進行排序，用群體較好的50 %粒子代替較差的50 %粒子，更新粒子速度和位置，優化算法使得航路規劃路線長度變短，路線趨向于平和，優化后的算法收斂到273.86，可以看出當改變慣性權重和采用自然選擇優化粒子群算法時，收斂速度明顯加快，同時相應地縮小了航路長度。所以改進方法得到了驗證。

圖3 基本粒子群算法航路規劃結果

圖4 基本粒子群算法適應值收斂圖

圖5 優化粒子群算法航路規化結果

圖6 優化粒子群算法適應值收斂圖

4 結束語

本文將優化粒子群算法應用于無人機的航路規劃，利用改變慣性權重，調整慣性因子的方法，提高算法搜索能力，減小搜索空間，通過自然選擇優化粒子群算法，提高算法收斂速度，防止陷入局部最優，避免了早熟收斂問題，縮短了航路長度。實驗表明：基于優化粒子群算法的航路規劃是一種相對有效和相對優越的方法。

[1] 田 偉.無人作戰飛機航路規劃研究[D].西安：西北工業大學,2007.

[2] 穆中林,魯 藝,任 波,等.基于改進A*算法的無人機航路規劃方法研究[J].彈箭與制導學報,2007,27(1):297-300.

[3] 姚永杰,席慶彪,劉慧霞.基于改進遺傳蟻群算法的無人機航路規劃[J].計算機仿真,2011,28(6):44-47.

[4] Fei S U,Hui P,Shen L C.Research on multi-UCAV cooperative route planning based on coevolutionary multi-ant-colony algorith-m[J].Binggong Xuebao/Acta Armamentarii,2009,30(11):1562-1568.

[5] Fu Y,Ding M,Zhou C.Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV[J].IEEE Transactions on Systems Man & Cybernetics Part A:Systems & Humans,2012,42(2):511-526.

[6] 王 波,王燦林,梁國強.基于粒子群尋優的D-S算法[J].傳感器與微系統,2007,26(1):84-86.

[7] 胡中華,趙 敏,姚 敏.無人機三維航路規劃技術研究及發展趨勢[J].計測技術,2009,29(6):6-9.

[8] 翟彥蓉,黃 歡,張 申,等.改進粒子群優化算法在TDOA定位中的應用[J].傳感器與微系統,2013,32(4):145-148.

[9] 張仁鵬,楊金孝,潘佳華,等.基于改進粒子群算法的無人機三維航跡規劃[J].計算機仿真,2014,31(3):65-69.

[10] 李 猛,王道波,柏婷婷,等.采用威脅啟發粒子群算法的無人機航路規劃[J].電光與控制,2011,18(12):1-4.

[11] 胡中華,趙 敏.基于人工蜂群算法的無人機航跡規劃研究[J].傳感器與微系統,2010,29(3):35-38.

[12] Wang G,Li Q,Guo L.Multiple UAVs routes planning based on particle swarm optimization algorithm[C]∥2010 the 2nd International Symposium on Information Engineering and Electronic Commerce(IEEC),IEEE,2010:1-5.

[13] 楊 遵,雷虎民.采用粒子群優化算法規劃無人機偵察航路[J].電光與控制,2007,14(2):4-7.

[14] 孫 湘,周大為,張希望.慣性權重粒子群算法模型收斂性分析及參數選擇[J].計算機工程與設計,2010,31(18):4068-4071.

[15] 馬傳焱.多無人機飛行路徑自動規劃算法研究[J].無線電工程，2015，45(2)：5-7.

[16] 潘 杰.基于改進蟻群算法的移動機器人路徑規劃[J].中國礦業大學學報,2012,34(1):473-475.

UAV route planning based on PSO algorithm*

ZHANG Jian-nan1， LIU Yi-an1， WANG Gang2

(1.College of IOT Engineering,Jiangnan University,Wuxi 214122,China;2.China Ship Research and Development Academe,Beijing 100192,China)

Aiming at unmanned aerial vehicle(UAV)route planning problem of particle swarm optimization(PSO)algorithm,introduce inertia weight and natural selection to optimize PSO,in order to improve convergence speed of basic PSO,prevent fall into part optimum.Algorithm analyze on influence of inertia weight on PSO algorithm,and then adjust inertial factor,improve search ability of algorithm;Using characteristics of convenience and regularity of natural selection update particle of PSO;At the same time through limiting practical course of UAV,narrow search range.Simulation results show that,UAV route planning based on optimized PSO algorithm not only reduces the optimal route,but also improve search speed.

unmanned aerial vehicle(UAV); route planning; particle swarm optimization(PSO)algorithm; inertia weight; natural selection

10.13873/J.1000—9787(2017)03—0058—04

2016—04—25

國家自然科學基金資助項目(61170120)

TP 391

A

1000—9787(2017)03—0058—04

張建南(1991-)，男，碩士研究生，主要研究方向為信息對抗與系統仿真。