基于動態加權A^*算法的無人機航跡規劃

何燕

摘 要：隨著無人機航跡規劃高維空間的擴展，無人機的飛行環境變得異常復雜，其外部威脅不再是簡單的二維靜態威脅，傳統的蟻群算法和人工勢場算法已經不能滿足實時性和高復雜環境的要求。為解決上述問題，提出新的基于動態加權A*算法的無人機航跡規劃。首先對無人機的飛行環境進行建模，通過研究航跡規劃的轉彎半徑、航跡段長度和最大航程限制等約束條件，用于保證無人機的安全飛行，從而降低墜機率和威脅概率；其次，通過研究無人機的航跡和外部威脅參數，設計出新的航行方式，降低航行危險和減少損失；然后，通過擴展頂點勢能定位和網格圖整體變化的動態權重，獲得動態環境下的代價函數，增加避障搜索速度、精度和加深回避程度。最后，通過仿真結果表明，在同一應用環境下，所提算法與蟻群算法和人工勢場算法相比，航跡路徑最優、威脅代價最小和算法執行的時間最短。綜上，基于動態加權A*算法很好地應用于無人機航跡規劃，降低了無人機航跡代價，縮短了算法完成時間，提高了復雜環境下無人機航跡規劃的搜索速度和精度。

關鍵詞：機電一體化技術；無人機；航跡規劃；動態加權；高維空間；復雜環境；A*算法

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

文章編號：1008-1542（2018）04-0349-07doi：10.7535/hbkd.2018yx04009

Abstract： With the expansion of high dimensional space in UAV trajectory planning， the flying environment of UAV is very complex， and the external threat of UAV is no longer a simple two-dimensional static threat. The traditional ant colony algorithm and artificial potential field algorithm cannot meet the requirements of real-time and high complex environment. To solve the above problems， a new dynamic programming algorithm based on dynamic weighted A* algorithm is proposed. Firstly， the flight environment of UAV is modeled. By studying the constraints such as the turning radius， the length of track section and the limit of the maximum range， the safe flight of UAV is ensured， thus reducing the crash rate and the threat probability. Secondly， a new navigation mode is designed by studying the track and external threat parameters of the UAV， which can reduce the danger of navigation and reduce the loss. Then， the potential energy of the vertex can be expanded. The dynamic weight of the overall change of location and grid graph is obtained， and the cost function in dynamic environment is obtained， which increases the speed， accuracy and evasion degree of obstacle avoidance search. Finally， the simulation results show that under the same application environment， the proposed algorithm has the best path， the least threat cost and the shortest execution time compared with the ant colony algorithm and artificial potential field algorithm. To sum up， the dynamic weighted A* algorithm can be well applied to UAV trajectory planning， reducing the cost of UAV track， shortening the completion time of the algorithm and improving the search speed and precision of unmanned aerial vehicle trajectory planning in complex environment.

Keywords：mechatronics technology； UAV； route planning； dynamic weighting； high dimensional space； complex environment； A* algorithm

近年來無人機（UAV）技術得到了迅猛發展，無人機越來越多地應用于測繪、監視、周邊巡邏或噴灑農藥[1-5]，特別是無人機具有比地面或水上飛行器更寬的視野和更靈活的機動性，更適用于目標搜索應用所需的覆蓋任務。假設一個人在野外迷路或一艘船沉入海中，隨著時間的推移，生存的可能性會迅速下降。在這個時間敏感的情況下，無人機需要有效地檢測感興趣的區域，以便盡快找到目標。因此，覆蓋搜索任務可以模擬為規劃可行路線的優化問題，沿著該優化問題，傳感器覆蓋重要區域，以便在有限的飛行時間內使累積檢測概率最大化[6]。與傳統的從起點到目的地產生避障路線的路線規劃任務不同[7-8]，由于需要覆蓋可能重要的區域，這項任務更為復雜。路徑規劃是無人機任務管理系統的關鍵技術之一，也是無人機自主控制改進的重要環節[9]，在實際應用中，由于飛行環境的復雜性，無人機本身和環境存在很多限制。因此，建立高效的無人機路徑規劃算法已成為無人機飛行路徑規劃的關鍵。目前存在多種無人機路徑規劃算法[10]。大多數研究都集中在任務分配策略上[11-14]，主要關注最小化旅行距離或完成任務的時間。Voronoi圖是解決路徑規劃問題的有效方法，但是如果不結合其他搜索算法[15]，很難找到最優解。蟻群算法[16-17]、遺傳算法[18]以及粒子群算法[19]在二維路徑規劃中表現良好，并且有一些改進的策略。但是，隨著搜索空間的擴展，這些算法已不能滿足實時要求。人工勢場[20-21]在無人機領域已經有很多的討論，盡管研究者們在改善目標不可達性和軌道震蕩現象等方面付出了很多努力，但解決這些問題的有效方法還有待開發。A*算法[22]是一種啟發式算法，廣泛應用于各種搜索問題，如機器人路徑規劃，計算機游戲AI和無人機障礙物無碰撞場等。

