杜卓穎，李金禧，張祥來(lái)，朱 琳

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

1 引言

目前倉(cāng)儲(chǔ)內(nèi)的貨物流通開始更多的使用AGV智能小車作為載體，隨著自動(dòng)化水平的提高和成本的降低，現(xiàn)在多數(shù)使用的是“貨到人”揀選模式。在揀選過程中，系統(tǒng)內(nèi)的揀選人有固定站位，貨物通過AGV小車等載體自動(dòng)輸送到揀選人面前。這種模式不僅可以提高揀選和存儲(chǔ)的效率，還可以有效減低人工成本和勞動(dòng)強(qiáng)度[1]。因此，本文將在以“貨到人”揀選系統(tǒng)為背景的倉(cāng)儲(chǔ)中進(jìn)行仿真實(shí)驗(yàn)。

目前對(duì)單智能體的路徑規(guī)劃方法有很多：一是使用搜索算法,如姜濤，等[3]提出利用Dijkstra 算法提高路徑規(guī)劃中的定位精度問題，使機(jī)器人與障礙物之間距離最大化，使移動(dòng)機(jī)器人的運(yùn)動(dòng)軌跡具有較高的可執(zhí)行性，減少碰撞幾率，實(shí)現(xiàn)了小型移動(dòng)機(jī)器人在信號(hào)丟失情況下的自主返航；陳靖輝，等[4]基于A*算法，通過消除對(duì)稱路徑，減少擴(kuò)展節(jié)點(diǎn)的方法，提高搜索效率和算法性能；二是使用啟發(fā)式算法，如梁凱，等[5]基于蟻群算法進(jìn)行動(dòng)態(tài)路徑規(guī)劃時(shí)的缺陷，提出了結(jié)合狼群分配原則、局部搜索策略和兩步可行域搜索策略的改進(jìn)蟻群算法；周馳，等[6]在標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上，結(jié)合遺傳算法的交叉變異思想、變鄰域搜索、動(dòng)態(tài)慣性權(quán)重的尋優(yōu)策略，對(duì)倉(cāng)儲(chǔ)環(huán)境叉車運(yùn)動(dòng)進(jìn)行尋路。

隨著對(duì)強(qiáng)化學(xué)習(xí)研究的深入，部分學(xué)者也將強(qiáng)化學(xué)習(xí)方法應(yīng)用于路徑規(guī)劃中。由于Q學(xué)習(xí)的探索方式，導(dǎo)致Q學(xué)習(xí)算法的收斂速度并不高，算法性能較差。因此很多人對(duì)傳統(tǒng)Q學(xué)習(xí)算法進(jìn)行改進(jìn)，如王健，等[7]改進(jìn)傳統(tǒng)Q學(xué)習(xí)算法探索收斂速度過低的問題，通過動(dòng)態(tài)調(diào)整探索因子的探索方法，提高機(jī)器人對(duì)環(huán)境的熟知程度，提高算法收斂速度；張峰，等[8]提出基于樹的經(jīng)驗(yàn)存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)探索過程中的狀態(tài)轉(zhuǎn)移概率，并據(jù)此提出了基于期望經(jīng)驗(yàn)回放的Q學(xué)習(xí)算法。該方法降低算法復(fù)雜度，實(shí)現(xiàn)對(duì)環(huán)境狀態(tài)轉(zhuǎn)移的無(wú)偏估計(jì)，減少Q(mào)學(xué)習(xí)算法的過估計(jì)問題；趙辰豪，等[9]使用Boltzmann 選擇策略，通過動(dòng)態(tài)調(diào)整算法對(duì)動(dòng)作的選擇概率，使回報(bào)值與動(dòng)作被選概率呈正相關(guān)，提高學(xué)習(xí)的合理性與有效性，從而提高算法收斂速度。除此之外，遺傳算法、模擬退火算法等對(duì)于解決單智能體的路徑規(guī)劃問題也有很好的效果。

傳統(tǒng)Q學(xué)習(xí)存在收斂速度慢、尋路時(shí)容易陷入局部最優(yōu)解的問題。對(duì)此，本文提出一種改進(jìn)Q學(xué)習(xí)的強(qiáng)化學(xué)習(xí)算法。受文獻(xiàn)[2]的啟發(fā)，提出將類似模擬退火算法的動(dòng)態(tài)調(diào)整選擇策略因子的特性與Q學(xué)習(xí)算法相結(jié)合，動(dòng)態(tài)選擇下一步動(dòng)作，進(jìn)一步提高Q學(xué)習(xí)算法的收斂速度，提高算法性能，改善傳統(tǒng)Q學(xué)習(xí)容易陷入局部最優(yōu)的問題。仿真方面，結(jié)合“貨到人”揀選系統(tǒng)這一實(shí)際物流場(chǎng)景，模擬出倉(cāng)儲(chǔ)AGV揀貨送到揀選臺(tái)的流程，找到了一種能夠在充滿貨架和障礙的靜態(tài)環(huán)境中使AGV 路線最優(yōu)的解決方法。

