饒東寧，羅南岳

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006）

0 概述

隨著電子商務(wù)等行業(yè)的快速發(fā)展，物流訂單井噴、土地成本快速上升，物流企業(yè)著手對(duì)倉(cāng)儲(chǔ)系統(tǒng)進(jìn)行智能化管理。亞馬遜研究開(kāi)發(fā)了Kiva Systems 倉(cāng)庫(kù)機(jī)器人系統(tǒng)［1］，使用數(shù)百個(gè)自動(dòng)導(dǎo)航車(chē)代替了工作人員完成貨物訂單的存取任務(wù)，極大地提高了貨物存取操作的效率。國(guó)內(nèi)企業(yè)如京東、?？档认群髮?shí)現(xiàn)了類(lèi)Kiva 智能倉(cāng)儲(chǔ)系統(tǒng)并推廣至國(guó)內(nèi)市場(chǎng)［2］。

針對(duì)倉(cāng)儲(chǔ)中調(diào)度問(wèn)題的建模與優(yōu)化，很多學(xué)者進(jìn)行了深入的研究。文獻(xiàn)［3］針對(duì)倉(cāng)庫(kù)中的隨機(jī)存儲(chǔ)情況和不同類(lèi)型的堆垛機(jī)，為每個(gè)存儲(chǔ)或檢索的位置選擇了足夠熟練的堆垛機(jī)，從而使得總使用時(shí)間最小化。于赫年等［4］通過(guò)分析多智能體調(diào)度系統(tǒng)的任務(wù)分配模式、作業(yè)流程及任務(wù)調(diào)度的約束條件，建立了以最小化任務(wù)完成時(shí)間為主要目標(biāo)的數(shù)學(xué)模型。然而上述兩種方法主要以時(shí)間作為優(yōu)化目標(biāo)，沒(méi)有考慮到提高累計(jì)回報(bào)值。魯建廈等［5］通過(guò)分析穿梭車(chē)倉(cāng)儲(chǔ)系統(tǒng)中的提升機(jī)與穿梭車(chē)的實(shí)際作業(yè)流程，建立了復(fù)合作業(yè)路徑規(guī)劃模型并通過(guò)人工魚(yú)群算法求解，有效地提高了該倉(cāng)儲(chǔ)系統(tǒng)的運(yùn)行效率。

盡管以上方法針對(duì)倉(cāng)儲(chǔ)中相關(guān)調(diào)度問(wèn)題提出了解決方案，但庫(kù)位問(wèn)題方面依然存在不足。傳統(tǒng)的庫(kù)位分配通?；谌藶榻?jīng)驗(yàn)，未充分考慮庫(kù)位的使用狀態(tài)和整體空間分布等，導(dǎo)致倉(cāng)庫(kù)管理效率下降。合理的庫(kù)位安排，可以提高堆垛機(jī)的效率和可靠性，因此需要解決面向倉(cāng)儲(chǔ)的多任務(wù)問(wèn)題。

堆垛機(jī)調(diào)度動(dòng)作是基于時(shí)間步的動(dòng)作序列，而強(qiáng)化學(xué)習(xí)常用于解決序列決策問(wèn)題。為了實(shí)現(xiàn)對(duì)更大狀態(tài)空間的問(wèn)題實(shí)例進(jìn)行更有效的求解，研究人員將深度學(xué)習(xí)的思想融入強(qiáng)化學(xué)習(xí)的算法中，并應(yīng)用于該類(lèi)調(diào)度問(wèn)題中。

本文通過(guò)對(duì)堆垛機(jī)調(diào)度問(wèn)題進(jìn)行建模，構(gòu)建倉(cāng)儲(chǔ)環(huán)境，并針對(duì)堆垛機(jī)調(diào)度問(wèn)題，提出一種基于近端策略?xún)?yōu)化（Proximal Policy Optimization，PPO）［6］強(qiáng)化學(xué)習(xí)的調(diào)度方法。將調(diào)度問(wèn)題視為序列決策問(wèn)題，使智能體與環(huán)境進(jìn)行持續(xù)交互，根據(jù)環(huán)境反饋不斷優(yōu)化動(dòng)作的抉擇，從而改善實(shí)驗(yàn)效果。針對(duì)調(diào)度中伴生的庫(kù)位優(yōu)化問(wèn)題，提出一種基于多任務(wù)學(xué)習(xí)的調(diào)度、庫(kù)位推薦聯(lián)合算法，通過(guò)構(gòu)建處理庫(kù)位推薦的Actor 網(wǎng)絡(luò)［7］，使該網(wǎng)絡(luò)與Critic 網(wǎng)絡(luò)進(jìn)行交互反饋，促進(jìn)整體的聯(lián)動(dòng)和訓(xùn)練，以實(shí)現(xiàn)該算法在調(diào)度和庫(kù)位問(wèn)題場(chǎng)景下的應(yīng)用。

1 研究背景

1.1 概率規(guī)劃

概率規(guī)劃［8］是人工智能的研究方向之一，描述的是馬爾可夫決策問(wèn)題，其主要特點(diǎn)是概率性和并行性，目標(biāo)是最大化累計(jì)回報(bào)值。概率規(guī)劃被應(yīng)用于各類(lèi)現(xiàn)實(shí)場(chǎng)景中。文獻(xiàn)［9］基于概率規(guī)劃的方法對(duì)股指模擬問(wèn)題進(jìn)行領(lǐng)域建模，并使用規(guī)劃器求解問(wèn)題。其中在國(guó)際概率規(guī)劃比賽中表現(xiàn)最好的規(guī)劃器為SOGBOFA［10］。

