基于雙向A*算法的城市無人機(jī)航路規(guī)劃

林　娜，李天嘯

(沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136)

?

基于雙向A*算法的城市無人機(jī)航路規(guī)劃

林娜，李天嘯

(沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136)

應(yīng)用雙向A*算法對(duì)在城市環(huán)境中的無人機(jī)進(jìn)行航路規(guī)劃，對(duì)比傳統(tǒng)的A*搜索算法，雙向A*搜索算法提高了搜索的效率，大大縮短了航路規(guī)劃的時(shí)間。同時(shí)針對(duì)雙向A*算法現(xiàn)有的不足，對(duì)雙向A*算法進(jìn)行改進(jìn)，提出了同步雙向A*搜索算法思想，通過編程實(shí)現(xiàn)雙向A*算法正向搜索和反向搜索同步進(jìn)行，并且采用柵格法對(duì)無人機(jī)的飛行環(huán)境進(jìn)行建模，在建模時(shí)充分考慮城市環(huán)境確定柵格的大小。通過實(shí)驗(yàn)驗(yàn)證，同步雙向A*算法可以快速為無人機(jī)規(guī)劃出航路，且航路可飛，對(duì)比改進(jìn)前的雙向A*算法，同步雙向A*算法的航路規(guī)劃速度更快，效率更高。

無人機(jī)；雙向A*；柵格法；城市環(huán)境；航路規(guī)劃

A*算法是一種經(jīng)典的啟發(fā)式搜索算法，并廣泛應(yīng)用于路徑搜索問題中。A*算法的思想最早由P.E Hait和N.J Nilsson提出，在以后的應(yīng)用中得到了不斷的改進(jìn)與發(fā)展。如：J.Szczerba提出了稀疏A*算法(Sparse A*Search，SAS)[1]，其主要思想為通過一個(gè)約束函數(shù)將A*算法的搜索范圍縮小，縮短了算法的時(shí)間，提高了算法的搜索效率；何雨楓、曾慶化等提出了無記憶A*算法[2]的思想，針對(duì)A*算法的OPEN表和CLOSE表進(jìn)行改進(jìn)，使OPEN表中的節(jié)點(diǎn)數(shù)每次都保持最小，從而提高算法的計(jì)算速度。

而以上方法都是基于單一方向的A*算法，即從起始節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)搜索。而本文將應(yīng)用雙向A*算法對(duì)無人機(jī)的航路進(jìn)行搜索，并針對(duì)傳統(tǒng)雙向A*算法存在的不足，提出了同步雙向啟發(fā)式A*算法，將其應(yīng)用于柵格建模環(huán)境中。

柵格思想由M．B．Meteas提出[3]，而A*算法便是基于柵格空間的一個(gè)經(jīng)典的路徑規(guī)劃算法。應(yīng)用同步雙向啟發(fā)式A*算法，通過把約束條件結(jié)合到搜索算法中去，可以有效地修剪搜索空間中無效的節(jié)點(diǎn)，從而縮短搜索時(shí)間，而同步雙向啟發(fā)式A*算法的應(yīng)用，可以提高路徑搜索的效率，縮短路徑搜索的時(shí)間。通過實(shí)驗(yàn)表明，該算法可行。

1　問題描述與環(huán)境建模

1.1問題描述

近年來，隨著無人機(jī)技術(shù)的不斷成熟與發(fā)展，無人機(jī)不再只局限于軍事領(lǐng)域之中，在民用領(lǐng)域中，諸如交通監(jiān)測(cè)、事故調(diào)查、追蹤車輛等任務(wù)中，無人機(jī)以其機(jī)動(dòng)性高、受環(huán)境影響小、反應(yīng)迅速、低空飛行等特點(diǎn)，在執(zhí)行任務(wù)時(shí)有著得天獨(dú)厚的優(yōu)勢(shì)。然而在執(zhí)行這些任務(wù)時(shí)，無人機(jī)的飛行環(huán)境大多以城市為主，而在城市環(huán)境中，對(duì)無人機(jī)來說最主要的障礙物就是城市中的建筑物。當(dāng)無人機(jī)進(jìn)行超低空飛行時(shí)，可以將每個(gè)街區(qū)近似看成一個(gè)大的障礙物，而這些障礙物相對(duì)于無人機(jī)來說都是靜止的，對(duì)路徑規(guī)劃來說也是已知的。

