韓 召 ，韓宏飛，于會敏 ，王延忠

(1.遼寧科技學(xué)院 電氣與自動化學(xué)院,遼寧 本溪 117004；2.株洲中車時代電氣股份有限公司，湖南 株洲 412000；3.北京航空航天大學(xué) 機械工程及自動化學(xué)院，北京 100191)

0 引言

物流AGV小車為了高效地完成運輸任務(wù)，需要從起點到目標(biāo)點規(guī)劃出一條最短且安全的最優(yōu)路徑，這條路徑是所有可到達(dá)的路徑中長度最短、耗時最少的路徑。如果物流小車的路徑規(guī)劃得不理想，將影響整個車間的工作節(jié)拍和車間調(diào)度效率。

目前，物流AGV小車的路徑規(guī)劃的算法分全局路徑規(guī)劃和局部路徑規(guī)劃，在大多數(shù)情況下，需要2種路徑規(guī)劃的算法同時使用。在局部路徑規(guī)劃算法中，應(yīng)用比較多的有人工勢場算法[1]、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、模糊邏輯法、強化學(xué)習(xí)算法[2]等。強化學(xué)習(xí)算法是機器學(xué)習(xí)方法的一種，其在物流AGV小車的路徑規(guī)劃中得到越來越多的應(yīng)用。強化學(xué)習(xí)是通過對環(huán)境信息的獲取，不斷與環(huán)境進(jìn)行交互的在線學(xué)習(xí)方法[3]。近年來，越來越多的學(xué)者將強化學(xué)習(xí)算法應(yīng)用于移動機器人的路徑規(guī)劃中，其中應(yīng)用非常多的是強化學(xué)習(xí)算法中的Q-learning算法，傳統(tǒng)的Q-learning算法在程序初始化過程中將Q值設(shè)置成隨機值或者0，這導(dǎo)致AGV小車在起始階段的搜索范圍盲目且無效迭代次數(shù)過多；其次，傳統(tǒng)的Q-learning算法在智能體的動作選擇時，采用的是ε探索策略，如果探索因子ε的值選取太大，會導(dǎo)致AGV小車搜索環(huán)境太大而不容易收斂，如果ε的值選取太小，則會導(dǎo)致AGV小車搜索環(huán)境不夠而得不到次優(yōu)解，這最終導(dǎo)致智能小車不能很好地平衡探索和利用之間的關(guān)系[4]。

文章針對強化學(xué)習(xí)中的Q-learning算法中存在的收斂速度過慢、探索與利用的沖突問題，提出了探索因子ε根據(jù)不同階段動態(tài)調(diào)整方法對路徑規(guī)劃算法進(jìn)行優(yōu)化，最后在仿真平臺及實體AGV小車上進(jìn)行實驗，證明這種改進(jìn)的算法可行且有效。

1 Q-learning算法原理

強化學(xué)習(xí)的算法主要有蒙特卡洛算法[5]、時間差分(TD)算法、Q-learning與SARSA學(xué)習(xí)算法[6]及Dyna學(xué)習(xí)算法[7]。其中的時間差分(TD)算法的思想是解決時間信度分配問題，它借鑒了蒙特卡洛和動態(tài)規(guī)劃的思想，相比于蒙特卡洛算法具有與模型無關(guān)的優(yōu)點，且具有更加充分利用環(huán)境的經(jīng)驗[7]。Q-learning算法是在時間差分(TD)算法的基礎(chǔ)上提出的通過狀態(tài)-動作對值函數(shù)Q(S,A)來進(jìn)行值函數(shù)迭代的算法，這是一種與模型無關(guān)的迭代學(xué)習(xí)過程，Q-learning算法的迭代公式如下：

α)-Q(St,At))

(1)

式中，St是系統(tǒng)環(huán)境狀態(tài)集；At是智能體可采取的動作集；α是學(xué)習(xí)率，其取值是小于1的正數(shù)；γ是折扣率，其取值范圍是0～1。Rt+1是智能體在狀態(tài)St做出的動作At后的獎勵值，Q(St,At)稱為動作-值函數(shù)，即Q函數(shù)。在Q-learning算法中首先建立一個Q值的表，智能體不斷與環(huán)境進(jìn)行交互，并得到反饋，通過對智能體的狀態(tài)-動作的獎賞值來進(jìn)行迭代修改查抄表，從而達(dá)到與環(huán)境交互迭代篩選，最終使智能體的動作集區(qū)趨近最優(yōu)動作解。

