一種能有效規(guī)避威脅區(qū)的雙層A路徑規(guī)劃算法*

(1.華中科技大學(xué)自動化學(xué)院多譜信息處理技術(shù)國防科技重點(diǎn)實(shí)驗(yàn)室 武漢 430074)

(2.中國運(yùn)載火箭技術(shù)研究院 北京 100076)

一種能有效規(guī)避威脅區(qū)的雙層A路徑規(guī)劃算法*

陽志如1陸宏澤2周成平1

(1.華中科技大學(xué)自動化學(xué)院多譜信息處理技術(shù)國防科技重點(diǎn)實(shí)驗(yàn)室 武漢 430074)

(2.中國運(yùn)載火箭技術(shù)研究院 北京 100076)

針對路徑規(guī)劃中A*算法遇到威脅區(qū)易陷入局部搜索的問題,對擴(kuò)展點(diǎn)的估計(jì)代價(jià)計(jì)算方式進(jìn)行了改進(jìn),提出了一種基于A*的雙層A*規(guī)劃算法。在該算法的雙層機(jī)制中,第一層規(guī)劃的擴(kuò)展點(diǎn)估計(jì)代價(jià)用第二層規(guī)劃的結(jié)果來計(jì)算,使得搜索過程中擴(kuò)展結(jié)點(diǎn)的估計(jì)代價(jià)更接近于真實(shí)代價(jià),從而得到該結(jié)點(diǎn)更加準(zhǔn)確的全代價(jià)值,引導(dǎo)算法向更合適的方向擴(kuò)展,提高了搜索效率。實(shí)驗(yàn)表明：在較復(fù)雜的規(guī)劃空間中,該算法能有效解決A*算法遇到威脅區(qū)陷入局部搜索的弊病。

A*算法;路徑規(guī)劃;威脅區(qū);雙層A*

ClassNumberU666

1 引言

在路徑規(guī)劃問題[1]中,適宜的路徑搜索算法在沒有人工干預(yù)的條件下,能夠自動、有效地完成路徑規(guī)劃任務(wù),使運(yùn)動體能有效地規(guī)避威脅、高效地到達(dá)目的地。常用的規(guī)劃算法有A*搜索算法、動態(tài)規(guī)劃法、Dijkstra算法、遺傳算法、粒子群算法、數(shù)學(xué)規(guī)劃等。所有這些算法中,A*搜索算法由于計(jì)算簡單、算法易實(shí)現(xiàn),并且在理論上可以保證全局最優(yōu)解的收斂性,因此得到了廣泛的應(yīng)用。在實(shí)際規(guī)劃任務(wù)的約束和需求中,自動和有效地規(guī)避威脅區(qū),是A*算法規(guī)劃的難點(diǎn)之一,它在搜索過程中遇到威脅區(qū)易陷入局部搜索問題[3]。

針對A*算法規(guī)避威脅區(qū)的問題,Khammapun Khantanapoka[4]、Basem M.ElHalawany[5]等提出了基于格網(wǎng)空間的A*規(guī)劃方法,該類方法能有效威脅建模與裁剪空間,從而更好地規(guī)避威脅,但是不能有效結(jié)合運(yùn)動體的運(yùn)動約束條件;李季[6]、李春華[7]等提出了改進(jìn)的A*規(guī)劃算法,該類方法結(jié)合飛行器簡化運(yùn)動學(xué)方程,更全面地考慮到了飛行器的約束,能有效削減搜索空間,實(shí)現(xiàn)自動的威脅回避,但威脅建模只考慮了簡單的威脅源的情況,不能解決遇到復(fù)雜的威脅區(qū)而陷入局部搜索的問題。嚴(yán)江江[8]、劉新[9]等提出了一種導(dǎo)引點(diǎn)集的策略,在威脅區(qū)比較密集的地方,用導(dǎo)引點(diǎn)來引導(dǎo)飛行器有效避開威脅區(qū),該方法減小了局部搜索,大大減少了搜索時(shí)間,但導(dǎo)引點(diǎn)集的設(shè)置沒有統(tǒng)一標(biāo)準(zhǔn),過于依賴人的經(jīng)驗(yàn),沒有實(shí)現(xiàn)自動威脅規(guī)避。針對以上情況提出了雙層A*規(guī)劃算法。雙層A*的機(jī)制是：第一層是標(biāo)準(zhǔn)A*流程,根據(jù)代價(jià)值引導(dǎo)擴(kuò)展點(diǎn)去生成子結(jié)點(diǎn)；第二層是利用A*的擴(kuò)展機(jī)制,尋找一條從當(dāng)前子結(jié)點(diǎn)到目標(biāo)點(diǎn)的近似路徑,將該路徑代價(jià)作為該子結(jié)點(diǎn)的估計(jì)代價(jià)。這種計(jì)算方式能引導(dǎo)算法更高效地進(jìn)行擴(kuò)展。經(jīng)仿真,證明了算法能有效解決A*算法遇到威脅區(qū)陷入局部搜索的弊病,更好地規(guī)避威脅。

