融合探索規(guī)則和知識共享的單智能體路徑規(guī)劃

鄧輔秦，官檜鋒，黃煥釗，李偉科，洪俊填，王宏民，馮其

（1.五邑大學 智能制造學部，廣東 江門 529020；2.深圳市人工智能與機器人研究院，廣東 深圳 518116；3.五邑大學 應用物理與材料學院，廣東 江門 529020）

移動機器人是科學技術(shù)發(fā)展中最活躍的領(lǐng)域之一，越來越多地用于醫(yī)療、交通運輸、安防等領(lǐng)域.路徑規(guī)劃是移動機器人不可或缺的一部分，在一定程度上代表了移動機器人的發(fā)展水平.因此，路徑規(guī)劃的研究對于促進移動機器人的發(fā)展具有重要意義.解決機器人路徑規(guī)劃問題的方法主要分為3類：傳統(tǒng)搜索類算法、強化學習算法以及二者的結(jié)合.

傳統(tǒng)搜索類路徑規(guī)劃算法因其獨特的優(yōu)勢而被應用于機器人導航，例如，Dijkstra算法可以計算從源節(jié)點到其他節(jié)點的最短路徑長度，但是在大規(guī)模復雜環(huán)境中搜索兩點間的最短路徑時，算法效率較低[1].人工勢場算法[2]具有求解實時性，但是需要計算復雜的合力大小與方向，若合力大小為0，則容易陷入局部最優(yōu)點.廣度優(yōu)先搜索算法[3]和深度優(yōu)先搜索算法[4]可以規(guī)劃出最佳路徑，卻需要遍歷環(huán)境模型的每個節(jié)點，不適用于高維度的未知環(huán)境.蟻群算法可以在未知環(huán)境中找到路徑，但每一次迭代后所有螞蟻得出的解可能不是最優(yōu)的[5].Rapidly-exploring Random Tree算法可以通過隨機采樣來快速規(guī)劃路徑，但是存在生成的路徑曲折的問題[6].

強化學習是一類允許移動機器人與環(huán)境互動并不斷提高機器人學習能力的算法，適用于未知環(huán)境下的路徑規(guī)劃[7].近年來基于傳統(tǒng)方法積累先驗知識再利用強化學習進行路徑優(yōu)化的方法逐漸成為主流，因為先驗知識有助于提高強化學習的收斂速度，如文獻[8]利用人工勢場法初始化環(huán)境每個點的Q值，提供了先驗知識，減少了Q-learning算法初始階段因重復探索而產(chǎn)生的大量無效迭代，但該算法容易陷入勢場值為 0的點，不適用于障礙物密度大的復雜環(huán)境.在柵格環(huán)境下，首先基于搜索規(guī)則積累先驗知識，再將其應用于強化學習算法進行路徑優(yōu)化的方法已經(jīng)取得了一定的效果[9].但是對于一些復雜的環(huán)境，固定性搜索規(guī)則容易使機器人陷入死角區(qū)域，不能積累有效的先驗知識.其次，需要探求能夠?qū)⑺e累的先驗知識進行有效整合與共享方法.最后，需要設計出良好的獎勵機制才能促使強化學習算法有效地收斂.為此，本文在 3方面進行改進：首先在固定性搜索規(guī)則內(nèi)加入隨機因子；其次，采用對Q值求和與求最大值兩種方法進行先驗知識的合成并共享；最后，通過對比實驗設計出一套良好的獎勵機制.

1 基于固定性搜索規(guī)則的強化學習路徑規(guī)劃

1.1 強化學習算法

強化學習方法是一種在未知環(huán)境中通過反復試錯來學習近似最優(yōu)策略，從而使機器人能夠在序列決策任務中選擇最佳動作的方法[10].在強化學習中，通常將機器人與其周圍環(huán)境之間的交互過程稱為馬爾可夫決策過程[11].馬爾可夫決策過程的基本單元是一個元組(S,A,R,T,γ)[12]，其中：S是狀態(tài)空間；A是動作空間；R獎勵函數(shù)；T是狀態(tài)轉(zhuǎn)移模型；γ獎勵折扣因子.

強化學習方法通過式（1）的貝爾曼方程不斷更新狀態(tài)動作值函數(shù)Q(s,a)來進行策略的優(yōu)化[13]，

將環(huán)境建模成二維柵格地圖，基于Q-learning的強化學習算法能有效地在柵格地圖進行動作決策來規(guī)劃最優(yōu)路徑.Q-learning是目前應用于機器人路徑規(guī)劃中最有效且能保證收斂的強化學習算法.該算法首先建立一張Q表，機器人在與環(huán)境進行交互的同時不斷基于環(huán)境反饋的獎勵來修改Q表的值，更正動作策略集，最終使得機器人的動作趨于最優(yōu)動作集，規(guī)劃出最優(yōu)路徑[14].

