基于強(qiáng)化學(xué)習(xí)的移動(dòng)機(jī)器人路徑規(guī)劃研究綜述

劉志榮，姜樹海

（1.南京林業(yè)大學(xué) 機(jī)械電子工程學(xué)院，南京 210037；2.南京林業(yè)大學(xué) 智能控制與機(jī)器人技術(shù)研究所，南京 210037）

0 引言

隨著電子信息技術(shù)，計(jì)算機(jī)技術(shù)以及機(jī)械制造技術(shù)不斷成熟，移動(dòng)機(jī)器人正往著高度智能化方向邁進(jìn)。智能機(jī)器人的一個(gè)重要特征就是在復(fù)雜動(dòng)態(tài)環(huán)境下能夠進(jìn)行良好的路徑規(guī)劃。所謂的路徑規(guī)劃就是指機(jī)器人根據(jù)各種傳感器對(duì)周圍環(huán)境進(jìn)行感知，自主搜索出一條從起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞路徑。路徑規(guī)劃的核心是算法的設(shè)計(jì)，路徑規(guī)劃算法根據(jù)智能化程度可分為傳統(tǒng)算法、啟發(fā)式算法、智能算法、強(qiáng)化學(xué)習(xí)算法四類。

傳統(tǒng)算法可分為可視圖法、人工勢(shì)場(chǎng)法[1]、模擬退火法[2]和模糊邏輯算法[3]。傳統(tǒng)算法缺乏靈活、易于陷入局部最優(yōu)值。啟發(fā)式算法是具有搜索能力的算法，該類算法在離散路徑拓?fù)渲芯哂泻芎玫剡\(yùn)用[4]。智能算法是人們通過仿生學(xué)研究發(fā)現(xiàn)的算法。常用的智能算法有神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、群智能算法。

以上介紹的算法都是基于樣本的監(jiān)督學(xué)習(xí)算法，監(jiān)督學(xué)習(xí)算法的固有屬性使得機(jī)器人先驗(yàn)知識(shí)不足時(shí)很難進(jìn)行良好的路徑規(guī)劃。強(qiáng)化學(xué)習(xí)又稱再勵(lì)學(xué)習(xí)，是由美國學(xué)者M(jìn)insky[5]于1954年提出的仿生算法。該算法通過機(jī)器人與環(huán)境進(jìn)行不斷試錯(cuò)迭代獲取反饋信息來優(yōu)化策略。它不依賴環(huán)境模型以及先驗(yàn)知識(shí)，又具有自主學(xué)習(xí)和在線學(xué)習(xí)的特點(diǎn)，逐漸成為機(jī)器人在非結(jié)構(gòu)環(huán)境下路徑規(guī)劃的研究熱點(diǎn)[6,7]。論文將對(duì)RL的研究現(xiàn)狀以及發(fā)展變化進(jìn)行綜述，整體框架圖如圖1所示。

圖1 本文的整體框架

1 強(qiáng)化學(xué)習(xí)基礎(chǔ)

強(qiáng)化學(xué)習(xí)的基本要素包含策略、值函數(shù)、獎(jiǎng)賞函數(shù)、環(huán)境模型[8]。根據(jù)求解方法不同，強(qiáng)化學(xué)習(xí)算法分為值函數(shù)法和直接策略搜索法。值函數(shù)法根據(jù)狀態(tài)轉(zhuǎn)移概率是否已知分為基于模型的強(qiáng)化學(xué)習(xí)算法和與模型無關(guān)強(qiáng)化學(xué)習(xí)算法兩類。前者利用已經(jīng)獲得的學(xué)習(xí)經(jīng)驗(yàn)構(gòu)建環(huán)境模型學(xué)習(xí)值函數(shù)來獲得策略，常用的基于模型的強(qiáng)化學(xué)習(xí)算法有DP、Dyna-Q、DDP算法。與模型無關(guān)的強(qiáng)化學(xué)習(xí)算法通過機(jī)器人與環(huán)境之間反復(fù)交互直接學(xué)習(xí)值函數(shù)來得到相應(yīng)的策略。典型的與模型無關(guān)的強(qiáng)化學(xué)習(xí)算法包括Q-learning、Monte Carlo、TD、Sarsa。直接策略搜索法不考慮值函數(shù)，而是把策略參數(shù)化，直接尋找一個(gè)最優(yōu)的決策。

