基于數(shù)字地圖和加權(quán)A*算法的戰(zhàn)術(shù)路徑規(guī)劃

蘇玉婷 原大川 侯磊

摘要：本文首先對(duì)在軍事仿真中經(jīng)常使用到的數(shù)字地圖進(jìn)行了詳細(xì)闡述；其次，對(duì)在靜態(tài)路網(wǎng)中求解最短路徑的A*算法進(jìn)行了介紹，并對(duì)靜態(tài)加權(quán)A*算法進(jìn)行了分析和實(shí)現(xiàn)；再次，提出了一種進(jìn)行戰(zhàn)術(shù)路徑規(guī)劃的實(shí)現(xiàn)方法；最后，運(yùn)用MATLB仿真平臺(tái)對(duì)某真實(shí)島嶼的數(shù)字地圖和靜態(tài)加權(quán)A*算法進(jìn)行結(jié)合，實(shí)現(xiàn)了戰(zhàn)術(shù)路徑規(guī)劃，證明了該方法的有效性和快速性。

關(guān)鍵詞：靜態(tài)加權(quán)A*搜索算法；數(shù)字地圖；戰(zhàn)術(shù)路徑規(guī)劃；MATLAB

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）08-0112-02

A*算法[1]是一種靜態(tài)路網(wǎng)中進(jìn)行路徑規(guī)劃時(shí)求解最短路徑最有效的直接搜索算法，該算法可針對(duì)真實(shí)地圖，可以使得尋路結(jié)果的逼真度和真實(shí)性得到體現(xiàn)。

以數(shù)字地圖為基礎(chǔ)，可以建立數(shù)字化戰(zhàn)場(chǎng)所必需的“戰(zhàn)場(chǎng)環(huán)境信息系統(tǒng)”。在現(xiàn)代戰(zhàn)爭(zhēng)中，數(shù)字地圖是高技術(shù)武器的一個(gè)重要支撐。[2] 本文首先對(duì)數(shù)字地圖進(jìn)行了環(huán)境建模，建立了二維柵格地圖和三維高程模型；其次，運(yùn)用靜態(tài)加權(quán)A*算法在已知環(huán)境下進(jìn)行戰(zhàn)術(shù)路徑規(guī)劃。

1 數(shù)字地圖

1.1 基于柵格數(shù)字地圖的環(huán)境描述

柵格（像素）數(shù)字地圖是以一系列大小相同、排列有序的柵格像素的灰度值表示的地圖，叫柵格（像素）數(shù)字地圖[3]，它通常由一個(gè)圖像矩陣G表示，即：

柵格數(shù)字地圖是采用整數(shù)對(duì)地形符號(hào)進(jìn)行表示的，其位置與分布表示為符號(hào)所在位置的像素的有序集合。

1.2 數(shù)字高程模型

數(shù)字高程模型是用一組有序數(shù)值陣列形式表示地面高程的一種實(shí)體地面模型。一般認(rèn)為，數(shù)字地形模型（Digital Terrain Model，DTM）是描述包括高程在內(nèi)的各種線性和非線性地貌因子組合的空間分布，如坡度、坡向、坡度變化率等等。[4]真實(shí)的數(shù)字高程模型如圖1所示，可在Index of /srtm/version2_1/SRTM3/Africa數(shù)據(jù)庫進(jìn)行下載，SRTM3表示采樣間隔為地球等角坐標(biāo)系的3角秒（約90米）。

1.3 數(shù)字地圖的MATLAB實(shí)現(xiàn)

MATLAB可用于實(shí)現(xiàn)圖形化建模，實(shí)現(xiàn)數(shù)據(jù)的可視化。首先建立createFigure（）函數(shù)用于創(chuàng)建一個(gè)大小為60×60的空?qǐng)D，創(chuàng)建函數(shù)initializeField（）將地圖進(jìn)行初始化。然后，讀取已經(jīng)建立好的地圖矩陣，將其進(jìn)行可視化，建立好的二維柵格地圖如圖2所示。將二維柵格地圖添加高程信息，進(jìn)行數(shù)字高程模型的建立。建立函數(shù)imread（'DEM.tif'）讀入高程矩陣，將其進(jìn)行可視化。

2 A*搜索算法

2.1 傳統(tǒng)的A*算法

A*算法是一種最佳優(yōu)先搜索算法，它通過搜索在所有可能路徑中代價(jià)最小的路徑來尋找目標(biāo)。A*算法的代價(jià)函數(shù)一般表示為：

其中，f（n）是從起點(diǎn)到終點(diǎn)的估計(jì)代價(jià)函數(shù)，g（n）表示從起點(diǎn)到當(dāng)前點(diǎn)的實(shí)際代價(jià)值，h（n）表示從當(dāng)前點(diǎn)到終點(diǎn)的最短路徑的估計(jì)代價(jià)值。數(shù)字地圖中，橫向移動(dòng)和豎向移動(dòng)，移動(dòng)代價(jià)是一個(gè)節(jié)點(diǎn)的距離，斜向移動(dòng)的移動(dòng)代價(jià)是×節(jié)點(diǎn)的距離。采用四向鄰域的移動(dòng)方式將避免開放和小數(shù)的計(jì)算，也將提高算法的計(jì)算效率。因此，在仿真中我們采用的是曼哈頓距離。

2.2 加權(quán)A*算法

雖然傳統(tǒng)的A*算法能保證在靜態(tài)網(wǎng)中找到最優(yōu)解路徑，但是它要檢查所以具有相同價(jià)值的路徑以找到最佳路徑，搜索速度較慢。加權(quán)A*算法/靜態(tài)加權(quán)算法加大了啟發(fā)函數(shù)的權(quán)重從而減少了搜索深度，在搜索結(jié)果可接受的前提下加快了搜索速度。其公式如下：

