自主移動機器人避障技術研究現狀*

晉曉飛， 王 浩， 宗衛佳， 王鵬程， 王 策

(1.南京航空航天大學 仿生結構與材料防護研究所，江蘇 南京 210016；2.南京航空航天大學 自動化學院，江蘇 南京 210016; 3.南京航空航天大學 航天學院，江蘇 南京 210016)

0 引 言

自主移動機器人的智能避障指機器人通過傳感器檢測到障礙物并采集其狀態信息，按照一定的算法進行的路徑規劃，從而避開障礙物，最終到達目的地。如何讓機器人判斷障礙物，并躲避，是機器人避障中的2個關鍵問題[1，2]。

自主移動機器人的避障問題分為2類：障礙物環境信息完全已知和障礙物環境信息未完全已知。前者機器人避障屬于全局路徑規劃；后者或完全未知情況下的機器人避障屬于局部路徑規劃[3～5]。大多情況下，機器人所處外部環境動態未知，傳統避障算法在這些情況下將出現很多缺陷。

近些年研究提出的智能避障算法在很大程度上彌補了傳統算法的不足，本文按照傳統避障算法與智能避障算法對自主移動機器人避障技術進行分類，分析優缺點，并介紹了一些改進的算法。

1 自主移動機器人避障技術

1.1 傳統避障算法

傳統避障方法主要實現機器人無碰撞全局路徑規劃，經典的算法有以下幾種：

1.1.1 人工勢場法

人工勢場法于20世紀80年代由 Khatib O等人[6]提出，將移動機器人的運動當作一個質點在一種抽象的人造勢力場中的運動：目標點對質點產生引力，而障礙物對質點產生斥力，依據合力確定移動機器人的運動方向和路徑。人工勢場法具有結構簡單、容易實現的優點，且規劃后的路徑比較平滑。不過這是一種局部尋優的方法，對于相對復雜的動態環境，不合理的勢場方程容易使機器人陷入局部最小點。

Huang Y等人[7]提出了帶記憶功能的沿墻(Wall-following)方法幫助機器人跳出局部最小點。徐飛[8]提出了一種基于相對速度的改進人工勢場法，針對傳統路徑規劃中局部最小點問題，提出了設置中間目標點的方法，給機器人一個外力以避免其在局部最小點處停止或者徘徊，確保機器人能夠逃出最小點陷阱并順利到達目標位置。

1.1.2 柵格法

Borenstein J和Koren Y[9]提出了基于柵格法的機器人避障，主要原理是將機器人的工作環境分割成為一系列具有二值信息的柵格單元，且將累積值放入每個矩形柵格中，累積值越高表明存在障礙物的可能性越大。柵格大小決定了算法的性能。若選擇柵格較小，環境信息存儲量即變大，機器人決策速度變慢，抗干擾能力變差；若選擇柵格較大，環境信息存儲量變小，決策速度變快的同時卻降低了分辨率，導致了機器人在復雜障礙物環境下的通過能力減弱，增加碰撞風險。

Zhao K K等人[10]提出了基于射頻識別( radio frequency identification，RFID) 系統的柵格法,借助網格劃分、信息處理和無線通信，計算機計算出最短路徑，并以標簽的形式存儲，通過標簽和機器人之間的通信，機器人通過與后臺支持數據庫交互完成路徑規劃，路徑規劃效率大幅提高。華劍鋒等人[11]提出了變分辨率柵格模型的方法，模型基于四叉樹思想構建，不僅考慮了地形表達數據冗余度和精度，而且有效消除了地物“邊緣效應”的影響，在此基礎上，設計了一種啟發式有向路徑規劃算法，既可以在連續空間中規劃出最優路徑，又可以提高路徑規劃的計算效率。

1.1.3 A*算法

尼爾森等人在1980年提出了A*算法[12]，是一種應用很廣的啟發式搜索算法。利用空間啟發式信息，通過對比選擇恰當的評估函數，通過動態搜索策略，求出移動機器人的最優規劃路徑。A*算法在全部已知且比較簡單的環境中，搜索速度非常快，并能找到最優路徑。但A*算法搜索路徑的優化性較差，對于比較復雜的未知環境，搜索效率不高。

