基于改進Q學(xué)習(xí)算法的“貨到人”系統(tǒng)AGV路徑規(guī)劃

張祥來，江尚容，羅 芹

（哈爾濱商業(yè)大學(xué)管理學(xué)院，哈爾濱 150000）

0 引言

AGV的一個重要特征是能夠在復(fù)雜多變的倉庫環(huán)境下進行路徑規(guī)劃，因此路徑規(guī)劃一直是AGV研究的熱點領(lǐng)域。AGV路徑規(guī)劃指的是在搜索區(qū)域內(nèi)給出合理的目標(biāo)函數(shù)，以最低的時間或路程為代價，使其能夠找到一條從出發(fā)點到目的地的可行路徑。常用的路徑規(guī)劃方法有A*算法、人工勢場法、遺傳算法、粒子群算法、柵格法等。隨著智能倉儲的不斷發(fā)展，以上算法在AGV路徑規(guī)劃上的局限性逐步體現(xiàn)，容易出現(xiàn)陷入局部最優(yōu)解以及難以解決復(fù)雜倉庫環(huán)境的問題。

作為機器學(xué)習(xí)的主流算法之一，強化學(xué)習(xí)能夠用來描述和解決智能體在探索環(huán)境的過程中如何學(xué)習(xí)和優(yōu)化策略的問題。不同于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)，強化學(xué)習(xí)通過主動試錯并自我完善的過程來適應(yīng)環(huán)境。隨著對強化學(xué)習(xí)研究的深入，部分學(xué)者也將強化學(xué)習(xí)方法應(yīng)用于路徑規(guī)劃中。由于強化學(xué)習(xí)的某些特點，使其在路徑規(guī)劃方面存在著收斂速度慢和維數(shù)災(zāi)難等缺點。

在TD算法的基礎(chǔ)上，1992年Watkins提出了Q學(xué)習(xí)算法，并得到了廣泛的應(yīng)用，成為目前AGV路徑規(guī)劃最有效的算法之一。由于Q學(xué)習(xí)存在探索效率低下的問題，對于Q學(xué)習(xí)的改進也是學(xué)者研究的熱點。總結(jié)開來，改進思路大致分為四類：如Li等引入啟發(fā)式搜索策略加快Q學(xué)習(xí)的收斂速度；葛媛等學(xué)者提出了一種基于RBF網(wǎng)絡(luò)的Q學(xué)習(xí)算法來加強對未知動態(tài)環(huán)境的適應(yīng)性；劉志榮通過利用雙層神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練，進行分層強化學(xué)習(xí)以此加快收斂進程；樸松昊等為提高路徑規(guī)劃的實時性將遺傳算法的初步全局最優(yōu)路徑與Q學(xué)習(xí)的避障功能進行結(jié)合。

本文針對Q學(xué)習(xí)“探索-利用”的困境，引入動態(tài)搜索因子來平衡“探索-利用”之間的關(guān)系。基本思想是依據(jù)AGV對環(huán)境的熟悉程度，動態(tài)改變AGV動作選擇策略，改善由于探索和利用之間不平衡關(guān)系所導(dǎo)致的收斂速度慢、容易陷入局部最優(yōu)解的問題。

1 貨到人系統(tǒng)機器人路徑規(guī)劃問題描述

隨著電子商務(wù)的繁榮，傳統(tǒng)的“摘果式”“播種式”等人至貨的揀選模式在網(wǎng)絡(luò)經(jīng)濟時代“小批量、多批次、多品種”為特征的訂單背景下，會導(dǎo)致揀選效率底下、人工成本升高、容易揀錯貨等情況，因此，“貨到人”揀選系統(tǒng)應(yīng)運而生并蓬勃發(fā)展。該系統(tǒng)的流程是貨架可移動并有多個貨格，AGV根據(jù)指令從停車點移動到貨架底部，將載有目標(biāo)貨物的貨架運送到揀選臺，揀選人員根據(jù)計算機提示完成揀貨過程。如圖1為一貨到人揀選系統(tǒng)。

圖1 貨到人揀選系統(tǒng)

