魏瑞軒,許卓凡,王樹磊,呂明海

(空軍工程大學航空航天工程學院,陜西西安710038)

基于Laguerre圖的自優(yōu)化A-Star無人機航路規(guī)劃算法

魏瑞軒,許卓凡,王樹磊,呂明海

(空軍工程大學航空航天工程學院,陜西西安710038)

為了降低無人機航路規(guī)劃的運算量,減少規(guī)劃時間,確保算法對于任意形狀威脅區(qū)域和地形的適應性以及所規(guī)劃航路的準確性,提出了一種新穎的LA-Star算法用于無人機航路規(guī)劃。首先把威脅區(qū)域和禁飛區(qū)域簡化為圓形,利用Laguerre圖算法進行航路預規(guī)劃,在此基礎上簡化二次規(guī)劃空間的范圍,之后恢復威脅區(qū)域和禁飛區(qū)域的真實形狀,在簡化后的規(guī)劃空間內(nèi)使用改進A-Star算法實施二次航路規(guī)劃,最后對生成的航路進行自優(yōu)化處理。仿真結(jié)果證明了LA-Star算法滿足航路規(guī)劃的實時性和準確性要求。

無人機;航路規(guī)劃;LA-Star算法;Laguerre圖;A-Star算法

0 引 言

隨著現(xiàn)代科學技術(shù)的進步和發(fā)展,未來戰(zhàn)場上以多架無人機(unmanned aerial vehicle,UAV)協(xié)同的方式執(zhí)行各類任務將成為一種重要的作戰(zhàn)方式[1]。航路規(guī)劃作為無人機任務規(guī)劃的重要組成部分之一,主要是依據(jù)地形和敵方火力威脅信息,在一定約束條件下,尋找從起點到目標點的可行航路[2]。在航路規(guī)劃問題中,常用的規(guī)劃算法包括AStar算法[3]、Dijkstra算法[4]、Voronoi圖算法[5]、Laguerre圖算法[6]、遺傳算法[7]、粒子群優(yōu)化算法[8]、蟻群算法[9]等。

基于圖形(Graph-based)的航路規(guī)劃算法由于空間復雜度和時間復雜度比較小、結(jié)構(gòu)簡單等特點受到了廣泛的關注[10-11],Laguerre圖就是其中的典型代表。文獻[6]針對目前Laguerre圖生成算法不易實現(xiàn)的問題,提出了一種基于Delaunay圖的Laguerre圖構(gòu)造算法,其時間復雜度為線性對數(shù)階,運行時間能夠滿足在線規(guī)劃的要求。但是由于Laguerre圖方便解決關于圓的幾何問題[12],因此使用Laguerre圖進行無人機航路規(guī)劃就必須把威脅區(qū)域(為了方便,本文中威脅區(qū)域和禁飛區(qū)域統(tǒng)一稱為威脅區(qū)域)簡化為二維平面上的一組圓,圓心坐標和圓的半徑分別代表威脅區(qū)域的位置以及威脅半徑,而對于大多數(shù)威脅區(qū)域不是圓形的情況Laguerre圖就無法進行準確航路規(guī)劃。A-Star算法是一種啟發(fā)式的圖搜索算法[13],可以在威脅區(qū)域是任意形狀的情況下進行航路規(guī)劃,但是由于算法較為復雜,時間復雜度較高,不易滿足實時規(guī)劃的要求[14]。

為了解決算法實時性和準確性之間的矛盾,本文首先對A-Star算法進行了改進,提出了自優(yōu)化A-Star算法,然后在此基礎上提出了基于Laguerre圖的自優(yōu)化A-Star算法,即LA-Star算法。保證了航路規(guī)劃的實時性以及對任意形狀威脅區(qū)域的適用性。

1 自優(yōu)化A-Star算法基本原理

1.1 A-Star算法

A-Star算法是一種啟發(fā)式的圖搜索算法,能夠在具有多約束條件以及任意形狀的威脅環(huán)境下進行航路規(guī)劃[13]。它的關鍵思想是選擇合適的啟發(fā)函數(shù),對于各個擴展節(jié)點的代價值進行計算和評估,從而選擇代價值最優(yōu)的結(jié)點加以擴展,直到找到目標節(jié)點為止。

