基于改進(jìn)A*算法的路徑規(guī)劃在海戰(zhàn)兵棋推演中的應(yīng)用

張韜， 項祺， 鄭婉文， 孫宇祥， 周獻(xiàn)中,2

(1.南京大學(xué) 工程管理學(xué)院， 江蘇 南京 210093； 2.南京大學(xué) 智能裝備新技術(shù)研究中心， 江蘇 南京 210093)

0 引言

隨著Alpha Go程序的問世，其方法創(chuàng)新、技術(shù)突破和認(rèn)識論上的進(jìn)步都給兵棋推演領(lǐng)域帶來了新的熱潮和機(jī)遇。在軍事智能化發(fā)展的大趨勢和計算機(jī)廣泛普及的大背景下，計算機(jī)兵棋推演既是戰(zhàn)爭推演、戰(zhàn)術(shù)設(shè)計和技術(shù)驗證等領(lǐng)域的一種重要輔助手段，又是全民學(xué)軍事、學(xué)戰(zhàn)例、提高國防意識、開展國防教育與軍事科普的一種有效手段。

路徑規(guī)劃作為計算機(jī)兵棋推演的重要組成部分，其主要任務(wù)是根據(jù)不同的推演地圖，在起始點(diǎn)和終止點(diǎn)之間快速規(guī)劃一條由多個路徑點(diǎn)依次連接而成的最優(yōu)路徑。在兵棋推演的背景下，最優(yōu)路徑的含義不僅是兩點(diǎn)之間的距離最短，而且是綜合考慮距離、裝備效能和威脅等因素后的最優(yōu)路線。

A算法作為一種智能啟發(fā)式算法，因其良好的通用性和拓展性，已廣泛應(yīng)用于物流運(yùn)輸、建筑工程、巖石工程、物聯(lián)網(wǎng)、航空航天和無人駕駛等眾多領(lǐng)域。又因為回合制兵棋推演中靜態(tài)路徑規(guī)劃的需求，本文嘗試將A算法引入海戰(zhàn)兵棋推演的最優(yōu)路徑規(guī)劃中，解決棋子的路徑選擇問題。在兵棋推演過程中，由于推演地圖的特殊類型和對路徑方案的多目標(biāo)需求，傳統(tǒng)A算法無法有效解決兵棋推演中的路徑規(guī)劃問題。針對上述問題，本文對A算法進(jìn)行了優(yōu)化改進(jìn)：通過增加地圖信息映射機(jī)制，解決了A算法正六邊形柵格地圖中的應(yīng)用問題；通過改進(jìn)估價函數(shù)的設(shè)置，提高了海戰(zhàn)兵棋推演中的路徑規(guī)劃質(zhì)量，保證了最優(yōu)路徑方案的生成。

1 海戰(zhàn)兵棋推演的環(huán)境

本文使用的推演環(huán)境為第二屆全國“先知·兵圣”人機(jī)對抗挑戰(zhàn)賽提供的“中國艦隊”回合制海軍戰(zhàn)術(shù)兵棋推演平臺。

該推演平臺使用的地圖類型是目前兵棋推演中常見的正六邊形柵格地圖，如圖1所示。該推演平臺使用的柵格共有6種屬性。

圖1 推演地圖示例Fig.1 Example ofwar gaming map

該推演平臺中的棋子共分為水面單位、空中單位、水下單位、岸基單位和基地單位5個大類。棋子的狀態(tài)可分為完好、受損和戰(zhàn)毀3個類別，棋子的狀態(tài)將直接影響其屬性的高低。棋子的屬性可分為機(jī)動、偵察、攻擊和防御4個主要類別。根據(jù)棋子的屬性，不同類型柵格將對棋子產(chǎn)生不同的影響，例如區(qū)域不可達(dá)、增加被敵方發(fā)現(xiàn)的可能性和增加被攻擊時的毀傷概率。