1.2 強(qiáng)化學(xué)習(xí)

隨著人工智能的發(fā)展，研究人員提出了DQN（Deep Q-Networks）［11］、TRPO（Trust Region Policy Optimization）［12］等深度強(qiáng)化學(xué)習(xí)算法，并在移動(dòng)機(jī)器人［13］、路徑規(guī)劃［14］、調(diào)度問(wèn)題等應(yīng)用場(chǎng)景中取得了較好的成果。例如，針對(duì)旅行商問(wèn)題和有容量限制的車(chē)輛路徑問(wèn)題，文獻(xiàn)［15］在關(guān)于路徑問(wèn)題的改進(jìn)啟發(fā)式算法上，構(gòu)建一個(gè)基于自注意力機(jī)制的深度強(qiáng)化學(xué)習(xí)架構(gòu)，該架構(gòu)泛化性表現(xiàn)良好。文獻(xiàn)［16］利用深度強(qiáng)化學(xué)習(xí)技術(shù)對(duì)適用于作業(yè)車(chē)間調(diào)度問(wèn)題的優(yōu)先調(diào)度規(guī)則進(jìn)行自動(dòng)學(xué)習(xí)，析取作業(yè)車(chē)間調(diào)度問(wèn)題的圖表示，根據(jù)該圖表示提出了一種基于圖神經(jīng)網(wǎng)絡(luò)的模式，并將其嵌入到狀態(tài)空間。

強(qiáng)化學(xué)習(xí)的基本思想是使智能體在與環(huán)境交互過(guò)程中獲得最大的累計(jì)回報(bào)值，從而不斷優(yōu)化自身動(dòng)作的決策［17］。其理論基于馬爾可夫決策過(guò)程，算法構(gòu)成主要包括智能體、環(huán)境、狀態(tài)、動(dòng)作以及獎(jiǎng)勵(lì)等。智能體若處于狀態(tài)st，根據(jù)策略函數(shù)得到動(dòng)作at并施加于環(huán)境之上，獲得返回獎(jiǎng)勵(lì)rt+1，期望回報(bào)Gt表示在γ折扣下估計(jì)的累計(jì)獎(jiǎng)勵(lì)。期望公式如下：

引入狀態(tài)價(jià)值函數(shù)V（s）對(duì)Gt進(jìn)行估計(jì)：

同時(shí)為了評(píng)價(jià)某一個(gè)狀態(tài)或者動(dòng)作的好壞，引入動(dòng)作價(jià)值函數(shù)Q（s，a）：

而針對(duì)動(dòng)作a為離散的現(xiàn)象，可以將其松弛化為動(dòng)作空間上的連續(xù)分布的采樣。例如，用Softmax 將網(wǎng)絡(luò)輸出規(guī)范化為動(dòng)作的概率分布，然后在此基礎(chǔ)上采樣動(dòng)作并執(zhí)行獲得反饋。

1.3 近端策略?xún)?yōu)化

在可擴(kuò)展性和魯棒性等方面上，Q-Learning 在許多簡(jiǎn)單的連續(xù)問(wèn)題上表現(xiàn)較差［18］，而TRPO 相對(duì)復(fù)雜，并且與包含噪聲或者參數(shù)共享的架構(gòu)不兼容。因此，研究人員在策略梯度算法的基礎(chǔ)上結(jié)合TRPO的優(yōu)勢(shì)，提出一種PPO 算法。

不同于基于Q值的強(qiáng)化學(xué)習(xí)算法，PPO 算法［6］將模型參數(shù)定義在策略函數(shù)［19］中：

式（4）表示在t時(shí)刻狀態(tài)為s，參數(shù)向量為θ時(shí)，模型選擇動(dòng)作a的概率。通過(guò)更新參數(shù)向量θt，可得到更優(yōu)的策略函數(shù)，從而使得回報(bào)函數(shù)最大化。

但在訓(xùn)練過(guò)程中，不合適的學(xué)習(xí)率可能會(huì)導(dǎo)致較差的模型表現(xiàn)。為解決此問(wèn)題，PPO 使用GAE 函數(shù)［20］對(duì)優(yōu)勢(shì)函數(shù)進(jìn)行了多步估計(jì)，并利用衰減因子進(jìn)行組合，將偏差控制到一定的范圍內(nèi)。k步優(yōu)勢(shì)估計(jì)公式和廣義優(yōu)勢(shì)函數(shù)估計(jì)GAE（γ，λ）為：

同時(shí)，為了使該方法具有更高的數(shù)據(jù)效率性和魯棒性，PPO 提出了包含裁剪概率比率的策略網(wǎng)絡(luò)目標(biāo)函數(shù)，該函數(shù)確保了策略性能的悲觀估計(jì)（即下限）。令rt（θ）表示新舊策略概率比，即：

結(jié)合上述GAE 優(yōu)勢(shì)函數(shù)，PPO 提出的主要目標(biāo)函數(shù)如下：

其中：clip（rt（θ），1-ε，1+ε）是裁剪函數(shù)，對(duì)新舊策略更新過(guò)大的情況進(jìn)行裁剪，使得rt（θ）穩(wěn)定在［1-ε，1+ε］區(qū)間。

1.4 多任務(wù)學(xué)習(xí)

