基于戰術意圖欺騙的無人艦艇航路規劃算法*

安 彧，張抒塵，劉 顥，耿 亮，鞏慶濤

（1.湖北工業大學理學院，武漢 430068；2.上海交通大學電子信息與電氣工程學院，上海 200240；3.武漢數字工程研究所，武漢 430074；4.魯東大學山東省海上航天裝備技術創新中心，山東 煙臺 264025）

0 引言

隨著智能化技術在船舶領域的升級和發展，無人艦艇已經成為海戰場中越來越重要的元素，其具有不同于傳統艦艇的優勢，如較小的體積重量、靈活的機動性、優秀的自主導航能力［1］等。而航路規劃作為無人艦艇控制系統中的重要組成部分，對于保證無人艦艇的安全性、減少控制成本、提高任務執行效率和自動巡航都具有重要意義，是當前研究的熱點。

目前無人艦艇的航路規劃算法主要可分為兩類：基于仿生的智能算法和基于圖論的搜索算法。其中，基于仿生的智能算法包括蟻群算法、細菌覓食法、人工魚群法等。王成等通過使蟻群信息素的分配不均勻和加入懲罰機制，解決了陷入死鎖航路的問題。但由于蟻群算法對初始解依賴性較強，參數量大且難以設置，導致算法的易用性上受到了局限［2］。YANG L 等提出了一種細菌覓食算法用于無人艦艇的航路規劃，可以加快路徑搜索性能，提高收斂速度。但在理論上尚存在不足，難以給出具體數學模型［3］。LIAO Y 等提出了一種改進的人工魚群算法用于提高航路求解精度，并采用最小消耗誤差進行優化，使規劃出的航路更加符合任務期望［4］。但由于魚群的行為是隨機的，不同的初始值仍會使結果出現差異?？偟膩碚f，仿生智能算法主要源自于大自然規律和生物行為，具有處理動態環境能力強、處理復雜規劃問題能力好的優點；但也普遍存在參數設置復雜、時間復雜度高以及較為依賴人工設置特征函數等缺點，在易用性和適用泛性上存在較大局限。

基于圖論的搜索算法具有搜索范圍廣、效率高、理論基礎充分和易于實現等優點，包括RRT 算法、Dijkstra 算法和A*算法等，這類算法相比仿生智能算法，有更強的可解釋性和易用性。LI J 等提出了一種基于角度距離的RRT 算法，提高了相鄰節點間的搜索速度［5］；但由于搜索是隨機的，該方法難以找出精確最短航路。呂成采用Dijkstra 算法建立了極區環境的航路規劃方法，將環境阻力納入考慮范圍，增加了算法可拓性［6］，但由于該算法僅根據廣度搜索策略進行節點搜索，在效率上不夠優秀。A*算法是一種效率高、靈活性強、工程實現容易的最短路徑搜索算法，其引入了啟發函數用于引導搜索，可快速地完成規劃任務［7］。且由于啟發函數的存在，A*算法還具有極強的可適性和拓展性，可根據實際需求靈活調整搜索范圍，以適應規劃需求。TANG R X 等通過提出雙向搜索和引導線的概念改進了A*算法，優化了算法效率及空間復雜度［8］。鄭煜坤等提出了一種基于追蹤模型方程改進的A*算法，使其能夠進一步縮短彎折處的路徑長度，并提高了避障能力［9］。

可見，目前研究中對于A* 算法的主要改進方向仍是優化其算法效率和路徑長度，這種改進難以滿足實際海上作戰中航路規劃問題的需求。對于海戰場而言，意圖欺騙是一種非常重要的作戰手段；通過意圖欺騙，可以讓敵方產生偏差，對方真實戰術意圖產生誤判，從而提高我方的作戰勝算概率。因此，為在實際作戰中規劃出一條帶有意圖欺騙性的最優無人艦艇航路，聯系A* 算法較強的拓展性與可適性，本文嘗試對A* 算法進行改進，試圖提出一種基于概率性意圖欺騙（probabilistic intentional deception，PID）代價函數的DTI-A*（deception of tactical intention-A*）算法，使算法在保留傳統A*算法優點的基礎上，能夠規劃出一條既能控制長度成本，又能滿足欺騙需求的最優決策航路，從而幫助己方無人艦艇隱瞞真實意圖，順利完成戰術任務。

1 欺騙性航路規劃模型

基本航路規劃問題的本質是在一個環境地圖中從給定的起點到給定的終點之間尋找最優路徑?？捎萌M來描述［10］：

〈D，s，gr〉

其中，s 為給定的起點，gr為真實目標點，D 為規劃域，有：

N 為地圖中非空節點的集合，E 為節點與節點之間邊的集合，c 為邊的長度代價。

對于通過規劃域D 所規劃出的一條航路d，本質上是一個非空節點構成的序列d=n1，n2，…，nk，整條航路d 的代價cost（d）等于路徑中每條邊的代價和，即：

其中，di表示路徑d 中的第i 個節點，有i∈｛0，1，…，k-1｝；（di，di+1）表示路徑中節點之間的邊c（di，di+1），表示節點di與di+1之間的邊的代價，對于基本的航路規劃，邊的代價通常為邊的長度。