強(qiáng)化學(xué)習(xí)以其模仿動(dòng)物的思維方式進(jìn)行學(xué)習(xí)，增加了系統(tǒng)的智能性，但以下三個(gè)問題使得基于強(qiáng)化學(xué)習(xí)的機(jī)器人在復(fù)雜動(dòng)態(tài)環(huán)境下的路徑規(guī)劃無法滿足實(shí)際應(yīng)用。一是在大規(guī)模狀態(tài)空間和動(dòng)作空間情況下，算法對(duì)每個(gè)狀態(tài)和動(dòng)作進(jìn)行無限次重復(fù)訓(xùn)練，將會(huì)導(dǎo)致維數(shù)災(zāi)難[9]，二是機(jī)器人在執(zhí)行完動(dòng)作后，所獲得的回報(bào)函數(shù)值往往不是即時(shí)的，這很難滿足機(jī)器人在路徑規(guī)劃中實(shí)時(shí)性的需要，三是強(qiáng)化學(xué)習(xí)必須在利用和探索之間進(jìn)行折中，即在已知的信息下進(jìn)行最優(yōu)策略選擇和進(jìn)行新路徑探索之間的折中。接下來的兩章節(jié)將分別從值函數(shù)法和直接策略搜索法綜述學(xué)者們基于改進(jìn)的強(qiáng)化學(xué)習(xí)算法在移動(dòng)機(jī)器人的路徑規(guī)劃中的應(yīng)用。

2 值函數(shù)法

值函數(shù)用來定義當(dāng)前狀態(tài)下機(jī)器人選擇策略π的優(yōu)劣程度。值函數(shù)法的目標(biāo)是通過最大化每個(gè)狀態(tài)的值函數(shù)來得到最優(yōu)策略。

Q-learning是最典型的基于值函數(shù)法求解的強(qiáng)化學(xué)習(xí)算法，由Watkins[10]在1989年提出。Q-learning算法無需知道模型就可以保證收斂，是目前應(yīng)用于機(jī)器人路徑規(guī)劃中最有效的強(qiáng)化學(xué)習(xí)算法。Q-learning改進(jìn)算法種類繁多，找其共性進(jìn)行歸類，主要有以下五個(gè)角度。

1）將Dyna學(xué)習(xí)框架加入到Q-learning中。該算法利用少許真實(shí)數(shù)據(jù)建立環(huán)境模型，采用虛擬樣本更新值函數(shù)，通過增加計(jì)算復(fù)雜度來降低時(shí)間復(fù)雜度。Kao-Shing Hwang等[11]結(jié)合樹狀結(jié)構(gòu)和Dyna-Q算法構(gòu)建環(huán)境模型來加速算法收斂，他們?yōu)镈yna-Q的完善發(fā)展做出了有益的研究工作。VIET Hoang-huu等[12]利用Dyna-Q算法解決移動(dòng)機(jī)器人在未知環(huán)境中的定位問題，這是Dyna-Q在定位導(dǎo)航中的第一次嘗試。

2）將啟發(fā)因子融入Q-learning中。啟發(fā)因子往往能增強(qiáng)算法的某個(gè)環(huán)節(jié)，最終獲得更好的效果。Bianchi RAC等[13]提出啟發(fā)式加速Q(mào)學(xué)習(xí)算法，即運(yùn)用啟發(fā)因子影響動(dòng)作選擇。Fengyun Zhang等[14]根據(jù)貪婪搜索因子來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，通過RBF（Radial Basis Function）神經(jīng)網(wǎng)絡(luò)進(jìn)行權(quán)重更新，改進(jìn)后的算法能夠提高初始先驗(yàn)知識(shí)不足情況下的學(xué)習(xí)效率。此外，啟發(fā)因子還能緩解強(qiáng)化學(xué)習(xí)的延時(shí)回報(bào)問題[15]。

