多AGV的路徑規(guī)劃與任務調(diào)度研究

于會群, 王意樂, 黃貽海

(上海電力大學 自動化工程學院, 上海 200090)

隨著電子商務與工業(yè)自動化等行業(yè)的飛速發(fā)展,倉儲物流行業(yè)在各個領域扮演的角色也越來越重要,人們迫切需要構(gòu)建一個更加高效的自動化倉儲系統(tǒng)。其中,自動導引車 (Automated Guided Vehicle,AGV)是實現(xiàn)整個自動化倉儲系統(tǒng)的關鍵因素之一。訂單揀選作為倉庫集成系統(tǒng)的關鍵環(huán)節(jié)之一,是影響物流配送中心作業(yè)效率的重要因素,AGV的出現(xiàn)實現(xiàn)了倉儲系統(tǒng)從“人到貨”到“貨到人”的轉(zhuǎn)變,揀選效率提高了2～4倍[1-2]。

目前,關于AGV任務調(diào)度與路徑規(guī)劃問題的研究都聚焦于單一問題[3],然而兩者存在相同的優(yōu)化目標,綜合優(yōu)化能更好地提高AGV分揀效率。

對于AGV任務調(diào)度問題,文獻[4]建立了一個混合整數(shù)規(guī)劃模型,采用文化算法和改進遺傳算法的混合算法進行優(yōu)化調(diào)度;文獻[5]將AGV無沖突路徑的任務調(diào)度問題描述為整數(shù)規(guī)劃問題進行求解;文獻[6]通過改進的Memetic算法來對多AGV調(diào)度問題進行求解,但并未考慮AGV之間的碰撞沖突以及死鎖。

AGV路徑規(guī)劃的好壞直接影響系統(tǒng)的效率[7]。路徑規(guī)劃問題的常用算法包括傳統(tǒng)的Dijkstra算法[8]與A*算法[9],近年來Q-learning算法[10]、遺傳算法[11],以及PSO算法[12]也陸續(xù)出現(xiàn)在求解路徑規(guī)劃問題上,但是大多僅能求解單AGV的路徑問題。對于多AGV系統(tǒng),如何避免AGV的路徑?jīng)_突尤為重要。文獻[13]提出了一種在線學習的Q-learning算法,通過構(gòu)建獎懲矩陣的形式,實現(xiàn)了多AGV的無沖突路徑規(guī)劃;文獻[14]通過預約表、改進A*算法與動態(tài)加權(quán)地圖,實現(xiàn)了多AGV的路徑協(xié)同優(yōu)化。

上述文獻在研究AGV任務調(diào)度問題時,大多將AGV運行路徑進行固定且很少考慮AGV間的碰撞沖突,同時,研究AGV路徑優(yōu)化問題時,大多默認分配給AGV的任務調(diào)度是固定的。另外,當前研究大都忽略了AGV電量的影響。因此,本文針對自動化揀選倉儲的多AGV環(huán)境,在考慮AGV電量的情況下,綜合研究任務調(diào)度和路徑優(yōu)化問題。首先,針對路徑規(guī)劃問題,設計了多AGV的路徑規(guī)劃算法,同時考慮AGV電量的影響,綜合優(yōu)化多AGV任務調(diào)度和路徑規(guī)劃,最終通過本文設定的AGV沖突優(yōu)先級,生成多AGV的無沖突路徑。

1 任務調(diào)度與路徑規(guī)劃問題描述

通過柵格化建模方式建立的自動化倉儲模型如圖1所示。

圖1 自動化倉儲模型

圖1中,倉儲的貨架排列是整齊對稱的,多AGV在倉儲環(huán)境中工作。其中,①為揀選區(qū),人工揀選區(qū)域;②為空載AGV,前往目標點搬運貨架;③為載貨AGV,搬運貨架中;④為貨架,AGV的搬運目標;⑤為充電區(qū),AGV電量不足時會駛?cè)氤潆姟?/p>

為了便于求解,本文對多AGV的運行場景簡化如下

(1) AGV的每條通行道是單向的,且相鄰通行道的通行方向相反;

