基于改進(jìn)A*算法的飛行器航跡規(guī)劃

秦鈺彧，夏豐領(lǐng)，黃國勇，2

（1.昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650504；2.昆明理工大學(xué) 民航與航空學(xué)院，云南 昆明 650504）

0 引言

飛行器航跡規(guī)劃是指綜合考慮飛行器機(jī)動性能、突防概率、碰地概率及飛行時(shí)間等約束因素，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或可行的飛行軌跡[1]。航跡規(guī)劃問題作為一個(gè)復(fù)雜的優(yōu)化問題，需要高效的算法來進(jìn)行求解。但隨著問題復(fù)雜度的增加，傳統(tǒng)算法往往存在過快陷入局部最優(yōu)解、迭代過慢等問題[2]。傳統(tǒng)的A*算法雖然是基于靜態(tài)圖最有效的直接搜索算法，但在規(guī)劃區(qū)域柵格化后，節(jié)點(diǎn)擴(kuò)展只限于柵格線的交叉點(diǎn)，存在無效轉(zhuǎn)折，因此路徑長度不是最短，實(shí)際規(guī)劃出的是次優(yōu)路徑。近些年，一些新興的群智能元啟發(fā)式算法相繼被提出，如灰狼算法（Grey Wolf Optimizer，GWO）、粒子群算法及遺傳算法等。RAM 等[3]將GWO 算法的性能與蟻群算法（Indicator Based Ant，IBA）、粒子群算法（Particle Swarm Optimization，PSO）、鯨魚算法（Whale Optimization Algorithm，WOA）以及正余弦算法（Sine Cosine Algorithm，SCA）等啟發(fā)式算法進(jìn)行了比較，在軌跡規(guī)劃中，GWO 算法的性能比其他啟發(fā)式算法更好。魏燕明等[4]采用灰狼優(yōu)化算法對軍用運(yùn)輸機(jī)進(jìn)行航路規(guī)劃，并與Dijkstra 算法和Floyd 算法進(jìn)行對比，證明了GWO 算法能很好地完成航路規(guī)劃的求解，但未對避障規(guī)劃能力進(jìn)行深入研究。雖然灰狼優(yōu)化算法具有控制參數(shù)少、能在一定程度上避免陷入局部最優(yōu)等優(yōu)點(diǎn)，但是灰狼優(yōu)化算法初始化時(shí)也存在問題：隨機(jī)初始化個(gè)體后生成的航點(diǎn)雜亂無序，造成個(gè)體的適應(yīng)度比較低，更新策略不靈活。TOO 等[5]提出了二進(jìn)制灰狼算法（Binary Grey Wolf Optimizer，BGWO），優(yōu)化了灰狼算法的搜索方法，使更新策略更加靈活。針對智能算法的初始值多采用隨機(jī)生成方式，導(dǎo)致算法的收斂速度降低、算法運(yùn)行時(shí)間較長的問題，實(shí)際應(yīng)用中，將經(jīng)典算法與智能算法進(jìn)行融合形成融合算法，取得較好的效果以及得到更優(yōu)解的同時(shí)，能加速算法收斂。黃辰等[6]通過使用A*算法取代蟻群算法的信息素隨機(jī)初始化過程，增加了蟻群算法的穩(wěn)定性；曹建秋等[7]提出了一種基于A*初始化的變異灰狼優(yōu)化算法解決無人機(jī)任務(wù)規(guī)劃問題，但狼群初始化后只能找到無威脅約束域下的可行解，需配合修正變異來進(jìn)一步優(yōu)化。針對A*算法節(jié)點(diǎn)擴(kuò)展時(shí)存在的局限性，Theta*算法[8]在A*算法的基礎(chǔ)上加入了可視化檢查機(jī)制，使得轉(zhuǎn)折角度更豐富，但頻繁可視化檢查會帶來難以忽視的計(jì)算成本，因此總的搜索效率會因地圖復(fù)雜而降低；而張帥等[9]采用圓形節(jié)點(diǎn)擴(kuò)展方法，使節(jié)點(diǎn)實(shí)現(xiàn)變方向和變步長形式擴(kuò)展，但隨著規(guī)劃精細(xì)化，搜索效率大幅度降低。

