基于概略圖的航跡優(yōu)化的改進(jìn)A*算法研究*

陳韶千，董國(guó)才，唐同斌，張健楠，章 校，王 姣，劉士勛，喻 戈，張 翔

(西安現(xiàn)代控制技術(shù)研究所， 西安 710065)

0 引言

A*算法作為一種航跡優(yōu)化的有效手段，可在數(shù)字地圖中規(guī)劃出合適的航跡[1]，但是由于A*算法是啟發(fā)式的，因此無(wú)論怎么改進(jìn)，都無(wú)法改變啟發(fā)式算法遍歷節(jié)點(diǎn)隨搜索范圍和距離的增加而大幅度增加的事實(shí)[2-3]。離線優(yōu)化階段，為從根本上減少搜索點(diǎn)的個(gè)數(shù)，提出了概略圖法——先使用概略圖技術(shù)對(duì)數(shù)字地圖進(jìn)行預(yù)處理，然后再在狹窄通道等小范圍使用A*算法。

概略圖(Skeleton)也稱為路標(biāo)圖(Roadmap)[4-5]。地形的概略圖是將地形中的山谷、通路，進(jìn)行概略抽象，表示成一個(gè)由一維線段構(gòu)成的網(wǎng)絡(luò)圖，然后采用搜索算法在該網(wǎng)絡(luò)圖上進(jìn)行搜索。這樣，路徑優(yōu)化問(wèn)題被轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖的搜索問(wèn)題。概略圖必須表示出地形控件中的所有可能的路徑，否則就是不完全的，即可能丟失最優(yōu)解。

最終生成的地形概略圖是一個(gè)帶有加權(quán)系數(shù)和經(jīng)緯度信息的路標(biāo)圖，在圖中每個(gè)節(jié)點(diǎn)都是帶有經(jīng)緯度信息的可能航路點(diǎn)，點(diǎn)與點(diǎn)之間是具有加權(quán)系數(shù)的連線，連線的加權(quán)系數(shù)反映了這條通路的代價(jià)(包括：威脅代價(jià)、高度代價(jià)、航程代價(jià)、燃油代價(jià)、飛機(jī)縱向機(jī)動(dòng)性能等因素)，連線之間的夾角考慮了飛機(jī)的橫側(cè)向機(jī)動(dòng)約束。

1 立體聯(lián)通概略圖

要利用概略圖法進(jìn)行航跡優(yōu)化，先必須得到概略圖。下面簡(jiǎn)略介紹得到概略圖的過(guò)程。

高程數(shù)字地圖的梯度信息能夠一定程度上反映地形上的差異，遇到山脊的地形，數(shù)字高程信息梯度變化較大，而山谷處較為平緩，數(shù)字高程信息梯度變化不大?？梢韵葘?duì)地圖模擬給山谷灌水的預(yù)處理操作，通過(guò)灌水處理后，谷底平坦，梯度較小，能利用梯度識(shí)別出適合飛行的區(qū)域。然后通過(guò)設(shè)置閾值來(lái)分割梯度圖，分割處理后，各點(diǎn)值為0或1，得到對(duì)應(yīng)的二值圖。再根據(jù)地形信息，利用中軸變換提取相對(duì)平坦的山谷骨架，再通過(guò)骨架去毛和拼接生成概略圖。

現(xiàn)在先選取秦嶺俯視地圖的一部分作為例子，該地圖顯示的是西安市附近秦嶺的俯視圖。該圖是一個(gè)黑白的地形俯視圖，將要對(duì)該地圖進(jìn)行分析操作。在地圖上選了兩個(gè)點(diǎn)，一個(gè)作為出發(fā)點(diǎn)，另一個(gè)作為目標(biāo)點(diǎn)。從出發(fā)點(diǎn)飛機(jī)要飛過(guò)很多山地障礙才能到達(dá)目的地。先選取80 m高度，得到地圖80 m高度的橫切面,如圖1所示。白色的部分是山體，是不可穿過(guò)的，黑色的部分是空曠可以穿過(guò)的，兩個(gè)紅點(diǎn)分別為起點(diǎn)和終點(diǎn)。從地圖上可以看出，在相對(duì)地面高度為80 m的時(shí)候，無(wú)論飛機(jī)從哪里飛，都不能夠穿越障礙區(qū)域到達(dá)目的地，所以這個(gè)高度就是無(wú)法通過(guò)的，必須要提升飛行高度，繼續(xù)尋找可能的路徑。

