基于Markov模型及A*算法的平臺(tái)航路規(guī)劃*

張富才 ，寧 芊 *，周新志

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

0 引言

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

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

1 基本A＊算法

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

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

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

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

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

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

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

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

2 Markov模型

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

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

2.1 生存模型

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

2.1.1 馬爾科夫過(guò)程

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

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

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

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

其中，eA定義為：。

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

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

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

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

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

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

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

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

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

1）Undetected→Detected→Tracked

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

2）Tracked→Detected→Undetected

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

3）Tracked?Engaged→Hit

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

2.1.4 生存代價(jià)

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

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

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

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

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

則：

由式（5）：

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

3 改進(jìn)算法

3.1 約束限制及搜索空間

平臺(tái)由于自身?xiàng)l件限制，為了避免在航路規(guī)劃后可能無(wú)法實(shí)際執(zhí)行。實(shí)驗(yàn)中為了防止該問(wèn)題，約束條件［5］主要考慮如下。

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

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

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

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

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

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

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

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

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

圖2 搜索空間

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)場(chǎng)景通過(guò)Matlab2014a采用差值法生成，結(jié)果如圖3，圖4所示。

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

圖4 結(jié)果俯視圖

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

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

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

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

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

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

5 結(jié)論

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

1）平臺(tái)飛行過(guò)程中比較重要的速度及油耗等問(wèn)題建模較為簡(jiǎn)單；

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

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

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

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