無人機(jī)從給定的起始點(diǎn)出發(fā)，最終要到達(dá)位置已知的目標(biāo)點(diǎn)，在障礙物位置與高度已知的條件下，通過路徑規(guī)劃，使無人機(jī)可以避開障礙物，為無人機(jī)規(guī)劃出一條適合城市環(huán)境的飛行航路。

1.2環(huán)境建模

本文將應(yīng)用柵格思想對(duì)無人機(jī)的飛行環(huán)境進(jìn)行建模。將無人機(jī)飛行的城市環(huán)境按柵格法分解成若干個(gè)柵格，柵格的大小按城市的規(guī)模而定。如果城市規(guī)模特大，柵格的大小也可按區(qū)域劃分。柵格的大小直接影響搜索算法的搜索效率：柵格越小，環(huán)境表達(dá)越精細(xì)，信息量越大，搜索算法的負(fù)擔(dān)就會(huì)越重，效率會(huì)下降；而較大的柵格會(huì)導(dǎo)致環(huán)境表達(dá)粗糙，使規(guī)劃出的航路不夠精細(xì)。

將每個(gè)柵格的中心點(diǎn)看作是A*算法的一個(gè)備選節(jié)點(diǎn)，若一個(gè)柵格內(nèi)包含障礙物，則將其視為障礙節(jié)點(diǎn)；若柵格空間內(nèi)不包含障礙物，則將其視為自由節(jié)點(diǎn)。

目前，無人機(jī)可分為固定翼無人機(jī)和旋翼無人機(jī)兩大種類，旋翼無人機(jī)相比于固定翼無人機(jī)來說，其機(jī)動(dòng)性及其可懸停性更適合在城市環(huán)境中飛行和執(zhí)行任務(wù)。

對(duì)于旋翼無人機(jī)來說，由于其機(jī)動(dòng)性很強(qiáng)，轉(zhuǎn)彎不受轉(zhuǎn)彎角度和轉(zhuǎn)彎半徑的限制，所以以旋翼無人機(jī)所在柵格為中心，周圍的上下左右8個(gè)柵格均為其可機(jī)動(dòng)?xùn)鸥?，如圖1所示。

圖1　旋翼無人機(jī)可機(jī)動(dòng)?xùn)鸥袷疽鈭D

旋翼無人機(jī)由于其機(jī)動(dòng)性強(qiáng)的特性，在設(shè)計(jì)柵格大小的時(shí)候就可以不用考慮無人機(jī)轉(zhuǎn)彎角度和轉(zhuǎn)彎半徑等因素?？梢愿嗟乜紤]所在城市的具體環(huán)境，如街區(qū)的尺寸和建筑物的尺寸等因素，使設(shè)計(jì)出的柵格模型更符合每個(gè)城市的特點(diǎn)，為無人機(jī)規(guī)劃出精細(xì)的航路的同時(shí)，也不會(huì)為搜索算法帶來太多的負(fù)擔(dān)。

2　基于雙向A*搜索算法的無人機(jī)航跡規(guī)劃

2.1任務(wù)條件描述

城市環(huán)境信息完全已知，所以問題可以簡化為在靜態(tài)環(huán)境中尋找從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)無障礙路徑的經(jīng)典全局路徑規(guī)劃問題。

根據(jù)已知障礙分布與地形，對(duì)無人機(jī)從起始點(diǎn)到目標(biāo)點(diǎn)之間的距離進(jìn)行航路預(yù)規(guī)劃，針對(duì)航路規(guī)劃要求日趨快速精確的特點(diǎn)，傳統(tǒng)的A*搜索算法已經(jīng)不能滿足性能要求，所以需要針對(duì)傳統(tǒng)的A*搜索算法進(jìn)行改進(jìn)，提高其航路規(guī)劃的效率。

2.2雙向A*搜索算法

所謂雙向A*搜索算法，指的就是搜索沿著正反兩個(gè)方向同時(shí)進(jìn)行，如圖2所示：