在A-Star算法需要建立兩個列表:open表和close表, open表用于存放經(jīng)過推算但是還沒有擴展過的節(jié)點,close表用于存放已經(jīng)被擴展過的節(jié)點。對于被擴展的節(jié)點需要進行代價評估,這需要構(gòu)造代價函數(shù),其一般形式如下:

式中,g(n)是指無人機從起始節(jié)點Start運動到節(jié)點n已經(jīng)消耗的代價;h(n)是指從節(jié)點n運用到目標節(jié)點Target估計需要消耗的代價;f(n)作為決定航路點拓展問題的關鍵信息,其形式一般根據(jù)實際問題的特點和需要決定[15]。

本文中g(shù)(n)用從初始節(jié)點Start到節(jié)點n所規(guī)劃航路的長度表示,h(n)用節(jié)點n到目標節(jié)點Target的歐氏距離表示。

1.2 威脅區(qū)域的規(guī)避

判斷A-Star算法拓展節(jié)點是否在威脅區(qū)域范圍以內(nèi),本文采用“射線判斷法”,如圖1所示,判斷點P(xn,yn)是否在多邊形威脅區(qū)域以內(nèi),則以P點為起點做如下射線:

判斷該射線與威脅區(qū)域邊界交點的個數(shù),若交點數(shù)為奇數(shù),則判斷Pn點在威脅區(qū)域內(nèi),若交點數(shù)為偶數(shù),則判斷Pn點在威脅區(qū)域外。在圖1中,點P2引出的射線與威脅區(qū)域邊界存在1個交點,因此在威脅區(qū)域內(nèi),而點P1、P3、P4分別存在0、0、2個交點,因此在威脅區(qū)域以外。

圖1 判斷拓展節(jié)點所在區(qū)域

在搜索拓展節(jié)點的時候,通過判斷節(jié)點是否在威脅區(qū)域內(nèi)來約束節(jié)點的拓展,不拓展在威脅區(qū)域內(nèi)的節(jié)點,也就是在航路規(guī)劃空間內(nèi)將威脅區(qū)域排除,從而進一步縮小了搜索空間,提高了搜索效率。

在規(guī)劃空間內(nèi)排除了威脅區(qū)域后,拓展新節(jié)點要分兩種情況討論,假設節(jié)點Pn-2和Pn-1已經(jīng)被拓展,下一步需要拓展節(jié)點Pn,如圖2所示,那么只需要判斷Pn-1與Pn的連線與威脅區(qū)域的邊界是否存在交點,圖中Pn-1P'n的連線與威脅區(qū)域存在兩個交點,因此P'n要排除,而Pn-1Pn的連線與威脅區(qū)域不存在交點,因此Pn是合適的拓展節(jié)點。

圖2 節(jié)點拓展時的兩種情況

1.3 進入角約束

由于任務需要,無人機在到達目標點之后需要按照一定的航向角接近目標[16],因此在目標點周圍設置了虛擬威脅區(qū)域,這樣一方面控制了無人機的進入角度,另一方面壓縮了算法的搜索空間,從而提高了效率,虛擬威脅區(qū)域的設置如圖3所示。

圖3 設置虛擬威脅區(qū)域

1.4 航路點自優(yōu)化

A-Star算法所規(guī)劃的航路存在航向變化頻繁且航路點過于密集的特征,不適合直接應用于無人機飛行[17]。因此對所規(guī)劃的航路點進行優(yōu)化是十分有必要的。這里提出一種在已規(guī)劃航路基礎上刪除、插入航路點的優(yōu)化算法。

1.4.1 航路點的刪除

定義2 Ni可優(yōu)化:如圖4所示,依次連接NiNi+kNi+k+1(k=1,2,3…),若連線互相沒有交點,則稱可連,否則稱不可連。若k＜K+1時NiNi+kNi+k+1可連,k=K+1時NiNi+kNi+k+1不可連,則可以連續(xù)刪除航路點Ni+k(k= 1,2,…,K),同時將NK后續(xù)航路點的下標減去K。航路點的刪除優(yōu)化從起點到終點依次順序進行。