隨著推演的進(jìn)行，推演雙方可以通過擊傷、擊毀敵方棋子，或者奪取奪控點(diǎn)而得到相應(yīng)的分?jǐn)?shù)；當(dāng)推演結(jié)束時，得分高者獲勝。根據(jù)勝負(fù)的判定規(guī)則，推演雙方的目標(biāo)均為保證己方棋子盡可能少地受到攻擊，盡可能多地打擊敵方棋子，并盡可能多地占領(lǐng)奪控點(diǎn)。為了達(dá)成該目標(biāo)，推演中使用的路徑方案需要有意識地避讓不利于己方棋子生存的區(qū)域。

2 路徑規(guī)劃算法設(shè)計

2.1 A*算法的原理

A算法是一種由Hart等在文獻(xiàn)[16]中提出的智能啟發(fā)式搜索算法，可用于在靜態(tài)路網(wǎng)中實現(xiàn)全局路徑規(guī)劃。A算法的算法流程是從起始節(jié)點(diǎn)開始向相鄰節(jié)點(diǎn)拓展；對于待拓展節(jié)點(diǎn)，通過估價函數(shù)()計算該節(jié)點(diǎn)的估計代價，從周圍節(jié)點(diǎn)中選擇擁有最小估計代價的節(jié)點(diǎn)作為下一個拓展節(jié)點(diǎn)；重復(fù)上一過程，當(dāng)搜索到目標(biāo)節(jié)點(diǎn)時便可生成最優(yōu)路徑。估價函數(shù)()用于確定拓展方向，是A算法的重要組成部分，其一般形式為

()=()+()

(1)

式中：()表示實價函數(shù)，用于計算從起始節(jié)點(diǎn)至到達(dá)待拓展節(jié)點(diǎn)的實際代價；()表示啟發(fā)函數(shù)，用于計算從待拓展節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計代價，即啟發(fā)信息。

為了能讓A算法總能得到正確的最優(yōu)路徑，啟發(fā)函數(shù)()對于路徑探索過程中的任意節(jié)點(diǎn)必須滿足(2)式：

()≤()

(2)

式中：()表示任意節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計代價；()表示節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的實際最小代價。

傳統(tǒng)A算法通常采用實際距離來表示實際代價，采用歐氏距離或者曼哈頓距離來表示啟發(fā)信息。以歐氏距離為例，對應(yīng)的啟發(fā)函數(shù)()如(3)式所示：

(3)

式中：、分別表示待拓展節(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)；、分別表示目標(biāo)節(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)。

傳統(tǒng)A算法從當(dāng)前節(jié)點(diǎn)進(jìn)行拓展時，需要搜索如圖2所示的8個相鄰節(jié)點(diǎn)，包括左上方節(jié)點(diǎn)、上方節(jié)點(diǎn)、右上方節(jié)點(diǎn)、右方節(jié)點(diǎn)、右下方節(jié)點(diǎn)、下方節(jié)點(diǎn)、左下方節(jié)點(diǎn)和左方節(jié)點(diǎn)。

圖2 傳統(tǒng)A*算法的節(jié)點(diǎn)拓展示意圖Fig.2 Node expansion diagram of classical A* algorithm

2.2 A*算法的改進(jìn)優(yōu)化

2.2.1 映射機(jī)制的構(gòu)建

柵格法是環(huán)境建模的經(jīng)典方法，該方法使用柵格對環(huán)境信息進(jìn)行表示。兵棋推演中大量使用柵格法構(gòu)建推演地圖，傳統(tǒng)A算法也通常使用柵格法量化提取地圖信息，但二者使用的柵格類型不同。兵棋推演正如本文涉及的推演平臺，通常使用正六邊形柵格地圖，而傳統(tǒng)A算法則使用正四邊形柵格地圖。因此，本文首先需要在兩種地圖間構(gòu)建一種映射機(jī)制，使A算法的環(huán)境模型適應(yīng)兵棋推演環(huán)境。

為了讓A算法能夠處理推演地圖，本文將推演地圖的六角格按序映射至A地圖的四角格。以圖3為例：圖3(a)為處理前的正六邊形柵格地圖，圖3(b)為處理后的正四邊形柵格地圖。推演地圖中每個柵格的坐標(biāo)按照推演平臺的規(guī)則確定；推演地圖中的六角格按照其坐標(biāo)映射到A地圖中具有相同坐標(biāo)的位置。

