杜婉茹 王瀟茵 賈福凱 鄭 重 李慧妍

(中國(guó)航天系統(tǒng)科學(xué)與工程研究院 北京 100048)

0 引 言

現(xiàn)代戰(zhàn)場(chǎng)環(huán)境錯(cuò)綜復(fù)雜，在對(duì)敵方目標(biāo)進(jìn)行打擊的過(guò)程中，很多隱蔽的障礙無(wú)法通過(guò)高空手段預(yù)先探測(cè)得知；另外作戰(zhàn)環(huán)境通常不會(huì)一成不變，無(wú)人智能體前往目的地的行進(jìn)過(guò)程中出現(xiàn)預(yù)料之外的障礙狀況時(shí)有發(fā)生，若不加處理，往往會(huì)影響智能體的作戰(zhàn)質(zhì)量與作戰(zhàn)效率。在此背景下，如何迅速響應(yīng)變化的戰(zhàn)場(chǎng)環(huán)境并做出決策，是對(duì)敵方目標(biāo)進(jìn)行有效打擊的重要保障環(huán)節(jié)。

路徑規(guī)劃問(wèn)題[1]按照算法思路通常分為盲目搜索路徑規(guī)劃和啟發(fā)式搜索路徑規(guī)劃。路徑規(guī)劃要求智能體能夠依據(jù)一定的優(yōu)化原則，找出一條從運(yùn)動(dòng)起點(diǎn)到終點(diǎn)且能夠規(guī)避障礙物的最優(yōu)路徑。盲目搜索定義了固定的搜索策略，通常通過(guò)迭代進(jìn)行全路徑搜索，是傳統(tǒng)的路徑規(guī)劃技術(shù),因此效率很低,一般只適用于求解環(huán)境障礙單一的路徑規(guī)劃問(wèn)題。啟發(fā)式搜索定義了評(píng)價(jià)函數(shù)，其中融合了所求解問(wèn)題的相關(guān)指標(biāo)信息，并將其加入搜索過(guò)程來(lái)指導(dǎo)路徑節(jié)點(diǎn)的選擇具有更優(yōu)的搜索效率。

A*算法是典型的啟發(fā)式搜索算法，在目前研究中，該算法多用于環(huán)境已知的條件下，面對(duì)未知突發(fā)態(tài)障礙時(shí)該算法具有局限性，且當(dāng)目標(biāo)區(qū)域較大的情況下,此算法的收斂速度會(huì)明顯變慢，搜索過(guò)程往往會(huì)產(chǎn)生過(guò)多的冗余節(jié)點(diǎn)，并且可能會(huì)因?yàn)楫a(chǎn)生相同代價(jià)的節(jié)點(diǎn)，從而造成規(guī)劃路徑抖動(dòng)現(xiàn)象。文獻(xiàn)[2]通過(guò)引入分區(qū)加權(quán)信息，更改障礙搜索矩陣的尺寸來(lái)獲得不同的安全間距，解決了不同機(jī)器人在不同地圖環(huán)境下的安全性問(wèn)題。然而該算法在路徑長(zhǎng)度上有所犧牲，在規(guī)劃過(guò)程中產(chǎn)生較多的冗余節(jié)點(diǎn)，在復(fù)雜環(huán)境中效率并未有較大的提升。文獻(xiàn)[3]提出一種動(dòng)態(tài)離散勢(shì)場(chǎng)路徑規(guī)劃算法。使機(jī)器人在迷宮環(huán)境中快速、高效地規(guī)劃出一條折線少、轉(zhuǎn)折角度小的優(yōu)化路徑。但是該算法的仿真場(chǎng)景基于迷宮模型設(shè)計(jì)，未考慮實(shí)際戰(zhàn)場(chǎng)環(huán)境的動(dòng)態(tài)復(fù)雜性，其應(yīng)用可行性有待提高。文獻(xiàn)[4]提出了一種基于方向約束的A*算法，提高了方向約束路徑規(guī)劃問(wèn)題的求解能力和路徑質(zhì)量。該算法的局限性在于其設(shè)計(jì)實(shí)現(xiàn)建立于環(huán)境障礙均已知，面對(duì)路徑中出現(xiàn)的未知障礙并未提出解決方案。文獻(xiàn)[5]采用了導(dǎo)引律控制的思想,通過(guò)法向加速度閾值約束轉(zhuǎn)彎半徑。因?yàn)閷?dǎo)引律的設(shè)置，該方法只能處理無(wú)障礙物環(huán)境, 目前僅應(yīng)用于高空飛行器或制導(dǎo)武器。