圖4 刪除多余的航路點

1.4.2 航路點的插入

經(jīng)過航路點刪除后,仍然可以實施進一步優(yōu)化,在航路點之間插入一些新的節(jié)點,再根據(jù)定義2進行反向順序點優(yōu)化。

航路點插入的流程如下,在生成航路上的兩個連續(xù)航路點連線上等間距地插入若干個新航路點。如圖5所示,初始生成的航路為ABCD,在連續(xù)航路點之間插入新的航路點后再進行反向順序點優(yōu)化,得到更優(yōu)的航路AA4C1D。

圖5 插入航路點優(yōu)化航路

2 LA-Star算法原理及實現(xiàn)

2.1 Laguerre圖航路規(guī)劃基本原理

Laguerre圖是Voronoi圖的衍生圖,非常適合用于解決涉及圓的幾何問題[12]。引入Laguerre圖用于UAV的航路規(guī)劃,其生成元為平面上的一組圓,圓心和半徑分別表示威脅源的位置及覆蓋范圍等信息,若兩個威脅區(qū)域不相交,Laguerre圖總能夠找到一條合適的路徑避開威脅源的攻擊范圍[6]。

使用Laguerre圖進行無人機航路規(guī)劃首先需要假設每個威脅區(qū)域為圓形,其次在任務空間內(nèi)根據(jù)各個威脅區(qū)域的位置和半徑畫出Laguerre圖,最后便可以通過對Laguerre圖各個路徑代價的分析得到合適的無人機航路。

2.2 Laguerre圖算法優(yōu)化

為了優(yōu)化生成的路徑,本文在使用Laguerre圖規(guī)劃之前在地圖邊緣上增加了若干虛擬威脅源,這樣使得生成的Laguerre圖路徑分布更加均勻,更加適合無人機飛行。如圖6所示,虛擬威脅源用深色小圓表示。

圖6 增加虛擬威脅源

2.3 威脅區(qū)域簡化

對于威脅區(qū)域簡化,采用“外切圓法”,即無論威脅區(qū)域是什么形狀,只取一個半徑盡可能小的圓與威脅區(qū)域外切,把威脅區(qū)域全部包含在內(nèi),這樣就把威脅區(qū)域簡化成為了圓形,如圖7所示。

探究1 在其他條件不變的情況下，點(為表達方便，以下討論中統(tǒng)稱該點為D)是否可以換成y軸上的其他點(0,b)呢？

圖7 簡化威脅區(qū)域

2.4 縮小自優(yōu)化A-Star算法規(guī)劃范圍

在使用自優(yōu)化A-Star算法進行二次規(guī)劃之前,需要對規(guī)劃空間進行簡化,以縮減算法的搜索空間,這也是LAStar算法的關鍵之一。在這里提出一種根據(jù)已有航路點簡化規(guī)劃區(qū)域的算法:

步驟1 連接NiNi+1并延長,若與第一次所規(guī)劃的航路沒有交點則NiNi+1為所簡化區(qū)域的一條邊。

步驟2 若NiNi+1的延長線與第一次所規(guī)劃的航路存在交點,則依次連接NiNi+k(k=1,2,3…),當0≤k≤q時,NiNi+k與Ni+mNi+n(0≤m,n≤q且m≠n)不相交,當k=q+1時,NiNi+q+1與Ni+qNi+q+1相交,則NiNi+q為所簡化區(qū)域的一條邊。

步驟3 根據(jù)第一次規(guī)劃的航路從起點開始按照順時針或者逆時針方向?qū)σ?guī)劃空間進行簡化,直到首尾連接形成簡化的多邊形區(qū)域。

2.5 LA-Star算法基本流程及創(chuàng)新性

LA-Star算法的基本流程如圖8所示。

圖8 LA-Star算法流程

