智能倉儲中的多機器人調度方法

王振庭，陳永府，劉 田

(華中科技大學機械科學與工程學院，湖北 武漢 430074)

0 引 言

在傳統(tǒng)的倉儲環(huán)境下，大多數(shù)時間都耗費在揀選貨物的過程之中。而在傳統(tǒng)的“人到貨”的運行模式下，人工出錯率較高，進而降低了倉儲物流效率。隨著電商行業(yè)的迅速發(fā)展，企業(yè)對物流效率和準確度提出了更高的要求?，F(xiàn)代倉儲系統(tǒng)已經(jīng)逐漸向“貨到人”[1]的運行模式進行轉變，使用倉儲物流機器人[2]將貨物直接送至揀選臺，大幅度提高了作業(yè)效率并減輕了工人的勞動強度。構建基于多移動機器人的智能倉儲系統(tǒng)已經(jīng)成為當下倉儲物流研究的一大熱點[3]。

多移動機器人的調度方式是構建智能倉儲平臺的關鍵。針對智能倉儲中的調度問題，國內外許多學者都展開了較多的研究并獲得了一定成果。在任務分配方法上，Sandholm[4]提出一種組合拍賣算法。李文玉[5]將調度問題看作一種非平衡指派問題，基于最鄰近算法思想設計了求解模型的啟發(fā)式算法，并利用匈牙利算法得到最優(yōu)指派方案。但該方案僅用于規(guī)模比較小的倉儲環(huán)境，未考慮任務增多時求解難度以指數(shù)形式增加，針對大型倉儲環(huán)境不能有效適用。Trigui等[6]提出了擴展的分布式市場化方法來解決機器人任務分配問題，通過交換任務來提高工作效率。但這種方法為局部調度方法，忽略了任務的全局性。Ma等[7]提出了將全局任務分組后重新分配的任務分組方法，將靜態(tài)的任務分配算法應用于動態(tài)環(huán)境中，提高了全局任務的均衡性。在路徑規(guī)劃方法上，沈博聞等[8]基于A*算法提出總分和考慮路徑代價和任務等待時間的機器人調度方法，實現(xiàn)了多機器人的靜態(tài)智能調度，但A*算法僅適用于小規(guī)模運算，無法解決多任務多機器人的情況。Sumii等[9]運用標準的A*搜索算法尋找最優(yōu)路徑，然而只能適用于可控的已知環(huán)境。宋勇等[10]利用人工勢場初始化Q值的方法提出了一種Q-learning算法，雖提高了算法的收斂度，但未考慮路徑的平滑度，規(guī)劃出的路徑仍存在較大的轉角。為了解決以上問題，本文提出一種將精英遺傳算法與Q-learning算法結合的調度算法。

1 問題描述

在智能倉儲的調度系統(tǒng)中，至關重要的環(huán)節(jié)就是多移動機器人[11]的任務調度和路徑規(guī)劃。其中，任務調度是指在智能倉儲環(huán)境下一系列任務合理分配給一定數(shù)量的機器人從而提高其任務執(zhí)行效率。而路徑規(guī)劃則是在任務分配后為每臺移動機器人規(guī)劃出合理的路徑，以減少機器人完成任務時的時間代價和路程代價以及減少機器人之間的路徑干涉，避免發(fā)生碰撞。

智能倉儲環(huán)境由貨架、機器人以及揀選臺構成。為了簡化模型，對倉儲環(huán)境進行柵格化處理[12]。整個倉儲環(huán)境由50個貨架、5臺移動機器人和1個揀選臺組成。每個貨架占據(jù)2個柵格，每個移動機器人占據(jù)一個柵格?？紤]到貨架的寬度，過道的寬度為2個柵格長度[13]。本文對該倉儲系統(tǒng)做出如下假設：

1)所有機器人的規(guī)格相同。

2)每個機器人均能獨立完成任務。

3)機器人移動方式為每次移動一個柵格，且動作只能上下左右移動。

4)機器人在揀選臺停留時間和在貨架挑選貨物時間為恒定值。

5)機器人移動速度恒定，但每次改變移動方向均會有一定的時間損耗。

6)為避免路線混亂，每一條直線柵格均為單行道，方向如圖1中的箭頭所示。

倉儲環(huán)境模型如圖1所示。

調度過程分2步進行：

1)通過任務調度算法將訂單中形成的待執(zhí)行任務列表分配給移動機器人，機器人得到訂單編號后便能得知貨物所在的貨架編號。

2)通過路徑規(guī)劃算法從當前位置移動到貨架位置，將貨架頂起后行駛到揀選臺由人工進行揀選。揀選完畢后機器人將貨架送回原地后待命，完成整個過程視為完成一個任務。

