0 引言

    隨著無(wú)人機(jī)技術(shù)的不斷完善,，無(wú)人機(jī)的應(yīng)用越來(lái)越廣泛,。如何使無(wú)人機(jī)在規(guī)劃的某片區(qū)域中尋找出一條從起始點(diǎn)到目標(biāo)點(diǎn)既安全又滿足相應(yīng)約束條件且所花費(fèi)代價(jià)最小的航跡一直是研究的熱點(diǎn)^[1]。標(biāo)準(zhǔn)解決航跡規(guī)劃問(wèn)題的順序是按照預(yù)先選定好的航跡代價(jià)函數(shù),，通過(guò)一定的搜索算法,，選出總的代價(jià)函數(shù)值最小的路線作為規(guī)劃出的航跡^[2-3],。

    在路徑規(guī)劃中,，常用的搜索算法有A*算法、動(dòng)態(tài)規(guī)劃法,、Dijkstra算法,、遺傳算法等。在這些算法中,，由于A*算法計(jì)算簡(jiǎn)單,，算法實(shí)現(xiàn)容易且在理論上能夠保證規(guī)劃出的路徑全局最優(yōu)，因此得到廣泛應(yīng)用^[3],。但是把A*算法應(yīng)用在航跡規(guī)劃中搜索空間將急劇增加,，由此導(dǎo)致收斂時(shí)間變長(zhǎng)，所需內(nèi)存空間增加,。針對(duì)這個(gè)問(wèn)題,，本文提出把無(wú)人機(jī)的機(jī)動(dòng)限制結(jié)合到搜索空間中從而縮小搜索空間，同時(shí)對(duì)A*算法中的open表的管理進(jìn)行改進(jìn),，以提高收斂時(shí)間,，縮小內(nèi)存使用量。

1 改進(jìn)A*算法實(shí)現(xiàn)航跡規(guī)劃

    航跡規(guī)劃的本質(zhì)是在規(guī)劃的區(qū)域內(nèi),，在給定的約束條件下尋找一條從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或次優(yōu)的飛行航跡,。傳統(tǒng)的規(guī)劃算法是基于預(yù)先確定的航跡代價(jià)函數(shù)生成一條具有最小代價(jià)的航跡^[4-5]。然而,，在許多應(yīng)用中,，這樣得到的最小代價(jià)的航跡并不能滿足實(shí)際需求。在實(shí)際應(yīng)用中,，航跡規(guī)劃需考慮無(wú)人機(jī)的機(jī)動(dòng)性能,、碰撞概率,、飛行時(shí)間等約束條件，同時(shí)由于無(wú)人機(jī)航跡規(guī)劃的地域廣闊,，因此形成的搜索空間大,。通常的搜索算法要獲得一條最優(yōu)航跡需要很長(zhǎng)的收斂時(shí)間和極大的內(nèi)存空間，所以在實(shí)際應(yīng)用中需對(duì)搜索算法進(jìn)行相應(yīng)的改進(jìn),。由于A*算法計(jì)算速度快,、實(shí)現(xiàn)容易且能達(dá)到全局最優(yōu)的特點(diǎn)，因此選擇對(duì)A*算法進(jìn)行改進(jìn),，使其適用于無(wú)人機(jī)航跡規(guī)劃,。

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

    無(wú)人機(jī)由于受機(jī)動(dòng)性能、最小飛行距離,、航跡距離,、飛行高度等的約束，通過(guò)A*規(guī)劃出來(lái)的航跡不一定能夠滿足無(wú)人機(jī)的實(shí)際飛行條件,。在擴(kuò)展節(jié)點(diǎn)時(shí)通常把相關(guān)的約束條件結(jié)合到搜索算法中,，這樣既有效減少了搜索空間，也縮短了規(guī)劃所需的時(shí)間,。無(wú)人機(jī)飛行時(shí)為達(dá)到最佳狀態(tài)一般需要滿足的約束條件有：最小飛行距離,、最大拐彎角、最大爬升/下滑角,、最長(zhǎng)飛行距離,、最低離地高度^[6]。

    假設(shè)給定了起始點(diǎn)和目標(biāo)位置,，一條從起始位置到當(dāng)前節(jié)點(diǎn)的航跡,，最小航跡段長(zhǎng)度為L(zhǎng)，最大拐彎角為φ,，最大爬升/下滑角為θ,，則從當(dāng)前位置在最小飛行距離、最大拐彎角以及最大爬升/下滑角的約束條件下能夠到達(dá)的就只有有限的位置空間,。如圖1所示,，節(jié)點(diǎn)o處的縱向的張角為2θ₂，在水平面上的張角為2θ₁,，扇面的半徑為最小飛行距離,。

    圖1是未經(jīng)離散化的可搜索空間示意圖。在離散規(guī)劃空間時(shí),，柵格的邊長(zhǎng)長(zhǎng)度為無(wú)人機(jī)的最小飛行距離,。把規(guī)劃空間離散化后結(jié)合無(wú)人機(jī)的約束條件可縮小算法搜索空間。無(wú)人機(jī)飛行是有方向性的,，在進(jìn)行當(dāng)前節(jié)點(diǎn)擴(kuò)展時(shí),，飛行反方向的節(jié)點(diǎn)以及垂直于該飛行方向的鄰接節(jié)點(diǎn)都可以裁剪掉,。這樣在水平方向上的最大拐彎角就可以限制在3個(gè)搜索空間中，垂直方向上的最大爬升/下滑角也同樣可以限制在3個(gè)搜索空間中,，這樣把擴(kuò)展當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)的搜索空間縮小為9個(gè),。如圖2所示，B節(jié)點(diǎn)是當(dāng)前新擴(kuò)展節(jié)點(diǎn),，A點(diǎn)是B點(diǎn)的父親節(jié)點(diǎn),，C點(diǎn)為新擴(kuò)展節(jié)點(diǎn)的鄰接計(jì)算節(jié)點(diǎn)。

    在三維空間中,，每個(gè)柵格都是一個(gè)立方體,，在水平剖面和豎直剖面上都要滿足最小步長(zhǎng)、最大拐彎角和最大爬升/下滑角,。但是在實(shí)際控制中,，最大轉(zhuǎn)彎角和最大爬升/下滑角可以通過(guò)一定的關(guān)系轉(zhuǎn)換，轉(zhuǎn)化為其他直接控制的參數(shù)來(lái)滿足要求,。下面就分別對(duì)水平面和豎直平面進(jìn)行轉(zhuǎn)換,。

