基于改進A*算法的越障平臺路徑規(guī)劃研究

［摘 要］ 針對傳統(tǒng)方法構(gòu)建的柵格地圖無法準確體現(xiàn)搜救平臺具備越障能力的局限性，將實際環(huán)境劃分為障礙區(qū)、越障通行區(qū)和無障礙區(qū)，依照通行權(quán)重建立了包含3類環(huán)境特征的二維柵格地圖。考慮到越障平臺在越障過程中轉(zhuǎn)向不便的局限，針對性提出了一種改進的A*算法，將路徑轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度作為代價評估函數(shù)的一部分，對算法進行優(yōu)化。將傳統(tǒng)A*算法和改進的A*算法進行對比試驗，實驗結(jié)果表明：與傳統(tǒng)算法相比，改進算法規(guī)劃的路徑、尋路代價有所改善，路徑長度、轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度均大幅減少，更適用于具備越障能力的搜救平臺。

［關(guān)鍵詞］ 越障平臺； 路徑規(guī)劃； A*算法； B樣條曲線

［中圖分類號］ TH122 ［文獻標識碼］ A

搜救機器人作為參與災后搜救和運輸?shù)闹匾ぞ咭阎饾u成為當前的研究熱點。作為搜救機器人的關(guān)鍵技術(shù)之一，路徑規(guī)劃為搜救機器人及時到達指定地點完成救援任務(wù)提供了有力保障。優(yōu)秀的路徑規(guī)劃算法能減少搜救機器人的行駛時間，提高搜救機器人的越野機動性，是當前研究的重點和難點[1]。作為一種啟發(fā)式尋路算法，A*算法已經(jīng)成為各領(lǐng)域、各場景廣泛使用的路徑規(guī)劃算法[2]。傳統(tǒng)A*算法的代價評估函數(shù)以路徑長度作為代價評估的唯一標準，在這種搜索機制下規(guī)劃出的路徑存在著大量彎折，對需要在復雜地形中完成越障而自身轉(zhuǎn)彎不便的搜救平臺而言并非最優(yōu)選擇。事實上，因為轉(zhuǎn)彎次數(shù)過多導致平臺的越障能耗增加，車身時常出現(xiàn)傾斜，極易造成平臺失穩(wěn)。基于此，本文提出了改進的A*算法，根據(jù)越障平臺的越障能耗重新定義和構(gòu)建柵格地圖，并對代價評估函數(shù)進行了改進和優(yōu)化。

1 環(huán)境模型的建立

1.1 建立柵格地圖

本文涉及的越障平臺整體尺寸為800 mm×600 mm×400 mm，整車重20 kg，滿載可負重40 kg，具備翻越200 mm垂直障礙物的越障能力。如圖1所示，在實際工作中越障平臺需要面臨的地形環(huán)境包含紅色圈內(nèi)的障礙區(qū)、藍色圈內(nèi)的越障通行區(qū)和其他無障礙區(qū)。對于越障平臺而言，越障通行區(qū)和無障礙區(qū)都是平臺可以通行的區(qū)域，但相對于無障礙區(qū)，越障平臺在越障通行區(qū)內(nèi)行駛單位路程時間消耗及能耗均會增大，因此基于圖1的環(huán)境建立柵格地圖時需要將二者區(qū)別對待。

根據(jù)搜救平臺的總體尺寸，將環(huán)境劃分成像素大小為1 m×1 m的柵格地圖（圖2）。地圖中黑色柵格表示無法通行的障礙區(qū)，含黑色圓圈的柵格表示可越障通行區(qū)，白色柵格表示無障礙區(qū)。

1.2 確定越障通行區(qū)的代價值

本文涉及的越障平臺為六輪結(jié)構(gòu)，其最大可越障高度為200 mm。將越障平臺滿載時越障消耗的能量與其在平坦路面行駛時消耗的能量進行比較，以確定平臺在越障通行區(qū)行駛時的通行代價。假設(shè)平臺在平坦路面以最快1 m/s的速度勻速行駛，行駛過程中不出現(xiàn)打滑現(xiàn)象，地面的動摩擦系數(shù)μ=0.3。則搜救越障平臺以滿載狀態(tài)在平坦路面行駛1 m所消耗的能量