圖1 倉儲環(huán)境模型

假設有m個任務{t1,t2,…,tm}和n臺機器人{r1,r2,…,rn}，先將任務分為n組，即第i臺機器人分到任務{ti1,ti2,…,tik}。在任務分配過程中，由于行走方向只能為橫向或者縱向，且過道的方向性對計算路徑距離影響較小，因此距離計算采用曼哈頓距離。用dij表示初始時刻機器人從任務i對應的貨架行駛到任務j對應貨架的曼哈頓距離。用si表示機器人執(zhí)行任務i從貨架位置到揀選臺的距離。由于任務調度過程暫不考慮多機協(xié)同問題，因此算法由2個指標來優(yōu)化性能：最大時間代價T和總路程代價S。公式(1)表示性能公式：

(1)

路徑規(guī)劃過程考慮到多機協(xié)同作用，用另2個指標來優(yōu)化性能：轉身次數(shù)c和路徑重復率r。轉身次數(shù)表示機器人在路徑中變換方向的次數(shù)，由于機器人改變方向時會有所停頓，因此在路徑轉折點會有一定的懲罰值Pc。路徑重復率是指在多機路徑協(xié)調時路徑的重復度，由于重復度越高，機器人發(fā)生碰撞的幾率也會越高，因此規(guī)劃路徑時在路徑重復片段也會有一定的懲罰值Pr。最終為機器人規(guī)劃一條轉身次數(shù)少、路徑重復率低的路徑。

2 算法設計

隨著任務數(shù)量和機器人數(shù)量增加，多機調度問題上升為NP難問題[14]。針對遺傳算法[15]具有全局性能好、魯棒性高以及快速收斂的優(yōu)點，本文中任務調度部分采用了多層編碼精英遺傳算法進行任務分配。而Q-Learning算法[16]在未知的環(huán)境下?lián)碛懈鼜姶蟮淖灾鲗W習能力，因此路徑規(guī)劃部分采用Q-Learning算法。整個過程的流程如圖2所示。

圖2 算法過程圖

2.1 任務分配算法

如上文所述，任務分配算法采用的是多層編碼的精英遺傳算法[17]，具體如下：

編碼方式有許多種，包括二進制編碼、浮點數(shù)編碼、符號編碼等。這里直接以整數(shù)編碼形式對任務進行直觀編碼[18]。假設一批訂單需搬運100個貨架，即生成100個任務。任務編號即為需搬運的貨架號?？烧{度的移動機器人數(shù)量為5個，由于機器人無法一次完成所有任務，因此在任務中間需加入返回任務，任務編號設為101，指的是機器人完成較大工作量時必須返回到揀選臺卸下貨物。

形成初代種群：編碼方式確定后可以根據(jù)生成的任務形成初代種群，這里以5×20的矩陣表示每個種群中的個體，每個種群中包含50個個體。初代種群由1～100范圍的隨機數(shù)無重復隨機生成。通過計算適應度記錄初始種群中最優(yōu)個體和最差個體。將初代最優(yōu)個體記錄為歷代最優(yōu)個體。公式(2)和公式(3)表示初始種群中個體由[1,100]隨機組成一個5×20的矩陣。

初始個體形成：

ti,j=randprem(20)

(2)

(3)

其中，列序號表示機器人編號，行序號表示每個機器人需執(zhí)行的任務編號。

初代種群包含50個初代個體，因此初代種群形成一個5×20×50的三維矩陣。

在遺傳算法中，評價種群中個體好壞需要使用適應度函數(shù)來進行評價。個體的適應度函數(shù)越大，代表個體越優(yōu)秀。在這里先計算出某一個指標的值(這里取種群每個個體的最大行駛距離)，然后取倒數(shù)使該指標更小的占比更大，最后取十次方以強化差異。進行歸一化后可得到種群中每個個體的適應度的占比。占比重越大的具有越高概率被選擇進行種群雜交。公式(4)表示第g代第n個個體中的編號為r的機器人的距離代價，公式(5)取每個個體中距離代價最高的為Dgn。

公式表達：

(4)

Dgn=max(Dgnr),r=1,2,3,4,5

(5)

在選擇過程中選擇操作采用的是輪盤賭法[19]，從每個個體計算出的適應度出發(fā)，根據(jù)每代種群所計算出的每個個體的適應度所占比依概率進行選擇。輪盤賭法能保證優(yōu)秀個體更容易被選擇，也能保證不優(yōu)的個體有概率被選擇，選擇出的個體能夠進行下一步操作。這樣既能保證種群的多樣性，又有助于算法的收斂。選擇操作公式如下：

(6)

(7)

公式(6)將距離代價取倒數(shù)，并取三次方進行強化差異。得到每個種群的適應度。公式(7)將適應度進行歸一化，便于進行選擇操作。得到的fgn即種群中每個個體的選擇概率。

在交叉過程中如果完全將相同部位片段進行交換，大概率會出現(xiàn)重復基因。因此交叉方式采用部分映射交叉，即從待交叉?zhèn)€體中選擇相同部位的基因片段進行交換。然后根據(jù)2組基因的映射關系做沖突檢測[20]。映射過程如下：