圖1 高度為80 m處的橫切面

圖2 高度為100 m處的橫切面

將飛機(jī)的飛行高度提升到相對(duì)地面100 m，現(xiàn)在得到100 m高度的橫切面如圖2所示?？梢钥闯鲭S著高度的增加，白色區(qū)域有所減少，有的地方出現(xiàn)了黑色的缺口和通道。缺口的寬度假定為100 m，在缺口或通道寬度大于這個(gè)值的時(shí)候我們就可以認(rèn)為這個(gè)地方是飛機(jī)可以通過(guò)的。從地圖上可以看到這樣的缺口出現(xiàn)了，并且還不止一處。所以，飛機(jī)在100 m高的空域飛行，可以穿越障礙達(dá)到目的地。

現(xiàn)在對(duì)圖像進(jìn)行處理，作出腐蝕與膨脹操作，操作的目的是去除地圖上的毛刺，得出圖3。

圖3 膨脹處理之后的100 m高度橫切面

圖4 120 m高度橫切面

從圖3上看出，白色的山體“變胖”了，這個(gè)膨脹的多少可以假定為我們上面選定的那個(gè)寬度值10 m。從這里看到，有一些通道被堵死了，有一條卻被壓縮得很細(xì)。很細(xì)的通道表明飛機(jī)可以從這里飛過(guò)去。被堵死的通道因?yàn)椴荒軡M足飛機(jī)安全通過(guò)的需求，被排除在外，仍然存在的這條通路就是飛機(jī)可以選擇的航路。將這條航路用線段連接，也就是將地圖骨骼化，標(biāo)記出它的起點(diǎn)和終點(diǎn)。對(duì)每一條被找出的這種通道都做這樣的處理，于是就得到了上面提出的概略圖，即表示成一個(gè)由一維線段構(gòu)成的網(wǎng)絡(luò)圖。每一個(gè)通道的起點(diǎn)和終點(diǎn)都被稱作關(guān)鍵點(diǎn)，這些點(diǎn)有經(jīng)緯度信息。

繼續(xù)改變高度，達(dá)到了120 m，這樣得到120 m的橫切面，如圖4所示。如圖可見(jiàn)，現(xiàn)在地圖上只有零星的障礙了，再用上述辦法得出高度為120 m時(shí)的最優(yōu)航路。直到高度提升到150 m以上，白色的障礙物消失，全部都是自由空域。

綜上所述，整個(gè)方案的關(guān)鍵就在如何尋找關(guān)鍵點(diǎn)并畫出概略圖。這樣做的目的是為了大大減小需要使用航跡搜索算法進(jìn)行航路優(yōu)化的地區(qū)的范圍，從整個(gè)地圖都需要使用航跡優(yōu)化算法變成了只要在幾個(gè)狹窄通道或者是缺口處才要使用。而這需要用到地理信息系統(tǒng)(GIS)知識(shí)中的地圖自動(dòng)抽象技術(shù)。該技術(shù)將一定高度所截得的地圖進(jìn)行處理，將障礙物進(jìn)行膨脹得到飛機(jī)實(shí)際能夠通過(guò)的通道和缺口的位置。

概略圖法的思路總結(jié)如下：將在海拔60 m到該處地圖最高山峰的高度范圍內(nèi)的數(shù)字地圖進(jìn)行間隔為10 m的等高切割，每層都得到一個(gè)固定在該高度下的數(shù)字地形的橫截面。規(guī)定在山體缺口最窄處的中點(diǎn)為圓心距離兩側(cè)山體都為100 m處為一處狹窄通道，從缺口向兩側(cè)開(kāi)闊地帶延伸。隨著地形越來(lái)越開(kāi)闊，跟山體兩側(cè)都相切的圓的半徑也在增大。取半徑為200 m的圓的圓心為關(guān)鍵點(diǎn)。因?yàn)樵陂_(kāi)闊地帶基本不需要避障和算法，所以概略圖法的最主要的目的就是找出狹窄通道。