E1=μmgL（1）

當越障平臺翻越200 mm高度的障礙物時，假設(shè)障礙物為如圖3所示的臺階，則越障平臺需要經(jīng)歷攀爬臺階、走完臺階以及下臺階等3個步驟。現(xiàn)將平臺攀爬臺階和下臺階的過程所消耗的能量近似為其重力勢能的改變量，則越障平臺在越障通行區(qū)走過1 m所消耗的能量

E2≈2mgH+μmgL（2）

其中，H為臺階的高度。假定平臺在無障礙柵格中沿上、下、左、右任意方向移動一格的代價為10，則由式（1）、式（2）計算可得，平臺在越障通行區(qū)，沿上、下左、右任意方向移動一格的代價值約為23。考慮到實際環(huán)境可能更加復雜，將越障平臺在越障通行區(qū)的通行代價值調(diào)整為30。

2 改進A*算法

2.1 A*算法描述

作為一種啟發(fā)式的全局路徑規(guī)劃算法[3]，A*算法采用當前點到起點的距離作為實際代價值，當前點到終點的距離作為預估代價值，二者之和作為當前節(jié)點的代價值，并選取子節(jié)點中代價值最小的點作為下一節(jié)點。重復此過程直到找到目標點[4]。A*算法的代價評估函數(shù)

F（n）=G（n）+H（n）（3）

式中：G（n）為起點到當前點n的實際代價值；H（n）表示當前點n到目標點的估計代價值[5]。由于越障平臺在越障過程中轉(zhuǎn)向存在一定的局限性，本文采用曼哈頓距離來表示當前點至目標點的估計代價值。曼哈頓距離

H（n）=｜xn-xg｜+｜yn-yg｜（4）

2.2 改進A*算法

傳統(tǒng)A*算法將環(huán)境視為理想狀態(tài)，受代價評估函數(shù)評價機制的作用，預估代價會假定距離終點最近的點為代價值最小的點，導致規(guī)劃的路徑出現(xiàn)大量的彎折。研究發(fā)現(xiàn)，如圖4b所示，藍色路線的長度與傳統(tǒng)算法規(guī)劃的路徑長度相等，但路徑中的轉(zhuǎn)折次數(shù)明顯減少。

基于此，本文改進了A*算法的搜索機制，將路徑轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度作為代價評估函數(shù)的一部分，重新定義了代價評估函數(shù)：

F（n）=G（n）+H（n）+T（n）+θn（5）

式中：n為當前點，F(xiàn)（n）為總的代價值；G（n）為起點到當前點的實際代價；H（n）為當前點到目標點的估計代價；T（n）為從起點出發(fā)至當前點路徑中出現(xiàn)的轉(zhuǎn)彎次數(shù)；θn為從當前點的父節(jié)點到當前點的方向向量與從當前點到當前節(jié)點的子節(jié)點的方向向量之間的夾角。

綜合上述分析，完成對本文改進A*算法的設(shè)計，其處理流程如圖5所示。

3 實驗仿真及結(jié)果分析

為驗證本文改進A*算法的合理性，在MATLAB R2016b環(huán)境中分別構(gòu)建傳統(tǒng)柵格地圖和改進的柵格地圖，將傳統(tǒng)A*算法和改進的A*算法進行對比試驗。計算機配置為：WINDOWS10系統(tǒng)，處理器Intel（R） Core（TM） i5-8400，主頻2.8 GHz，運行內(nèi)存32 GB。

3.1 路徑規(guī)劃仿真實驗

本實驗以越障平臺實際工作環(huán)境為原型，分別建立傳統(tǒng)二維柵格地圖和改進的二維柵格地圖，并選取不同的起點和終點對傳統(tǒng)A*算法與本文改進的A*算法進行仿真對比試驗。

