基于改進A*算法的機器人路徑規劃與避障技術

黃宸希，韓韜，吳雪瓊，馮榮強

（南瑞集團公司（國網電力科學研究院），江蘇南京 211100）

隨著信息技術的發展，巡檢機器人作業被廣泛應用于各個領域[1]，且目前已實現了根據巡檢點位置進行自動巡檢的功能。但對于復雜應用場景，其仍存在自主避障能力弱、運算消耗的內存資源較大等缺陷，從而制約了該技術的進一步發展。因此，針對巡檢機器人精準巡檢、智能避障及性能優化等關鍵技術的研究顯得至關重要。當前，已有大量文獻對機器人移動避障進行了相關研究。文獻[2-3]通過尋找關鍵點來縮短機器人的行進路徑，進而提升了其路徑搜索效率。但該方法并未考慮路徑的平滑處理及環境模型的建立，使得機器人在行進過程中并不流暢。文獻[4]雖提出了多種不同類型的障礙物信息以指導機器人如何避障，但卻未考慮與障礙物之間的最短距離，因此易與其發生碰撞。綜上所述，文中提出了一種基于柵格精度的關鍵轉折點選取方法。該方法既可提高節點的搜索效率，降低路徑規劃中的節點搜索個數，從而解決內存消耗問題；此外，還可通過轉折點的平滑處理使得機器人行進路徑更為平滑。

1 機器人移動路徑規劃算法

為了提升機器人的路線規劃效率，首先需要基于環境采集傳感器收集機器人工作場景的工況信息，再精確抽象出其工作環境的地圖數學模型[5]。文中基于二維柵格法進行機器人的移動環境建模[6]，具體思路如圖1 所示。

圖1 機器人移動環境示意圖

圖1 中，每個柵格均具備二維平面的坐標屬性。對移動機器人而言，算法關注的重點是該柵格是否可以同行。文中采用0-1 編碼的方式，對機器人移動環境中的所有柵格Cell 進行編碼，具體方式如下：

其中，0 代表可通行，在圖1 中用白色表示；1 代表不可通行，圖1 中用黑色表示。通過柵格編碼，便可將環境模型存儲在機器人系統中。

由于柵格精度也會對機器人行進路徑造成一定的影響：柵格精度越高，其存儲的環境量信息就越多，這便更容易干擾機器人的行進；反之，柵格精度越低，存儲的環境量信息便越少，機器人也越容易碰到障礙物。因此，可通過引入柵格精度進行更為有效的路徑規劃[7-8]。具體的流程如下：

1）獲取環境中的某一障礙物信息。

2）判斷障礙物的外形，若該障礙物為凸形，便可將其劃分為多個互不相交的三角形；若障礙物為其他形狀，則計算其最大與最小頂點后，將該頂點作為矩形對角線，并通過計算矩形的面積，進而獲得障礙物的面積。

3）根據面積公式確定障礙物的面積。

4）觀察剩余的柵格中是否仍存在其他障礙物，若存在，則返回至步驟1）。

5）計算柵格的精度，其計算公式為：

式中，d為對應柵格的邊長；Stotal為柵格的總面積且Stotal=∑i∈PS，S是障礙物的面積，P是障礙物集合，i則為其中某一障礙物。

2 改進的A*算法設計

2.1 A*算法優化

A*算法運行過程中的主要內存開銷是OpenList、CloseList 這兩個列表。在該算法的運行過程中，需隨時計算所有的節點代價，并搜索列表中代價最小的節點進行替換。

圖2 為機器人的行進路徑圖，其中灰色區域為A*算法在搜索過程中參與計算的節點。從圖中可以看出，這些節點與最終的路徑并無關聯。但卻消耗了計算機較多的計算與存儲資源，且影響了算法的效率。此外，A*算法生成的路徑還包含了諸如P1到P的不必要轉折點，故影響了機器人的巡檢效率。綜上所述，需要對A*算法加以改進[9-10]。

圖2 機器人行進路徑圖

該文提出了一種可以減少計算機內存消耗的方法，圖中灰色代表需要計算的區域，*則代表規劃的路線。可以看出，P1點到P點的直線距離最短，其僅需要計算兩點間的距離。由于規劃路徑中存在過多的轉折點，也會對機器人巡線造成影響，故該文通過尋找關鍵點來進行優化[11]。

為解決A*算法內存消耗過大，行進路徑不平滑及行進過程中可能與障礙物發生碰撞的問題，此次優化將從以下幾個角度進行：

1）在選擇關鍵點時，盡量選擇不靠近障礙物的點，以避免機器人在前進過程中發生碰撞。

2）經過轉折點時，盡量將折線轉變為曲線，使得機器人的行進路徑更為平緩。

3）通過關鍵點的選取，降低機器人內存的消耗。

2.2 關鍵轉折點選取

該文提出的關鍵點選取方法[12-14]如圖3 所示，其中P1、P3分別是路徑的起點和終點。在傳統的A*算法中，需分別計算(1，2)、(2，1)及(2，2)這三個點的代價值，然后將代價最小的點(2，2)作為下一個父節點，并計算該節點周邊所有點的代價值，再選擇代價最小的路徑。從圖中可以看出，P1到P3存在一條最短路徑，故僅需計算(2，2)、(3，3)、(4，4)與(5，5)這些點的代價即可。

圖3 關鍵點選取原理示意圖

關鍵點的選取可分為以下兩種情況：

1）P1、P2和P3在一條直線上。

2）P1、P2與P3不在一條直線上。

針對上述兩種不同情況，選取策略分別如下：

