王 健，趙亞川，趙忠英 ，張平陸

（1.沈陽(yáng)新松機(jī)器人自動(dòng)化股份有限公司 特種機(jī)器人BG，沈陽(yáng) 110169.2.沈陽(yáng)科技學(xué)院 機(jī)械與交通工程系，沈陽(yáng) 110167）

路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航的重要組成部分，其目標(biāo)是在復(fù)雜環(huán)境下能夠?qū)ふ乙粭l從起點(diǎn)到終點(diǎn)的無(wú)碰撞路徑。路徑規(guī)劃的優(yōu)劣直接影響移動(dòng)機(jī)器人的運(yùn)動(dòng)效率、機(jī)器損耗和工作效率?；趶?qiáng)化學(xué)習(xí)的智能移動(dòng)機(jī)器人的導(dǎo)航和避障正在成為一個(gè)重要的研究方向。與其它機(jī)器學(xué)習(xí)方法不同，增強(qiáng)學(xué)習(xí)方法無(wú)需監(jiān)督信號(hào)，通過(guò)智能體與環(huán)境之間的信息交互進(jìn)行“試錯(cuò)”，以極大化評(píng)價(jià)反饋信號(hào)為目標(biāo)，通過(guò)學(xué)習(xí)得到最優(yōu)或次優(yōu)的搜索策略。

目前強(qiáng)化學(xué)習(xí)已經(jīng)引起國(guó)內(nèi)外機(jī)器學(xué)習(xí)領(lǐng)域?qū)W者的廣泛關(guān)注。文獻(xiàn)[1]所提出的基于獎(jiǎng)賞的強(qiáng)化學(xué)習(xí)方法具有較快的收斂速度；文獻(xiàn)[2]深入研究基于BP神經(jīng)網(wǎng)絡(luò)的Q-learning，實(shí)現(xiàn)移動(dòng)機(jī)器人環(huán)境下的自主導(dǎo)航；文獻(xiàn)[3]將強(qiáng)化學(xué)習(xí)方法用于機(jī)器人的任務(wù)規(guī)劃和調(diào)度；文獻(xiàn)[4]以神經(jīng)網(wǎng)絡(luò)擬合Q-learning中的Q函數(shù)，再用經(jīng)驗(yàn)回放和目標(biāo)網(wǎng)絡(luò)方法改善Q-learning收斂穩(wěn)定性；文獻(xiàn)[5]基于模糊邏輯的路徑規(guī)劃方法，利用狀態(tài)空間與動(dòng)作空間映射關(guān)系，解決了人工勢(shì)場(chǎng)法容易陷入局部極小問(wèn)題。

強(qiáng)化學(xué)習(xí)在未知環(huán)境下求解具有較少先驗(yàn)信息的問(wèn)題具有巨大優(yōu)勢(shì)，是目前機(jī)器學(xué)習(xí)中富有挑戰(zhàn)性和廣泛應(yīng)用前景的研究領(lǐng)域之一[6-8]。

在移動(dòng)機(jī)器人路徑規(guī)劃相關(guān)應(yīng)用中，傳統(tǒng)的基于Q（λ）-learning探索方法存在由于探索不平衡致使無(wú)法找到最優(yōu)解的問(wèn)題。故在此通過(guò)改進(jìn)探索方法，提出基于成功率動(dòng)態(tài)調(diào)整探索因子的探索方法。

1 基于Q（λ）-learning的改進(jìn)探索方法

Q-learning 是以狀態(tài)-動(dòng)作對(duì)應(yīng)的 Q（s，a）為估計(jì)函數(shù)，逐漸減小相鄰狀態(tài)間Q值估計(jì)的差異達(dá)到收斂條件。更新公式為

引入跡的思想，其更新公式為

誤差項(xiàng)為

更新動(dòng)作公式為

解決探索利用平衡問(wèn)題常用的方法是ε-貪心策略。這種方法探索環(huán)境時(shí)，隨著訓(xùn)練時(shí)間的增加而減小探索因子。搜索函數(shù)為

