基于改進(jìn)稀疏A*編隊(duì)航跡實(shí)時(shí)規(guī)劃方法*

程 越，周中良，江建成

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

0 引言

在對地突防任務(wù)中，隨隊(duì)支援干擾機(jī)在壓制敵對空警戒雷達(dá)，提升突防效率方面發(fā)揮著極其重要的作用。在任務(wù)執(zhí)行中，干擾機(jī)編隊(duì)的任務(wù)與航跡應(yīng)隨著戰(zhàn)場態(tài)勢的變化而不斷變化，確保突防任務(wù)的順利實(shí)施。

在航跡規(guī)劃與干擾資源分配方面，文獻(xiàn)［1］通過ISODATA算法對干擾目標(biāo)分組，改變干擾樣式，實(shí)現(xiàn)對干擾資源的優(yōu)化分配。文獻(xiàn)［2］以各航線點(diǎn)精度的平均值為目標(biāo)函數(shù)，對干擾組網(wǎng)雷達(dá)提出了資源分配的方法。文獻(xiàn)［3-4］提出了基于不同邊界條件的分枝定界法來對武器資源分配問題進(jìn)行求解。文獻(xiàn)［5］為簡化規(guī)劃計(jì)算量，將空間規(guī)劃等效為平面規(guī)劃與高度規(guī)劃，并運(yùn)用動(dòng)態(tài)步長提升規(guī)劃精度，降低威脅度。文獻(xiàn)［6］基于任務(wù)對多飛行器的航跡進(jìn)行協(xié)同規(guī)劃，可以較小代價(jià)獲得較好作戰(zhàn)效果。文獻(xiàn)［7］設(shè)計(jì)了混合整數(shù)線性規(guī)劃方法對航跡進(jìn)行優(yōu)化。文獻(xiàn)［8］提出了利用遺傳算法和粒子群算法來降低三維環(huán)境下航跡規(guī)劃問題的復(fù)雜度。文獻(xiàn)［9］通過構(gòu)建基于可部分觀測的馬爾科夫決策過程的行動(dòng)空間，引導(dǎo)無人機(jī)對地面多目標(biāo)進(jìn)行跟蹤。

本文考慮到突發(fā)威脅的情況，重新對編隊(duì)干擾資源進(jìn)行分配，并對威脅數(shù)據(jù)庫進(jìn)行更新。利用改進(jìn)的稀疏 A*搜索（Sparse A*Search，SAS）算法，以發(fā)現(xiàn)威脅時(shí)我方隨隊(duì)支援干擾編隊(duì)的位置為起點(diǎn)進(jìn)行規(guī)劃，開展基于動(dòng)態(tài)干擾資源分配的航跡實(shí)時(shí)規(guī)劃技術(shù)可行性研究。

1 航跡實(shí)時(shí)規(guī)劃模型

圖1 編隊(duì)航跡實(shí)時(shí)規(guī)劃示意圖

圖1為編隊(duì)航跡實(shí)時(shí)規(guī)劃的示意圖。當(dāng)編隊(duì)沿著原始航跡向目標(biāo)點(diǎn)C飛行時(shí)，在節(jié)點(diǎn)A處遭遇了一個(gè)突發(fā)威脅。由于事前規(guī)劃的航跡是穿過了該威脅區(qū)域的，若繼續(xù)沿著事前規(guī)劃的航跡飛行，顯然會(huì)遭遇到敵方攔截。因此，必須實(shí)施航跡的實(shí)時(shí)規(guī)劃，在突發(fā)威脅的局部區(qū)域進(jìn)行尋優(yōu)，以突破威脅。實(shí)時(shí)規(guī)劃的步驟如下：

Step1：確定實(shí)時(shí)規(guī)劃航跡的規(guī)劃起始點(diǎn)。以當(dāng)前節(jié)點(diǎn)A作為航跡實(shí)時(shí)規(guī)劃起始點(diǎn)。

Step2：確定實(shí)時(shí)規(guī)劃航跡的終點(diǎn)。這里有兩種選擇：一是把原始航跡穿過突發(fā)威脅區(qū)域的第1個(gè)柵格點(diǎn)作為更新航跡的終點(diǎn)，之后繼續(xù)按照原始航跡前進(jìn)，最后到達(dá)目標(biāo)點(diǎn)；二是把原始航跡的目標(biāo)點(diǎn)作為更新航跡的終點(diǎn)，直接建立從節(jié)點(diǎn)A到目標(biāo)點(diǎn)C的最優(yōu)航跡，而不需要再使用原始航跡。兩種方式各有優(yōu)劣，第1種的計(jì)算量小，實(shí)時(shí)性比第2種強(qiáng)，但是優(yōu)化性不如第2種。