劉斌等人[13]提出了一種基于A*算法的動態多路徑規劃方法，結合A*算法與矩形限制搜索區域算法[14]，給出了一種求解單一優化路徑的動態路徑規劃算法。同時提出了一種重復路徑懲罰因子，可以利用其一次搜索出多條優化路徑。方昕等人[15]將A*算法與柵格法進行有效結合，改進A*算法采用多個柵格包絡障礙物方式，利用頂點外延節點生成路徑來構造連通圖。在此基礎上，引入了平滑度概念，將算法應用于二維空間進行機器人路徑規劃，提高了算法搜索效率。

1.1.4 可視圖法

Janet J A[16]將目標、障礙物以及機器人的各個頂點看作節點，再將所有節點進行組合相連，連線稱為弧，并且設定各節點之間連接而成的弧均不能穿越障礙物，將弧看作可視的。該方法直觀易懂，可得到最短的路徑；但當移動機器人的起點或終點發生變化時，需要重構可視圖，如果環境中障礙物較多，重構地圖的過程會很復雜，搜索路徑的時間就會加長。

楊淮清等人[17]提出了一種基于可視圖法的移動機器人路徑規劃算法，將復雜輪廓的障礙物近似看成矩形或者多個矩形的組合體，以此建立障礙物邊界地圖，實現了路徑規劃。陳超等人[18]利用射頻識別系統，通過超高頻射頻識別系統與低頻射頻識別系統的聯合運用實現準確定位，將可視圖法與A*算法相結合，提出了一種路徑規劃算法，在提高搜索效率的同時保證了規劃路徑的可行性。

1.1.5 自由空間法

自由空間法通過將移動機器人路徑規劃轉變為在自由空間內的路徑尋找解決路徑規劃問題，采用自定義的幾何形狀構建地圖環境，同時將地圖環境表示為連通圖，最終通過對圖的搜索實現了路徑規劃[19，20]。自由空間法原理簡單，在起點和終點發生變化時，僅需重新定位，不需重繪整幅地圖，易于實現；但當環境中存在復雜障礙物時，連通圖會變得很復雜，算法實現困難，并且不能保證生成最優路徑。

盧曉軍等人[21]提出了一種基于自由空間的路徑規劃方法，結合啟發式A*算法進行路徑搜索，產生從初始位置到目標位置的最優路徑。

1.1.6 拓撲法

拓撲法將移動機器人的運動空間劃分為具備拓撲特征的一系列節點，并構建拓撲關系網，在所構建關系網上連接出起點和終點間的幾何路線，最終將幾何路線轉化為移動機器人的幾何路徑[22]。拓撲法縮小了搜索范圍，且不需要獲得移動機器人在環境中的精確定位，對位置誤差的處理具有很好的魯棒性。但建立整個拓撲網絡是個復雜的過程，且當環境中障礙物發生變化時難以快速準確地修改拓撲網絡。

吳海濤等人[23]提出了一種基于鄰接矩陣網絡拓撲樹構建的路徑尋優方法，引入路網節點間鄰接關系，將路網按照其節點鄰接關系歸類劃分為以路網節點間鄰接值為表征的路網拓撲進化樹，同時對路徑尋優問題中目標節點進行動態回溯分類，在限定路網搜索區域的同時采用分支定界搜索策略進行搜索優化，降低了搜索算法的時間復雜度。

此外，目前還有快速擴展隨機樹(rapidly-exploring random tree，RRT)算法、遺傳算法等。RRT算法采用隨機查詢采樣搜索，經過一個優化策略對外部空間進行信息采樣，執行最佳路徑策略；RRT算法對全局環境有較大的依賴性，且實時性較差[24]。遺傳算法是由美國的Holland J H[25]提出的一種隨機搜索算法。遺傳算法將希望求解的問題進行編碼，初始階段隨機生成候選種群，以適應度函數的形式評估種群的性能，并且在此基礎上繁殖、交叉和變異[26]。遺傳算法屬于多點搜索算法，有更多機會尋找到全局最優解。但遺傳算法只適用于全局路徑規劃，在復雜環境中若路徑個體編碼不合適，會導致進化速度緩慢；若遺傳算子的選擇不合理，不會有明顯的進化效果。

1.2 智能避障算法