2 “貨到人”揀選系統(tǒng)

“貨到人”揀選采用物流機(jī)器人（AGV）駝?shì)d貨物到揀選人面前的方式，供人揀選。相對(duì)于傳統(tǒng)的“人到貨”揀選方式，“貨到人”揀選在作業(yè)效率、成本控制、揀選正確率等方面，都具有顯著的優(yōu)勢(shì)[10]。目前有幾種主流的“貨到人”揀選方案，包括多層穿梭車方案、Autostore 方案、Miniload 方案、旋轉(zhuǎn)貨架方案和類Kiva 方案。從市場(chǎng)熱度來(lái)看，隨著亞馬遜Kiva 機(jī)器人的大規(guī)模應(yīng)用，類Kiva機(jī)器人（也稱為智能倉(cāng)儲(chǔ)機(jī)器人）得到越來(lái)越多的關(guān)注和追捧[11]。該系統(tǒng)相較于其他的方案更加靈活，易擴(kuò)展性強(qiáng)，高度自動(dòng)化，可以極大程度地代替人工。同時(shí)項(xiàng)目建立交付快，非常適用于一些庫(kù)存保有量大、商品訂單多品種的場(chǎng)景。本文采用的便是類Kiva機(jī)器人方案。

3 基于Q 學(xué)習(xí)的AGV路徑規(guī)劃

強(qiáng)化學(xué)習(xí)是做出最佳決策的科學(xué)，Q學(xué)習(xí)算法是其中的一個(gè)分支。Q學(xué)習(xí)算法是馬爾科夫決策過程的遞增式動(dòng)態(tài)規(guī)劃算法，由狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)組成的三元組來(lái)對(duì)Q值進(jìn)行選擇更新，最終得到AGV 最大限度的回報(bào)值，是通過值函數(shù)進(jìn)行估計(jì)后驗(yàn)概率來(lái)得到預(yù)測(cè)的算法。在進(jìn)行路徑規(guī)劃時(shí)，Q學(xué)習(xí)算法對(duì)AGV進(jìn)行初始化操作，設(shè)AGV的初始狀態(tài)為s,并建立矩陣R和矩陣Q分別存儲(chǔ)AGV 每步探索的即時(shí)獎(jiǎng)勵(lì)和Q值函數(shù)值。通過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)作。

傳統(tǒng)Q學(xué)習(xí)的主要流程如圖1所示。

對(duì)于Q學(xué)習(xí)來(lái)說，最重要的一步是根據(jù)Q值函數(shù)對(duì)Q值表進(jìn)行更新。Q值函數(shù)一般表示為：

根據(jù)Q值函數(shù)計(jì)算AGV路徑下一步動(dòng)作所帶來(lái)的可能影響，并根據(jù)選擇策略選擇帶來(lái)最好影響的路徑動(dòng)作。其選擇策略為：

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

圖1 傳統(tǒng)Q 學(xué)習(xí)流程

其中，Q'為更新的Q值函數(shù)值，s'為s的下一時(shí)刻路徑狀態(tài)，α'為α的下一時(shí)刻路徑動(dòng)作。α為學(xué)習(xí)率，定義了Q值更新占原Q值的比例，γ為折扣因子，定義未來(lái)獎(jiǎng)勵(lì)的重要程度。α和γ是Q值函數(shù)的兩個(gè)可操作數(shù)，通常認(rèn)為取值0時(shí)為程度最不重要，取值1時(shí)為程度最重要。

但傳統(tǒng)Q學(xué)習(xí)算法具有自身的局限性，在尋路時(shí)較容易陷入局部最優(yōu)解，并且當(dāng)倉(cāng)儲(chǔ)內(nèi)的AGV 數(shù)量增多或者單一AGV 可選擇的行走動(dòng)作集合過大時(shí)，易導(dǎo)致整體的狀態(tài)空間過大，出現(xiàn)Q學(xué)習(xí)算法效率降低，學(xué)習(xí)效果不明顯等問題，產(chǎn)生“維數(shù)災(zāi)難”。

4 基于改進(jìn)Q 學(xué)習(xí)的AGV路徑規(guī)劃

4.1 模擬退火算法

模擬退火算法從某一較高初始溫度出發(fā)，通過溫度參數(shù)的不斷降溫，使算法中的解逐步趨于穩(wěn)定。并在解集中以一定的概率跳出局部最優(yōu)解，來(lái)尋找目標(biāo)函數(shù)的全局最優(yōu)解。在模擬退火算法執(zhí)行過程中，主要存在三個(gè)參數(shù)設(shè)定問題：溫度T、退火速度（迭代次數(shù)L）和溫度管理（降溫方式）。