A*算法作為全局搜索算法，可以把握大局，確保能夠找到可行的航線。結(jié)合二進(jìn)制灰狼算法，可打破A*算法節(jié)點(diǎn)擴(kuò)展時(shí)帶來的轉(zhuǎn)彎角度局限，并通過縮減航跡點(diǎn)來縮短航程。本文提出了一種基于改進(jìn)A*（A*-BGWO）算法的飛行器航跡規(guī)劃方法，通過A*算法在離散化的地圖上求取一個(gè)較優(yōu)的初始矩陣，隨后通過二進(jìn)制灰狼優(yōu)化算法構(gòu)建和更新種群，得到最優(yōu)航跡點(diǎn)集合。該算法規(guī)劃出的航跡能在準(zhǔn)確避開多個(gè)障礙物的同時(shí)，減少多余航跡點(diǎn)從而最縮短航程，優(yōu)化轉(zhuǎn)彎角度。

1 環(huán)境模型

本文首先對三維地理環(huán)境進(jìn)行離散化處理。通過對規(guī)劃空間進(jìn)行柵格劃分，將規(guī)劃空間劃分為大小相等、彼此相鄰的立方體，在規(guī)劃空間搜索多個(gè)有序的飛行航跡點(diǎn)，從起點(diǎn)依次連接到目標(biāo)點(diǎn)，形成航跡。

規(guī)劃時(shí)，本文將威脅區(qū)及其領(lǐng)空視為禁飛區(qū)，規(guī)劃為統(tǒng)一的威脅模型，并用等效地形來近似模擬。由于還需考慮飛行器與實(shí)際威脅區(qū)域之間的安全距離以及飛行器轉(zhuǎn)彎半徑，因此在柵格地圖上對威脅區(qū)進(jìn)行膨脹處理，擴(kuò)大威脅模型，并允許搜索的航跡通過障礙柵格的頂點(diǎn)。

地圖離散化后，該矩陣的第i行j列元素代表該精度下該節(jié)點(diǎn)的海拔高度hij，設(shè)該規(guī)劃段的最小飛行高度為hmin，于是設(shè)置hmin為安全海拔。威脅區(qū)的威脅模型高度設(shè)置為高于安全海拔的數(shù)值，威脅較小的安全區(qū)域作為地形模型，該區(qū)域高度設(shè)置為安全海拔以下的數(shù)值，海拔越高，模型顏色設(shè)置越淺。

2 評價(jià)函數(shù)

為使飛行器能避開威脅區(qū)的同時(shí)，避免頻繁調(diào)整航向和姿態(tài)，需要達(dá)到的效果為：在無威脅的自由空間，航跡搜索的航跡點(diǎn)間隔較大，避免無效轉(zhuǎn)折，縮短航程；在接近威脅區(qū)域時(shí)，確保飛行器飛行時(shí)能成功規(guī)避威脅的同時(shí)，轉(zhuǎn)彎角度不易過大，避免頻繁轉(zhuǎn)向。因此，本文將飛行時(shí)間代價(jià)、威脅代價(jià)及轉(zhuǎn)彎角度代價(jià)進(jìn)行線性加權(quán)，其和作為對航跡優(yōu)劣的評價(jià)函數(shù)及后續(xù)改進(jìn)二進(jìn)制灰狼算法的適應(yīng)度函數(shù)。

2.1 航程代價(jià)

航程是評價(jià)航跡優(yōu)劣的重要指標(biāo)之一。航程代價(jià)函數(shù)表示為：

式中：Li為航程長度，(xi+1,yi+1,zi+1)和(xi,yi,zi)為對應(yīng)相鄰航點(diǎn)的坐標(biāo)。

2.2 威脅代價(jià)