傳統(tǒng)的機(jī)器學(xué)習(xí)方法基于單任務(wù)學(xué)習(xí)的模式進(jìn)行學(xué)習(xí)，處理復(fù)雜任務(wù)時(shí)會(huì)將其分解為多個(gè)獨(dú)立的單任務(wù)，這種做法具有可行性，但忽略了任務(wù)之間的信息聯(lián)系。通過(guò)任務(wù)之間的共享表示和信息聯(lián)系，能夠使模型更好地概括原始任務(wù)，這種方式稱(chēng)為多任務(wù)學(xué)習(xí)［21］，其被應(yīng)用于自然語(yǔ)言處理［22］、語(yǔ)音識(shí)別［23］、計(jì)算機(jī)視覺(jué)［24］和強(qiáng)化學(xué)習(xí)等各種領(lǐng)域。例如，針對(duì)三維裝箱問(wèn)題中較少的信息量和較大的動(dòng)作空間的情況，YUAN等［25］將原始任務(wù)劃分為序列、方向和位置3 個(gè)有信息聯(lián)系的子任務(wù)，并基于深度強(qiáng)化學(xué)習(xí)的方法順序處理3 個(gè)子任務(wù)，該算法采用了多模態(tài)編碼器-解碼器的架構(gòu)。

本文通過(guò)深度強(qiáng)化學(xué)習(xí)的方法同時(shí)對(duì)堆垛機(jī)調(diào)度和庫(kù)位推薦問(wèn)題進(jìn)行聯(lián)合求解，其聯(lián)合目標(biāo)是在多問(wèn)題環(huán)境中獲得最大化累計(jì)回報(bào)值。

2 倉(cāng)儲(chǔ)問(wèn)題

本文考慮了倉(cāng)庫(kù)貨物存取的調(diào)度問(wèn)題。三維倉(cāng)儲(chǔ)模型如圖1 所示，整個(gè)倉(cāng)庫(kù)對(duì)象體系包含堆垛機(jī)（即小車(chē)）、通道、內(nèi)外層庫(kù)位、入庫(kù)點(diǎn)和出庫(kù)點(diǎn)。堆垛機(jī)在通道中移動(dòng)并根據(jù)訂單需求進(jìn)行存貨和取貨，同時(shí)在入庫(kù)點(diǎn)（出庫(kù)點(diǎn)）進(jìn)行入庫(kù)（出庫(kù)）。因此，堆垛機(jī)有關(guān)貨物的動(dòng)作分為2 類(lèi)：1）裝貨，即將貨物裝入堆垛機(jī)中，包括上述的入庫(kù)操作和取貨操作；2）卸貨，即從堆垛機(jī)中卸下貨物，包括出庫(kù)操作和存貨操作。入庫(kù)是指堆垛機(jī)從入庫(kù)點(diǎn)載入貨物，出庫(kù)是指堆垛機(jī)在出庫(kù)點(diǎn)卸下貨物，存儲(chǔ)貨物是指將貨物存儲(chǔ)進(jìn)庫(kù)位中，取出貨物是指從庫(kù)位中拿出貨物并置于車(chē)上。

圖1 三維倉(cāng)儲(chǔ)模型示意圖Fig.1 Schematic diagram of 3D warehouse model

堆垛機(jī)調(diào)度問(wèn)題的目標(biāo)是以盡可能小的堆垛機(jī)運(yùn)行代價(jià)滿(mǎn)足盡可能多的訂單存取需求，公式化為：

其中：、、、分別表示堆垛機(jī)每次運(yùn)行的移動(dòng)代價(jià)、執(zhí)行代價(jià)、時(shí)間代價(jià)和成功裝卸貨物得到的收益。

移動(dòng)代價(jià)是指堆垛機(jī)在倉(cāng)儲(chǔ)環(huán)境中移動(dòng)的開(kāi)銷(xiāo)，即：

其中：nnums表示執(zhí)行了該動(dòng)作的堆垛機(jī)數(shù)量。

執(zhí)行代價(jià)是指當(dāng)堆垛機(jī)執(zhí)行了裝貨和卸貨操作時(shí)的開(kāi)銷(xiāo)，即：

其中：nnum是存取操作下的貨物數(shù)量。

時(shí)間代價(jià)是指堆垛機(jī)沒(méi)有執(zhí)行操作時(shí)的空耗的開(kāi)銷(xiāo)，即：

堆垛機(jī)完成裝貨、卸貨時(shí)都會(huì)獲得相應(yīng)的收益：

本節(jié)包含的常量及其釋義如表1 所示。

表1 部分相關(guān)常量的對(duì)應(yīng)含義 Table 1 Corresponding meanings of some of the related constants

3 模型構(gòu)建

針對(duì)以上問(wèn)題，本文對(duì)環(huán)境中的狀態(tài)空間、動(dòng)作空間和獎(jiǎng)懲規(guī)則這三大要素進(jìn)行了定義。

3.1 狀態(tài)空間

狀態(tài)空間是調(diào)度過(guò)程中所有狀態(tài)的集合，狀態(tài)特征是對(duì)狀態(tài)屬性的數(shù)值表示?？梢詫顟B(tài)特征表示為一個(gè)三維矩陣的形式；第一維和第二維記錄了倉(cāng)庫(kù)的平面信息，包括該平面層倉(cāng)儲(chǔ)庫(kù)位的使用情況、出入庫(kù)點(diǎn)位置和貨物信息、堆垛機(jī)位置及承載情況；第三維主要記錄了垂直方向的層信息。觀測(cè)的信息包括：

與倉(cāng)庫(kù)相關(guān)的觀測(cè)信息如下：

與堆垛機(jī)相關(guān)的觀測(cè)信息如下：

最終智能體觀察到的狀態(tài)信息為：

3.2 動(dòng)作空間

在堆垛機(jī)調(diào)度任務(wù)中，智能體可采取的動(dòng)作為調(diào)度動(dòng)作。在堆垛機(jī)調(diào)度和庫(kù)位優(yōu)化的聯(lián)合任務(wù)中，智能體可采取的動(dòng)作分為調(diào)度動(dòng)作和庫(kù)位動(dòng)作兩類(lèi)。