(2) 每個貨架僅搬運1次;

(3) 忽略貨架重量的影響,AGV裝貨與卸貨時間固定為2 s;

(4) AGV運行速度是固定的,AGV運動一個柵格的時間為1 s;

(5) AGV執(zhí)行一次啟停操作時間為2 s,AGV執(zhí)行一次轉(zhuǎn)彎操作時間為3 s;

(6) AGV在載貨狀態(tài)的電量是空載狀態(tài)的2倍,空載AGV運行1 s消耗電量1;

(7) AGV不可沿對角線跨越柵格。

AGV在執(zhí)行任務過程中,根據(jù)其運行狀態(tài)的不同,將其分為載貨和空載2個工作狀態(tài)。載貨狀態(tài)指AGV將目標貨架搬運到揀選區(qū)再返回時的狀態(tài),此時AGV只能在規(guī)定巷道內(nèi)行駛,AGV的運動障礙點為固定貨架與其他AGV;空載狀態(tài),即AGV前往目標貨架點時的狀態(tài),AGV可從規(guī)定巷道內(nèi)行駛,亦可從貨架下方行駛,此時AGV在倉儲環(huán)境中運動時,障礙僅為其他AGV。

為方便描述,本文定義以下符號:i表示AGV編號;j表示任務編號;n表示機器人數(shù)量;m表示任務數(shù)量;AGVi表示編號為i的AGV;Yi表示AGVi的任務搬運序列;Yi(r) 表示Yi的第r個任務;D表示AGV設定的最低電量;Ei表示AGVi的電量;hij表示AGVi執(zhí)行第j個任務載貨運行時間;kij表示AGVi執(zhí)行第j個任務空載運行時間;Ti表示AGVi的搬運任務完成時間;Tes表示為電量充足的AGV搬運任務完成時間最大值與最小值的差值;S1i表示AGVi空載狀態(tài)下的停車等待次數(shù);S2i表示AGVi載貨狀態(tài)下的停車等待次數(shù);Ts表示AGV單次停車避讓時間。

Ti的計算公式為

(1)

AGV完成任務的空載時間與AGV空置率的優(yōu)化目標函數(shù)為

(2)

考慮AGV電量的影響,設置AGV完成任務后的電量不能低于設定值D,即

Ts(S1i+2×S2i)]≥D

(3)

在調(diào)度過程中,若AGV電量低于設定值時,應對AGV所承擔任務進行舍棄,使之電量不能低于設定值,且將此AGV設定為低電量狀態(tài)。

2 多AGV路徑規(guī)劃算法

若搬運路徑確認的情況下,多AGV搬運問題可以理解為多旅行商問題,針對多AGV調(diào)度問題本文設計了一種改進的遺傳算法。

在執(zhí)行任務序列Yi時,采用一種基于Q-learning的路徑規(guī)劃算法。Q-learning算法通過建立獎勵函數(shù)R和Q值表,分別用來存儲瞬時獎勵和Q值函數(shù)值。通過AGV的當前位置s和相應的路徑動作a,計算并更新對應的Q值函數(shù)值,記為Q(s,a)。最終通過選擇最大的累計回報值,選擇AGV的下一位置s′,從而生成AGV的運動路徑。

將獎勵函數(shù)R分為主獎勵函數(shù)R1與輔助獎勵函數(shù)R2,即

R=R1+R2

(4)

首先,建立主獎勵函數(shù)R1為

(5)

對于傳統(tǒng)的Q-learning算法,存在收斂速度慢等問題,因此本文引入了導向機制,用以建立輔助獎勵函數(shù)R2。

R2=C(s,goal)-C(s′,goal)

(6)

式中:C(s,goal)——AGV當前位置點到目標點的歐式距離;

C(s′,goal)——AGV下一位置點到目標點的歐式距離。

當R2為正值時,表示AGV正在向目標點靠近,應給予獎勵;反之,應給予懲罰。引入導向機制,可以加快Q-learning算法的迭代速度,使得AGV更快地向目標點靠近。

