基于深度強化學習的多自動導引車運動規劃

孫 輝,袁 維

(東南大學 機械工程學院,江蘇 南京 211189)

0 引言

近年來,移動機器人倉儲系統(Mobile Robot Fulfillment System, MRFS)逐漸在現代物流業中獲得了廣泛認可[1],以Kiva機器人系統[2]為典型代表的MRFS已在許多世界知名企業(如亞馬遜、Gap、Staples、阿里巴巴、京東、順豐)的物流配送中心得到了大規模應用[1-3]。MRFS采用“貨到人”的揀選方式,使用移動機器人或自動導引車(Automated Guided Vehicle,AGV)將存放商品的貨架搬運至工作站等待人工揀選,顯著降低了傳統“人到貨”揀選方式下作業人員的勞動強度,并可獲得“人到貨”揀選方式2～3倍的揀選效率[4]。

大型MRFS中同時執行搬運作業的AGV數量可達數百臺[1-2],對AGV行駛路徑的規劃和運動控制直接影響系統的揀選效率,這里路徑規劃(path planning)指為每臺AGV單獨確定一條能夠避免與系統中已知靜態障礙物(如墻和貨架)發生碰撞的最短路徑。然而當AGV沿預先規劃的路徑出行時,碰撞(collision)或死鎖(deadlock)等沖突仍有可能發生,這是由于在實際行駛過程中,AGV可能會遇到一些事先未考慮到的動態障礙物,如其他在執行任務的AGV或路過的工作人員[5]。為確保AGV真正實現無沖突行駛,在靜態路徑規劃完成之后,通常需要對系統中的AGV進行協同運動規劃(motion planning),并在任務執行過程中對AGV進行及時有效的控制。本文將針對MRFS環境下的多AGV協同運動規劃問題展開深入研究。

運動規劃是基于沖突預測而對預規劃路徑進行的驗證、確認和修正,目的是為了避免AGV行駛過程中的潛在沖突。一般而言,規避沖突的方法主要分為分區控制(zone control)[6-8]、路徑更改[9-12]、速度調整(包括停止等待)[12-14]、行程安排(scheduling)[15-18]4類。分區控制采用限制特定通行區域內AGV數量的方式避免沖突,路徑更改則通過使用備選路徑或重新規劃來規避沖突,這兩類方法是為了避免AGV行駛軌跡在空間維度上重疊,而速度調整和行程安排旨在從時間維度上消除AGV發生沖突的可能。

MRFS是一種新型智能倉儲系統,從投入實際應用至今只有十余年歷史,文獻中關于MRFS環境下AGV路徑規劃和運動規劃的研究相當有限。張丹露等[19]為解決AGV路徑規劃問題提出一種考慮動態加權地圖和預約表的改進A*算法,并通過仿真實驗驗證了該方法的可行性和高效性;ZHANG等[20]和LEE等[21]分別采用改進Dijkstra算法和A*算法進行AGV路徑規劃,繼而在運動規劃時通過時間窗預測潛在的碰撞,并針對不同碰撞類型提出使用備選路徑、延遲出發、重新規劃路徑、主動避讓等幾個可選的防碰撞策略。雖然這些策略的有效性也通過仿真實驗得到了驗證,但是文中沒有明確指出存在多種可行策略時的選擇方法。另外,文中也沒有詳細說明運動規劃算法中個別關鍵參數(如碰撞檢測閾值)的設置方法。為解決MRFS環境下的AGV運動規劃問題,MAOPOLSKI[22]提出一個基于網格預約占用思想的啟發式算法,即在AGV規劃路徑的每個網格上按照搬運任務先來先服務(First Come First Served,FCFS)原則構建一個AGV預約占用的隊列,同時規定AGV必須嚴格按照隊列順序通行。該算法雖然可以確保實現AGV無沖突行駛,但是單一嚴格的通行規則也存在柔性不足的問題,可能會增加承擔后續任務的AGV的通行等待時間,降低整個AGV系統的作業效率。綜上所述,目前針對MRFS環境下AGV運動規劃的研究還存在一定局限和不足,不僅需要進一步完善傳統規劃方法來提高其普適性和靈活性,還需要設計開發基于新思路和新視角的智能規劃方法,以充分挖掘MRFS的效率潛力。