圖3 地圖信息映射的示例Fig.3 An example of map information mapping

由于上述映射機(jī)制改變了節(jié)點(diǎn)之間的相鄰關(guān)系，需要從四角格坐標(biāo)的角度解析相鄰六角格之間的坐標(biāo)關(guān)系。四角格節(jié)點(diǎn)進(jìn)行拓展時，需要搜索周圍的8個節(jié)點(diǎn)；六角格節(jié)點(diǎn)進(jìn)行拓展時，需要搜索如圖4所示的6個相鄰節(jié)點(diǎn)。

圖4 改進(jìn)A*算法節(jié)點(diǎn)拓展示意圖Fig.4 Node expansion diagram of improved A* algorithm

假設(shè)的坐標(biāo)為(,)，則的坐標(biāo)為(-1,)，的坐標(biāo)為(+1,)。六角格的排列方式導(dǎo)致了剩下4個節(jié)點(diǎn)的坐標(biāo)與的取值有關(guān)。當(dāng)為偶數(shù)時，的坐標(biāo)為(,+1)，的坐標(biāo)為(+1,+1)，的坐標(biāo)為(+1,-1)，的坐標(biāo)為(,-1)；當(dāng)為奇數(shù)時，的坐標(biāo)為(-1,+1)，的坐標(biāo)為(,+1)，的坐標(biāo)為(,-1)，的坐標(biāo)為(-1,-1)。

通過構(gòu)建上述映射機(jī)制，即可實現(xiàn)A算法在正六邊形柵格地圖上的初步應(yīng)用。

222 估價函數(shù)的構(gòu)建

傳統(tǒng)A算法以路徑最短為目標(biāo)，而僅以路徑最短為目標(biāo)搜索得到的路徑無法滿足海戰(zhàn)兵棋推演的需求。在海戰(zhàn)兵棋推演中，不同的海域類型和與敵方棋子的距離也將直接影響己方棋子在裁決時的點(diǎn)數(shù)修正，進(jìn)而影響戰(zhàn)斗的結(jié)果。因此，本文選出3個指標(biāo)作為路徑規(guī)劃時需要考慮的因素和評價路徑方案質(zhì)量的依據(jù)，對各指標(biāo)進(jìn)行定義。

路徑長度指數(shù)。路徑長度指數(shù)，簡稱路徑指數(shù)，表示棋子從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的過程中需要經(jīng)過的路徑長度，其表達(dá)式如(4)式所示：

(4)

式中：()表示該路徑的路徑長度指數(shù)，其值越大表示路徑長度越大、路徑質(zhì)量越差,表示路徑的末端節(jié)點(diǎn)，且編號為不小于2的整數(shù)；|-1·|表示從節(jié)點(diǎn)-1到節(jié)點(diǎn)的路徑長度，根據(jù)本文涉及的推演平臺可知該值為1，表示路徑上編號為的節(jié)點(diǎn)，∈[1,]。

根據(jù)路徑長度指數(shù)的定義可知：在其他條件相同的情況下，應(yīng)選擇擁有較小路徑長度指數(shù)的路徑方案，保證能及時到達(dá)指定地點(diǎn)的同時節(jié)省我方棋子的機(jī)動值。路徑長度指數(shù)與傳統(tǒng)A算法中的實價函數(shù)相同。

裝備限制指數(shù)。裝備限制指數(shù)，簡稱裝備指數(shù)，表示棋子從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的過程中各個海域類型對棋子性能或裝備效能的影響情況，其表達(dá)式如(5)式所示：

(5)

式中：()表示該路徑的裝備限制指數(shù)，其值越大表示棋子性能或裝備效能被限制得越嚴(yán)重、路徑質(zhì)量越差；()表示節(jié)點(diǎn)對棋子性能或裝備效能的影響，取值與棋子類別和節(jié)點(diǎn)的海域類型有關(guān)，取值范圍為[0,1]。需要注意的是：若某個節(jié)點(diǎn)的裝備指數(shù)為1，則表示棋子不可到達(dá)該節(jié)點(diǎn)；一個可行路徑方案中每個節(jié)點(diǎn)的裝備指數(shù)都應(yīng)小于1。