單一的傳統避障算法在未知或者部分已知的環境中存在著較為明顯的缺陷，開發適合動態未知環境的避障算法是自主移動機器人避障技術中亟需解決的問題。智能避障算法能夠克服傳統算法的缺陷，使機器人有效躲避障礙物。目前，較為新穎的幾種智能算法有：

1.2.1 基于神經網絡的機器人避障方法

Mihai D和Gheorghe M[27]研究了一種基于神經網絡的新避障方法解決機器人在包含靜態和動態障礙物的環境中自主移動的問題，規劃出了自主移動機器人在不確定的包含靜止和移動實體的工作空間內的無碰撞軌跡。該方案使用“Q學習”和“神經網絡規劃器”解決路徑規劃問題。如圖1所示，Pos網神經網絡是一個多層感知器，接收作為初始輸入的P向量，P向量包含機器人當前位置、時間樣本t，Q值矩陣，輸出三值矢量(X,Y,t)。如果到達目標前發生碰撞或者步數已達到最大值，則Pos網神經網絡重新開始權值初始化和迭代。該方法可以在計算軌跡之前設置機器 人的速度，在時間受限的應用中具有很大的優勢。

圖1 Pos網路徑規劃結構[27]

齊方遠[28]研究了基于神經網絡避障和 GPS定位的移動機器人自主運動方法，構建了基于BP神經網絡和距離信息的移動機器人避障模型，并在此基礎上提出了室外環境下移動機器人的自主運動方法。該避障模型效果較好，自主運動模型亦具備一定的自主運動能力。

1.2.2 基于可視性二叉樹算法的機器人避障方法

Abdulmuttalib T R[29]提出了一種動態環境中機器人避障的新方法，可視性二叉樹算法。為規劃機器人的路徑，算法依賴于機器人和目標之間的所有完整路徑集合的構建，考慮機器人和圓形障礙物之間的內部和外部的可見切線。使用這些路徑創建可視性二叉樹，選擇出最短優化路徑。

1.2.3 基于滾動時域控制算法的機器人避障方法

Giuseppe F和Walter L[30]提出了滾動時域策略，用于解決動態環境中線性定常系統所描述的自主移動機器人的路徑規劃問題。滾動時域的方法即對于所有可能的障礙物場景，預先計算精確可控集內的橢圓近似序列，并在線分析，確定適當的控制動作使機器人完成避障。如圖2所示，虛線橢圓代表可控集序列，沿箭頭方向增加，經障礙物序列、場景切換序列、障礙物切換系列等滾動時域，實現避障路徑規劃。無論遇到任何障礙物，所產生的框架均能保證均勻的最終邊界并且滿足約束條件。

圖2 滾動時域算法避障原理[30]

1.2.4 基于神經控制器的機器人避障方法

Nacer H和Boubekeur M[31]針對全向自主移動機器人提出了一種基于神經控制器的自主導航和避障策略。機器人規劃一個路徑，從初始點開始移動到目標點。將二階多項式整體性規劃方法應用到機器人沿理想路徑情況下的運動，利用神經控制避免機器人與靜態或動態障礙物之間發生碰撞。如圖3所示，機器人從A點出發前往目標，期望路徑(desired path，DP)即最短路徑是兩點之間的直線，但在這條路徑附近有靜態和動態障礙物，所以要使機器人沿DP方向規劃路徑，同時又要避免障礙物垂直于DP。神經控制器的設計是基于“感應矢量”和“間隙矢量”的概念。“感應矢量”是一個二進制向量，提供了有關障礙物的檢測信息，“間隙矢量”提供了一個機器人可能通過的最近間隙的信息。

圖3 神經控制器路徑規劃[31]

1.2.5 基于混合算法的機器人避障方法

Pai N S等人[32]設計了一種基于模糊理論和可拓理論的全向自主移動機器人。模糊理論用于調整控制電機轉速的脈寬調制(pulse width modulation,PWM)信號，糾正機器人移動時出現的路徑偏差問題。可拓理論用于建立機器人避障模型，建立多種移動模型以處理不同類型的障礙。機器人安裝有超聲波距離傳感器估算障礙物的距離。如果遇到障礙，相關函數將進行評估，機器人將自主選擇最合適的模式來避開障礙。系統流程如圖4所示。