本文提出一個新的基于深度強化學習(Deep Reinforcement Learning,DRL)的方法來解決MRFS環境下的多AGV運動規劃問題,以探究應用人工智能方法求解此類問題的可行性和有效性。與上述已有研究工作不同,該方法的主要思想是通過集中協同規劃AGV車隊系統在任務執行過程中的一系列動作決策達到避免碰撞沖突的目的。應用該方法同時為每一臺AGV制訂其在預規劃路徑上的行程時間表(schedule),最終得到一個完整的無沖突的AGV運動方案。需要指出的是,文獻中尚未發現有使用DRL方法來解決多AGV運動規劃問題的研究。

1 MRFS環境中的多AGV協同運動規劃

1.1 問題描述

圖1所示為一個小型MRFS,該倉儲系統地面采用網格(grid)布局。系統中共停放有120個可移動貨架,每個貨架占用一個單元格,貨架間的通道均為雙向通道。訂單到達系統后,AGV將存放訂單商品的貨架托舉搬運至揀選站,待人工揀選作業完成后再將其運回存儲區域。AGV由電池驅動,具有舉升和原地旋轉功能,利用粘貼在單元格上的二維碼進行定位和導航,可以在網格單元間直線行走。另外,空載AGV可以在貨架下方自由通行,這意味著接到指令的空閑AGV總是能夠沿最短路徑趕至目標貨架下方,然后開始執行搬運任務。

假設系統中每臺AGV的貨架搬運任務清單已知,而且每臺AGV在執行任務過程中的行駛路徑已事先確定。本文多AGV協同運動規劃要解決的問題是為每臺AGV制訂具體的行程時間表,目的是使用“錯開出行”策略避免潛在的AGV碰撞,確保其能夠在無沖突發生的情況下盡快完成所有貨架搬運任務。需要說明的是,這里沒有為避免沖突而使用更改預規劃路徑的傳統策略,而是通過在既定路徑上為每臺AGV設置合理的行程時間表來避免碰撞。這是因為在一個復雜的大型AGV系統中,單純通過更改路徑很難達到杜絕沖突的目的。另外,本文假設系統中所有AGV均保持同一固定速度行駛,不會出現AGV之間的同向追及碰撞問題,這樣AGV之間可能發生的碰撞共有相向碰撞、交叉碰撞、停留碰撞3種類型,如圖2所示[21]。

1.2 數學模型

已知在一個MRFS中,共有G臺AGV同時執行各自的貨架搬運任務。每臺AGVg(g=1,2,…,G)的規劃路徑Pg可用該路徑上的單元格編號序列表示,即Pg=(cg1,cg2,cg3,…),這里cgj(j=1,2,3,…)為路徑Pg上第j個單元格的編號。假設每臺AGV以速度v勻速行駛,將AGV駛過一個單元格的時間視為一個單位時間步(time step),則v在數值上等于單元格的邊長。另外,假設在每個單位時間步開始的時刻,每臺AGV都恰好完全處于某個單元格內,而且已經為該時間步內將要執行的下一個動作做好了準備,從而可以采用各AGV所處的單元格位置表示AGV車隊系統當前的狀態。進一步假設車隊系統的下一個動作決策只和其當前狀態相關,則可以使用一個Markov決策過程(Markov Decision Process,MDP)模型描述MRFS環境下的多AGV協同運動規劃問題。下面詳細介紹該過程中的狀態(states)、動作(actions)、獎勵(rewards)和策略(policy)。

1.2.1 狀態

