基于改進A*算法的無人機動態(tài)航跡規(guī)劃

馬立

（中國電子科技集團公司第二十研究所，西安 710068）

0 引言

無人機在未來戰(zhàn)場上起著舉足輕重的作用，而航路規(guī)劃則是無人機的重中之重，它不僅保證無人機以合理的路線進行規(guī)避并打擊從而提高無人機的作戰(zhàn)效能，而且防止了無人機在協(xié)同條件下的碰撞從而保證無人機的安全性。航路規(guī)劃是實現(xiàn)無人機自主飛行和任務(wù)執(zhí)行的重要手段。在復(fù)雜的戰(zhàn)場環(huán)境下，隨著信息量和規(guī)劃約束條件的增加，對算法的需求也越來越多樣化。目前，對于航路規(guī)劃的研究還集中在單機算法的研究，比如Voronoi圖法[1]，遺傳算法[2]，粒子群算法[3]等，對于單無人機的動態(tài)航路規(guī)劃，研究還不夠深入。實際環(huán)境中，面對突發(fā)威脅，無人機不得不改變原有線路重新規(guī)劃，所以動態(tài)航路規(guī)劃[4]更接近實際戰(zhàn)場。

1 算法的選取

航路規(guī)劃的算法很多，但每種算法都有各自的優(yōu)缺點，如何選取算法也顯得格外重要。遺傳算法[2]不需要確定的模型，算法魯棒性強，但對復(fù)雜的環(huán)境和航路不僅難以進行算法編碼，而且搜索時間長；蟻群算法[5-6]具有正反饋，分布計算等優(yōu)點，但算法初始信息素設(shè)定和信息素更新規(guī)則難以確定。

A*算法[7-9]是人工智能中的一種啟發(fā)式搜索算法，它將實際代價看成兩部分之和，即已經(jīng)付出的代價和將要付出的代價，該代價函數(shù)可表示為式（1）：

其中，n表示當(dāng)前節(jié)點，g(n)和h(n)表示兩個代價函數(shù)，本文表示為距離。設(shè)Spoint表示起點，Epoint表示目標點，則g(n)表示從Spoint到當(dāng)前點n的路徑代價；h(n)表示從n到Epoint的估計代價，稱之為啟發(fā)函數(shù)。f(n)就表示從Spoint出發(fā)，通過節(jié)點n到達Epoint的路徑代價的估計值。A*算法的思想就是每次在多個候選節(jié)點中選擇f值最小的節(jié)點進行擴展。

A*算法一般在搜索過程中構(gòu)造兩個表：open表和close表，其中，open表用于記錄待擴展的節(jié)點,close表用于存放已經(jīng)被擴展的節(jié)點[10]。在每步搜索過程中，首先從 open表中找出代價值最小的節(jié)點，將其加入 close表進行擴展。對擴展后的節(jié)點進行分析，根據(jù)分析結(jié)果對open表和close表進行修改，選擇合適的擴展節(jié)點加入close表[11]。A*算法具有簡單，易實現(xiàn)等優(yōu)點，但算法計算量較大，不能很好的滿足無人機動態(tài)規(guī)劃的需求。

圖1 搜索區(qū)域示意圖

在二維平面內(nèi)，本文創(chuàng)立了一種基于 A*的廣義搜索算法。首先，把圖1規(guī)定為上下左右四個方向；其次，把每一步的搜索區(qū)域限定在上，下，右，右上，右下這五個大方向，如圖1所示，黑色矩形框中，中間六角星代表當(dāng)前節(jié)點，五條線條表示搜索的五個方向，灰色區(qū)域表示整個搜索的大范圍；其次，根據(jù)代價值判斷子節(jié)點是否存在openlist列表中。這樣，該算法不僅加快了規(guī)劃時間，而且可以不斷更新openlist來實時規(guī)劃航路。

2 基于改進A*算法的動態(tài)航路規(guī)劃

2.1 模型的建立

將空間離散化，設(shè)規(guī)劃空間為 40*40的點陣，每一個點即為無人機航路搜索節(jié)點。如圖2所示。

圖2 規(guī)劃空間模型

用黑色圓點表示威脅障礙和戰(zhàn)場邊緣，空白區(qū)域表示可行路徑節(jié)點，圖中加號表示無人機起飛點和目標點。在二維平面內(nèi)，地理地形和地方雷達、威脅半徑等約束可近似等效為一個圓，所以障礙威脅用圓點表示。航路規(guī)劃的目的就是尋找一條從起點到目標點的飛行航路，且航路躲避敵方威脅，可以確保無人機安全高效的完成作戰(zhàn)任務(wù)。那么航路點的集合即為完整的航路，表示為式（2）：