每求出一個(gè)新的最短路徑解x'，都要計(jì)算優(yōu)化目標(biāo)函數(shù)f(x)的增量，Δf=f(x')-f(x)。在尋找最短路徑時(shí)，若Δf ＜0 則接受x'作為最優(yōu)路徑保留下來(lái)，否則以概率p的可能來(lái)接受x作為最優(yōu)路徑。其中p為：

文獻(xiàn)[2]提出，降火過程中降火函數(shù)的選取在一定程度上也會(huì)對(duì)算法收斂速度有很大的影響。經(jīng)過大量文獻(xiàn)分析，筆者發(fā)現(xiàn)在尋最短路徑過程中對(duì)于同一溫度下的可選路徑進(jìn)行“充分”搜索是相當(dāng)必要的，而因此也消耗了大量的時(shí)間成本。循環(huán)次數(shù)增加必定帶來(lái)計(jì)算開銷的增大。針對(duì)此問題并且結(jié)合本算例的特殊性，筆者提出使用路徑表來(lái)緩解時(shí)間成本的壓力。

4.2 改進(jìn)Q 學(xué)習(xí)算法

在模擬退火算法中，通過以一定的概率跳出當(dāng)前局部最優(yōu)解的思想對(duì)于AGV尋路優(yōu)化有一定的借鑒意義。結(jié)合上述模擬退火算法的思想，對(duì)傳統(tǒng)Q學(xué)習(xí)的每個(gè)狀態(tài)和動(dòng)作的選擇執(zhí)行模擬退火降溫過程，并將其中動(dòng)作選擇策略添加一個(gè)概率，使得算法能夠以一定的概率跳出局部最優(yōu)解。根據(jù)“貨到人”揀選系統(tǒng)的特殊性，在動(dòng)態(tài)調(diào)節(jié)因子的基礎(chǔ)上增加一個(gè)路徑表PTable，用于存放已得到的最優(yōu)路徑，包括路徑起點(diǎn)、路徑終點(diǎn)、路徑經(jīng)過節(jié)點(diǎn)、該段路起點(diǎn)和終點(diǎn)四周的四個(gè)點(diǎn)的坐標(biāo)信息，以及所存儲(chǔ)節(jié)點(diǎn)之間的父子節(jié)點(diǎn)關(guān)系。該改進(jìn)Q學(xué)習(xí)算法核心算法的偽代碼如下，其流程圖如圖2所示。

（0）掃描路徑表PTable，若起點(diǎn)終點(diǎn)存在，則直接使用；若不存在，則從（1）執(zhí)行。

（1）初始化初始溫度T、終止溫度Tmin、退火速度q、初始化Q(s,a)。

（2）初始化動(dòng)作a，狀態(tài)s。

（3）退火T=q*T。

（4）AGV在狀態(tài)s時(shí)刻，選擇隨機(jī)動(dòng)作a，計(jì)算回報(bào)值amax。

（5）隨機(jī)產(chǎn)生一個(gè)（0,1）之間的隨機(jī)數(shù)β。

（6）判斷β與概率p進(jìn)行比較，根據(jù)上述選擇策略采取相應(yīng)的最好動(dòng)作amax或者隨機(jī)動(dòng)作a。

（7）若冷卻完成，T=Tmin，執(zhí)行下一步；否則返回（2）。

（8）依據(jù)Q學(xué)習(xí)算法Q值函數(shù)（式（1））和選擇策略（式（2））更新Q值表。

（9）更新路徑表PTable。

圖2 改進(jìn)Q 學(xué)習(xí)算法基本流程

5 仿真實(shí)驗(yàn)

5.1 實(shí)驗(yàn)描述

設(shè)計(jì)一個(gè)簡(jiǎn)單的方格“貨到人”揀選系統(tǒng)環(huán)境（如圖3所示），揀選環(huán)境模擬為26*26的柵格（單位：1），圖中“START”和“GOAL”所在的區(qū)域分別為車輛的停車點(diǎn)和揀選臺(tái)區(qū)域。中間部分8 個(gè)2*9 長(zhǎng)方形黑色區(qū)域代表貨架，其余17 個(gè)突起的灰色填充塊狀區(qū)域模擬靜態(tài)倉(cāng)儲(chǔ)環(huán)境多AGV相遇情況。其中貨架區(qū)域底部可走車。

圖3 仿真?zhèn)}儲(chǔ)環(huán)境圖