在為多臺AGV進行運動規劃時,需要同時關注MRFS中每臺AGV的當前位置。將系統中所有AGV組成的車隊視為一個整體,則各AGV在每個時間步開始時所處的單元格位置聯合定義了車隊的一個狀態。以一個5臺AGV的車隊為例,該車隊在某一時刻t的狀態st如圖3所示。

1.2.2 動作

由于假設行駛路徑已知且保持不變,在每一時間步開始時每臺AGV可選擇的動作只有兩個,即原地等待或者沿給定路徑前進一個單元格,用“0”表示AGV將原地等待,用“1”表示AGV將前行。對于整個車隊,將每臺AGV的動作決策組合起來構成車隊系統的一個動作決策,仍以一個5臺AGV的車隊為例,車隊在某個時刻t將要執行的動作at如圖4所示。

1.2.3 獎勵

獎勵用以評估車隊在某個狀態下采取相應動作的優劣程度。令rt表示AGV車隊系統在狀態st時采取動作at后獲得的獎勵,rt既和車隊中每臺AGV所采取的動作相關,又和車隊的行駛狀況相關,

(1)

式中:rt(g)表示給予第g(g=1,2,…,G)臺AGV執行動作的獎勵或懲罰,當AGVg沿其既定路徑前進時,rt(g)=f(f>0),表示鼓勵AGVg按照規劃路徑前進;當AGVg選擇等待時,rt(g)=w(w<0),表示給予其一定懲罰。這樣定義rt(g)是希望車隊中有更多的AGV同時前行,從而使完成所有搬運任務的時間(即最大完工時間)最短。p表示碰撞引起的懲罰,在執行動作at的過程中,如果發生碰撞,則p=-P(P是一個很大的正數),表示應盡量避免沖突,否則p=0。c是在車隊完成全部任務后給予的獎勵,當所有AGV都到達其目標位置時,c=C(C為一個很大的正數),表示此時已經找到了無碰撞的協同運動方案,否則c=0。

1.2.4 策略

在MDP中,策略定義了狀態和動作之間的映射關系。在每一個時間步的開始時刻t,AGV車隊根據一個特定的策略π選擇下一個要執行的動作。策略的優劣采用強化學習(reinforcement learning)理論中的動作值函數Qπ(s,a)(也稱Q函數)來評估[23]。Q函數指智能體在狀態s時采取動作a,并在后續狀態轉移過程中按照π選擇動作獲得的期望累計折扣獎勵,

Qπ(s,a)=

E[rt+γrt+1+γ2rt+2+…|st=s,at=a,π]。

(2)

式中γ(0≤γ≤1)為折扣因子,用以區分短期獎勵和長期獎勵?？梢钥闯?AGV車隊在未來某一時刻t+i(i=1,2,…)所獲獎勵rt+i對應的折扣系數γi將隨時間的推移而減小。

本文多AGV運動規劃的目標即是確定一個最優策略π*,使AGV車隊在無沖突的情況下順利完成所有貨架搬運任務,而且可以獲得最大的期望累計獎勵,即滿足

(3)

2 基于DRL的多AGV協同運動規劃方法

采用參數為θ的深度Q網絡(DeepQ-Network,DQN)作為上述Q函數的逼近器,即Q(s,a;θ)≈Qπ*(s,a)。DQN的概念由谷歌DeepMind團隊于2013年首次提出[24],其將反映狀態特征的高維原始數據作為輸入,在輸出端得到每一個狀態—動作組合所對應的動作值,因此能夠處理具有較大規模和連續狀態空間的復雜決策過程?；贒QN的深度強化學習(Deep Reinforcement Learning,DRL)算法已被成功應用于求解多種不同類型的問題,如游戲問題[25]和調度問題[26-27]。