以上算法能夠一定程度地解決路徑規(guī)劃問(wèn)題，但在實(shí)際應(yīng)用中受環(huán)境制約影響較大，無(wú)法處理出現(xiàn)動(dòng)態(tài)障礙的未知環(huán)境，且大規(guī)模復(fù)雜場(chǎng)景下收斂速度慢，會(huì)產(chǎn)生大量冗余節(jié)點(diǎn)，影響路徑規(guī)劃速度?；诖?，本文提出一種考慮拐角行進(jìn)安全的多層雙向A*算法，引入分層策略，當(dāng)驅(qū)使智能體行走遇到未知障礙時(shí)，將觸發(fā)下層搜索進(jìn)行避障路徑重規(guī)劃；采用雙向搜索，為了保證雙向搜索在起點(diǎn)和目標(biāo)點(diǎn)的中間位置附近重合，動(dòng)態(tài)定義了啟發(fā)式搜索的目標(biāo)節(jié)點(diǎn)，添加同步機(jī)制降低算法復(fù)雜度；改進(jìn)啟發(fā)式代價(jià)函數(shù)減少冗余節(jié)點(diǎn)產(chǎn)生，加速了算法的收斂，保證路徑規(guī)劃時(shí)效性；最后，使用Hermite差值對(duì)所得路徑進(jìn)行平滑處理，保證了智能體在尖銳拐角處的行進(jìn)安全。

1 多層雙向A*算法框架

1.1 A*算法分析

A*算法[6]是一種典型的啟發(fā)式搜索算法， 其結(jié)合了Dijkstra 和BFS 兩種算法各自的優(yōu)勢(shì)，在保證搜索效率的同時(shí)，可以得到最優(yōu)的路徑規(guī)劃。A*的核心思想體現(xiàn)在綜合考慮了起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的真實(shí)代價(jià)和當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估計(jì)代價(jià)，因此可以引導(dǎo)搜索方向。A*算法的代價(jià)函數(shù)為：

f(n)=g(n)+h(n)

(1)

式中：f(n)為經(jīng)過(guò)當(dāng)前節(jié)點(diǎn)n的全局評(píng)估代價(jià)值；g(n)為起始節(jié)點(diǎn)按照當(dāng)前選擇的路徑行進(jìn)至當(dāng)前節(jié)點(diǎn)n真實(shí)代價(jià)值；h(n)為當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)。

基本思路為：以起點(diǎn)為第一個(gè)計(jì)算點(diǎn)，計(jì)算其八鄰域中每個(gè)節(jié)點(diǎn)的代價(jià)值f(n)，若某個(gè)節(jié)點(diǎn)被占用即為障礙物則不入棧。然后取其中f(n)值最小的節(jié)點(diǎn)作為下一個(gè)計(jì)算點(diǎn)，并存儲(chǔ)其父節(jié)點(diǎn)，直到搜索到終點(diǎn)。最后從終點(diǎn)追溯其父節(jié)點(diǎn)獲取規(guī)劃路徑。

傳統(tǒng)的A*算法只能在環(huán)境障礙已知的條件下正常應(yīng)用，在實(shí)際使用場(chǎng)景下，任何阻礙前進(jìn)道路的障礙均會(huì)造成作戰(zhàn)終止。并且在應(yīng)用于作戰(zhàn)場(chǎng)景時(shí)沒(méi)有考慮周?chē)系K物的不規(guī)則形狀對(duì)避障的影響、未知障礙及行進(jìn)安全性等因素，在面對(duì)地圖很大的場(chǎng)景時(shí),此算法搜索過(guò)程往往會(huì)產(chǎn)生過(guò)多的冗余節(jié)點(diǎn)，從而導(dǎo)致收斂速度會(huì)明顯變慢，路徑規(guī)劃的效率將大幅下降。本文針對(duì)以上缺陷提出一種考慮拐角行進(jìn)安全的多層雙向A*路徑規(guī)劃算法。

