無(wú)人機(jī)航跡規(guī)劃算法綜述

成都飛機(jī)工業(yè)集團(tuán)有限責(zé)任公司 彭閃 殷苑 田峰 馮張偉 姚森

航跡規(guī)劃作為任務(wù)規(guī)劃的核心，在任務(wù)規(guī)劃中起著決定性作用。本文首先介紹了無(wú)人機(jī)航跡規(guī)劃的國(guó)內(nèi)外研究現(xiàn)狀，再介紹了幾種常見(jiàn)的航跡規(guī)劃算法，最后表述了航跡規(guī)劃中的一些難點(diǎn)與問(wèn)題，并對(duì)航跡規(guī)劃的發(fā)展進(jìn)行了總結(jié)。

近幾十年來(lái)，無(wú)人駕駛飛機(jī)在戰(zhàn)爭(zhēng)中已得到廣泛應(yīng)用，由于其機(jī)上無(wú)人操作的特點(diǎn)，直接減少了人員傷亡，缺少飛行員可以減輕體重，降低成本，并為新的作戰(zhàn)范例提供機(jī)會(huì)。將使無(wú)人機(jī)能夠在最少或沒(méi)有人為干預(yù)的情況下執(zhí)行任務(wù)，這樣的軍事和民用任務(wù)可能包括情報(bào)搜集、目標(biāo)跟蹤和救援任務(wù)[1]。

1 國(guó)內(nèi)外研究現(xiàn)狀

近年來(lái)，國(guó)內(nèi)外涌現(xiàn)了大量關(guān)于航跡規(guī)劃的算法。各式各樣的算法優(yōu)缺點(diǎn)各異，所適用的場(chǎng)景也不盡相同。Al等人[2]提出了一種以較低的計(jì)算復(fù)雜度提供動(dòng)態(tài)路徑發(fā)現(xiàn)的啟發(fā)式算法。2003年，Nikolos等人[3]設(shè)計(jì)出一種用于無(wú)人駕駛飛行器(UAV)自主導(dǎo)航的離線(xiàn)/在線(xiàn)路徑規(guī)劃器。解決了在已知環(huán)境中使用離線(xiàn)規(guī)劃器的無(wú)人機(jī)導(dǎo)航問(wèn)題。Sahingoz等人[4]采用遺傳算法(GA)，提出了一種多無(wú)人機(jī)系統(tǒng)的可飛行路徑規(guī)劃。2006年，F(xiàn)oo等人[5]提出了一種粒子群優(yōu)化(PSO)算法來(lái)規(guī)劃三維路徑。通過(guò)使用PSO算法規(guī)劃出避開(kāi)障礙物和威脅區(qū)的可行路徑。魏等人[6]在2016年研究了一種基于高度層引導(dǎo)因子的改進(jìn)蟻群算法。2013年，劉等人[7]提出了一種改進(jìn)后的稀疏A*算法，通過(guò)降維將三維航跡規(guī)劃將至二維航跡規(guī)劃，降低了計(jì)算復(fù)雜度與規(guī)劃時(shí)間。2014年，王等人[8]研究了一種基于三維約束的人工勢(shì)場(chǎng)法，用于實(shí)時(shí)航跡規(guī)劃。2016年，丁等人[9]提出了一種改進(jìn)后的人工勢(shì)場(chǎng)法，該方法簡(jiǎn)單易于實(shí)現(xiàn)，且具有較好的適應(yīng)性。

2 航跡規(guī)劃算法

近年來(lái)，國(guó)內(nèi)外學(xué)者研究了許多航路規(guī)劃的算法，主要可分為三類(lèi)：確定性算法、隨機(jī)性算法、最優(yōu)化算法。

2.1 確定性算法

確定性算法，大致理解是指當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)或下一序列是確定的。下面將介紹幾種典型的確定性算法。

2.1.1 Voronoi圖