Path表示路徑點集的集合，Si表示每一個路徑的點，xi、yi分別表示每一個路徑點的橫坐標和縱坐標。

2.2 算法改進

啟發(fā)式 A*搜索算法的基本思想是通過設(shè)定合適的啟發(fā)函數(shù)，全面評估各擴展搜索節(jié)點的代價值，通過比較各擴展節(jié)點代價值的大小，選擇最有希望的點加以擴展，直到找到目標節(jié)點為止。在傳統(tǒng)A*算法的節(jié)點擴展中，節(jié)點擴展方式采用8個相鄰的節(jié)點單元（圖3中用“X”表示），這樣不僅讓節(jié)點擴展過于繁瑣，算法的計算量也過大，航路不一定是最優(yōu)，而且節(jié)點重復(fù)計算的比較多，使算法效率偏低。由于本文研究的是在二維平面內(nèi)，考慮的約束模型比較簡化，所以提出一種廣義節(jié)點搜索法來替代以前的搜索方法。廣義搜索法就是根據(jù)目標點和起始點的相對位置，確定目標點和起始點的連線方向，增加約束條件使搜索節(jié)點方向與連線的大方向一致，即朝著目標的方向搜索，這樣不僅減少了節(jié)點搜索量，而且可以高效的找出最優(yōu)路線，如圖2所示，起始點和目標點連線的大方向即為右上方向；或者將搜索方向限定在上，下，右，右上，右下五個方向，如圖1所示。根據(jù)A*算法的機理，搜索的節(jié)點應(yīng)選取代價值最小的作為父節(jié)點。圖 3中圈出的3個點的代價值必然是8個點中代價值較大的（規(guī)定正方向為右），因為它是向后搜索的，在航路的反向，所以去掉這3個點不僅不會影響航路，反而更加優(yōu)化。如圖3、圖4所示，“+”表示當(dāng)前節(jié)點，“X”表示搜索的相鄰節(jié)點，圓點表示棄用的相鄰節(jié)點。圖4（a）為廣義節(jié)點搜索的原始方法，圖4（b）、圖4（c）、圖4（d）則是它演化而來，是它的一部分區(qū)域。

圖3 傳統(tǒng)A*搜索的節(jié)點

圖4 （a） 廣義節(jié)點搜索

圖4 （b） 廣義節(jié)點搜索

圖4 （c） 廣義節(jié)點搜索

圖4 （d） 廣義節(jié)點搜索

傳統(tǒng)A*節(jié)點表示為式（3）：

廣義搜索法表示為式（4）：

式（4）四個公式依次對應(yīng)圖 4中（a）、（b）、（c）、（d）。為當(dāng)前父節(jié)點的坐標，根據(jù)i,j的取值范圍可以確定搜索節(jié)點的位置（點陣的單位距離為1），式（3）和式（4）表示圖3和圖4中的灰色節(jié)點。

從圖中可以清楚的看到，改進后的搜索擴展節(jié)點變少，這樣可以大幅度縮減搜索空間，提高航跡規(guī)劃效率。這在實際戰(zhàn)場中有著重要意義，不僅縮短了作戰(zhàn)時間，而且提高了無人機的壽命。

2.3 代價值重新估價

若要動態(tài)規(guī)劃，那么就要重新估價代價值并進行判斷，設(shè)當(dāng)前點為Y，它的一個子節(jié)點為a，那么a的估價值為

C(Y,a)表示Y到a的距離，即

然后判斷a是否存在于open和close中，如果a在open表中，那么比較當(dāng)前a的g值和以前a的g值，取較小者，更新a的g值；同理，比較close表中的g值，如果a不在這兩個表，則把a添加進open表，把Y添加到close表。流程圖如圖5所示。

圖5 重新估價代價值的流程圖

3 仿真結(jié)果與討論

本文用 MATLAB進行仿真，初始界面已經(jīng)在模型建立中給出，航路起點為（2，2），終點為（38，34）。

（1）建立open和close表，把起點放入open中；

（2）尋找該點周圍可到達的點，忽略已在close中的點；

（3）把該點添加到close表中；

（4）計算該點周圍點的總代價值；

（5）找到代價值最小的點加入close中；

（6）重復(fù)2～5步驟直到目標點加入close中；

（7）將父節(jié)點畫出得到航路。

結(jié)果如下。

圖6 A*算法的仿真

圖7 改進后A*算法的仿真

表1 仿真結(jié)果

