張富才 ，寧 芊 *，周新志

（1.四川大學(xué)電子信息學(xué)院，成都 610065；2.中國電子科技集團(tuán)公司第二十九研究所電子信息控制重點實驗室，成都 610036）

0 引言

航路規(guī)劃目的在于根據(jù)地形與威脅信息，并考慮到平臺性能的情況下，為完成飛行任務(wù)到達(dá)目標(biāo)點規(guī)劃出最優(yōu)飛行路徑。一般平臺在出發(fā)前按照已知航路上的地形及威脅進(jìn)行到達(dá)目的地的航路規(guī)劃，在途中若有突發(fā)事件則根據(jù)當(dāng)前狀況進(jìn)行重新規(guī)劃航路。

目前，搜索最優(yōu)路徑的算法很多，其中A*作為啟發(fā)式算法的代表，對其本身的優(yōu)化及改進(jìn)的方法也很多。然而很多改進(jìn)都只是針對點搜索空間、航跡平滑、搜索速度等方面進(jìn)行優(yōu)化［1-2，11-14］。例如，通過剪裁搜索區(qū)域，設(shè)計新的搜索策略以及優(yōu)化算法計算速度進(jìn)行改進(jìn)［1］；通過優(yōu)化節(jié)點擴展方式以及路徑的平滑進(jìn)行改進(jìn)［2］等。然而實際中由于突發(fā)事件，可能存在地圖信息不明確以及多種威脅條件，從而無法及時查詢平臺狀態(tài)，導(dǎo)致無法完成任務(wù)并到達(dá)目標(biāo)點。因此，針對以上問題，采用生存代價優(yōu)化適應(yīng)度函數(shù)，可在當(dāng)前突發(fā)事件情況下由于地圖信息不明確、或者存在威脅情況下搜索路徑，并通過過程中每個狀態(tài)的轉(zhuǎn)移概率獲取在威脅區(qū)域中平臺實時狀態(tài)。

1 基本A＊算法

A*算法作為啟發(fā)式搜索算法，通過對狀態(tài)空間中每個搜索點的位置進(jìn)行評估，選取最優(yōu)點，然后再以當(dāng)前位置進(jìn)行搜索，最終到達(dá)目標(biāo)點。代價函數(shù)如下：

式中：f（n）為當(dāng)前節(jié)點的代價值；g（n）為從起點到節(jié)點n的實際代價；h（n）為啟發(fā)函數(shù)，表示從節(jié)點n到目標(biāo)點的估計代價值，算法步驟如下：

1）將起點放入Open表并估計從出發(fā)點到目標(biāo)點的代價；

2）判斷Open表是否為空，是則結(jié)束循環(huán)，否則繼續(xù)；

3）從Open表中取出f（n）值最小的節(jié)點作為當(dāng)前節(jié)點，將其添加進(jìn)Close表并從Open表中刪除；

4）判斷當(dāng)前節(jié)點是否為目標(biāo)節(jié)點，是則規(guī)劃成功，否則繼續(xù)；

5）對當(dāng)前節(jié)點的相鄰節(jié)點進(jìn)行擴展，判斷相鄰節(jié)點是否在Close中，若是則放棄該節(jié)點，否則作為當(dāng)前節(jié)點的擴展子節(jié)點；

6）對每一個擴展子節(jié)點，判斷其是否在Open表中，如果不在，計算該節(jié)點 g（n）和 h（n），并添加進(jìn)Open表，并把當(dāng)前節(jié)點作為該節(jié)點的父節(jié)點，跳轉(zhuǎn)到第2）步；若在Open表中，檢查新路徑的g（n）是否更小，是則將該節(jié)點的父節(jié)點改為當(dāng)前節(jié)點，并重新計算 g（n）和 h（n），跳轉(zhuǎn)到第 2）步，否則直接跳轉(zhuǎn)到第2）步。

2 Markov模型