本文提出一種基于DRL的多AGV運動規劃方法,其主要思想是將AGV車隊系統的狀態輸入DQN,利用DQN估計該狀態下采取每個動作所能獲得的最大期望累計獎勵。DQN的參數θ經由多次訓練后確定,其可為車隊選擇在一系列連續狀態下的最佳動作。DQN訓練采用經典的深度Q學習(Deep Q-Learning,DQL)算法[25]完成,并用一個數據集D存儲訓練過程中的經驗數據;另外,用一個與原始網絡(也稱在線網絡)具有相同結構的DQN網絡(即目標網絡)生成Q函數的目標值,以加強訓練的穩定性。表1所示為算法描述中使用的符號和參數。

表1 DQN訓練算法中的符號和參數

DQN訓練算法的主要流程如算法1所示。每次訓練開始時(t=1),每臺AGV都位于其各自規劃路徑的起點。當所有AGV均完成搬運任務并到達終點后,一次完整的訓練結束。訓練過程中DQN智能體為AGV車隊在每一個時間步選擇一個動作,執行后車隊到達下一狀態,該狀態轉換經驗隨即被存入數據集D,智能體從D中隨機抽取部分經驗數據,并用小批量梯度下降法(mini-batch gradient descent)更新在線網絡參數θ。當完成預先設定的M次訓練后,算法終止運行并輸出最終的網絡參數θ。下面詳細介紹DQN的網絡結構、算法的經驗回放(experience reply)機制、智能體選擇動作所采用的ε-貪婪策略和小批量梯度下降法。

算法1DQN訓練算法。

1 初始化經驗數據集D的容量N

2 初始化在線網絡和目標網絡的參數,θ=θ′

3 FOR episode = 1 TO M

4 獲取AGV車隊初始狀態和目標狀態

5 FOR t = 1 TO T

6 計算st下的可行候選動作集

7 計算st下所有可行動作的Q值 /由在線網絡/

8 選擇一個動作at/根據ε-貪婪策略/

9 執行at,獲得獎勵rt,到達下一狀態st+1

10 將轉換經驗(st, at, rt, st+1)存入D

11 從D中隨機抽取b個轉換經驗(sj, aj, rj, sj+1)

12 計算近似目標Q值yj/由目標網絡/

13 對(yj-Q(sj,aj;θ))2執行梯度下降,更新θ

14 每F個時間步,令θ′=θ

15 IF AGV碰撞發生

16 THEN 結束本次訓練

17 END IF

18 END FOR

19 END FOR

20 輸出網絡參數θ

2.1 DQN網絡結構

在線網絡和目標網絡的結構相同且初始參數值相等,分別用于計算Q函數的估計值和目標值。在訓練過程中,在線網絡不斷更新參數θ(即每個神經元節點的權重和偏差),而目標網絡的參數θ′相對穩定,在一段時間內保持不變。每隔固定的F個時間步,通過復制當前的在線網絡(即令θ′=θ)得到一個新的目標網絡。

本文DQN是一個全連接(fully connected)深度神經網絡,包括1個輸入層、2個隱藏層和1個輸出層(如圖5)。表2所示為DQN的結構參數,其中輸入層的節點數等于AGV的數量,兩個隱藏層各自包含64個節點,輸出層的節點數為車隊可執行的動作總數。仍以一個包括5臺AGV的車隊為例,網絡輸入層有5個節點,每個節點的輸入信息分別對應其中一臺AGV當前所在的單元格編號;輸出層有25=32個神經元節點,每個節點的輸出為其中一個動作決策所對應的Q值。兩個隱藏層的激活函數均為修正線性單元(Rectified Linear Unit,ReLU)。

表2 DQN的結構參數

2.2 經驗回放機制

