基于Laguerre圖的自優化A-Star無人機航路規劃算法

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

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

基于Laguerre圖的自優化A-Star無人機航路規劃算法

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

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

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

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

0 引 言

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

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

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

1 自優化A-Star算法基本原理

1.1 A-Star算法

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

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

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

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

1.2 威脅區域的規避

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

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

圖1 判斷拓展節點所在區域

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

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

圖2 節點拓展時的兩種情況

1.3 進入角約束

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

圖3 設置虛擬威脅區域

1.4 航路點自優化

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

1.4.1 航路點的刪除

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

圖4 刪除多余的航路點

1.4.2 航路點的插入

經過航路點刪除后,仍然可以實施進一步優化,在航路點之間插入一些新的節點,再根據定義2進行反向順序點優化。

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

圖5 插入航路點優化航路

2 LA-Star算法原理及實現

2.1 Laguerre圖航路規劃基本原理

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

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

2.2 Laguerre圖算法優化

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

圖6 增加虛擬威脅源

2.3 威脅區域簡化

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

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

圖7 簡化威脅區域

2.4 縮小自優化A-Star算法規劃范圍

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

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

步驟2 若NiNi+1的延長線與第一次所規劃的航路存在交點,則依次連接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為所簡化區域的一條邊。

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

2.5 LA-Star算法基本流程及創新性

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

圖8 LA-Star算法流程

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

3 算法仿真與性能分析

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

圖9 航路規劃區域

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

圖10 經過簡化的航路規劃區域

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

圖11 Laguerre圖算法規劃結果

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

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

經過計算,所得到的二次規劃區域如圖13中深灰色區域所示。

圖13 簡化后的航路規劃區域

簡化后的空間內使用自優化A-Star算法進行航路規劃,所得到的航路如圖14中實線所示。

圖14 LA-Star算法規劃的航路

3.2 數據分析與結論

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

表1 3種航路規劃算法規劃時間比較_

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

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

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

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

3.3 算法快速性分析

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

圖15 LA-Star算法比較分析

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

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

4 結束語

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

[1]Wei R X,Li X R.UAV system and operational use[M].Beijing:National Defense Industry Press,2009.(魏瑞軒,李學仁.無人機系統及作戰使用[M].北京:國防工業出版社,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.(高暉,陳欣,夏云程.無人機航路規劃研究[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.(王樹磊,魏瑞軒,沈東,等.面向航路規劃的Laguerre圖構造算法[J].系統工程與電子技術,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算法的無人機航跡規劃算法研究[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.(李素娟.無人機航路規劃及評價方法研究[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

網址:www.sys-ele.com

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

2013 10 10;

2014 05 04;網絡優先出版日期:2014 07 13。

網絡優先出版地址:http://w ww.cnki.net/kcms/detail/11.2422.TN.20140713.1456.003.html

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