鄧 青，薛 青，陳 琳，陳 俊

(1.陸軍裝甲兵學(xué)院， 北京 100072； 2．陸軍指揮學(xué)院，南京 210045)

裝甲車輛計(jì)算機(jī)生成兵力(Computer Generated Forces,CGF)面臨的虛擬戰(zhàn)場環(huán)境異常復(fù)雜，包含了真實(shí)戰(zhàn)場環(huán)境的大部分要素[1]，例如地形地貌、道路、建筑、水系、植被、障礙物、彈坑等等。規(guī)劃約束條件多，并且戰(zhàn)場環(huán)境具有不確定性，例如某一時(shí)刻，裝甲車輛CGF在沿著規(guī)劃好的路徑行進(jìn)時(shí)，前方出現(xiàn)了新的彈坑，構(gòu)成車輛前進(jìn)的障礙，為避開障礙物就需要重新進(jìn)行路徑規(guī)劃。目前常用的路徑規(guī)劃方法有圖搜索算法、遺傳算法、人工勢(shì)場法、快速擴(kuò)展隨機(jī)樹法[2-5]，但也存在一些不足，比如搜索空間大、局部尋優(yōu)能力不強(qiáng)、搜索速度慢、實(shí)時(shí)性能力不足等。基于此，結(jié)合分層[6]思想，本文提出一種混合路徑規(guī)劃方法，將裝甲車輛CGF路徑規(guī)劃分為全局路徑規(guī)劃層和局部路徑規(guī)劃層，運(yùn)用IGA和幾何算法搜尋路徑，通過仿真實(shí)驗(yàn)驗(yàn)證該方法具有全局搜索和快速靈活的特點(diǎn)，能夠達(dá)到仿真的實(shí)時(shí)性要求。

1 規(guī)劃空間模型

規(guī)劃空間建模就是運(yùn)用環(huán)境表示方法，將虛擬戰(zhàn)場環(huán)境中與路徑規(guī)劃有關(guān)的要素由其原始形式轉(zhuǎn)化為適合規(guī)劃的內(nèi)部模型，從而量化成可通行與不可通行區(qū)域。規(guī)劃空間建模是路徑規(guī)劃的前提。

可視圖法以多邊形障礙物模型[7]為基礎(chǔ)，將路徑規(guī)劃問題轉(zhuǎn)化為路徑點(diǎn)組合尋優(yōu)問題。其具體構(gòu)造過程：任意形狀障礙物用多邊形近似代替，用線段將裝甲車輛CGF的起始點(diǎn)s和障礙物的頂點(diǎn)以及目標(biāo)點(diǎn)g連接，并要求起始點(diǎn)和障礙物各頂點(diǎn)之間、目標(biāo)點(diǎn)和障礙物各頂點(diǎn)之間以及各障礙物頂點(diǎn)與頂點(diǎn)之間的連線均不能穿越障礙物，對(duì)虛擬戰(zhàn)場環(huán)境中的所有頂點(diǎn)都執(zhí)行完這個(gè)操作后，就得到了該環(huán)境的可視圖，如圖1所示。

用可視圖法建立規(guī)劃空間模型后，裝甲車輛CGF的路徑可由起始點(diǎn)、路徑點(diǎn)、目標(biāo)點(diǎn)構(gòu)成，其中路徑點(diǎn)用障礙物的頂點(diǎn)來表示。如圖1中，節(jié)點(diǎn)序列{s,A,B,g}用來表示一條路徑，s為起始點(diǎn)，A、B為路徑點(diǎn)，g為目標(biāo)點(diǎn)。

圖1 可視圖

2 混合路徑規(guī)劃方法

基本思想是在完成路徑規(guī)劃預(yù)處理后，將輪式裝甲車輛CGF路徑規(guī)劃分為兩層：全局路徑規(guī)劃層和局部路徑規(guī)劃層。其中，全局路徑規(guī)劃層主要用于仿真前生成初始全局路徑，采用的算法具有全局搜索性能；局部路徑規(guī)劃層是在初始全局路徑的基礎(chǔ)上，主要用于仿真中實(shí)時(shí)避開一些視界內(nèi)或者車輛所能探測(cè)范圍內(nèi)新出現(xiàn)的障礙物，規(guī)劃算法的效率越高越好。

2.1 基于IGA的全局路徑規(guī)劃

裝甲車輛CGF全局路徑規(guī)劃需要完成大部分路徑規(guī)劃的計(jì)算工作，搜索算法要求具有較強(qiáng)的搜索能力。免疫遺傳算法(Immune Genetic Algorithm,IGA)具有遺傳算法的全局性和免疫算法的自我調(diào)節(jié)功能[8-9]，提高傳統(tǒng)遺傳算法的總體搜索能力，最終找到最優(yōu)解。介于IGA的優(yōu)勢(shì)，將其用于全局路徑規(guī)劃，重點(diǎn)研究抗體編碼、適應(yīng)度、選擇算子。

