改進A*算法在噴漿機器人路徑規劃中的研究

蘇 暢,袁 泉,李子強,余曉帆

(安徽理工大學 機械工程學院,安徽 淮南 232001)

基于目前國家智慧礦山建設的背景,噴漿機器人的研發與應用獲得了較大的進步。作為一種電子、機械、人工智能等多學科交叉融合的復雜系統,自主行走能力是噴漿機器人在礦井環境應用中的重要性能標準[1]。由于井下巷道復雜的環境情況,噴漿機器人需要具備自主運動能力,以及對巷道環境的感知和路徑規劃能力,以高效、可靠的完成噴漿作業。其中,路徑規劃是非常關鍵的,為了保障了機器人可以順利的抵達目標點[2],需要機器人在未知環境中規劃出一條從起點到目標點的平穩路徑,常見的路徑規劃算法包括Dijkstra算法[3]、A*算法[4]、D*算法[5]、D*Lite算法[6]。其中,D*和D*Lite算法多用于不確定的動態環境,而在已知的靜態環境下,Dijkstra和A*算法可以更快速地找到最優路徑。Dijkstra算法是以搜索點與起點之間的代價為基礎來搜索最短路徑,但由于其搜索范圍太大,使得搜索效率低下。A*算法是在Dijkstra算法的基礎上添加啟發函數的路徑搜索算法,并綜合考慮了搜索點與起點以及搜索點與目標點兩種代價,這樣可以平衡路徑代價和搜索時間。但是在實際的噴漿機器人路徑規劃中,A*算法存在安全性低,轉折路徑多,平滑性較差等問題。

針對以上問題,目前學者們已經提出了許多改進A*算法。王中玉等[7]通過調整計算方法與函數比例來減少路徑搜索時間和多余節點數目。辛煜等[8]在經典A*算法的基礎上,將可搜索鄰域數目從八個擴展到了無限個,并且可以在任何方向進行搜索,既減少了求解的路徑長度,又極大的降低了拐點的數量。趙以毛等[9]重新設計啟發式函數,減少了機器人路徑規劃的時間,且規劃的路徑更加平滑。吳飛龍等[10]對傳統評價函數作出改進,同時設置了安全閾值并對路徑節點進行優化。陳靖輝等[11]采用定向搜索的方法去除了對稱搜索路徑,由此減少了經過的節點數量。ZHANG等[12]首先通過經典A*算法規劃出一條從起點到目標點的安全路徑,再利用關鍵點選擇方法進行二次規劃,將路徑中多余的中間節點刪除,只保存起點、拐點和目標點,從而減少了搜索節點的數目和規劃時間。陳若男等[13]利用領域矩陣方法對障礙物進行搜索,雖然改進了路徑的安全性,但是路徑的搜索效率并沒有得到提高。本文在以上研究的基礎上,對A*算法的評價函數,子節點的選取方式,以及路徑平滑等方面進行改進,使改進算法在路徑規劃中具有快速,高效,更平滑,安全性更強的特點。

1 A*算法

1.1 環境建模

環境建模指的是在進行路徑規劃之前,噴漿機器人通過視覺或激光傳感器將真實的物理環境轉變成計算機能夠識別的抽象環境。W.E.Howden在1968年提出了柵格法[14],因為這種方法在計算障礙物信息時較為簡單,而且容易實現,因此被普遍地用于路徑規劃的環境建模上。通過柵格法把環境空間分割成若干個柵格單元,每個柵格的尺寸都是一樣的,并對其進行定義來表達障礙物的信息。柵格單元的尺寸對路徑規劃的精度和效率有很大影響,當柵格分割的較小時,柵格個數較多,搜索空間過大,導致路徑規劃耗時長,效率低下。當柵格分割的較大時,環境空間劃分的不夠細致,導致路徑規劃的準確性下降,但柵格數量少可以縮短路徑規劃時間,提高效率。因此,需要確定大小合適的柵格地圖,通常根據實際環境中障礙物的稀疏程度和路徑規劃的要求來確定。圖1是一個20*20的柵格地圖,白色柵格為空閑區域,能夠讓噴漿機器人自由通行,黑色柵格為障礙區域,機器人無法通行。

圖1 20×20柵格地圖

1.2 經典A*算法

A*算法具有搜索效率高、規劃速度快等特點,已經廣泛應用于路徑規劃。A*算法首先在起點開始尋找附近節點,然后根據評價函數選擇移動代價最少的點作為下一個搜索節點,直至擴大到目標點。A*算法的評價函數f(n)的表達式為:

f(n)=g(n)+h(n)

(1)

式(1)中,g(n)為起點到當前節點的移動代價,h(n)為當前節點到目標節點的估計代價,也稱啟發函數。

