移動機器人的智能路徑規劃算法綜述*

王春穎, 劉 平, 秦洪政

(山東農業大學 機械與電子工程學院 山東省園藝機械與裝備重點實驗室,山東 泰安 271000)

0 引 言

移動機器人的路徑規劃是指在具有障礙物的環境中尋找一條從起始狀態到目標狀態的無碰撞路徑[1]。目前對于已知環境的路徑規劃已存在很多成熟算法,實現了無碰撞到達目標地點,但在未知環境下如何能夠根據移動機器人的傳感器實時探測到的局部環境信息,進行路徑規劃,仍處于試驗研究階段。近年來,我國農業裝備產業快速發展,路徑規劃作為自主導航的關鍵技術之一,是智能農業裝備的研究重點。

本文針對路徑規劃技術進行分析與歸納,重點分析了基于強化學習算法的路徑規劃技術,并提出類腦智能在路徑規劃上的應用展望和農業裝備路徑規劃的新思路。

1 移動機器人的路徑規劃

移動機器人種類繁多,根據路徑應用目的的不同,如時間最優、路徑最優、路徑全遍歷,將路徑分為點對點路徑和完全遍歷路徑2種[2]。

1.1 點對點路徑規劃

根據移動機器人所處外部環境信息的獲取情況將點對點路徑規劃[3]分為全局路徑規劃和局部路徑規劃。全局路徑規劃[3]是在已知的環境信息下,在事先建好的環境模型中,獲得從初始地到目標地的最優路徑,其優點是保證了規劃路徑的最優性和可達性。局部路徑規劃[3]是在未知環境中,基于傳感器獲取周圍環境信息,并使機器人自主獲得一條無碰撞的最優路徑,其優點是更具有對于未知環境的適應性和規劃的實時性。

1.1.1 全局路徑規劃

1)根據對環境構建的描述分為構型空間法、柵格法、拓撲法[4]等,在構型空間法中,較為成熟的有可視圖法[5]、Voronoi圖法[4,6]。柵格法[7,8]應用較多,具有直觀簡潔、分辨率可變、容易創建和存儲等優點,適用于室內環境路徑規劃地圖模型的建立,魯棒性強。環境構建法常與其他路徑規劃算法結合實現路徑規劃,如陳曉蛾在環境柵格地圖的基礎上實現多機器人路徑規劃。

2)在搜尋最優路徑的算法上,全局路徑規劃依據搜索算法分類,主要包括圖搜索類算法、隨機采樣類算法、智能算法等。圖搜索類算法[9]主要有Dijkstra算法、A*算法、D*算法等,與Dijkstra算法相比,A*增加了啟發式估計,減少搜索量,提高效率,同時保證路徑的最優性,但環境復雜、規模較大時,效率仍較低；隨機采樣類算法主要有概率路標算法[10]、快速隨機數算法[11],廣泛應用在動態障礙物、高維狀態空間和存在運動學、動力學等微分約束的復雜環境中,但存在耗費代價大、應用實時性較差、規劃所得路徑有可能不是最優路徑的問題[12]；智能仿生算法是一種模擬生物進化和仿生自然界動物昆蟲覓食筑巢行為的智能化算法,主要有遺傳算法[13]、蟻群算法[14]、粒子群算法[15,16]等,遺傳算法、蟻群算法適用于復雜問題求解和優化,具有潛在的并行性,但存在運算速度慢,解早熟現象；與這兩種算法相比粒子群算法優點在于收斂速度快。朱鐵欣[17]提出將蟻群算法和人工勢場法、Memetic結合應用于農業機器人。王春華等人[18]提出一種改進蟻群算法用于機器人焊接路徑規劃,王友釗等人[19]將貪心算法和遺傳算法結合用于實現倉儲車輛調度。

1.1.2 局部路徑規劃