避障是飛行器飛行任務(wù)中極其重要的一個(gè)環(huán)節(jié)，因此本文加入了威脅代價(jià)作為評價(jià)指標(biāo)。為簡化規(guī)劃問題，本文在柵格規(guī)劃環(huán)境中，將威脅區(qū)及其領(lǐng)空都設(shè)為禁飛區(qū)，而威脅較小的地形模型允許飛行器通過，于是通過路徑線段與威脅源的距離來確定威脅代價(jià)，設(shè)(xoj,yoj,0)為第j個(gè)禁飛區(qū)的坐標(biāo)，roj為第j個(gè)禁飛區(qū)的邊長，則威脅代價(jià)函數(shù)為：

式中：Sr為飛行器與禁飛區(qū)的最小歐氏距離，

2.3 轉(zhuǎn)彎角代價(jià)

考慮到飛行器存在機(jī)動過載約束和航跡傾角/偏角約束等，航跡傾角、偏角約束限制了飛行器的飛行軌跡彎曲程度，使得轉(zhuǎn)彎角度不易過小，本文加入了轉(zhuǎn)彎角代價(jià)函數(shù)：

式中：(xi+1,yi+1)，(xi+2,yi+2)以及(xi,yi)對應(yīng)于相鄰航點(diǎn)的坐標(biāo)，根據(jù)三角形特性，(xi+2,yi+2)與(xi,yi)連線越長，轉(zhuǎn)彎角度越大。

綜上，總的評價(jià)函數(shù)為：

3 規(guī)劃算法

3.1 A*算法存在的缺陷及改進(jìn)

在邊長為l的柵格環(huán)境下，A*算法節(jié)點(diǎn)擴(kuò)展時(shí)僅可以向與當(dāng)前節(jié)點(diǎn)相鄰的8 個(gè)方向擴(kuò)展，步長限制為l，，導(dǎo)致規(guī)劃得到局部航跡時(shí)存在無效轉(zhuǎn)折，如圖1 所示，最終導(dǎo)致規(guī)劃結(jié)果并非最短路徑。

圖1 A*算法局部路徑

將A*算法與二進(jìn)制灰狼算法融合，目的是利用二進(jìn)制灰狼算法對航跡點(diǎn)進(jìn)行篩選，直接刪除會帶來無效轉(zhuǎn)折的節(jié)點(diǎn)。

3.2 改進(jìn)A*算法

A*算法作為一種經(jīng)典的啟發(fā)式搜索算法，是靜態(tài)環(huán)境中求解最短路徑較為有效的直接搜索方法[7]。針對飛行器航跡規(guī)劃的問題，本文對A*算法的評價(jià)函數(shù)[10]做了一定的改變，因?yàn)锳*算法的主要目的是找尋可行的安全航跡。為保證算法效率，此時(shí)僅先將對威脅代價(jià)的評價(jià)指標(biāo)考慮到A*算法中，A*的評價(jià)函數(shù)可變?yōu)椋?/p>

式中：f(n)為當(dāng)前節(jié)點(diǎn)n的評價(jià)函數(shù)，h(n)為當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計(jì)代價(jià)。

然而，此階段A*算法得到的是可行解而不是最優(yōu)解，因?yàn)锳*算法過程中，節(jié)點(diǎn)擴(kuò)展只限于柵格線的交叉點(diǎn)，所以得到的航跡點(diǎn)集合存在一部分會使飛行器頻繁轉(zhuǎn)彎的節(jié)點(diǎn)。而二進(jìn)制灰狼算法是灰狼算法在特征選擇問題上的優(yōu)化，于是選擇二進(jìn)制灰狼算法對A*算法進(jìn)行改進(jìn)。二進(jìn)制灰狼算法更新過程中，同時(shí)將評價(jià)函數(shù)更新為：

3.3 二進(jìn)制灰狼算法更新過程

狼群的初始化及更新過程采用二進(jìn)制灰狼算法[5]進(jìn)行。為了加快迭代速度，且降低過快陷入局部最優(yōu)的概率，將頭狼簡化為一只進(jìn)行狼群更新[11]。為了使灰狼位置二值化，需要將灰狼的位置轉(zhuǎn)換為二進(jìn)制矢量來進(jìn)行位置更新，其公式如下：