2 Q學(xué)習(xí)原理

Q學(xué)習(xí)是一種基于值函數(shù)的無模型強化學(xué)習(xí)算法，采用馬爾可夫決策過程的形式，其本質(zhì)是構(gòu)建一個由狀態(tài)到行為的函數(shù)Q（s，a）。在進行路徑規(guī)劃時，Q學(xué)習(xí)算法對AGV進行初始化操作，建立矩陣R和矩陣Q分別存儲AGV每步探索的即時獎勵和Q值函數(shù)值。通過AGV隨機選擇下一步路徑動作a并計算相應(yīng)的Q值函數(shù)值，來進行Q值表的更新操作。在該算法下，每個Q(s,a)都由對應(yīng)的一個Q值，即為得到的累計回報。最終根據(jù)得到的最大累計回報，選擇相對應(yīng)的AGV行走動作。

Q值的計更新公式

距離計算采用曼哈頓距離測算法，AGV小車只能上下左右運動，排除對角線行走：

其中α和γ為學(xué)習(xí)率和折扣因子，都在［0，1］內(nèi)取值；S表示AGV當(dāng)前所處狀態(tài)；a代表智能體做出的有效動作。R（S，a）表示智能體在狀態(tài)下執(zhí)行動作獲得的即時獎勵；Q表示AGV對應(yīng)狀態(tài)下采取行動a的Q值。更新到最終狀態(tài)稱為一次學(xué)習(xí)，智能體不斷進行學(xué)習(xí)Q表收斂或者達到最大學(xué)習(xí)次數(shù)，此時Q表中每一狀態(tài)下智能體對應(yīng)的動作即認為最優(yōu)解。

單智能體的Q學(xué)習(xí)算法的最優(yōu)策略是選擇最大回報值的動作，結(jié)合kiva倉庫的背景環(huán)境，本文將AGV視為智能體，AGV在倉庫節(jié)點中的位置作為狀態(tài)S。傳統(tǒng)Q學(xué)習(xí)在動作選擇的策略上，大多采用Greedy策略，在每一次迭代中以的概率選擇隨機動作；以1-選擇最大獎勵值動作，這使其在AGV路徑規(guī)劃的過程中會容易出現(xiàn)陷入局部最優(yōu)解的問題，Q學(xué)習(xí)的運行模型如圖2所示。

圖2 Q學(xué)習(xí)運行模式

3 改進的Q學(xué)習(xí)原理

作為機器學(xué)習(xí)的重要分支，Q學(xué)習(xí)無需任何環(huán)境先驗知識，能夠以一種探索并不斷試錯的方式來了解陌生環(huán)境，有令人滿意的魯棒性和自適應(yīng)性，這一過程得益于探索。很多時候我們認為滿意解即最優(yōu)解，這在以kiva倉庫為代表的現(xiàn)代化智能倉庫中更加適用，在AGV路徑規(guī)劃的過程中，一味的追求最優(yōu)解，不僅對AGV運行效率的提升作用不大，更會使學(xué)習(xí)的效率大幅度降低，因而沒有太大的意義。因此智能體會根據(jù)學(xué)習(xí)到的策略決策，選擇當(dāng)下智能體認為能獲取“最大獎勵值”的動作，這一過程稱之為利用。

探索和利用的實質(zhì)在于AGV動作的選擇，從表面上看前者強調(diào)隨機選擇，后者側(cè)重目的性而相互矛盾，實則不然，提升Q學(xué)習(xí)效率的關(guān)鍵是兩者間的平衡關(guān)系，這種關(guān)系在傳統(tǒng)Q學(xué)習(xí)中是不變的，寬泛的探索使算法難于收斂，做無用功；過度利用使AGV容易陷入局部最優(yōu)解。所以從該角度出發(fā)，傳統(tǒng)Q學(xué)習(xí)存在的問題本質(zhì)是探索和利用不平衡所導(dǎo)致。

