基于多智能體強化學(xué)習(xí)的自動化電力倉庫貨位優(yōu)化

王鐵錚，胡亞楠，潘 焜，喻 曉

(國網(wǎng)北京市電力公司 物資分公司，北京 100053)

電力倉庫負責(zé)供電公司電力項目建設(shè)、搶修、維修的物資供應(yīng)任務(wù)。隨著自動化大型電力倉庫的建設(shè)使用和物資供應(yīng)任務(wù)的增多，對于電力倉庫的物資管理提出更高的要求。目前自動化大型電力倉庫基于貨架構(gòu)造形式分為單元貨架形式[1-2]、貫通形式[3]、水平旋轉(zhuǎn)式[4]和垂直旋轉(zhuǎn)貨架式。

物資貨位優(yōu)化是影響自動化倉庫管理效率的重要因素之一。為了進一步提升自動化倉庫管理效率，相關(guān)學(xué)者在貨位優(yōu)化問題上進行了大量相關(guān)研究。印美等[5]以物資出入庫距離、貨架穩(wěn)定性為目標建立非支配遺傳算法對多目標的貨位優(yōu)化問題進行求解。張思建等[6]基于自動小車存取系統(tǒng)的電力倉庫，應(yīng)用模擬退火算法對多批的物資入庫貨位分配進行優(yōu)化。肖鋒[7]利用物資歷史入庫經(jīng)驗數(shù)據(jù)，使用強化學(xué)習(xí)算法解決貨位分配問題。

基于遺傳算法[8]、模擬退火算法[9-10]或粒子群算法[11]進行貨位優(yōu)化問題的求解，已經(jīng)能夠?qū)崿F(xiàn)單次物資入庫時綜合考慮多個目標，使得優(yōu)化后的物資入庫貨位在多個目標上綜合效益全局最優(yōu)或局部最優(yōu)。但是該方法在優(yōu)化時，只能考慮到當(dāng)前時間點的倉庫最優(yōu)情況，無法考慮到未來物資入庫后的倉儲情境。基于強化學(xué)習(xí)[12]的方法構(gòu)建貨位優(yōu)化算法可以利用倉庫的歷史物資出入庫數(shù)據(jù)進行模型訓(xùn)練，在貨位優(yōu)化時綜合考慮當(dāng)前時間點的即時獎勵和未來獎勵，實現(xiàn)電力物資倉庫在較長時間范圍內(nèi)的利益最大化。多智能體強化學(xué)習(xí)算法[13]相對于普通的單智能體強化學(xué)習(xí)算法[14]，能夠更好地處理較為復(fù)雜的優(yōu)化問題，具有較高的穩(wěn)定性、適應(yīng)性。本文在MADDPG多智能體強化學(xué)習(xí)算法[15]基礎(chǔ)上，針對貨位優(yōu)化問題，提出改進算法ECS-MADDPG。

1 貨位優(yōu)化目標數(shù)學(xué)模型

根據(jù)電力自動化倉庫實際情況和電力物資信息，以提升倉庫效率、物資運輸能耗和貨架穩(wěn)定性為原則，建立多目標貨位優(yōu)化數(shù)學(xué)模型。

1.1 倉庫物資出入庫時間

倉庫物資出入庫時間越短，倉庫物資出入庫效率越高，物資運輸能耗越低。焦玉玲等[16]以堆垛機Y、Z兩個運動方向建立數(shù)學(xué)模型。研究設(shè)定傳動帶加堆垛機的運輸方式，運動速度分別以 vx、vy、vz在X、Y、Z方向上進行勻速運動，忽略傳送帶和堆垛機啟動、制動過程，則倉庫物資出入庫時間優(yōu)化的數(shù)學(xué)描述如下。

式(1)中，T 為物資單程運輸時間，x、y、z分別為在X、Y、Z 3個方向上的位移距離。

1.2 倉庫貨架垂直質(zhì)心

倉庫貨架垂直重心越低，倉庫整體物資運輸能耗越低，貨架穩(wěn)定性越好。為了使貨架整體垂直重心盡可能低，建立數(shù)學(xué)描述如下。

式(2)中，Gz為單個貨架的垂直質(zhì)心值； mxyz為貨架上每個貨位中物資的質(zhì)量，空貨位質(zhì)量為0；L為貨位的邊長；n、p、q分別為在3個方向上位移的步數(shù)。