Voronoi圖是根據(jù)戰(zhàn)場(chǎng)上的場(chǎng)景信息，將威脅區(qū)域的中心區(qū)域用一個(gè)圓點(diǎn)代替，再構(gòu)建相鄰?fù){區(qū)之間的連線(xiàn)的垂直中位線(xiàn)，使得該垂直中位線(xiàn)上的每一點(diǎn)，與該相鄰?fù){點(diǎn)的作用距離一致，或者根據(jù)戰(zhàn)場(chǎng)環(huán)境和任務(wù)需求調(diào)整權(quán)重，均衡了各區(qū)域的威脅。每一條垂直平分線(xiàn)共同構(gòu)成了一個(gè)由若干多邊形組成的網(wǎng)格，以此將航路規(guī)劃轉(zhuǎn)換成最小路徑求解。如圖1所示。其中灰色圈表示威脅區(qū)中心位置，多邊形的任一條邊為相鄰?fù){點(diǎn)的垂直中位線(xiàn)。

圖1 Voronoi圖Fig.1 Voronoi diagram

Voronoi圖通常應(yīng)用于劃分復(fù)雜場(chǎng)景的區(qū)域，通過(guò)Voronoi圖劃分后，復(fù)雜區(qū)域被分成了很多個(gè)子區(qū)域。而多邊形的每一條邊則為可行路徑，但可行路徑不一定是最優(yōu)路徑，因此還需要采取其他搜索算法進(jìn)行尋優(yōu)，最終得出最優(yōu)或次優(yōu)航跡。Voronoi圖的一大特征是直觀(guān)，通過(guò)劃分區(qū)域，可以將躲避威脅轉(zhuǎn)變?yōu)榍蠼庾疃搪窂絾?wèn)題，Voronoi圖一般適合用在二維航路規(guī)劃中。

2.1.2 A?算法

A*算法的主要思想是：設(shè)定合適的啟發(fā)函數(shù)，選取一個(gè)當(dāng)前節(jié)點(diǎn)，搜索其下一節(jié)點(diǎn)，計(jì)算其所有下一節(jié)點(diǎn)的代價(jià)值，并將所有下一節(jié)點(diǎn)的代價(jià)值進(jìn)行比較，選取代價(jià)值最小的點(diǎn)，將其標(biāo)記為擴(kuò)展節(jié)點(diǎn)，作為潛在最優(yōu)航跡節(jié)點(diǎn)之一，以此不斷遞推，直到計(jì)算到最終的目標(biāo)節(jié)點(diǎn)。從起始點(diǎn)到目標(biāo)點(diǎn)做標(biāo)記的擴(kuò)展點(diǎn)，即可構(gòu)成由A*算法搜索出的最優(yōu)路徑。

在A*算法中，通常會(huì)設(shè)定一個(gè)OPEN表和一個(gè)CLOSE表。其中，OPEN表用來(lái)表示已經(jīng)計(jì)算出代價(jià)值但還未標(biāo)記為擴(kuò)展節(jié)點(diǎn)的點(diǎn)集合，不包括已擴(kuò)展的點(diǎn)。如圖2所示，若當(dāng)前節(jié)點(diǎn)為A點(diǎn)，則A點(diǎn)的下一節(jié)點(diǎn)有B點(diǎn)、C點(diǎn)和D點(diǎn)，計(jì)算出A點(diǎn)到B點(diǎn)的代價(jià)值為3，A點(diǎn)到C點(diǎn)的代價(jià)值為4，A點(diǎn)到D點(diǎn)的代價(jià)值為2，因此將B點(diǎn)、C點(diǎn)和D點(diǎn)放入OPEN表中，即OPEN=[B,C,D]。比較其大小，得出A點(diǎn)到D點(diǎn)的代價(jià)值最小，因此將D點(diǎn)放入CLOSE表，即CLOSE=[D]，同時(shí)將D點(diǎn)從OPEN表中刪除，更新后的OPEN=[B,C]。以此類(lèi)推，按A*算法計(jì)算出的CLOSE表中所存儲(chǔ)的節(jié)點(diǎn)為CLOSE=[A,D,E,F,H,K]，即構(gòu)成由該算法搜索出的最優(yōu)航跡。

圖2 路線(xiàn)示意圖Fig.2 Schematic diagram of the route

A*算法的搜索過(guò)程用數(shù)學(xué)模型表示，代價(jià)估計(jì)值表示為：

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

其中，f(n)表示從起始點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)n到目標(biāo)點(diǎn)的代價(jià)估計(jì)函數(shù)，g(n)表示起始點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)函數(shù)，h(n)是啟發(fā)函數(shù)，也是從當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的代價(jià)估計(jì)函數(shù)。通常情況下，啟發(fā)函數(shù)h(n)決定了是否能找到最優(yōu)路徑，因此啟發(fā)函數(shù)的選取尤為重要。

