針對不規則機器人路徑規劃改進的A*算法

焦莉莉 王鳳嬌 張蘇林 靳志剛

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

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

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

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

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

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

1 A*算法基本概念

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

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

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

2改進的A*算法

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

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

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

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

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

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

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

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