圖2　雙向搜索示意圖

正向搜索是指從起始點(diǎn)方向向目標(biāo)點(diǎn)方向搜索，而反向搜索則是指從目標(biāo)點(diǎn)方向向起始點(diǎn)方向進(jìn)行搜索。在搜索過程中，要把另外一個(gè)方向上已經(jīng)產(chǎn)生的節(jié)點(diǎn)作為現(xiàn)節(jié)點(diǎn)的目標(biāo)節(jié)點(diǎn)。如圖，在正向搜索過程中，將反向搜索的當(dāng)前點(diǎn)G2作為正向搜索的目標(biāo)節(jié)點(diǎn)，相對(duì)的，在反向搜索過程中，將正向搜索的當(dāng)前節(jié)點(diǎn)S2作為反向搜索的目標(biāo)節(jié)點(diǎn)。正向和反向搜索過程同時(shí)進(jìn)行。

當(dāng)正向和反向搜索同時(shí)將一個(gè)節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)(如圖節(jié)點(diǎn)為Sn或Gn)，且該節(jié)點(diǎn)滿足兩個(gè)方向搜索的約束條件，則搜索結(jié)束。

2.3對(duì)雙向A*搜索算法的改進(jìn)

在雙向啟發(fā)式A*算法中，有兩個(gè)條件是必不可少的，一個(gè)是算法停止搜索的條件，另一個(gè)是正向搜索和反向搜索之間轉(zhuǎn)換的條件。

在算法終止的條件中，如上圖所示，當(dāng)正向搜索和反向搜索的目標(biāo)節(jié)點(diǎn)為同一個(gè)節(jié)點(diǎn)時(shí)，且該節(jié)點(diǎn)滿足兩個(gè)方向搜索的約束條件，則路徑搜索成功，搜索算法終止。

另一種情況(如圖3所示)，當(dāng)正向搜索和反向搜索的目標(biāo)節(jié)點(diǎn)沒有相遇，而是分別搜索到了自己方向上的目標(biāo)節(jié)點(diǎn)，或者兩個(gè)方向在搜索過程中一直在更新目標(biāo)節(jié)點(diǎn)，而目標(biāo)節(jié)點(diǎn)一直沒有相遇陷入循環(huán)的情況下，將終止搜索算法，作為搜索失敗處理，在這種情況下，只選擇正向搜索出來的路徑選為全局路徑。

圖3　特殊情況算法搜索示意圖

理想的條件下，正向搜索和反向搜索會(huì)在起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)連線的中心點(diǎn)相遇，這樣在理想狀態(tài)下，可以減少一半的搜索空間(如圖4所示)，但是在實(shí)際的無人機(jī)飛行環(huán)境中，會(huì)有不同的障礙阻擋在航路之中，正向搜索和反向搜索往往不會(huì)在起始點(diǎn)和目標(biāo)點(diǎn)的中心相遇，而在極端情況下，可能會(huì)比單向A*搜索的代價(jià)還要大，所以要保證搜索在中間部分相遇，而避免在邊緣區(qū)域相遇。

圖4　雙向搜索相遇區(qū)域示意圖

傳統(tǒng)的雙向A*搜索算法在搜索過程中，正向搜索和反向搜索是交替進(jìn)行的。也就是說，先進(jìn)行一次正向搜索，當(dāng)正向搜索搜索到一個(gè)代價(jià)最小的節(jié)點(diǎn)時(shí)，再進(jìn)行反向搜索，且反向搜索將正向搜索到的當(dāng)前最佳節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)進(jìn)行搜索。

這里對(duì)正向搜索與反向搜索交替進(jìn)行的機(jī)制進(jìn)行改進(jìn)，改進(jìn)的目的是使雙向A*算法的正向搜索和反向搜索同時(shí)進(jìn)行，提出同步雙向A*搜索算法的思想。