A*算法其實(shí)是一種擴(kuò)展節(jié)點(diǎn)不斷擴(kuò)大的搜索過(guò)程，算法簡(jiǎn)單，計(jì)算量小，具有較快的規(guī)劃計(jì)算速度。并且A*算法收斂程度更好，時(shí)間復(fù)雜度更小，應(yīng)用范圍更廣，全局性好，計(jì)算效率高，內(nèi)存需求少，適合解決靜態(tài)的規(guī)劃問(wèn)題。

2.1.3 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法采用虛擬模仿的方法，將戰(zhàn)場(chǎng)上的敵方威脅區(qū)及各種禁飛區(qū)、避飛區(qū)、障礙物等視為無(wú)人機(jī)飛行的阻力，將該阻力假設(shè)成戰(zhàn)場(chǎng)空間中，無(wú)人機(jī)飛行前進(jìn)中的所受到的排斥力，阻礙無(wú)人機(jī)飛行。而無(wú)人機(jī)的目標(biāo)終點(diǎn)被視為對(duì)無(wú)人機(jī)產(chǎn)生吸引力，于是將無(wú)人機(jī)在復(fù)雜環(huán)境下的航路規(guī)劃過(guò)程看作由吸引力和排斥力組成的合力的作用過(guò)程。

人工勢(shì)場(chǎng)法具有安全性高、算法計(jì)算簡(jiǎn)單易實(shí)現(xiàn)的優(yōu)點(diǎn)，其規(guī)劃時(shí)間短、速度快、實(shí)時(shí)性好。若斥力的合力大于或等于目標(biāo)的吸引力，將導(dǎo)致無(wú)法規(guī)劃出最優(yōu)或次優(yōu)路徑，容易陷入局部最優(yōu)。人工勢(shì)場(chǎng)法一般適用于協(xié)同規(guī)劃和局部靜態(tài)航跡規(guī)劃。

2.2 隨機(jī)性算法

隨機(jī)性算法，大致理解是當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)或下一序列通常是隨機(jī)出現(xiàn)的，該類(lèi)算法的不確定性增強(qiáng)。下面將介紹幾種典型的隨機(jī)性算法。

2.2.1 遺傳算法

在航跡規(guī)劃中，首先建立代價(jià)函數(shù)，再通過(guò)代價(jià)函數(shù)計(jì)算出每一節(jié)點(diǎn)的數(shù)值，并將其作為下一代節(jié)點(diǎn)選取的依據(jù)，不斷進(jìn)化迭代，最終規(guī)劃出最優(yōu)航跡。通常情況下，遺傳算法的穩(wěn)定性很強(qiáng)，能實(shí)現(xiàn)在全局范圍內(nèi)尋找最優(yōu)解，時(shí)間復(fù)雜度更小，不容易陷入局部極值，找到全局最優(yōu)解的概率很大。適用于三維全局航跡規(guī)劃和靜態(tài)航跡規(guī)劃[10]。

2.2.2 蟻群算法

蟻群算法的思想是：由于蟻群在覓食的時(shí)候，會(huì)產(chǎn)生某種能傳遞信息的物質(zhì)。因此螞蟻在經(jīng)過(guò)的路段中，都會(huì)存在這種物質(zhì)，在找到食物的最短路徑上存在的該種物質(zhì)會(huì)越積越多，含量越來(lái)越高，進(jìn)而使得該條路徑上的螞蟻不斷增加，最終所有的螞蟻都選擇這條路徑，逐漸收斂。

在航路規(guī)劃中，滿(mǎn)足約束條件下，信息素濃度相當(dāng)于航跡代價(jià)，航跡代價(jià)越小的路徑，會(huì)被無(wú)人機(jī)優(yōu)先選擇，并將代價(jià)反饋。蟻群算法具有很好的穩(wěn)定性與通用性，易于并行實(shí)現(xiàn)，也適合和其他算法共同規(guī)劃路徑，其收斂程度更好，時(shí)間復(fù)雜度更小，范圍更廣泛，適用于離線(xiàn)狀態(tài)下的全局航跡規(guī)劃。

2.2.3 粒子群算法