圖4 系統流程[32]

Chen W J等人[33]提出了一種用于自主移動機器人的路徑跟蹤方法，包括路徑規劃和控制器設計。在路徑規劃中，使用B樣條代替A*算法創建平滑和避障路徑，減少了碰撞的可能性，B樣條曲線如圖5所示。在控制器設計中，將遺傳算法和模糊邏輯組合在一起用于對在某一環境中運動的移動機器人的速度調控。

圖5 B樣條曲線(n=4,k=3)[33]

An P[34]提出了基于無線傳感器網絡的移動機器人的避障策略。該算法以模糊控制和神經網絡控制理論相結合，使用數學模型表達難以描述的規則，大幅提高了機器人躲避障礙物的實時性、準確性和穩定性。

1.3 傳統避障算法與智能避障算法性能對比

綜合上文所述算法可以看出，傳統避障算法局限性較大，不適合復雜未知的動態環境，而智能避障算法則在這方面表現出了巨大的優勢。部分傳統避障算法與智能避障算法性能對比如表1所示。

2 自主移動機器人避障技術展望

隨著智能機器人技術的成熟，自主移動機器人將在工業、農業、醫療、服務等行業中得到廣泛的應用，將來更會在城市安全、國防和空間探測領域等有害與危險場合得到很好的應用。自主移動機器人的避障技術是實現機器人智能性的一個重要方面，將會是機器人領域內的研究熱點。

未來移動機器人避障算法的研究中，將多種算法的優點結合，整合出具有多重優勢的混合算法，以實現機器人躲避障礙和路徑規劃的高效、實時與智能，這種避障模式將會是未來機器人避障技術的發展趨勢。另外，多傳感器信息融合技術可以使機器人建立更加準確的外部環境模型，未來，多傳感器信息融合技術必定有更多的應用。此外，多機器人系統聯合協作避障也將是未來研究的熱點[35～38]。

表1 部分傳統避障算法與智能避障算法性能對比

3 結束語

詳細介紹了傳統避障算法和智能算法的基本原理，優缺點，并進行了總結對比；對未來移動機器人避障技術進行了展望。

參考文獻:

[1] 金 娟.自主移動機器人軌跡跟蹤與避障控制研究[D].長沙：湖南大學,2015.

[2] 呂玉彬.基于多傳感器融合的機器人導航系統中的避障研究[D].長沙：湖南大學,2012.

[3] 劉東輝.自主移動式機器人路徑規劃研究[D].大慶：東北石油大學,2013.

[4] John F C,Ming C L.An opportunistic global path planner,robo-tics and automation 1990[C]∥Proceedings of 1990 IEEE International Conference,1990:1554-1561.

[5] Kohtaro S,Masaki F,Jens S G,et al。Obstacle avoidance and path planning for humanoid robot using stereo vision[C]∥Proceedings of the 2004 IEEE International Conference on Robotics and Automation,2004:592-597.

[6] Khatib O.Real-time obstacle avoidance for manipu-lators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.

[7] Huang Y,Hu H,Liu X.Obstacles avoidance of artificial potential field method with memory function in complex environment[C]∥The 8th World Congress on Intelligent Control and Automation(WCICA),2010:6414-6418.

[8] 徐 飛.基于改進人工勢場法的機器人避障及路徑規劃研究[J].計算機科學,2016,43(12):293-296.

[9] Borenstein J,Koren Y.Real-time obstacle avoidance for fast mobile robots[J].IEEE Transactions on Systems,Man and Cybernetics,1989,19(5):1179-1187.

[10] Zhao K K,Zhou Y M,Song Z B,et.al.A grid method for robot path recognition based on RFID technology[C]∥2016 the 12th World Congress on Intelligent Control and Automation(WCICA),2016.

[11] 華劍鋒,張 豐,杜震洪,等.基于變分辨率柵格模型的啟發式有向搜索最優路徑算法[J].浙江大學學報:理學版,2016,43(1):51-56.

[12] 王利敏.基于A*算法和B樣條函數的月球車路徑規劃研究[D].長春：吉林大學,2016.

[13] 劉 斌，陳賢富，程 政.一種基于A*算法的動態多路徑規劃算法[J].微型計算機與應用,2016,35(4):17-20.