在算法開始執(zhí)行階段，AGV對陌生倉庫環(huán)境并不了解，此時需要進行探索以不斷試錯的方式來隨機選擇動作以了解環(huán)境信息，隨著AGV行走路程的增加，對環(huán)境的了解程度也逐步提升，AGV應(yīng)減少對環(huán)境的學(xué)習(xí)，轉(zhuǎn)而利用學(xué)到的策略獲取最大回報。即，隨著AGV對環(huán)境信息的掌握，探索過程應(yīng)該由開始的主導(dǎo)地位逐步下降，策略取而代之，來成為AGV動作選擇的主要依據(jù)。根據(jù)此思路，本文將傳統(tǒng)Q學(xué)習(xí)中統(tǒng)靜態(tài)學(xué)習(xí)率和貪婪因子轉(zhuǎn)為動態(tài)，以提高Q學(xué)習(xí)在AGV路徑規(guī)劃中的性能，具體進行如下兩方面改革。

通過引入反正弦函數(shù)，作為貪婪因子函數(shù)變化的主體，具體改革如下：

其中n代表第n次迭代。

學(xué)習(xí)率決定了AGV在探索倉庫過程中，每次執(zhí)行動作后從倉庫中了解信息的多少，在一定程度上影響著Q值。即當(dāng)AGV對環(huán)境進行探索時需較高的學(xué)習(xí)率。而在利用已學(xué)習(xí)到的策略時較低的學(xué)習(xí)率能避免AGV陷入局部最優(yōu)解，故學(xué)習(xí)率α進行如下改進：

改進QL的學(xué)習(xí)步驟如下：

（1）搭建kiva倉庫的環(huán)境，據(jù)此建立Q表，并初始化參數(shù)。

（2）AGV從打包臺出發(fā)，對倉庫環(huán)境進行探索，起點位置對應(yīng)初始狀態(tài)。

（3）QL根據(jù)AGV當(dāng)前所處的狀態(tài)s，依據(jù)式（3）中貪婪因子的大小來決定AGV的動作a。

（4）AGV移動后，計算獎勵值Q（s，a），更新Q表。

（5）更新AGV的狀態(tài)S。

（6）判斷AGV是否到達終點或者是否達到AGV最大行駛步長，若沒有，返回步驟（3），若滿足條件，退出循環(huán)，進入步驟（7）。

（7）判斷Q表是否收斂或已達到最大迭代次數(shù)，若是，說明AGV已經(jīng)找到最優(yōu)路徑，輸出最終Q表。否則說明AGV此次尋找失敗，回到步驟（2）繼續(xù)進行迭代。

4 實例仿真與分析

4.1 實例描述

為驗證本文提出的改進Q學(xué)習(xí)算法在尋找AGV最優(yōu)路徑上的有效性，搭建如圖3所示的26×26的柵格地圖作為kiva倉庫仿真環(huán)境，以此作為AGV的運行環(huán)境，并且通過改變倉庫布局，以及增加障礙物來增加仿真的真實性。黑色的每個柵格代表一個可移動的貨架，圓形區(qū)域為停車點，三角形區(qū)域代表揀選臺為AGV運行的終點區(qū)域。

圖3 倉庫仿真環(huán)境

表1 倉庫仿真環(huán)境參數(shù)

為檢驗改進后的Q學(xué)習(xí)對單車路徑規(guī)劃的效果，忽略商品的儲位以及其它因素。AGV在倉庫中所處的坐標(biāo)位置對應(yīng)Q表里的不同狀態(tài)，AGV在動作選擇時，有上、下、左、右四個可選項，因此對應(yīng)本倉庫的Q表容量為26×26×4。倉庫中會有貨架與障礙物，其中障礙物不可通行，在沒有載貨之前，AGV可以在貨架底部穿梭，運貨之后貨架也視為障礙物。當(dāng)AGV選擇的下一動作會導(dǎo)致碰到障礙物或者出界時會停留在該狀態(tài)，不然就進入下一狀態(tài)。AGV在接收到揀選任務(wù)后，從停車臺出發(fā)，前往目標(biāo)貨架所在坐標(biāo)點，并將其送至揀選臺，完成后將貨架送至原位置，即視為完成任務(wù)。此后根據(jù)任務(wù)需求AGV可以返回停車臺，或者前往下一目標(biāo)貨架。

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

