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

王春穎, 劉 平, 秦洪政

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

0 引 言

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

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

1 移動機器人的路徑規(guī)劃

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

1.1 點對點路徑規(guī)劃

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

1.1.1 全局路徑規(guī)劃

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

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

1.1.2 局部路徑規(guī)劃

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

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

1.2 遍歷路徑規(guī)劃

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

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

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

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

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

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

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

2.1 從狀態(tài)到動作映射的正確策略

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

表1 三種函數(shù)區(qū)別對比

2.2 狀態(tài)泛化問題

狀態(tài)泛化問題[44～46]即環(huán)境狀態(tài)的內(nèi)部表示,作為強化學習的主要研究內(nèi)容之一,目的在于為強化學習方法提供較好的學習基礎(chǔ),提高機器人的學習效率。主要有離散化方法、值函數(shù)逼近方法,其中值函數(shù)逼近的方法主要有神經(jīng)網(wǎng)絡(luò)法、模糊邏輯法、人工勢場法等。

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

3 結(jié)束語

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

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

類腦智能是實現(xiàn)通用人工智能的重要途徑,因此類腦智能應用于農(nóng)業(yè)裝備的路徑規(guī)劃能夠解決目前農(nóng)業(yè)裝備的路徑規(guī)劃在復雜環(huán)境中魯棒性差,適應性差的問題,可實現(xiàn)農(nóng)田全區(qū)域路徑規(guī)劃、地頭轉(zhuǎn)向最優(yōu)路徑規(guī)劃以及作物行跟蹤等智能規(guī)劃,提高農(nóng)業(yè)裝備自動化、智能化水平。