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

何燕

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

關(guān)鍵詞：機(jī)電一體化技術(shù)；無人機(jī)；航跡規(guī)劃；動(dòng)態(tài)加權(quán)；高維空間；復(fù)雜環(huán)境；A*算法

中圖分類號(hào)：TP13 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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

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

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

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

無人機(jī)航跡規(guī)劃是在三維空間中進(jìn)行搜索，設(shè)（x，y，z）是任務(wù)空間中的擴(kuò)展頂點(diǎn)n，其中xn，yn分別為縱向坐標(biāo)和橫向坐標(biāo)，zn為該點(diǎn)的地形高度，該搜索空間可表示為Ωn={（xn，yn，zn）|0≤xn≤max Xn，0≤yn≤max Yn，0≤zn≤max Zn}。（1）在三維空間中，如圖1所示對(duì)每個(gè)步驟都需要搜索24個(gè)點(diǎn)（整個(gè)空間被劃分為一個(gè)小網(wǎng)格，只能在這些節(jié)點(diǎn)上選擇飛行節(jié)點(diǎn)）。 因?yàn)椴煌愋偷耐{會(huì)不同程度地影響無人機(jī)的飛行，所以約束條件比較復(fù)雜。

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

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

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

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

2）無人機(jī)航跡段長(zhǎng)度最小化約束

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

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

3 仿真分析

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)/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] 李永偉，王紅飛.六旋翼植保無人機(jī)模糊自適應(yīng)PID控制[J].河北科技大學(xué)學(xué)報(bào)，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]吳學(xué)禮，賈云聰，張建華，等.一種改進(jìn)蟻群算法的無人機(jī)避險(xiǎn)方法仿真研究[J].河北科技大學(xué)學(xué)報(bào)，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]甄然，甄士博，吳學(xué)禮.一種基于人工勢(shì)場(chǎng)的無人機(jī)航跡規(guī)劃算法[J].河北科技大學(xué)學(xué)報(bào)，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]李季，孫秀霞.基于改進(jìn)A-Star算法的無人機(jī)航跡規(guī)劃算法研究[J].兵工學(xué)報(bào)，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 算法的無人機(jī)任務(wù)規(guī)劃方法研究[D].南京：南京航空航天大學(xué)，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.