3.2.1 調(diào)度動(dòng)作空間

在堆垛機(jī)調(diào)度問(wèn)題中，智能體執(zhí)行的動(dòng)作與堆垛機(jī)移動(dòng)和貨物存取操作相關(guān)聯(lián)，共有以下5 類(lèi)動(dòng)作：

1）Idle：堆垛機(jī)在原地待命。

2）Forward：在通道中前進(jìn)，方向?yàn)閺娜霂?kù)點(diǎn)到出庫(kù)點(diǎn)；若在通道中最靠近出庫(kù)點(diǎn)的位置，則移動(dòng)至出庫(kù)點(diǎn)。

3）Backward：在通道中后退，方向?yàn)閺某鰩?kù)點(diǎn)到入庫(kù)點(diǎn)；若在通道中最靠近入庫(kù)點(diǎn)的位置，則移動(dòng)至入庫(kù)點(diǎn)。

4）Load：在入庫(kù)點(diǎn)的位置，將貨物裝入堆垛機(jī)中；若在通道中，則找到距離最近的待取貨庫(kù)位，從中取出貨物。

5）Unload：在出庫(kù)點(diǎn)的位置，堆垛機(jī)卸下貨物；若在通道中，則找到距離最近的空余庫(kù)位，并往庫(kù)位中儲(chǔ)存貨物（就近原則只應(yīng)用在調(diào)度環(huán)境中）。

調(diào)度動(dòng)作以向量a=(ac1，ac2，…，aci，…，acN)形 式表示，aci是對(duì)應(yīng)堆垛機(jī)ci的動(dòng)作值，ci∈C。

3.2.2 庫(kù)位動(dòng)作空間

在調(diào)度和庫(kù)位優(yōu)化的雙重問(wèn)題中，調(diào)度動(dòng)作Unload 進(jìn)行存儲(chǔ)貨物的操作時(shí)，存儲(chǔ)位置的選擇由庫(kù)位推薦網(wǎng)絡(luò)來(lái)處理。庫(kù)位優(yōu)化的動(dòng)作信息由向量(bc1，bc2，…，bci，…，bcN)表示，bci是對(duì)應(yīng)堆垛機(jī)ci的庫(kù)位動(dòng)作值，bci∈{IL，AL，AR，IR}，如圖2 所示的IL、AL、AR 和IR，其物理意義如下：

圖2 平面?zhèn)}儲(chǔ)模型示意圖Fig.2 Schematic diagram of plane storage model

1）IL（Inner-Left）：當(dāng)前堆垛機(jī)的左側(cè)貨架中遠(yuǎn)離通道的庫(kù)位。

2）AL（Aisle-Left）：當(dāng)前堆垛機(jī)的左側(cè)貨架中靠近通道的庫(kù)位。

3）AR（Aisle-Right）：當(dāng)前堆垛機(jī)的右側(cè)貨架中靠近通道的庫(kù)位。

4）IR（Inner-Right）：當(dāng)前堆垛機(jī)的右側(cè)貨架中遠(yuǎn)離通道的庫(kù)位。

3.3 獎(jiǎng)懲規(guī)則

在智能體與環(huán)境交互的過(guò)程中，獎(jiǎng)勵(lì)函數(shù)決定了環(huán)境對(duì)智能體的行為給出的反饋，該反饋用以指導(dǎo)智能體學(xué)習(xí)。令A(yù)ction=｛Idle，F(xiàn)orward，Backward，Load，Unload｝表示動(dòng)作選項(xiàng)集合?；谑剑?）的任務(wù)目標(biāo)，對(duì)于智能體的動(dòng)作a，本文定義其對(duì)應(yīng)的反饋如下：

其中：cmovement為N輛堆垛機(jī)移動(dòng)代價(jià)的總和；caction是執(zhí)行代價(jià)的總和；ctime是時(shí)間代價(jià)的總和。計(jì)算公式分別如下：

其中：l表示貨架層數(shù)，當(dāng)l為0時(shí)，對(duì)應(yīng)的是入庫(kù)（出庫(kù)）代價(jià)。

g是裝貨、卸貨收益的總和：

其中：nnum指的是成功處理的貨物數(shù)量。

4 網(wǎng)絡(luò)模型設(shè)計(jì)

4.1 整體結(jié)構(gòu)

繼承于Actor-Critic（AC）架構(gòu)，基于PPO 強(qiáng)化學(xué)習(xí)算法的堆垛機(jī)調(diào)度網(wǎng)絡(luò)分為調(diào)度Actor 網(wǎng)絡(luò)和Critic 網(wǎng)絡(luò)，如圖3 所示，下文簡(jiǎn)稱(chēng)為調(diào)度網(wǎng)絡(luò)。

圖3 網(wǎng)絡(luò)模型整體架構(gòu)Fig.3 Overall architecture of network model

在多任務(wù)的情況下，除堆垛機(jī)調(diào)度外，還包括庫(kù)位推薦。所以，在原有的AC 框架下，本文引入了額外的庫(kù)位Actor 網(wǎng)絡(luò)用于庫(kù)位推薦，整體對(duì)應(yīng)的是基于多任務(wù)強(qiáng)化學(xué)習(xí)的調(diào)度、庫(kù)位推薦聯(lián)合算法的網(wǎng)絡(luò)模型，簡(jiǎn)寫(xiě)為多任務(wù)網(wǎng)絡(luò)。

4.2 堆垛機(jī)調(diào)度網(wǎng)絡(luò)

4.2.1 網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)