LA-Star算法的創(chuàng)新有以下幾點:一是對于傳統(tǒng)A-Star算法的改進,包括改進了威脅區(qū)域的規(guī)避方法、利用虛擬威脅區(qū)域增加了無人機進入角約束以及增加了航路點自優(yōu)化的過程;二是對Laguerre圖算法的優(yōu)化,即增加虛擬威脅源以優(yōu)化生成的航路;三是對于任意形狀威脅源的處理可以簡化成圓形區(qū)域的思想以及兩種規(guī)劃算法的結(jié)合。

3 算法仿真與性能分析

現(xiàn)假設任務區(qū)域為一個大小為100 km×75 km的二維區(qū)域,加入位置和形狀隨機產(chǎn)生的10個四邊形威脅區(qū)域,任務需要兩架完全相同的無人機從兩個初始位置(單位: km)Start1(9.527,40.765)和Start2(14.975,50.075)分別飛往兩個目標位置Target1(91.056,46.599)和Target2 (82.095,61.907),“■”點表示無人機初始位置;“◆”點表示目標點,如圖9所示。下面使用LA-Star算法進行航路規(guī)劃。

圖9 航路規(guī)劃區(qū)域

根據(jù)“外切圓法”計算出每一個多邊形威脅區(qū)域的外切圓,經(jīng)過簡化后的威脅區(qū)域如圖10所示。

圖10 經(jīng)過簡化的航路規(guī)劃區(qū)域

對于簡化后的威脅區(qū)域使用Laguerre圖算法進行航路規(guī)劃,得到的航路如圖11中粗實線所示。

圖11 Laguerre圖算法規(guī)劃結(jié)果

取消威脅區(qū)域的簡化,即使用威脅區(qū)域的真實形狀代替之前簡化的圓形,如圖12所示。對比看出,第一步中使用Laguerre圖進行航路規(guī)劃后,所規(guī)劃的航路對于簡化的威脅區(qū)域來說效果較好,但是在恢復威脅區(qū)域真實形狀后,第一步中所規(guī)劃的航路就明顯不符合航路規(guī)劃要求,因此需要進一步規(guī)劃。接下來的任務就是簡化任務區(qū)域,使用自優(yōu)化A-Star算法進行航路規(guī)劃。

圖12 恢復威脅區(qū)域形狀后的任務空間

經(jīng)過計算,所得到的二次規(guī)劃區(qū)域如圖13中深灰色區(qū)域所示。

圖13 簡化后的航路規(guī)劃區(qū)域

簡化后的空間內(nèi)使用自優(yōu)化A-Star算法進行航路規(guī)劃,所得到的航路如圖14中實線所示。

圖14 LA-Star算法規(guī)劃的航路

3.2 數(shù)據(jù)分析與結(jié)論

對同樣條件下的任務區(qū)域分別使用LA-Star算法、A-Star算法以及Laguerre圖算法進行航路規(guī)劃,比較它們的規(guī)劃時間以及路徑長度,結(jié)果如表1和表2所示。

表1 3種航路規(guī)劃算法規(guī)劃時間比較_

表2 3種航路規(guī)劃算法規(guī)劃路徑長度比較__

從表1和表2的數(shù)據(jù)可以看出,在規(guī)劃時間上, Laguerre圖算法用時最少,LA-Star算法其次,A-Star算法用時最多且比其他兩種算法大很多。這是由于LA-Star算法是在Laguerre圖算法的基礎上使用了自優(yōu)化A-Star算法進行了精確規(guī)劃,因此用時略長于Laguerre圖算法,但是用時明顯少于A-Star算法。

在航路長度上,Laguerre圖算法規(guī)劃的航路最長,LAStar算法和A-Star算法所規(guī)劃的長度相同,且明顯短于Laguerre圖算法,這是由于使用威脅區(qū)域的原始形狀使得規(guī)劃的航路準確性更高。