與實際戰(zhàn)爭一樣，兵棋推演中也充滿著不確定性。因此，在其他條件相同的情況下，應(yīng)選擇能最大程度地發(fā)揮棋子性能或裝備效能的路徑方案，保證我方棋子以相對較好的狀態(tài)應(yīng)對突發(fā)情況。

敵方威脅指數(shù)。敵方威脅指數(shù)，簡稱威脅指數(shù)，表示棋子從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的過程中受敵方棋子威脅程度的總和，其表達(dá)式如(6)式所示：

(6)

式中：()表示該路徑的敵方威脅指數(shù)，其值越大表示我方棋子被擊毀的可能性越大、路徑質(zhì)量越差；()表示棋子在節(jié)點(diǎn)受敵方棋子威脅的程度，其取值范圍為[0,1]。需要注意的是：若某個節(jié)點(diǎn)的威脅指數(shù)為1，則表示我方棋子在該節(jié)點(diǎn)處將被擊毀；在正常情況下，一個路徑方案中每個節(jié)點(diǎn)的威脅指數(shù)都應(yīng)小于1。

根據(jù)敵方威脅指數(shù)的定義可知：在其他條件相同的情況下，應(yīng)選擇擁有較小敵方威脅指數(shù)的路徑方案，保證我方棋子的存活。

綜合考慮路徑長度指數(shù)、裝備限制指數(shù)和敵方威脅指數(shù)3個因素，本文改進(jìn)A算法中的實價函數(shù)如(7)式所示：

()=·()+·()+·()

(7)

式中：()亦可稱為總評價指數(shù)，用于評價路徑方案的質(zhì)量，其值越小表明路徑方案的質(zhì)量越高，即路徑方案更優(yōu)；()表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)的實際路徑長度指數(shù)；()表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)的實際裝備效能指數(shù)；()表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)的實際敵方威脅指數(shù)；、和分別表示對應(yīng)指數(shù)的修正系數(shù)，三者的關(guān)系如(8)式所示：

(8)

、和取值大小表示對應(yīng)指數(shù)在實價函數(shù)中的重要性，可根據(jù)棋子屬性和當(dāng)前態(tài)勢等信息，由指揮員或者領(lǐng)域?qū)＜掖_定。

針對本文正六邊形柵格地圖的類型，在立方體坐標(biāo)系下可以計算出任意2個柵格之間的準(zhǔn)確距離，而在21節(jié)涉及的笛卡爾坐標(biāo)系下則不能。立方體坐標(biāo)系下任意兩點(diǎn)(,,)和(,,)之間的距離如(9)式所示：

(9)

假設(shè)笛卡爾坐標(biāo)系中某點(diǎn)的坐標(biāo)為(,)，與之對應(yīng)的立方體坐標(biāo)為(,,)，則二者的轉(zhuǎn)換關(guān)系如(10)式所示：

(10)

式中：&表示按位與運(yùn)算，即參加運(yùn)算的2個數(shù)按二進(jìn)制位進(jìn)行與運(yùn)算。

結(jié)合海戰(zhàn)兵棋推演的特點(diǎn)和(9)式、(10)式，本文設(shè)計的啟發(fā)函數(shù)()如(11)式所示：

()=·((-)+(-+
(+&1--&1)2)+
(-+-+
(+&1--&1)2))2

(11)

式中：修正系數(shù)與(7)式中路徑長度指數(shù)的修正指數(shù)相同。由于裝備限制指數(shù)和敵方威脅指數(shù)具有較大的不確定性，本文沒有將其納入啟發(fā)函數(shù)中。

根據(jù)啟發(fā)函數(shù)的性質(zhì)和本文背景，可得到如下定理1。

對于路徑方案={,,…,}中的任意節(jié)點(diǎn)，不等式()≤()在正六邊形柵格地圖中恒成立。其中，()表示本文構(gòu)建的啟發(fā)函數(shù)。

