何燕

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

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

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

1 無人機飛行環(huán)境建模

無人機航跡規(guī)劃是在三維空間中進行搜索，設(shè)（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個點（整個空間被劃分為一個小網(wǎng)格，只能在這些節(jié)點上選擇飛行節(jié)點）。 因為不同類型的威脅會不同程度地影響無人機的飛行，所以約束條件比較復雜。

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

1.1 無人機路徑規(guī)劃的約束

1）轉(zhuǎn)彎半徑最小化約束

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

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

2 基于動態(tài)加權(quán)A*算法的無人機航跡規(guī)劃

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

3 仿真分析

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

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

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

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

4 結(jié) 論

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

參考文獻/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]甄然，甄士博，吳學禮.一種基于人工勢場的無人機航跡規(guī)劃算法[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算法的無人機航跡規(guī)劃算法研究[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]李猛.基于智能優(yōu)化與RRT 算法的無人機任務規(guī)劃方法研究[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.