實驗一：使用傳統(tǒng)地圖構(gòu)建方法構(gòu)建二維柵格地圖，對傳統(tǒng)算法和改進的算法選擇多個起點、終點在傳統(tǒng)地圖中進行仿真對比試驗，結(jié)果如圖6所示。

實驗二：使用本文改進的方法構(gòu)建二維柵格地圖，對傳統(tǒng)算法和改進算法選擇多個起點、終點在改進的地圖中進行仿真對比試驗，結(jié)果如圖7所示。

實驗三：將改進的A*算法分別置于傳統(tǒng)方法構(gòu)建的柵格地圖和本文改進方法構(gòu)建的柵格地圖中進行仿真對比試驗，結(jié)果如圖8所示。

將實驗的結(jié)果分別進行統(tǒng)計，統(tǒng)計結(jié)果見表1—3。

由表1可知，在傳統(tǒng)方法構(gòu)建的地圖中，與傳統(tǒng)A*算法相比改進的算法路徑長度和搜索代價值略有減小，而路徑中的轉(zhuǎn)彎次數(shù)及轉(zhuǎn)彎角度有了明顯減少，路徑更加平滑。

由表2可知，在改進方法構(gòu)建的地圖中，與傳統(tǒng)A*算法相比改進的算法路徑長度基本不變，搜索代價值略有減小，路徑中的轉(zhuǎn)彎次數(shù)及轉(zhuǎn)彎角度有了明顯減少，路徑更加平滑。

由表3可知，使用改進的A*算法在改進的地圖中規(guī)劃的路徑與在傳統(tǒng)地圖中規(guī)劃的路徑相比，路徑長度減少，代價值減小，轉(zhuǎn)彎次數(shù)及轉(zhuǎn)彎角度略有增加，符合預期目標。

綜合表1、表2、表3可知，與傳統(tǒng)A*算法相比，改進的算法尋路代價有所改善，路徑長度、轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度均大幅減少，路徑更加平滑，更適用于在復雜工作環(huán)境中具備越障能力的越障搜救平臺。

3.2 路徑平滑處理

機器人在行駛路線中出現(xiàn)轉(zhuǎn)角時在轉(zhuǎn)向過程中極易出現(xiàn)抖動，導致偏航，而在修正路徑時會消耗大量的時間和能源，因此對柵格路徑進行平滑處理以保證越障平臺在越障過程中擁有良好的行駛狀態(tài)是十分必要的[6]。

B樣條曲線作為路徑規(guī)劃中路徑平滑處理的常用工具，因其具有集合保凸性、不變性、凸包性等特點而被廣泛使用[7]。本文采用3次均勻B樣條曲線對改進A*算法規(guī)劃的柵格路徑作平滑處理。B樣條曲線表達式為：

采用3次B樣條曲線對改進的A*算法以（13，13）為起點，（25，46）為終點規(guī)劃的路徑作平滑處理。處理結(jié)果如圖9所示。其中，紅色路線為處理前的路徑，藍色路線為B樣條處理后的路徑。從圖9中可以看出，經(jīng)過處理，路徑變得十分平滑，更適合用于指導越障平臺。

4 結(jié)束語

本文針對傳統(tǒng)A*算法在構(gòu)建柵格地形和代價評估函數(shù)時沒有將其與實際應用場景相結(jié)合的不足，根據(jù)越障平臺實際工作環(huán)境及其越障能力提出了一種改進的A*算法。將越障平臺工作環(huán)境進行劃分，依照通行權(quán)重建立了包含3類環(huán)境特征的二維柵格地圖。針對越障平臺在越障過程中轉(zhuǎn)向不便的局限，將路徑轉(zhuǎn)彎角度和轉(zhuǎn)彎次數(shù)作為路徑規(guī)劃代價評估函數(shù)的一部分，對A*算法進行了改進。最后，通過仿真對比實驗，驗證了本文改進A*算法的優(yōu)越性，并使用3次B樣條曲線對路徑進行了平滑處理，得到了適用于越障平臺的更優(yōu)路徑，適用于指導具備越障能力的越障平臺高效完成搜救任務(wù)。