根據(jù)目標(biāo)函數(shù)式（8），構(gòu)造一個(gè)Actor 網(wǎng)絡(luò)來(lái)生成調(diào)度行為策略，即圖3 中的調(diào)度Actor 網(wǎng)絡(luò)。網(wǎng)絡(luò)的輸入為3.1 節(jié)提到的狀態(tài)空間S，網(wǎng)絡(luò)的輸出為調(diào)度動(dòng)作的概率向量。

構(gòu)造一個(gè)Critic 網(wǎng)絡(luò)用于表示狀態(tài)值函數(shù)，網(wǎng)絡(luò)的輸入為狀態(tài)空間S，網(wǎng)絡(luò)的輸出為對(duì)應(yīng)狀態(tài)的狀態(tài)估計(jì)值。

4.2.2 Actor 和Critic 網(wǎng)絡(luò)設(shè)計(jì)

在強(qiáng)化學(xué)習(xí)中，策略網(wǎng)絡(luò)和值函數(shù)網(wǎng)絡(luò)通常是少量的全連接層或者全卷積層，因?yàn)檫^(guò)于復(fù)雜的網(wǎng)絡(luò)層數(shù)會(huì)造成模型難以收斂。例如，PPO 在多個(gè)實(shí)驗(yàn)中使用了兩層各64 個(gè)單元的全連接層。

倉(cāng)儲(chǔ)問(wèn)題環(huán)境具有三維狀態(tài)空間信息的特點(diǎn)，狀態(tài)空間記錄了入庫(kù)點(diǎn)信息、貨物信息等。每個(gè)庫(kù)位狀態(tài)表示具有相似性，所以在類(lèi)似的庫(kù)位狀態(tài)下可以采用類(lèi)似的策略安排貨物，而卷積可以對(duì)相似空間中的明顯數(shù)值特征進(jìn)行提取。因此，本文在輸入層后加入了卷積層和池化層。

同時(shí)為了簡(jiǎn)化計(jì)算過(guò)程、并保證網(wǎng)絡(luò)的輸入固定在一定范圍內(nèi)，緩解梯度消失，加速模型收斂，本文引入批標(biāo)準(zhǔn)化［26］處理，用以規(guī)范化網(wǎng)絡(luò)的輸入?；诰矸e層和批標(biāo)準(zhǔn)化層的引入，本文調(diào)度網(wǎng)絡(luò)模型命名為PPO-CB。如圖3 中的調(diào)度Actor 網(wǎng)絡(luò)和Critic 網(wǎng)絡(luò)所示。

4.2.3 動(dòng)作策略函數(shù)

為了使調(diào)度問(wèn)題中的輸出更具有穩(wěn)定性，本文在PPO 算法的基礎(chǔ)上，用Log-Softmax 函數(shù)重新定義目標(biāo)函數(shù)中的策略函數(shù)，公式如下：

其中：φ（s，a）表示與狀態(tài)和動(dòng)作輸入相關(guān)的向量；πθ表示參數(shù)向量；N為動(dòng)作選項(xiàng)的總數(shù)。

基于該動(dòng)作策略函數(shù)，調(diào)度動(dòng)作從概率分布中進(jìn)行采樣。相較于Softmax 方法定義的策略函數(shù)，Log-Softmax 函數(shù)在數(shù)值穩(wěn)定性、優(yōu)化性和懲罰等方面有更好的表現(xiàn)。

與其他深度強(qiáng)化學(xué)習(xí)算法類(lèi)似，PPO 算法也采用了緩沖庫(kù)（Buffer）的思想。在每輪網(wǎng)絡(luò)開(kāi)始訓(xùn)練之前，將上一輪訓(xùn)練后的動(dòng)作策略與環(huán)境進(jìn)行交互，從而獲取樣本數(shù)據(jù)，同時(shí)計(jì)算狀態(tài)估計(jì)值和優(yōu)勢(shì)值，最終將以上相關(guān)數(shù)據(jù)存儲(chǔ)至緩沖庫(kù)中，以備訓(xùn)練需求。另外，在本輪訓(xùn)練結(jié)束后，會(huì)清空緩沖庫(kù)中所有數(shù)據(jù)。

相比較其他基于緩沖庫(kù)的算法，PPO 算法根據(jù)裁剪目標(biāo)函數(shù)有效地避免了訓(xùn)練前后策略差異過(guò)大的情況，從而提升了采樣效率。

4.2.4 算法流程

基于PPO 的堆垛機(jī)調(diào)度算法主要內(nèi)容包括：1）收集智能體在倉(cāng)儲(chǔ)環(huán)境中的交互數(shù)據(jù)，并存儲(chǔ)至緩沖庫(kù)中；2）多次調(diào)用緩沖庫(kù)中的數(shù)據(jù)并反向訓(xùn)練神經(jīng)網(wǎng)絡(luò)，以獲得良好的調(diào)度策略。

算法1基于PPO 的堆垛機(jī)調(diào)度算法

輸入初始環(huán)境信息S0，訓(xùn)練迭代次數(shù)K，學(xué)習(xí)率η，超參數(shù)γ、ε

輸出Actor 網(wǎng)絡(luò)參數(shù)θ，Critic 網(wǎng)絡(luò)參數(shù)φ

1.初始化Actor 網(wǎng)絡(luò)的策略參數(shù)θ0和Critic 網(wǎng)絡(luò)的值函數(shù)參數(shù)φ0，初始化數(shù)據(jù)緩沖庫(kù)，大小為M。

2.從第k 次回合開(kāi)始進(jìn)行迭代（k=0，1，…，K）。