式中：r0是[0，1]的隨機(jī)數(shù)，A為系數(shù)向量，n是搜索空間的維數(shù)，Xα，Xβ，Xδ代表α，β，δ狼在搜索空間中的位置；X1，X2，X3分別定義為受α，β，δ狼影響的二進(jìn)制步長；X n(t+1)是迭代t時(shí)維數(shù)n中更新的二進(jìn)制位置。S(a)定義為：

3.4 算法流程

首先，使用A*算法從起點(diǎn)出發(fā)，將以起點(diǎn)為中心的相鄰節(jié)點(diǎn)中不經(jīng)過威脅區(qū)的節(jié)點(diǎn)組成OPEN表，取評價(jià)函數(shù)值最小的節(jié)點(diǎn)放入CLOSE 表中，再以此節(jié)點(diǎn)為中心，選評價(jià)函數(shù)值最小的節(jié)點(diǎn)放入CLOSE 表中，從而迅速搜索到一條從起點(diǎn)到目標(biāo)點(diǎn)評價(jià)函數(shù)相對最優(yōu)的航跡，CLOSE 表中的節(jié)點(diǎn)即為可行航跡的航跡點(diǎn)。其次，本文將A*算法求取的航跡點(diǎn)集合作為二進(jìn)制灰狼算法的輸入，隨機(jī)初始化狼群（置0 或1）。再次，對每個(gè)航跡點(diǎn)都進(jìn)行評估，將綜合評價(jià)函數(shù)作為適應(yīng)度值來評估航跡點(diǎn)集合得到的航跡的航程長短、是否成功避障以及轉(zhuǎn)彎角大小，代價(jià)函數(shù)越小、適應(yīng)度越高，得到的航跡越優(yōu)。根據(jù)計(jì)算得到的適應(yīng)度值，選擇適應(yīng)度值最大的3 頭狼作為領(lǐng)導(dǎo)者。對于每一只狼，分別使用式（8）計(jì)算Y1，Y2，Y3。通過式（9）來更新灰狼位置。再對灰狼的適應(yīng)度值進(jìn)行計(jì)算，并更新α，β，δ三頭灰狼的位置。重復(fù)該算法，直到滿足終止條件。算法的流程如圖2 所示。

圖2 算法流程圖

4 仿真分析

為評估A*-BGWO 算法的性能，設(shè)計(jì)了不同規(guī)劃空間的兩個(gè)仿真案例進(jìn)行展示，仿真程序于Matlab 軟件中編寫。兩個(gè)案例中，均設(shè)柵格單位為km。因?yàn)楸苷显陲w行器飛行任務(wù)中最為重要，其次是航程長短和轉(zhuǎn)彎角度，所以本文仿真過程中設(shè)ω1=0.3，ω2=0.5，ω3=0.2 分別為航程代價(jià)函數(shù)、威脅代價(jià)函數(shù)及轉(zhuǎn)彎角代價(jià)函數(shù)的權(quán)重。飛行任務(wù)為起點(diǎn)位置到達(dá)終點(diǎn)位置并避開威脅區(qū)，最小飛行高度設(shè)為安全海拔15 km，高于安全海拔的模型即為威脅模型，低于安全海拔的為地形模型。規(guī)劃出的路徑都需要遇到屬于禁飛區(qū)的威脅模型，飛行器必須從旁側(cè)繞過。遇到威脅較小的地形模型，飛行器可以從其上方飛過。仿真案例的初始參數(shù)如表1 所示。

表1 航跡仿真參數(shù)

在案例1 中，環(huán)境模型隨機(jī)生成多個(gè)不規(guī)則地形模型以模擬飛行環(huán)境，其中包括高度設(shè)置高于安全海拔高度的威脅模型（淺色模型塊）和高度設(shè)置低于安全海拔高度的地形模型（深色模型塊）。圖3 展示了A*算法和A*-BGWO 算法的仿真結(jié)果及差異對比，其中，白色為傳統(tǒng)A*算法規(guī)劃的航跡，紅色為A*-BGWO 算法規(guī)劃的航跡。改進(jìn)算法迭代7 次后適應(yīng)度最優(yōu)。