局部路徑規劃[20,21]是在未知環境中,基于傳感器獲取周圍環境信息,并使機器人自主獲得一條無碰撞的最優路徑。用于局部路徑規劃的經典算法有人工勢場法[22]、模擬退火法[23]、模糊邏輯法[24]、神經網絡法[25]、動態窗口法[26]、強化學習法[27]以及基于行為的路徑規劃方法。人工勢場法結構簡單、計算量較小,但存在容易產生局部最小值的問題,在實際應用中發現,當目標點附近存在障礙物時,移動機器人無法順利到達,于振中[28]在障礙物的斥力勢場中添加系數項,解決了這一問題。模擬退火法,將熱力學的理論套用到統計學上,利用概率的突跳性,實現隨機優化問題的求解,避免出現局部極值問題,彌補人工勢場法的缺陷。劉愛軍[29]提出模擬退火算法與粒子群算法相結合,解決了粒子群算法容易陷入局部最優的問題,并引入自適應溫度衰變系數,使模擬退火算法能夠根據當前環境自動調整搜索條件,從而提高算法的搜索效率。模糊邏輯法是根據模糊的環境信息,依照對應表格規劃出的信息,實現局部路徑規劃,優點在于容易計算,能夠實時跟蹤規劃。楊小菊等人[30]提出一種基于模糊控制的移動機器人避障方法,但模糊規則根據經驗設定,存在經驗不完備等問題,因此該算法靈活性差,存在未知短板。

目前多采用兩種算法結合的方法彌補各自存在的問題。對于容易陷入局部最優的缺陷如遺傳算法、蟻群算法、粒子群算法、人工勢場法等,可以采用混沌或者神經網絡等算法進行優化。2013年,胡喜玲[31]將混沌優化算法的遍歷特性引入遺傳算法,以防止和克服進化過程中的“早熟”現象。2012年,肖樂[32]對蟻群算法的信息素添加混沌擾動,提高最優解的精度,多用于倉儲和物流配送。2013年,劉愛軍[29]提出混沌模擬退火粒子群優化算法,解決了粒子群算法容易陷入局部極值點、進化后期收斂速度慢、精度較差等缺點。2007年,劉玲[33]將神經網絡和遺傳算法相結合,環境采用神經網絡進行描述后,遺傳算法經路徑搜索,實現無碰撞路徑規劃。

1.2 遍歷路徑規劃

與常規的點對點的規劃不同,遍歷路徑規劃[2]找到一條能夠遍歷區域內的所有點,同時避開障礙物的路徑。該方法要求遍歷性強、重復率低,相關算法可以分為3類[34]：

1)隨機遍歷策略。采用迂回往復式、內外螺旋式[35]、隨機轉向式進行路徑規劃,不采用目前通用的效益函數,規劃算法簡單,遍歷性強、重復率低,但不能有效避開障礙物,需與局部路徑規劃算法結合。

2)沿邊規劃策略。首先沿邊移動建立環境輪廓模型,然后采用全局視角與局部路徑規劃相結合的算法實現路徑規劃。環境建模的方法有柵格法、可視圖法、Voronoi圖法、拓撲法等,局部路徑規劃方法有人工勢場法、模擬退火法、模糊邏輯法、神經網絡法等。竇文豪[36]針對大棚環境,提出基于拓撲地圖的路徑規劃方法,以最短的路徑遍歷必走路線。王仲民[37]將神經元激勵與柵格地圖結合實現全遍歷的路徑規劃。

3)漫步式探測路徑規劃。主要有動態窗口法、強化學習法、隨機采樣類搜索算法,能夠有效地避開障礙物,實現全遍歷路徑規劃,但存在著遍歷重復率高、時間開銷大、資源浪費嚴重等缺點。

遍歷路徑規劃不同于常規的點對點的規劃,要求規劃的路徑具有覆蓋率高、重復率低等特點,但采用的算法是相通的,如神經網絡、強化學習、動態窗口等智能算法。通過將智能算法融入沿邊策略、漫步策略,實現在未知地圖下的全遍歷路徑規劃。

2 強化學習算法在路徑規劃上的應用

