改進強化學(xué)習(xí)算法應(yīng)用于移動機器人路徑規(guī)劃

王科銀，石 振，楊正才，楊亞會，王思山

1.湖北汽車工業(yè)學(xué)院 汽車工程學(xué)院，湖北 十堰442002

2.汽車動力傳動與電子控制湖北省重點實驗室（湖北汽車工業(yè)學(xué)院），湖北 十堰442002

3.湖北汽車工業(yè)學(xué)院 汽車工程師學(xué)院，湖北 十堰442002

隨著科技的發(fā)展，移動機器人越來越多地走進人們的日常生活。移動機器人的路徑規(guī)劃問題也越來越受到重視。路徑規(guī)劃技術(shù)能夠在參照某一指標(biāo)的條件下，幫助機器人避開障礙物規(guī)劃出一條從起點到目標(biāo)點的最優(yōu)運動路線。根據(jù)路徑規(guī)劃過程中對環(huán)境知識的已知程度，路徑規(guī)劃可以分為全局路徑規(guī)劃和局部路徑規(guī)劃[1-2]。其中應(yīng)用較為廣泛的全局路徑規(guī)劃算法有A*算法[3]、dijkstra算法[4]、可視圖法[5]、自由空間法[6]等；局部路徑規(guī)劃算法有人工勢場算法[7]、遺傳算法[8]、神經(jīng)網(wǎng)絡(luò)算法[9]、強化學(xué)習(xí)算法[10]等。強化學(xué)習(xí)算法是一種適應(yīng)性比較強的算法，可以在完全未知的環(huán)境中通過不斷試錯尋找最優(yōu)路徑，這也使得強化學(xué)習(xí)算法在移動機器人路徑規(guī)劃領(lǐng)域獲得越來越多的關(guān)注。

在移動機器人路徑規(guī)劃領(lǐng)域應(yīng)用最為廣泛的強化學(xué)習(xí)算法是Q-learning算法。傳統(tǒng)的Q-learning算法存在以下問題：（1）在初始化的過程中將所有的Q值設(shè)置成0或者是隨機值，這使得智能體在起始階段只能是盲目搜索，導(dǎo)致算法出現(xiàn)過多的無效迭代；（2）在動作選擇時采用ε-貪婪策略，太大的ε值會使智能體更多地探索環(huán)境不容易收斂，太小ε值會導(dǎo)致智能體對環(huán)境探索不夠而找到次優(yōu)解，難以平衡探索和利用之間的關(guān)系[11]。

針對上述問題，很多學(xué)者提出了各種Q-learning的改進算法。宋勇等人[12]引入人工勢場，利用先驗知識確定每點的勢能值，根據(jù)勢能值初始化Q值，提高了算法初始階段的學(xué)習(xí)效率。董培方等人[13]聯(lián)合人工勢場和環(huán)境陷阱搜索作為先驗知識初始化Q值，得到更快的收斂速度和更優(yōu)的規(guī)劃路徑。Wen等人[14]基于模糊規(guī)則初始化Q值，加快了算法的收斂速度。徐曉蘇等人[15]在引入人工勢場初始化Q值的基礎(chǔ)上，增加移動機器人的搜索步長和方向因素，縮短了路徑規(guī)劃時間，提高了路徑的平滑度。上述對Q-learning算法的改進都是根據(jù)一定規(guī)則對Q值初始化，這在一定程度上提高了算法性能，但是缺乏對智能體動作選擇策略的研究。針對當(dāng)前研究現(xiàn)狀的不足本文提出一種改進的Q-learning算法，在Q值初始化的過程中引入改進人工勢場的引力場函數(shù)，使得越靠近目標(biāo)位置狀態(tài)值越大從而智能體在起始階段就能朝著目標(biāo)位置進行搜索，減少算法起始階段的無效迭代；在動作選擇上改進ε-貪婪策略，根據(jù)算法的收斂程度動態(tài)調(diào)整貪婪因子，更好地平衡探索和利用之間的關(guān)系，進一步加快算法收斂速度，并且保證算法的收斂穩(wěn)定性。

1 相關(guān)理論

1.1 Q-learning算法

Q-learning是一種離線的時序差分強化學(xué)習(xí)算法[16]。智能體根據(jù)某一策略對狀態(tài)-動作對(s,a)進行k次采樣，得到狀態(tài)動作值函數(shù)估計值Q(s,a)，當(dāng)進行下一次采樣時，可獲得獎勵值R(s,a)并進入下一個狀態(tài)s′，智能體直接選擇狀態(tài)s′所對應(yīng)的最大狀態(tài)動作值Q(s′,a′)來更新上一個狀態(tài)s的Q(s,a)，更新公式如下：

