基于改進A*算法的室內(nèi)服務(wù)機器人路徑規(guī)劃

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

0 引言

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

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

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

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

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

1 算法描述

1.1 A*算法

A*算法是目前移動機器人領(lǐng)域運用范圍最廣的路徑規(guī)劃算法，A*算法是在Dijkstra算法的基礎(chǔ)上提出的，引入了啟發(fā)式函數(shù)和估計代價，提升了算法的效率。

A*算法的估計函數(shù)為：

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

(1)

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

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

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

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

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

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

1.2 A*算法的缺點

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

2 A*算法的改進

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

2.1 視線算法與跳點搜索法的結(jié)合

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

2.2 路徑平滑處理

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

3 仿真實驗與分析

為了驗證改進A*算法在室內(nèi)服務(wù)機器人路徑規(guī)劃的效果，論文使用MATLAB2016a進行仿真實驗。傳統(tǒng)A*算法仿真結(jié)果如圖1所示，改進A*算法如圖2所示。

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

圖1 傳統(tǒng)A*算法的路徑規(guī)劃結(jié)果

圖2 改進A*算法的路徑規(guī)劃結(jié)果

4 結(jié)語

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