Q-learning算法的Q值通過一個查找表來存儲Q值相對應(yīng)的每個狀態(tài)。從公式(1)中可以得知，想要得到對于狀態(tài)St對應(yīng)的最終Q值，首先要使?fàn)顟B(tài)St+1對應(yīng)的maxQ(St+1,At)=Qt+1恒定，否則，上一個時刻狀態(tài)所對應(yīng)的Q值會受到下一個狀態(tài)Q值的影響，因為，強化學(xué)習(xí)算法是一個整體的回溯過程。假設(shè)St+1狀態(tài)是穩(wěn)定的，那么Qt+1值恒定，為了使Q(St,At)所對應(yīng)的狀態(tài)穩(wěn)定，借助公式1進(jìn)行n次迭代后，其結(jié)果如下：

Q(St,At)=(1-α)nQt+[1-(1-α)n]

(γ+γQt+1)

(2)

其中，0<(1-α)<1,當(dāng)n取足夠大的時候，可以得到如下結(jié)果：

(1-α)n→0,

=γ+γQt+1

(3)

Q值不斷迭代更新，當(dāng)n趨近于正無窮時，Q(St,At)將以概率1收斂于最優(yōu)值，此時，再繼續(xù)更新迭代則不會改變Q值，此時Q(St,At)收斂。

在Q-learning算法中，不同的優(yōu)先級對應(yīng)不同的狀態(tài)，前一時刻狀態(tài)的收斂由后一時刻的條件決定，不同狀態(tài)的收斂優(yōu)先級也是有區(qū)別的，越接近最終狀態(tài)的Q值收斂越早，越遠(yuǎn)離目標(biāo)狀態(tài)的Q值收斂越遲，當(dāng)算法通過不斷的迭代，其訓(xùn)練次數(shù)達(dá)到最多的次數(shù)時，Q值會達(dá)到理想值，Q學(xué)習(xí)的查表值是Q學(xué)習(xí)的體現(xiàn)，這個查表值記錄了每個狀態(tài)對應(yīng)的Q值，這也是智能體采取動作后所獲得的回報函數(shù)[10]。當(dāng)環(huán)境滿足馬爾可夫性、回報函數(shù)r有界、折扣因子γ在0～1之間、Q函數(shù)用查找表來表示、狀態(tài)-動作對Q(S,A)有可重復(fù)性且步長選取合適這些條件時，該算法收斂，這種算法是基于平均化取樣回報解決強化學(xué)習(xí)問題。

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

物流AGV小車在路徑規(guī)劃中使用強化學(xué)習(xí)算法來搜尋最優(yōu)路徑，機器人為了獲得更好的回報函數(shù)，需要執(zhí)行不同的動作來獲得更多的經(jīng)驗和信息，這就是探索與利用的平衡問題。太少的探索會阻礙系統(tǒng)收斂到最優(yōu)策略，太多的探索會影響收斂速度，為了解決這個問題，學(xué)者們在智能體的動作選擇策略中提出了ε探索策略，這種策略在選擇動作時，每次都選擇最大Q值函數(shù)的狀態(tài)-動作對，經(jīng)過不斷迭代與學(xué)習(xí)，最終找到全局最優(yōu)解。

在傳統(tǒng)Q-learning算法基于差分策略的動作選擇策略中，ε探索策略在一定程度上平衡了探索與利用的關(guān)系，但是由于它獎賞值最大的方法是利用當(dāng)前的知識，它通常智能得到一個次優(yōu)結(jié)果，系統(tǒng)就容易陷入局部最優(yōu)解中。ε探索策略引入一個概率值ε，智能體AGV小車每次都以ε的概率在動作集合中隨機選擇動作，最優(yōu)和最差動作都以同樣的概率被選中，這樣就會導(dǎo)致整個過程的收斂速度放慢，且最后動作選擇結(jié)果也會有波動，為了解決這個問題，文章在研究幾種常用的動作策略方法的基礎(chǔ)上，提出一種改進(jìn)的探索因子動態(tài)調(diào)整策略，該算法流程偽代碼如表1所示。