其中，(s,a)為當(dāng)前狀態(tài)-動作對，(s′,a′)為下一時刻的狀態(tài)-動作對，R(s,a)為狀態(tài)s下執(zhí)行動作a的即時獎勵，α為學(xué)習(xí)率，通常設(shè)置a為小于1的正數(shù)，γ為折扣因子，折扣因子的取值范圍是0~1。

在Q-learning的應(yīng)用中，通常采用ε-貪婪策略來選擇下一狀態(tài)的動作，其表示在智能體選擇下一動作時以ε(ε<1)的概率隨機在動作空間中選擇動作，以1-ε的概率選擇最優(yōu)動作。

1.2 改進人工勢場法

人工勢場包括引力場和斥力場，其中目標(biāo)點對移動機器人產(chǎn)生引力，引導(dǎo)機器人朝著目標(biāo)點運動，越靠近目標(biāo)點引力越大。障礙物對機器人產(chǎn)生斥力，避免與之發(fā)生碰撞。移動機器人運動路徑上的每一點所受的合力等于該點所受目標(biāo)點的引力和障礙物的斥力之和，在合力的作用下移動機器人從起始位置出發(fā)，避開障礙物到達目標(biāo)位置。因為本文的研究基于未知環(huán)境，障礙物位置無法確定，所以只考慮引入引力場，提出如下引力場函數(shù)：

其中，ζ是大于0的尺度因子，用來調(diào)節(jié)引力大小， ||d為當(dāng)前位置與目標(biāo)點所在位置的距離，η為正常數(shù)，防止目標(biāo)點處引力值出現(xiàn)無窮大。

該方法構(gòu)造的人工勢場，整個勢能場從起點到目標(biāo)點呈現(xiàn)單調(diào)遞增趨勢，目標(biāo)點具有最大勢能值且不為無窮大。

2 改進Q-learning算法

2.1 Q值初始化

傳統(tǒng)的Q-learning算法把所有Q值初始化為0或者是隨機數(shù)值，在算法初期智能體只能是隨機地選擇動作，從而產(chǎn)生巨大的無效迭代。通過1.2節(jié)中改進的引力場函數(shù)初始化狀態(tài)值，通過狀態(tài)動作值函數(shù)和狀態(tài)值函數(shù)關(guān)系式（3）對Q值初始化。通過該方法初始化的Q值使得智能體在初始階段就能以更大的概率向目標(biāo)點方向移動，減少了算法初期的大量無效迭代，加快算法收斂。

其中，P(s′|s,a)為當(dāng)前狀態(tài)s和動作a確定的情況下轉(zhuǎn)移到狀態(tài)s′的概率，V(s′)為下一狀態(tài)的狀態(tài)值函數(shù)，對于本研究初始化Q值時，V(s′)=Uatt。

2.2 貪婪因子動態(tài)調(diào)整

如何平衡強化學(xué)習(xí)當(dāng)中探索和利用之間的關(guān)系是強化學(xué)習(xí)算法實際應(yīng)用的難點之一。探索是指智能體在選擇動作時，不遵循已經(jīng)學(xué)習(xí)到的策略，而是運用其他可能不太好的策略擴大對環(huán)境的搜索范圍，減小出現(xiàn)局部最優(yōu)的可能性；利用是指智能體在選擇下一步動作時根據(jù)已經(jīng)學(xué)習(xí)到的策略選擇當(dāng)前最優(yōu)動作。ε-貪婪策略在一定程度上平衡了探索和利用，但是智能體每次都以ε的概率在動作集中隨機選擇動作，不好的動作也以同樣的概率被選擇，由此會導(dǎo)致整個過程收斂速度慢，即使在最后收斂也會因為以ε的概率隨機選擇動作使得結(jié)果存在一定的波動。針對該問題，本文提出一種改進的ε-貪婪策略。

e為自然對數(shù)的底，當(dāng)自變量t大于0時，tanh(t)的取值范圍為（0，1）；stdn為連續(xù)n次迭代次數(shù)的步數(shù)標(biāo)準(zhǔn)差；T為系數(shù)，與模擬退火算法[17]中的溫度值作用相反，T越大隨機性越??；εmax和εmin分別為所設(shè)置的探索率的最大值和最小值。