Step3：確定航跡實(shí)時(shí)規(guī)劃的步長。要求步長大于或等于最小規(guī)劃步長。

Step4：確立航跡實(shí)時(shí)規(guī)劃的目標(biāo)函數(shù)。

Step5：判斷威脅類型，如果出現(xiàn)的威脅為障礙物，則只需要在規(guī)劃的時(shí)候繞過這片區(qū)域即可，即只用對撞山威脅數(shù)據(jù)庫進(jìn)行更新。如果是雷達(dá)威脅，則需要重新為每架干擾機(jī)分配一種干擾樣式以及干擾目標(biāo)，進(jìn)行干擾資源的調(diào)整。在進(jìn)行了干擾資源重分配后，就可以對航跡段所在空域的威脅數(shù)據(jù)庫進(jìn)行更新。

Step6：采用優(yōu)化算法求解航跡段。

Step7：在編隊(duì)到達(dá)下一航跡點(diǎn)之前，以下一航跡點(diǎn)為起點(diǎn)，重新規(guī)劃下一航跡段直到下一航跡點(diǎn)為目標(biāo)點(diǎn)。

航跡實(shí)時(shí)規(guī)劃流程如圖2所示：

圖2 航跡實(shí)時(shí)規(guī)劃流程圖

2 改進(jìn)稀疏A＊算法

航跡實(shí)時(shí)規(guī)劃由于它的實(shí)時(shí)性，就是一個(gè)典型的需要局部尋優(yōu)的問題。而啟發(fā)式搜索算法則可以滿足這個(gè)需求。改進(jìn)稀疏A*算法可以對領(lǐng)域進(jìn)行搜索，從起點(diǎn)開始，不斷搜索最有希望到達(dá)終點(diǎn)的領(lǐng)域節(jié)點(diǎn)并依次往下，形成一條代價(jià)最小的航跡。因此，本文利用改進(jìn)稀疏A*算法對航跡進(jìn)行實(shí)時(shí)規(guī)劃。

2.1 稀疏A＊算法

傳統(tǒng)的A*算法屬于經(jīng)典啟發(fā)式算法，具有簡單、搜索航跡最優(yōu)的優(yōu)點(diǎn)。它的搜索節(jié)點(diǎn)分為3種：1）已經(jīng)被擴(kuò)展的節(jié)點(diǎn)，存入CLOSED表中；2）計(jì)算了航跡代價(jià)，但是還沒有被擴(kuò)展的節(jié)點(diǎn)，存入OPEN表中；3）還未計(jì)算航跡代價(jià)也未被擴(kuò)展的節(jié)點(diǎn)。OPEN表與CLOSED表中都記錄著相同的節(jié)點(diǎn)信息，包括節(jié)點(diǎn)的坐標(biāo)、父節(jié)點(diǎn)的坐標(biāo)以及各節(jié)點(diǎn)的航跡代價(jià)。算法首先計(jì)算當(dāng)前柵格領(lǐng)域的每一個(gè)柵格的代價(jià)，并對其進(jìn)行比較。之后將所有領(lǐng)域柵格及其代價(jià)存入OPEN表中，作為待擴(kuò)展節(jié)點(diǎn)，而已經(jīng)被擴(kuò)展的柵格節(jié)點(diǎn)則存入CLOSED表中。這樣通過不斷搜索當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間代價(jià)最小的節(jié)點(diǎn)，直至目標(biāo)點(diǎn)，就可以確定出一條航跡代價(jià)最小的點(diǎn)跡序列，形成最優(yōu)航跡。

A*算法中目標(biāo)函數(shù)的表現(xiàn)形式一般為：

由于每次設(shè)立儀器站時(shí)都沒有對儀器進(jìn)行定向，也沒有將儀器站的坐標(biāo)納入統(tǒng)一的坐標(biāo)系中，因此儀器在每個(gè)儀器站上獲得的目標(biāo)點(diǎn)坐標(biāo)之間沒有關(guān)聯(lián)，必須統(tǒng)一坐標(biāo)系。本文采用文獻(xiàn)［1］的計(jì)算方法進(jìn)行統(tǒng)一坐標(biāo)轉(zhuǎn)換。文獻(xiàn)［1］給出的計(jì)算方法：

其中，n是待擴(kuò)展節(jié)點(diǎn)，f（n）是待擴(kuò)展節(jié)點(diǎn)的評估函數(shù)，g（n）是起點(diǎn)到待擴(kuò)展節(jié)點(diǎn) n 的真實(shí)代價(jià)，h（n）為啟發(fā)函數(shù)，表示從待擴(kuò)展節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的代價(jià)估值。

