基于改進粒子群算法的無人機航跡規劃

杜云　劉冰　邵士凱　彭瑜

摘 要：針對當前基本粒子群算法無人機航跡規劃在后期收斂速度比較慢、效率不高、易陷入局部最優等問題，提出一種改進粒子群算法。首先，在迭代前期和后期分段設置慣性權值的調整，實現粒子慣性和尋優行為的平衡;其次，設置一個定值與相鄰2次適應度函數最優值比較策略，防止陷入局部最優;最后，引入遺傳算法的交叉、變異機制，得出更優的結果。并通過仿真驗證了改進粒子群算法在三維空間航跡規劃的有效性和可行性。結果表明，與其他航跡規劃算法相比，新算法具有路徑長度更短、耗時更少、路徑更平滑等優點，加快了收斂速度，提高了航跡規劃效率和穩定性。因此，改進算法的航跡規劃可得到滿足約束關系的最優航跡，對實現自主飛行有重要的參考價值。

關鍵詞：計算機仿真;無人機;航跡規劃;粒子群算法;慣性權值;遺傳算法

中圖分類號：TP29?? 文獻標志碼：A

Abstract：Aiming at the problems of slow convergence， low efficiency and easy to fall into local optimum for the UAV flight path planning of basic particle swarm optimization， an improved method is provided. Firstly， the adjustment of the inertia weight is set in the early and late stages of the iteration to achieve the balance between particle inertia and optimization behavior. Secondly， a comparison strategy is set between the fixed value and the adjacent two fitness function optimal values to prevent falling into local optimum. Finally， the crossover and mutation mechanism of the genetic algorithm is introduced to get better results. The effectiveness and feasibility of the improved particle swarm optimization algorithm in 3D space track planning are verified by simulation results. Compared with other track planning algorithms， it has the advantages of shorter path length， less time-consuming， smoother path， etc.， which accelerates the convergence speed and improves the overall efficiency and stability. The flight path planning based on the improved algorithm can obtain the optimal flight path satisfying the constraint relation， which has important reference value for realizing autonomous flight.

Keywords：computer simulation; UAV; track planning; particle swarm optimization; inertia weight; genetic algorithm

現今社會科技進步日新月異，無人機開始大量投入使用。對無人機的任務航跡進行有效并且合理的規劃，需要綜合考慮無人機本身的性能、最遠飛行距離以及油耗、地形和氣象威脅等等。在這些限制條件下，需要找出飛行地域范圍內起始點與目標點之間的最優航跡，從而高效地完成指定的作戰任務并保證自身安全。對無人機任務航跡進行規劃的主旨是進行多約束的目標優化，以找出無人機最優或次優路線。在無人機航跡規劃過程中，面對的威脅有很大的不可測性，地形環境復雜多變，且要面對未知的天氣因素。因此航跡規劃的條件多且模糊性較大[1]，不僅要考慮這些因素自身特有的控制方式，還要考慮各因素之間存在的強耦合關系，這就大大增加了航跡規劃的難度。國內外學者們提出了許多關于航跡規劃的算法，如神經網絡[2]，退火算法[3]、遺傳算法[4]、蟻群算法[5]等。但是由于無人機航跡規劃空間復雜，約束條件多，模糊性較大，導致傳統航跡搜索算法尋優能力不足、計算量大，航跡規劃在最優性以及實時性兩方面亟待提高。粒子群算法優點明顯，能夠在處理一些優化問題時取得相對更優結果，但存在后期收斂速度過慢，容易陷入局部最優的情況[6]。本文對粒子群算法進行改進，并結合改進后的算法對無人機航跡進行規劃。

圖8為遺傳算法迭代收斂曲線，可看出遺傳算法迭代初期和后期收斂速度較慢，中期收斂速度雖然加快，但迭代結束后沒有達到收斂，最終代價較高。圖9為標準粒子群算法迭代收斂曲線，可看出標準粒子群算法前期收斂速度較快，但后期收斂速度明顯變慢，最終代價為132，表明規劃結果可能陷入了局部最優。圖10為改進粒子群算法迭代收斂曲線，從圖中明顯看出收斂速度優于遺傳算法和標準粒子群算法，并在第80次迭代達到最優，代價為128，表明設計的改進算法加快了收斂速度，提升了解的最優性。

4 結 語

針對現有無人機航跡規劃算法存在過早收斂和易陷入局部最優的缺點，提出了一種基于改進粒子群算法的無人機航跡規劃方法。通過調整粒子群算法中的慣性權重，控制參數，并引入遺傳算法交叉、變異思想，提高搜索無人機航跡最優性，大大加強了算法穩定性。無人機航跡規劃仿真結果表明，改進粒子群算法收斂到最優解的有效性高，且相比遺傳算法和標準粒子群算法得出的路徑更加平緩，路徑更短。利用設計的改進算法雖然可得到最優航跡，但在實時性方面仍有很大的提升空間，在下一步工作中，將把無人機在線航跡規劃作為研究重點，并將通過無人機實際飛行對規劃方案進行驗證。