當(dāng)執(zhí)行的任務(wù)區(qū)位于敵方武器攻擊范圍外，此時平臺生存狀態(tài)最好；而當(dāng)平臺執(zhí)行位于敵方武器攻擊范圍內(nèi)的任務(wù)時，將會暴露在敵方防空系統(tǒng)中。一般后者情況居多，并且在執(zhí)行任務(wù)時也會存在以下因素：1）敵方保護(hù)貴重物資，會有敵機阻止平臺到達(dá)目標(biāo)，此時為了保證平臺安全，需要平衡完成任務(wù)、與敵機對戰(zhàn)等方面的狀態(tài)；2）敵人的偽裝，定位的敵方雷達(dá)、武器等信息存在不準(zhǔn)確的情況，即使根據(jù)最佳情報信息已經(jīng)規(guī)劃出路徑，當(dāng)平臺實際執(zhí)行任務(wù)時情況可能會再次變化。因此，在執(zhí)行任務(wù)過程中出現(xiàn)新的情報時，平臺需要根據(jù)當(dāng)前信息采用生存代價對任務(wù)路徑進(jìn)行新的評價，重新選取威脅最小的路徑。

由上可知平臺的威脅主要來自敵方雷達(dá)與武器，并且敵方發(fā)現(xiàn)與擊落的幾率主要取決于平臺的位置。

2.1 生存模型

生存模型是描述平臺與敵方之間狀態(tài)的連續(xù)時間馬爾科夫模型，主要用來描述隨機的多領(lǐng)域過程［3-4］。

2.1.1 馬爾科夫過程

連續(xù)時間 Markov過程{X（t）|t≥0}是一個連續(xù)、離散值的隨機過程，如式（2）：

其中，AT為矩陣A的轉(zhuǎn)置。

2.1.2 狀態(tài)與狀態(tài)概率

生存模型設(shè)置為5個狀態(tài)：未發(fā)現(xiàn)（Undetected）、發(fā)現(xiàn)（Detected）、跟蹤（Tracked）、對戰(zhàn)（Engaged）與擊中（Hit）。由式（4），設(shè)置向量為路徑中某時間點狀態(tài)概率，該模型轉(zhuǎn)移強度矩陣A（t）與平臺經(jīng)過的雷達(dá)武器區(qū)域及經(jīng)過的時間點相關(guān)。在時間點tn：

其中，eA定義為：。

2.1.3 區(qū)域與轉(zhuǎn)移強度關(guān)系

2.1.3.1 單個雷達(dá)、武器區(qū)域

圖1 狀態(tài)轉(zhuǎn)移方向

1）雷達(dá)、武器區(qū)域外。在該區(qū)域，飛行過程在Undetected狀態(tài)結(jié)束，可通過DU＞0，TD＞0 及ET＞0對模型進(jìn)行描述。然而考慮到敵方對平臺運動軌跡的預(yù)測，因此，并不會立刻從較高狀態(tài)轉(zhuǎn)移，此時可以設(shè)置ET為最大。該過程轉(zhuǎn)移強度見表1。

表1 不同區(qū)域初始化轉(zhuǎn)移強度值

2）雷達(dá)區(qū)域內(nèi)。雷達(dá)內(nèi)，平臺可能會處于Undetected、Detected與 Tracked狀態(tài)，在 Detected與Tracked狀態(tài)，可用DU＞0，TD＞0 描述；由于在Undetected狀態(tài)的幾率較小，因此，可設(shè)置DU、TD為平臺在雷達(dá)范圍外時該值的最小值，如果敵方雷達(dá)偵查精度極高，則TD=DU=0。

3）武器區(qū)域內(nèi)。該區(qū)域不存在Detected與Tracked狀態(tài)，可設(shè)置DU=TD=0。在確定平臺位置的情況下攻擊有效，因此，武器一般位于雷達(dá)區(qū)域內(nèi)，此時為重疊區(qū)域，分別用TE、EH描述對戰(zhàn)與擊中兩種狀態(tài)，具體分析見下文。

2.1.3.2 雷達(dá)、武器重疊區(qū)域

假設(shè)路徑上要經(jīng)過的某區(qū)域是由K個雷達(dá)與武器組成的重疊區(qū)域，并且每個獨立的區(qū)域可用轉(zhuǎn)移強度矩陣Ak進(jìn)行描述，則最終重疊區(qū)的轉(zhuǎn)移強度矩陣AComb可通過計算該區(qū)域中每個獨立區(qū)域的轉(zhuǎn)移強度矩陣得到。

1）Undetected→Detected→Tracked