[14] 許震洪.動態路徑誘導系統的最優路徑算法研究及相關軟件實現[D].南京:南京理工大學,2004.

[15] 方 昕，呂方興.一種改進A*算法的智能機器人路徑規劃[J].信息技術，2015(9):40-42.

[16] Janet J A,Luo R C,Kay M G.The essential visibility graph:An approach to global motion planning for autonomous mobile ro-bots[C]∥IEEE International Conference on Robotics and Automation,1995:958-1963.

[17] 楊淮清，肖興貴，姚 棟.一種基于可視圖法的機器人全局路徑規劃[J].沈陽工業大學學報，2009,31(2):225-230.

[18] 陳 超,唐 堅.靳祖光,等一種基于可視圖法導盲機器人路徑規劃的研究[J].機械科學與技術,2014,33(4):490-495.

[19] Brooks R A.Solving the find-path problem by good representation of free space[J].IEEE Trans on Syst Mans on Cyb,1983,13(2):190-197.

[20] Ghodgaonkar D K,Varadan V V,Varadan V K.A free space method for measurement of dielectric constants and loss tangents at microwave frequencies[J].IEEE Tran Instrum Meas,1989,38(3):789-793.

[21] 盧曉軍，李 焱，賀漢根.一種基于自由空間法的虛擬人行走規劃方法[J].計算機工程與科學，2005,27(8):60-69.

[22] Thrun S.Learning metric-topological maps for indoor mobile robot navigation[J].Artif Intel,1998,99(1):21-71.

[23] 吳海濤,張貴軍,洪 榛,等.進化樹拓撲路網構建及多停靠點路徑規劃方法研究[J].計算機學報，2012,35(5):964-971.

[24] 胡遠航.未知環境下自主移動機器人避障研究[D].哈爾濱：哈爾濱工程大學,2013.

[25] Holland J H.Adaptation in natural and artificial systems:An introductory analysis with applications to biology,control,and artificial intelligence[M].2nd ed.Cambridge:MIT Press,1992.

[26] 馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29(4):1201-1206.

[27] Mihai D,Gheorghe M.Neural networks based reinforcement learning for mobile robots obstacle avoidance[J].Expert Systems With Applications,2016 (62):104-115.

[28] 齊方遠.基于神經網絡避障和GPS 定位的移動機器人[D].北京：北方工業大學,2015.

[29] Abdulmuttalib T R,Abduladhem A A,Mattia F.Path planning with obstacle avoidance based on visibility binary tree algori-thm[J].Robotics and Autonomous Systems,2013,61:1440-1449.

[30] Giuseppe F，Walter L.The obstacle avoidance motion planning problem for autonomous vehicles:A low-demanding receding horizon control scheme[J].Systems & Control Letters,2015,77:1-10.

[31] Nacer H，Boubekeur M.Toward safety navigation in cluttered dynamic environment:A robot neural-based hybrid autonomous navigation and obstacle avoidance with moving target tra-cking[C]∥The 3rd International Conference on Control,Engineering and Information Technology(CEIT),2015.

[32] Pai N S,Hsieh H H,Lai Y C.Implementation of obstacle avoidance control for an autonomous omni-directional mobile robot based on extension theory[J].Sensors,2012,12:13947-13964.

[33] Chen W J,Jhong B G,Chen M Y.Design of path planning and obstacle avoidance for a wheeled mobile robot[J].International Journal of Fuzzy Systems,2016,18(6):1080-1091.

[34] An Peng.Obstacle avoidance strategy of mobile robot based on wireless sensor network[J].iJOE,2016,12(11):10-15.

[35] 常 建，吳成東，李 斌.移動機器人避障方法綜述[J].儀器儀表學報，2010,31(8):439-442.

[36] Antonio S,Renato Z.Planning and obstacle avoidance in mobile robotics[J].Robotics and Autonomous Systems,2012,60:628-638.

[37] 張玉婷，鄒彤雯，王艷麗,等.自主移動機器人避障算法研究及展望[J].黑龍江科學,2013,4(7):59-61.

[38] 楊 興.室內自主導航移動機器人路徑規劃研究[D].太原：中北大學,2016.