本研究工作主要不足有：1）在地形識別時，未針對不同障礙物類型作細化區(qū)分，構(gòu)建的柵格地圖越障通行區(qū)的通行代價計算較為籠統(tǒng)，后期有望改進地形識別算法，細化障礙物類別從而提升柵格地圖構(gòu)建的準確性以提高路徑規(guī)劃精度；2） 代價評估函[LL]數(shù)中各影響因素的權(quán)值系數(shù)未做確定，后期有望通過重復實驗進行擬合，提高代價評估的準確性；3）本文設(shè)計的路徑規(guī)劃算法針對的實驗場景區(qū)域較小，其主要受限于項目中地形識別和重建能力，后期有望結(jié)合其他地形探測設(shè)備為越障平臺動態(tài)的提供全局地圖，從而增大平臺的路徑規(guī)劃區(qū)域，提高其實際應用能力。

［ 參 考 文 獻 ］

［1］ 馬小陸，梅宏，龔瑞，等.基于改進ACS算法的移動機器人路徑規(guī)劃研究[J].湖南大學學報（自然科學版），2021，336（12）：79-88.

[2] 楊俊成，李淑霞，蔡增玉.路徑規(guī)劃算法的研究與發(fā)展[J].控制工程，2017，24（07）：1473-1480.

[3] 秦玉鑫，王紅旗，杜翠杰.基于雙層A*算法的移動機器人路徑規(guī)劃[J].制造業(yè)自動化，2014，36（24）：21-25.

[4] 霍鳳財， 遲金， 黃梓健， 等. 移動機器人路徑規(guī)劃算法綜述[J].吉林大學學報（信息科學版）， 2018， 36（06）：639-647.

[5] 楊興，張亞，楊巍，等.室內(nèi)移動機器人路徑規(guī)劃研究[J].科學技術(shù)與工程，2016，16（15）：234-238.

[6] 程傳奇，郝向陽，李建勝，等.融合改進A*算法和動態(tài)窗口法的全局動態(tài)路徑規(guī)劃[J].西安交通大學學報，2017，51（11）：137-143.

[7] 張敬寒，陶兆勝，彭澎，等.基于擴大搜索鄰域A*算法的平滑路徑規(guī)劃[J].長春理工大學學報（自然科學版），2018，41（06）：124-127.

Research on Path Planning of Obstacle Crossing Search and Rescue Platform Based on Improved A* Algorithm

CHEN Xiaoli， ZHAO Di， WANG Xiongjin

（School of Mechanical Engineering， Hubei Univ. of Tech.， Wuhan 430068， China）

Abstract： In view of the limitation that the grid map constructed by the traditional method can not accurately reflect the obstacle crossing ability of the search and rescue platform， this paper divides the actual environment into obstacle area， obstacle crossing traffic area and barrier free area， and establishes a two-dimensional grid map containing three types of environmental characteristics according to the traffic weight. Considering the limitation of inconvenient turning of obstacle crossing platform in the process of obstacle crossing， this paper proposes an improved A* algorithm， which optimizes the algorithm by taking the number of path turns and turning angle as part of the cost evaluation function. Finally， the traditional A* algorithm and the improved A* algorithm are compared. The experimental results show that compared with the traditional algorithm， the path planning cost of the improved algorithm is improved， and the path length， turning times and turning angle are greatly reduced. It is more suitable for the search and rescue platform with obstacle crossing ability.

Keywords： obstacle crossing platform; route planning; A* algorithm; B-spline curve

［責任編校： 張 眾］

［收稿日期］ 2022-03-04

［基金項目］ 軍隊后勤科研國家級項目（BS318J009）

［第一作者］ 陳小利（1997-），男，湖北荊門人，湖北工業(yè)大學碩士研究生，研究方向為智能機器人。

［通信作者］ 趙 迪（1981-），男，湖北武漢人，湖北工業(yè)大學副教授，研究方向為機械設(shè)計及理論、智能機器人、虛擬現(xiàn)實。