隨著移動機器人智能化的應用需求逐漸上升,基于強化學習的路徑規劃方法[27]成為當前研究的熱點,該方法將傳感器感知的環境狀態映射到執行器動作,對外界環境變化快速響應,實現自主路徑規劃,具有實時、快速的優點。強化學習利用類似于人類思維中的試錯的方法來發現最優行為策略,目前已經在機器人行為學習方面展現出了良好的學習性能。針對基于強化學習的路徑規劃方法主要從兩大方面內容進行分析：從狀態到動作映射的正確策略和移動機器人所在環境狀態的內部表示即狀態泛化問題。

2.1 從狀態到動作映射的正確策略

強化學習的算法有時間差分法(temporal difference,TD)[38]、Q-Learning算法[39]、Sarsa算法[40]、Dyna算法[39]、Actor-Critic[41]算法等。其中TD算法是較早出現的強化學習算法,Q-Learning算法、Sarsa算法都是在TD算法的基礎上改進的,區別在于迭代的是動作值函數Q(s,a)或狀態值函數V(s),如表1。前3種算法多用于已知環境狀態下,Dyna 算法是建立環境模型代替真實環境,迭代虛擬樣本函數值,實現實時學習規劃。Actor-Critic算法[42]是一種同時估計值函數和策略的學習方法,是一種具有獨特記憶功能的TD算法,提高收斂速度,保證處處收斂。強化學習算法仍處于不斷發展的過程中,收斂速度和狀態泛化是研究的主要問題,其中在收斂速度問題上,Q-Learning算法表現出良好的收斂性,目前多采用該方法。馬朋委、潘地林[40]采用策略擇優和優化回報函數的啟發函數對Sarsa(λ)算法進行優化,提高起收斂速度；Wen S,Chen X[43]將Q-Learning與SLAM結合,實現移動機器人自主行走。

表1 三種函數區別對比

2.2 狀態泛化問題

狀態泛化問題[44～46]即環境狀態的內部表示,作為強化學習的主要研究內容之一,目的在于為強化學習方法提供較好的學習基礎,提高機器人的學習效率。主要有離散化方法、值函數逼近方法,其中值函數逼近的方法主要有神經網絡法、模糊邏輯法、人工勢場法等。

離散化方法容易出現信息丟失和“維數災難”的問題,多采用值函數逼近的方法進行優化。值函數逼近的方法多應用于連續環境狀態中,能夠降低存儲量,提高收斂速度。童亮[27]采用Kohonen狀態泛化,提高了Q-Learning的收斂速度；宋勇、李貽斌[46]提出基于人工勢能場的移動機器人強化學習初始化方法；Cruz D L,Yu W[38]將神經網絡和內核平滑技術用于強化學習的狀態泛化；黃鋁文[41]將強化學習、神經網絡應用到蘋果采摘機器人路徑規劃,得到最優安全路徑。

3 結束語

基于以上分析,移動機器人智能路徑規劃方法[47，48]研究雖然取得了重要成果,但仍存在局限性,如遺傳算法、蟻群算法容易陷入局部最優,神經網絡算法需要大量樣本。目前的改進算法以多種算法相結合、分層優化等方式為主,雖彌補了缺點,但存在諸多發展瓶頸,如算法復雜度增加,收斂速度慢。

較于其他算法，強化學習,學習能力強,適應復雜未知環境,但目前強化學習的試錯學習、狀態泛化,需要耗費大量資源。近年來腦科學與類腦智能已成為世界各國研究和角逐的熱點,類腦智能能夠智能化獲取信息、智能信息處理與通信、智能人機交互,能夠適應路徑規劃的智能化需求。類腦智能通過模仿及與環境的交互進行動作和規劃,具有自主發育能力,少量樣本學習,解決了強化學習的資源浪費的缺陷,使機器人具有發育能力,不斷提升路徑規劃的智能化水平。

類腦智能是實現通用人工智能的重要途徑,因此類腦智能應用于農業裝備的路徑規劃能夠解決目前農業裝備的路徑規劃在復雜環境中魯棒性差,適應性差的問題,可實現農田全區域路徑規劃、地頭轉向最優路徑規劃以及作物行跟蹤等智能規劃,提高農業裝備自動化、智能化水平。