由于算法的主要目的就是找出關(guān)鍵點(diǎn)和狹窄通道，僅在該處使用航跡優(yōu)化搜索算法進(jìn)行優(yōu)化，從而縮短離線優(yōu)化所需要的時(shí)間。這里的關(guān)鍵點(diǎn)其實(shí)都可以稱做狹窄通道。下面來(lái)說(shuō)明如何判斷某處是否可以被稱為狹窄通道。

圖5 典型狹窄通道示意圖

假設(shè)飛行器允許通過(guò)的通道最窄處圓的半徑為100 m。為減少滿足這個(gè)條件的點(diǎn)的數(shù)量，需要過(guò)濾掉無(wú)效關(guān)鍵點(diǎn)，所以同時(shí)規(guī)定，狹窄通道的最寬的地方圓的半徑為200 m。圖5展示的是一種典型的狹窄通道尋找關(guān)鍵點(diǎn)的情況。下面兩個(gè)以點(diǎn)A為圓心的同心圓一個(gè)是100 m半徑，另一個(gè)是200 m半徑，上面那個(gè)圓半徑是100 m。兩側(cè)的陰影部分圓弧表示山體部分，虛線圓弧是虛擬的向外擴(kuò)張了100 m的山體。從圖5可見(jiàn)，因?yàn)锳點(diǎn)到C點(diǎn)之間這個(gè)狹窄通道中最窄處的B點(diǎn)處寬度為半徑100 m，所以從點(diǎn)A到點(diǎn)C之間總有點(diǎn)滿足到山體的距離大于100 m小于200 m的條件，可以取兩個(gè)端點(diǎn)A和C為此處狹窄通道內(nèi)關(guān)鍵點(diǎn)。因?yàn)閷脮r(shí)要在此處進(jìn)行A*的優(yōu)化，在A和C點(diǎn)之間使用算法，在該處狹窄通道之外就可以直接與其他狹窄通道的關(guān)鍵點(diǎn)或者起始點(diǎn)/目標(biāo)點(diǎn)鏈接。若是最窄處的圓半徑大于等于100 m，則該高度處滿足飛機(jī)安全通過(guò)的要求，若小于100 m，則該高度處不能滿足要求。從圖上可以清楚的知道，既然最窄處都滿足要求，那其至少還存在分布于兩側(cè)的同心圓，如上圖中的A和C。這樣，搜索算法到這里需要遍歷的點(diǎn)就從一堆變成了兩個(gè)。

因?yàn)樵诘匦纹教沟钠皆貐^(qū)上空飛行，一般可以直接采用盡量貼地的直線飛行，無(wú)需使用航跡優(yōu)化軟件來(lái)提前優(yōu)化路徑，所以在常用的低空突防航跡優(yōu)化的環(huán)境中，飛機(jī)都是在山區(qū)的環(huán)境中執(zhí)行任務(wù)。山體一般來(lái)說(shuō)都是上小下大，同樣的地區(qū)，空域的海拔越高，障礙物就越稀少。基于山體的這個(gè)特征，只要在某山谷的較低海拔處飛機(jī)可以安全通過(guò)，在同一個(gè)經(jīng)緯度的較高海拔處也一定可以讓飛機(jī)安全通過(guò)。所以，在立體地形中選取關(guān)鍵點(diǎn)，還是像上面一樣在不同的高度對(duì)數(shù)字地形進(jìn)行橫切，在這些橫切的圖形中尋找關(guān)鍵點(diǎn)，并把所有高度層找到的所有關(guān)鍵點(diǎn)放在一起跟起始點(diǎn)和終點(diǎn)相連，比較代價(jià)，選擇代價(jià)最小的路線。為了確保能夠盡量降低飛行器的飛行高度，只選取最窄處圓半徑恰好為100 m的通道，這個(gè)高度的狹窄通道的關(guān)鍵點(diǎn)就作為整個(gè)立體地形的一處關(guān)鍵點(diǎn)。這樣選出來(lái)的關(guān)鍵點(diǎn)是同一處狹窄通道的海拔最低的關(guān)鍵點(diǎn)，在滿足飛機(jī)安全通過(guò)需要的前提下同時(shí)又能滿足低空突防盡量降低飛行高度的要求。

