基于改進A*算法的室內服務機器人路徑規劃

(蘇州科技大學，江蘇 蘇州 215009)

0 引言

近年來，將服務型智能機器人應用到智能家居系統中，越來越成為一個熱點研究問題[1]。機器人也給人類的生產生活方式帶來了巨大的變化，服務機器人也逐漸進入人類社會的各行各業。關于移動機器人的路徑規劃技術一直以來都是相關領域研究的熱點。

簡而言之，路徑規劃就是給機器人設定一個起點和一個終點，然后機器人根據它自身的算法，為機器人設計一條避開障礙物到達的終點的路線。根據環境信息的完全已知，部分未知或完全未知，把移動機器人的路徑規劃分為兩部分：全局路徑規劃[2]和局部路徑規劃。

常見的局部路徑規劃算法有遺傳算法、人工勢場算法和模糊邏輯算法；常見的全局路徑規劃算法有A*算法、Dijkstra算法、粒子群算法等。

A*算法作為傳統的啟發式算法，由尼爾森提出，廣泛地應用于機器人導航領域。A*算法在啟發函數的引導下可以減少搜索空間，快速搜索路徑，避免了BFS、Dijkstra算法的盲目性[3]，缺點是在對較大場景進行路徑規劃時存在多冗余點和拐點、計算量大、內存消耗嚴重等問題。文獻[4]提出了在open列表中添加時間閾值N使算法更快速，并且結合Floyd算法使路徑更光滑，文獻[5]提出了一種對路徑節點進行指數衰減的方式加權，提升路徑的安全性，最后對路徑進行五次多項式平滑處理便于機器人控制。文獻[6]針對室內多U型障礙的問題，引入領域矩陣提升安全性，然后結合角度信息對啟發函數進行改進，文獻[7]對評價函數的權重比例，減少多余節點，然后引入障礙物拓展策略來保證規劃路徑的可行性，文獻[8]根據節點與障礙物的最小距離定義該節點的安全威脅代價，并引入估價函數提升安全性。

以上論文用不同方法改進了A*算法，優化了路徑規劃效果。本文提出了一種結合視線算法和跳點搜索法的改進A*算法，來解決A*算法規劃路徑中多冗余點問題，然后又利用幾何優化處理對規劃出的路徑進行平滑處理。仿真顯示，改進過后能明顯提升家居服務機器人路徑規劃的效率和效果。

1 算法描述

1.1 A*算法

A*算法是目前移動機器人領域運用范圍最廣的路徑規劃算法，A*算法是在Dijkstra算法的基礎上提出的，引入了啟發式函數和估計代價，提升了算法的效率。

A*算法的估計函數為：

f(x，y)=g(x，y)+h(x，y)

(1)

在式(1)中，f(x，y)是機器人所在節點的評價函數，第一部分是起始節點到當前節點的成本函數g(x，y)，第二部分是當前節點到目標節點的估計代價h(x，y)。

A*算法尋路過程中有2個列表，open列表和close列表，尋路的流程如下。

1)初始化open列表和close列表，確保close列表為空，然后將起點放入open列表。

2)判斷open列表是不是空列表，若是空列表，則尋路失敗，若存在目標節點，則尋路成功。

3)選取open列表中f值最小的節點作為父節點，然后放入close列表，將當前節點可到達的節點放入open列表中，計算當前節點每一個可到達節點的f值，將f值最低的節點作為新的拓展節點。

4)跳到操作2)，直到找到終點。

1.2 A*算法的缺點

A*算法由于搜索策略的問題，很多節點被重復地訪問和維護，導致規劃的路徑存在過多的冗余點和拐點，機器人尋找路徑的效率不高，最終路徑也存在過多折角，并不平滑。

2 A*算法的改進

為了解決尋路過程存在多余節點的問題，本文引入視線算法，與跳點搜索算法結合，對傳統A*算法進行改進；然后又引入幾何優化處理對規劃出的路徑進行平滑處理，使路徑更加適合室內服務機器人。

2.1 視線算法與跳點搜索法的結合

視線算法用于判斷2點之間是否有障礙物存在，視線算法早期應用于游戲中的目標檢測與跟蹤，應用場景與機器人路徑規劃符合。通過視線算法來判斷2個節點之間是否存在障礙物，若不存在障礙物則啟發距離值為0，若存在則不為0。然后將傳統A*算法規劃出來的路徑用較大的分割步長進行分割，得到一系列具有代表性的路徑節點，然后用視線算法對這些路徑節點依次進行可視檢測，若2個點之間無障礙物，那就可以結合跳點搜索法直接跳過這2個路徑節點之間所有的節點，直線達到下一節點，減少了路徑不必要的拐點和彎折；反之，若存在障礙物，則還是依照之前的路徑行走，然后再檢測下2個節點之間是否存在障礙物，直到到達終點。

2.2 路徑平滑處理

經過對節點的處理，規劃出來的路徑已經完成初步優化，但是路徑仍存在很多尖銳點，需要用平滑的曲線來代替尖銳點，本文采用幾何優化處理對路徑進行平滑處理。幾何優化處理主要利用函數計算原路徑的拐角度數，然后根據距離拐角點的距離，使用平滑的曲線代替原來尖銳的拐角。

3 仿真實驗與分析

為了驗證改進A*算法在室內服務機器人路徑規劃的效果，論文使用MATLAB2016a進行仿真實驗。傳統A*算法仿真結果如圖1所示，改進A*算法如圖2所示。

由圖1和圖2可以很直觀地看出，改進A*算法規劃的路徑長度要優于傳統A*算法規劃的路徑，多余的拐角也較少，提高了路徑規劃的效率也更加符合移動機器人的運動規律。另一方面，由于對路徑進行了平滑處理，更加適合室內服務機器人的運動。

圖1 傳統A*算法的路徑規劃結果

圖2 改進A*算法的路徑規劃結果

4 結語

采用傳統A*算法對移動機器人進行路徑規劃，雖然可以使機器人到達目的地，但是過多冗余點使規劃路徑時間較長且路徑也不平滑。為了解決這些A*算法的傳統問題，提出了一種改進A*算法，在冗余點過多以及平滑性兩個方面做出改進。經過MATLAB仿真實驗，證明了改進A*算法的優越性，能夠有效地減少尋路過程中對多余節點的訪問，縮短尋路時間以及路徑長度，并且平滑的路徑也更適合室內服務機器人的導航。