3）與其他算法進(jìn)行融合。單一算法在解決特定問題上往往有比較好的表現(xiàn)，而機(jī)器人在復(fù)雜環(huán)境下的路徑規(guī)劃問題是一個(gè)NP難題，因此融合不同算法的優(yōu)點(diǎn)成為學(xué)者們的研究熱點(diǎn)。Ni Jianjun等[16]在Q學(xué)習(xí)基礎(chǔ)上通過神經(jīng)網(wǎng)絡(luò)來估計(jì)難以獲得的狀態(tài)，為群體機(jī)器人路徑規(guī)劃提供了一個(gè)解決方案。另外，動(dòng)態(tài)障礙物的路徑軌跡也取得了發(fā)展，Mihai Duguleana等[17]在已知全局信息基礎(chǔ)上，通過Q-learning和神經(jīng)網(wǎng)絡(luò)融合算法可以在動(dòng)態(tài)和靜態(tài)障礙物并存的環(huán)境中獲得無碰撞地軌跡。Khanduja等[18]為群機(jī)器人的路徑規(guī)劃的發(fā)展做了有益的工作。

4）將分層思想引入到Q-learning中。分層強(qiáng)化學(xué)習(xí)算法[19]將原來的整個(gè)任務(wù)分解成一些彼此獨(dú)立的子任務(wù)進(jìn)行學(xué)習(xí)，加快學(xué)習(xí)速率。很多學(xué)者基于這一思想對(duì)Q學(xué)習(xí)進(jìn)行了研究。Buitrago等[20]提出了基于選擇的分層學(xué)習(xí)方法，在第一層里利用Q-learning算法分別訓(xùn)練運(yùn)動(dòng)的基本行為，在第二層里協(xié)調(diào)這些基本行為來解決規(guī)劃的任務(wù)，仿真結(jié)果表明該算法能夠很好地應(yīng)用于未知環(huán)境的路徑規(guī)劃。

5）將深度學(xué)習(xí)框架融入Q-learning算法中。深度強(qiáng)化學(xué)習(xí)算法是近幾年在深度學(xué)習(xí)發(fā)展的基礎(chǔ)上而興起的新的算法，該算法將深度學(xué)習(xí)的感知能力和強(qiáng)化學(xué)習(xí)的決策能力進(jìn)行了有機(jī)統(tǒng)一，是一種更接近人類思維方式的人工智能方法，可以有效解決維數(shù)災(zāi)難問題。Lei Tai等[21]利用深度強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)了移動(dòng)機(jī)器人在復(fù)雜環(huán)境下的導(dǎo)航。之后他們[22]通過深度強(qiáng)化學(xué)習(xí)以視覺傳感器為平臺(tái)，以RGB-D圖片為輸入信息，直接輸出機(jī)器人的控制動(dòng)作，該思想將強(qiáng)化學(xué)習(xí)算法上升到了新的高度。Linhai Xie等[23]利用單眼RGB視覺傳感器，構(gòu)建雙層強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)就能獲得很好的避障效果，為路徑規(guī)劃的實(shí)現(xiàn)打下了很好的基礎(chǔ)。Yu Fan Chen等[24]利用深度強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)了機(jī)器人小車在行人密集的環(huán)境中自動(dòng)導(dǎo)航的任務(wù)。

3 直接策略搜索法

直接策略搜索法將策略參數(shù)化，通過梯度上升思想來尋找最優(yōu)參數(shù)。直接策略搜索算法包括模仿學(xué)習(xí)、策略梯度方法和基于演化算法的強(qiáng)化學(xué)習(xí)[25]。在機(jī)器人路徑規(guī)劃上主要使用前兩種算法。