表1 基于改進(jìn)的強化學(xué)習(xí)算法

基于改進(jìn)強化學(xué)習(xí)Q-learning算法中的探索因子ε取值如下：

(4)

其中：tanh函數(shù)的具體形式如下：

(5)

其中：e是自然對數(shù)的底，當(dāng)自變量t>0時，0

在強化學(xué)習(xí)算法起始階段，由于算法不收斂，Stdn的值較大，智能體AGV以εmax的概率進(jìn)行隨機動作的選取，隨著算法的運行，Stdn的值減小，使得ε的取值在εmin和εmax之間。Stdn的值越大，說明迭代次數(shù)之間的步數(shù)差別越大，環(huán)境越需要探索，ε的取值就會越大；而Stdn的值較小時，強化學(xué)習(xí)算法趨于收斂，ε值穩(wěn)定在εmin。通過以上分析可以得出，這樣設(shè)計的探索因子動態(tài)調(diào)整策略可以在算法起始階段以更大的概率對環(huán)境進(jìn)行搜索，隨著算法的進(jìn)行，ε值逐漸減小并穩(wěn)定在εmin，小車動作選擇策略逐漸趨于利用，這樣就會更好地解決探索和利用之間的矛盾。

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

文章的物流AGV小車的模型是通過URDF(Unified Robot Description Format)文件搭建的，在Gazebo仿真軟件中，URDF文件可以用XML格式進(jìn)行描述，機器人操作系統(tǒng)ROS也提供了URDF文件的C++解析器，文章所搭建的AGV小車的模型如圖1所示。

圖1 物流AGV小車模型

路徑規(guī)劃算法仿真環(huán)境是30 cm*30 cm的柵格地圖，設(shè)置的障礙與調(diào)研的某加工車間基本相同，圖中藍(lán)色區(qū)域是設(shè)置的障礙物，黃色區(qū)域是表示無障礙物，隨機設(shè)置的起始點(SP)和目標(biāo)點(EP)如圖中所示。文章搭建的環(huán)境二維地圖如圖2所示。

圖2 仿真空間中的環(huán)境二維地圖

文章借助MATLAB軟件對改進(jìn)后的強化學(xué)習(xí)算法進(jìn)行仿真實驗，在應(yīng)用改進(jìn)強化學(xué)習(xí)算法的小車路徑規(guī)劃中，使用探索因子動態(tài)調(diào)整策略的參數(shù)是：εmax=0.7和εmin=0.05，T=400，n=500,學(xué)習(xí)率α=0.05，折扣因子γ=0.9。在仿真空間中程序運行500次后，小車的第500次路徑規(guī)劃圖如圖3所示。圖中在起點SP和終點EP之間的連線就是小車最終的路徑規(guī)劃路線，從圖3中，我們也可以看出，此路徑是非常合理的。

圖3 路徑規(guī)劃

圖4是運行500次后，每100次小車路徑的長度和迭代次數(shù)變化趨勢圖，圖4中縱坐標(biāo)是表示AGV小車規(guī)劃的路徑步數(shù)，橫坐標(biāo)是小車算法的迭代次數(shù)，圖中的藍(lán)色曲線是小車第100次運行的長度與迭代次數(shù)曲線，紫色是第200次運行結(jié)果，黃色是第300次運行結(jié)果，橙色是第400次運行結(jié)果，綠色是第500次運行結(jié)果。

圖4 路徑規(guī)劃趨勢變化圖

由圖3和圖4可以看出，在采用基于動態(tài)因子調(diào)整策略的強化學(xué)習(xí)算法后，在仿真環(huán)境中，當(dāng)程序運行500次后，其自主規(guī)則路徑長度變短，且算法的迭代次數(shù)也在減少，算法的收斂速度較快且規(guī)劃路徑的結(jié)果穩(wěn)定。