綜合分析規(guī)劃時間和航路長度兩組數(shù)據(jù),可以得出結(jié)論:Laguerre圖算法雖然用時最短,但是所規(guī)劃的航路長度明顯大于另外兩種算法,且航路較為彎曲,不適合在威脅區(qū)域為非圓形的情況下使用,A-Star算法雖然路徑長度較優(yōu),但是規(guī)劃用時過長,不符合實時性要求。而LA-Star的規(guī)劃時間略大于Laguerre圖算法,但是其規(guī)劃的航路長度最小,路徑更優(yōu),同時符合實時性和準確性的要求。

3.3 算法快速性分析

保證其他試驗條件不變,分別比較LA-Star算法、AStar算法、Laguerre圖算法以及Voronoi圖算法在不同威脅源個數(shù)情況下的運行時間,實驗結(jié)果如圖15所示。

圖15 LA-Star算法比較分析

根據(jù)文獻[6],Laguerre圖算法的復雜度為O(n log n), A-Star算法的復雜度為O(n2),由結(jié)果分析可得,當威脅源個數(shù)較小的時候,LA-Star算法、Laguerre圖算法以及Voronoi圖算法的運行時間相差不大,其中Laguerre圖算法的快速性最好,當威脅源數(shù)目增加,3種算法的差距逐漸增大,然而相比以上3種算法,A-Star算法的運行時間始終較長,并且相差的時間迅速增大。因此,這4種算法的快速性從優(yōu)到差的順序為:Laguerre圖算法＞Voronoi圖算法＞LA-Star算法＞A-Star算法。

通過實驗仿真可以得出以下結(jié)論:綜合LA-Star算法的快速性和準確性,其明顯優(yōu)于其余3種算法。

4 結(jié)束語

由Laguerre圖算法和自優(yōu)化A-Star算法結(jié)合的LAStar算法能夠很好地解決無人機航路規(guī)劃中的實時性問題和準確性問題,對現(xiàn)有的無人機航路規(guī)劃發(fā)展具有顯著的意義。然而,本算法仍有待完善之處,比如多架無人機協(xié)同的情況以及無人機初始位置和目標位置在威脅區(qū)域內(nèi)的情況,這也將在后續(xù)的論文中進行研究與完善。

[1]Wei R X,Li X R.UAV system and operational use[M].Beijing:National Defense Industry Press,2009.(魏瑞軒,李學仁.無人機系統(tǒng)及作戰(zhàn)使用[M].北京:國防工業(yè)出版社,2009.)

[2]Gao H,Chen X,Xia Y C.Research on UAV path planning[J]. Journal of Nanjing University of Aeronautics and Astronautics,2001,33(2):135 138.(高暉,陳欣,夏云程.無人機航路規(guī)劃研究[J].南京航空航天大學學報,2001,33(2):135 -138.)

[3]Yao J F,Lin C,Xie X B,et al.Path planning for virtual human motion using improved A*star algorithm[C]∥Proc.of the 7th International Conference on Information Technology:New Generations,2010:1154-1158.

[4]Kang H,Lee B,Kim K.Path planning algorithm using the particle swarm optimization and the improved dijkstra algorithm[C]∥Proc.of the Pacific-Asia Workshop on Computational Intelligence and Industrial Application,2008:1002-1004.

[5]Peng C,Lu X Q,Dai J Y,et al.Research of path planning method based on the improved Voronoi diagram[C]∥Proc.of the 25th Chinese Control and Decision Conference,2013:2940-2944.

[6]Wang S L,Wei R X,Shen D,et al.Construction algorithm of Laguerre diagram for path planning[J].Systems Engineering and Electronics,2013,35(3):552 556.(王樹磊,魏瑞軒,沈東,等.面向航路規(guī)劃的Laguerre圖構(gòu)造算法[J].系統(tǒng)工程與電子技術(shù),2013,35(3):552-556.)

[7]Ju M Y,Cheng C W.Smooth path planning using genetic algorithms[C]∥Proc.of the 9th World Congress on Intelligent Control and Automation,2011:1103 1107.

[8]Shakiba R,Najafipour M,Salehi M E.An improved PSO-based path planning algorithm for humanoid soccer playing robots[C]∥Proc.of the 3rd Joint Conference of AI&Robotics and the 5th RoboCup Iran Open International Symposium,2013:1-6.