河北科技大學學報2018年第4期何 燕：基于動態加權A*算法的無人機航跡規劃本文提出了一種改進的動態加權A*算法用于復雜環境下的無人機路徑規劃。首先給出航跡規劃的約束條件，保證了無人機的安全飛行，降低墜機率和威脅概率；其次通過設計無人機的航跡代價，對外部威脅進行全面分析，設計出較好的航行方式，降低航行危險，減少損失；再者，通過擴展頂點勢能定位，獲得動態環境下的代價函數，根據網格圖整體變化的動態權重，在接近障礙物時增加搜索速度，加深回避程度，在接近目標時提高搜索精度。

1 無人機飛行環境建模

無人機航跡規劃是在三維空間中進行搜索，設（x，y，z）是任務空間中的擴展頂點n，其中xn，yn分別為縱向坐標和橫向坐標，zn為該點的地形高度，該搜索空間可表示為Ωn={（xn，yn，zn）|0≤xn≤max Xn，0≤yn≤max Yn，0≤zn≤max Zn}。（1）在三維空間中，如圖1所示對每個步驟都需要搜索24個點（整個空間被劃分為一個小網格，只能在這些節點上選擇飛行節點）。 因為不同類型的威脅會不同程度地影響無人機的飛行，所以約束條件比較復雜。

三維搜索空間中的問題更加復雜，因此需要縮小搜索空間的范圍。在實際情況下，無人機的飛行路徑必須滿足最小轉彎半徑約束，最小航跡段長度、最大航程限制、最低飛行高度限制、最大爬升/俯沖角的要求等限制條件。由約束條件得到的當前節點的搜索區域如圖2所示，在水平方向上，對稱區域的最大偏航角度約束了選擇，而在垂直方向最大上升角度中起到相同的作用。

1.1 無人機路徑規劃的約束

1）轉彎半徑最小化約束

受無人機硬件設施的性能限制，機身的轉彎半徑受到一定約束。在三維網格化搜索環境中，無人機必須在有限的方位上選取候選頂點，根據無人機所在頂點的方位信息，選出合適的待選頂點如圖3所示。圖3中mi為當前所在頂點，mi-1為進入該擴展節點的前一頂點， mj為待選頂點。

2）無人機航跡段長度最小化約束

2 基于動態加權A*算法的無人機航跡規劃

由于A*算法不僅可以用來尋找最短路徑，還可以使用啟發式引導自己，將Dijkstra算法使用的信息（偏向接近起始的頂點）和Greedy Best-First-Search使用的信息（偏向接近目標的頂點）進行有效組合。A*算法通過執行最佳優先搜索找到從起始頂點S到目標頂點G的圖中的路徑。從S開始，A*算法迭代地擴展頂點n，這使得成本函數f（n）=g（n）+h（n）最低。g（n）表示從起始S到任意頂點n的路徑的確切成本，即從S到n的最佳發現路徑的代價；h（n）表示從擴展頂點n到目標G的啟發式估計成本，即估計從狀態n到G的代價的啟發函數。每次通過主循環時，它檢查具有最低啟發函數的擴展頂點n：

3 仿真分析

在仿真部分，可以建立一個飛行環境，假設無人機可以在北緯25°到北緯36°，東經101°到東經115°，高度為0～7 000 m。比較了改進的加權A*算法與蟻群算法和人工勢場算法在無人機飛行1 000 m以上的情況。在本文中，假設無人機以不同類型的威脅從起點飛向目的地，并且必須穿過每個任務點。改進的A*算法仿真結果如圖6所示，黑色圓圈代表威脅源，黑色圓點為無人機必須通過的任務點，曲線為無人機的航行軌跡。

在同一環境中使用蟻群算法和人工勢場算法，仿真航跡分別如圖7和圖8所示。

為了比較這3種算法，使用3個指標來描述其質量，即航跡長度，航跡代價和算法完成時間。所有的模擬都在同一個平臺上執行，3種算法航跡規劃性能比較如表1所示。

從結果中可以看到改進的A*算法優于蟻群算法和人工勢場算法。首先，改進的A*算法在航跡代價和航跡長度上具有很大的優勢。盡管人工勢場算法的完成時間比A*算法快一點兒，但與蟻群算法相比，A*算法的速度也很快了，這意味著它的實時重新計算能力是可以接受的。

4 結 論

針對無人機高維復雜飛行環境下，高維地形數學建模、任務目標搜索路徑規劃及航跡代價設計等問題，對A*算法、人工勢場算法和蟻群算法進行了深入研究，提出基于動態加權A*算法的無人機航跡規劃方案，以解決無人機路徑規劃問題。首先對基本的A*算法進行了一系列改進，使其更適應復雜的真實環境，通過無人機路徑規劃的約束保證無人機安全飛行，達到很好的避障效果；根據無人機所在的任務區域，綜合考慮影響航行軌跡性能的各種因素，包括威脅代價、高度代價和航程代價的綜合航跡代價指標，設計了精確的實際代價函數；將歸一化的全局勢場作為啟發函數的權重系數，提高了搜索精度和實時性。最后的實驗結果驗證了基于動態加權的A*算法在解決無人機路徑規劃問題中的可行性和有效性，降低了無人機的航行成本，減少了算法執行時間，提高了復雜環境下無人機航跡規劃的搜索速度和精度。