本文對Q值函數(shù)值進行初始化操作,同時在Q值函數(shù)值中加入導向機制,減少算法前期大量的無用迭代,以提高算法效率。具體公式為

Q(s,a)=C(s,goal)-C(s′,goal)

(7)

Q′(s,a)=(1-α)Q(s,a)+α(R(s,a)+

βmaxQ(s′,a′))

(8)

式中:Q′(s,a)——更新后的Q值函數(shù)值;

α——學習率,α∈[0,1],定義了Q值更新占原Q值的比例;

R(s,a)——當前狀態(tài)下,系統(tǒng)采取的路徑動作獲得的獎勵;

β——折扣因子,β∈[0,1],定義未來獎勵的重要程度;

a′——下一狀態(tài)所采取的路徑動作;

Q(s′,a′)——下一狀態(tài)下所能得到的最大Q值函數(shù)值。

AGV在運行過程中,如果同一時間內(nèi)有2臺或以上AGV占據(jù)了同一柵格,即發(fā)生了AGV沖突。為了解決AGV的沖突問題,本文設置AGV沖突避讓規(guī)則如下。

規(guī)則1 低電量機器人獲得最高優(yōu)先級,即:AGV設置2個電量等級,機器人電量不可低于20%的電量,否則,將前往充電區(qū);對低電量機器人賦予高優(yōu)先級。

規(guī)則2 若不滿足規(guī)則1,即AGV的電量充足,則先判斷AGV是否為載貨狀態(tài),載貨狀態(tài)的AGV賦予高優(yōu)先級。

規(guī)則3 若不滿足規(guī)則1和規(guī)則2,即AGV電量充足且在相同工作狀態(tài)下發(fā)生沖突,則計算各個AGV完成分配的任務序列總時間長短,賦予搬運時間長的機器人高優(yōu)先級。

規(guī)則4 若AGV均不滿足以上3條規(guī)則,則隨機確定AGV的沖突優(yōu)先級。

規(guī)則1的制定是為了保證AGV的電量充足,避免AGV因為電量不足,從而導致碰撞或死鎖;規(guī)則2的制定,是為了減少AGV的電量消耗;規(guī)則3的制定,使得AGV的最大搬運時間不會再增加,降低AGV空置率。根據(jù)以上規(guī)則,在AGV發(fā)生沖突時,使得高優(yōu)先級AGV直接通過,低優(yōu)先級AGV停車避讓。

3 改進遺傳算法求解調(diào)度問題

本文針對AGV搬運任務序列提出了一種改進的遺傳算法,設計了雙重染色體編碼方案,使得每個個體中都包含各AGV的搬運任務序列;然后通過本文設置的自適應交叉和變異因子對個體進行進化。AGV的搬運任務序列表示為Y={r1,r2,r3,…,rm}。為了提高AGV的運行效率,需要通過調(diào)度來生成一條有序地任務序列,使AGV按照序列有序地執(zhí)行訂單任務,以保障:低電量機器人不會承擔超過設定值電量的任務;AGV執(zhí)行任務的路徑最短;降低AGV最大任務完成時間,從而降低AGV空置率。

3.1 種群初始化

本文為解決多AGV的任務調(diào)度問題,設計了一種雙重染色體編碼方案。染色體分為2層:第1層決定任務序列;第2層決定AGV編碼。例如,任務數(shù)m為4,AGV數(shù)量n為2。染色體Ca為

(9)

此時AGV的搬運序列為:Y1為4-1;Y2為2-3。

3.2 選 擇

遺傳算法通過選擇最優(yōu)的個體作為父代,然后通過進化操作產(chǎn)生新的子代,但如果將所有的個體都放入進化過程,個體中的優(yōu)質(zhì)基因很容易被破壞,因此本文通過輪盤賭和精英保留的方式進行個體選擇。將種群中適應度值前10%的個體進行保留,確保種群的群優(yōu)良,然后再通過輪盤賭的方式選擇個體成為父代。

3.3 交叉變異