研究表明，加權(quán)A*算法的速度是傳統(tǒng)A*算法的ε倍。[6]

3 戰(zhàn)術(shù)路徑規(guī)劃

機(jī)動(dòng)是軍隊(duì)?wèi)?zhàn)場(chǎng)主動(dòng)權(quán)的體現(xiàn)，在高技術(shù)裝備的條件下，沿道路機(jī)動(dòng)將是陸地戰(zhàn)場(chǎng)的最主要機(jī)動(dòng)方式；而對(duì)具體的戰(zhàn)斗而言，越野機(jī)動(dòng)占有及其重要的地位。沿道路機(jī)動(dòng)和越野機(jī)動(dòng)都會(huì)受到地形的限制和影響。分析地形對(duì)機(jī)動(dòng)的影響及其大小，在于選擇最為合理的機(jī)動(dòng)路線。綜合分析地形對(duì)沿道路機(jī)動(dòng)運(yùn)動(dòng)的影響或?qū)υ揭皺C(jī)動(dòng)的影響，目的在于選擇距離最短、最便于機(jī)動(dòng)、隱蔽性最好、危險(xiǎn)性最少，要點(diǎn)地形有利且便于控制的機(jī)動(dòng)路線，以便在最短時(shí)間內(nèi)快速到達(dá)目的地。[5]地形對(duì)機(jī)動(dòng)的影響包括地貌、水系、植被和居民地四個(gè)方面。不同地形條件下各級(jí)公路的行車速度如表1所示，本表摘自交通部1981年《公路工程技術(shù)標(biāo)準(zhǔn)》。

從表1可看出，在丘陵上的行車速度是在平原上行車速度的50%-67%，因此，在丘陵道路上的通行代價(jià)大約是在平原道路上通行代價(jià)的兩倍。

本文在運(yùn)用MATLAB在真實(shí)數(shù)字地圖上使用加權(quán)A*算法進(jìn)行路徑規(guī)劃時(shí)，將地形對(duì)通行的影響轉(zhuǎn)換為在不同地形條件下比較合理的通行代價(jià)比例，如表2所示。

使用三維地形柵格地圖和數(shù)字高程模型對(duì)環(huán)境區(qū)域進(jìn)行建模，從起點(diǎn)開始尋找相鄰的可能到達(dá)或者可以通過的方格，同時(shí)按照不同的地形條件改變通行代價(jià)的設(shè)置。改進(jìn)加權(quán)A*算法進(jìn)行戰(zhàn)術(shù)路徑規(guī)劃的代價(jià)函數(shù)可表示如下：

其中x（n）表示不同地形的不同通行代價(jià)。經(jīng)過測(cè)試，將ε設(shè)置為10，即：

運(yùn)用MATLAB讀取坐標(biāo)是北緯xx度東經(jīng)yy度的數(shù)字高程模型（島嶼模型），大小為408×408，完成設(shè)置起點(diǎn)和目標(biāo)點(diǎn)后，利用改進(jìn)加權(quán)A*算法進(jìn)行戰(zhàn)術(shù)路徑規(guī)劃。其結(jié)果如圖3所示。

4 結(jié)果分析

真實(shí)可信的行為是軍事概念模型行為模型可信度的核心。經(jīng)過上文的分析，改進(jìn)加權(quán)A*算法在真是數(shù)字地圖上進(jìn)行戰(zhàn)術(shù)路徑規(guī)劃的可行性，逼真有效的模型可使得模擬訓(xùn)練的效率得到很大提高。隨著科技的不斷發(fā)展，路徑規(guī)劃技術(shù)所要求的環(huán)境將會(huì)越來越復(fù)雜，尋路算法迅速響應(yīng)復(fù)雜環(huán)境變化的能力需要得到不斷提高。將好的環(huán)境建模技術(shù)與優(yōu)秀的路徑規(guī)劃算法相結(jié)合進(jìn)行優(yōu)勢(shì)互補(bǔ)，以期更加適應(yīng)復(fù)雜的作戰(zhàn)仿真環(huán)境。[7]本文在進(jìn)行環(huán)境建模時(shí)運(yùn)用到了GIS（地理信息系統(tǒng)）的一些技術(shù)，提高了仿真環(huán)境的逼真度，同時(shí)運(yùn)用改進(jìn)加權(quán)A*算法，實(shí)驗(yàn)結(jié)果也表明該方法的能夠在真實(shí)數(shù)字地圖上進(jìn)行路徑規(guī)劃的有效性和搜索的快速性。

參考文獻(xiàn)

[1]P. E. Hart， N. J. Nilsson， and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs[J].IEEE Trans. Syst. Sci. and Cybernetics，SSC-4（2）：100-107，1968.

[2]湯國(guó)安.我國(guó)數(shù)字高程模型與數(shù)字地形分析研究進(jìn)展[J].地理學(xué)報(bào)，2014，69（09）：1305-1325.

[3]李兆旺.電子地圖的內(nèi)涵及其優(yōu)勢(shì)[J].科技視界，2012，（23）：122+226.

[4]王崢.基于GIS的涇河流域特征信息提取分析和降水徑流預(yù)測(cè)[D].西北農(nóng)林科技大學(xué)，2012.

[5]白多寧.軍事地形學(xué)訓(xùn)戰(zhàn)實(shí)用詞典[M].北京：國(guó)防大學(xué)出版社，2010.

[6]Pearl，Judea.Heuristics： Intelligent Search Strategies for Computer Problem Solving[M]. Addison-Wesley Pub.Co，1984.

[7]馬仁利，關(guān)正西.路徑規(guī)劃技術(shù)的現(xiàn)狀與發(fā)展綜述[J].現(xiàn)代機(jī)械，2008，（03）：22-24.