2 A*算法的基本原理

A*算法是一種典型的啟發(fā)式圖搜索算法[10]。A*算法本身的特性是：在狀態(tài)空間中進(jìn)行搜索時(shí),它對每一個(gè)搜索的位置利用啟發(fā)式信息(即代價(jià))進(jìn)行評估,得到當(dāng)前最好的位置。每次都選擇最好位置進(jìn)行下一步擴(kuò)展,直到到達(dá)目標(biāo)(或稱找到問題的解),從而省略一些無謂的搜索,提高搜索效率。A*算法能夠利用擴(kuò)展策略,將約束條件、任務(wù)需求與搜索過程緊密結(jié)合,能在有限的可選狀態(tài)中,選擇最優(yōu)解,并且在理論上滿足全局最優(yōu)解的收斂性[11]。

2.1 擴(kuò)展策略

路徑規(guī)劃的研究對象包括飛行器、水面艦艇、地面車輛以及機(jī)器人等?？紤]一般運(yùn)動體的約束條件：最小/最大轉(zhuǎn)彎角度、最小/最大轉(zhuǎn)彎半徑、最小/最大轉(zhuǎn)彎弧長、距威脅區(qū)的安全距離。根據(jù)這些約束條件,將A*擴(kuò)展策略與之緊密結(jié)合。同時(shí)考慮到最優(yōu)性和高效性兩個(gè)特點(diǎn)：最優(yōu)性指的是擴(kuò)展策略能夠充分覆蓋包含最優(yōu)路徑的解空間；高效性指的是擴(kuò)展策略能夠利用約束條件有效裁剪空間,提高搜索效率,降低計(jì)算的時(shí)空復(fù)雜度[12]。基于以上兩個(gè)特點(diǎn),結(jié)合約束條件來制定擴(kuò)展策略。圖1是擴(kuò)展策略示意圖。

圖1 結(jié)點(diǎn)擴(kuò)展示意圖

A*的擴(kuò)展區(qū)域S是運(yùn)動體作一次機(jī)動能到達(dá)的區(qū)域。如圖1所示,P是當(dāng)前擴(kuò)展點(diǎn),直線L1代表P點(diǎn)的當(dāng)前運(yùn)動方向,顯然S是以L1為中心對稱。R為運(yùn)動體最小的轉(zhuǎn)彎半徑,L2是沿最小半徑機(jī)動時(shí)的擴(kuò)展弧線,L3是最小弧長擴(kuò)展線,L4是最大弧長擴(kuò)展線,L5是最小轉(zhuǎn)彎角的擴(kuò)展線,L6是最大轉(zhuǎn)彎角的擴(kuò)展線。S的近端由最小轉(zhuǎn)彎半徑和最小弧長限定,遠(yuǎn)端由最大弧長限定；左右兩邊由最大轉(zhuǎn)彎角限定,考慮到最小轉(zhuǎn)彎角а內(nèi)是不可到達(dá)的,則L5將圖示а角范圍限定在可達(dá)區(qū)域外。由此可見,擴(kuò)展區(qū)域S是由L1～L6這幾條弧或線包絡(luò)圍成的兩片對稱的區(qū)域組成,擴(kuò)展點(diǎn)是通過網(wǎng)格劃分在S中選擇點(diǎn)來進(jìn)行的。