1.2 基于固定性搜索規(guī)則的強化學習算法

在超市、物流倉庫等環(huán)境中，貨架的排列一般是規(guī)則的，所以機器人的導航地圖常是柵格地圖，基于Q表的Q-learning算法適用于該場景下的路徑規(guī)劃.由于經(jīng)典的Q-learning算法在初始化時沒有先驗知識，這意味著機器人將隨機選擇一個可能會碰到障礙物的動作，但是在以上環(huán)境中，機器人需要具有有效避開障礙物并像人類一樣迅速向目標點移動的能力.

在現(xiàn)實生活中，一些基本的交通規(guī)則要求駕駛員具有正確的駕駛行為，而移動導航制造商積累了大量正確的駕駛行為知識作為基本路徑數(shù)據(jù)，此路徑數(shù)據(jù)可以協(xié)助其他駕駛員高效且安全地進行路徑規(guī)劃任務.相似地，在機器人使用 Q-learning規(guī)劃路徑之前，可以根據(jù)人類交通經(jīng)驗制定一些具有探索性的規(guī)則.文獻[9]提出了一種基于固定性搜索規(guī)則的兩階段強化學習路徑規(guī)劃算法：Rule-Based Shallow-Trial Reinforcement Learning (RSRL)，本文使用該算法作為對比方法.該算法的第一階段：機器人基于固定性搜索規(guī)則生成一張存儲著前往目標點的路徑知識Q表.固定性搜索規(guī)則可歸納為以下步驟：

1）在柵格環(huán)境中，分別檢測上下左右 4個方向上距離機器人一個格子單元的位置是否有障礙物，并將不會碰壁的動作添加到可執(zhí)行列表中；

2）以機器人當前位置為起點，得到一個指向目標點的向量，比較該向量的x分量和y分量的大小，以向量的大小為優(yōu)先級依次檢測2個分量方向?qū)膭幼魇欠裨诳蓤?zhí)行列表，若在，輸出較大分量方向?qū)膭幼鳎瑒t執(zhí)行步驟4），若都不在，執(zhí)行步驟3）；

3）從可執(zhí)行列表中隨機挑選一個動作；

4）執(zhí)行所選動作，每個動作只移動一個柵格，并使用狀態(tài)動作值函數(shù)更新Q表；

5）若抵達目標點則該次迭代結(jié)束，否則繼續(xù)執(zhí)行步驟1）；

6）執(zhí)行以上步驟N次后輸出機器人對應的Q表；

該算法的第二階段：機器人使用Q-learning算法進行訓練直到完成設定的迭代次數(shù).

2 固定性搜索規(guī)則強化學習算法的改進

2.1 固定性搜索規(guī)則強化學習算法的不足與改進

在障礙物少的靜態(tài)場景中，使用RSRL算法第一階段固定性搜索規(guī)則方法產(chǎn)生的先驗知識可以提高第二階段使用Q-learning算法進行路徑優(yōu)化的時間效率，但機器人在某些復雜環(huán)境下仍舊無法有效地進行路徑規(guī)劃，甚至會被卡在死角位置，這是因為在第一階段的第 2步中，RSRL算法幾乎以接近 100%的概率徑直地驅(qū)使機器人往目標點方向移動，這使得機器人缺乏處理不同環(huán)境的靈活性，如果前往目標點的方向上障礙物圍成了直角區(qū)域，如圖1所示，左上角的三角形代表起點，右下角圓圈為目標點，黑色方塊是障礙物，則機器人不能高效地移動到目標點.

為了解決上述問題，本文提出了一種兩階段強化學習路徑規(guī)劃方法.相比于 RSRL中固定性搜索規(guī)則，本文算法在第一階段添加了概率為(100 -β)/100的隨機探索規(guī)則，以提高適應不同場景的靈活性.本文將累積先驗知識的機器人命名為先行機器人，β表示先行機器人對固定性搜索規(guī)則的依賴程度.為了驗證不同β值對先行機器人路徑規(guī)劃的影響，在如圖 1環(huán)境中，先行機器人需要基于本文算法第一階段的方法完成從起點到目標點移動兩次的實驗.表 1記錄了不同β值的程序運行時間.顯然，在這類復雜障礙物環(huán)境中，β值越大，路徑規(guī)劃效率越低.

表1 β值與消耗時間的對應關(guān)系

圖1 RSRL算法難以規(guī)劃路徑的環(huán)境

本文算法是一種兩階段的方法，第一階段基于探索規(guī)則積累路徑知識，而探索規(guī)則是對 RSRL算法中固定性搜索規(guī)則的創(chuàng)新，流程如下：