在強化學(xué)習(xí)算法起始階段，因為算法不收斂stdn較大，智能體以εmax的概率隨機選擇動作；隨著算法的進行stdn減小，使得ε在(εmin,εmax)范圍內(nèi)取值，stdn越大表明迭代次數(shù)之間的步數(shù)差別越大，環(huán)境越需要探索，ε的取值就越大；stdn較小時，表明算法趨于收斂，ε穩(wěn)定在εmin。由以上分析可以看出，該方法設(shè)計的貪婪因子動態(tài)調(diào)整策略，使得前期以更大的概率對環(huán)境進行探索，隨著算法的進行，逐漸趨于利用，能夠更好地平衡探索和利用之間的矛盾。

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

3.1 實驗環(huán)境

利用Python的Tkinter標(biāo)準(zhǔn)化庫，搭建如圖1所示的20×20的格柵地圖作為仿真環(huán)境，每個小格柵的尺寸是20×20像素。其中方塊代表障礙物，白色格柵為無障礙區(qū)域。格柵地圖中的每一格代表一個狀態(tài)，共400個狀態(tài)。起點設(shè)置在（10，10）的坐標(biāo)位置，即狀態(tài)（1，1），終點設(shè)置在狀態(tài)（18，14）。

圖1 路徑規(guī)劃仿真環(huán)境Fig.1 Simulation enviroment of path planning

3.2 實驗參數(shù)

在仿真環(huán)境中對比以下4種算法：Trad_Q-learning代表傳統(tǒng)的Q-learning算法；APF_Q-learning代表引入人工勢場法初始化Q值的改進算法；Adj_Q-learning代表使用貪婪因子動態(tài)調(diào)整策略替代ε-貪婪策略改進算法；Imp_Q-learning代表本文提出的最終改進算法。

4種算法的相同參數(shù)設(shè)置為：學(xué)習(xí)率a=0.01，折扣因子γ=0.9，最大迭代次數(shù)20 000次。其他設(shè)置如表1。

表1 4種算法的設(shè)置Table 1 Settings of 4 kinds of algorithms

對于4種算法獎勵函數(shù)設(shè)置為：

貪婪因子動態(tài)調(diào)整策略參數(shù)如下：εmax=0.5,εmin=0.01,T=500,n=10。

3.3 實驗結(jié)果與分析

圖2中（a）~（d）依次表示上述4種算法的收斂情況，當(dāng)路徑長度在小范圍內(nèi)波動時認(rèn)為算法收斂。表2詳細(xì)對比了4種算法的性能，收斂條件都設(shè)置為連續(xù)10次迭代步數(shù)標(biāo)準(zhǔn)差小于5，每種算法運行10次取數(shù)據(jù)平均值。

圖2 4種算法收斂回合Fig.2 Convergence episode in 4 kinds of algorithms

表2 4種算法性能比較Table 2 Performences comparison of 4 kinds of algorithms

實驗結(jié)果表明4種算法在迭代一定次數(shù)后都可以規(guī)劃出最優(yōu)路徑，圖1中的藍色圓點展示了某次實驗規(guī)劃出的最優(yōu)路徑。對比算法APF_Q-learning和算法Trad_Q-learning可知，引入人工勢場法初始化Q值可使得算法收斂時間縮短79.2%，迭代次數(shù)減少50.0%，但是算法在收斂穩(wěn)定性上沒有提升；對比算法Adj_Q-learning和算法Trad_Q-learning可知，動態(tài)調(diào)整貪婪因子可使得算法收斂時間縮短62.4%，迭代次數(shù)減少40.2%，算法的收斂結(jié)果穩(wěn)定性得到了提升，算法收斂后只有極少數(shù)的波動；對比算法Imp_Q-learning和算法Trad_Q-learning可知，本文提出的最終改進算法在初始化Q值時引入人工勢場法，在動作選擇時動態(tài)調(diào)整貪婪因子可使得算法收斂時間縮短85.1%，迭代次數(shù)減少74.7%，同時算法的收斂結(jié)果穩(wěn)定性也得到了提升。

4 結(jié)語

針對未知靜態(tài)環(huán)境下移動機器人的路徑規(guī)劃問題，為了提高強化學(xué)習(xí)算法的收斂速度和收斂結(jié)果穩(wěn)定性，本文在傳統(tǒng)Q-learning算法的基礎(chǔ)上引入改進人工勢場法初始化Q值，同時在動作選擇時動態(tài)調(diào)整貪婪因子。通過實驗表明算法的效率和收斂結(jié)果的穩(wěn)定性都得到大幅提升。但是該算法在應(yīng)用時需要根據(jù)不同的情境設(shè)置6個參數(shù)，如何設(shè)置算法中的參數(shù)，使得算法具有更好的適應(yīng)性是接下來研究的重點。