4 物流AGV小車實物實驗

4.1 物流AGV實物

為了驗證算法的有效性，本課題的科研團(tuán)隊將仿真空間設(shè)計的AGV物流小車模型做成了實體，其實物的前后對照圖如圖5所示。

圖5 AGV小車實物前后照

物流AGV小車底盤上安裝2輪差速輪，下位機的主控芯片是STM32F103ZET6。上位機采用Intel QM77芯片組，集成Intel Celeron I5-2430M處理器，提供增強圖像處理性能和3D視頻性能。小車上安裝有激光雷達(dá)、防碰撞傳感器及慣性檢測單元IMU。小車最上層搭載有顯示器，顯示器上實時顯示規(guī)劃路徑及構(gòu)建的環(huán)境地圖信息。

4.2 加工車間環(huán)境地圖

文章所調(diào)研的加工車間實際尺寸是:120 m*50 m。實際車間的工作臺、數(shù)控機床、加工車床與仿真空間中的數(shù)量相同。圖6是調(diào)研某加工車間兩個部分的實際照片。

圖6 調(diào)研車間部分圖

4.3 改進(jìn)算法后小車路徑規(guī)劃

將改進(jìn)的基于強化學(xué)習(xí)的路徑規(guī)劃算法加載于物流AGV小車后，啟動程序，AGV小車的顯示屏上呈現(xiàn)出加載創(chuàng)建的地圖，地圖中物流AGV小車周圍有許多綠色箭頭，這些綠色箭頭就是通過概率定位的方法來確定AGV小車的位置，在綠色箭頭最密集的地方是AGV小車最有可能出現(xiàn)的位置。小車真實的起始位置與小車屏幕上RVIZ軟件中的起始位置對比如圖7所示。

圖7 小車導(dǎo)航起始位置

環(huán)境地圖中所有的障礙物都做了膨脹，藍(lán)色區(qū)域就是膨脹出來的安全區(qū)域，AGV小車應(yīng)盡量避免進(jìn)入藍(lán)色區(qū)域里。AGV小車首先會通過全局路徑規(guī)劃方法獲得最優(yōu)的全局路徑，在遇到障礙物后，小車會結(jié)合局部路徑規(guī)劃方法來避開障礙物。小車遇到障礙物時進(jìn)行避障規(guī)劃及小車顯示屏幕上RVIZ軟件顯示出來的小車路徑規(guī)劃如圖8所示。

小車到達(dá)終點后，小車按預(yù)定的位置準(zhǔn)確地停

圖8 物流小車自主避障路徑規(guī)劃

在了預(yù)設(shè)的目標(biāo)點上，小車到達(dá)終點時的實際位置及小車顯示屏上RVIZ軟件中的位置如圖9所示。

圖9 小車到達(dá)目標(biāo)點

物流AGV小車的整體規(guī)劃路徑如圖10所示，圖中紅色箭頭是設(shè)置目標(biāo)點的位置及方向，小車到目標(biāo)點之間的綠色線就是小車結(jié)合全局與局部路徑規(guī)劃得到的最優(yōu)路徑。

圖10 AGV小車路徑規(guī)劃

將改進(jìn)的基于強化學(xué)習(xí)的算法運用于實物AGV物流小車路徑規(guī)劃，經(jīng)運行后，可看出，小車的路徑規(guī)劃更合理，且小車的耗時更短，效果更穩(wěn)定。

5 總結(jié)

文章針對物流行業(yè)AGV小車的路徑規(guī)劃問題提供了解決方案，將強化學(xué)習(xí)算法應(yīng)用于小車的自主導(dǎo)航和避障控制中，并針對傳統(tǒng)的強化學(xué)習(xí)算法中的Q-learning算法進(jìn)行了改進(jìn)，為了提高傳統(tǒng)Q-learning算法中的收斂速度和收斂結(jié)果的穩(wěn)定性，文章提出了在動作選擇時，動態(tài)調(diào)整探索因子ε策略。仿真實驗表明算法的收斂速度和收斂結(jié)果的穩(wěn)定性明顯提升。