林　娜，李天嘯

(沈陽航空航天大學 計算機學院，沈陽 110136)

?

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

林娜，李天嘯

(沈陽航空航天大學 計算機學院，沈陽 110136)

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

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

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

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

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

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

1.1問題描述

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

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

1.2環(huán)境建模

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

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

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

對于旋翼無人機來說，由于其機動性很強，轉(zhuǎn)彎不受轉(zhuǎn)彎角度和轉(zhuǎn)彎半徑的限制，所以以旋翼無人機所在柵格為中心，周圍的上下左右8個柵格均為其可機動柵格，如圖1所示。

圖1　旋翼無人機可機動柵格示意圖

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

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

2.1任務(wù)條件描述

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

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

2.2雙向A*搜索算法

所謂雙向A*搜索算法，指的就是搜索沿著正反兩個方向同時進行，如圖2所示：

圖2　雙向搜索示意圖

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

當正向和反向搜索同時將一個節(jié)點作為目標節(jié)點(如圖節(jié)點為Sn或Gn)，且該節(jié)點滿足兩個方向搜索的約束條件，則搜索結(jié)束。

2.3對雙向A*搜索算法的改進

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

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

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

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

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

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

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

這里對正向搜索與反向搜索交替進行的機制進行改進，改進的目的是使雙向A*算法的正向搜索和反向搜索同時進行，提出同步雙向A*搜索算法的思想。

在改進之后，因為正向和反向搜索是同步進行的(如圖5所示)，所以兩個方向上的搜索就不能將對向的當前節(jié)點作為目標節(jié)點，為了保證算法在搜索過程中保持同步且在正向與反向搜索的中心區(qū)域相遇，規(guī)定將兩個方向上當前節(jié)點的前一個節(jié)點作為兩個方向搜索的目標節(jié)點。如圖2所示，在進行搜索時，正向搜索的當前節(jié)點S2是以反向搜索中節(jié)點G1作為目標節(jié)點搜索得來的，反向搜索的當前節(jié)點G2則是以正向搜索中節(jié)點S1作為目標節(jié)點搜索得來的，這樣可以保證兩個方向上搜索的目標節(jié)點同時更新，即保證了正反兩個方向的搜索可同時進行。

具體步驟如下：

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

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

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

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

Step4：若當前節(jié)點的目標節(jié)點為相對方向上搜索的當前節(jié)點，則搜索成功，退出。

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

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

3　代價評估函數(shù)

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

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

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

(1)

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

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

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

(2)

(3)

式中，g(m)為從起始點到節(jié)點m的代價值，nx、ny為待選節(jié)點的坐標值，mx、my為當前節(jié)點的坐標值，goalx、goaly為目標節(jié)點的坐標值。

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

4　結(jié)果分析

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

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

以下是同步雙向A*搜索算法進行航路搜索的程序運行截圖：

圖6　搜索案例一

圖7　搜索案例二

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

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

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

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

5　總結(jié)

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

[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)微型飛行器實時路徑規(guī)劃算法研究[J].電子測量技術(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]黃文剛，張 怡，姜文毅，等.基于改進稀疏A*算法的無人機航路規(guī)劃[J].遙測遙控,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]陳謀，肖健，姜長生.基于改進蟻群算法的無人機三維航路規(guī)劃[J].吉林大學學報(工學版),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*算法的遠程導彈三維航跡規(guī)劃算法[J].北京理工大學學報,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].計算機工程與應(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]張彪,曹其新,王雯珊.使用三維柵格地圖的移動機器人路徑規(guī)劃[J].西安交通大學學報,2013,47(10):57-61.

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

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

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

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

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

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

信息科學與工程

2095-1248(2016)04-0055-06

TP391.9

A

10.3969/j.issn.2095-1248.2016.04.010