焦莉莉 王鳳嬌 張?zhí)K林 靳志剛

摘要：對復雜環(huán)境下移動機器人全局路徑規(guī)劃問題進行研究，提出一種針對不規(guī)則機器人路徑規(guī)劃改進的A*路徑規(guī)劃算法。首先，對全局運動空間進行建圖錄制;然后，將全局地圖根據(jù)碰撞空間進行地圖預處理，運用改進的A*算法規(guī)劃一條從起點到終點的全局路徑;最后在vs平臺將A*路徑規(guī)劃算法與改進的A*路徑規(guī)劃算法進行對比實驗。實驗結果表明：文中方法較全局路徑規(guī)劃A*算法任務的效率明顯提升。

關鍵詞：移動機器人;全局路徑規(guī)劃;A*算法

中圖分類號：TP3? ? ? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）27-0098-03

在科學技術快速發(fā)展的今天，機器人在日常生活中得到廣泛的應用，其中路徑規(guī)劃是機器人技術的一個重要組成部分。機器人的路徑規(guī)劃指在特定的工作環(huán)境中，不斷查詢障礙物信息從而找出一條從起始點到目標終點的可通行路徑。路徑規(guī)劃算法是實現(xiàn)機器人自主移動的關鍵前提。近年來路徑規(guī)劃的算法研究也被國內(nèi)外學者所熱衷。

目前路徑規(guī)劃算法主要有以下幾種：基于圖搜索的路徑規(guī)劃算法，如A*、D*、人工勢場法、柵格圖法等;基于智能仿生學的路徑規(guī)劃算法，如遺傳算法、蟻群算法等;基于圖搜索算法，雖然能夠收斂到路徑最優(yōu)，但隨著空間緯度的增加會導致算法的復雜化;對于智能仿生學算法在進行路徑搜索時可能會陷入局部最小值。為了更好地解決上述路徑規(guī)劃算法局限，有關學者提出一種基于采樣的路徑規(guī)劃算法，主要包括概率路標算法[1]（PRM）和快速拓展隨機樹算法[2]（RRT）。

1 A*算法基本概念

A*算法的基本思想是從起點開始根據(jù)評價函數(shù)不斷向目標終點的方向進行搜索，通過數(shù)據(jù)容器記錄每次搜索確定的點，最后搜索到目標點，從而獲得最小代價的全局路徑。A*算法定義，移動機器人基于在當前柵格尋路時，通常選擇八鄰域法，即有8個鄰域可作為下一步運動方向，分別為正前、正后、正左、正右、左前、左后、右前、右后。

A*算法目的在于獲得最小的代價路徑，其中評價函數(shù)為f（ n） = g（ n） + h（ n）。評價函數(shù)中f（n）的物理意義為當前點的評價函數(shù)， g（ n） 的物理意義為過去代價函數(shù)，用于評價起始點到當前節(jié)點的代價，h（ n） 的物理意義為當前成本函數(shù)，用于評價當前節(jié)點到目標節(jié)點的代價。g（n）通常用固定的數(shù)值表示，但h（n）通常不是固定的，h（n）的表達式選擇會影響到f（n）最小代價函數(shù)的合理性?；谝陨系脑O計，啟發(fā)函數(shù)h（n）設計為A*算法的關鍵要素。合理的啟發(fā)函數(shù)設計能提高尋路效率。啟發(fā)函數(shù)常見四種表達式，其中最常用的是曼哈頓距離。

曼哈頓距離指代x坐標方向距離與y坐標方向距離之和，啟發(fā)函數(shù)表示：h（n）=D*[abs（xb-xn）+abs（yb-yn）]，（xb，yb）為目標節(jié)點坐標，（xn，yn）為當前結點坐標，其中D表示h（n）啟發(fā)函數(shù)的代價系數(shù)，針對不同地圖環(huán)境，通常選用不同的代價系數(shù)，本方案選擇10為代價系數(shù)。例如文獻[3]根據(jù)當前結點和目標結點的距離不同，嘗試了不同的代價系數(shù)D，從而實現(xiàn)障礙物環(huán)境地圖不變時降低搜索時間。

2改進的A*算法

文獻[4]提出了一種融合改進A*算法和動態(tài)窗口法的全局動態(tài)路徑規(guī)劃方法。但是A *算法的效率仍然比較低，如果地圖中存在比較多的U 型和 L 型等特殊障礙物時，A *算法仍然需要訪問大量無效地圖空間。因此，在路徑規(guī)劃的實際應用中，當?shù)貓D環(huán)境機器人通道空間比較寬闊時常常把地圖障礙物按照機器人半徑膨脹處理后再調用A*尋路算法。這樣可以減少A*算法的搜索時間。

但我們所研究的項目中機器人為車型機器人，地圖環(huán)境中機器人的通道空間比較狹窄，將車型機器人按照車型機器人半徑進行障礙物膨脹處理時會導致狹窄區(qū)域沒有路徑。

針對這一問題增加不規(guī)則機器人的障礙物碰撞邏輯。A*算法的搜索實質上是對當前柵格相鄰的柵格正前、正后、正左、正右、左前、左后、右前、右后進行碰撞預判，如果相鄰柵格超出地圖邊界、相鄰柵格為障礙物區(qū)域或者相鄰柵格之前搜索過即相鄰柵格在關閉列表中，則添加該相鄰柵格進關閉列表，其他情況則將相鄰柵格添加進開啟列表。增加不規(guī)則機器人的障礙物碰撞邏輯就在這一步添加，在加入開啟列表或關閉列表前，額外再加一個條件（以鄰接柵格為中心，以目標車的方向和大小構建下一步車的位置，判斷下一步該車是否會覆蓋到不可走狀態(tài)的柵格——即與障礙物不能碰撞），若滿足此額外條件，相鄰接柵格加入開啟列表，否則添加該相鄰柵格進關閉列表。

在增加的不規(guī)則機器人的障礙物碰撞邏輯中，目標車邊界柵格在左前、左后、右前、右后已經(jīng)不是一行或者一列，而是傾斜的，但是注意到左前、左后、右前、右后四個方向柵格傾斜的角度為45的奇數(shù)倍，依次將左前、左后、右前、右后四個方向用兩個循環(huán)來判斷長和寬邊界;利用計算幾何的思路計算此時虛線矩形的四個邊角點a1、a2、a3和a4，每一個邊角點由車形機器人的幾何中心以一定的角度向外延伸一定的半徑計算得來。注意，代碼中對于目標車越界情況進行處理-即目標車虛線矩形邊界覆蓋到了柵格地圖的外面，判定此時目標車幾何中心所在柵格的相鄰柵格進入關閉列表。

通過實際項目測試，可滿足車型機器人狹窄區(qū)域路徑規(guī)劃要求。

3針對不規(guī)則機器人路徑規(guī)劃的預處理算法

上述A*算法，增加了條件2的約束增加了算法的復雜性，延長了算法計算周期。在實際項目中增加條件2的地圖預處理功能。即將條件2作為地圖柵格化的一個已知元素。在實時A*路徑規(guī)劃中降低了算法的計算周期。

本算法驗證通過Windows操作系統(tǒng)的VisualStudio2010開發(fā)平臺。算法主要分為3個功能模塊，地圖構建模塊、地圖預處理模塊和主程序模塊。