1.2 改進(jìn)啟發(fā)函數(shù)的多層雙向A*算法設(shè)計(jì)

考慮到實(shí)際作戰(zhàn)場(chǎng)景的不確定性，對(duì)突發(fā)狀況(前進(jìn)道路產(chǎn)生未知障礙)添加應(yīng)對(duì)方案，采用分層策略，當(dāng)驅(qū)使智能體沿規(guī)劃路徑行進(jìn)過(guò)程中遇到障礙時(shí)，觸發(fā)下層搜索，完成有效避障路徑重規(guī)劃；針對(duì)算法在大規(guī)模復(fù)雜未知環(huán)境中因冗余節(jié)點(diǎn)過(guò)多而產(chǎn)生計(jì)算效率低下的問(wèn)題，改進(jìn)算法單向計(jì)算過(guò)程為雙向計(jì)算，降低算法復(fù)雜度，同時(shí)，為了保證雙向搜索在理論中點(diǎn)位置附近的重合，提高算法收斂時(shí)效，動(dòng)態(tài)定義了啟發(fā)式搜索的目標(biāo)節(jié)點(diǎn)，添加同步機(jī)制。

為了提高算法在大規(guī)模環(huán)境下的工作效率，對(duì)當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)估計(jì)函數(shù)進(jìn)行改進(jìn)：以分區(qū)加權(quán)方式來(lái)表示距離信息，避免相鄰節(jié)代價(jià)相同而造成的路徑不確定性，在路徑規(guī)劃中產(chǎn)生抖動(dòng)現(xiàn)象；以叉積距離來(lái)表示角度信息[7]，設(shè)計(jì)新的啟發(fā)函數(shù)。智能體按改進(jìn)的啟發(fā)函數(shù)可以提高在復(fù)雜環(huán)境的路徑規(guī)劃效率，縮短遇到動(dòng)態(tài)障礙的再次規(guī)劃耗費(fèi)的時(shí)間。

新的代價(jià)估計(jì)函數(shù)定義如下：

(2)

式中：

X1=|n.x-goal.x|

Y1=|n.y-goal.y|

X2=|start.x-goal.x|

Y2=|start.y-goal.y|

式中：n為當(dāng)前的節(jié)點(diǎn)，goal為目標(biāo)節(jié)點(diǎn)，x、y分別時(shí)節(jié)點(diǎn)的行列號(hào)，p、q、w是權(quán)值。

在原始的啟發(fā)函數(shù)中，g(n)與h(n)共同決定了代價(jià)值f(n)，因此g(n)和h(n)必須要保持量綱的統(tǒng)一，保證真實(shí)代價(jià)與估計(jì)代價(jià)的同等重要性。同理，角度信息和距離信息需要保持量綱統(tǒng)一，才能保證其貢獻(xiàn)量一致。

算法框架圖如圖1所示。

圖1 改進(jìn)的多層雙向A*算法框架

首先，將改進(jìn)啟發(fā)函數(shù)及添加同步機(jī)制的雙向A*算法與初始環(huán)境數(shù)據(jù)加載至智能體，智能體根據(jù)環(huán)境信息規(guī)劃出一條行進(jìn)路徑，計(jì)入路徑集P。按照該路徑行進(jìn)，并實(shí)時(shí)探測(cè)行進(jìn)中是否出現(xiàn)未知障礙，當(dāng)未知障礙發(fā)生時(shí)，智能體對(duì)障礙進(jìn)行探測(cè)并確定位置及形狀，觸發(fā)下層搜索并同時(shí)更新環(huán)境數(shù)據(jù)庫(kù)信息。以當(dāng)前節(jié)點(diǎn)為起始點(diǎn)規(guī)劃新的避障路徑，并同樣計(jì)入路徑集P。當(dāng)智能體成功到達(dá)終點(diǎn)時(shí)，將路徑集合P中的子路徑合并，獲得最終PATH。

2 算法實(shí)現(xiàn)

2.1 改進(jìn)啟發(fā)函數(shù)的同步雙向A*算法