從圖6圈中的地方以及圖7的對比中可以看到，圖6雖然成功避開了威脅，但是航路不合理，多繞了路，圖7則非常簡潔又避開了威脅。表1的數(shù)據(jù)可以清楚的反映出改進后的算法優(yōu)于傳統(tǒng)算法。

無人機在規(guī)劃中會遇到突發(fā)威脅[13]，文中將突發(fā)威脅用一段障礙（3個黑星號）表示出來，動態(tài)規(guī)劃如圖8所示。

比較圖7和圖8這兩圖，遇到突發(fā)威脅時，只對突發(fā)威脅附近的路線重新規(guī)劃，其他區(qū)域路徑不變，達到了良好的實時性。航路平滑處理后[12]，得到一條光滑無尖角的曲線，如圖9所示。

圖8 動態(tài)規(guī)劃

圖9 平滑處理后的曲線

改進后的仿真結(jié)果清楚地表明，此無人機航路動態(tài)規(guī)劃模型能夠使無人機的作戰(zhàn)效能達到最佳，生存概率極大，該模型是一種有效的模型，為無人機在復(fù)雜環(huán)境下的航路動態(tài)規(guī)劃提供了一種有效地求解方法。

4 結(jié)論

本文針對無人機二維的動態(tài)航路規(guī)劃問題進行了研究，根據(jù)動態(tài)航路規(guī)劃的特性和文獻建立了更加詳細的航路規(guī)劃空間模型，仿真實驗表明。

（1）廣義A*搜索算法不僅縮短了規(guī)劃的時間而且優(yōu)化了航路，同時在動態(tài)規(guī)劃中，可以避開突發(fā)威脅并快速航路重規(guī)劃，經(jīng)過平滑處理后，規(guī)劃航路沒有尖角。

（2）該算法滿足動態(tài)規(guī)劃的需求，具有較強的工程實用性。

本文建立在二維模型上，有許多約束條件和一些代價問題不能直觀的在圖中顯示，后續(xù)工作是建立精確的規(guī)劃模型并將該算法擴展到三維甚至四維空間。

參考文獻：

[1]劉森琪, 段海濱, 余亞翔. 基于 Voronoi圖和蟻群優(yōu)化算法的無人作戰(zhàn)飛機航路規(guī)劃[J]. 系統(tǒng)仿真學(xué)報，2008(21).

[2]李檸, 萬頃浪, 劉福, 張殿富. 基于改進遺傳算法的無人機協(xié)同航路規(guī)劃[J]. 計算機測量與控制, 2013(08).

[3]劉慧卓, 楊金孝, 王泰然, 王鑫. 改進粒子群算法在三維航路規(guī)劃中的應(yīng)用[J]. 火力與指揮控制, 2013(11).

[4]王緒芝. 不確定環(huán)境下無人機航跡動態(tài)規(guī)劃及仿真研究[D]. 南京航空航天大學(xué), 2013

[5]盧江松. 基于改進蟻群算法的多機協(xié)同突防航跡規(guī)劃方法研究[D]. 國防科學(xué)技術(shù)大學(xué), 2012

[6]王銘謙. 基于蟻群算法的多無人機協(xié)同航路規(guī)劃[J]. 計算機工程, 2001(S1).

[7]李季, 孫秀霞. 基于改進A-Star算法的無人機航跡規(guī)劃算法研究[J]. 兵工學(xué)報, 2008(7).

[8]蒙波, 皮亦鳴, 曹宗杰. 基于改進A*算法的無人機航跡規(guī)劃[J]. 計算機仿真, 2010(9).

[9]席慶彪, 蘇鵬, 劉慧霞. 基于 A*算法的無人機航路規(guī)劃算法[J]. 火力與指揮控制, 2013(11).

[10]杜萍, 楊春. 飛行器航跡規(guī)劃算法綜述[J]. 飛行力學(xué)，2005，23(2):10-14.

[11]George F Luger. 人工智能: 復(fù)雜問題求解的結(jié)構(gòu)和策略(英文版. 第4版)[M]. 北京: 機械工業(yè)出版社, 2003.

[12]馬云紅, 周德云. 基于B樣條曲線的無人機航路規(guī)劃算法[J]. 飛行力學(xué), 2004, 22(2):74-77.

[13]Lam Thu Bui, Zbignew Michalewicz, Eddy Parkinson,and Manuel Blanco Abello. Adaptation in Dynamic Environments: A Case Study in Mission Planning[J].Evolutionary Computation, Vol. 16, No. 2, April 2012

[14]Lanah Evers, Ana Isabel Barros, Herman Monsuur,Albert Wagelmans. Online stochastic UAV mission planning with time windows and time-sensitive targets [J].European Journal of Operational Research，238(2014)348–362