經驗回放機制指在每個時間步t,將智能體與環境交互得到的狀態轉換經驗(st,at,rt,st+1)存入數據集D。例如,狀態轉換經驗((10,20,5,50,106),(0,1,0,1,1),0.000 5,(10,21,5,51,122)),表示一個包括5臺AGV的車隊在執行一個動作(0,1,0,1,1)后可以獲得的獎勵是0.000 5,同時其狀態也由(10,20,5,50,106)轉換為(10,21,5,51,122)。當經驗數據量達到D的容量后,舊的經驗將被新的經驗取代,從而保證所有訓練樣本均來自智能體和環境的不斷交互。另外,每次更新網絡參數時從D中隨機抽取固定數量的經驗數據,可以滿足深度學習對訓練數據獨立同分布的假設,而且一個經驗有機會被多次抽中也提高了數據的利用率。

2.3 ε-貪婪策略

另外,ε隨訓練次數的增加不斷衰減,其數值計算為

ε=εmin+(εmax-εmin)×e-λ,E。

(4)

式中:εmax和εmin分別為預先設置的最大和最小ε值;λε為衰減因子;E為當前累計的訓練次數。隨著訓練次數的增加,ε將從εmax逐漸減小到εmin,表示訓練初期以鼓勵全局探索為主,后期更加專注于局部開發。

2.4 損失函數與小批量梯度下降

本文用均方差(Mean squared error,MSE)衡量目標Q值與真實Q值之間的差距(即損失),每次迭代時通過最小化均方差損失來訓練DQN。第i次迭代時的損失函數Li(θi)定義為

(5)

在線網絡參數θ的更新采用小批量梯度下降方法,每次從數據集D中隨機選擇b個樣本進行學習。損失函數的梯度

θiL(θi)=

E(s,a,r,s′)[(y-Q(s,a;θi))θiQ(s,a;θi)]。

(6)

3 數值實驗

本章通過設計算例驗證本文所提AGV協同運動規劃算法的可行性和有效性。算例涉及的MRFS倉儲系統(如圖1)中共包括18×16=288個單元格和120個貨架。另外,系統中有一個揀選站,位于第1行第9列的單元格處。假設開始時所有AGV都停放在第1行的泊車單元格內。算例共分為兩組,分別用2臺和3臺AGV執行搬運任務,每臺AGV平均承擔3～4個任務,平均規劃路徑長度為120～160個單元格邊長,每組算例均包括20個運動規劃問題。采用基于DRL的運動規劃算法對所有40個算例問題進行求解,并與文獻[22]的啟發式規劃算法進行對比。

在文獻[22]中,每臺AGV完成任務后就近前往系統中的某個安全?？奎c等待。如果其路徑終點恰好位于另一臺AGV的行駛路徑上,則這臺處于空閑狀態的AGV將成為一個通行障礙,因此在文獻[22]算法中加入了終點檢測與避讓操作,即在每個時間步結束時檢查AGV規劃路徑上的下一個單元格,判斷該單元格是否正被其他空閑AGV占用,是則將這臺AGV移至附近可用單元格進行避讓。

基于DRL的運動規劃算法在JetBrains公司的PyCharm平臺上用Python語言實現,相關軟件及第三方庫的版本有Python 3.7.9,tensorflow-gpu 2.0,CUDA 10.0,cuDNN 10.0,keras 2.3.1。文獻[22]的啟發式運動規劃算法在微軟公司的Visual Studio 2019平臺上用C++語言實現。程序調試和算例求解均在一臺CPU主頻為1.60 GHz、GPU為NVIDIA GeForce MX250、內存為8.00 GB的個人計算機上完成。

基于文獻[23,25-26]推薦和一系列的實驗驗證,基于DRL的運動規劃算法的參數設置如下:M=1 000,N=10 000,F=200,b=128,γ=0.9,εmax=1,εmin=0.1,λε=0.001。DQN訓練過程中,每2個時間步進行一次迭代,在線網絡參數θ更新時的學習率為0.002。MDP模型中獎勵函數的參數f=0.000 5,w=-0.000 1,P=1,C=1。