2 基于概略圖的航跡優(yōu)化算法

文中基于概略圖的航跡優(yōu)化的具體做法是：

第一步:讀取數(shù)字地圖，將其以10 m為高度間隔，從海拔60 m到海拔4 500 m分割成不同高度的地圖橫切面；

第二步:在這些橫切面里面分別尋找關(guān)鍵點(diǎn)，并將這些關(guān)鍵點(diǎn)放在同一張數(shù)字地形地圖里形成立體概略圖；

第三步:連接起始點(diǎn)、目標(biāo)點(diǎn)和這些關(guān)鍵點(diǎn)，形成多條航路，計(jì)算這些航路的代價(jià)，選擇其中代價(jià)最低的那一條作為大概航路；

第四步:對(duì)這條航路中的狹窄通道部分使用改進(jìn)型稀疏A*算法得到最終的優(yōu)化航跡。

3 離線仿真結(jié)果對(duì)比

為了驗(yàn)證立體聯(lián)通概略圖的實(shí)際作用效能，將在同一數(shù)字地圖的同一部位，在起始點(diǎn)和預(yù)設(shè)各目標(biāo)點(diǎn)坐標(biāo)相同，約束條件也相同的情況下，分別運(yùn)用未經(jīng)修改的啟發(fā)式A*算法、改進(jìn)的稀疏A*算法和立體聯(lián)通概略圖法進(jìn)行航跡優(yōu)化，將得到的路線和搜索時(shí)間進(jìn)行一個(gè)對(duì)比。由于距離遠(yuǎn)，為更清楚的對(duì)比各情況的結(jié)果，選取含有起始點(diǎn)、大量威脅點(diǎn)和復(fù)雜地形的這部分的航跡優(yōu)化結(jié)果。圖中紅色的線是航跡的一些預(yù)先設(shè)定的必經(jīng)節(jié)點(diǎn)之間的連線。這里顯示出的5個(gè)節(jié)點(diǎn)緯度和經(jīng)度坐標(biāo)分別為(34.20°，108.80°)、(34.20°，108.38°)、(34.08°，108.20°)、(33.70°，107.02°)、(33.20°，106.90°)。3個(gè)大小不一的紅褐色圓為威脅區(qū)域，其坐標(biāo)、高度和作用范圍為(34.21°, 108.60°, -1 000 m, 10 000 m)、(33.80°, 108.80°, -1 000 m, 40 000 m)、(33.80°, 107.90°, -1 000 m, 30 000 m)。此時(shí)視威脅為無(wú)限高山峰，所以威脅中心高度沒(méi)有意義。因此，高度選取-1 000 m以代表這是一個(gè)沒(méi)有實(shí)際意義的高度。

1)未經(jīng)修改的啟發(fā)式A*算法

使用未經(jīng)修改的啟發(fā)式A*算法，整個(gè)算法完成優(yōu)化用時(shí)27 min 19 s，得到的優(yōu)化結(jié)果如圖6所示。

圖6 未加修改的啟發(fā)式A*算法優(yōu)化

2)立體聯(lián)通概略圖法

采用立體連通概略圖和改進(jìn)的稀疏A*算法相結(jié)合的方式，選用的參數(shù)和改進(jìn)的稀疏A*算法相同時(shí)，搜索時(shí)間為7 min 26 s，得到的優(yōu)化結(jié)果如圖7所示。

圖7 改進(jìn)的A*算法相結(jié)合的優(yōu)化

4 結(jié)論

綜上所述，隨著算法的改進(jìn)和概略圖技術(shù)的應(yīng)用，離線優(yōu)化所需的時(shí)間被有效縮短，優(yōu)化時(shí)間從27 min多鐘縮減到7 min左右。雖然每次的路徑結(jié)果不盡相同，但是優(yōu)化的路徑都能滿足飛行器各項(xiàng)物理約束限制、飛行安全和執(zhí)行任務(wù)的需要。由此可見(jiàn)，概略圖技術(shù)和改進(jìn)的稀疏A*算法相結(jié)合之后相比于一般的航跡優(yōu)化算法搜索的效率大大提高。