雙向A*算法指搜索沿著正逆兩個(gè)方向進(jìn)行，正向是指從起點(diǎn)開(kāi)始向目標(biāo)點(diǎn)行進(jìn)的路徑搜索方向，反之為逆向。正向與逆向搜索過(guò)程交替進(jìn)行。當(dāng)正向和逆向搜索路徑相遇，且該節(jié)點(diǎn)滿足兩個(gè)方向搜索的約束條件時(shí)，搜索結(jié)束。該算法在理想狀態(tài)下，正向搜索與逆向搜索會(huì)在起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的連線中心相遇。然而，由于實(shí)際作戰(zhàn)環(huán)境中障礙物復(fù)雜多變，正向與逆向搜索通常不在中心點(diǎn)相遇，極端情況下，A*搜索代價(jià)將類(lèi)似于盲目搜索，效率大大降低。所以確保搜索在起始與目標(biāo)點(diǎn)連線中點(diǎn)位置附近相遇是保證算法收斂效率的重要環(huán)節(jié)。

針對(duì)傳統(tǒng)雙向A*算法在實(shí)際作戰(zhàn)場(chǎng)景中應(yīng)用產(chǎn)生的局限性，提出同步雙向A*算法，為了保證雙向搜索在理論中點(diǎn)位置附近的相遇，將兩個(gè)方向上的當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)作為兩個(gè)方向搜索的目標(biāo)節(jié)點(diǎn)。動(dòng)態(tài)定義了啟發(fā)式搜索的目標(biāo)節(jié)點(diǎn)，添加同步機(jī)制降低算法復(fù)雜度，加速了算法的收斂，保證正反兩個(gè)方向的搜索同時(shí)進(jìn)行。

為了避免相鄰節(jié)點(diǎn)代價(jià)相同而造成的路徑不確定性在路徑規(guī)劃中產(chǎn)生抖動(dòng)現(xiàn)象，即當(dāng)前節(jié)點(diǎn)要將其周?chē)拇鷥r(jià)相同的節(jié)點(diǎn)均遍歷之后才能進(jìn)入下一節(jié)點(diǎn)狀態(tài)的現(xiàn)象，提高算法在大規(guī)模環(huán)境下的工作效率，對(duì)當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)估計(jì)函數(shù)h(n)進(jìn)行改進(jìn)，以分區(qū)加權(quán)方式來(lái)表示距離信息；以叉積距離來(lái)表示角度信息[7]，加入距離信息和角度信息設(shè)計(jì)新的啟發(fā)函數(shù)：

F(n)=G(n)+H(n)

(3)

F(n)為經(jīng)過(guò)當(dāng)前節(jié)點(diǎn)n的全局評(píng)估代價(jià)值。

圖2 真實(shí)代價(jià)值計(jì)算示意圖

H(n)為添加了距離信息與角度信息的改進(jìn)代價(jià)函數(shù)，用于表示當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)。該函數(shù)的改進(jìn)能夠有效減少當(dāng)某些路徑具有相同的F值時(shí)均被搜索，從而產(chǎn)生大量冗余搜索節(jié)點(diǎn)出現(xiàn)的路徑抖動(dòng)現(xiàn)象，公式如下：

H(n)=p×X+q×Y+w×|X×Y-X′×Y′|

(4)

式中：(p×X+q×Y)為路徑信息，在曼哈頓距離的計(jì)算基礎(chǔ)加入權(quán)值，進(jìn)行一定的方向引導(dǎo)；X為當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的橫向距離，即X=abs(n.x-goal.x)；Y為當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的縱向距離，即Y=abs(n.y-goal.y)；(w×|X×Y-X′×Y′|)為角度信息；X′、Y′為起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的橫向、縱向距離。

智能體按改進(jìn)的啟發(fā)函數(shù)可以提高在復(fù)雜環(huán)境的路徑規(guī)劃效率，縮短遇到動(dòng)態(tài)障礙的再次規(guī)劃耗費(fèi)的時(shí)間，具體算法步驟如下：

Step1維護(hù)兩個(gè)Open_list及Close_list，將起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別加入Open_list1 和Open_list2。

Step2判斷兩個(gè)Open_list是否為空，若為空。則搜索失??；若不為空，則轉(zhuǎn)入Step3。

Step3彈出兩個(gè)Open_list中F值最小的節(jié)點(diǎn)，分別放入Close_list中。