本文中的抗體編碼采用符號(hào)編碼，對(duì)所有頂點(diǎn)按橫坐標(biāo)值從小到大進(jìn)行排序確定頂點(diǎn)編號(hào)(v1,v2,…,vn)，用這些編號(hào)來表示路徑點(diǎn)，則裝甲車輛CGF的路徑表示可簡化為一維編碼，具有編碼長度短、簡單直觀的優(yōu)點(diǎn)。

裝甲車輛CGF路徑的適應(yīng)度主要考慮路徑長度和路徑偏離起始點(diǎn)目標(biāo)點(diǎn)連線sg的距離，采用各項(xiàng)評(píng)價(jià)函數(shù)相乘的形式確定適應(yīng)度函數(shù)。根據(jù)規(guī)劃空間模型，可求路徑長度適應(yīng)度為：

(1)

式(1)中，n表示路徑中包含的頂點(diǎn)數(shù)量；d表示起始點(diǎn)至目標(biāo)點(diǎn)的距離；dij表示兩路徑點(diǎn)的距離。

路徑偏離適應(yīng)度為：

(2)

由式(1)、(2)得到適應(yīng)度為：

fit=fit1×fit2

(3)

選擇是模仿自然選擇現(xiàn)象，目的在于把優(yōu)化的抗體直接遺傳到下一代或通過配對(duì)交叉產(chǎn)生新的抗體再遺傳到下一代。選擇算子采用比例選擇算子，其基本思想建立在群體中抗體的適應(yīng)度和濃度的評(píng)價(jià)基礎(chǔ)上，各個(gè)抗體被選中的概率P與其適應(yīng)度大小成正比，而與濃度大小成反比，表示如下：

(4)

2.2 基于幾何算法的局部路徑規(guī)劃

當(dāng)裝甲車輛CGF按照初始規(guī)劃的全局路徑機(jī)動(dòng)，如果虛擬戰(zhàn)場環(huán)境出現(xiàn)了新的障礙物，基于兩點(diǎn)之間直線距離最短的思想，首先會(huì)判斷這個(gè)障礙物是否在當(dāng)前行進(jìn)方向上，如果沒有在當(dāng)前行進(jìn)方向上，則直接按照預(yù)先規(guī)劃路徑行進(jìn)，不用考慮該障礙物；如果在當(dāng)前行進(jìn)方向上，則要分析怎樣繞過這個(gè)障礙物，即選擇一個(gè)可行路徑點(diǎn)避開障礙物。這是局部路徑規(guī)劃的內(nèi)容。為便于描述，給出以下幾個(gè)定義：

定義1：裝甲車輛CGF的當(dāng)前位置為r，下一個(gè)子目標(biāo)點(diǎn)為g，其中g(shù)為初始全局路徑中r的下一個(gè)路徑點(diǎn)，則rg連線的方向稱為裝甲車輛CGF的目標(biāo)方向。

定義2：裝甲車輛CGF的運(yùn)動(dòng)方向與目標(biāo)方向之間的夾角稱為路徑方向角，記作δ。

本文提出幾何算法的基本思路如下：如圖2所示，以裝甲車輛CGF的當(dāng)前位置r為原點(diǎn)，以目標(biāo)方向rg為橫軸建立相對(duì)坐標(biāo)系x′o′y′，則相對(duì)坐標(biāo)系的橫軸將障礙物頂點(diǎn)分為上、下兩個(gè)集合，考慮視覺局限性，選擇CGF當(dāng)前位置r所能觀察到的障礙物頂點(diǎn)A、F、E、D作為備選路徑點(diǎn)，求取并比較上、下兩個(gè)頂點(diǎn)集中備選路徑點(diǎn)的路徑方向角，分別找到上、下兩個(gè)頂點(diǎn)集中路徑方向角最大的兩個(gè)點(diǎn)A、D，然后選擇這兩個(gè)點(diǎn)中路徑方向角較小的點(diǎn)A作為“最佳路徑點(diǎn)”行進(jìn)。具體流程見圖3。

3 實(shí)驗(yàn)驗(yàn)證

3.1 算法對(duì)比分析