式中：σ為0～1之間的隨機(jī)數(shù)；ε為探索因子，為0～1之間的數(shù)。傳統(tǒng)調(diào)整探索因子的方法過(guò)多利用環(huán)境快速收斂到對(duì)應(yīng)解，但由于探索不夠充分，往往很難得到最優(yōu)解。在此，采用基于成功率的方法動(dòng)態(tài)調(diào)整探索因子ε，適時(shí)的鼓勵(lì)探索，使移動(dòng)機(jī)器人對(duì)環(huán)境探索的更加完全，找到更多解，從而找到最優(yōu)解。其算法流程如圖1所示。

隨著訓(xùn)練次數(shù)的增加，移動(dòng)機(jī)器人找到目標(biāo)路徑成功率逐漸增加，此時(shí)判斷路徑解數(shù)量。當(dāng)?shù)陀谧钌俾窂浇鈹?shù)量時(shí)，增大探索因子，以尋找更多解；當(dāng)高于最多路徑解時(shí)，說(shuō)明移動(dòng)機(jī)器人對(duì)環(huán)境熟悉程度已經(jīng)很高，此時(shí)逐漸降低探索因子，直至降為0。

圖1 動(dòng)態(tài)調(diào)整探索因子算法流程Fig.1 Dynamic exploring factor algorithm flow chart

基于Q（λ）-learning的改進(jìn)探索方法，具體實(shí)現(xiàn)步驟如下：

步驟1 初始化，并獲取當(dāng)前狀態(tài)s；

步驟2 進(jìn)行第i次迭代計(jì)算，最大迭代次數(shù)為n，根據(jù)圖1所示流程更新探索因子ε；

步驟3 生成隨機(jī)數(shù)σ，執(zhí)行搜索策略π（s），如式（5）所示；

步驟4 執(zhí)行動(dòng)作a，得到獎(jiǎng)勵(lì)r，轉(zhuǎn)移到新?tīng)顟B(tài) s′；

步驟5 根據(jù)s′是否為目標(biāo)狀態(tài)更新成功率Suc，并根據(jù)路徑解是否為新解，更新路徑解數(shù)量Path；

步驟6 判斷s′是否為終止?fàn)顟B(tài)，如果是則跳到步驟2進(jìn)行下一次迭代（i=i+1），如果不是則跳到步驟7；

步驟7 根據(jù)式（3），計(jì)算誤差；

步驟8 根據(jù)式（2），更新動(dòng)作狀態(tài)跡，并更新其他動(dòng)作狀態(tài)跡；

步驟9 根據(jù)式（4），更新動(dòng)作值函數(shù)；

步驟10 s←s′，跳到步驟3搜索下一個(gè)狀態(tài)。

2 仿真試驗(yàn)與結(jié)果分析

通過(guò)仿真試驗(yàn)來(lái)驗(yàn)證改進(jìn)探索方法的有效性。試驗(yàn)環(huán)境采用10×10柵格地圖，如圖2所示。由圖可見(jiàn)，以圖左上角為移動(dòng)機(jī)器人起點(diǎn)，右下角為目標(biāo)，移動(dòng)機(jī)器人無(wú)法穿越黑色柵格障礙物。

圖2 10×10柵格地圖Fig.2 10×10 grid map

移動(dòng)機(jī)器人動(dòng)作集A包括上移、下移、左移、右移4個(gè)動(dòng)作。狀態(tài)集用1～100表示，障礙物和目標(biāo)狀態(tài)為終止?fàn)顟B(tài)。當(dāng)移動(dòng)機(jī)器人移動(dòng)到終止?fàn)顟B(tài)，本次訓(xùn)練循環(huán)結(jié)束，重新進(jìn)行下一次訓(xùn)練。

將本文方法與典型的ε-decreasing探索方法進(jìn)行仿真對(duì)比試驗(yàn)，驗(yàn)證該方法的有效性。ε-decreasing探索方法采用式（6）更新探索因子，即

式中：Vinit為探索因子初始值；i為迭代學(xué)習(xí)次數(shù)；S為步長(zhǎng)。