Step4若該方向的當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)中，被選為下一輪搜索的節(jié)點(diǎn)，與相對(duì)方向上的當(dāng)前搜索節(jié)點(diǎn)為同一節(jié)點(diǎn)，則搜索成功。

Step5若Open_list長(zhǎng)度不再改變，無(wú)節(jié)點(diǎn)參與擴(kuò)展，則轉(zhuǎn)Step2。

Step6選取當(dāng)前節(jié)點(diǎn)鄰域的所有子節(jié)點(diǎn)，并且判斷其合法性，對(duì)比其代價(jià)函數(shù)，確定最小F值的節(jié)點(diǎn)為下一節(jié)點(diǎn)，將合法的節(jié)點(diǎn)放對(duì)應(yīng)的Open_list中。

Step7修改啟發(fā)式搜索的目標(biāo)節(jié)點(diǎn)，改為相對(duì)方向上的當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，轉(zhuǎn)Step2。

2.2 A*算法的未知障礙應(yīng)對(duì)方法——分層策略

傳統(tǒng)A*算法的路徑規(guī)劃實(shí)現(xiàn)需要建立在環(huán)境與障礙物已知的條件下，但在實(shí)際的作戰(zhàn)場(chǎng)景中，環(huán)境通常不會(huì)一成不變，突發(fā)狀況會(huì)引發(fā)未知的障礙，當(dāng)未知障礙橫亙于先前規(guī)劃的路線上，會(huì)導(dǎo)致智能體無(wú)法完成既定任務(wù)，為了解決A*算法無(wú)法繞過(guò)未知障礙物問(wèn)題，增強(qiáng)算法應(yīng)用的健壯性，提出A*算法的未知障礙的應(yīng)對(duì)方案——分層策略。

首先根據(jù)現(xiàn)有的已知環(huán)境信息利用改進(jìn)啟發(fā)函數(shù)的同步雙向A*算法，規(guī)劃出一條從起點(diǎn)A到終點(diǎn)S最優(yōu)路徑l1。其次，驅(qū)使智能體按照該路徑行進(jìn)，并實(shí)時(shí)探測(cè)行進(jìn)路線的環(huán)境。若在行進(jìn)路徑中遇到未知障礙阻攔，則探測(cè)該障礙物的位置及形狀信息，并實(shí)時(shí)更新環(huán)境數(shù)據(jù)庫(kù)。之后，將智能體當(dāng)前位置B作為新的路徑起點(diǎn)，調(diào)用改進(jìn)啟發(fā)函數(shù)的同步雙向A*算法規(guī)劃出從B點(diǎn)到S點(diǎn)的最優(yōu)路徑l2，以此類(lèi)推，直至智能體成功抵達(dá)目標(biāo)位置。此時(shí)，將路徑集合l={l1,l2,…,ln}進(jìn)行合并，即可得到最終的從A到S的規(guī)劃路徑PATH。

2.3 規(guī)劃路徑平滑處理

由于算法理論規(guī)則為在下一個(gè)探索方向存在障礙區(qū)時(shí)轉(zhuǎn)換探索方向，因此規(guī)劃所得路徑中免不了會(huì)存在較為尖銳的拐角，這對(duì)實(shí)際行進(jìn)的智能體會(huì)產(chǎn)生較大威脅。例如無(wú)人機(jī)的飛行轉(zhuǎn)彎，通過(guò)機(jī)身傾斜產(chǎn)生空氣動(dòng)力差側(cè)向力，從而實(shí)現(xiàn)飛機(jī)方向的更改，傾斜角度過(guò)大會(huì)造成機(jī)體的失速失控，很容易與障礙物產(chǎn)生刮蹭，智能車(chē)同理。所以帶有尖銳拐角的路徑無(wú)法滿足實(shí)際的飛行需求，會(huì)對(duì)智能體實(shí)際行進(jìn)安全產(chǎn)生較大威脅，因此需要在繞開(kāi)障礙物時(shí)選擇更為安全的行進(jìn)角度。