但當(dāng)搜素范圍增加后，搜索節(jié)點(diǎn)過多，A*算法容易出現(xiàn)搜索時(shí)間長難以收斂的缺點(diǎn)，因此，為了提高搜索速度，本文采用了稀疏A*算法。該算法由Szczerba［10］在2000年提出，它通過加入約束條件，可以有效剔除空間中的無效節(jié)點(diǎn)，縮小搜索空間。稀疏A*算法在空間中的搜索示意圖如圖3所示：

圖3 稀疏A*算法搜索示意圖

2.2 算法改進(jìn)

本文主要約束條件為前文提到的航跡可飛行性，即用撞山威脅、雷達(dá)網(wǎng)探測威脅以及飛行器自身性能對空間中的可飛節(jié)點(diǎn)進(jìn)行篩選。同時(shí)，為了解決航跡規(guī)劃的實(shí)時(shí)性，本文依據(jù)實(shí)時(shí)規(guī)劃模型對算法進(jìn)行改進(jìn)。

在對航跡點(diǎn)進(jìn)行搜索的過程中，考慮到搜索角度以及步長的影響，最后不一定能搜索到目標(biāo)點(diǎn)。因此，這里對算法的結(jié)束條件進(jìn)行更改。當(dāng)航跡搜索的當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)之間的距離小于R0時(shí)，搜索結(jié)束，即：

其中，（xT，yT，zT）為目標(biāo)點(diǎn)的坐標(biāo)，（xc，yc，zc）為當(dāng)前節(jié)點(diǎn)的坐標(biāo)。

為使航跡能夠向目標(biāo)點(diǎn)方向搜索，這里引入人工勢場的思想對算法進(jìn)行改進(jìn)。在實(shí)時(shí)規(guī)劃起始點(diǎn)與目標(biāo)點(diǎn)之間構(gòu)造一個(gè)虛擬的引力場與勢力場，引力場的中心為目標(biāo)點(diǎn)，斥力場的中心為起始點(diǎn)。

3 航跡實(shí)時(shí)規(guī)劃的目標(biāo)函數(shù)

假設(shè)從節(jié)點(diǎn)ai開始實(shí)時(shí)規(guī)劃，即a1至ai-1的航路節(jié)點(diǎn)是已規(guī)劃好的航路節(jié)點(diǎn)，ai到目標(biāo)點(diǎn)的節(jié)點(diǎn)是未規(guī)劃的航路節(jié)點(diǎn)。改進(jìn)后的目標(biāo)函數(shù)為

其中，P1（li）表示編隊(duì)在航跡點(diǎn)ai及其航跡段li的航程威脅，P2（li）表示編隊(duì)在航跡點(diǎn)ai及其航跡段li的撞山威脅，P3（li）表示編隊(duì)在航跡點(diǎn)ai及其航跡段li的雷達(dá)網(wǎng)探測威脅，需要在節(jié)點(diǎn)處進(jìn)行干擾資源優(yōu)化分配，使探測威脅最小。

γ1、γ2、γ3、γ4、γ5表示 5 個(gè)指標(biāo)的權(quán)重系數(shù)且和為1，具體的數(shù)值根據(jù)任務(wù)性質(zhì)由專家打分法獲得，一般前3個(gè)較大。則目標(biāo)函數(shù)前3個(gè)為代價(jià)函數(shù)，后兩個(gè)為啟發(fā)函數(shù)。

P4（li）的定義如下：

式（4）中，R0代表以航跡目標(biāo)點(diǎn)為圓心的一個(gè)球體的半徑，Ri，z表示待規(guī)劃航跡點(diǎn)與航跡終點(diǎn)的距離，Ri，q表示待規(guī)劃航跡點(diǎn)與實(shí)時(shí)規(guī)劃航跡起點(diǎn)的距離。為了使目標(biāo)函數(shù)在離航跡終點(diǎn)越近時(shí)收斂速度越快，需要目標(biāo)函數(shù)隨著距離的減小而減小，因此，加入該指標(biāo)。

P5（li）的定義如下：

式（5）中，Rm（ai）表示節(jié)點(diǎn)ai與目標(biāo)點(diǎn)的距離，Rq（ai）表示節(jié)點(diǎn)ai與起始點(diǎn)的距離，k為人工勢場增益。該代價(jià)的定義包含了人工勢場的思想，可以使節(jié)點(diǎn)搜索方向朝著目標(biāo)點(diǎn)的方向。

4 航跡與干擾資源的實(shí)時(shí)規(guī)劃

采用改進(jìn)的稀疏A*算法來對節(jié)點(diǎn)進(jìn)行擴(kuò)展，算法步驟如下：