1.1.1 水平面關(guān)系轉(zhuǎn)化

    假設(shè)無(wú)人機(jī)當(dāng)前節(jié)點(diǎn)的坐標(biāo)為(x，y,，z),，新擴(kuò)展的節(jié)點(diǎn)坐標(biāo)為(x₁，y₁,，z₁)，航跡偏角為θ,，航跡傾斜角為β,，轉(zhuǎn)彎半徑為R，最大側(cè)向過(guò)載為N_ymax,，S₁,、S₂分別為水平面上兩節(jié)點(diǎn)的擴(kuò)展步長(zhǎng)。三維航跡規(guī)劃是基于地球坐標(biāo)系,，水平方向是通過(guò)改變航向來(lái)躲避障礙物,，因此在水平方向上的轉(zhuǎn)化關(guān)系如圖3所示。

    根據(jù)圖3的幾何關(guān)系可知新擴(kuò)展的節(jié)點(diǎn)坐標(biāo)為：

1.1.2 縱向關(guān)系轉(zhuǎn)化

    無(wú)人機(jī)的縱向機(jī)動(dòng)性能主要受到最大爬升/下滑角的限制,。在低空飛行時(shí),，可以通過(guò)對(duì)地形坡度的限制來(lái)達(dá)到對(duì)最大爬升角的限制。

    如圖4所示,，假設(shè)當(dāng)前節(jié)點(diǎn)的空間坐標(biāo)為(x_i,，y_i，z_i),，待擴(kuò)展節(jié)點(diǎn)的空間坐標(biāo)為(x_i+1,，y_i+1,，z_i+1)，兩節(jié)點(diǎn)之間的距離為l,，其爬升角為β,，則由幾何關(guān)系可知：