Hermite曲線[8]為利用Hermite插值從一個(gè)點(diǎn)到另一個(gè)點(diǎn)產(chǎn)生的一個(gè)三次多項(xiàng)式，在坐標(biāo)系中曲線表示平滑，符合現(xiàn)實(shí)環(huán)境里物體的運(yùn)行軌跡，因此使用Hermite插值對(duì)規(guī)劃出的路徑進(jìn)行處理，最終得出實(shí)際路徑軌跡，保證智能體的安全行進(jìn)。

在函數(shù)值與一階導(dǎo)數(shù)給定的情況下，n個(gè)節(jié)點(diǎn)x1,x2,…,xn的Hermite插值多項(xiàng)式的表達(dá)式如下：

(5)

式中：

yi=y(xi)

2.4 面向未知環(huán)境的多層雙向A*算法

將上述機(jī)制結(jié)合，提出一種改進(jìn)的多層雙向A*算法，能夠在解決因未知障礙導(dǎo)致路徑規(guī)劃崩潰問(wèn)題，增強(qiáng)算法健壯性的同時(shí)能夠有效減少搜索過(guò)程產(chǎn)生的冗余節(jié)點(diǎn)數(shù)量，提高算法在大規(guī)模復(fù)雜環(huán)境中路徑規(guī)劃的效率，在計(jì)算所得理論路徑的基礎(chǔ)上，使用Hermite插值得出滿足實(shí)際行進(jìn)的最終軌跡，保證了智能體的行進(jìn)安全。

改進(jìn)后的面向未知環(huán)境的多層雙向A*算法流程如圖3所示。

圖3 面向復(fù)雜未知環(huán)境的多層雙向A*算法流程圖

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

3.1 作戰(zhàn)場(chǎng)景建模方法

路徑規(guī)劃依賴于地圖，建立環(huán)境模型是路徑規(guī)劃的前提。軍事作戰(zhàn)的實(shí)際場(chǎng)景是一個(gè)復(fù)雜且龐大的環(huán)境系統(tǒng)，障礙物形狀各異，若單純地將其轉(zhuǎn)化為理想的圓形或矩形，在應(yīng)用算法時(shí)會(huì)產(chǎn)生路徑冗余、高能耗等現(xiàn)象?？紤]算法在實(shí)際環(huán)境中的普適性，需要在建模過(guò)程中對(duì)不規(guī)則障礙物進(jìn)行處理，保證智能體在躲避障礙物時(shí)的安全性。

(1) 不規(guī)則形狀障礙物的規(guī)則建模。為了解決算法在實(shí)際環(huán)境中，路徑規(guī)劃因不規(guī)則形狀障礙物而產(chǎn)生的路徑冗余現(xiàn)象的發(fā)生，特別是U型障礙物等凹邊形，需要引入對(duì)不規(guī)則障礙物的規(guī)則化處理[12]，步驟如下：

Step1對(duì)不規(guī)則障礙物凹凸點(diǎn)進(jìn)行識(shí)別，記錄個(gè)數(shù)cnt及凹點(diǎn)坐標(biāo)pos。

Step2若cnt為0，則記錄凸點(diǎn)坐標(biāo)轉(zhuǎn)向Step4，否則轉(zhuǎn)Step3。

Step3連接凸點(diǎn)，將障礙物凸形化，重復(fù)Step1。

Step4結(jié)束。

不規(guī)則形狀障礙物凸形化處理效果如圖4所示。

圖4 不規(guī)則形狀障礙凸型化效果

(2) 柵格環(huán)境建模。應(yīng)用A*算法時(shí)，為了更好地獲取智能體的前進(jìn)方向，并且盡可能減少智能體在避障拐角處與障礙物的剮蹭，考慮使用添加智能體大小指標(biāo)的柵格法將實(shí)際場(chǎng)景進(jìn)行建模。柵格法[9-11]可用于有限運(yùn)行區(qū)域進(jìn)行建模，在柵格建模中，柵格粒度的大小直接影響著柵格法的效率。該建模方法數(shù)學(xué)描述如下。