圖1中Length為長度步長,θ為角度步長。劃分格網(wǎng)時(shí),具體做法是在S內(nèi),過P點(diǎn)作偏離L1的角度為K倍θ的一系列直線和以P為圓心作半徑為K倍Length長度的一系列圓弧,其中,K為1～n的常數(shù)。用所作的直線和圓弧對網(wǎng)格進(jìn)行劃分,把網(wǎng)格交點(diǎn)作為P的擴(kuò)展子結(jié)點(diǎn)。

若M為當(dāng)前點(diǎn)P的坐標(biāo)點(diǎn)擴(kuò)展子結(jié)點(diǎn),則其坐標(biāo)值與運(yùn)動方向MFly的計(jì)算公式如下所示：

(1)

MFly=PFly+2ξ

(2)

其中L為MP連線的距離,ξ為MP連線與L1的夾角,逆時(shí)針為正,順時(shí)針為負(fù)。

2.2 路徑評價(jià)與擴(kuò)展基本流程

路徑規(guī)劃本質(zhì)上是最優(yōu)路線問題,以f(n)表示從出發(fā)點(diǎn)V到目標(biāo)點(diǎn)T的路徑上的代價(jià)值,則路徑規(guī)劃問題為找到V到T的路徑,使代價(jià)函數(shù)最小。

對A*算法來說,其關(guān)鍵在于設(shè)計(jì)出一個(gè)如下形式的合適的啟發(fā)函數(shù),這個(gè)函數(shù)即代價(jià)函數(shù)。

f(n)=g(n)+h(n)

(3)

g(n)是從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的代價(jià),h(n)為從當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的實(shí)際代價(jià)。通過比較f(n),選擇合適的結(jié)點(diǎn)進(jìn)行擴(kuò)展[13]。實(shí)際情況中,因?yàn)閺漠?dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)無法計(jì)算,一般是用估計(jì)代價(jià)h*(n)代替h(n),則相應(yīng)的代價(jià)為f*(n)。

理論上,為了收斂到全局最優(yōu)解,必須滿足收斂條件[14]：

h*(n)≤h(n)

(4)

在本文中,代價(jià)只考慮距離長度,所以式(4)可以具體化為

(5)

其中l(wèi)i為實(shí)際的第i段實(shí)際的已規(guī)劃的路徑。li的轉(zhuǎn)彎半徑為Ri,第i個(gè)點(diǎn)的Mi坐標(biāo)為Mi(MiX,MiY,MiFly)。li是由Mi和M(i+1)組成。

(6)

(7)

在擴(kuò)展過程中創(chuàng)建兩個(gè)表：OPEN表和CLOSE表,OPEN表保存所有已經(jīng)生成但未被擴(kuò)展的點(diǎn),CLOSE表記錄已經(jīng)被擴(kuò)展的點(diǎn)。

它實(shí)現(xiàn)的步聚是：

1)將起點(diǎn)置入OPEN,然后利用擴(kuò)展策略生成與之相關(guān)的子結(jié)點(diǎn)；

2)對每一個(gè)可行子結(jié)點(diǎn)都計(jì)算相應(yīng)的代價(jià)f*(n),依次置入OPEN,并選出最小值的點(diǎn)作為新的擴(kuò)展點(diǎn),并將其置入CLOSE表;

3)如果該結(jié)點(diǎn)是目標(biāo)點(diǎn),就結(jié)束搜索,轉(zhuǎn)4),否則對新的擴(kuò)展點(diǎn)進(jìn)行擴(kuò)展,并進(jìn)入步驟2);

4)從目標(biāo)點(diǎn)回溯記錄最短路徑,直到出發(fā)點(diǎn)。

3 改進(jìn)的雙層機(jī)制的A*算法

本文的算法是在二維空間中進(jìn)行搜索。設(shè)(x,y)為規(guī)劃空間某一點(diǎn)的坐標(biāo),則規(guī)劃空間可以表示為集合{(x,y)|0≤x≤MaxX,0≤y≤MaxY},它代表了一個(gè)空間區(qū)域。在實(shí)際規(guī)劃過程中,還需要將該空間區(qū)域離散化,即將x,y分別按不同的分辨率進(jìn)行劃分,從而得到離散化的規(guī)劃空間。