1.1.3 對(duì)open表結(jié)構(gòu)進(jìn)行改進(jìn)

    由于在進(jìn)行節(jié)點(diǎn)擴(kuò)展尋找最優(yōu)航跡時(shí)頻繁地對(duì)open表中的節(jié)點(diǎn)執(zhí)行插入、刪除,、排序操作,，同時(shí)open表中的節(jié)點(diǎn)數(shù)目也相對(duì)較多，每次執(zhí)行插入,、刪除操作后都需要對(duì)open表進(jìn)行排序,。順序存儲(chǔ)結(jié)構(gòu)執(zhí)行插入、刪除,、排序操作均較費(fèi)時(shí),。執(zhí)行插入、刪除操作的時(shí)間復(fù)雜度是O(n),，排序的時(shí)間復(fù)雜度為O(n²),。由于在搜索時(shí)從open表中刪除的是代價(jià)值最小的節(jié)點(diǎn)，而open表是按照節(jié)點(diǎn)代價(jià)值大小來(lái)組成的有序表,，因此實(shí)際在執(zhí)行刪除操作時(shí)的時(shí)間復(fù)雜度是O(1),，當(dāng)有新節(jié)點(diǎn)插入時(shí)即需對(duì)open表進(jìn)行排序以保證open表一直處于有序狀態(tài)。由此分析得出對(duì)open表的管理主要時(shí)間花銷是在節(jié)點(diǎn)排序上,，為提高整體的運(yùn)行效率,，這里對(duì)open表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行一定的改進(jìn)，通過(guò)采用樹(shù)形的數(shù)據(jù)結(jié)構(gòu)來(lái)管理open表,。最小二叉堆是一種典型的樹(shù)形數(shù)據(jù)結(jié)構(gòu),，通過(guò)最小二叉堆對(duì)節(jié)點(diǎn)進(jìn)行排序的時(shí)間復(fù)雜度為O(n log₂ n)，通過(guò)此種數(shù)據(jù)結(jié)構(gòu)可減少open表節(jié)點(diǎn)排序的時(shí)間花銷,。

1.2 代價(jià)函數(shù)的建立

    軍用無(wú)人機(jī)航跡規(guī)劃的目標(biāo)是在滿足無(wú)人機(jī)物理特性約束以及具體飛行任務(wù)約束的前提下生成超低空地形跟隨,、地形回避以及威脅回避的飛行軌跡，以提高無(wú)人機(jī)的生存概率,。其數(shù)學(xué)表達(dá)式為：

其中P_Ci為無(wú)人機(jī)在第i航跡的撞地概率,；P_Di是無(wú)人機(jī)在第i段航跡被敵方雷達(dá)探測(cè)到的概率，P_Ki為無(wú)人機(jī)在第i段航跡被敵方雷達(dá)探測(cè)到并被擊毀的概率^[7],。由于這些概率和地區(qū)的地形,、威脅的分布密度、發(fā)現(xiàn)威脅的能力等都存在著很大關(guān)系,，同時(shí)這些概率和無(wú)人機(jī)的各項(xiàng)狀態(tài)（飛行高度,、速度、油量等）之間的關(guān)系很難定義，即使找出他們之間關(guān)系,，該公式也將十分復(fù)雜,，勢(shì)必將增加代價(jià)函數(shù)的計(jì)算難度。由此需要對(duì)上述的代價(jià)函數(shù)進(jìn)行優(yōu)化,。無(wú)人機(jī)在低空突防時(shí)飛行的高度越低,，被敵人發(fā)現(xiàn)的幾率就越小，規(guī)劃出的航跡飛行時(shí)間越短,，越能達(dá)到出其不意的效果,，同時(shí)也提高了無(wú)人機(jī)的生存概率；若飛行時(shí)間過(guò)長(zhǎng),，會(huì)增加累計(jì)威脅,，同時(shí)也增加油量的消耗?；谏鲜鲈蛟俳Y(jié)合啟發(fā)式A*算法的表達(dá)式,，把g(n)和h(n)分別簡(jiǎn)化為如下形式：

    起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)函數(shù)值：

    上述代價(jià)函數(shù)表達(dá)式中L_i表示從起始點(diǎn)到當(dāng)前節(jié)點(diǎn)飛行過(guò)的路程，F(xiàn)_max表示無(wú)人機(jī)油箱中的總的油量,，H_min,、H_max分別表示無(wú)人機(jī)為防止撞地的最小飛行高度和為防止被敵人雷達(dá)探測(cè)到的最高飛行高度，T_f表示無(wú)人機(jī)能接受威脅的最大門限值,。啟發(fā)函數(shù)中L_n表示當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離,，h_n表示目標(biāo)節(jié)點(diǎn)的高程值，λ₁,、λ₂,、λ₃、μ₁,、μ₂為表達(dá)式中各項(xiàng)的加權(quán)系數(shù),。設(shè)定不同的加權(quán)系數(shù)，獲得的航跡也有所不同：如果增大高度值的系數(shù)λ₁,，則規(guī)劃出來(lái)的平均航跡高度就會(huì)越低，增大威脅值的系數(shù)值λ₂,，則規(guī)劃出來(lái)的航跡將遠(yuǎn)離威脅,，同理增大航跡長(zhǎng)度系數(shù)值λ₃，這樣規(guī)劃出來(lái)的航跡長(zhǎng)度將減少,。通過(guò)對(duì)這些權(quán)重系數(shù)的不同組合,，可以得到所期望的滿足條件的最優(yōu)航跡。