3.初始化累計(jì)回報(bào)值為0，初始化入庫(kù)點(diǎn)貨物數(shù)量、堆垛機(jī)初始位置和貨架庫(kù)位等信息。

4.在環(huán)境中運(yùn)行策略，與環(huán)境交互輸出動(dòng)作，獲得對(duì)應(yīng)的獎(jiǎng)勵(lì)，計(jì)算狀態(tài)估計(jì)值和優(yōu)勢(shì)估計(jì)值，并在緩沖庫(kù)中存儲(chǔ)當(dāng)前狀態(tài)動(dòng)作序列和相關(guān)數(shù)值。根據(jù)以上步驟收集容量為M 的數(shù)據(jù)量。

5.從緩沖庫(kù)中讀取樣本數(shù)據(jù)。通過(guò)最大化目標(biāo)函數(shù)來(lái)更新策略，并得到參數(shù)θk+1，此處使用隨機(jī)梯度上升的方法；通過(guò)均方誤差函數(shù)來(lái)回歸擬合值函數(shù)，并得到參數(shù)φk+1，此處使用梯度下降的方法。

6.結(jié)束當(dāng)前回合，進(jìn)入下一個(gè)回合。

7.結(jié)束。

4.3 多任務(wù)學(xué)習(xí)網(wǎng)絡(luò)

4.3.1 網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)

庫(kù)位推薦的網(wǎng)絡(luò)同樣是一個(gè)策略網(wǎng)絡(luò)，因此，構(gòu)建一個(gè)Actor 網(wǎng)絡(luò)來(lái)生成庫(kù)位推薦的策略。網(wǎng)絡(luò)的輸入為多任務(wù)問(wèn)題環(huán)境中觀察到的狀態(tài)空間，網(wǎng)絡(luò)的輸出為庫(kù)位動(dòng)作的概率向量。在多任務(wù)問(wèn)題下，環(huán)境除了堆垛機(jī)調(diào)度之外還包含了庫(kù)位相關(guān)因素。

在多任務(wù)環(huán)境（即包含堆垛機(jī)調(diào)度和庫(kù)位問(wèn)題的環(huán)境）中，兩個(gè)任務(wù)是互相影響的個(gè)體，調(diào)度Actor網(wǎng)絡(luò)和庫(kù)位Actor 網(wǎng)絡(luò)與狀態(tài)值函數(shù)的Critic 網(wǎng)絡(luò)有著直接的關(guān)聯(lián)。

當(dāng)智能體選擇的調(diào)度動(dòng)作為Unload（且為存儲(chǔ)貨物）時(shí)，庫(kù)位Actor 網(wǎng)絡(luò)根據(jù)環(huán)境中狀態(tài)信息輸出位置推薦，共同對(duì)環(huán)境施加影響，進(jìn)而得到reward 反饋；Critic 網(wǎng)絡(luò)根據(jù)reward 值進(jìn)行狀態(tài)值的估計(jì)和優(yōu)勢(shì)值的計(jì)算。同時(shí)，該狀態(tài)估計(jì)值和估計(jì)優(yōu)勢(shì)值會(huì)作為相關(guān)反饋值，參與到兩個(gè)Actor 網(wǎng)絡(luò)的目標(biāo)函數(shù)的參數(shù)訓(xùn)練，整體過(guò)程如圖3 所示。本文多任務(wù)網(wǎng)絡(luò)模型命名為PPO-CB-store。

4.3.2 算法流程

基于多任務(wù)學(xué)習(xí)的調(diào)度、庫(kù)位推薦聯(lián)合算法主要內(nèi)容包括：1）初始化雙Actor 網(wǎng)絡(luò)和Critic 網(wǎng)絡(luò)參數(shù)，構(gòu)建多任務(wù)網(wǎng)絡(luò)架構(gòu)；2）庫(kù)位動(dòng)作和調(diào)度動(dòng)作產(chǎn)生聯(lián)動(dòng)關(guān)系，并收集智能體在多任務(wù)問(wèn)題環(huán)境中的交互數(shù)據(jù)，存儲(chǔ)至緩沖庫(kù)中；3）多次調(diào)用緩沖庫(kù)中數(shù)據(jù)并訓(xùn)練神經(jīng)網(wǎng)絡(luò)，以獲得基于堆垛機(jī)調(diào)度和庫(kù)位推薦的策略。

算法2基于多任務(wù)學(xué)習(xí)的堆垛機(jī)調(diào)度和庫(kù)位推薦算法

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

5.1 實(shí)驗(yàn)環(huán)境和網(wǎng)絡(luò)參數(shù)設(shè)置

本文算法基于Python 語(yǔ)言與Tensorflow2.5 框架實(shí)現(xiàn)，并基于OpenAI-Gym 庫(kù)對(duì)倉(cāng)儲(chǔ)環(huán)境和堆垛機(jī)調(diào)度及庫(kù)位問(wèn)題進(jìn)行建模。

在本文模型的網(wǎng)絡(luò)結(jié)構(gòu)中，Actor 網(wǎng)絡(luò)第1 層為輸入層，接著是卷積層、標(biāo)準(zhǔn)化層、池化層，之后是三層全連接層和輸出層。Critic 網(wǎng)絡(luò)的后半部分對(duì)應(yīng)的是2 個(gè)全連接層，最終輸出的是狀態(tài)估計(jì)值，如圖3 所示。參數(shù)設(shè)置如表2 所示。

表2 網(wǎng)絡(luò)模型的部分參數(shù)設(shè)置 Table 2 Some parameter settings of the network model

5.2 問(wèn)題環(huán)境設(shè)置