結(jié)合具體環(huán)境,擴(kuò)展過程中綜合考慮的約束條件一般主要有威脅區(qū)約束、運(yùn)動體約束。

3.1 威脅區(qū)模型

二維區(qū)域的威脅區(qū)都具有幾何形狀,威脅區(qū)都是一個(gè)二維的幾何圖形。因此,本文利用多個(gè)點(diǎn)組成的多邊形來近似建模。這種建模方法雖然一定程度上擴(kuò)大了威脅區(qū)區(qū)域,但大大簡化了威脅區(qū)的表達(dá),能提高效率；另一方面,用多邊形建模的方法靈活多變,能表示各種不同的形狀信息,使仿真環(huán)境更貼近于實(shí)際環(huán)境,從而提高規(guī)劃的準(zhǔn)確性。

威脅區(qū)可以采用的多邊形描述為n個(gè)點(diǎn)的集合S(P1,P2,…,Pn),Pn表示組成多邊形的第n個(gè)坐標(biāo)點(diǎn),如圖2所示,虛線是實(shí)際的障礙物模型,用多邊形直線進(jìn)行擬合。

圖2 多邊形擬合實(shí)際的威脅區(qū)示意圖

由此可見,用這種方法能較好地貼合實(shí)際形狀,而且,如果坐標(biāo)點(diǎn)越多的話,越能與實(shí)際形狀相一致。這種威脅區(qū)的建模方法,簡單直觀,大大簡化計(jì)算,給規(guī)劃、編程都帶來便利。

3.2 改進(jìn)思路

在A*規(guī)劃的規(guī)避威脅處理上,要求對所有的威脅均作規(guī)避,即要求規(guī)劃路徑滿足代價(jià)上最優(yōu)的同時(shí),不能穿越任何威脅區(qū),并將穿越威脅區(qū)的點(diǎn)定義為無效點(diǎn)。

為了滿足式(4)的全局收斂條件,常規(guī)A*的做法是以當(dāng)前點(diǎn)P到目標(biāo)點(diǎn)T的直線距離作為啟發(fā)函數(shù)的估計(jì)代價(jià)項(xiàng)h*(n)。這種做法簡單、易于實(shí)現(xiàn),但由于估計(jì)代價(jià)偏小,導(dǎo)致局部搜索區(qū)內(nèi)(如圖3所示)的點(diǎn)被優(yōu)先擴(kuò)展,但這些點(diǎn)的子結(jié)點(diǎn)又容易落在威脅區(qū)內(nèi),成為無效點(diǎn),致使當(dāng)前路徑搜索失敗。此情況下,規(guī)劃極易陷入局部搜索,難以跳出,耗時(shí)太大,存在很多的無效點(diǎn)的搜索,搜索效率太低。

圖3 大面積遮擋示意圖

為了更有效地利用環(huán)境信息,得到擴(kuò)展點(diǎn)更準(zhǔn)確的代價(jià)信息,從而避免在一些遮擋面積較大的威脅區(qū)前大量無效點(diǎn)的擴(kuò)展,更快地跳出局部搜索,節(jié)省規(guī)劃時(shí)間。在A*算法的基礎(chǔ)上進(jìn)行改進(jìn)時(shí),必然要對當(dāng)前擴(kuò)展點(diǎn)能否通過威脅區(qū)作一個(gè)判斷,把不能通過的點(diǎn)排除在可行點(diǎn)之外；另一方面是要對估計(jì)代價(jià)的計(jì)算方式進(jìn)行改進(jìn)。

改進(jìn)方法是對于第一層擴(kuò)展點(diǎn)生成的子結(jié)點(diǎn),先判斷其能否規(guī)避當(dāng)前威脅區(qū),能規(guī)避的點(diǎn)再用第二層A*去計(jì)算估計(jì)代價(jià)值h*(n)。第二層A*的結(jié)果是一條由威脅區(qū)切點(diǎn)組成的估計(jì)路徑折線,用這個(gè)折線去評估能否規(guī)避威脅區(qū),同時(shí),去更準(zhǔn)確估算代價(jià)。

3.3雙層A*規(guī)劃