1.3 算法實(shí)現(xiàn)

    通過(guò)結(jié)合無(wú)人機(jī)的自身限制以及任務(wù)要求,，在三維航跡搜索過(guò)程中將大大縮小搜索空間,，從而規(guī)劃出滿足條件的航跡。A*算法的實(shí)現(xiàn)主要是維護(hù)兩個(gè)表：open表以及closed表。在三維空間中算法實(shí)現(xiàn)的具體實(shí)現(xiàn)步驟如下：

    (1)把地理威脅等環(huán)境信息初始化到規(guī)劃空間中,。

    (2)把起始點(diǎn)添加到open表中,，同時(shí)把closed表置空。

    (3)判斷open表是否為空,，若為空則算法結(jié)束,；反之，則找出open表中代價(jià)值最小的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),，同時(shí)把該節(jié)點(diǎn)從open表中刪除,，放入closed表中。

    (4)判斷當(dāng)前節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn),，若當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離小于最小飛行距離,，則將目標(biāo)節(jié)點(diǎn)的父親節(jié)點(diǎn)當(dāng)作當(dāng)前節(jié)點(diǎn)，航跡搜索過(guò)程結(jié)束,。

    (5)對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展：

    ①根據(jù)約束條件產(chǎn)生當(dāng)前節(jié)點(diǎn)待擴(kuò)展區(qū),；

    ②對(duì)待擴(kuò)展區(qū)中的每個(gè)節(jié)點(diǎn)，根據(jù)式(5),、(6)計(jì)算每個(gè)節(jié)點(diǎn)的航跡代價(jià),；

    ③如果待擴(kuò)展區(qū)域中的某個(gè)節(jié)點(diǎn)已經(jīng)在closed表中且其代價(jià)估值小于closed表中的估價(jià)值，則更新closed表中的估價(jià)值,，同時(shí)把該節(jié)點(diǎn)移出closed表,，放入open表中；如若不在closed表中,，則判斷該節(jié)點(diǎn)是否在open表中,，如果不在則把該節(jié)點(diǎn)插入到open表中；

    ④如果該節(jié)點(diǎn)在open表中且open表中的g(n)值都大于當(dāng)前計(jì)算的g(n)值,，則更新open表中節(jié)點(diǎn)g(n)的值,，更新后需保證open表仍然有序。

    (6)接著繼續(xù)跳轉(zhuǎn)到步驟(3)執(zhí)行上述操作直至找到目標(biāo)節(jié)點(diǎn),。

    由于在節(jié)點(diǎn)擴(kuò)展時(shí),，每個(gè)被擴(kuò)展的節(jié)點(diǎn)都會(huì)記錄其父節(jié)點(diǎn)，當(dāng)算法找到目標(biāo)節(jié)點(diǎn)后則算法結(jié)束,。接著通過(guò)從目標(biāo)節(jié)點(diǎn)向前回溯直到起始位置,，這樣就得到了從起始點(diǎn)到目標(biāo)點(diǎn)的最小代價(jià)航跡。