1.3 倉庫貨架水平質(zhì)心

倉庫貨架水平質(zhì)心越接近中心點，倉庫貨架穩(wěn)定性越好。為了使貨架整體水平質(zhì)心盡可能靠近中心點，建立數(shù)學(xué)描述如下。

式(3)中，Gy為單個貨架的水平質(zhì)心值。

2 ECS-MADDPG貨位優(yōu)化算法設(shè)計

2.1 倉庫物資出入庫時間

強化學(xué)習(xí)基本的模型是馬爾可夫決策過程[17]，一般有4個核心要素：環(huán)境狀態(tài)空間S、動作空間A、環(huán)境獎勵函數(shù)R、環(huán)境狀態(tài)轉(zhuǎn)移函數(shù)T。強化學(xué)習(xí)的算法訓(xùn)練過程就是智能體和環(huán)境交互的過程，智能體依據(jù)當(dāng)前環(huán)境信息St選擇動作At，環(huán)境給智能體返回獎勵Rt，并更新環(huán)境狀態(tài)到St+1。

在電力倉庫貨位優(yōu)化問題中，倉庫環(huán)境狀態(tài)信息包括每一個貨位的位置信息、所在貨架信息、倉庫中未擺放貨物的貨位信息、倉庫中擺放貨物的貨位信息以及對應(yīng)的貨物信息等。Agent感知到的電力倉庫環(huán)境狀態(tài)S可表示為

其中，P為貨位位置及所在貨架，G為物資種類，M為貨物質(zhì)量，n為倉庫中的貨位數(shù)。

在貨位優(yōu)化過程中，物資入庫任務(wù)可能會有多個物資同時入庫。本文研究的多智能體算法為每一類物資設(shè)置一個對應(yīng)的智能體，基于物資種類的變化算法可靈活調(diào)節(jié)智能體的數(shù)量。在一次物資入庫任務(wù)中多個智能體分別為對應(yīng)的種類物資規(guī)劃入庫貨位，當(dāng)一次物資入庫任務(wù)中某一種類物資有多個，一個智能體順序為多個同類物資規(guī)劃入庫貨位。智能體的動作執(zhí)行空間為選擇一個倉庫中的空置貨位。由于多個智能體并行規(guī)劃物資的貨位時可能出現(xiàn)多個物資分配到同一貨位的異常狀況，設(shè)定同一批入庫物資由多個智能體順序執(zhí)行物資貨位規(guī)劃。

在電力倉庫貨位優(yōu)化問題中，物資入庫任務(wù)和物資出庫任務(wù)時常出現(xiàn)交替情況，貨位優(yōu)化算法僅在物資入庫任務(wù)階段執(zhí)行。因此當(dāng)兩次物資入庫任務(wù)之間存在物資出庫任務(wù)時，第1次物資入庫動作執(zhí)行后的倉庫環(huán)境和第2次物資入庫動作執(zhí)行前的倉庫環(huán)境可能存在不一致，因此傳統(tǒng)的強化學(xué)習(xí)中智能體與環(huán)境的交互過程無法滿足需求。研究提出貨位優(yōu)化問題中強化學(xué)習(xí)智能體與環(huán)境的交互過程，如圖1所示。

圖1 強化學(xué)習(xí)的智能體與環(huán)境的交互過程Figure 1 The interaction between the agent and the environment in of reinforcement learning

圖1 中智能體根據(jù)物資入庫時的倉庫環(huán)境執(zhí)行物資貨位分配動作后，倉庫環(huán)境不會立刻給予智能體新的倉庫環(huán)境狀體和獎勵反饋，而是當(dāng)有新的物資入庫時，智能體獲得前一次執(zhí)行動作后的獎勵以及新的倉庫環(huán)境狀態(tài)。

2.2 獎勵函數(shù)設(shè)計