參考文獻/References：

[1] BEARD R W， MCLAIN T W，NELSON D B， et al. Decentralized cooperative aerial surveillance using fixed-wing miniature UAVs[J]. IEEE， 2006，94（7）： 1306-1324.

[2] KALYANAM K， CHANDLER P， PACHTER M， et al. Optimization of perimeter patrol operations using unmanned aerial vehicles[J]. Journal of Guidance Control & Dynamics， 2015，35（2）：434-441.

[3] OH H， KIM S， SHIN H S， et al. Coordinated standoff tracking of moving target groups using multiple UAVs[J]. IEEE Trans， 2015， 51（2） ：1501-1514.

[4] WANG Y， WANG S， TAN M . Path generation of autonomous approach to a moving ship for unmanned vehicles[J]. IEEE Trans， 2015， 62（9）：5619-5629.

[5] 李永偉，王紅飛.六旋翼植保無人機模糊自適應PID控制[J].河北科技大學學報，2017，38（1）：59-65.

LI Yongwei， WANG Hongfei. Fuzzy-adaptive PID control of six-rotor wing plant protection UAV[J]. Journal of Hebei University of Science and Technology， 2017， 38（1）：59-65.

[6] BOURGAULT F， FURUKAWA T， DURRANT-WHYTE H F. Coordinated decentralized search for a lost target in a Bayesian world[C]//Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas： IEEE， 2003： 48-53.

[7] ROBERGE V， TARBOUCHI M， LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE ， 2013， 9（1）：132-141.

[8] YAO P， WANG H L， SU Z K. UAV feasible path planning based on disturbed fluid and trajectory pro-pagation[J].Chinese Journal of Aer-onautics，2015，28（4）： 1163-1177.

[9] CHANDLER P R， PACHTER M. Research issues in autonomous control of tactical UAVs[J]. IEEE， American Control Conference， 1998，1：394-398.

[10]BORTOFF S A. Path planning for UAVs[J]. IEEE，American Control Conference， 2000，1（6）： 364-368.

[11]BERTUCCELLI L F， HOW J P. Search for dynamic targets with uncertain probability maps[J]. IEEE，2006， 6：737-742.

[12]ZHU Hongguo，ZHENG Changwen，HU Xiaohu， et al. Path planner for unmanned aerial vehicles based on modified PSO algorithm[C]// International Conference on Information and Automation.Changsha：[s.n.]， 2008：541-544.

[13]RATHINAM S， SENGUPTA R. Lower and upper bounds for a multiple depot UAV routing problem[C]// Proceedings of the 45th IEEE Conference on Decision and Control.San Diego：IEEE，2006：5287-5292.

[14]SUJIT P B， BEARD R. Multiple UAV path planning using anytime algorithms[C]//2009 American Control Conference.St. Louis：IEEE， 2009：2978-2983.

[15]PEHLIVANOGLU Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J]. Aerospace Science and Technology， 2012， 16（1）： 47-55.

[16]DORIGO M， MANIEZZO V， COLORNI A. Ant system： Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， 1996，26（1）： 29-41.

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

WU Xueli， JIA Yuncong， ZHANG Jianhua， et al. Simulation research on hedging method of UAV based on improved ant colony algorithm [J]. Journal of Hebei University of Science and Technology， 2018， 39（2）：166-175.

[18]NIKOLOS I K， VALAVANIS K P， TSOURVELOUDIS N C， et al. Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE， 2003， 33（6）： 898-912.

[19]ALEJO D， COBANO J A， HEREDIA G， et al. Particle swarm optimization for collision-free 4d trajectory planning in unmanned aerial vehicles[C]//2013 International Conference on Unmanned Aircraft Systems.Seville：IEEE，2013： 298-307.

[20]LIN C L， LEE C S， HUANG C H， et al. Unmanned aerial vehicles evolutional flight route planner using the potential field approach[J]. Journal of Aerospace Computing Information and Communication， 1971，9（9）：92-109.

[21]甄然，甄士博，吳學禮.一種基于人工勢場的無人機航跡規劃算法[J].河北科技大學學報，2017，38（3）：278-284.

ZHEN Ran， ZHEN Shibo， WU Xueli. An improved route planning algorithm for unmanned aerial vehicle based on artificial potential field[J]. Journal of Hebei University of Science and Technology， 2017， 38（3）： 278-284.

[22]李季，孫秀霞.基于改進A-Star算法的無人機航跡規劃算法研究[J].兵工學報，2008，29（7）：788-792.

LI Ji， SUN Xiuxia. A route planning's method for unmanned aerial vehicles based on improved A-Star algorithm [J]. Acta Armamentarii，2008，29（7）：788-792.

[23]李猛.基于智能優化與RRT 算法的無人機任務規劃方法研究[D].南京：南京航空航天大學，2012.

LI Meng. Research on Mission Planning of UAV Based on Intelligent Optimization and RRT Algorithm[D]. Nanjing：Nanjing University of Aeronautics and Astronautics，2012.