設(shè)作戰(zhàn)區(qū)域?yàn)锳，智能體的可行區(qū)域記為B，障礙物集合記為O，O∈A,O∈B。實(shí)際環(huán)境中的柵格記為g(a,b),其中a為g所在的水平橫坐標(biāo)(a=1,2,…,n)，b為g所在的水平縱坐標(biāo)(b=1,2,…,n)，對(duì)實(shí)際環(huán)境場(chǎng)景進(jìn)行采樣，將采樣的環(huán)境信息記為G(g1,g2,…,gi)，i=1,2,…,n，其中n為采樣序號(hào)。在柵格法的建模中，柵格的寬度δ與智能體的長(zhǎng)寬有關(guān)，實(shí)際環(huán)境坐標(biāo)與柵格坐標(biāo)存在以下關(guān)系約束：

a=int(x/δ)

(6)

b=int(y/δ)

(7)

依照上述柵格理論，便可以將實(shí)際環(huán)境中的坐標(biāo)(x,y)映射為柵格建模后的坐標(biāo)g(a,b)∈O∈A，基于此，我們即可建立相應(yīng)的作戰(zhàn)場(chǎng)景的柵格模型。

在使用柵格環(huán)境建模法對(duì)該作戰(zhàn)場(chǎng)景進(jìn)行建模時(shí)，為了保證智能體在行進(jìn)過(guò)程中不刮蹭拐角處障礙，將柵格寬度定義為智能體寬度的5倍進(jìn)行坐標(biāo)映射。

根據(jù)上述不規(guī)則障礙凸型化處理結(jié)果，按照上述環(huán)境建模理論，將其映射至柵格環(huán)境中，如圖5所示。

圖5 不規(guī)則形狀障礙柵格化映射

最終定義實(shí)驗(yàn)案例的場(chǎng)景建模結(jié)果如圖6所示。

圖6 使用柵格化建模后的作戰(zhàn)場(chǎng)景

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

編程實(shí)現(xiàn)面向未知環(huán)境的多層雙向A*算法。當(dāng)智能體行進(jìn)中遇到障礙，將觸發(fā)算法的下層搜索，規(guī)劃新的避障路徑。

在該案例中，初始的驅(qū)動(dòng)路徑Path1經(jīng)過(guò)了四段未知障礙覆蓋區(qū)，如圖7(a)中禁行符號(hào)所示。驅(qū)動(dòng)智能體按Path1行進(jìn)，圖7(b)中實(shí)線為智能體實(shí)際行走路線，當(dāng)遇到未知障礙時(shí)，觸發(fā)下層搜索，產(chǎn)生第二次避障路徑Path2，即虛線所示。可以看出，Path2仍將通過(guò)兩段未知障礙覆蓋區(qū)。同理，當(dāng)行進(jìn)過(guò)程再次遇到障礙時(shí)觸發(fā)重規(guī)劃，得出Path3，如圖7(c)所示。以此類(lèi)推，直到智能體成功行進(jìn)至目標(biāo)點(diǎn)。圖中：虛線為路徑規(guī)劃結(jié)果，實(shí)線為智能體實(shí)際行走路線，禁行標(biāo)志為路徑中所遇為未知障礙的位置。

圖7 四次路徑重規(guī)劃示意圖

最終，將實(shí)驗(yàn)結(jié)果所得的四條分路徑Path1-Path4進(jìn)行合并，得出最終智能體行進(jìn)的避障路徑，如圖8所示。

圖8 面向未知環(huán)境的多層雙向A*算法路徑規(guī)劃結(jié)果

實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)如表1所示。

表1 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

3.3 實(shí)驗(yàn)結(jié)果分析及對(duì)比

實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)的A*算法及目前研究現(xiàn)狀中一些改進(jìn)的路徑規(guī)劃算法，本文算法在應(yīng)用場(chǎng)景適應(yīng)性、算法健壯性及計(jì)算效率方面均有改進(jìn)，具體統(tǒng)計(jì)如表2所示。

表2 本文算法與現(xiàn)有算法的改進(jìn)對(duì)比

在實(shí)驗(yàn)仿真環(huán)境中，編碼復(fù)現(xiàn)了文獻(xiàn)[13]中所提的路徑規(guī)劃算法，將彈、壓棧節(jié)點(diǎn)數(shù)、最終PATH的節(jié)點(diǎn)數(shù)以及算法收斂時(shí)間三個(gè)指標(biāo)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 本文算法與現(xiàn)有算法的實(shí)驗(yàn)結(jié)果數(shù)據(jù)對(duì)比