相對于單個雷達(dá)，平臺在多雷達(dá)系統(tǒng)中更易處于Detected與Tracked狀態(tài)。假設(shè)每個雷達(dá)之間的探測是相互獨立的，則平臺在重疊區(qū)從Undetected狀態(tài)到Detected狀態(tài)的轉(zhuǎn)移強度為K個轉(zhuǎn)移強度之和。

2）Tracked→Detected→Undetected

多雷達(dá)系統(tǒng)中平臺更易被追蹤。由于系統(tǒng)中每個雷達(dá)的壽命為指數(shù)分布形式。則該系統(tǒng)的轉(zhuǎn)移強度Comb為系統(tǒng)壽命 的倒數(shù)。

3）Tracked?Engaged→Hit

判斷平臺是否進(jìn)入對戰(zhàn)狀態(tài)取決于敵方，并且與位于重疊區(qū)的路徑長度有關(guān)。實驗中假設(shè)敵人采用一臺高精度武器攻擊，其轉(zhuǎn)移強度為：

2.1.4 生存代價

生存代價用來描述模型中每個狀態(tài)信息，主要分為以下兩個方面。

1）狀態(tài)內(nèi)代價。假設(shè)單位時間為bi，則在狀態(tài)i內(nèi)，代價為所有單位時間代價和；

2）狀態(tài)轉(zhuǎn)移代價cij。當(dāng)狀態(tài)i與狀態(tài)j發(fā)生轉(zhuǎn)換時，計算 cij。

設(shè)置u（t）為飛行過程中t時刻的代價，即在區(qū)間［0，t］內(nèi)的代價。u（t）取決于過程最終輸出，是一個隨機變量，因此，選擇期望值v（t）進(jìn)行計算。假設(shè)模型在微小時間間隔Δ內(nèi)只有一次轉(zhuǎn)換，過程中t時刻處于狀態(tài)i的概率為p（it），則在Δ內(nèi)保持在狀態(tài)i的概率為1-v（it）Δ，此時代價為biΔ；在該過程中從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率為ijΔ，此時代價為：，其中相當(dāng)于，則：

由式（4）與式（6），定義

則：

由式（5）：

X（tn）為tn時刻當(dāng)前生存狀態(tài)概率分布。

3 改進(jìn)算法

3.1 約束限制及搜索空間

平臺由于自身條件限制，為了避免在航路規(guī)劃后可能無法實際執(zhí)行。實驗中為了防止該問題，約束條件［5］主要考慮如下。

1）角度限制。分為偏轉(zhuǎn)角與俯仰角。偏轉(zhuǎn)角表示在平臺當(dāng)前飛行方向上，限定平臺左、右轉(zhuǎn)彎最大角度，俯仰角表示在當(dāng)前飛行方向上平臺上升、下降的最大角度；

2）最短飛行距離。當(dāng)平臺以一定飛行速度飛行時，兩次調(diào)整飛行狀態(tài)期間平臺所需飛行的最短直線距離。它由不同的飛行速度以及平臺的自身性能決定，無論對于飛行速度的控制還是對航跡的評估，都希望盡可能地直飛以使航跡平滑；

3）最低、高飛行高度。保證平臺安全飛行的高度限制，當(dāng)平臺在最低飛行高度下飛行時會由于威脅源過近而被擊落，同時，過低飛行時對規(guī)劃空間的劃分更加精確，當(dāng)航跡間節(jié)點距離較遠(yuǎn)時，平臺與地面撞擊的概率大大增加，當(dāng)平臺在最高飛行高度上飛行時易被雷達(dá)探測到，不能有效地利用地面遮擋進(jìn)行隱蔽，所以在此高度范圍內(nèi)飛行安全系數(shù)較高；

4）速度、油耗。平臺飛行時，限定最大速度Vmax，最小飛行速度Vmin，并且在飛行時，考慮到雷達(dá)與武器區(qū)域，為了提高平臺生存率，在該區(qū)域內(nèi)的速度要大于在該區(qū)域外的速度，因此，在雷達(dá)區(qū)域速度設(shè)置為Vrd=1.5，武器區(qū)域為Vwp=2，雷達(dá)武器區(qū)域外為Vout=1；平臺油耗通過求和不同速度在單位時間內(nèi)的耗油量獲得，在一定情況下，油耗低則較優(yōu)；

5）任務(wù)約束。平臺在保持生存條件的前提下務(wù)必執(zhí)行。