若h(n)的評估值遠小于g(n),則f(n)將近似等于g(n),此時A*算法的遍歷節點會增多,搜索效率將大大降低;若h(n)遠大于g(n),此時A*算法路徑規劃的速度變快,但會出現穿過障礙物的情況。因此啟發函數h(n)決定了A*算法的搜索效率。歐幾里德距離、曼哈頓距離和對角線距離是常用h(n)的預測方法。相比于曼哈頓和對角線距離,歐幾里德距離具有更高的計算精度,而且更容易搜索最優路徑,因此本文選取歐幾里德距離對h(n)進行移動代價預估。假設起點坐標為(s1,s2),目標點坐標為(g1,g2),則歐幾里德的啟發函數為:

(2)

2 改進A*算法

2.1 評價函數的優化

在A*算法的介紹中提出,A*算法的核心是f(n),其中g(n)的值是固定的,因此對啟發函數的優化通常是圍繞h(n)實現的。針對實際的工作需求,h(n)越貼近實際的路徑代價,其節點的選擇準確度就越高,但h(n)的復雜程度越高,搜索節點就會越多,導致路徑規劃的運算速度降低,所以選擇合適的h(n)是十分重要的。評價函數是移動代價與估計代價的和,通過更改移動代價與估計代價的權重,可以控制A*算法更偏向移動代價或是估計代價,如果移動代價的權重過大,則路徑規劃的速度較慢但可以搜尋到最佳路徑;如果估計代價的權重過大,則路徑規劃的速度快但無法保證搜尋到最佳路徑。因此本文更改評價函數的公式為:

f(n)=g(n)+(1+r/R)*h(n)

(3)

式(3)中,r為當前點到目標點的長度,R為起點到目標點的長度。即在估計代價h(n)前更改系數,從而改變估計代價的權重,以提高算法搜索路徑的速度。

2.2 優化子節點的選擇方式

A*算法在尋找從起始點到終點的路徑過程中,有4鄰接和8鄰接兩種常用的選擇子節點的方式,如圖2(a)、圖2(b)所示,但這兩種方式規劃的路徑拐點較多且路徑長。為此本文選擇16鄰接的方式,如圖2(c)所示,該方式規劃的路徑拐點少、路徑短,適合噴漿機器人的路徑規劃。

自費疫苗并不是某些網友所說的試驗性的，都是正式銷售的，而且基本是進口疫苗（有些是國產的），這些進口疫苗是美國FDA認證過的，在歐美日等發達國家是免費的計劃內疫苗，所謂的自費只是需要家長來付這筆費用。

A*算法在生成其子節點后,對子節點進行判斷,如果子節點存在障礙物,則不生成該位置的子節點,而是選取評價函數值最小的子節點作為路徑節點,因此,所規劃出的路徑會穿過圖3(a)所示障礙物的頂點,或與圖3(b)所示的障礙物距離太近而發生碰撞,從而導致路徑規劃失敗,甚至造成機器人損壞。圖3中,三角形是機器人路徑規劃的起點,圓形是目標點,黑色線段是規劃的路徑。

(a)

為了改善經典A*算法安全性低的問題,改進子節點的選擇方式,在父節點生成子節點的時候,對子節點與障礙物之間的位置關系進行判斷,改變子節點的選擇方式,防止機器人在移動過程中出現斜穿障礙物頂點的問題,有效地避免了機器人與障礙物之間的碰撞,提高了噴漿機器人移動過程中的安全性。圖4所示為16個子節點的分布圖,本文設計的子節點選擇方式為:

圖4 子節點分布圖

(1)若子節點1或5為障礙物,那么子節點2、4、6、8、9、10、13、14均不作為預選節點;

(2)若子節點3或7為障礙物,那么子節點2、4、6、8、11、12、15、16均不作為預選節點;

(3)若子節點無障礙物則不作處理。

通過優化子節點的選擇方式,改進的A*算法規劃的路徑不會斜穿障礙物或離障礙物距離過近,如圖5(a)、圖5(b)所示,有效的避免了碰撞,機器人路徑規劃的安全性得到提高。

(a)

2.3 路徑平滑度優化

經典A*算法在規劃路徑時,由于路徑節點位于柵格中心,導致規劃的路徑具有多個拐點、平滑性差等問題。在噴漿機器人實際的作業環境中,上述問題對其工作效率會產生較大影響。為了解決這些問題,本文對路徑進行了平滑度優化,以減小路徑轉折的角度。本文選擇貝塞爾曲線法對路徑進行平滑處理。貝塞爾曲線是一種應用于二維圖像的曲線,它的取點方式是在兩條線段上尋找一個可以將兩條線段等分的點,再在其連線上尋找到一個可以等比例平分這條連線的點,這個點就是貝塞爾曲線上的一點,貝塞爾曲線上的其他點則通過改變比例得到,這些點組成的曲線就是貝塞爾曲線。二階貝塞爾曲線公式如式(4)所示。