首先，若P1、P2及P3在一條直線上，則僅需保留起始點P1和終點P3即可；其次，P1、P2與P3是三個不在一條直線上的點，則又可分為以下兩個步驟：①若P1、P2的連線與P1、P3的連接線均不與障礙物發生碰撞，刪除P2；若P1、P3的連線與障礙物發生碰撞，則保留P1、P2及P3三個節點，再以P2為節點向下選取其他節點構成三角形。②以P2為起點繼續選取其他節點，若選取的兩個節點P3、P4與P5在同一條直線上，則刪除P4并保留P3、P5節點，且重復該步驟直至到達終點。關鍵點選取過程，如圖4 所示。

圖4 關鍵點選取過程

在機器人行進過程中通常會遇到許多轉折點，此時可將路徑中的轉折點記錄在一個集合P中。轉折點的計算如圖5 所示，圖中黑色方塊為障礙物。從起始點開始依次連接各個轉折點，并從集合P中再次選取關鍵轉折點。通過定義評價函數G(x)，且將其作為最優轉折點的選擇依據，同時以設置權重的方式對評價函數進行重新定義，即：

圖5 轉折點計算

其中，α為調節參數，d1為障礙物中心到起始點、轉折點連線的垂線長度；d2則為轉折點到障礙物所在平面的垂線長度。

對每個節點基于式（2）計算其評價函數的值，然后對所有節點的評價值進行排序，再選取評價值最小的點作為轉折的關鍵點。當引入關鍵點選取策略后，可大幅降低機器人行進路徑中節點搜索的個數。

2.3 路徑轉折點選取及平滑處理

將選取的路徑轉折點進行平滑處理[15-16]，如圖6所示。設MN點的坐標為(X1,Y1)、(X2,Y2)，OP點的坐標為(X3,Y3)、(X4,Y4)，A點的坐標則為(a,b)。其中BM與BN分別垂直于OA和AP，且兩條垂直線相交于B點。原A*算法需經過的長度為L=L1+L2，具體的計算方法如下：

圖6 路徑轉折點平滑處理

經算法改進后，原來的直線變為平滑曲線，L的距離也發生了變化。假設B點的坐標為(X，Y)，通過聯立方程組可求解出圓的半徑R。如圖可知α角為π-θ，則利用式（6）可計算出半徑為：

根據圖6 聯立上述的幾何關系，可求得弧長MN為：

通過比較LMN與NA與MA距離的和，可發現路徑長度顯著減小。

3 算法仿真

為驗證所提算法的準確性及可靠性，文中通過仿真實驗將優化后的A*算法與傳統算法進行比較。仿真實驗在Matlab 上進行，具體的軟硬件環境參數如表1 所示。

表1 軟硬件環境參數

首先，利用二維柵格來對算法在二維空間的循跡性進行驗證。在該二維平面中，通過坐標系構建現場環境情況，則機器人在二維柵格上進行的路徑搜索過程，如圖7 所示。

圖7 在二維空間內的路徑搜索示意圖

從圖7可以看出，算法寫入機器人后，機器人便可完成二維平面下的路徑循跡，同時實現自主避障功能。

為了進一步評估算法的性能，從機器人行進路徑長度、轉折點個數、與障礙物的最近距離以及時間四個方面對比該文算法與傳統A*算法的性能。算法仿真結果，如圖8-10 所示。

圖8 傳統A*算法路徑

其中，圖8 給出了傳統算法下機器人的路徑軌跡。根據式（2），改進A*算法的評價函數中，不同的α取值會影響算法的路徑規劃。圖9-10 則給出了不同α值下機器人的行進路徑。

圖9 α=0.75 時，改進A*算法的路徑

圖10 α=0.5 時，改進A*算法的路徑

由上圖可知，傳統算法下機器人的行進路線轉折點過多，路徑也并不平滑，且極易與障礙物發生接觸。而改進A*算法在對關鍵點進行平滑處理后，機器人的行進變得更為平緩。此外通過對比不同α取值下的路徑可知，α越大，機器人的行進便越平滑。

在上述場景下，具體的指標計算結果如表2所示。

表2 傳統算法與改進算法結果比較

從表2可以看出，隨著α的增大，改進A*算法的性能也在不斷改善。同時機器人的路徑長度由61.326 2 m縮短至56.527 6 m，相較于傳統A*算法降低了1.80%；而算法的轉折點個數由9 個減少至6 個，相較傳統算法降低了40%；機器人的運動時間則由0.133 s 降低至0.091 s，相較于傳統的A*算法下降了10.78%。此外，α的取值還會影響機器人與障礙物的最近距離。且當α較小時，機器人與障礙物的距離較遠，不易發生碰撞。因此，算法可根據機器人對于安全性和運行速度的要求，合理選擇α值。

通過上述實驗可知，傳統A*算法規劃的機器人行進路徑存在過多轉折點及路徑不平滑等問題。而與其相比，所提算法的路徑更短，轉折點較少且路徑也更為平滑。同時在該算法中，根據參數α的不同，可以調整對行進路徑、障礙物距離與運行時間的側重，相較于傳統A*算法有一定的提升。

4 結束語

該文提出了基于柵格精度的關鍵轉折點、路徑平滑處理方法，來對傳統A*算法進行了改進。利用關鍵點方法可降低計算機內存的使用情況，而路徑平滑處理則能解決機器人行進過程中轉折點過多的問題。同時，通過加入障礙物計算方法，還確保了機器人行進過程中不會觸碰到障礙物。基于多因素的移動機器人避障算法能夠縮短機器人的行進路徑與運行時間，并提升行進路線的高效與合理性。實驗結果表明，改進后的A*算法比傳統的A*算法更具優勢。