該定理可用數(shù)學(xué)歸納法證明，具體的證明過程如下。

當(dāng)=時，()≤()顯然成立。

合作小組組長不僅要有管理，還要有示范。既然是示范，就要有一定標(biāo)準(zhǔn)。為此，我要求小亮做3個工作：一是對自己進(jìn)行“全身體檢”，檢查自己存在哪些問題，必要時做全面整改；二是密切注意其他3位成員的表現(xiàn)，在看得見的地方，不能做得比他們差；三是做人做事要有底線，不能突破底線。

假設(shè)當(dāng)=+1時，定理1成立。

根據(jù)(11)式可得()≤(+1)+；

又根據(jù)(7)式可得(+1)+≤()，

則(+1)≤(+1)

?(+1)+≤(+1)+

?()≤()

因此，當(dāng)=時定理1成立。證畢。

根據(jù)定理1可知，本文構(gòu)建的啟發(fā)函數(shù)符合(2)式中對啟發(fā)函數(shù)的限制，即保證了本文提出的改進(jìn)A算法在求解最優(yōu)路徑方案時的正確性。

通過構(gòu)建上述實價函數(shù)，可以滿足兵棋推演中對路徑方案的多目標(biāo)需求；通過構(gòu)建上述啟發(fā)函數(shù)，可以保證最優(yōu)路徑方案的生成。綜合實價函數(shù)和啟發(fā)函數(shù)，本文提出的估價函數(shù)如(12)式所示：

()=()+()

(12)

2.2.3 算法流程

本文改進(jìn)A算法沿用傳統(tǒng)A算法中對節(jié)點(diǎn)的管理方式，即使用open表管理正在探索的節(jié)點(diǎn)、closed表管理探索過的節(jié)點(diǎn)。算法流程如圖5所示。

圖5 改進(jìn)A*算法流程圖Fig.5 Flow chart of improved A* algorithm

具體步驟如下：

提取推演地圖中的信息，建立符合A算法要求的環(huán)境模型。

構(gòu)建估價函數(shù)，初始化open表和closed表，計算起始節(jié)點(diǎn)的估計代價并將其放入open表中。

判斷open表是否為空。若open表不為空，則執(zhí)行步驟4；若open表為空，則因無法搜索到可行路線而結(jié)束。

在open表中選取具有最小估計代價的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，并將該節(jié)點(diǎn)從open表移至closed表。

使用本文估價函數(shù)計算周圍節(jié)點(diǎn)的估計代價，并將其存入open表中。拓展方式如圖4所示。需要注意的是：在拓展節(jié)點(diǎn)時，若節(jié)點(diǎn)已在open表中，則需要重新計算其估計代價并據(jù)此判斷是否需要更新其父節(jié)點(diǎn)；若節(jié)點(diǎn)的裝備限制指數(shù)或者敵方威脅指數(shù)為1，則直接將該節(jié)點(diǎn)移至closed表中。

判斷是否到達(dá)目標(biāo)節(jié)點(diǎn)。若已到達(dá)，則執(zhí)行步驟7；否則返回步驟3重復(fù)操作。

保存規(guī)劃的路徑。從目標(biāo)節(jié)點(diǎn)開始，按每個節(jié)點(diǎn)的父節(jié)點(diǎn)回溯至起始節(jié)點(diǎn)，即可得到相應(yīng)的路徑。

3 實驗與分析

本文在推演平臺提供的地圖上對改進(jìn)A算法進(jìn)行了效果驗證。

在兵棋推演中，由于每類棋子具有其特定的屬性特點(diǎn)，不同類型的棋子評價同一路徑方案的結(jié)果不同，即需要針對每類棋子給各類節(jié)點(diǎn)的3個指數(shù)設(shè)置特定的參數(shù)。以更適合深海機(jī)動的棋子A和更適合淺海機(jī)動的棋子B為例，總評價指數(shù)中各參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