1）初始化仿真環(huán)境；

2）每個先行機器人檢測其當前位置上下左右 4個方向上距離一個格子的位置是否有障礙物，并將無障礙物方向?qū)膭幼骷{入各自的可執(zhí)行列表；

3）每個先行機器人以β的概率執(zhí)行：以當前位置為起點，得到一個指向目標點的向量，比較該向量的x分量和y分量的大小，以向量的大小為優(yōu)先級依次檢測兩個分量方向?qū)膭幼魇欠裨诳蓤?zhí)行列表，若在，挑選較大分量對應的動作，執(zhí)行步驟5），若都不在，則在可執(zhí)行列表隨機選擇一動作；

4）每個先行機器人以100-β的概率在可執(zhí)行列表選擇一個動作；

5）每個先行機器人執(zhí)行所選動作，并通過狀態(tài)動作值函數(shù)更新各自的 Q表，直到抵達同一個目標點；

6）執(zhí)行以上步驟N次后輸出先行機器人對應的Q表；

2.2 知識共享方法的設計

第一階段算法雖克服了RSRL方法的缺陷，但規(guī)劃出來的路徑有可能是次優(yōu)的，原因有二：1）僅有一個機器人利用算法從同一起點積累先驗知識不能對環(huán)境進行充分地探索；2）算法存在一定隨機性.

假定一些隨機分布在不同的位置的先行機器人使用第一階段算法來生成路徑知識，這些原始的路徑知識共享給未被訓練新機器人以提高路徑規(guī)劃效率.本文假設先行機器人與新機器人的相對位置是已知的，若在室外，通過定位技術(shù)可以確定機器人間的相對位置.

每個先行機器人使用本文算法第一階段方法積累路徑知識后都輸出一張存儲了路徑知識的 Q表，路徑知識以Q值的形式存儲于Q表，Q表的每一格對應柵格環(huán)境中的每一格即強化學習中的狀態(tài)，每一格根據(jù)動作維度劃分為若干小格即狀態(tài)動作序列，小格存儲機器人在該狀態(tài)下執(zhí)行某一動作后得到的Q值.本文分別利用以下兩種知識共享方法對Q表進行處理：

方法1）：在所有Q表中，將相同狀態(tài)動作序列的Q值相加，然后合并到一個共享Q表中，該表可用作下一迭代中新機器人的基礎(chǔ)經(jīng)驗.

方法2）：在所有Q表中，對挑選相同狀態(tài)動作序列求最大的Q值，然后賦值到一個共享的Q表中，該表可用作下一迭代時新機器人的基礎(chǔ)經(jīng)驗.文獻[15]將類似的策略應用在Q-learning算法.

本文算法只包含兩個子類：RBAQT和RBMQT，分別對應上述知識共享方法1）和2）.因此，在本文算法的第二階段，分別利用知識共享方法1）或2）合成對應的新Q表后共享給新機器人，新機器人以新Q表作為先驗知識，并基于Q-learning算法優(yōu)化路徑直到完成設定的迭代次數(shù).

2.3 獎勵機制的設計

強化學習算法需要良好的獎勵機制才能有效收斂，如果機器人在探索過程中難以獲得正獎勵，則容易出現(xiàn)學習緩慢等問題.為解決該問題，本文設計了兩種獎勵機制并通過實驗來挑選出最優(yōu)的一種獎勵方法，如表2所示.在表2中，實驗設置R0是機器人成功規(guī)避障礙物的即時獎勵；R1是機器人到達目標點的獎勵；R2是機器人碰到障礙物的負獎勵；R3是機器人到達目標點的獎勵；R4是機器人基于兩種算法第一階段方法訓練的即時獎勵.在獎勵機制二中，d表示機器人當前狀態(tài)與目標點之間的歐式距離，距離目標點越近，d值越小，機器人獲得的獎勵值就越大，d大于等于1.若機器人執(zhí)行動作后的位置比之前更加遠離目標點，則參數(shù)i為-1；否則，i為1.參數(shù) f表示在一次迭代中機器人訪問某個狀態(tài)s的頻率，f值越大，獎勵就越小.每迭代完一次后，f設置為0.

表2 獎勵機制

3 仿真實驗及結(jié)果分析

本文首先設置2種環(huán)境進行各10組的隨機生成障礙物實驗，分別為13× 13維度約有60個障礙物和14× 14維度約有80個障礙物，障礙物約占環(huán)境面積的 30%到 40%，但是為了更好地進行各算法在所規(guī)劃出路徑長度上的對比，本文還設置了19× 19維度約有121個障礙物的實驗環(huán)境，如圖2所示，起點為左上角的三角形，右下角實心圓點代表目標點，黑色方塊表示障礙物.在該環(huán)境的10組實驗中，障礙物的位置和數(shù)量是不變的.本文算法在以上網(wǎng)格環(huán)境進行路徑規(guī)劃時，僅設置了兩個先行機器人（圖2空心圓圈）積累先驗知識，其在空白區(qū)域隨機初始化.