判斷當(dāng)前點(diǎn)P能否規(guī)避當(dāng)前威脅區(qū)M時(shí),如圖4所示,每個(gè)威脅區(qū)都具有左、右兩個(gè)可以規(guī)避的方向,過P作M的左、右兩個(gè)切點(diǎn)S、S′,所得切線與PT連線的兩個(gè)夾角定義為左切角α和右切角β,設(shè)置一種機(jī)制：給α、β設(shè)置一個(gè)角度的上限閾值λ,若α或β滿足小于或等于λ的條件,則認(rèn)為當(dāng)前點(diǎn)P可以通過M的相應(yīng)方向；否則,認(rèn)為此方向不可行。兩個(gè)方向均不可行的擴(kuò)展點(diǎn)則不能規(guī)避當(dāng)前威脅區(qū)。

設(shè)置威脅區(qū)的角度的上限閾值λ的機(jī)制,如圖4所示,所有左、右兩邊切角等于λ點(diǎn)的集合組成的軌跡是兩段圓弧,數(shù)學(xué)意義上,表示ST、S′T弧分別在相應(yīng)圓上對應(yīng)的圓周角等于λ。定義兩段圓弧與威脅區(qū)共同圍起來的這個(gè)區(qū)域?yàn)橥{區(qū)的局部擴(kuò)展區(qū)。顯然,落在局部擴(kuò)展區(qū)內(nèi)的子結(jié)點(diǎn)的切角均大于相應(yīng)的角度閾值λ。且λ越大局部擴(kuò)展區(qū)越小,大λ對應(yīng)的局部擴(kuò)展區(qū)包含在相應(yīng)的小λ的局部擴(kuò)展區(qū)內(nèi)。

圖4 威脅區(qū)擴(kuò)展示意圖

這種方法中威脅區(qū)的范圍有所擴(kuò)大,人為地把落在局部擴(kuò)展區(qū)的點(diǎn)等效為無效點(diǎn),把易陷入局部搜索的區(qū)域排除在可達(dá)區(qū)域之外。這樣做的優(yōu)點(diǎn)是：

1)這種方法能避免一些無效擴(kuò)展,更快地跳出局部搜索,啟發(fā)的路徑能更好地規(guī)避威脅區(qū)。

2)另一方面這種方法得到的擬合折線在可行性上面是有保障的,不會出現(xiàn)很短的距離作很大拐彎的現(xiàn)象,進(jìn)一步提高估計(jì)代價(jià)的準(zhǔn)確度。

顯然,角度閾值λ的大小決定著局部擴(kuò)展區(qū)的大小。也可以設(shè)置λ的不同數(shù)值,由此控制局部擴(kuò)展區(qū)的范圍的大小,調(diào)整擴(kuò)展和規(guī)劃速度。λ越小,局部擴(kuò)展區(qū)的范圍就越大,可行點(diǎn)的區(qū)域就會變小,擴(kuò)展的速度相對來說會更快。但如果λ過小,導(dǎo)致局部擴(kuò)展區(qū)過大,可行點(diǎn)的選擇范圍被大大壓縮,就會影響路徑的全局最優(yōu)性。λ越大,被排除在可行區(qū)域之外的局部擴(kuò)展區(qū)就越小,可行點(diǎn)的范圍就越大,路徑的全局最優(yōu)性就更能得到保障。λ的值的范圍設(shè)置在0°～90°之間,為了更好引導(dǎo)運(yùn)動體從兩邊規(guī)避威脅區(qū),產(chǎn)生更加平滑的路徑,λ不宜超過60°。

圖5 第二層A*示意圖

若折線規(guī)劃到達(dá)目標(biāo)點(diǎn),且總共有2N個(gè)點(diǎn),則P-S1-P1-S2-P2-…-SN-PN-T即為當(dāng)前點(diǎn)P的預(yù)估折線。利用這條預(yù)估折線對當(dāng)前點(diǎn)P的預(yù)估代價(jià)進(jìn)行計(jì)算。

(8)

3.4第二層A*流程

第二層中跟第一層擴(kuò)展一樣,也創(chuàng)建功能相似的兩個(gè)表：D-OPEN表和D-CLOSE表。

子結(jié)點(diǎn)P的第二層A*的過程如下：

1)置P入D-OPEN表中；

