基于通行性分析的分層越野路徑規(guī)劃方法

閆星宇，杜偉偉，石 昊

（北方自動(dòng)控制技術(shù)研究所，太原 030006）

0 引言

在戰(zhàn)場(chǎng)環(huán)境下，機(jī)動(dòng)部隊(duì)在避險(xiǎn)行進(jìn)、野外行進(jìn)、隱蔽行進(jìn)等機(jī)動(dòng)任務(wù)中，需要完成野外環(huán)境下幾十乃至上百公里的大范圍地域越野路徑規(guī)劃。相對(duì)于傳統(tǒng)的有路網(wǎng)路徑規(guī)劃，越野路徑規(guī)劃需要處理大量環(huán)境信息，如坡度限制、地表覆蓋及地面起伏程度等，在面臨大范圍地域的野外路徑規(guī)劃問題時(shí)，會(huì)面臨數(shù)據(jù)量激增，計(jì)算量過大的挑戰(zhàn)。因此，研究大范圍地域越野條件下機(jī)動(dòng)車輛的路徑規(guī)劃方法，對(duì)戰(zhàn)場(chǎng)環(huán)境下的部隊(duì)執(zhí)行機(jī)動(dòng)任務(wù)具有重要意義。

由于越野路徑規(guī)劃計(jì)算量較大，為了解決實(shí)時(shí)性問題，常使用縮小搜索空間的啟發(fā)式算法進(jìn)行規(guī)劃。A*算法屬于啟發(fā)式搜索算法的優(yōu)化算法，其算法建立在Dijkstra和BFS算法基礎(chǔ)上，是一種廣泛使用的路徑規(guī)劃算法。范林林等設(shè)計(jì)了以通行速度為估價(jià)函數(shù)的A*算法，多維考慮了地貌因素對(duì)車輛越野行車速度的影響，但環(huán)境建模時(shí)選取的柵格較大，無法準(zhǔn)確衡量柵格的通行性能。吳天羿等設(shè)計(jì)了考慮坡度和粗糙度約束的A*路徑優(yōu)化算法；王坤等設(shè)計(jì)了基于禁忌表的越野路徑規(guī)劃算法，充分考慮了野外地理環(huán)境對(duì)車輛通行能力的影響，但存在處理數(shù)據(jù)過多，時(shí)效性下降的問題。

盡管目前越野路徑規(guī)劃方法和傳統(tǒng)道路路徑規(guī)劃方法相比較，能夠考慮環(huán)境因素對(duì)機(jī)動(dòng)車輛機(jī)動(dòng)能力的影響，但詳盡的環(huán)境數(shù)據(jù)分析使路徑規(guī)劃數(shù)據(jù)量過大，在處理大范圍地域的部隊(duì)野外機(jī)動(dòng)業(yè)務(wù)時(shí)，會(huì)因?yàn)樘幚頂?shù)據(jù)過多、計(jì)算量過大而無法保持時(shí)效性。同時(shí)，如果為了減少計(jì)算量而降低路徑柵格分辨率，又會(huì)導(dǎo)致規(guī)劃結(jié)果不可靠。

1 分層越野路徑規(guī)劃方法

1.1 大范圍地域的越野路徑規(guī)劃問題

越野環(huán)境下的路徑規(guī)劃需要在無路網(wǎng)條件下規(guī)劃車輛的行進(jìn)路線，使得車輛在該路徑行駛時(shí)，時(shí)間及油料等綜合耗費(fèi)最少，該問題可以建模為：

其中，Z 為路徑總耗費(fèi)；S 為任務(wù)區(qū)域；（x，y）為路徑點(diǎn)；f（x，y）為該路徑點(diǎn)的通行耗費(fèi)。由于在越野機(jī)動(dòng)時(shí)，車輛受到環(huán)境的影響比起道路行駛時(shí)更大，為了保證機(jī)動(dòng)任務(wù)順利進(jìn)行，f（x，y）需要綜合考慮地表覆蓋種類和地形起伏程度對(duì)車輛通行能力的影響。