在改進(jìn)之后，因?yàn)檎蚝头聪蛩阉魇峭竭M(jìn)行的(如圖5所示)，所以兩個(gè)方向上的搜索就不能將對(duì)向的當(dāng)前節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，為了保證算法在搜索過程中保持同步且在正向與反向搜索的中心區(qū)域相遇，規(guī)定將兩個(gè)方向上當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)作為兩個(gè)方向搜索的目標(biāo)節(jié)點(diǎn)。如圖2所示，在進(jìn)行搜索時(shí)，正向搜索的當(dāng)前節(jié)點(diǎn)S2是以反向搜索中節(jié)點(diǎn)G1作為目標(biāo)節(jié)點(diǎn)搜索得來的，反向搜索的當(dāng)前節(jié)點(diǎn)G2則是以正向搜索中節(jié)點(diǎn)S1作為目標(biāo)節(jié)點(diǎn)搜索得來的，這樣可以保證兩個(gè)方向上搜索的目標(biāo)節(jié)點(diǎn)同時(shí)更新，即保證了正反兩個(gè)方向的搜索可同時(shí)進(jìn)行。

具體步驟如下：

Step1：將兩個(gè)方向上的起始節(jié)點(diǎn)分別放入OPEN0表和OPEN1表。

Step2：判斷OPEN0表和OPEN1表是否為空，若為空，則搜索失敗，退出。

圖5　同步雙向A*搜索過程示意圖

Step3：移出OPEN0表和OPEN1表中的第一個(gè)節(jié)點(diǎn)，放入CLOSE0表和CLOSE1表中。

Step4：若當(dāng)前節(jié)點(diǎn)的目標(biāo)節(jié)點(diǎn)為相對(duì)方向上搜索的當(dāng)前節(jié)點(diǎn)，則搜索成功，退出。

Step5：若OPEN表中的當(dāng)前節(jié)點(diǎn)不能再擴(kuò)展，轉(zhuǎn)Step2。

Step6：擴(kuò)展當(dāng)前節(jié)點(diǎn)鄰域上的子節(jié)點(diǎn)，對(duì)比子節(jié)點(diǎn)的代價(jià)函數(shù)值，確定下一個(gè)擴(kuò)展節(jié)點(diǎn)，將余下的待選節(jié)點(diǎn)放入OPEN0表和OPEN1表中，轉(zhuǎn)Step2。

3　代價(jià)評(píng)估函數(shù)

在航路規(guī)劃的過程中，代價(jià)評(píng)估函數(shù)是其中的核心問題也是難點(diǎn)，一個(gè)好的代價(jià)評(píng)估函數(shù)應(yīng)該具有以下特點(diǎn)：計(jì)算簡單，不能有太大的計(jì)算量，否則會(huì)影響算法的性能；直觀明了，對(duì)航跡中代價(jià)評(píng)估客觀真實(shí)，函數(shù)中各個(gè)變量意義明確。

該算法的代價(jià)評(píng)估函數(shù)如式(1)所示：

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

(1)

公式中：f(n)為待選節(jié)點(diǎn)的評(píng)價(jià)函數(shù)，g(n)為從起始點(diǎn)到節(jié)點(diǎn)n的代價(jià)，h(n)為從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的啟發(fā)式估值，h(n)的設(shè)計(jì)對(duì)A*算法能否找到可行解以及算法的求解速度和性能起到了決定性的作用。一個(gè)好的h(n)應(yīng)該滿足小于并且盡量接近于真實(shí)值。

因?yàn)樵诔鞘兄?，無人機(jī)的飛行環(huán)境相對(duì)穩(wěn)定，只需要避開建筑物和一些特殊敏感區(qū)域如軍事部隊(duì)駐地上空和機(jī)場周邊空域即可。這里選取歐幾里得距離作為評(píng)價(jià)函數(shù)的計(jì)算方法，即起點(diǎn)到任意節(jié)點(diǎn)的代價(jià)值為其父節(jié)點(diǎn)的代價(jià)值加上該節(jié)點(diǎn)與父節(jié)點(diǎn)之間的距離，任意節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的啟發(fā)式估值為該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的直線距離。

用n表示待選節(jié)點(diǎn)，m表示其父節(jié)點(diǎn)，即當(dāng)前正在擴(kuò)展的節(jié)點(diǎn)，g(n)和h(n)的計(jì)算分別如式(2)和式(3)所示：

(2)

(3)