Q（λ）-learning算法中幾個(gè)重要的參數(shù)會(huì)直接影響收斂速度。仿真試驗(yàn)中，折扣因子γ初始化為0.8，學(xué)習(xí)速率α初始化為0.05。在此，探索因子ε初始化為0.5，ε-decreasing方法初始化為1，最大探索步數(shù)初始化為100。當(dāng)搜索步數(shù)超過(guò)最大步數(shù)時(shí)，仍未到達(dá)終止?fàn)顟B(tài)，則認(rèn)為此次訓(xùn)練失敗，重新進(jìn)入下一次訓(xùn)練。

獎(jiǎng)勵(lì)函數(shù)設(shè)置：當(dāng)移動(dòng)機(jī)器人到達(dá)目標(biāo)狀態(tài)時(shí)獎(jiǎng)勵(lì)1，當(dāng)碰到障礙物得到-1的懲罰，到達(dá)其余狀態(tài)時(shí)得到-0.05的懲罰，用于加快向目標(biāo)狀態(tài)移動(dòng)。

ε-decreasing方法收斂曲線如圖3所示，約在訓(xùn)練13000次時(shí)收斂；基于成功率搜索方法收斂曲線如圖4所示，約在訓(xùn)練32000次時(shí)收斂。兩者收斂時(shí)間差別較大，是因?yàn)楫?dāng)ε-decreasing搜索方法找到一條最優(yōu)策略時(shí)，有很大的幾率不去試探新的最優(yōu)策略，很快地達(dá)到收斂狀態(tài)，本文方法會(huì)根據(jù)最優(yōu)解的搜索情況適當(dāng)增大探索因子，犧牲收斂時(shí)間來(lái)尋找更多最優(yōu)解。

圖3 ε-decreasing方法收斂曲線Fig.3 Convergence curve based onε-decreasing search method

圖4 基于成功率搜索方法收斂曲線Fig.4 Convergence curve based on success rate search method

2種搜索方法訓(xùn)練完成的最優(yōu)策略分別如圖5和圖6所示。由圖5可見(jiàn)，ε-decreasing搜索策略中，一些狀態(tài)并未得到最優(yōu)解（陰影表示），以圖5中狀態(tài)83和87為例，最優(yōu)解應(yīng)分別為向右和向下，由于訓(xùn)練過(guò)程中隨著探索因子不斷減小，不再進(jìn)行新的探索，因此并未得到最優(yōu)解。由圖6可見(jiàn)，基于成功率的搜索策略，完全接近于最優(yōu)策略。

圖5 基于ε-decreasing方法收斂策略Fig.5 Search strategy based onε-decreasing method

圖6 基于成功率搜索方法收斂策略Fig.6 Search strategy based on success rate search method

統(tǒng)計(jì)移動(dòng)機(jī)器人在地圖所有狀態(tài)下到達(dá)目標(biāo)狀態(tài)的平均步數(shù)見(jiàn)表1。其中，2號(hào)～5號(hào)試驗(yàn)為使用同樣的方法，另外生成的4個(gè)障礙物分布不同的柵格地圖，采用同樣的參數(shù)完成訓(xùn)練。

表1 平均步數(shù)的對(duì)比Tab.1 Comparison of average step

移動(dòng)機(jī)器人移動(dòng)的平均步數(shù)越少，說(shuō)明策略越優(yōu)。由表1可知，本文搜索策略在4次試驗(yàn)中，平均步數(shù)均明顯低于ε-decreasing策略。

3 結(jié)語(yǔ)

本文提出了一種基于成功率的探索方法，采用Q（λ）-learning算法對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃，引入成功率的改進(jìn)搜索方法，解決了強(qiáng)化學(xué)習(xí)中存在的探索利用平衡問(wèn)題。最后通過(guò)仿真實(shí)驗(yàn)將改進(jìn)搜索方法與經(jīng)典ε-decreasing搜索方法作對(duì)比，驗(yàn)證了該方法的有效性。