基于深度強化學習的汽車零件生產車間AGV節(jié)能調度算法

榮子鳴

（新疆大學商學院，烏魯木齊 830000）

0 引言

AGV（automated guided vehicle）［1］，是指裝備有電磁或光學導引裝置，以電池為動力，具有運行、停止、安全保護等多種功能的自動引導小車。隨著智能制造在制造業(yè)企業(yè)的不斷推進，作為智能制造關鍵性設備的AGV 在以汽車零件生產車間為代表的各種產品生產車間中的應用越來越廣泛，受到行業(yè)內研究者的廣泛關注。2021 年，我國提出了“碳達峰”“碳中和”理念。工業(yè)［2］作為降碳節(jié)能的主戰(zhàn)場，要平衡好自身發(fā)展與節(jié)能減排之間的關系。作為工業(yè)重要組成部分的汽車制造業(yè)也積極響應降碳節(jié)能，AGV 的引入大大助力了降碳節(jié)能的推進，AGV 完全由電力驅動，本身沒有碳排放，是較為環(huán)保的運輸工具。但市場競爭的加劇，汽車零件生產車間承擔的生產任務越來越多、引入的AGV 越來越多，AGV 調度場景逐漸由已知所有任務轉變到任務動態(tài)生成。傳統(tǒng)的AGV 調度算法難以適應這些變化，將AGV 任務分配和路徑規(guī)劃分開計算，導致AGV 路徑規(guī)劃解效果不佳，完成所有任務所行駛路程過長，浪費了大量電力，此外，導致多AGV 調度場景中發(fā)生碰撞沖突的次數(shù)大大增加。

目前，上述車間多AGV 調度中所存在問題的研究已取得了較大的進展。張宇航等［3］提出了一種基于改進A*算法的路徑規(guī)劃方法，通過提高算法效率節(jié)約了能源。魏劉倩［4］構建了一種基于靈活時空網絡模型的AGV 節(jié)能路徑規(guī)劃辦法，并根據模型設計了一種雙層啟發(fā)式算法進行求解，得到了有效的節(jié)能路徑規(guī)劃解并證明了優(yōu)越性。張中偉等［5］提出了一種基于粒子群優(yōu)化算法的AGV 節(jié)能路徑規(guī)劃算法，降低了AGV 完成所有任務的耗能。鄭曉軍等［6］建立了以軟時間窗為約束的多車型AGV優(yōu)化配送模型，最后使用遺傳算法對其求解，成功降低了能耗。王唯鑒等［7］采用了一種基于多智能體強化學習的多AGV 任務分配方法，優(yōu)化了車間多AGV 任務分配的流程。Krell 等［8］提出了一種融合可視圖法的粒子群優(yōu)化算法，成功降低了能耗。Zhang 等［9］提出了一種改進A*算法，大大降低AGV 完成所有任務需要的行駛里程，從而節(jié)約了能源。Du 等［10］建立了一種改進的遺傳節(jié)能路徑規(guī)劃算法，并進行了對比實驗驗證它的優(yōu)越性。Hu 等［11］提出了一種帶基準線的節(jié)能路徑規(guī)劃方法，并設計仿真實驗驗證該方法的有效性。Zhu 等［12］提出了一種DQN（Double Deep Q Network，Double DQN）算法多AGV 節(jié)能路徑規(guī)劃算法，降低了AGV在未知環(huán)境下的能量消耗。

但是現(xiàn)有的研究仍然存在一些問題，目前大部分研究將節(jié)能指標聚焦在完成所有任務時間和路徑長度［13］上，將碰撞沖突次數(shù)也作為節(jié)能指標的研究較少。此外，目前現(xiàn)有的AGV 節(jié)能調度算法多采用傳統(tǒng)的啟發(fā)式算法，如A*算法［3，9］、Dijkstra 算法［14］、粒子群優(yōu)化算法［5，8］、遺傳算法［6，10，15-17］。這些算法無法適應當前動態(tài)生成任務的AGV 調度場景，而對適用動態(tài)環(huán)境的深度強化學習算法研究較少。此外，現(xiàn)有的研究大多將AGV 調度中的任務分配和路徑規(guī)劃分開計算，聯(lián)合計算AGV 任務分配和路徑規(guī)劃的AGV調度算法研究較少。