為了驗(yàn)證該改進(jìn)算法在大規(guī)模復(fù)雜環(huán)境中的路徑規(guī)劃效果，分別在地圖信息為100×100，200×200，300×300三種規(guī)模的環(huán)境模型中進(jìn)行實(shí)驗(yàn)，隨機(jī)生成不同形狀的障礙物，進(jìn)行實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)，結(jié)果如下：

表4 不同地圖規(guī)模中本文算法與文獻(xiàn)[13]算法實(shí)驗(yàn)結(jié)果對(duì)比

結(jié)果表明，本文提出的面向未知環(huán)境的多層雙向A*算法相對(duì)于傳統(tǒng)及現(xiàn)有改進(jìn)的路徑規(guī)劃算法，在相同的實(shí)驗(yàn)環(huán)境中，彈、壓棧節(jié)點(diǎn)總數(shù)、最終規(guī)劃路徑長(zhǎng)度、算法計(jì)算耗時(shí)三個(gè)指標(biāo)實(shí)驗(yàn)結(jié)果均有提升。統(tǒng)計(jì)可知，實(shí)驗(yàn)過(guò)程處理冗余節(jié)點(diǎn)數(shù)減少12.9%，總用時(shí)縮短了17.4%，極大提高了路徑規(guī)劃的效率。在復(fù)雜未知的環(huán)境中，隨著地圖規(guī)模的增大，本文算法對(duì)于避障路徑的規(guī)劃效率提升得到更好的驗(yàn)證。

4 結(jié) 語(yǔ)

針對(duì)未知戰(zhàn)場(chǎng)環(huán)境打擊敵方目標(biāo)的路徑規(guī)劃問(wèn)題提出一種考慮拐角行進(jìn)安全的多層雙向A*算法。該算法突破了對(duì)環(huán)境已知的依賴，能夠使智能體在行進(jìn)過(guò)程中實(shí)時(shí)響應(yīng)突發(fā)障礙，進(jìn)行有效的避障路徑重規(guī)劃；采用同步雙向搜索，動(dòng)態(tài)定義了搜索方向上的目標(biāo)節(jié)點(diǎn)，保證搜索在起點(diǎn)和目標(biāo)點(diǎn)的中間位置附近重合；改進(jìn)啟發(fā)式代價(jià)函數(shù)，加入位置及角度信息，避免多個(gè)代價(jià)相同節(jié)點(diǎn)造成的搜索節(jié)點(diǎn)冗余，提高算法在大規(guī)模環(huán)境下的工作效率；使用Hermite差值對(duì)所得路徑進(jìn)行平滑處理，保證了智能體在拐角的行進(jìn)安全。

實(shí)驗(yàn)環(huán)境建?？紤]了實(shí)際環(huán)境中路徑規(guī)劃因不規(guī)則形狀障礙物而產(chǎn)生的路徑冗余現(xiàn)象的發(fā)生，結(jié)果表明，與現(xiàn)有路徑規(guī)劃算法相比，本文提出的算法通過(guò)分層策略解決了未知環(huán)境出現(xiàn)動(dòng)態(tài)障礙的路徑規(guī)劃問(wèn)題，通過(guò)對(duì)啟發(fā)函數(shù)及同步雙向機(jī)制的改進(jìn)，使得算法收斂速度提升17.4%，產(chǎn)生冗余節(jié)點(diǎn)數(shù)減少12.9%。使用Hermite差值對(duì)路徑進(jìn)行平滑處理，能夠驅(qū)使智能體以更加安全的角度通過(guò)拐角，躲避障礙。同時(shí)，在不同規(guī)模的地圖環(huán)境下開(kāi)展的實(shí)驗(yàn)結(jié)果表明，該算法的路徑規(guī)劃準(zhǔn)確度和效率均有較大提高。

未來(lái)的工作將結(jié)合實(shí)際三維戰(zhàn)場(chǎng)環(huán)境，考慮時(shí)效性、隱蔽性及能耗等多要素，實(shí)現(xiàn)最優(yōu)路徑的綜合規(guī)劃技術(shù)，并考慮加入多智能體，通過(guò)多智能體協(xié)同工作，進(jìn)一步提高大規(guī)模復(fù)雜環(huán)境的路徑規(guī)劃效率。