王科銀，石 振，楊正才，楊亞會(huì)，王思山

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

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

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

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

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

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

1 相關(guān)理論

1.1 Q-learning算法

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

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

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

1.2 改進(jìn)人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)包括引力場(chǎng)和斥力場(chǎng)，其中目標(biāo)點(diǎn)對(duì)移動(dòng)機(jī)器人產(chǎn)生引力，引導(dǎo)機(jī)器人朝著目標(biāo)點(diǎn)運(yùn)動(dòng)，越靠近目標(biāo)點(diǎn)引力越大。障礙物對(duì)機(jī)器人產(chǎn)生斥力，避免與之發(fā)生碰撞。移動(dòng)機(jī)器人運(yùn)動(dòng)路徑上的每一點(diǎn)所受的合力等于該點(diǎn)所受目標(biāo)點(diǎn)的引力和障礙物的斥力之和，在合力的作用下移動(dòng)機(jī)器人從起始位置出發(fā)，避開障礙物到達(dá)目標(biāo)位置。因?yàn)楸疚牡难芯炕谖粗h(huán)境，障礙物位置無法確定，所以只考慮引入引力場(chǎng)，提出如下引力場(chǎng)函數(shù)：

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

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

2 改進(jìn)Q-learning算法

2.1 Q值初始化

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 實(shí)驗(yàn)參數(shù)

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

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

對(duì)于4種算法獎(jiǎng)勵(lì)函數(shù)設(shè)置為：

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

4 結(jié)語

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