模仿學(xué)習(xí)[26]是從人類社會(huì)的教學(xué)過程中受到啟發(fā)，通過引入“導(dǎo)師”來解決問題的一種方法。模仿學(xué)習(xí)分為逆向強(qiáng)化學(xué)習(xí)和直接策略學(xué)習(xí)兩大類，前者先從示范數(shù)據(jù)中學(xué)習(xí)獎(jiǎng)賞函數(shù)，然后基于此通過RL算法學(xué)習(xí)最優(yōu)策略。論文[27]中，機(jī)器人從給定的數(shù)據(jù)庫中學(xué)習(xí)獎(jiǎng)賞函數(shù)獲得最優(yōu)策略。后者直接從示范數(shù)據(jù)中學(xué)習(xí)從狀態(tài)到動(dòng)作的映射函數(shù)。Hazara M等[28]讓機(jī)器人從人類示范動(dòng)作中挑選出最合適的動(dòng)作。

策略梯度方法[29]是通過梯度上升思想，最大化累積期望獎(jiǎng)賞來優(yōu)化帶參策略。策略梯度避免了基于值函數(shù)的方法帶來的策略退化[30]現(xiàn)象。Kober J等[31]通過優(yōu)化策略參數(shù)來獲得最優(yōu)參數(shù)。

相比于值函數(shù)法，策略搜索的方法容易收斂到局部最小值，此外，機(jī)器人進(jìn)行路徑規(guī)劃中的動(dòng)作空間一般都是離散動(dòng)作，策略搜索的優(yōu)越性并不能體現(xiàn)出來，因此策略搜索方法在機(jī)器人的路徑規(guī)劃中應(yīng)用較少。

4 結(jié)束語

強(qiáng)化學(xué)習(xí)無需任何的環(huán)境先驗(yàn)知識(shí)，在經(jīng)過反復(fù)試錯(cuò)后就能進(jìn)行良好的路徑規(guī)劃，這將使得其在動(dòng)態(tài)環(huán)境下的路徑規(guī)劃具有更加廣泛的應(yīng)用。從移動(dòng)機(jī)器人路徑規(guī)劃的研究現(xiàn)狀以及發(fā)展需求來看，未來移動(dòng)機(jī)器人的路徑規(guī)劃研究主要集中在以下三個(gè)方面。

1）更廣義的路徑規(guī)劃。傳統(tǒng)機(jī)器人的路徑規(guī)劃一般以路徑最短為原則，但隨著機(jī)器人應(yīng)用越來越廣泛，路徑規(guī)劃的評(píng)判標(biāo)準(zhǔn)也越來越多樣化。例如對(duì)人流量密集的場(chǎng)所來說，能否遵循社會(huì)準(zhǔn)則或許是評(píng)判機(jī)器人路徑規(guī)劃好壞的依據(jù)。

2）新的路徑規(guī)劃方法的研究。隨著現(xiàn)代科技的發(fā)展，將會(huì)出現(xiàn)新的智能方法，結(jié)合現(xiàn)代科技尋找更優(yōu)越的路徑規(guī)劃方法已成為一種趨勢(shì)。比如近幾年興起的深度強(qiáng)化學(xué)習(xí)算法。

3）多機(jī)器人多任務(wù)路徑規(guī)劃的研究。隨著移動(dòng)機(jī)器人應(yīng)用范圍的不斷擴(kuò)大，移動(dòng)機(jī)器人的工作環(huán)境與任務(wù)會(huì)更加復(fù)雜。需要考慮怎樣將單個(gè)機(jī)器人的路徑規(guī)劃擴(kuò)展到多機(jī)器人的路徑規(guī)劃。此外，未來機(jī)器人在路徑規(guī)劃的同時(shí)可能還要執(zhí)行其他任務(wù)。