父代1與父代2片段交換后：

顯然交換后有重復片段，此時子代1中非交叉段基因在父代2中找到相同基因，并在父代1中可找到該基因位置對應的基因。比如子代1的第一個基因1，在父代2中的基因1對應父代1的基因6，于是第一個位置的基因替換成6。同理，6也屬于重復基因，于是在父代1中找到對應基因3，替換成3，直到無重復為止。最終完成沖突檢測的子代基因為：

變異過程有多種方式，包括2點交換和基因間的翻轉。這里采用選擇2點間的基因翻轉，如上面第一個子代翻轉后染色體變?yōu)椋?/p>

由于染色體的交叉和變異操作是為了增加種群的個體多樣性。交叉操作用于判定2個個體是否進行交叉，此實驗中交叉概率Pc選取0.9，而變異操作則是允許少數(shù)個體存在突變情況，以避免陷入局部最優(yōu)解，本實驗變異概率Pm選取0.1。

經(jīng)過上面的交叉變異后得到了一個新的種群，計算新種群中各個個體的適應度，同樣記錄最好個體與最差個體。并將當代最優(yōu)個體與歷代最優(yōu)個體進行比較，選出其中更優(yōu)的個體做為歷代最優(yōu)個體并替代掉當代最差個體。優(yōu)化后的種群進行下一次迭代。這種精英保留策略能夠保證優(yōu)秀個體不被流失，并且能加快種群的收斂速度。

2.2 路徑規(guī)劃算法

本文的多機器人路徑規(guī)劃[21]是指在該倉儲環(huán)境中同時存在多個移動機器人，每個機器人都通過強化學習的方法不斷與環(huán)境進行交互，不斷學習最優(yōu)行為。由于在行進過程中，多機器人的相遇并試圖同時占用同一柵格，這些問題是無法預測的，因此在路徑規(guī)劃階段會減少相遇情形。在算法中將采用3個參數(shù)來評判路徑的好壞：轉身次數(shù)t、路徑交叉度c和路徑長度l。轉身次數(shù)指的是在路徑中機器人將會轉彎的次數(shù)，由于機器人轉身需要一定時間，因此該值的大小影響了機器人行進效率。路徑交叉度是指多機器人規(guī)劃路徑時路徑之間的交叉程度，該值越高機器人相遇的幾率越高，容易發(fā)生碰撞。路徑長度參數(shù)是在前2個參數(shù)基礎上的限制參數(shù)，對路徑長度不加以限定，規(guī)劃出的路徑為了滿足前2個條件可能會極大增加路徑長度，因此增加該參數(shù)以限定路徑長度。

2.2.1 獎勵矩陣

獎勵由2個部分組成，對地圖重采樣可得到整個柵格地圖可行走部分由32×23的柵格組成。而每個柵格都對應有上、下、左、右4個動作。因此，先將地圖中每個柵格編號，然后得到一個每個狀態(tài)所對應的動作可行性矩陣。該矩陣記為可行行為矩陣PA，由于在地圖中黑色部分表示貨架，因此該部分的值記為0，同時還有柵格邊界部分的可行值也記為0，其余部分的可行值記為1。取地圖左上邊緣為例，給柵格進行編號(見圖3)。

圖3 部分可行行為柵格

此時，由于柵格1的上方和左方均為柵格邊緣，因此可行性值記為0，右方因為規(guī)定單行道的方向，該通道只能向右行進，因此可行性值為1。下方根據(jù)單行道規(guī)則亦可通行，可行性值記為1。柵格12所在的y軸方向根據(jù)單行道規(guī)則只能向上，因此，左方和上方的可行性值記為1。右方到達貨架，下方不可行，因此這2個方向的可行性值記為0。

于是對于該部分柵格的可行性矩陣為：

Action

左 上 右 下

(8)

其中，橫軸表示左、上、右、下4個方向的移動行為Action，縱軸表示所處的點或情形State。