1.2 分層越野路徑規(guī)劃方法

越野環(huán)境下的路徑規(guī)劃為了更加準(zhǔn)確地描述環(huán)境，需要將（x，y）代表的柵格大小適配車輛長寬，導(dǎo)致數(shù)據(jù)量和計(jì)算量過大，極大地影響了路徑規(guī)劃的時(shí)效性。因此，需要一種路徑規(guī)劃方法，在合理量化環(huán)境影響數(shù)據(jù)的前提下，提高大范圍地域越野路徑規(guī)劃時(shí)的實(shí)效性和準(zhǔn)確性，本文使用分層規(guī)劃方法解決這一問題。

如圖1 所示，分層越野路徑規(guī)劃方法是指將野外路徑規(guī)劃過程分層，在兩個(gè)不同分辨率下對(duì)野外區(qū)域環(huán)境進(jìn)行分層建模，并在低分辨率模型規(guī)劃結(jié)果的基礎(chǔ)上進(jìn)行高分辨率路徑規(guī)劃。

圖1 分層越野路徑規(guī)劃方法示意圖

整體方法流程如圖2 所示。

圖2 分層越野路徑規(guī)劃方法流程圖

1）根據(jù)任務(wù)區(qū)域裁切地圖數(shù)據(jù)、確定高低分辨率比例，并以兩種不同分辨率分層構(gòu)建柵格模型。

2）使用針對(duì)通行速度優(yōu)化的A*算法對(duì)低分辨率柵格模型進(jìn)行路徑規(guī)劃，并輸出規(guī)劃結(jié)果。

3）使用考慮避障的A*算法在高分辨率層，依次處理低分辨率規(guī)劃結(jié)果所經(jīng)過的每個(gè)區(qū)域。

4）將所有高分辨率層的路徑規(guī)劃結(jié)果合并輸出。

2 分層環(huán)境建模及通行性分析

2.1 分層環(huán)境建模

越野路徑規(guī)劃由于沒有路網(wǎng)拓?fù)漭o助，首先需要進(jìn)行野外環(huán)境建模，即對(duì)地理環(huán)境進(jìn)行描述，主要是對(duì)需要的區(qū)域環(huán)境信息進(jìn)行特征提取和表達(dá)。常用的環(huán)境模型有可視圖法、Voronoi 圖法、拓?fù)鋱D法和柵格圖法等。其中，柵格化建模能夠清晰地描述環(huán)境信息，并且建模簡(jiǎn)單、維護(hù)方便、易于構(gòu)建高效的數(shù)據(jù)索引，是大多數(shù)路徑規(guī)劃方法的首選。柵格大小的選取直接影響著路徑規(guī)劃算法的性能，想要更準(zhǔn)確的環(huán)境描述，柵格就要盡可能地小，但是存儲(chǔ)數(shù)據(jù)量會(huì)急劇增大，使得計(jì)算量大幅增加，系統(tǒng)實(shí)時(shí)性降低；與之相對(duì)的，柵格選取較大、數(shù)據(jù)量變小能夠有效提高路徑規(guī)劃速度，但會(huì)導(dǎo)致對(duì)環(huán)境障礙敏感度降低，無法規(guī)劃出有效路徑。為此，本文采取分層環(huán)境建模的方式解決柵格大小選取的矛盾問題。

分層環(huán)境建模的基本思想是使用高程數(shù)據(jù)和地表覆蓋數(shù)據(jù)，對(duì)規(guī)劃區(qū)域分層構(gòu)建柵格模型。首先對(duì)大范圍區(qū)域內(nèi)的野外環(huán)境進(jìn)行低分辨率柵格化，每個(gè)柵格都保存有地表覆蓋類型和柵格區(qū)域粗糙度數(shù)據(jù)，然后再次對(duì)野外環(huán)境進(jìn)行高分辨率柵格化，每個(gè)柵格都保存有坡度數(shù)據(jù)。通常高分辨率柵格可以采用5 m 分辨率，而低分辨率柵格需要結(jié)合實(shí)際任務(wù)區(qū)域計(jì)算得到，一般保持兩個(gè)分辨率的路徑規(guī)劃層單次處理數(shù)據(jù)量相近，可以通過如下方式得到：