2 仿真結(jié)果    

    對(duì)上述改進(jìn)后的算法在Intel Core i5,、3.1 GHz的PC上進(jìn)行驗(yàn)證試驗(yàn),，運(yùn)行環(huán)境是Windows7操作系統(tǒng)。規(guī)劃的空域大小為60 km×60 km,，假設(shè)起始節(jié)點(diǎn)的坐標(biāo)為(0,，0,，0)，目標(biāo)節(jié)點(diǎn)的坐標(biāo)為(60,，60,，0)，最低離地間隙為100 m,，最大轉(zhuǎn)彎角為45°,，最大爬升/下滑角為30°。實(shí)驗(yàn)通過(guò)用基本A*算法和改進(jìn)后的A*算法分別設(shè)置二組不同的λ₁,、λ₂,、λ₃、u₁,，u₂值來(lái)規(guī)劃最優(yōu)航跡并對(duì)算法改進(jìn)前后的性能進(jìn)行比較分析,。仿真圖5的λ₁、λ₂,、λ₃,、μ₁、μ₂分別為λ₁=0.1,，λ₂=0.3,，λ₃=0.6，μ₁=0.45,，μ₂=0.55,，由于λ₃所占權(quán)重較大，所以規(guī)劃出來(lái)的航跡總的路程較小,。仿真圖6的λ₁,，λ₂，λ₃,，μ₁,，μ₂分別為λ₁=0.4，λ₂=0.5,，λ₃=0.1,，μ₁=0.45，μ₂=0.55,，由于λ₁,、λ₂所占權(quán)重較大，所以規(guī)劃出的航跡飛行高度較低,，安全性較高。

    兩種參數(shù)的飛行高度分別如圖7,、圖8所示,。通過(guò)對(duì)比可知，第一組數(shù)據(jù)的平均飛行高度要高于第二組，這就印證了參數(shù)λ₁的大小影響無(wú)人機(jī)的平均飛行高度,，飛行高度越低也間接提高了無(wú)人機(jī)的安全性,，飛行高度越低，越難被敵人雷達(dá)發(fā)現(xiàn),。

    基本A*算法與改進(jìn)后的A*算法性能比較如表1所示,。通過(guò)各項(xiàng)數(shù)據(jù)對(duì)比可以看出，改進(jìn)后的算法規(guī)劃時(shí)間較改進(jìn)前的少很多,，并且總的航跡路程也縮減了不少,，這樣能夠在最快的時(shí)間內(nèi)規(guī)劃出滿足需求的最優(yōu)航跡。通過(guò)改變參數(shù)λ₁,、λ₂,、λ₃的權(quán)重比例可以規(guī)劃出更側(cè)重于飛行高度、安全性以及飛行距離的航跡,。

3 結(jié)束語(yǔ)

    本文通過(guò)把無(wú)人機(jī)的各項(xiàng)機(jī)動(dòng)性能限制,、飛行路程以及飛行高度等約束條件相結(jié)合的方式來(lái)縮小節(jié)點(diǎn)擴(kuò)展時(shí)的搜索空間，同時(shí)對(duì)節(jié)點(diǎn)水平方向和縱向方向的空間劃分,，使規(guī)劃出的航跡節(jié)點(diǎn)包含了無(wú)人機(jī)在該節(jié)點(diǎn)的各項(xiàng)狀態(tài),。在三維空間中，經(jīng)過(guò)限制后滿足要求的節(jié)點(diǎn)已很少,，大大提高了搜索效率,，對(duì)open表結(jié)構(gòu)的改進(jìn)減少了open表中節(jié)點(diǎn)排序的時(shí)間。同時(shí)對(duì)評(píng)價(jià)代價(jià)函數(shù)進(jìn)行優(yōu)化,，使算法能夠更快地收斂到最優(yōu)解,。

參考文獻(xiàn)

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

[2] 高暉,，陳欣,，夏云程.無(wú)人機(jī)航路規(guī)劃研究[J].南京航空航天大學(xué)學(xué)報(bào)，2001,，33(2)：135-138.

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

[4] 趙鋒,，楊偉，楊朝旭,，等.無(wú)人機(jī)三維航路動(dòng)態(tài)規(guī)劃及導(dǎo)引控制研究[J].計(jì)算機(jī)工程與應(yīng)用,，2014,，50(2)：58-64.

[5] 李季，孫秀霞.基于改進(jìn)A-Star算法的無(wú)人機(jī)航跡規(guī)劃算法研究[J].兵工學(xué)報(bào),，2008,，29(7)：789-792.

[6] 杜萍，楊春.行器航跡規(guī)劃算法綜述[J].飛行力學(xué),，2005,，23(2)：10-14.

[7] 辛貴州.無(wú)人飛行器航跡規(guī)劃算法研究[D].哈爾濱：哈爾濱工程大學(xué)，2010.