基于改進Q學習的“貨到人”揀選系統AGV路徑規劃

杜卓穎，李金禧，張祥來，朱 琳

（哈爾濱商業大學 管理學院，黑龍江 哈爾濱 150000）

1 引言

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

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

隨著對強化學習研究的深入，部分學者也將強化學習方法應用于路徑規劃中。由于Q學習的探索方式，導致Q學習算法的收斂速度并不高，算法性能較差。因此很多人對傳統Q學習算法進行改進，如王健，等[7]改進傳統Q學習算法探索收斂速度過低的問題，通過動態調整探索因子的探索方法，提高機器人對環境的熟知程度，提高算法收斂速度；張峰，等[8]提出基于樹的經驗存儲結構來存儲探索過程中的狀態轉移概率，并據此提出了基于期望經驗回放的Q學習算法。該方法降低算法復雜度，實現對環境狀態轉移的無偏估計，減少Q學習算法的過估計問題；趙辰豪，等[9]使用Boltzmann 選擇策略，通過動態調整算法對動作的選擇概率，使回報值與動作被選概率呈正相關，提高學習的合理性與有效性，從而提高算法收斂速度。除此之外，遺傳算法、模擬退火算法等對于解決單智能體的路徑規劃問題也有很好的效果。

傳統Q學習存在收斂速度慢、尋路時容易陷入局部最優解的問題。對此，本文提出一種改進Q學習的強化學習算法。受文獻[2]的啟發，提出將類似模擬退火算法的動態調整選擇策略因子的特性與Q學習算法相結合，動態選擇下一步動作，進一步提高Q學習算法的收斂速度，提高算法性能，改善傳統Q學習容易陷入局部最優的問題。仿真方面，結合“貨到人”揀選系統這一實際物流場景，模擬出倉儲AGV揀貨送到揀選臺的流程，找到了一種能夠在充滿貨架和障礙的靜態環境中使AGV 路線最優的解決方法。

2 “貨到人”揀選系統

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

3 基于Q 學習的AGV路徑規劃

強化學習是做出最佳決策的科學，Q學習算法是其中的一個分支。Q學習算法是馬爾科夫決策過程的遞增式動態規劃算法，由狀態、動作和獎勵組成的三元組來對Q值進行選擇更新，最終得到AGV 最大限度的回報值，是通過值函數進行估計后驗概率來得到預測的算法。在進行路徑規劃時，Q學習算法對AGV進行初始化操作，設AGV的初始狀態為s,并建立矩陣R和矩陣Q分別存儲AGV 每步探索的即時獎勵和Q值函數值。通過AGV隨機選擇下一步路徑動作a 并計算相應的Q值函數值，來進行Q值表的更新操作。在該算法下，每個Q(s,a)都有對應的一個Q值，即為得到的累計回報。最終根據得到的最大累計回報，選擇相對應的AGV行走動作。

傳統Q學習的主要流程如圖1所示。

對于Q學習來說，最重要的一步是根據Q值函數對Q值表進行更新。Q值函數一般表示為：

根據Q值函數計算AGV路徑下一步動作所帶來的可能影響，并根據選擇策略選擇帶來最好影響的路徑動作。其選擇策略為：

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

圖1 傳統Q 學習流程

其中，Q'為更新的Q值函數值，s'為s的下一時刻路徑狀態，α'為α的下一時刻路徑動作。α為學習率，定義了Q值更新占原Q值的比例，γ為折扣因子，定義未來獎勵的重要程度。α和γ是Q值函數的兩個可操作數，通常認為取值0時為程度最不重要，取值1時為程度最重要。

但傳統Q學習算法具有自身的局限性，在尋路時較容易陷入局部最優解，并且當倉儲內的AGV 數量增多或者單一AGV 可選擇的行走動作集合過大時，易導致整體的狀態空間過大，出現Q學習算法效率降低，學習效果不明顯等問題，產生“維數災難”。

4 基于改進Q 學習的AGV路徑規劃

4.1 模擬退火算法

模擬退火算法從某一較高初始溫度出發，通過溫度參數的不斷降溫，使算法中的解逐步趨于穩定。并在解集中以一定的概率跳出局部最優解，來尋找目標函數的全局最優解。在模擬退火算法執行過程中，主要存在三個參數設定問題：溫度T、退火速度（迭代次數L）和溫度管理（降溫方式）。