設(shè)整個(gè)區(qū)域邊長為R，低分辨率柵格長度為r，則

將r 值取整百即可作為低分辨率柵格邊長。

2.2 地表通行性分析

在低分辨率柵格模型中，地形量化主要考慮地表覆蓋類型和地形起伏對(duì)車輛機(jī)動(dòng)能力的影響。在柵格中，將地表覆蓋類型的影響量化為地表覆蓋通行度，越難以通行的地表覆蓋類型，設(shè)置其通行度越低；將地形起伏的影響量化為地表粗糙度，通過計(jì)算區(qū)域內(nèi)各高程點(diǎn)到擬合平面距離的方差得到。

根據(jù)全球30 m 地表覆蓋（GlobeLand30）數(shù)據(jù)集，將地表覆蓋類型分為農(nóng)田、森林、草地、灌叢、濕地、水體、苔原和不透水層、裸地和冰雪。根據(jù)不同地表對(duì)車輛通行能力的影響，分別設(shè)置地表覆蓋通行度如表1 所示。

表1 地表屬性通行度表

假設(shè)柵格區(qū)域內(nèi)有m 個(gè)地表覆蓋數(shù)據(jù)點(diǎn)，任意一個(gè)點(diǎn)的通行度為r，則區(qū)域地表覆蓋通行度可由如下公式獲?。?/p>

在高分辨率情況下，地形量化主要考慮因坡度形成的障礙對(duì)車輛行進(jìn)的影響。在量化時(shí)，將坡度大于車輛最大爬坡度的柵格設(shè)置為不可通行。高分辨率地形的高程數(shù)據(jù)來源于5 m 分辨率的柵格，設(shè)每個(gè)柵格高程值為H。

本文引入窗口移動(dòng)法，計(jì)算當(dāng)前柵格于其相鄰8 個(gè)柵格的坡度大小。窗口移動(dòng)法采用3×3 窗口，如下頁圖3 所示。

圖3 柵格的鄰接八坡度示意圖

以逆時(shí)針方向順序，以此計(jì)算相鄰柵格相對(duì)于中心點(diǎn)（i，j）的坡度大小S，其中，1≤k≤8。具體公式如下：

當(dāng)arctan（S）小于車輛最大爬坡度時(shí)，該相鄰柵格可通行。

3 分層越野路徑規(guī)劃算法

3.1 改進(jìn)A＊算法

啟發(fā)式A* 算法是路徑規(guī)劃中使用最多的算法。傳統(tǒng)意義上的A*算法是以周圍地形信息一致的前提下進(jìn)行的，即假設(shè)同距離下消耗相同，而在研究戰(zhàn)場(chǎng)環(huán)境下的最短路徑問題時(shí)，需要考慮地形因素對(duì)車輛機(jī)動(dòng)的影響。在研究低分辨率模型的路徑規(guī)劃時(shí)，將地表覆蓋通行度和地表粗糙度作為消耗系數(shù)，對(duì)實(shí)際通行距離進(jìn)行放縮來描述柵格之間的實(shí)際消耗；在研究高分辨率模型的路徑規(guī)劃時(shí)，使用當(dāng)前地格到目標(biāo)地格的距離來描述柵格之間的實(shí)際消耗。

A*算法的運(yùn)作需要維護(hù)Open、Closed、PassCost 3 個(gè)表，Open 表負(fù)責(zé)存儲(chǔ)待檢查的柵格，初始化時(shí)將起始柵格放入Open 表中。Closed 表用來存儲(chǔ)所有不需要再次考察的柵格，從而避免重復(fù)搜索已通行的柵格，初始化時(shí)將所有不可通行的柵格加入到Closed 表中。PassCost 表用來檢查當(dāng)前柵格的鄰域柵格的可通行性。