因此，本文建立以最小化完成所有任務的最長行駛路徑（以下簡稱最長路程）和碰撞沖突次數(shù)（以下簡稱沖突次數(shù)）為目標的汽車零件生產車間多AGV 節(jié)能調度模型，并提出了一種改進的Double DQN 算法對模型進行求解，最后在仿真環(huán)境中驗證算法的有效性并且與遺傳算法進行對比，證明基于改進Double DQN 的車間AGV調度算法的優(yōu)越性。

1 問題描述與數(shù)學模型

1.1 問題描述

目前汽車零件生產車間中，位于停靠區(qū)可使用的AGV 數(shù)量為k，其編號集合K為{1,2,3,…,g,…,k}。其停靠點集合o為{o1,o2,o3,…,ok}，停靠點ok坐標為(Ax0k,Ay0k)。車間中的各個區(qū)域會先后生成的搬運任務數(shù)為n，由k輛AGV 從各自停靠點ok出發(fā)去協(xié)同完成。但由于生產的持續(xù)性，同一時間里，汽車零件柔性生產車間中最多同時存在的待完成任務數(shù)量為m（m＜n)，可以得到一個任務最大個數(shù)為m的動態(tài)待完成任務列表M，一個長度最大值為m的動態(tài)待完成任務列表I={I1,I2,…Ii,Ij,…,Im}，新產生的任務為Im+1,Im+2,…,In。列表I中第i號任務記作Ii，其起點記作Iis，坐標為(Iisx,Iisy）；其終點記作Iie，坐標為(Iies,Iiey），W=o∪I表示所有任務位置和所有AGV停靠點的位置集合。

由于有多個AGV 協(xié)同完成任務，所以先要將任務列表I的任務進行均衡分配，保證每個AGV 任務負載相對均衡，然后根據任務分配的結果每個AGV 進行路徑規(guī)劃完成任務，路徑規(guī)劃的原則為在盡量避免碰撞的情況下縮短任務路徑。如果單個AGV 被分配到多個任務，也要在路徑規(guī)劃之前，確定執(zhí)行任務的先后順序。AGV 完成任務的過程可以用pick up and delivery來概括，首先前往任務起點完成pick up（取貨），接著前往任務終點送貨（delivery），當貨物送至終點任務完成。當AGV 完成被分配的任務后會暫時處于空閑狀態(tài)，等待任務列表I更新加入新的任務。為了兼顧各個AGV 任務負載均衡和利用效率，任務列表I中的新任務會按先完成先分配和輪流分配組合規(guī)則來進行分配。當新任務產生時，分配給處于空閑狀態(tài)的AGV；當存在多個空閑AGV 時，優(yōu)先分配給已完成任務數(shù)量較少的AGV。如此循環(huán)往復直到所有任務都被分配、AGV 完成被分配的任務，本輪作業(yè)結束。多AGV調度的流程如圖1所示。

圖1 多AGV調度流程示意圖

為了方便建模，本文對多AGV 調度問題做出如下假設：

（1）假設每臺AGV 在調度過程中都電量充足，不會因缺電停止工作。

（2）每臺AGV 在調度過程中保持勻速，速度為1 個單位長度/秒，不考慮起步的加速和停靠過程中的減速。

（3）每臺AGV 調度中裝卸物料的時間與調度時間相比忽略不計，不影響本文問題的解決，因此本文研究的問題不需要考慮裝載和卸載的時間。

（4）AGV 都是同質的，即所有硬件條件完全相同。

（5）車間的AGV 通道為橫縱向布置，AGV行駛距離用曼哈頓距離表示。

1.2 數(shù)學模型

為建立多AGV 調度數(shù)學模型，定義如下模型參數(shù)、決策變量、目標函數(shù)和約束條件。

（1）模型參數(shù)。

：表示第k輛AGV 從任務i起點到任務i終點搬運物料所用的時間；

：表示第k輛AGV 從任務i終點到下一任務j起點的運行時間；

：表示第k輛AGV 從停靠點ok行駛到第一個任務起點所用的時間；

Vk：表示第k輛AGV的運行速度。

（2）決策變量。

：0-1 變量，若第k輛AGV 完成任務i后接著完成任務j，等于1，否則為0；

：0-1 變量，如果任務i被第k輛AGV 完成，則等于1，否則等于0；

：整數(shù)變量，表示第k輛AGV 完成任務i接著再完成任務j，即完成其被分配任務的先后順序；

Smax：整數(shù)變量，表示所有AGV 完成所有任務的過程中所行駛的最長路程；

Fki：整數(shù)變量，表示第k輛AGV 完成任務i過程中的沖突次數(shù)。

（3）目標函數(shù)。

式（1）表示最小化最長路程，式（2）表示最小化AGV沖突次數(shù)。

（4）約束條件。

約束（4）保證第k輛AGV 從停靠點ok出發(fā)完成任務。約束（5）、（6）表示每個任務只會被每輛AGV完成一次。約束（7）表示所有任務都會被完成。約束（8）為線路平衡約束，用于均衡AGV任務分配。約束（9）表示AGV與任務之間的分配關系。約束（10）表示第k輛AGV 從停靠點出發(fā)到第一個任務起點間的距離時間關系。約束（11）表示第k輛AGV 完成任務i運行過程中的距離時間關系。約束（12）表示第k輛AGV 從任務i終點到下一個任務j起點運行過程中的距離時間關系。約束（13）為消除子循環(huán)約束。

2 算法設計

Double DQN 作為DQN 算法的改進，很大程度上緩解了傳統(tǒng)DQN 中Q 值估計過度的問題，具有穩(wěn)定性好、誤差較小、易于實現(xiàn)等特點。算法的主要步驟為狀態(tài)動作空間設計、獎勵函數(shù)設計、神經網絡訓練。

2.1 狀態(tài)動作空間設計

2.1.1 狀態(tài)空間設計

（1）AGV狀態(tài)。

表示第k輛AGV 的運行狀態(tài)，停止狀態(tài)用0 表示，運行狀態(tài)用1 表示，碰撞狀態(tài)用2 表示。

表示第k輛AGV 的實時位置，第k輛AGV 會在的區(qū)域內運行，第k輛AGV的實時位置坐標會連續(xù)變化，第k輛AGV 的實時坐標可以用來判斷第k輛AGV是否順利完成了避障以及是否完成了目標。

表示第k輛AGV 的實時目標位置，指第k輛AGV 當前要到達的目標位置（任務起點或終點）。

（2）任務狀態(tài)。

I表示當前動態(tài)待完成任務列表。

表示任務i的狀態(tài)。任務未分配狀態(tài)用0表示，當任務i剛產生時，處于未分配狀態(tài)；已分配待開始狀態(tài)用1 表示，當任務i被分配給第k輛AGV 但AGV 尚未到達任務起點時，處于已分配待開始狀態(tài)；任務進行中狀態(tài)用2表示，

當AGV 到達任務i起點提取到物料時，任務狀態(tài)轉變?yōu)檫M行中；任務已完成狀態(tài)用3 表示，當AGV 到達任務i終點卸下物料時，任務狀態(tài)變?yōu)橐淹瓿桑蝿読被從I中剔除。

