王春穎, 劉 平, 秦洪政

(山東農(nóng)業(yè)大學(xué) 機(jī)械與電子工程學(xué)院 山東省園藝機(jī)械與裝備重點(diǎn)實(shí)驗(yàn)室,山東 泰安 271000)

0 引 言

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

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

1 移動(dòng)機(jī)器人的路徑規(guī)劃

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

1.1 點(diǎn)對(duì)點(diǎn)路徑規(guī)劃

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

1.1.1 全局路徑規(guī)劃

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

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

1.1.2 局部路徑規(guī)劃

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

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

1.2 遍歷路徑規(guī)劃

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

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

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

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

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

2 強(qiáng)化學(xué)習(xí)算法在路徑規(guī)劃上的應(yīng)用

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

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

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

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

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

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

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

3 結(jié)束語

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

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

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