3.2 柵格距離模型

由于模型采用正方形柵格的方式建模兩點(diǎn)之間的距離估算可以按照?qǐng)D4 建模，因此，模型中任意兩點(diǎn)之間的距離D 可以表示為：

圖4 起終點(diǎn)之間的距離估算

3.3 估價(jià)函數(shù)優(yōu)化

啟發(fā)式A*算法中估價(jià)函數(shù)定義為f（i，j）=g（i，j）+h（i，j），f（i，j）為算法在當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的啟發(fā)函數(shù)，它由兩部分組成，第1 部分g（i，j）是起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)實(shí)際的通行代價(jià)，第2 部分h（i，j）是當(dāng)前節(jié)點(diǎn)到終點(diǎn)的通行代價(jià)的估計(jì)值。

在低分辨率層進(jìn)行規(guī)劃時(shí)，實(shí)際消耗g（i，j）通過實(shí)際距離、柵格地表覆蓋通行度和柵格地表粗糙度計(jì)算得出的通行時(shí)間衡量，其公式為：

在高分辨率層進(jìn)行規(guī)劃時(shí)，需要建立一個(gè)tabu 表，用于標(biāo)記柵格相對(duì)于相鄰格網(wǎng)的通行禁忌表，當(dāng)柵格（i，j）的坡度大于最大爬坡度時(shí)，令tabu（i，j）=0。

柵格（i，j）的實(shí)際消耗g（i，j）。通過實(shí)際距離衡量，其公式為：

3.4 算法流程

在給定起始格元S 和目標(biāo)格元E 的前提下，戰(zhàn)場(chǎng)環(huán)境下機(jī)動(dòng)車輛生成最短路徑的A* 算法流程，如圖5 所示。

圖5 A*算法步驟流程

4 實(shí)驗(yàn)結(jié)果及分析

本文提出的越野路徑規(guī)劃方法在國產(chǎn)麒麟系統(tǒng)平臺(tái)上實(shí)現(xiàn)仿真，采用的數(shù)據(jù)是某地ALOS PALSAR 12.5 m DEM 數(shù)據(jù)經(jīng)過插值計(jì)算得到的5 m 高程數(shù)據(jù)以及清華大學(xué)2017 年全球10 m 分辨率地表覆蓋數(shù)據(jù)，空間范圍為65 km×75 km，規(guī)劃區(qū)域展示如圖6 所示。本實(shí)驗(yàn)以國內(nèi)最多的現(xiàn)役主戰(zhàn)坦克96 式坦克在該區(qū)域執(zhí)行越野任務(wù)為背景，根據(jù)坦克最大爬坡度，將坡度約束設(shè)為31°。為了保證坦克行進(jìn)路線的可行性，規(guī)劃路線分辨率應(yīng)以5 m 以上精度為優(yōu)。

圖6 規(guī)劃區(qū)域展示

實(shí)驗(yàn)中使用本文提出的分層越野路徑規(guī)劃方法和A*避障算法尋路方法，對(duì)不同分辨率條件下的地圖數(shù)據(jù)進(jìn)行仿真模擬。分別設(shè)定A*避障算法規(guī)劃分辨率為50 m 和20 m，分層越野路徑規(guī)劃方法規(guī)劃分辨率為20 m 和5 m。

圖7 為使用避障A*算法規(guī)劃在地圖數(shù)據(jù)上進(jìn)行規(guī)劃的結(jié)果，其中，陰影區(qū)域越濃代表坡度越大，粗線為50 m 分辨率規(guī)劃結(jié)果，細(xì)線為20 m 分辨率規(guī)劃結(jié)果。

圖7 A*坡度避障規(guī)劃結(jié)果（局部）