參考文獻/References：

[1] 簡康. 無人機航跡規劃算法研究[D]. 西安：西安電子科技大學， 2014.

IAN Kang. A Study of UAV Path Planning Algorithms[D]. Xi’an： Xidian University，2014.

[2] 徐卓. 基于神經網絡算法的無人機航跡規劃研究[D]. 石家莊：河北科技大學，2016.

XU Zhuo. Research on UAV Path Planning Based on Neural Networks[D]. Shijiazhuang：ebei University of Science and Technology，2016.

[3] 王強， 張安， 吳忠杰. 改進人工勢場法與模擬退火算法的無人機航路規劃. 火力與指揮控制， 2014，39（8）：70-73.

WANG Qiang， ZANG An， WU Zhongjie.UCAV path planning based on improved artificial potential field and simulated annealing. Fire Control & Command Control， 2014，39（8）：70-73.

[4] 張鑫源， 胡曉敏， 林盈. 遺傳算法和粒子群優化算法的性能對比分析. 計算機科學與探索， 2014， 8（1）：90-102.

ZANG Xinyuan，U Xiaomin，LIN Ying. Comparisons of genetic algorithm and particle swarm optimization. ournal of Frontiers of Computer Science and Technology， 2014， 8（1）：90-102.

[5] 吳學禮， 賈云聰， 張建華，等. 一種改進蟻群算法的無人機避險方法仿真研究. 河北科技大學學報， 2018，39（2）：166-175.

WU Xueli， IA Yuncong， ZANG ianhua， et al. Simulation study of UAV conflict resolution based on an improved ant colony algorithm. ournal of ebei University of Science and Technology， 2018，39（2）：166-175.

[6] LI ianping. Improved quantum-behaved particle swarm optimization. Open ournal of Applied Sciences，2015 （5）：240-250.

[7] 瞿博陽，劉丁明，喬百豪，等.粒子群算法及其改進研究.自動化應用，2016（11）：49-51.

[8] 朱收濤， 曹林平， 翁興偉，等.采用改進粒子群算法的無人機協同航跡規劃. 電光與控制， 2012，19（12）：29-33.

ZU Shoutao，CAO Linping，WENG Xingwei， et al. Cooperative path planning for UCAVs based on improved PSO algorithm. Electronics Optics & Control， 2012，19（12）：29-33.

[9] 傅陽光. 粒子群優化算法的改進及其在航跡規劃中的應用研究[D]. 武漢：華中科技大學， 2011.

FU Yangguang. Research on Modified Particle Swarm Optimization and Their Application in Route Planning for UAV[D]. Wuhan：uazhong University of Science and Technology，2011.

[10]陳攀峰， 劉文軍， 王為. 基于粒子群算法的無人機航跡規劃. 電子設計工程， 2013， 21（22）：36-39.

CEN Panfeng，LIU Wenjun，WANG Wei. Route planning of UAV based on particle swarm optimization （PSO） algorithm . Electronic Design Engineering， 2013， 21（22）：36-39.

[11]KENNEDY ， EBERART R C. Particle swarm optimization[C]//IEEE International Conlerence on Neural Networks.[S.l.]：[s.n.]，1995： 1942-1948.

[12]高明君， 張國義， 高家一，等.基于粒子群優化的網絡動態可靠性分析. 計算機測量與控制， 2015， 23（1）：307-309.

GAO Mingjun， ZANG Guoyi，GAO iayi， et al. Time-variant reliability analysis for network based on PSO. Computer Measurement & Control， 2015， 23（1）：307-309.

[13]方群， 徐青. 基于改進粒子群算法的無人機三維航跡規劃. 西北工業大學學報， 2017， 35（1）：66-73.

FANG Qun，XU Qing. 3D route planning for UAV based on improved PSO algorithm. ournal of Northwestern Polytechnical University， 2017， 35（1）：66-73.

[14]熊軍華， 謝飛. 基于混沌理論和雜交策略改進的粒子群優化算法. 信息技術與信息化， 2017（10）：55-57.

[15]周璐， 李軍華. 一種滿足方向約束的動態航跡規劃方法. 計算機應用研究， 2018， 35（7）：1982-1985.

ZOU Lu， LI unhua. Dynamic route planning method based on directional constraints. Application Research of Computers， 2018， 35（7）： 1982-1985.