獎勵函數(shù)負責(zé)計算智能體為入庫物資分配貨位的效果收益。針對電力倉庫貨位優(yōu)化的需求，設(shè)定倉庫所有物資的出入庫運輸時間、所有貨架垂直重心和水平重心的平均值為優(yōu)化目標。多個智能體為完全合作的關(guān)系，常用的獎勵函數(shù)設(shè)計方式為多個智能體使用相同的獎勵函數(shù)，這樣多個智能體得到的回報也是相同的，多個智能體的聯(lián)合動作目標為獲得整體最大化回報。實驗過程中發(fā)現(xiàn)，多個智能體采用相同獎勵函數(shù)的方式會導(dǎo)致部分智能體產(chǎn)生惰性，進而影響多個智能體的整體回報。本文設(shè)計的獎勵函數(shù)為混合獎勵機制，智能體執(zhí)行動作后，環(huán)境將同時給予智能體單獨的獎勵以及所有智能體聯(lián)合動作的整體獎勵。該獎勵機制使得多個智能體之間既有合作關(guān)系也有競爭關(guān)系。通過引入多個智能體之間的適度競爭提升了多個智能體的聯(lián)合動作的整體回報。

電力倉庫中所有物資的運輸時間受到倉庫中物資所在貨位位置和物資的存儲時間影響。對于存儲時間短的物資，算法應(yīng)偏向于為物資分配距離倉庫出入口較近的貨位，反之應(yīng)偏向于為物資分配距離倉庫出入口較遠的貨位。

針對貨位優(yōu)化問題的特性，設(shè)定智能體執(zhí)行貨位分配動作后的獎勵由2部分構(gòu)成。第1部分為智能體執(zhí)行動作引起環(huán)境變化得到的單獨獎勵，如式(5)所示。

式(5)中，T表示單個物資運輸?shù)街付ㄘ浳坏臅r長；Gz和Gy分別表示單個物資放置到貨位后，該貨位所在的貨架的垂直質(zhì)心數(shù)值和水平質(zhì)心數(shù)值。W為T、Gz和Gy對于智能體獎勵值影響的權(quán)重；Fnor為maxmin歸一化函數(shù)，函數(shù)細節(jié)如式(6)所示，max和min值分別為變量x的最大可取數(shù)值和最小可取數(shù)值。通過歸一化函數(shù)可將多個不同量綱的指標數(shù)據(jù)轉(zhuǎn)換為同一量綱指標。式(5)中，d表示該物資當(dāng)前入庫時間與該物資下一批次入庫時間之間相差的天數(shù)，相差時間越高說明物資入庫頻率可能越低，物資出入庫運輸時長對倉庫整體的優(yōu)化目標較小，因此通過動態(tài)調(diào)整指標數(shù)值映射范圍調(diào)低該指標對整體優(yōu)化目標的影響。由于T、Gz和Gy數(shù)值越低表示算法優(yōu)化效果越好，因此獎勵值取T、Gz和Gy加權(quán)求和的倒數(shù)。

第2部分為同一批次執(zhí)行物資分配任務(wù)的多個智能體執(zhí)行的聯(lián)合動作引起環(huán)境變化得到的整體獎勵，如式(8)所示。

式(8)中，表示同一批次所有物資運輸?shù)街付ㄘ浳坏臅r長總和；分別表示該批物資入庫貨位對應(yīng)的所有貨架的垂直質(zhì)心數(shù)值總和以及水平質(zhì)心數(shù)值總和。

智能體執(zhí)行動作得到的單獨獎勵和多個智能體聯(lián)合動作得到整體獎勵加權(quán)求和值為單個智能體的最終獎勵，獎勵函數(shù)如式(9)所示。

2.3 ECS-MADDPG算法

DDPG算法[18]是一種使用Actor-Critic算法框架和深度確定性策略梯度方式的強化學(xué)習(xí)算法。該算法分為Actor和Critic兩個部分。

Actor網(wǎng)絡(luò)部分由Actor主網(wǎng)絡(luò)和Actor目標網(wǎng)絡(luò)組成。Actor主網(wǎng)絡(luò)負責(zé)根據(jù)當(dāng)前環(huán)境狀態(tài)S選擇動作A，得到環(huán)境反饋值R和新的狀態(tài)S′；同時更新網(wǎng)絡(luò)參數(shù)θu，并將交互數(shù)據(jù)以多元組 〈 S,A,R,S′〉的形式存入經(jīng)驗池E中，表達式如式(10)。Actor目標網(wǎng)絡(luò)負責(zé)從經(jīng)驗池中隨機采樣狀態(tài)S′并 產(chǎn)生動作A′，Actor目標網(wǎng)絡(luò)參數(shù) θu′通 過復(fù)制參數(shù) θu更新，表達式如式(11)，式中u為目標值參數(shù)。