2)若D-OPEN表為空,則規(guī)劃失敗；否則從D-OPEN表中取出代價(jià)最小的點(diǎn)S；

3)求S到目標(biāo)點(diǎn)T之間的連線,按順序記錄此連線穿行的威脅區(qū),若沒有穿過威脅區(qū),置目標(biāo)點(diǎn)入D-CLOSE表,規(guī)劃成功,并轉(zhuǎn)第5)步,否則轉(zhuǎn)下一步；

5)規(guī)劃成功,由目標(biāo)點(diǎn)回溯,得到當(dāng)前P點(diǎn)的預(yù)估折線路徑。

4 實(shí)驗(yàn)結(jié)果

本算法在CPU為Core E7200 2.53GHz、內(nèi)存2.0GB的PC機(jī)上進(jìn)行了實(shí)驗(yàn),運(yùn)行環(huán)境為Windows XP,編程環(huán)境為VS2005。實(shí)驗(yàn)使用了分辨率為30*30、大小為900km×350km的地圖和模擬生成的威脅區(qū)數(shù)據(jù),仿真的基本參數(shù)如下：

運(yùn)動體的轉(zhuǎn)彎角度范圍為10°～45°,起始點(diǎn)到目標(biāo)點(diǎn)的直線距離為740km。其中,擴(kuò)展的最小半徑為100km,最小弧長為70km,最大弧長為250km。角度步長為5°,擴(kuò)展步長為25km,安全距離為30km。

在同樣的環(huán)境下,利用兩種方法進(jìn)行路徑規(guī)劃。從方法上比較,常規(guī)的A*是以當(dāng)前點(diǎn)P到目標(biāo)點(diǎn)T的直線距離作為啟發(fā)函數(shù)的估計(jì)代價(jià)項(xiàng),而改進(jìn)的方法是用第二層A*來計(jì)算估計(jì)代價(jià),并對角度閾值λ設(shè)置不同的數(shù)值進(jìn)行比較。表1給出了以上實(shí)驗(yàn)的部分?jǐn)?shù)據(jù)。其中,擴(kuò)展結(jié)點(diǎn)的個(gè)數(shù)是指總共嘗試去擴(kuò)展的節(jié)點(diǎn),有效節(jié)點(diǎn)是與無效點(diǎn)相對的概念,是指那些成功加入OPEN表,能組成有效路徑的點(diǎn)。

實(shí)驗(yàn)參數(shù)設(shè)置如下：λ=20°,25°,…,45°。實(shí)驗(yàn)結(jié)果及部分?jǐn)?shù)據(jù)如表1、圖6、圖7所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

圖6 常規(guī)A*路徑的水平投影圖

圖7 雙層A*路徑的水平投影圖

其中,深色區(qū)域表示威脅區(qū),旗幟和三角形分別表示出發(fā)點(diǎn)和目標(biāo)點(diǎn),灰色圓點(diǎn)表示機(jī)動變化點(diǎn)(轉(zhuǎn)彎起始點(diǎn)/轉(zhuǎn)彎結(jié)束點(diǎn))。

從表1數(shù)據(jù)可知：與常規(guī)A*相比,雙層A*的規(guī)劃速度、擴(kuò)展效率均占有優(yōu)勢。對λ進(jìn)行調(diào)整時(shí),λ過小,時(shí)間大大減小,但規(guī)劃路徑效果變差。同樣,λ增加到一定程度后收斂到全局最優(yōu)解,不會再改變規(guī)劃效果,但會相應(yīng)增加規(guī)劃時(shí)間。

實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法大大減小了無效點(diǎn)的擴(kuò)展,能有效地提高規(guī)劃速度、提升擴(kuò)展點(diǎn)的效率,更好地實(shí)現(xiàn)規(guī)避威脅區(qū)的目的。同時(shí),可以更靈活地通過調(diào)整λ的大小的方式來調(diào)節(jié)規(guī)劃的速度與規(guī)劃效果。

5 結(jié)語