搜索空間［7］設(shè)計如圖2所示，其中R1為路徑上當(dāng)前點，R0為上一個點，點O為R0R1直線上距離R1為R1O的點，R1O為搜索步長，α為最大偏轉(zhuǎn)角，β為最大俯仰角。搜索點時，首先在圓O邊上以夾角θ選擇固定數(shù)量點，設(shè)置為點集A，然后以同樣方法，在圖中虛線圓邊上選取固定數(shù)量點，設(shè)置為點集B，該圓半徑為1/2圓O半徑，最終搜索點集為A、B及點 O 的并集［14-15］。

3.2 適應(yīng)度函數(shù)

由式（1），修改A*算法的適應(yīng)度函數(shù)［6］為：

f（n）為當(dāng)前節(jié)點代價，v（tn）為生存代價，g（n）表示從起點到節(jié)點n的實際代價，h（n）為啟發(fā)函數(shù)，表示從節(jié)點n到目標(biāo)點的估計代價值，其中wt為生存代價權(quán)值，wl為實際航程代價權(quán)值，wh為距離目標(biāo)點代價權(quán)值，相當(dāng)于任務(wù)權(quán)值。

圖2 搜索空間

4 實驗結(jié)果

實驗場景通過Matlab2014a采用差值法生成，結(jié)果如圖3，圖4所示。

圖3 結(jié)果側(cè)視圖

圖4 結(jié)果俯視圖

實驗中把雷達(dá)與武器區(qū)域視為空間球體，圖中半徑較大的藍(lán)色區(qū)域表示雷達(dá)范圍，較小的紅色區(qū)域表示武器范圍，黃色區(qū)域為實驗所設(shè)置的任務(wù)點，表2為不同路徑結(jié)果數(shù)據(jù)。

表2 不同路徑油耗、時間、距離結(jié)果

圖3中路徑滿足高度約束，且圖中路徑rt1為標(biāo)準(zhǔn)算法結(jié)果，權(quán)值為：wt=0，wl=0.6，wh=1，rt1 只設(shè)置了地形與雷達(dá)武器的距離約束；路徑rt2與rt3為加入生存代價后結(jié)果，rt2權(quán)值為：wt=0.15，wl=0.5，wh=1，路徑中添加了生存代價；rt3在rt2的基礎(chǔ)上增大了生存代價wt，降低了任務(wù)代價wh，權(quán)值為：wt=0.28，wl=0.22，wh=0.75。從圖4與表2可知，rt1相對于rt2路徑長，油耗高，且處于雷達(dá)武器范圍內(nèi)的路徑較長，因此，加入Markov模型后更優(yōu)；rt3增加生存權(quán)值，減小任務(wù)權(quán)值，因此，相對于rt2路徑及時間較長，然而由于處于雷達(dá)武器范圍內(nèi)的路徑點較少，油耗相對較低。

圖5為rt2與rt3路徑狀態(tài)曲線，由于rt3生存代價權(quán)值較高，在Undetected狀態(tài)rt3比rt2概率更大，而在Detected與Tracking狀態(tài)，比rt2概率更小，并且不在武器區(qū)域，因此，Engaged與Hit狀態(tài)概率為0。

圖5 rt2、rt3狀態(tài)概率

因此，通過設(shè)置不同權(quán)值可以獲得不同路徑，并且加入生存代價改進(jìn)后的搜索算法更優(yōu)。

5 結(jié)論

本文采用實驗地形進(jìn)行測試，根據(jù)當(dāng)前約束情況，添加生存代價后，可以獲取平臺在路徑中每個時刻的狀態(tài)變化，從而及時判斷平臺狀態(tài)進(jìn)行分析，結(jié)果較好，然而考慮到實際情況的復(fù)雜，本文存在其他一些不足，例如：

1）平臺飛行過程中比較重要的速度及油耗等問題建模較為簡單；

2）實際中任務(wù)點分布情況較多，本實驗只采用當(dāng)前一種任務(wù)布置方式；

3）實際地理環(huán)境中的地形因素；

4）任務(wù)執(zhí)行狀況。

因此，期望在后續(xù)實驗中可以加入更多的復(fù)雜情況進(jìn)一步實驗研究，使之可以最大化地靠近真實環(huán)境，得到更加準(zhǔn)確、有效的結(jié)果。