相比于基本航路規劃問題，意圖欺騙性航路的規劃問題還要額外考慮3 個因素指標［11］：用來欺騙敵方的虛假目標點、節點對應各目標的概率分布以及各節點的欺騙性能。其元組表示形式如下：

其中，〈D，s，gr〉為基本航路規劃問題；gf為虛假目標點，為異于真實目標點gr的一個非空節點，通常由指揮官和專家根據戰場態勢確定；p 為節點對應目標概率分布；c'為考慮了節點欺騙性能后的代價。

2 A*算法基本原理

A*算法是一種高效、直接的啟發式搜索算法。其原理是以起始節點為第一個搜索點，向其周圍待搜索節點拓延并將周圍節點納入搜索域，隨后通過代價函數計算搜索域內各節點的估計代價，并選取估計代價最小的節點作為下一個搜索點，不斷重復此步驟，直至搜索到目標節點時便可生成一條最優航路。

在柵格地圖中，各節點為柵格的中心點，A*算法在從當前搜索點nnow向周圍節點進行拓延搜索時，其搜索規則如圖1 所示，會將周圍上、下、左、右、上左、上右、下左、下右共8 個方位的節點納入搜索域：

圖1 A*算法拓延搜索示意圖Fig.1 Illustration of A*algorithm with extended search

代價函數f（n）影響著搜索點的確定規則，它對A*算法至關重要，對于傳統A*算法而言，其代價函數形式為［5］：

其中，f（n）為總代價函數，g（n）為實價函數，表示待搜索節點n 到起始節點的實際代價，h（n）為啟發函數，也稱估價函數，是決定A*算法搜索精度的關鍵，通過啟發函數可計算節點n 的估計代價值，得到啟發信息。

傳統A*算法的實價函數g（n）通常是通過累加邊權來計算的，而啟發函數h（n）的估計值則是通過曼哈頓距離（Manhattan distance）、歐幾里得距離（Euclidean distance）等來計算，以歐幾里得距離為例，對應的啟發函數表達式為［9］：

其中，nx、ny為待搜索節點n 的橫縱坐標，gx、gy為最終目標點的橫縱坐標。

3 基于戰術意圖欺騙的DTI-A＊航路規劃算法

3.1 基于目標概率差值的欺騙性能表征方法

欺騙性航路規劃需要對無人艦艇周圍的環境空間進行柵格化離散處理，并對各柵格的中心節點進行欺騙性能表征。利用無人艦艇在各節點上可能前往的終點目標概率來進行節點欺騙性能表征：設共有m 個可能存在的目標，則地圖中的任意一個節點所對應的目標概率分布可由節點到各目標的距離長度計算得出，其式為：

其中，gi為可能的任意一個目標（i=0，1，…，m），為節點對應的目標為gi時的概率，li表示節點到目標gi的最短路徑長度。

由此，節點欺騙性能值可借助節點對應目標概率的差值來表征，其含義為節點在航路規劃問題中欺騙性能的優劣，表達式為：

其中，dp（n）表示節點n 的欺騙性能值，值越大代表節點n 的欺騙效果越好，p（gi）、p（gr）分別為節點n對應的虛假目標概率和真實目標概率。通過該計算過程，可得到無人艦艇在行駛到各節點時的意圖欺騙性，完成作戰空間欺騙性能的離散表征。

3.2 PID 代價函數的構建與融入

為使規劃出的航路具有意圖欺騙性，構建PID代價函數融入算法，PID 代價值應與節點的欺騙性能值dp（n）呈負相關，即節點的欺騙性能越好，其PID 代價就越低，考慮代價函數的收斂性，設定PID代價函數表達式如下：

其中，gi、gr分別代表真實目標點和虛假目標點，dp（n）表示節點n 的欺騙性能值。

由式（7）可見：當節點n 越靠近真實目標點時，根據式（5）和式（6）可知，其對應的真實目標概率p（gr）越大，欺騙性能值dp（n）越小，此時的PID（n）也越大；反之，當節點n 越靠近虛假目標點時，其PID（n）就越小。

在式（3）中，傳統A*算法考慮的節點代價完全是從航路的距離長度出發，規劃出的最優解為一條總長度距離最短的航路。距離長度成本是航路規劃中必須考慮的問題，降低航路距離可以提升無人艦艇的作戰效率，為保持這一特性，綜合考慮航路距離長度和欺騙性兩個因素，在傳統A*算法代價函數中融入PID 代價作為DTI-A*算法的代價函數，如式（8）所示：

其中，g（n），h（n）為傳統A*算法中的實價函數與估價函數；考慮無人艦艇的航行方向可以斜對角移動，h（n）取式（4）的歐幾里得距離。

e 為欺騙因子，值為一個大于等于1 的常系數。當e 取值越小，PID 代價的權重越小，則代表在航路規劃中更多考慮航路的距離成本而非欺騙效果；相反，當e 取值較大時，則代表在規劃時更多考慮航路的欺騙性。通過對e 數值的調整，可以實現不同強度的戰術意圖欺騙策略，e 值越大，則規劃出的航路，欺騙時間往往就越長，二者總體呈正相關。但由于不同戰場任務對航路欺騙性的閾值定于不同，具體e 值需要結合戰場任務條件來進行設定，以達到期望的欺騙時間。