實(shí)驗(yàn)主要分為調(diào)度問(wèn)題實(shí)驗(yàn)和多任務(wù)問(wèn)題實(shí)驗(yàn)2 個(gè)部分。相對(duì)應(yīng)的環(huán)境實(shí)例有調(diào)度環(huán)境和多任務(wù)問(wèn)題環(huán)境2類(lèi)。環(huán)境中的部分參數(shù)設(shè)置如表3所示。

表3 倉(cāng)儲(chǔ)環(huán)境參數(shù)設(shè)置 Table 3 Parameter Settings of environment parameters

調(diào)度環(huán)境對(duì)應(yīng)的動(dòng)作信息為調(diào)度動(dòng)作空間，實(shí)例標(biāo)識(shí)為“l(fā)evel 數(shù)量×section數(shù)量×shelf數(shù)量”，以圖1 為例，該倉(cāng)儲(chǔ)環(huán)境實(shí)例有3 層貨架（level 數(shù)量為3）、2 條通道和8 排貨架（總和section 數(shù)量為10），每個(gè)通道對(duì)應(yīng)4 排貨架，即兩側(cè)各有2 排內(nèi)外層的貨架；每排貨架各有3 個(gè)庫(kù)位（shelf 數(shù)量為3），將其標(biāo)識(shí)為“3×10×3”。

多任務(wù)問(wèn)題環(huán)境對(duì)應(yīng)的動(dòng)作信息為調(diào)度動(dòng)作空間和庫(kù)位動(dòng)作空間，加前綴“S-”表示。

5.3 堆垛機(jī)調(diào)度實(shí)驗(yàn)分析

為驗(yàn)證調(diào)度模型算法的有效性，對(duì)表4 中所有實(shí)例進(jìn)行實(shí)驗(yàn)，改進(jìn)模型算法在表中標(biāo)記為PPOCB。其中，PPO-CB、PPO 對(duì)每個(gè)實(shí)例分別進(jìn)行訓(xùn)練以及測(cè)試。在當(dāng)前實(shí)驗(yàn)中，最大累計(jì)回報(bào)信息作為評(píng)價(jià)指標(biāo)。選用Ran（隨機(jī)采樣方法）、基于概率規(guī)劃的SOG 算法、粒子群優(yōu)化算法PSO、PPO 與本文算法進(jìn)行比較。在粒子群優(yōu)化算法［27］中，初始種群大小為200，最大迭代次數(shù)為1 000。算例實(shí)驗(yàn)對(duì)比情況如表4 所示，其中，最優(yōu)調(diào)度結(jié)果以粗體顯示，—表示計(jì)算時(shí)間嚴(yán)重超時(shí)，無(wú)法求解。同時(shí)為了驗(yàn)證改進(jìn)網(wǎng)絡(luò)中新增的不同因素帶來(lái)的影響，對(duì)基于批標(biāo)準(zhǔn)化的PPO 模型和基于卷積的PPO 模型分別進(jìn)行實(shí)驗(yàn)，分別標(biāo)記為PPO（BN）和PPO（CNN）。相較于PPO-CB，PPO（BN）不包括卷積和池化層，PPO（CNN）不包括批標(biāo)準(zhǔn)化層。

表4 調(diào)度問(wèn)題實(shí)驗(yàn)結(jié)果對(duì)比 Table 4 Comparison of experimental results of scheduling problems

分析表4 可知，本文方法模型PPO-CB 在實(shí)例環(huán)境中的表現(xiàn)明顯優(yōu)于基礎(chǔ)的Ran 算法。同時(shí)相較于原PPO 算法模型，本文模型雖然在1×5×5 和1×5×10實(shí)例中與原方法差距不大，但在其他實(shí)例環(huán)境中都有明顯的提升。基于概率規(guī)劃的SOG 算法在前兩個(gè)小型實(shí)例環(huán)境中取得較好的效果，但在更大狀態(tài)空間的實(shí)例環(huán)境中，效果逐漸趨同于Ran 算法，甚至無(wú)法求解。本文算法模型相較于粒子群算法PSO，在所有實(shí)例中都有著不同程度的提升，尤其是在2×10×20、2×20×10 和2×20×20 的實(shí)例中提升較大。

在不同因素的驗(yàn)證實(shí)驗(yàn)中，相較于原PPO 算法模型，PPO（BN）雖然在1×10×10、2×5×5 和2×5×20 實(shí)例環(huán)境略差于原算法模型，但在其他大多數(shù)環(huán)境中都能高于原算法模型，程度不一；而PPO（CNN）在大多數(shù)環(huán)境中，表現(xiàn)效果都為良好。

由表4 可知，在2×10×20 實(shí)例中，PPO-CB相較于原算法模型，其平均累計(jì)回報(bào)值提升最為明顯，提升了58%，其隨著迭代次數(shù)的增加逐漸收斂于較高的回報(bào)值，如圖4 所示。在1×5×10 實(shí)例中，PPO-CB的提升效果最弱，其收斂曲線(xiàn)略微高于原方法，平均累計(jì)回報(bào)值只提升了8.9%，如圖5 所示。綜合表4 中所有實(shí)例的數(shù)據(jù)，可計(jì)算得到PPO-CB 相較于原PPO算法能收斂于更高的累計(jì)回報(bào)值，平均提升了33.6%。

圖4 2×10×20 調(diào)度問(wèn)題實(shí)例中累計(jì)回報(bào)值的訓(xùn)練迭代對(duì)比Fig.4 Training iteration comparison of cumulative reward values in 2×10×20 scheduling problem instances

圖5 1×5×10 調(diào)度問(wèn)題實(shí)例中累計(jì)回報(bào)值的訓(xùn)練迭代對(duì)比Fig.5 Training iteration comparison of cumulative reward values in 1×5×10 scheduling problem instances