給出5組任務(wù)，每組任務(wù)10個(gè)貨物坐標(biāo)點(diǎn)，隨機(jī)給出每組任務(wù)的貨架坐標(biāo)和揀選臺(tái)坐標(biāo)點(diǎn)，任務(wù)邏輯為AGV從停車點(diǎn)出發(fā)，首先到達(dá)第一個(gè)任務(wù)貨架，將貨架運(yùn)到揀選臺(tái)，揀選完畢后將貨架送回原位置，再走到下一任務(wù)貨架，直至10個(gè)任務(wù)點(diǎn)全部走完，從揀選臺(tái)返回停車點(diǎn)。

基于上述規(guī)則，比較在相同情況下分別采用改進(jìn)Q學(xué)習(xí)和傳統(tǒng)A*算法、傳統(tǒng)Q學(xué)習(xí)算法時(shí)AGV的行駛距離長(zhǎng)短，并且比較兩種算法的尋路時(shí)間，來(lái)判斷改進(jìn)Q學(xué)習(xí)算法的有效性和優(yōu)越性。其中，本次實(shí)驗(yàn)不考慮訂單的任務(wù)分配問題，因此訂單編號(hào)和位置均為隨機(jī)，并未做歸并處理。

5.2 實(shí)驗(yàn)結(jié)果與分析

模擬退火算法中規(guī)定初始溫度T=1 000,終止溫度Tmin=0.001，降溫系數(shù)q=0.90。規(guī)定最大迭代次數(shù)為100 000 次。當(dāng)?shù)^最大迭代次數(shù)時(shí)或?qū)さ铰窂?，本次尋路結(jié)束。在Q學(xué)習(xí)算法中，規(guī)定學(xué)習(xí)率α=0.7，折扣因子γ=0.95，獎(jiǎng)勵(lì)矩陣R如下：

給定5組路徑信息（見表1），其中前三組為隨機(jī)坐標(biāo)點(diǎn)，第四組為第二組的對(duì)照組，揀選臺(tái)同第二組重合，停車點(diǎn)為第二組停車點(diǎn)的相鄰點(diǎn)，任務(wù)點(diǎn)坐標(biāo)為部分重復(fù)點(diǎn)；第五組為第一組對(duì)照組，揀選臺(tái)坐標(biāo)為第一組相鄰點(diǎn)，停車點(diǎn)坐標(biāo)不同，任務(wù)點(diǎn)坐標(biāo)與第一組部分相同或?yàn)橄噜忺c(diǎn)。第四組、第五組用于測(cè)試路徑表與改進(jìn)Q學(xué)習(xí)的配合情況。

表1 任務(wù)點(diǎn)坐標(biāo)

通過對(duì)比圖4、圖5可知，倉(cāng)儲(chǔ)環(huán)境中三種算法均能找到最短路徑，尋路長(zhǎng)度誤差5%以內(nèi)。尋路能力基本相同。但較于A*算法和傳統(tǒng)Q學(xué)習(xí)算法，改進(jìn)Q學(xué)習(xí)算法收斂到最優(yōu)值的速度普遍快于其他兩種算法的均值，效率最高可提高20%。由于改進(jìn)Q學(xué)習(xí)算法引進(jìn)了路徑表，使第四組和第五組任務(wù)點(diǎn)尋路的效率大大提高，且具有一定的穩(wěn)定性。

圖4 三種算法尋路長(zhǎng)度對(duì)比

圖5 三種算法收斂對(duì)比

6 結(jié)語(yǔ)

本文針對(duì)“貨到人”揀選系統(tǒng)，提出一種結(jié)合動(dòng)態(tài)探索因子和路徑表的改進(jìn)Q學(xué)習(xí)算法，來(lái)改善傳統(tǒng)Q學(xué)習(xí)算法效率低下、容易陷入局部最優(yōu)解的問題。首先引入動(dòng)態(tài)探索因子，將傳統(tǒng)Q學(xué)習(xí)的最優(yōu)選擇策略以一定的概率實(shí)現(xiàn)，并提出路徑表的概念，一定程度上節(jié)省了探路成本。然后建立柵格環(huán)境模擬倉(cāng)儲(chǔ)，通過仿真實(shí)驗(yàn)，將改進(jìn)Q學(xué)習(xí)算法和傳統(tǒng)Q學(xué)習(xí)、A*兩種算法對(duì)比，得出在“貨到人”揀選背景下倉(cāng)儲(chǔ)物流機(jī)器人AGV 的揀貨路徑最短。通過實(shí)驗(yàn)，改進(jìn)Q學(xué)習(xí)算法能夠找到最優(yōu)解，并且收斂速度優(yōu)于傳統(tǒng)A*算法和傳統(tǒng)Q學(xué)習(xí)算法，在一定程度上體現(xiàn)了該算法的高效和可用性。