式中，g(m)為從起始點(diǎn)到節(jié)點(diǎn)m的代價(jià)值，nx、ny為待選節(jié)點(diǎn)的坐標(biāo)值，mx、my為當(dāng)前節(jié)點(diǎn)的坐標(biāo)值，goalx、goaly為目標(biāo)節(jié)點(diǎn)的坐標(biāo)值。

反向搜索中采用與正向搜索相同的代價(jià)評(píng)估函數(shù)。在兩個(gè)方向上應(yīng)用相同的代價(jià)評(píng)估函數(shù)，確保正反兩個(gè)方向上的搜索效率相同，使兩個(gè)方向同時(shí)更新目標(biāo)節(jié)點(diǎn)，保證正向搜索和反向搜索可以同步進(jìn)行。

4　結(jié)果分析

采用同步雙向A*搜索算法對(duì)無人機(jī)進(jìn)行航路規(guī)劃仿真，并與單向A*搜索算法和傳統(tǒng)雙向A*搜索算法進(jìn)行對(duì)比。實(shí)驗(yàn)計(jì)算機(jī)為Windows7 x64操作系統(tǒng)，處理器主頻為3.10 GHz。

實(shí)驗(yàn)過程中，引入障礙物、建筑物以及禁飛空域，且障礙物的位置可以在每次規(guī)劃之前即時(shí)更新。

以下是同步雙向A*搜索算法進(jìn)行航路搜索的程序運(yùn)行截圖：

圖6　搜索案例一

圖7　搜索案例二

其中黑色三角形代表起始點(diǎn)，黑色圓形代表目標(biāo)點(diǎn)，灰色陰影部分代表障礙物。圖6和圖7說明，程序在不同的城市環(huán)境下可以為無人機(jī)快速規(guī)劃出航路，且航路可飛。

圖8說明在起始點(diǎn)與目標(biāo)點(diǎn)之間障礙物對(duì)稱的情況下，同步雙向A*算法也可為無人機(jī)規(guī)劃出代價(jià)較小航路，并沒有陷入循環(huán)狀態(tài)，且規(guī)劃出的航路可飛。

表1是單向A*搜索算法、雙向A*搜索算法與同步雙向A*搜索算法在相同條件下對(duì)航路進(jìn)行規(guī)劃的用時(shí)和航路距離的對(duì)比。距離的單位為柵格，航路長度62表示無人機(jī)從起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過了62個(gè)柵格，時(shí)間單位為秒。起始點(diǎn)分別設(shè)定在柵格環(huán)境的左上角、右下角和中間位置，對(duì)應(yīng)的目標(biāo)點(diǎn)分別選在起始點(diǎn)的上方、兩側(cè)與對(duì)角位置。當(dāng)目標(biāo)點(diǎn)更換時(shí)，障礙物保持不變的情況下，對(duì)三種算法進(jìn)行橫向比較。從表中的數(shù)據(jù)可以看出，在航路規(guī)劃的距離上，三種算法是相同的，說明雙向A*搜索算法可以得到與單向A*搜索算法相同的最優(yōu)解。而在航路規(guī)劃的時(shí)間上，雙向A*搜索算法則比傳統(tǒng)的單向A*搜索算法縮短了近一半的時(shí)間，而改進(jìn)后的同步雙向A*搜索算法，對(duì)比傳統(tǒng)的雙向A*搜索算法在航路規(guī)劃的用時(shí)上又有所縮短，這表明在雙向搜索中，正向搜索與反向搜索同步進(jìn)行，可以提高算法的搜索效率。

表1　數(shù)據(jù)統(tǒng)計(jì)表

5　總結(jié)

本文提出的同步雙向A*搜索算法，可以為無人機(jī)在城市環(huán)境下規(guī)劃出航路，在保證航路最優(yōu)且可飛的情況下，較大地提升了航路規(guī)劃的速度。下一步的研究方向是把該算法應(yīng)用在三維環(huán)境中并測(cè)試其性能。

[1]SZCZERBA ROBERT J.Robust algorithm for real-time route planning[J].IEEE Transaction son Aerospace and Electronic Systems(S0018-9251),2000,36(3):869-878.