圖2 19×19維度固定障礙物實驗環(huán)境

本文使用RBMQT和RBAQT兩種方法分別基于獎勵機制一和獎勵機制二在如圖2所示實驗環(huán)境中進行10組實驗，記錄的10組實驗的平均運行時間如表3所示.從表3可以明顯得出獎勵機制二比獎勵機制一有更高的路徑規(guī)劃效率這一結(jié)論.機器人越接近目標點，d越小，獲得的正獎賞值越大.因此，獎勵機制二可以驅(qū)動機器人有效地朝目標點移動，故后續(xù)實驗使用獎勵機制二.

表3 程序運行時間對比

機器人的動作空間集合A包括上下左右 4個動作，每個動作只移動一個柵格.一次迭代被定義為機器人從其起點一直運動到目標點的一次過程.為了確保算法最終可以收斂，一組實驗中設置19次迭代，其中包括了算法第一階段方法進行先驗知識積累的N次迭代.實驗參數(shù)的設定如表4所示，ε是貪婪率，它表示機器人對先驗知識的依賴，若ε太小，則不能充分利用先驗知識；若ε太大，則機器人無法很好地探索，然后容易陷入局部最優(yōu)狀態(tài).Δε表示每兩次迭代中ε的增量，直到ε大于97.5則停止.α是學習率，γ是折扣因子.

表4 參數(shù)設置

在19× 19維度約有121個障礙物的實驗環(huán)境中，機器人基于本文算法、蟻群算法、Q-learning、RSRL算法在相同的迭代次數(shù)下所規(guī)劃的路徑如圖3所示.

圖3 路徑規(guī)劃圖

本文實驗旨在算法能夠穩(wěn)定地規(guī)劃出最優(yōu)路徑的前提下統(tǒng)計算法運行的時間.故在確保 RSRL算法和本文算法可以收斂的前提下，重復做 10組實驗，每組實驗迭代 19次，計算 10組實驗的平均運行時間，這包括先行機器人使用兩種算法第一階段方法產(chǎn)生先驗知識的訓練時間.此外，本文還將近些年流行的強化學習算法Q-learning納入對比范疇，迭代的次數(shù)、實驗的組數(shù)與RSRL算法和本文算法一致.每種算法的平均運行時間對比如表5所示，與Q-learning、RSRL算法相比，本文算法在每種環(huán)境下均具有優(yōu)勢.特別地，為了量化本文算法的優(yōu)勢，先計算出對比方法中最具優(yōu)勢的RSRL算法在3種實驗環(huán)境平均運行時間之和，為249.43 s，再計算出本文兩個算法在3種實驗環(huán)境平均運行時間之和的均值，為150.30 s，得出差值99.13 s，該差值占RSRL算法平均運行時間之和的百分比即為本文算法相對于RSRL算法在時間效率上的提升，最終求得為39.7%.

表5 不同實驗環(huán)境下的各算法平均運行時間對比

最后，在gazebo仿真平臺上進行了如圖2所示實驗環(huán)境下的機器人路徑規(guī)劃仿真，機器人規(guī)劃最優(yōu)路徑的視頻可以在以下鏈接中查看：https://www.bilibili.com/video/BV1SK411F75e/.

4 結(jié)論

本文提出了一種融合隨機探索規(guī)則和知識共享的兩階段強化學習路徑規(guī)劃方法，適用于求解柵格環(huán)境下的單智能體路徑規(guī)劃任務.在本文算法的第一階段，先行機器人基于隨機探索規(guī)則高效地完成先驗知識的積累，之后分別利用兩種知識共享方法得到Q表.在本文算法的第二階段，新機器人基于共享Q表進行路徑規(guī)劃，無需大量的訓練時間即可規(guī)劃出最優(yōu)路徑.本文在3種實驗環(huán)境中進行了算法運行時間的對比測試，與傳統(tǒng)方法中最優(yōu)的RSRL算法相比，本文算法在時間效率上提均提升了39.7%.新機器人可以在訓練過程中減少無效探索的次數(shù)，路徑規(guī)劃效率得以提高.本文算法適用于執(zhí)行離散動作的無人倉儲物流機器人.但是由于 Q-learning算法的局限性，如若目標點發(fā)生變動則需要再次學習才可規(guī)劃出最優(yōu)路徑，后期有望通過更多的啟發(fā)式的算法產(chǎn)生更加有效的先驗知識以克服本文算法的局限性.