獎勵矩陣基于可行性矩陣，在每一個情形中，不可行的行為給予懲罰值-50，可行的行為通常給予0的獎懲值，但由于還得遵循上文提到的轉身次數(shù)t和路徑長度限定參數(shù)l，每走一步與當前方向相同的行為給予懲罰值-1，與當前方向不同的行為給予懲罰值-2。到達目標貨架即目標點時給予最大獎勵200。如圖3假設目標貨架是13，則情形8的向下移動行為、情形12的向右移動行為、情形14的向左移動行為獎勵值均為200。因此，獎勵值可分如下情形：

(9)

因此，可行性矩陣PA對應的獎勵矩陣R(i,j)為：

動作

左 上 右 下

狀態(tài)

(10)

2.2.2 Q值表的更新

Q-learning中通過Q估計來進行決策，通過學習定義在狀態(tài)-行為上的值函數(shù)Q(s,a)形成Q值表來尋找最優(yōu)策略。因此，Q值表的自我學習與迭代更新是Q-learning[22]算法中最重要的過程。

Q值表與獎勵矩陣R同階，且橫軸與縱軸表示的意義相同，初始化的Q值表中值全為0。在重采樣的柵格圖中，Q(s,a)的值在機器人的不斷探索中更新迭代。在探索的過程中，環(huán)境的下一狀態(tài)由機器人當前狀態(tài)和動作決定，直到機器人到達目標點完成一次探索，更新Q值表。此時Q值表還未收斂，于是機器人進行第二次探索，直到Q值表完全收斂或者達到最大學習次數(shù)。最后機器人根據(jù)行為矩陣PA和Q值表Q(s,a)選擇最大的收益進行規(guī)劃。

迭代中的Q值表的更新原則如下：

Q(s,a)=R(s,a)+γmax(Q(si,ai))

(11)

其中，s表示當前狀態(tài)，a表示采取的行動，si表示在狀態(tài)s采取行動a后到達的狀態(tài)，ai表示在狀態(tài)si下能采取的行動。而γ表示衰減因子，衰減值在0到1之間有助于讓越靠近目標點的狀態(tài)對到達該狀態(tài)的動作影響越大，此處設為0.8。

本文中Q值表的更新過程分如下幾步：

Step1給定衰減因子γ和獎勵矩陣R。

Step2初始化Q值表。

Step3根據(jù)任務分配算法得到分配到的任務，并鎖定起始點和目標點。

Step4迭代：

Step 4.1在可行性矩陣中根據(jù)當前狀態(tài)s選取一個行為a。

Step 4.2利用選定的行為a得到下一個狀態(tài)s′。

Step 4.3根據(jù)公式(11)計算Q(s,a)。

Step 4.4令s=s′。

在迭代到Q值表收斂后，機器人就可根據(jù)Q值表規(guī)劃出一條路徑。

3 仿真實驗與分析

為驗證算法的有效性，本實驗采用Matlab進行仿真。實驗環(huán)境設置n=100個訂單任務、100個貨架、1臺揀選臺和5臺移動機器人。其中，每個柵格實際表示為1 m×1 m，初始時刻移動機器人均位于揀選臺位置。表1為仿真參數(shù)的設定。

表1 仿真參數(shù)設定

根據(jù)任務分配算法，迭代次數(shù)設為500次，最終得到的任務分配方案如圖4所示。

圖4 任務最優(yōu)分配方式

圖5 最短行走距離收斂圖

圖4中縱軸表示機器人序號，橫軸表示機器人任務執(zhí)行順序。

通過精英遺傳算法與Q-learning算法結合的方式，機器人執(zhí)行完任務距離收斂圖如圖5所示。

該算法與改進遺傳算法[23]在機器人的行走距離和任務最大等待時間上的對比見表2。

表2 機器人行走距離和任務最大等待時間對比

由表2可以看出，在調度算法上，本文算法在行走路程上較傳統(tǒng)的遺傳算法縮短10%，任務最大等待時間縮短131.8 s。因此機器人無論是在行走效率上還是降低任務等待時間上都有一定的改善。

4 結束語

本文針對智能倉儲環(huán)境中多機器人的調度問題，提出一種精英遺傳算法與Q-learning算法結合的調度算法。該算法通過精英遺傳算法在不考慮路徑障礙問題時同時對多移動機器人進行編碼和任務分配，減少了算法運行次數(shù)，增加了算法運行效率。然后通過Q-learning算法對分配完成的任務進行路徑規(guī)劃，規(guī)劃過程中考慮了路徑轉向次數(shù)、路徑長度等限定因素，減少了機器人行進過程中的轉向停頓過程并縮短了機器人的最短行走路程，降低了任務最大等待時間，并且在與傳統(tǒng)遺傳算法對比中取得了一定的改善，證實了該算法切實可行。然而在算法運行時間上仍有欠缺，需進一步改善。