在相同起點(diǎn)和終點(diǎn)的情況下，本文讓棋子分別用具有傳統(tǒng)估價函數(shù)的A算法(簡稱傳統(tǒng)A算法)和改進(jìn)A算法生成路徑方案。實驗1是棋子A和棋子B使用傳統(tǒng)A算法在兩種地圖下進(jìn)行路徑規(guī)劃，其路徑方案如圖6所示。由于傳統(tǒng)A算法僅考慮路徑長度因素，棋子A和棋子B的路徑方案是一樣的。實驗2是棋子A使用改進(jìn)A算法在兩種地圖下進(jìn)行路徑規(guī)劃，其路徑方案如圖7所示。實驗3是棋子B使用改進(jìn)A算法在兩種地圖下進(jìn)行路徑規(guī)劃，其路徑方案如圖8所示。

圖6 棋子A和棋子B使用傳統(tǒng)A*算法進(jìn)行路徑規(guī)劃(實驗1)Fig.6 Operator A and Operator B using traditional A* algorithm for path planning (Experiment 1)

圖7 棋子A使用改進(jìn)A*算法進(jìn)行路徑規(guī)劃(實驗2)Fig.7 Operator A using improved A* algorithm for path planning (Experiment 2)

圖8 棋子B使用改進(jìn)A*算法進(jìn)行路徑規(guī)劃(實驗3)Fig.8 Operator B using improved A* algorithm for path planning (Experiment 3)

實驗1、實驗2和實驗3的結(jié)果數(shù)據(jù)分別如表2、表3和表4所示。表2和表3中的百分比表示改進(jìn)A算法相對于傳統(tǒng)A算法的性能提升。

表2 實驗1的結(jié)果

表3 實驗2結(jié)果及其相對實驗1結(jié)果的提升幅度

表4 實驗3結(jié)果及其相對實驗1結(jié)果的提升幅度

通過實驗2和實驗3的對比可知，改進(jìn)A算法可以為不同類型的棋子提供符合其特性的路徑方案。分析表3和表4的數(shù)據(jù)可知，在不同類型的棋子上，本文提出的改進(jìn)A算法較傳統(tǒng)A算法而言，除了路徑指數(shù)外，裝備指數(shù)、威脅指數(shù)和總評價指數(shù)都出現(xiàn)了不同程度的降低。根據(jù)2.2.2節(jié)中對這4個指數(shù)的定義，本文改進(jìn)A算法雖然在路徑指數(shù)部分的性能略有下降，但是在裝備指數(shù)和威脅指數(shù)部分的性能都有大幅度提升，且總評價指數(shù)所表示的路徑方案質(zhì)量也得到了提高。此外，生成實驗中路徑方案的用時均小于0.5 s. 總之，本文改進(jìn)A算法可以實現(xiàn)對3個指標(biāo)的較好平衡且能結(jié)合不同棋子類型的特性規(guī)劃出各自最佳路徑，與傳統(tǒng)A算法中只關(guān)注路徑的長度不同，在提高路徑方案質(zhì)量的同時也更加符合實際兵棋推演的需求。

4 結(jié)論

本文在傳統(tǒng)A算法基礎(chǔ)上引入地圖信息映射機(jī)制，提出既能滿足多目標(biāo)需求又能保證生成最優(yōu)路徑的估價函數(shù)，使改進(jìn)A算法可高效地用于海戰(zhàn)兵棋推演中的路徑規(guī)劃任務(wù)。得出主要結(jié)論如下：

1)本文算法可按照棋子屬性和當(dāng)前態(tài)勢等信息提供符合其需求的路徑方案，有效地提高了海戰(zhàn)兵棋推演中路徑規(guī)劃的質(zhì)量。

2)本文工作使A算法更加契合海戰(zhàn)兵棋推演的需要，進(jìn)一步優(yōu)化了實際推演過程中的路徑規(guī)劃模塊。

3)本文研究成果已成功運(yùn)用于第二屆全國“先知·兵圣”人機(jī)對抗挑戰(zhàn)賽的海戰(zhàn)比賽中，并且所屬團(tuán)隊在全國“先知·兵圣”群隊級兵棋推演中獲得了智能AI優(yōu)良獎。