B(t)=(1-t)2P0+2t(1-t)P1+

t2P2,t∈(0,1)

(4)

式(4)中,P0是起點坐標,P1是目標點坐標,P2是位置點坐標。

貝塞爾曲線擬合的方法是:在一個平面上選擇3個不同線的點A、B、C,將三個點依次連成一條直線,在線段AB和BC上分別選擇點D和E,使AD/AB=BE/BC,連接DE,并在DE上確定一點F,使得DF/DE=AD/AB=BE/BC,如圖6所示,讓選取的點D在第一條線段上從點A移動到點B,然后確定所有點F,并將點F移動的軌跡連接起來,所得到的曲線就是貝塞爾曲線。

圖6 原理圖

3 實驗與分析

3.1 仿真實驗

在噴漿機器人工作過程中,煤礦環境中存在著大小不一的施工材料和障礙物。為了對本文提出的改進A*算法的有效性進行驗證,使用經典A*算法與本文所提的改進A*算法在不同大小的柵格地圖上展開仿真試驗。實驗環境為CPU Inter Core i7 12700F,內存16GB,實驗工具MATLAB 2019a。本文首先在尺寸20×20的柵格地圖上展開實驗,每個柵格是邊長為1個單位的正方形,柵格地圖障礙物按照20%的比例隨機生成,其中不同形狀的黑色柵格表示煤礦環境中不同大小的施工材料和障礙物。傳統A*算法與本文改進A*算法的路徑規劃的實驗結果如圖7所示,圖中三角形是路徑規劃的起點,圓形是路徑規劃的的目標點。圖7(a)中實線是經典A*算法規劃的路徑,圖7(b)中黑色實線是改進A*算法平滑后的路徑。經過比較可以看出,在相同環境下,與經典A*算法規劃的路徑相比,改進A*算法規劃的路徑轉折角度小,安全性高,路徑更加平滑。

(a)經典A*算法

仿真實驗在3種不同尺寸但障礙率都為20%的柵格地圖上分別成功運行10次(實驗中存在障礙物堵住機器人前進路徑的情況),記錄傳統A*算法和改進A*算法運行時路徑搜索時間和路徑長度。不同尺寸地圖的起點和目標點不同。

地圖尺寸為20×20時,起點坐標為(6,4),目標點坐標為(18,19)。

地圖尺寸為50×50時,起點坐標為(3,40),目標點坐標為(46,10)。

地圖尺寸為100×100時,起點坐標為(20,80),目標點坐標為(90,20)。

仿真結果見表1。

表1 路徑規劃參數對比表

表1給出了在不同大小的柵格地圖上,經典A*算法相對于改進A*算法路徑規劃的時間和規劃路徑的長度。從表1中能夠發現,與經典A*算法相比,改進A*算法的尋路時間節省了50%左右,路徑長度節省了20%左右,這說明改進A*算法路徑規劃的效率更高、路徑更短。

3.2 結果分析

經過多次仿真實驗得出的結果,分析得出路徑優化的三個主要因素。

(1)評價函數的優化。通過更改估計代價的權重,以減少路徑規劃過程中搜索節點的數量,減少了搜索時間,增加路徑規劃的效率。

(2)優化子節點的選擇方式。通過改變子節點的鄰接方式,降低了路徑的拐點,使得路徑更短,同時優化子節點的選擇方式,通過增加噴漿機器人與障礙物之間的距離,從而避免危險情況發生。

(3)路徑平滑。選擇貝塞爾曲線對路徑進行平滑處理,減少了路徑的轉折角度,保證了噴漿機器人運動時的平穩性。

通過以上實驗和分析可知,噴漿機器人采用改進A*算法進行路徑規劃,可以提高工作效率,保證安全性和平穩性,具有一定的應用價值。

結語

為了解決經典A*算法在路徑規劃時存在的缺陷,本文對A*算法的評價函數、子節點的選擇方式以及路徑平滑作出了一定的優化。改進A*算法通過改變估計代價的權重來減少搜索路徑的時間,提高路徑規劃的效率;然后為了使噴漿機器人不會斜穿障礙物頂點,對子節點的選擇方式進行改進,增加了機器人與障礙物之間的安全距離,改善了機器人運動過程中的安全性;最后對路徑進行平滑優化,減少路徑的拐點,規劃出更平穩的路徑。經過實驗分析,本文改進的A*算法搜索時間少、路徑短、安全性高、路徑更加平滑,證明了所提改進算法的優越性,可用于煤礦環境中的噴漿機器人路徑規劃。