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

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

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

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

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

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

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

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

0 引 言

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

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

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

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

1.1 A-Star算法

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

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

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

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

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

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

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

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

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

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

圖2 節(jié)點(diǎn)拓展時(shí)的兩種情況

1.3 進(jìn)入角約束

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

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

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

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

1.4.1 航路點(diǎn)的刪除

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

圖4 刪除多余的航路點(diǎn)

1.4.2 航路點(diǎn)的插入

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

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

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

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

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

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

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

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

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

圖6 增加虛擬威脅源

2.3 威脅區(qū)域簡(jiǎn)化

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

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

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

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

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

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

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

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

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

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

圖8 LA-Star算法流程

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

3 算法仿真與性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 算法快速性分析

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

圖15 LA-Star算法比較分析

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

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

4 結(jié)束語(yǔ)

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

[1]Wei R X,Li X R.UAV system and operational use[M].Beijing:National Defense Industry Press,2009.(魏瑞軒,李學(xué)仁.無人機(jī)系統(tǒng)及作戰(zhàn)使用[M].北京:國(guó)防工業(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.(高暉,陳欣,夏云程.無人機(jī)航路規(guī)劃研究[J].南京航空航天大學(xué)學(xué)報(bào),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.(李季,孫秀霞.基于改進(jìn)A-Star算法的無人機(jī)航跡規(guī)劃算法研究[J].兵工學(xué)報(bào),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.(李素娟.無人機(jī)航路規(guī)劃及評(píng)價(jià)方法研究[D].南京:南京航空航天大學(xué)自動(dòng)化學(xué)院,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-),男,教授,博士,主要研究方向?yàn)轱w行器控制理論與應(yīng)用。

E-mail:rxw123@sohu.com

許卓凡(1989-),男,碩士研究生,主要研究方向?yàn)闊o人飛行器控制理論與應(yīng)用。

E-mail:15129006715@163.com

王樹磊(1983-),男,博士研究生,主要研究方向?yàn)閷?dǎo)航、制導(dǎo)與控制。

E-mail:wangshulei2009@gmail.com

呂明海(1990-),男,碩士研究生,主要研究方向?yàn)闊o人飛行器控制理論與應(yīng)用。

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)絡(luò)優(yōu)先出版日期:2014 07 13。

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

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