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

張祥來(lái)，江尚容，羅 芹

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

0 引言

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

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

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

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

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

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

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

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

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

Q值的計(jì)更新公式

距離計(jì)算采用曼哈頓距離測(cè)算法，AGV小車(chē)只能上下左右運(yùn)動(dòng)，排除對(duì)角線行走：

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

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

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

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

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

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

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

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

其中n代表第n次迭代。

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

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

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

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

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

（4）AGV移動(dòng)后，計(jì)算獎(jiǎng)勵(lì)值Q（s，a），更新Q表。

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

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

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

4 實(shí)例仿真與分析

4.1 實(shí)例描述

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

圖3 倉(cāng)庫(kù)仿真環(huán)境

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

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

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

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

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

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

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

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

圖6 算法時(shí)間

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

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

圖7 算法效率提升圖

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

5 結(jié)語(yǔ)

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