粒子群優(yōu)化算法基本思想為：(1)已知當(dāng)前粒子的位置與速度矢量，包括大小和方向；(2)已知當(dāng)前節(jié)點(diǎn)的歷史最優(yōu)速度矢量，包括歷史最優(yōu)速度大小與方向，即節(jié)點(diǎn)自身的極值；(3)已知在全部節(jié)點(diǎn)中的全局歷史最優(yōu)速度矢量，即全部節(jié)點(diǎn)的極值。根據(jù)這三個(gè)已知量，不斷進(jìn)化最后達(dá)到一個(gè)收斂的狀態(tài)，直到搜索出全局最優(yōu)解。以此更新后的位置點(diǎn)距離真實(shí)目標(biāo)點(diǎn)有一定的偏差，通過(guò)不斷進(jìn)化更新，逐漸收斂于真實(shí)值。

粒子群算法具有易于實(shí)現(xiàn)、快速收斂的優(yōu)點(diǎn)，可變參數(shù)少，其算法魯性較強(qiáng)，原理簡(jiǎn)單，搜索能力全面。

2.3 數(shù)學(xué)規(guī)劃

動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃算法一種求解決策過(guò)程最優(yōu)的算法。它將一個(gè)問(wèn)題分解成多個(gè)子問(wèn)題，每一個(gè)子問(wèn)題之間不是相互獨(dú)立的，上一個(gè)子問(wèn)題的解會(huì)影響對(duì)下一個(gè)子問(wèn)題的求解，但是下一個(gè)子問(wèn)題的解不會(huì)改變前面上一個(gè)子問(wèn)題的解。在航跡規(guī)劃中，選取恰當(dāng)?shù)拇鷥r(jià)函數(shù)，從最后一個(gè)節(jié)點(diǎn)往前推，找到其表示形式，直到到達(dá)起始節(jié)點(diǎn)。如圖3所示。

圖3 動(dòng)態(tài)規(guī)劃算法Fig.3 Dynamic programming algorithm

其中，每一條路徑的數(shù)字代表該路徑的代價(jià)數(shù)，到K點(diǎn)的代價(jià)f(K)表示為:

f(K)=min[f(D)+4,f(E)+3]

f(D)=min[f(B)+2,f(A)+4,f(C)+4]f(E)= min[f(D)+2,f(B)+1]

到每一個(gè)節(jié)點(diǎn)地代價(jià)為該節(jié)點(diǎn)的前一節(jié)點(diǎn)的代價(jià)加上兩節(jié)點(diǎn)之間的代價(jià)，動(dòng)態(tài)規(guī)劃的思想是通過(guò)找到代價(jià)最小的節(jié)點(diǎn)，從目標(biāo)點(diǎn)倒推，最終規(guī)劃出一條選取代價(jià)最小的路徑，并以此類(lèi)推，直到規(guī)劃出最優(yōu)航跡或次優(yōu)航跡。動(dòng)態(tài)規(guī)劃算法具有搜索效率高，耗費(fèi)時(shí)間短的優(yōu)點(diǎn)，并且其穩(wěn)定可靠。

3 結(jié)語(yǔ)

在真實(shí)作戰(zhàn)中，作戰(zhàn)場(chǎng)景通常都是非常復(fù)雜的，當(dāng)提前規(guī)劃好的路徑，在戰(zhàn)場(chǎng)上遇到緊急情況時(shí)，如突然增加的障礙物，緊急出現(xiàn)的威脅源，例如敵方的導(dǎo)彈等等，如何及時(shí)規(guī)避新的障礙物以及重新規(guī)劃接下來(lái)的航跡，是一個(gè)值得研究的問(wèn)題。

在規(guī)劃航跡時(shí)需要考慮約束條件，如飛機(jī)性能限制、任務(wù)約束等。同時(shí)也需考慮性能指標(biāo)，如按照規(guī)定時(shí)間到達(dá)、飛行時(shí)間最短、任務(wù)效能最高等。而各類(lèi)算法則是針對(duì)各種約束與指標(biāo)形成的規(guī)劃出最優(yōu)航跡的方法，不同算法適用的場(chǎng)景不同，在實(shí)際選擇規(guī)劃方法時(shí)，應(yīng)選擇相應(yīng)的算法進(jìn)行航跡規(guī)劃，以尋得最優(yōu)航跡。