2.1.2 動作空間設計

在多AGV 調度的過程中，每個AGV 有5 個動作，分別為0（靜止）、1（向上）、2（向右）、3（向下）、4（向左），每個AGV 的動作選擇ak構成了多AGV 調度優(yōu)化算法的動作空間A，如式（14）、（15）所示。

2.2 獎勵函數(shù)設計

本文根據目標函數(shù)將獎勵函數(shù)分為兩個部分：目標獎勵和避障獎勵。每個AGV 每到達一個目標點獲得的獎勵為1，每個AGV 每發(fā)生一次沖突獲得的獎勵為-1，以每個AGV 每完成一個任務為一個迭代，每個迭代的總獎勵為目標獎勵和避障獎勵之和，每個迭代的獎勵累加為總獎勵。

2.3 神經網絡設計

Double DQN 算法有當前Q 網絡和目標Q 網絡兩個神經網絡，輸出分別記為Qn(si,ai,θ)和Qt(s'i,aimax,θ-)，其中θ為神經網絡參數(shù)，隨著訓練的持續(xù)不斷更新。本文采用有兩個隱藏層的全連接結構來構建兩個神經網絡，損失函數(shù)為兩個神經網絡輸出Q值的均方誤差φ，如式（16）所示，其中N為目標網絡更新頻率。

與傳統(tǒng)Double DQN 算法不同，本文所提出的Double DQN 重點關注經驗中已經選擇過的動作，只更新已選擇動作的Q值，從而加快算法迭代，具體見如下算法流程。

改進Double DQN算法：車間多AGV調度優(yōu)化算法

輸入：狀態(tài)信息（每臺AGV 狀態(tài)信息、任務信息）、車間環(huán)境地圖Map

輸出：最大Q值、每臺AGV 動作選擇、每臺AGV目標位置

初始化：探索率ε、學習率α、獎勵衰減因子γ、初始狀態(tài)s0、經驗池memory、目標網絡更新頻率C

0 for episode

1 讀取車間環(huán)境地圖Map 數(shù)據以及當前狀態(tài)信息，根據組合規(guī)則得出每臺AGV 任務分配與任務排序結果和目標位置。

2 根據每臺AGV 當前觀測內容選擇每臺AGV 動作并記錄當前訓練步數(shù)step。

3 for eachA∈a

4 if random（0，1）＜ε

5=max（A）

6 else

7=random（A）

8 ifε_increment is not None elseε_max

//隨著訓練的持續(xù)逐漸增加ε到最大值

9 endif

10 endfor

11s'=s+

//將采用的動作作用于環(huán)境并計算出每臺AGV的總獎勵以及采取動作后的新狀態(tài)s'

12

//將計算的結果存入經驗池中

13 if（step＞200）and（step%5==0）:

//達到指定條件后開始訓練

14 learn（step）

//在經驗池中選取經驗開始訓練

15Qt(s,a)=Qn(s,a)

//當前Q網絡對當前所有狀態(tài)動作對的Q值估計復制給目標Q網絡

16 根據采集到的經驗，修改目標Q 網絡輸出的Q值，將之前經驗中選擇的動作a的Q值修改為Rtotal+γ*maxQt(s')，計算Qt'(s,a)與Qn(s,a)的均方誤差，作為損失函數(shù)反向傳遞給神經網絡進行訓練。

17 以目標網絡更新頻率C更新目標Q 網絡參數(shù)

18 endif

19s=s'//更新狀態(tài)

20 step++

21 判斷訓練是否繼續(xù)：到達終止狀態(tài)（所有AGV 完成所有任務）或達到迭代次數(shù)

22 如果達到終止條件，則終止；否則從第1步開始繼續(xù)訓練。

23 endfor

3 算法實施與結果分析

3.1 算法訓練過程

仿真訓練場景設置50*50的柵格地圖，經過測試，約訓練4000 個回合達到收斂，故設置訓練次數(shù)為4000，學習率為2e-2，設置探索概率ε由0.05逐漸衰減為0.03，采樣容量大小為1000。

圖2和圖3 分別展示了訓練過程中損失函數(shù)和獎勵函數(shù)的變化情況。

圖2 訓練過程中獎勵函數(shù)變化情況

圖3 訓練過程中損失函數(shù)變化情況

可以看出訓練4000個回合后算法基本收斂，由圖2可以看出在訓練早期，由于沒有訓練出有效的策略，所獲得的獎勵較低且不穩(wěn)定，隨著訓練的持續(xù)，智能體逐漸學習到有效策略，算法收斂。

3.2 算法性能對比

為充分展示算法性能，基于最長路程和總沖突次數(shù)兩個指標，選擇了不同規(guī)模的應用場景。柵格地圖大小設置為50*50，AGV數(shù)量設置為5，動態(tài)任務序列長度m和總任務數(shù)量n分別設置為不同的5 組值，即5 個任務場景。結果見表1，無論哪種場景，基于改進Double DQN 的調度算法的性能表現(xiàn)均優(yōu)于目前車間常用的傳統(tǒng)算法（遺傳算法，GA），隨著任務數(shù)量的不斷增加，基于改進Double DQN 的調度算法的性能優(yōu)勢越來越顯著，最長路程最多減少18.61%，沖突次數(shù)最多減少18.58%，通過減小行駛路徑長度、碰撞次數(shù)實現(xiàn)了節(jié)能。

表1 算法性能對比

4 結語

本文針對當前汽車零件生產車間AGV 調度算法性能落后、忽視任務分配與路徑規(guī)劃耦合性的問題，應用柵格地圖對多AGV 調度場景進行建模并提出了一種基于改進Double DQN 的AGV 調度算法，通過算法訓練和與傳統(tǒng)調度算法進行對比，證明了所提出算法的可行性以及在節(jié)能上的優(yōu)越性。