[9]Zhao S G,Li M.Path planning of inspection robot based on ant colony optimization algorithm[C]∥Proc.of the International Conference on Electrical and Control Engineering,2010:1474 -1477.

[10]Choi J W,Curry R E.Real-time obstacle-avoiding path planning for mobile robots[C]∥Proc.of the AIAA Conference on Guidance,Navigation,and Control,2010:216-227.

[11]Lum C W,Vagners J.A search algorithm for teams of heterogeneous agents with coverage guarantees[J].Journal of Aerospace Computing,Information,and Communication,2010,7 (1):1-28.

[12]Berg M D,Kreveld M V,Overmars M,et al.Computation geometry algorithms and application[M].3rd ed.Berlin:Springer-Verlag,2008.

[13]Qi Z,Shao Z H,Ping Y S,et al.An improved heuristic algorithm for UAV path planning in 3D environment[C]∥Proc.of the 2nd International Conference on Intelligent Human-Machine Systems and Cybernetics,2010:258-260.

[14]Qu Y H,Pan Q,Yan J G.Flight path planning of UAV based on heuristically search and genetic algorithms[C]∥Proc.of the 31st Annual Conference of IEEE on Industial Electronics Society,2005:45-49.

[15]Li J,Sun X X.A route planning’s method for unmanned aerial vehicles based on improved A-star algorithm[J].Acta Armamentarii,2008,29(7):788-792.(李季,孫秀霞.基于改進A-Star算法的無人機航跡規(guī)劃算法研究[J].兵工學報,2008,29 (7):788-792.)

[16]Pascarella D,Venticinque S,Aversa R.Agent-based design for uav mission planning[C]∥Proc.of the 8th International Conference on P 2P,Parallel,Grid,Cloud and Internet Computing,2013:76-83.

[17]Li S J.Research on UAV path planning and evaluation methodology[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2012.(李素娟.無人機航路規(guī)劃及評價方法研究[D].南京:南京航空航天大學自動化學院,2012.)

Self-optimization A-Star algorithm for UAV path planning based on Laguerre diagram

WEI Rui-xuan,XU Zhuo-fan,WANG Shu-lei,LüMing-hai
(School of Aeronautics and Astronautics,Air Force Engineering University,Xi’an 710038,China)

In order to relieve the operation burden and time consume for unmanned aerial vehicle(UAV) path planning,a novel UAV path planning method named LA-Star algorithm is proposed which as well guarantees the adaption in scenarios of various threat areas and terrains.Under the roundness assumption of all threat areas and no-fly-zones,the Laguerre diagram algorithm is applied to pre-plan the flight path which largely benefits path re-plan because of shrunk operation space.With the original shape of threat areas,improved A-Star algorithm is then applied in path re-planning with reference to pre-planned path.Finally,optimize the path planned above.Simulations show the LA-Star algorithm satisfies time and veracity requirements.

unmanned aerial vehicle(UAV);path planning;LA-Star algorithm;Laguerre diagram; A-Star algorithm

V 219

A

10.3969/j.issn.1001-506X.2015.03.16

魏瑞軒(1968-),男,教授,博士,主要研究方向為飛行器控制理論與應用。

E-mail:rxw123@sohu.com

許卓凡(1989-),男,碩士研究生,主要研究方向為無人飛行器控制理論與應用。

E-mail:15129006715@163.com

王樹磊(1983-),男,博士研究生,主要研究方向為導航、制導與控制。

E-mail:wangshulei2009@gmail.com

呂明海(1990-),男,碩士研究生,主要研究方向為無人飛行器控制理論與應用。

E-mail:lmh199001@163.com

網(wǎng)址:www.sys-ele.com

1001-506X(2015)03-0577-06

2013 10 10;

2014 05 04;網(wǎng)絡優(yōu)先出版日期:2014 07 13。

網(wǎng)絡優(yōu)先出版地址:http://w ww.cnki.net/kcms/detail/11.2422.TN.20140713.1456.003.html

航空科學基金(20135896027)資助課題