[2]何雨楓,曾慶化,王云舒,等.室內(nèi)微型飛行器實(shí)時(shí)路徑規(guī)劃算法研究[J].電子測(cè)量技術(shù),2014,2:23-27.

[3]LAVALLE SM,KUFFNER J J.Rapidly-exploring random trees:progress and prospects[C].Proceedings of the Fourth Workshop on the Algorithmic Foundations of Robotics.Dartmauth，MA,2000:293-308.

[4]黃文剛，張 怡，姜文毅，等.基于改進(jìn)稀疏A*算法的無人機(jī)航路規(guī)劃[J].遙測(cè)遙控,2012,33(6):12-16.

[5]WANG N,GU X,CHEN J,et al.A hybrid neural network method for UAV attack route integrated planning[C].The 6th International Symposium on Neural Networks,Wuhan,2009,5553:226-235.

[6]GENG Q,ZHAO Z.A kind of route planning method for UAV based on improved PSO algorithm[C].The 25th Chinese Control and Decision Conference Guiyang,2013:2328-2331.

[7]陳謀，肖健，姜長生.基于改進(jìn)蟻群算法的無人機(jī)三維航路規(guī)劃[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2008,38(4):991-995.

[8]RODRIGUEZ S,TANG X,LIEN J,et al.An obstacle-based rapidly-exploring random tree[C].The 2006 IEEE International Conference on Robotics and Automation,ICRA 2006,2006,Orlando,FL,United states.

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

[10]ZHANG B,MAO Z,LIU W,et al.Geometric reinforcement learning for path planning of UAVs[J].Journal of Intelligent and Robotic Systems:Theory and Applications,77(2):391-409.

[11]郝振國,王玉玫.雙向A*算法在軍事路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(29):246-248.

[12]BAOCHANG ZHANG,WANQUAN LIU,ZHILI MAO,et al.Cooperative and geometric learning algorithm (CGLA) for path planning of UAVs with limited information[J].Automatica,2014,50(3):809-820.

[13]KUWATA Y,TEO J,KARAMAN S,et al.Motion planning in complex environments using closed-loop prediction[C].The AIAA Guidance,Navigation and Control Conference and Exhibit,Honolulu,HI,United states,2008.

[14]張彪,曹其新,王雯珊.使用三維柵格地圖的移動(dòng)機(jī)器人路徑規(guī)劃[J].西安交通大學(xué)學(xué)報(bào),2013,47(10):57-61.

[15]武雪玲,李清泉,任福.基于分層分塊數(shù)據(jù)組織的雙向A*算法[J].測(cè)繪信息與工程,2006,31(6):1-3.

[16]董文洪,易波,栗飛.無人機(jī)航路規(guī)劃環(huán)境模型研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(15):236-239.

(責(zé)任編輯：劉劃英文審校：趙亮)

Urban UAV route planning based on bidirectional A*algorithm

LIN Na,LI Tian-xiao

(College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

The bidirectional A*algorithm was applied in the urban UAV route planning.Compared with the traditional A*search algorithm,the synchronous bidirectional A*search algorithm,the improved bidirectional A*search algorithm,has higher search efficiency,and saves great time of route planning.Experiment was built to realize the forward search and the backward search working on the same time by using the grid method to build the environment model for UAVs.It was fully considered that the urban environment to determine the grid size while building the environment model.Experimental result shows that the synchronous bidirectional A*algorithm is more efficient since it can make the route planning faster for UAVs and the route flyable.

unmanned aerial vehicle (UAV);bidirectional A*;grid;the urban environment;route planning

2015-10-28

遼寧省自然科學(xué)基金聯(lián)合基金(項(xiàng)目編號(hào):2015020008);遼寧省自然科學(xué)基金(項(xiàng)目編號(hào):20102175);遼寧省高等學(xué)校優(yōu)秀人才支持計(jì)劃(項(xiàng)目編號(hào)：LJQ2012011)。

林娜(1977-)，女，遼寧沈陽人，副教授，主要研究方向：無人機(jī)航路規(guī)劃，智能交通，E-mail：lin_na2000@163.com。

信息科學(xué)與工程

2095-1248(2016)04-0055-06

TP391.9

A

10.3969/j.issn.2095-1248.2016.04.010