每求出一個新的最短路徑解x'，都要計算優化目標函數f(x)的增量，Δf=f(x')-f(x)。在尋找最短路徑時，若Δf ＜0 則接受x'作為最優路徑保留下來，否則以概率p的可能來接受x作為最優路徑。其中p為：

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

4.2 改進Q 學習算法

在模擬退火算法中，通過以一定的概率跳出當前局部最優解的思想對于AGV尋路優化有一定的借鑒意義。結合上述模擬退火算法的思想，對傳統Q學習的每個狀態和動作的選擇執行模擬退火降溫過程，并將其中動作選擇策略添加一個概率，使得算法能夠以一定的概率跳出局部最優解。根據“貨到人”揀選系統的特殊性，在動態調節因子的基礎上增加一個路徑表PTable，用于存放已得到的最優路徑，包括路徑起點、路徑終點、路徑經過節點、該段路起點和終點四周的四個點的坐標信息，以及所存儲節點之間的父子節點關系。該改進Q學習算法核心算法的偽代碼如下，其流程圖如圖2所示。

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

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

（2）初始化動作a，狀態s。

（3）退火T=q*T。

（4）AGV在狀態s時刻，選擇隨機動作a，計算回報值amax。

（5）隨機產生一個（0,1）之間的隨機數β。

（6）判斷β與概率p進行比較，根據上述選擇策略采取相應的最好動作amax或者隨機動作a。

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

（8）依據Q學習算法Q值函數（式（1））和選擇策略（式（2））更新Q值表。

（9）更新路徑表PTable。

圖2 改進Q 學習算法基本流程

5 仿真實驗

5.1 實驗描述

設計一個簡單的方格“貨到人”揀選系統環境（如圖3所示），揀選環境模擬為26*26的柵格（單位：1），圖中“START”和“GOAL”所在的區域分別為車輛的停車點和揀選臺區域。中間部分8 個2*9 長方形黑色區域代表貨架，其余17 個突起的灰色填充塊狀區域模擬靜態倉儲環境多AGV相遇情況。其中貨架區域底部可走車。

圖3 仿真倉儲環境圖

給出5組任務，每組任務10個貨物坐標點，隨機給出每組任務的貨架坐標和揀選臺坐標點，任務邏輯為AGV從停車點出發，首先到達第一個任務貨架，將貨架運到揀選臺，揀選完畢后將貨架送回原位置，再走到下一任務貨架，直至10個任務點全部走完，從揀選臺返回停車點。

基于上述規則，比較在相同情況下分別采用改進Q學習和傳統A*算法、傳統Q學習算法時AGV的行駛距離長短，并且比較兩種算法的尋路時間，來判斷改進Q學習算法的有效性和優越性。其中，本次實驗不考慮訂單的任務分配問題，因此訂單編號和位置均為隨機，并未做歸并處理。

5.2 實驗結果與分析

模擬退火算法中規定初始溫度T=1 000,終止溫度Tmin=0.001，降溫系數q=0.90。規定最大迭代次數為100 000 次。當迭代超過最大迭代次數時或尋到路徑，本次尋路結束。在Q學習算法中，規定學習率α=0.7，折扣因子γ=0.95，獎勵矩陣R如下：

給定5組路徑信息（見表1），其中前三組為隨機坐標點，第四組為第二組的對照組，揀選臺同第二組重合，停車點為第二組停車點的相鄰點，任務點坐標為部分重復點；第五組為第一組對照組，揀選臺坐標為第一組相鄰點，停車點坐標不同，任務點坐標與第一組部分相同或為相鄰點。第四組、第五組用于測試路徑表與改進Q學習的配合情況。

表1 任務點坐標

通過對比圖4、圖5可知，倉儲環境中三種算法均能找到最短路徑，尋路長度誤差5%以內。尋路能力基本相同。但較于A*算法和傳統Q學習算法，改進Q學習算法收斂到最優值的速度普遍快于其他兩種算法的均值，效率最高可提高20%。由于改進Q學習算法引進了路徑表，使第四組和第五組任務點尋路的效率大大提高，且具有一定的穩定性。

圖4 三種算法尋路長度對比

圖5 三種算法收斂對比

6 結語

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