本文提出了一種雙層A*算法路徑規(guī)劃方法,該方法采用雙層機(jī)制,利用第二層A*對第一層A*的代價(jià)進(jìn)行更準(zhǔn)確的計(jì)算,從而加快了收斂速度,提高搜索效率。實(shí)驗(yàn)結(jié)果表明,在滿足運(yùn)動體自身約束、環(huán)境約束的條件下,該方法能夠有效解決遇到相對較大威脅區(qū)陷入局部搜索的弊病。

[1]馬仁利,關(guān)正西.路徑規(guī)劃的現(xiàn)狀與發(fā)展綜述[J].現(xiàn)代機(jī)械,2008(3):22-27.

[2]Chabini, Lan shan.Adaptation of the algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks[J].IEEE Trans on intelligent Transportation Systems,2002,3(1):60-74.

[3]蒙波,皮亦鳴,曹宗杰.基于改進(jìn)算法的無人機(jī)航跡規(guī)劃[J].計(jì)算機(jī)仿真,2010(9):29-32.

[4]Khantanapoka K, Chinnasarn K.Path finding of 2D &3D game real-time strategy with depth direction algorithm for multi-layer[C]//2009 Eighth International Symposium on Natural Language Processing,2009:184-188.

[5]Basem M.ElHalawany, Hala M.Abdel-Kader, Adly TagEldeen, et al.Modified Algorithm for Safer Mobile Robot[C]//Navigation, 2013 Proceeding of International Conference on Modelling, Idetification &control(ICMIC),2013:74-78.

[6]李季,孫秀霞.基于改進(jìn)A-star算法的無人機(jī)航跡規(guī)劃算法研究[J].兵工學(xué)報(bào),2008(29):788-792.

[7]李春華,鄭昌文,周成平,等.一種三維航跡快速搜索方法[J].宇航學(xué)報(bào),2002(3):12-17.

[8]嚴(yán)江江,丁明躍,周成平,等.一種基于可行優(yōu)先的三維航跡規(guī)劃方法[J].宇航學(xué)報(bào),2009(30):139-144.

[9]劉新,周成平,俞琪,等.基于分層策略的三維航跡快速規(guī)劃方法[J].宇航學(xué)報(bào),2010(11):2524-2529.

[10]Steven M.LaVatle Planning Algorithms[M].London: Cambridge University Press,2006.

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

[12]宋建梅,李侃.基于算法的遠(yuǎn)程導(dǎo)彈三維航跡規(guī)劃算法[J].北京理工大學(xué)學(xué)報(bào),2007(7):613-617.

[13]漆陽華,楊戰(zhàn)平,黃清華.A*的改進(jìn)路徑規(guī)劃[J].信息與電子工程,2009(4):326-329.

[14]Peter E.Hart, Nils J.Nilsson.Bertram Raphael A formal basis for the heuristic determination of minimum cost paths in graphs[J].IEEE Transactions of Systems Science and Cybernetics,1968,SSC-4(2):100-107.

ABi-levelA*PathPlanningAlgorithmforEffectivelyAvoidingtheObstacle-areas

YANG Zhiru1LU Hongze2ZHOU Chengping1

(1.State Key Laboratory for Multi-Spectral Information Processing Technologies,
School of Automation, Huazhong University of Science and Technology, Wuhan 430074)
(2.China Academy of Launch Vehicle Technology, Beijing 100076)

In the case that path A*planning algorithm falling into local search problems in search process when encountering threat areas, the estimated-cost calculation method of the expansion point is improved and a bi-level planning algorithm based on original A*algorithm is proposed.In the bi-level mechanism, the estimated-cost of the expansion node in the first-level is calculated by the outcome of the second-level to make the estimated-cost of search process closer to real cost so to obtain more accurate whole-cost of the current node, thereby guiding expansion of the algorithm to a more appropriate direction, and to improve the search efficiency.Experiments show that in the planning space containing complex threat areas, the algorithm can effectively solve the algorithm encountering threat area into local search problems.

A*algorithm, path planning, threat area, bi-level mechanism

2014年1月3日,

:2014年2月21日

陽志如,男,碩士研究生,研究方向:無人飛行器的航跡規(guī)劃。陸宏澤,女,博士研究生,工程師。周成平,男,副教授,研究生導(dǎo)師,研究方向:無人飛行器航跡規(guī)劃。

U666DOI:10.3969/j.issn1672-9730.2014.07.011