在本文實(shí)驗(yàn)中，實(shí)例輸入的狀態(tài)空間與對(duì)應(yīng)倉(cāng)庫(kù)環(huán)境大小呈正相關(guān)，同時(shí)動(dòng)作空間的大小與對(duì)應(yīng)環(huán)境中的堆垛機(jī)通道數(shù)量有直接關(guān)聯(lián)，所以不同實(shí)例之間的狀態(tài)、動(dòng)作空間的規(guī)模差別較大。例如，實(shí)例1×5×10 與1×20×20 之間的庫(kù)位數(shù)量相差了16倍，通道數(shù)量相差了4倍。因此，在面向模型訓(xùn)練時(shí)，不同實(shí)例的輸入輸出規(guī)模均不相同，所以需要對(duì)每個(gè)實(shí)例分別進(jìn)行訓(xùn)練和測(cè)試。

在基于不同方法的實(shí)驗(yàn)時(shí)間對(duì)比中，PPO 類(lèi)算法整體求解時(shí)間明顯比常規(guī)方法較長(zhǎng)，因?yàn)樾枰獙?duì)實(shí)例進(jìn)行訓(xùn)練。相較于原PPO 算法模型，PPO-CB 相對(duì)復(fù)雜的網(wǎng)絡(luò)架構(gòu)導(dǎo)致訓(xùn)練時(shí)間更長(zhǎng)，其最短訓(xùn)練時(shí)間為34 min，最長(zhǎng)為63 min，如表5 所示。

表5 實(shí)驗(yàn)平均時(shí)間對(duì)比 Table 5 Comparison of experimental mean time

綜合而言，本文提出的改進(jìn)模型算法在大多數(shù)實(shí)例環(huán)境中表現(xiàn)良好，同時(shí)可以對(duì)較大狀態(tài)空間的實(shí)例環(huán)境進(jìn)行求解。

5.4 調(diào)度和庫(kù)位問(wèn)題實(shí)驗(yàn)分析

為驗(yàn)證多任務(wù)模型算法的可行性，對(duì)表6 中實(shí)例進(jìn)行實(shí)驗(yàn)，多任務(wù)模型在表中標(biāo)記為PPO-CB-store。在當(dāng)前實(shí)驗(yàn)中，最大累計(jì)回報(bào)值作為評(píng)價(jià)指標(biāo)。在該部分實(shí)驗(yàn)，主要驗(yàn)證該算法的可行性。選用Ran（隨機(jī)采樣方法）作為對(duì)比，實(shí)驗(yàn)效果情況如表6 所示，其中最優(yōu)調(diào)度結(jié)果用粗體顯示。

表6 多任務(wù)問(wèn)題實(shí)驗(yàn)結(jié)果對(duì)比 Table 6 Experimental results for multi-task problems

由表6 分析可知，PPO-CB-store 在實(shí)例環(huán)境中能夠有正面的效果表現(xiàn)，且相對(duì)于Ran 這種基礎(chǔ)的抽樣方法有著明顯的提升。同時(shí)隨著實(shí)例規(guī)模的擴(kuò)大，PPO-CB-store 依然能夠求解實(shí)例問(wèn)題，驗(yàn)證了該方法的可行性。

圖6和圖7 分別為PPO-CB-store 在2×10×10 和2×10×20 實(shí)例環(huán)境中累計(jì)回報(bào)值隨迭代次數(shù)變化的曲線(xiàn)。

圖6 2×10×10 多任務(wù)問(wèn)題實(shí)例中累計(jì)回報(bào)值的迭代對(duì)比Fig.6 Iteration comparison of cumulative reward values in 2×10×10 multi-task problem instances

圖7 2×10×20 多任務(wù)問(wèn)題實(shí)例中累計(jì)回報(bào)值的迭代對(duì)比Fig.7 Iteration comparison of cumulative reward values in 2×10×20 multi-task problem instances

從圖6 和圖7 中分析可知：PPO-CB-store 在迭代過(guò)程中可以收斂至較高的累計(jì)回報(bào)值，并且能有效地應(yīng)對(duì)調(diào)度和庫(kù)位優(yōu)化的多任務(wù)場(chǎng)景。

6 結(jié)束語(yǔ)

本文針對(duì)倉(cāng)儲(chǔ)環(huán)境問(wèn)題進(jìn)行建模，提出一種基于深度強(qiáng)化學(xué)習(xí)算法的堆垛機(jī)調(diào)度算法，來(lái)實(shí)現(xiàn)倉(cāng)儲(chǔ)環(huán)境問(wèn)題在PPO 強(qiáng)化學(xué)習(xí)算法中的應(yīng)用，同時(shí)針對(duì)倉(cāng)儲(chǔ)系統(tǒng)中衍生的庫(kù)位優(yōu)化問(wèn)題，提出基于多任務(wù)學(xué)習(xí)的算法模型，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該模型的可行性，為該類(lèi)多任務(wù)問(wèn)題提供一個(gè)有效的解決方案。由于不同實(shí)例的狀態(tài)空間規(guī)模不相同，因此在求解時(shí)間方面仍存在不足，下一步將考慮引入編碼器-解碼器架構(gòu)，使單個(gè)網(wǎng)絡(luò)模型能夠?qū)Χ鄠€(gè)實(shí)例進(jìn)行訓(xùn)練，從而減少重復(fù)訓(xùn)練，并將模型遷移到未曾訓(xùn)練過(guò)的實(shí)例中實(shí)現(xiàn)模型的復(fù)用，以從根本上降低求解時(shí)間。