改進(jìn)強(qiáng)化學(xué)習(xí)算法在AGV路徑規(guī)劃中的應(yīng)用研究

韓 召 ，韓宏飛，于會(huì)敏 ，王延忠

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

0 引言

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

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

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

1 Q-learning算法原理

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

α)-Q(St,At))

(1)

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

Q-learning算法的Q值通過(guò)一個(gè)查找表來(lái)存儲(chǔ)Q值相對(duì)應(yīng)的每個(gè)狀態(tài)。從公式(1)中可以得知，想要得到對(duì)于狀態(tài)St對(duì)應(yīng)的最終Q值，首先要使?fàn)顟B(tài)St+1對(duì)應(yīng)的maxQ(St+1,At)=Qt+1恒定，否則，上一個(gè)時(shí)刻狀態(tài)所對(duì)應(yīng)的Q值會(huì)受到下一個(gè)狀態(tài)Q值的影響，因?yàn)?，?qiáng)化學(xué)習(xí)算法是一個(gè)整體的回溯過(guò)程。假設(shè)St+1狀態(tài)是穩(wěn)定的，那么Qt+1值恒定，為了使Q(St,At)所對(duì)應(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取足夠大的時(shí)候，可以得到如下結(jié)果：

(1-α)n→0,

=γ+γQt+1

(3)

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

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

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

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

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

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

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

(4)

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

(5)

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

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

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

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

圖1 物流AGV小車模型

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

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

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

圖3 路徑規(guī)劃

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

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

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

4 物流AGV小車實(shí)物實(shí)驗(yàn)

4.1 物流AGV實(shí)物

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

圖5 AGV小車實(shí)物前后照

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結(jié)

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