Critic網(wǎng)絡(luò)部分由Critic主網(wǎng)絡(luò)和Critic目標網(wǎng)絡(luò)組成。Critic主網(wǎng)絡(luò)負責(zé)計算預(yù)估值q并更新網(wǎng)絡(luò)參數(shù)θq，表達式如式(12)。Critic目標網(wǎng)絡(luò)負責(zé)計算目標值q，網(wǎng)絡(luò)參數(shù) θq′通過定期復(fù)制θq更新，表達式如式(13)。Critic部分主要作用是優(yōu)化網(wǎng)絡(luò)參數(shù)。

MAGGPG算法將DDPG算法思想拓展應(yīng)用到多智能體強化學(xué)習(xí)領(lǐng)域，使用多智能體集中訓(xùn)練，獨立分布式執(zhí)行動作的架構(gòu)，每一個智能體擁有自己獨立的Actor和Critic網(wǎng)絡(luò)。在訓(xùn)練環(huán)節(jié)，智能體的Actor網(wǎng)絡(luò)僅使用智能體自身可獲得的環(huán)境信息。Critic網(wǎng)絡(luò)利用智能體自身獲得的環(huán)境信息以及其他智能體的動作信息等進行訓(xùn)練，并指導(dǎo)Actor網(wǎng)絡(luò)的參數(shù)更新。在預(yù)測環(huán)節(jié)，每一個智能體可獨立執(zhí)行動作。

ECS-MADDPG算法在MAGGPG算法的基礎(chǔ)上針對貨位優(yōu)化問題，設(shè)計執(zhí)行相似任務(wù)的智能體共享經(jīng)驗池和Critic網(wǎng)絡(luò)的方式改進模型訓(xùn)練時長和部分智能體可能無法收斂的問題。研究設(shè)定每一類物資設(shè)置一個對應(yīng)的智能體，不同智能體執(zhí)行任務(wù)的差異在于其對應(yīng)的不同物資的裝箱質(zhì)量和出入庫頻率不同。通過物資的質(zhì)量和出入庫頻率對部分出入庫頻率較低的物資進行K-Means聚類，將物資與智能體分為幾個大的類別。大類別內(nèi)部智能體共享經(jīng)驗池和Critic網(wǎng)絡(luò)，當(dāng)智能體Actor主網(wǎng)絡(luò)在狀態(tài)S產(chǎn)生動作A后，會將數(shù)據(jù)交互元組 〈 S,A,R,S′〉存入共享經(jīng)驗池E，多個智能體從共享經(jīng)驗池中隨機采樣數(shù)據(jù)，并使用和更新同一個共享Critic網(wǎng)絡(luò)。貨位優(yōu)化問題中算法訓(xùn)練過程不同智能體執(zhí)行動作的次數(shù)不同，通過共享經(jīng)驗池的方式可使得交互數(shù)據(jù)比較少的智能體擁有更豐富的經(jīng)驗交互數(shù)據(jù)，從而減少模型整體訓(xùn)練時長和交互數(shù)據(jù)比較少的智能體的收斂時長。ECS-MADDPG算法結(jié)構(gòu)如圖2所示。

圖2 ECS-MADDPG算法結(jié)構(gòu)Figure 2 The structure of the ECS-MADDPG algorithm

ECS-MADDPG算法流程如下所示。

1) 初始化n個智能體的Actor和Critic網(wǎng)絡(luò)參數(shù)。

2) for k=1 to 最大回合數(shù)。

3) 初始化倉庫物資狀。

4) for t=1 to 最大物資入庫次數(shù)。

5) 多個智能體通過Actor主網(wǎng)絡(luò)進行動作選擇ai=μ(Si)， 執(zhí)行動作獲得環(huán)境獎勵r和新的狀態(tài) S′，將多元組 〈S,A,R,S′〉智能體-環(huán)境交互數(shù)據(jù)分別存入對應(yīng)的經(jīng)驗池。

6) for agent=1 to 最多n個智能體。

7) 隨機在多個經(jīng)驗池中采樣W組 〈 S,A,R,S′〉交互數(shù)據(jù)，組成聯(lián)合交互數(shù)據(jù)。

8) Critic網(wǎng)絡(luò)目標q值計算，其中γ為常數(shù)值參數(shù)

9) 損失函數(shù)計算并更新Critic主網(wǎng)絡(luò)參數(shù)，損失函數(shù)如下，其中表示第i個智能體的狀態(tài)-動作函數(shù)。