3.3 算法流程

本文提出的DTI-A*算法沿用傳統A*算法中對代搜索節點的處理方式，即使用開放列表（open list）和封閉列表（close list）對節點進行管理。開放列表中的節點為正在被搜索的，其初始值為起始節點，而封閉列表中的節點為已經搜索過的。算法流程圖如圖2 所示。

圖2 DTI-A*算法流程圖Fig.2 The flowchart of DTI-A*algorithm

4 航路規劃算法仿真

為驗證DTI-A*算法性能，從Moving-AI 地圖測試集［12］中隨機抽取出一副水域環境地圖，采用正四邊形柵格對其進行柵格化處理進行仿真實驗，每個正四邊形的中心點為節點。仿真在Ubuntu20.04、Intel Core i5-8300H CPU@2.30Ghz、16GB RAM 的計算機環境下進行。

4.1 仿真設計

為模擬真實水面戰場環境，融入戰場態勢信息，在某次作戰任務中：節點（2，11）設為我方無人艦船起始節點，以船標表示；節點（18，17）設為真實目標點，以綠色表示；節點（18，5）設為虛假目標點，以紫色表示；中間3×3 的紅色區域為敵方警戒區，我方艦船不能經過，屬于不可通行區域。為使模型更貼合實際，還需作出如下戰場條件假設：

1）敵方的航路意圖識別器采用基于代價的快速航路意圖識別方法［13］。

2）航路被識別出的“攻擊真實目標點概率”小于0.5 時，視為航路具有欺騙性；大于0.5 時敵方會采取防御手段，采取防御手段10 min 后若我方無人艦艇仍未到達真實目標點，視為任務失敗。

3）無人艦船可在各相鄰節點間進行單位直線移動和單位斜線移動，且所需時間都為1 min。

融入戰場態勢信息后的柵格化環境地圖如圖3所示。

圖3 融合了戰場態勢信息的柵格地圖Fig.3 Grid map fused with battlefield situation information

4.2 仿真結果分析

為模擬不同強度的戰術意圖欺騙策略，將式（9）中欺騙因子e 分別設定為1、2、3，模擬輕度欺騙、中度欺騙和重度欺騙3 種策略。在圖3 的戰場態勢柵格地圖上分別對蟻群算法、傳統A*算法和本文提出的DTI-A*算法進行仿真驗證，其中蟻群算法的主要參數設定為：信息素重要程度因子alpha為1，啟發函數重要程度因子beta 為2，螞蟻數量20，迭代次數50，測試結果如圖4 所示。

圖4 各種算法規劃的航路對比圖Fig.4 Comparison of routes planned by various kinds of algorithms

通過意圖識別器對不同航路進行航路終點意圖識別，識別結果如圖5 所示。

圖5 5 條航路的意圖識別結果Fig.5 Intent recognition results of the five flight routes

將上述信息轉化為表格，各航路的質量對比如表1 所示。

表1 5 條航路對比Table 1 Comparison five routes

通過表1 中的指標可知：本文提出的DTI-A*算法相比傳統A*算法和蟻群算法，可以將任務結果從失敗變為成功。在設定不同的欺騙因子時，可實現不同強度的欺騙策略，隨著欺騙策略強度的增加（欺騙因子e 的增大），航路的欺騙性能也會顯著提升，最多可使敵方在第22 min 時才采取防御手段，使航路欺騙時間占比增加77.78%，被識別出的攻擊真實目標點的概率最小值降至0.07。這意味著DTI-A*算法可以很好地延誤敵方采取反制防御手段的時間，滿足意圖欺騙性航路規劃問題的需求，能夠極大程度提升無人艦艇執行作戰任務的成功率。

5 結論

針對“現有研究對A*算法的改進方向難以滿足航路意圖欺騙需求”這一局限性，為實現無人艦艇在水面戰場中的航路戰術意圖欺騙，本文重點研究了基于欺騙思想的航路規劃算法。相比現有研究，本文構建了欺騙航路規劃模型，探索性地提出了作戰空間節點欺騙性能的表征方法，以此構建和融入PID 代價函數來實現欺騙航路規劃算法DTI-A*。

通過仿真實驗驗證，本文提出的DTI-A*算法延長了欺騙時間及其占比，極大降低了攻擊真實目標點被識別的概率，可使任務執行結果由失敗轉為成功；相比其他航路規劃算法，能夠有效提高水面戰場中無人艦艇的欺騙性航路規劃質量，這對于在未來的海戰場中增強我方作戰能力和信息化水平、提高我方電子戰裝備的智能化程度具有現實意義，力圖為維護海上安全、完成海上作戰任務做出更大的貢獻。在未來的研究中，將在欺騙航路規劃模型中可以探索更多的參數設置和優化策略，進一步提高欺騙性能并適應更加復雜的水面戰場環境。