圖3 案例1 三維規(guī)劃航跡

從圖3 整體可以看出，GWO 算法轉(zhuǎn)向靈活但搜索航跡較長，規(guī)劃效果明顯次于A*算法和A*-BGWO 算法。

GWO 算法與另兩種算法得到的航跡差異較大，暫不做局部對比。因?yàn)锳*算法與改進(jìn)算法重合部分較多，所以用圖4 展示飛行器避障規(guī)劃時(shí)A*算法與A*-BGWO 算法的局部航跡差異。本文提出的A*-BGWO 算法所規(guī)劃出的航跡減少了一部分不必要的航跡點(diǎn)（黑點(diǎn)表示），避免了無效轉(zhuǎn)折，航跡轉(zhuǎn)折線路也不受A*算法節(jié)點(diǎn)擴(kuò)展方向限制，因而縮短了航程，規(guī)劃出的航跡的轉(zhuǎn)彎角度也優(yōu)于A*算法。

圖4 案例1 三維規(guī)劃局部航跡

案例2 主要展現(xiàn)A*算法和A*-BGWO 算法在威脅區(qū)固定的地圖模型上的避障效果差異。案例中減少了地圖模型上的總威脅源個(gè)數(shù)，把威脅模型設(shè)為規(guī)則圖形，并把威脅區(qū)設(shè)置到從起始點(diǎn)到目標(biāo)點(diǎn)的直線路徑附近。威脅區(qū)個(gè)數(shù)在一定范圍內(nèi)對規(guī)劃結(jié)果影響不大，為了顯示方便及對比清晰，此案例中將威脅源設(shè)置為7 個(gè)。圖5 展示了A*算法和A*-BGWO 算法的仿真結(jié)果及差異對比。

圖5 案例2 二維規(guī)劃航跡

不同規(guī)劃算法航跡仿真結(jié)果如表2 所示?？梢钥闯?，A*-BGWO 算法在不影響避障效果的同時(shí)，能縮減大部分航跡點(diǎn)，縮短航程。從表2 還可以看出，從起始點(diǎn)到目標(biāo)點(diǎn)規(guī)劃航跡上經(jīng)過的威脅模型數(shù)目對A*算法的規(guī)劃時(shí)間的影響較大，而A*-BGWO 算法的規(guī)劃時(shí)間對經(jīng)過的威脅模型數(shù)目增減不敏感，且不會因?yàn)榈貓D復(fù)雜而嚴(yán)重影響規(guī)劃效率，運(yùn)算穩(wěn)定性更優(yōu)。

表2 不同規(guī)劃算法航跡仿真結(jié)果

綜合以上結(jié)果，A*-BGWO 算法的規(guī)劃時(shí)間雖然略高于A*算法，但是搜索效果更好，規(guī)劃出的航跡總航程更短，優(yōu)化了轉(zhuǎn)彎角度，故算法具有更好的性能。

5 結(jié)語

針對帶有多威脅區(qū)域復(fù)雜地形的飛行器航跡規(guī)劃問題，本文提出了一種基于改進(jìn)A*算法的航跡規(guī)劃方法。該算法利用了A*算法在離散化的地圖上求取的結(jié)果與二進(jìn)制灰狼優(yōu)化算法進(jìn)行融合，既打破了A*算法節(jié)點(diǎn)擴(kuò)展時(shí)帶來的轉(zhuǎn)彎角度限制，也使二進(jìn)制灰狼算法有一個(gè)較優(yōu)的初始矩陣，避免了盲目搜索，能更快得到最優(yōu)的航跡點(diǎn)集合。隨后通過將灰狼的位置轉(zhuǎn)換為二進(jìn)制矢量來進(jìn)行位置更新，得到最優(yōu)航跡點(diǎn)集合，極大地提升了種群的收斂效果。仿真結(jié)果表明，該算法能夠?qū)崟r(shí)為飛行器規(guī)劃出一條最短飛行路徑，且能有效地避開威脅區(qū)域，同時(shí)轉(zhuǎn)彎角度更優(yōu)。