圖8 為分層越野路徑規(guī)劃方法在低分辨率層上的規(guī)劃結(jié)果，左圖展示了低分辨率層規(guī)劃結(jié)果在區(qū)域高程地圖上的情況。右圖展示了低分辨率層規(guī)劃結(jié)果在區(qū)域地表覆蓋地圖上的情況，區(qū)域內(nèi)地表覆蓋主要為黃色裸地、綠色草地，并伴有少量藍(lán)色水體、白色冰雪、深綠森林等。

圖8 低分辨率規(guī)劃結(jié)果

圖9 為高分辨率層規(guī)劃結(jié)果在區(qū)域坡度地圖上的部分展示。其中，陰影區(qū)域越濃代表坡度越大，透明區(qū)域?yàn)榈头直媛蕦右?guī)劃路徑，粗線為20 m 分辨率規(guī)劃結(jié)果，細(xì)線為5 m 分辨率規(guī)劃結(jié)果。

圖9 高分辨率規(guī)劃結(jié)果（局部）

表2 為A*避障算法規(guī)劃和分層越野路徑規(guī)劃在不同分辨率條件下進(jìn)行實(shí)驗(yàn)的結(jié)果對(duì)比。

表2 兩種路徑規(guī)劃方法結(jié)果對(duì)比表

從以上實(shí)驗(yàn)結(jié)果能夠看出：

1）基于通行性分析的分層越野路徑規(guī)劃所選擇的通行區(qū)域有著更易通行的地表覆蓋和更平坦的路面。比起直接使用A*避障算法，基于通行性分析的分層越野路徑規(guī)劃方法產(chǎn)生的規(guī)劃結(jié)果不僅能夠避開坡度障礙，還能引導(dǎo)車輛避開通行性較差的復(fù)雜地域。

2）基于通行性分析的分層越野路徑規(guī)劃方法能夠有效縮減越野路徑規(guī)劃的規(guī)劃時(shí)長，并能夠完成高精度的路徑規(guī)劃來保證路線可行性。實(shí)驗(yàn)結(jié)果表明，未經(jīng)優(yōu)化的A*算法在分辨率由50 m 提升至20 m 時(shí)，規(guī)劃時(shí)長急劇升高，并且由于單次規(guī)劃數(shù)據(jù)量過大，無法順利完成實(shí)驗(yàn)背景下分辨率為5 m的越野路徑規(guī)劃任務(wù)；而分層越野路徑規(guī)劃方法在相同分辨率條件下有更好的表現(xiàn)，且規(guī)劃時(shí)長受分辨率影響較小，當(dāng)分辨率達(dá)到5 m 時(shí)仍然能夠以較短的時(shí)間完成越野路徑規(guī)劃，從而及時(shí)為坦克部隊(duì)完成路徑規(guī)劃任務(wù)，并保證規(guī)劃結(jié)果的可行性。

5 結(jié)論

本文使用分層越野路徑規(guī)劃和改進(jìn)后的A*算法，對(duì)大范圍地域的車輛越野路徑規(guī)劃問題進(jìn)行了研究。通過提出分層規(guī)劃概念，設(shè)計(jì)了基于通行性分析的分層越野路徑規(guī)劃方法。在規(guī)劃算法中，引入了考慮地表覆蓋和地形粗糙度的通行性分析，設(shè)計(jì)了考慮地表覆蓋通行度和地表粗糙度約束的改進(jìn)A*路徑規(guī)劃算法。仿真結(jié)果表明，本規(guī)劃方法相對(duì)于傳統(tǒng)A*算法，能夠降低規(guī)劃過程計(jì)算量，并規(guī)劃出更加合理的越野區(qū)域通行路徑。

本文在進(jìn)行通行性分析時(shí)參數(shù)仍可以優(yōu)化，下一步研究工作可以繼續(xù)在相關(guān)方面進(jìn)行研究，用以完善A*算法的估價(jià)函數(shù)。