表2為最終Q表的部分，本次實驗通過更改倉庫布局并引入障礙物進一步驗證仿真結(jié)果的合理性。圖4為實驗所用的三種實驗環(huán)境，圖5為在環(huán)境3下兩種算法路徑規(guī)劃的結(jié)果。從圖中結(jié)果可知，兩者都能成功找到AGV的最短行駛路徑，并且進行多次重復(fù)實驗發(fā)現(xiàn)算法改進前后所得的最優(yōu)路徑在運行距離上并沒有差距。

表2 改進Q學(xué)習(xí)的最終Q表（部分）

圖4 其余兩種不同布局的倉庫環(huán)境

圖5 環(huán)境3下兩種算法最優(yōu)路徑對比

利用改進Q學(xué)習(xí)和傳統(tǒng)Q學(xué)習(xí)尋找最優(yōu)路徑時，會出現(xiàn)AGV所行駛路徑重疊以及兩者最優(yōu)路徑相同的情況，為更加直觀呈現(xiàn)實驗結(jié)果，選擇利用改進前后的算法所得不同且無重疊的最優(yōu)路徑進行繪制。對比結(jié)果圖可知，AGV行走到相應(yīng)貨架后載到指定的打包臺的路徑均為最短路徑。為進一步比較兩者的優(yōu)劣，本文選用算法的收斂時間與迭代次數(shù)來進行比較，如圖6所示。

圖6 算法時間

部分迭代次數(shù)算法的收斂時間如表3所示。

表3 部分迭代次數(shù)算法的收斂時間

圖7 算法效率提升圖

結(jié)合數(shù)據(jù)與圖進行分析，相較于傳統(tǒng)Q學(xué)習(xí)算法，可以發(fā)現(xiàn)改進后的Q學(xué)習(xí)算法收斂時間更快，平均運行效率提升約為28%，其中最低提升值為18%，最高提升40%，并且隨著最高迭代次數(shù)的不斷增加，改進后的Q學(xué)習(xí)效率優(yōu)勢更加明顯。可以發(fā)現(xiàn)，在最大迭代次數(shù)超過2500次時，效率提升均超過35%。將效率提升值視為一連續(xù)函數(shù)，可以發(fā)現(xiàn)效率提升函數(shù)大致呈現(xiàn)先減后增的趨勢。導(dǎo)致此現(xiàn)象的原因是AGV迭代次數(shù)較少時，對環(huán)境信息的掌握就越少，學(xué)習(xí)到的策略對算法的影響較低，此時主要目標(biāo)是對環(huán)境進行探索。隨著迭代次數(shù)增加，探索影響因素降低，此時策略依舊不成熟，而由于采用反三角貪婪策略，探索下降較快，導(dǎo)致效率的提升有所下降，但其運行效率仍然比傳統(tǒng)Q學(xué)習(xí)高約20%，迭代次數(shù)越高，策略影響越大，此時過高的探索也是導(dǎo)致傳統(tǒng)Q學(xué)習(xí)收斂速度慢的原因。

5 結(jié)語

本文針對單AGV在現(xiàn)代化智能倉庫中的路徑規(guī)劃問題展開研究，就傳統(tǒng)Q學(xué)習(xí)存在的收斂速度慢、易陷入局部最優(yōu)解的原因進行探討，從改變探索和利用兩者的關(guān)系為導(dǎo)向，根據(jù)AGV對倉庫環(huán)境的了解程度，引入反正弦貪婪策略動態(tài)調(diào)整AGV對倉庫環(huán)境的探索和利用兩種狀態(tài)，在保證最優(yōu)路徑的前提下以此提高算法的收斂速度。反正弦貪婪策略根據(jù)迭代的次數(shù)來調(diào)整探索因子，動態(tài)貪婪因子能夠避免局部搜索困境，并且利用柵格地圖對改進后的Q學(xué)習(xí)算法較傳統(tǒng)Q學(xué)習(xí)進行了驗證，在保證最優(yōu)路徑的前提下使收斂速度與運行效率提高約28%。