Step1：發(fā)現(xiàn)突發(fā)威脅時(shí)，對航跡實(shí)時(shí)規(guī)劃的起始節(jié)點(diǎn)進(jìn)行判斷，若為可飛節(jié)點(diǎn)，將其插入OPEN表中，同時(shí)將上一航跡段的節(jié)點(diǎn)從CLOESED表中刪除。

Step2：對OPEN表中的節(jié)點(diǎn)分別重新進(jìn)行干擾資源分配，計(jì)算節(jié)點(diǎn)及其航跡段對應(yīng)的目標(biāo)函數(shù)。將目標(biāo)函數(shù)值小的節(jié)點(diǎn)作為當(dāng)前航跡點(diǎn)，并放入CLOSED表中。

Step3：如果OPEN表中沒有節(jié)點(diǎn)，則表示搜索失敗，調(diào)整算法參數(shù)后重新進(jìn)行搜索。

Step4：如果下一個(gè)航跡節(jié)點(diǎn)即為目標(biāo)點(diǎn)，則表示搜索結(jié)束。

Step5：重復(fù)以上步驟，直到搜索失敗或?qū)ふ业骄植孔顑?yōu)航跡。若搜索失敗，則回到Step2。

5 仿真實(shí)驗(yàn)及結(jié)果分析

圖4 突發(fā)威脅示意圖1

圖5 突發(fā)威脅示意圖2

如圖4所示，編隊(duì)在突防過程中發(fā)現(xiàn)在山峰上出現(xiàn)了一部之前沒有得到任何相關(guān)信息的雷達(dá)5，且該雷達(dá)出現(xiàn)在前方航跡的附近。由于這種雷達(dá)一般是戰(zhàn)備的時(shí)候才使用，也是防止其他雷達(dá)失效或損毀而準(zhǔn)備的備用雷達(dá)，因此，這種雷達(dá)與其他4部雷達(dá)并沒有組網(wǎng)關(guān)系。但由于這部雷達(dá)較雷達(dá)4離航線更近，因此，需要重新優(yōu)化干擾策略，將雷達(dá)對編隊(duì)自身的探測降到最低。

圖6 編隊(duì)實(shí)時(shí)規(guī)劃航跡圖1

圖7 編隊(duì)實(shí)時(shí)規(guī)劃航跡圖2

圖6、圖7顯示了在出現(xiàn)新的突發(fā)威脅后，對局部航跡進(jìn)行實(shí)時(shí)在線實(shí)時(shí)規(guī)劃，得到的最優(yōu)航跡。與之前沒有出現(xiàn)突發(fā)威脅時(shí)施加干擾的事前規(guī)劃航跡進(jìn)行對比，可以看出航跡在雷達(dá)5處有一個(gè)向左的偏移。此時(shí)編隊(duì)為了降低雷達(dá)對編隊(duì)整體的探測威脅，增加了航程威脅。

圖8 實(shí)時(shí)規(guī)劃航跡探測威脅

圖9 實(shí)時(shí)規(guī)劃航跡綜合威脅

圖8顯示了航跡點(diǎn)與雷達(dá)探測威脅的關(guān)系。在整段航跡上，探測威脅較之前沒有出現(xiàn)新的雷達(dá)時(shí)有了明顯提升，尤其是在經(jīng)過雷達(dá)1、5、3時(shí)，探測威脅維持在了一個(gè)較高的水平，這也與預(yù)期估計(jì)的效果相符。之后隨著離雷達(dá)越來越遠(yuǎn)，探測威脅趨于穩(wěn)定。圖9則是表明了綜合威脅在航跡中的變化程度?？偟膩碚f，雖然新雷達(dá)的出現(xiàn)對我方的航跡規(guī)劃造成了一定的影響，但是通過局部實(shí)時(shí)規(guī)劃技術(shù)，將這種影響降到了最低的程度。

6 結(jié)論

本文首先對航跡實(shí)時(shí)規(guī)劃技術(shù)進(jìn)行了介紹，在事前規(guī)劃的基礎(chǔ)上，考慮了隨隊(duì)支援干擾編隊(duì)在突防過程中遭遇突發(fā)威脅的處理方法。之后建立了編隊(duì)航跡實(shí)時(shí)規(guī)劃的模型以及步驟。然后針對對抗態(tài)勢的變化，首先重新分配干擾資源，并對局部空間的威脅數(shù)據(jù)庫進(jìn)行更新，再進(jìn)行下一步航跡節(jié)點(diǎn)的規(guī)劃。最后利用改進(jìn)稀疏A*算法，對航跡進(jìn)行了實(shí)時(shí)規(guī)劃。仿真結(jié)果驗(yàn)證了算法的有效性。