遺傳算法的交叉過程為隨機產(chǎn)生兩個數(shù)(大小不能超過染色體的長度),通過兩個隨機數(shù)可選中父代染色體的兩段基因片段,然后將兩個基因片段進行互換,即可生成兩個子代染色體,染色體進行基因片段互換后,可能會使得個體中出現(xiàn)重復任務,需要對染色體進行調(diào)整,最終生成交叉后的子代染色體。具體交叉操作如圖2所示。

圖2 染色體交叉過程示意

染色體交叉過程中,AGV編碼可與任務序列編碼一起變動。在算法進化過程中,如果給予所有個體相同的交叉概率Cr,在進化過程中會造成種群優(yōu)良基因的流失,因此本文提出一種自適應交叉因子。對每1對交叉的個體賦予1個交叉概率,當該個體的質(zhì)量較好時,賦予較低的交叉概率,希望將個體保留下來;反之,則提高交叉概率,希望生成更好的個體。

(10)

式中:Crmax,Crmin——最大和最小交叉概率;

f′——當前2個個體中最高的適應度值;

favg,fmax——種群中個體平均和最高適應度值。

在算法迭代前期,種群個體的適應差值較大,需要較大的交叉概率來生成新的個體,而隨著迭代逐漸靠近中后期,此時的種群個體的適應差值逐漸減小,需要減小交叉概率,因此設計了隨算法迭代次數(shù)而變化的最大交叉概率為

(11)

式中:gen,Gen——當前和最大迭代次數(shù)。

變異操作時,采用單點變異的方式,即產(chǎn)生兩個隨機數(shù),確定父代個體中2個基因點,將選中的2個基因點位置進行互換,即可得到變異后子代個體。AGV染色體編碼與任務序列編碼一起變動用來避免算法早熟且可以改善算法的局部搜索能力。本文設計的自適應變異算子Mr計算公式如下

(12)

(13)

式中:Mrmax,Mrmin——最大和最小變異概率。

4 仿真驗證

構(gòu)建仿真場景模型,設置基本參數(shù)如下:AGV數(shù)量為5,任務數(shù)量為100,2#AGV初始電量為低電量4 000,其他編號的AGV初始電量為滿電量10 000,AGV最低運行電量D為2 000。算法參數(shù)設置如下:α為0.6,β為0.2;初始種群數(shù)量為100,最大迭代次數(shù)為2 000,最小交叉概率為0.3,最小變異概率為0.1。 為了更加直觀地觀察算法的性能,將本文所提算法與其他算法進行對比,結(jié)果如圖3所示。

圖3 不同算法收斂曲線對比

由圖3可知:本文所提算法在650代取得了最小值821,而遺傳算法、蟻群算法和模擬退火算法分別在555,596,343取得最小值825,828,836;本文所提算法在396代收斂到823,就已經(jīng)超越其他算法的最優(yōu)收斂值。因此,本文所提算法在收斂速度上要優(yōu)于其他算法。

在最終求解的路徑結(jié)果上,表1和表2分別給出了4種算法的AGV運行時間以及AGV空置時間。

表1 AGV運行時間對比 單位:s

表2 AGV空置時間對比 單位:s

由表1和表2可以看出:對低電量2#AGV的調(diào)度和路徑優(yōu)化,所有算法都得出了相同的規(guī)劃結(jié)果;而對于其他編號的AGV,本文所提算法的AGV運行時間和AGV空置時間更短,系統(tǒng)的運行效率更高。由此可以得出本文所提算法在求解質(zhì)量上優(yōu)于其他算法。

5 結(jié) 語

本文針對多AGV的路徑及調(diào)度優(yōu)化問題,綜合AGV完成任務的空載時間與AGV的空置時間為目標展開研究。針對路徑優(yōu)化過程,通過加入導向機制用來改善Q-learning算法的效率低下問題。針對多AGV路徑和調(diào)度的綜合優(yōu)化,本文通過設計自適應的交叉和變異因子來改善遺傳算法的效率以及局部最優(yōu)問題。最后通過仿真驗證,本文算法在收斂速度和求解質(zhì)量方面要優(yōu)于其他算法,在一定程度上體現(xiàn)了該算法的高效性。