計算結果表明,對于所有算例問題,基于DRL的運動規劃算法均可為車隊中的每一臺AGV確定其在規劃路徑上的行程時間表,使得按照時間表運動的AGV車隊能夠在無碰撞的情況下完成搬運任務。另外,與文獻[22]中的啟發式算法相比,該算法得到的AGV運動規劃方案所需要的平均最大完工時間更短。

3.1 DQN的訓練過程

圖6～圖8所示為DQN訓練過程中一些關鍵指標的變化趨勢(以一個包括3臺AGV的規劃問題為例)。圖6中,累計獎勵R≈-1表示在訓練過程中AGV之間發生了碰撞,導致本次訓練提前結束;R≈1表示本次訓練最終找到了無碰撞沖突的規劃方案?？梢?智能體在訓練后期找到無碰撞規劃方案的頻次顯著增加。另外,隨著累計時間步的增加,DQN預測Q值相對于目標Q值的均方差損失在整體上顯著下降(如圖7),同時Q值的預測準確率也大幅提高(如圖8)。以上指標的變化趨勢表明了DQN訓練算法的有效性。

3.2 協同運動規劃算法的性能驗證

由于AGV的行駛速度v恒定(v=1單元格邊長/時間步),可用完成全部搬運任務所需要的時間步數(即最大完工時間)作為衡量一個運動規劃方案性能的重要指標,時間步數越少,該運動規劃方案所需的最大完工時間越短,AGV的搬運作業效率越高。圖9和圖10所示分別為采用DRL算法和啟發式算法求解兩組設計算例所得的結果。

由圖9可知,對于第1組算例問題,DRL算法和啟發式算法求得的規劃方案大致相當,所需最大完工時間比較接近,其中DRL算法所得規劃方案導致的平均最大完工時間為164個時間步,略少于啟發式算法需要的173個時間步。然而在求解效率方面,啟發式算法的平均CPU運行時間不到0.1 s,遠少于DRL算法5 s的平均運行時間。

由圖10可知,對于第2組算例,除了第19個規劃問題外,DRL算法求得的運動方案均有顯著優勢。DRL算法所得運動方案的平均最大完工時間為220個時間步,明顯少于啟發式算法的253個時間步?？梢婋S著車隊規模的擴大,DRL算法的優勢更加明顯,這可能是因為DRL算法通過智能體的迭代試錯能夠充分探索問題的解空間,從而有效壓縮AGV行駛過程中的等待時間;另一方面,啟發式算法自身不具備迭代搜索能力,而且算法要求AGV必須嚴格按照任務到達的先后順序占用單元格的通行規則靈活性不夠,可能增加承擔后續任務的AGV的無效等待時間,最終延長最大完工時間,降低系統整體搬運作業效率。然而在求解效率方面,啟發式算法的CPU運行時間仍然遠少于DRL算法。

4 結束語

本文針對新型MRFS智能倉儲系統中的多AGV協同無沖突運動規劃問題,基于AGV“錯開出行”的規劃策略建立了MDP模型,并設計了基于DQN的DRL算法進行求解。將AGV在系統中的位置輸入DQN,輸出端可以得到每一可行動作決策的最大期望累計獎勵。采用經典的DQL算法訓練DQN,訓練結束后利用DQN為AGV車隊選擇行駛過程中一系列連續運動狀態下的最佳動作,即可得到每臺AGV的最佳出行時間表。算例驗證結果表明,應用本文所提DRL算法可以有效求解MRFS環境中的多AGV協同運動規劃問題,而且求解質量優于文獻中的一種啟發式運動規劃算法。

本文主要探究了基于DQN的DRL方法對小規模AGV車隊進行運動規劃的效果,后續將進一步驗證其求解大規模車隊運動規劃問題的性能。另一方面,為提高智能體學習的效率,嘗試采用其他DRL方法進行求解,如基于競爭深度Q網絡(dueling DQN)的學習方法或融合6種DQN改進的Rainbow學習方法。