10) 通過策略梯度更新Actor主網(wǎng)絡(luò)參數(shù)，計算公式如下，其中表示第n個智能體在時間步下的環(huán)境觀察信息。

11) 更新Actor和Critic目標網(wǎng)絡(luò)，其中 τ為常數(shù)參數(shù)值，表示權(quán)重。

3 實驗結(jié)果及分析

實驗的電力自動化倉庫共有3個相同規(guī)模的倉庫，每個倉庫有18排貨架，每排有16列8層高，每一個倉庫有2 304個貨位，所有貨位尺寸相同。電力倉庫水平方向使用傳送帶進行物資傳送，垂直方向使用堆垛機進行物資運輸。倉庫貨位長寬高尺寸為2 500 mm×1 000 mm×4 500 mm，單個貨位最大承受重力為1 t。自動化倉庫如圖3所示。

圖3 電力自動化倉庫俯視圖Figure 3 Top view of power automation warehouse

為了驗證本文提出的ECS-MADDPG強化學(xué)習(xí)算法的效果，實驗設(shè)計使用MADDPG算法、DDPG算法、DQN算法作為對照組。實驗數(shù)據(jù)使用9個月的某電力物資倉庫物資出入庫數(shù)據(jù)。初始時，3個倉庫已存有電力物資的貨位分別為1 534個、974個和367個。通過均勻分布和正態(tài)分布方式對3個倉庫初始物資擺放位置進行隨機分配，每種分布生成10組初始隨機倉庫物資分布。實驗數(shù)據(jù)中的物資統(tǒng)一裝入相同尺寸規(guī)格的箱子中，不同物資裝入箱中的數(shù)量和裝箱后總質(zhì)量不相同，箱子尺寸小于貨位尺寸。部分物資裝箱數(shù)量和質(zhì)量樣例如表1所示。

表1 物資裝箱數(shù)據(jù)樣例Table 1 Sample packaging data

實驗過程中每一輪3個電力倉庫分別有462批次、951批次和1 267批次物資入庫，每一批次物資入庫數(shù)量不等。圖4表示1號倉庫實驗組和對照組算法在1 000回合的迭代過程中獲得的平均回報。

圖4 1號倉庫各算法迭代次數(shù)對應(yīng)的平均回報Figure 4 Average reward corresponding to the number of iterations of each algorithm in warehouse 1

圖5表示2號倉庫實驗組和對照組算法在1 000回合的迭代過程中獲得的平均回報。

圖5 2號倉庫各算法迭代次數(shù)對應(yīng)的平均回報Figure 5 Average reward corresponding to the number of iterations of each algorithm in warehouse 2

圖6表示3號倉庫實驗組和對照組算法在1 000回合的迭代過程中獲得的平均回報。

圖6 3號倉庫各算法迭代次數(shù)對應(yīng)的平均回報Figure 6 Average reward corresponding to the number of iterations of each algorithm in warehouse 1

通過圖4～6可以發(fā)現(xiàn)，ECS-MADDPG算法在3組倉庫環(huán)境中通過200次迭代均可以收斂，MADDPG算法在3組倉庫環(huán)境中通過250次迭代均可以收斂，DDPG算法和DQN算法在3組倉庫環(huán)境中通過230次迭代可以收斂。MADDPG算法隨著實驗每一回合入庫物資批次增多有較為明顯的穩(wěn)定性和最高平均回報值的提升，說明入庫物資批次較少時，非共享結(jié)構(gòu)的MADDPG中可能存在部分智能體網(wǎng)絡(luò)學(xué)習(xí)不充分的現(xiàn)象。ECS-MADDPG算法在3組倉庫環(huán)境中模型效果的穩(wěn)定性和最高平均回報值均優(yōu)于其他3組對照組實驗。

4 結(jié)論

本文提出了一種多智能體強化學(xué)習(xí)的電力倉庫貨位優(yōu)化算法。該算法在貨位優(yōu)化時同時考慮當(dāng)前時間點的即時獎勵和未來獎勵，實現(xiàn)電力物資倉庫在較長時間范圍內(nèi)的所有物資的出入庫時間、貨架的重心加權(quán)指標在較長時間范圍內(nèi)為較優(yōu)的結(jié)果。實驗表明，相對于普通單智能體和多智能體強化學(xué)習(xí)算法，ECS-MADDPG算法效果具有較高的穩(wěn)定性和回報值。