為了驗(yàn)證本文提出的混合路徑規(guī)范算法的性能，選擇遺傳算法和A*算法進(jìn)行對(duì)比實(shí)驗(yàn)。算法參數(shù)設(shè)置如下：遺傳算法的種群大小為150，交叉概率、變異概率分別取0.8、0.1，終止進(jìn)化代數(shù)為200；A*算法的啟發(fā)函數(shù)h(n)代表從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的估計(jì)路徑長度。選擇算法的運(yùn)行時(shí)間、路徑長度兩個(gè)指標(biāo)來評(píng)價(jià)算法優(yōu)劣。為消除實(shí)驗(yàn)誤差，每種算法各進(jìn)行5次實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行平均處理。結(jié)果如表1、表2所示。

圖2 幾何算法示意圖

圖3 幾何算法流程

12345遺傳算法1.0251.2521.3251.4551.345A*算法0.0330.0750.1540.2480.187混合算法0.0130.0250.0280.0450.030

表2 三種算法的路徑長度比較

通過對(duì)比實(shí)驗(yàn)結(jié)果可知：

運(yùn)行時(shí)間方面，混合路徑規(guī)劃算法的運(yùn)行時(shí)間最少，而遺傳算法和A*算法的運(yùn)行時(shí)間多。混合路徑規(guī)劃算法的運(yùn)行時(shí)間最少的原因在于路徑規(guī)劃時(shí)，僅判斷與起始點(diǎn)和目標(biāo)點(diǎn)連線相交的障礙物，規(guī)劃空間中障礙物多邊形頂點(diǎn)數(shù)量減少，路徑方向角計(jì)算簡單，提高了算法運(yùn)行效率。A*算法通過計(jì)算啟發(fā)函數(shù)估價(jià)待擴(kuò)展節(jié)點(diǎn)的值，需要擴(kuò)展到整個(gè)規(guī)劃空間才能搜索到理想路徑。遺傳算法在進(jìn)行路徑規(guī)劃時(shí)，需要循環(huán)迭代計(jì)算，運(yùn)行時(shí)間最長。

路徑長度方面，混合路徑規(guī)劃算法通過改進(jìn)抗體編碼和算子設(shè)計(jì)，可以避免不可行路徑的產(chǎn)生，改善路徑質(zhì)量，路徑長度最小。A*算法對(duì)啟發(fā)函數(shù)的依賴性強(qiáng)，不能保證每次都搜索到最優(yōu)路徑，有可能是次優(yōu)路徑。遺傳算法由于本身參數(shù)優(yōu)化問題，容易陷入局部最優(yōu)。

3.2 仿真實(shí)例

以某型裝甲分隊(duì)作戰(zhàn)仿真系統(tǒng)山地作戰(zhàn)仿真實(shí)驗(yàn)為背景，將裝甲車輛CGF加入到具有逼真地形地貌、地表特征和自然景象的虛擬三維戰(zhàn)場環(huán)境中，檢驗(yàn)混合路徑規(guī)劃方法在作戰(zhàn)仿真系統(tǒng)中的實(shí)用性。裝甲車輛CGF路徑規(guī)劃過程如圖4所示，圖4(a)中A、B兩點(diǎn)是裝甲車輛CGF通過全局路徑規(guī)劃搜尋的兩個(gè)路徑點(diǎn)，當(dāng)機(jī)動(dòng)至路徑點(diǎn)A時(shí)，探測(cè)到前方新出現(xiàn)一個(gè)彈坑，此時(shí)再調(diào)用局部路徑規(guī)劃模塊，運(yùn)用幾何算法規(guī)劃得到新的路徑點(diǎn)H，并機(jī)動(dòng)至該點(diǎn)，如圖4(b)所示。待裝甲車輛繞過彈坑后，繼續(xù)回到路徑點(diǎn)B上按照初始全局路徑行進(jìn)，如圖4(c)所示。

實(shí)驗(yàn)表明，應(yīng)用混合路徑規(guī)劃方法的裝甲車輛CGF能夠在虛擬戰(zhàn)場環(huán)境里根據(jù)地形信息選擇機(jī)動(dòng)路線，實(shí)現(xiàn)良好的路徑規(guī)劃，滿足作戰(zhàn)仿真系統(tǒng)的實(shí)時(shí)性要求。

圖4 裝甲車輛CGF路徑規(guī)劃場景

4 結(jié)論

1) 提出一種混合路徑規(guī)劃方法，分別運(yùn)用IGA實(shí)現(xiàn)全局路徑規(guī)劃和幾何算法實(shí)現(xiàn)局部路徑規(guī)劃并應(yīng)用在一個(gè)具體的作戰(zhàn)仿真實(shí)驗(yàn)中。

2) 該方法能夠規(guī)劃出合理的路徑，滿足作戰(zhàn)仿真系統(tǒng)的實(shí)時(shí)性要求。