基于深度強(qiáng)化學(xué)習(xí)的汽車零件生產(chǎn)車間AGV節(jié)能調(diào)度算法

榮子鳴

（新疆大學(xué)商學(xué)院，烏魯木齊 830000）

0 引言

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

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

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

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

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 問(wèn)題描述

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

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

圖1 多AGV調(diào)度流程示意圖

為了方便建模，本文對(duì)多AGV 調(diào)度問(wèn)題做出如下假設(shè)：

（1）假設(shè)每臺(tái)AGV 在調(diào)度過(guò)程中都電量充足，不會(huì)因缺電停止工作。

（2）每臺(tái)AGV 在調(diào)度過(guò)程中保持勻速，速度為1 個(gè)單位長(zhǎng)度/秒，不考慮起步的加速和停靠過(guò)程中的減速。

（3）每臺(tái)AGV 調(diào)度中裝卸物料的時(shí)間與調(diào)度時(shí)間相比忽略不計(jì)，不影響本文問(wèn)題的解決，因此本文研究的問(wèn)題不需要考慮裝載和卸載的時(shí)間。

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

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

1.2 數(shù)學(xué)模型

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

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

：表示第k輛AGV 從任務(wù)i起點(diǎn)到任務(wù)i終點(diǎn)搬運(yùn)物料所用的時(shí)間；

：表示第k輛AGV 從任務(wù)i終點(diǎn)到下一任務(wù)j起點(diǎn)的運(yùn)行時(shí)間；

：表示第k輛AGV 從停靠點(diǎn)ok行駛到第一個(gè)任務(wù)起點(diǎn)所用的時(shí)間；

Vk：表示第k輛AGV的運(yùn)行速度。

（2）決策變量。

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

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

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

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

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

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

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

（4）約束條件。

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

2 算法設(shè)計(jì)

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

2.1 狀態(tài)動(dòng)作空間設(shè)計(jì)

2.1.1 狀態(tài)空間設(shè)計(jì)

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

表示第k輛AGV 的運(yùn)行狀態(tài)，停止?fàn)顟B(tài)用0 表示，運(yùn)行狀態(tài)用1 表示，碰撞狀態(tài)用2 表示。

表示第k輛AGV 的實(shí)時(shí)位置，第k輛AGV 會(huì)在的區(qū)域內(nèi)運(yùn)行，第k輛AGV的實(shí)時(shí)位置坐標(biāo)會(huì)連續(xù)變化，第k輛AGV 的實(shí)時(shí)坐標(biāo)可以用來(lái)判斷第k輛AGV是否順利完成了避障以及是否完成了目標(biāo)。

表示第k輛AGV 的實(shí)時(shí)目標(biāo)位置，指第k輛AGV 當(dāng)前要到達(dá)的目標(biāo)位置（任務(wù)起點(diǎn)或終點(diǎn)）。

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

I表示當(dāng)前動(dòng)態(tài)待完成任務(wù)列表。

表示任務(wù)i的狀態(tài)。任務(wù)未分配狀態(tài)用0表示，當(dāng)任務(wù)i剛產(chǎn)生時(shí)，處于未分配狀態(tài)；已分配待開(kāi)始狀態(tài)用1 表示，當(dāng)任務(wù)i被分配給第k輛AGV 但AGV 尚未到達(dá)任務(wù)起點(diǎn)時(shí)，處于已分配待開(kāi)始狀態(tài)；任務(wù)進(jìn)行中狀態(tài)用2表示，

當(dāng)AGV 到達(dá)任務(wù)i起點(diǎn)提取到物料時(shí)，任務(wù)狀態(tài)轉(zhuǎn)變?yōu)檫M(jìn)行中；任務(wù)已完成狀態(tài)用3 表示，當(dāng)AGV 到達(dá)任務(wù)i終點(diǎn)卸下物料時(shí)，任務(wù)狀態(tài)變?yōu)橐淹瓿桑蝿?wù)i被從I中剔除。

2.1.2 動(dòng)作空間設(shè)計(jì)

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

2.2 獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)

本文根據(jù)目標(biāo)函數(shù)將獎(jiǎng)勵(lì)函數(shù)分為兩個(gè)部分：目標(biāo)獎(jiǎng)勵(lì)和避障獎(jiǎng)勵(lì)。每個(gè)AGV 每到達(dá)一個(gè)目標(biāo)點(diǎn)獲得的獎(jiǎng)勵(lì)為1，每個(gè)AGV 每發(fā)生一次沖突獲得的獎(jiǎng)勵(lì)為-1，以每個(gè)AGV 每完成一個(gè)任務(wù)為一個(gè)迭代，每個(gè)迭代的總獎(jiǎng)勵(lì)為目標(biāo)獎(jiǎng)勵(lì)和避障獎(jiǎng)勵(lì)之和，每個(gè)迭代的獎(jiǎng)勵(lì)累加為總獎(jiǎng)勵(lì)。

2.3 神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)

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

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

改進(jìn)Double DQN算法：車間多AGV調(diào)度優(yōu)化算法

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

輸出：最大Q值、每臺(tái)AGV 動(dòng)作選擇、每臺(tái)AGV目標(biāo)位置

初始化：探索率ε、學(xué)習(xí)率α、獎(jiǎng)勵(lì)衰減因子γ、初始狀態(tài)s0、經(jīng)驗(yàn)池memory、目標(biāo)網(wǎng)絡(luò)更新頻率C

0 for episode

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

2 根據(jù)每臺(tái)AGV 當(dāng)前觀測(cè)內(nèi)容選擇每臺(tái)AGV 動(dòng)作并記錄當(dāng)前訓(xùn)練步數(shù)step。

3 for eachA∈a

4 if random（0，1）＜ε

5=max（A）

6 else

7=random（A）

8 ifε_(tái)increment is not None elseε_(tái)max

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

9 endif

10 endfor

11s'=s+

//將采用的動(dòng)作作用于環(huán)境并計(jì)算出每臺(tái)AGV的總獎(jiǎng)勵(lì)以及采取動(dòng)作后的新?tīng)顟B(tài)s'

12

//將計(jì)算的結(jié)果存入經(jīng)驗(yàn)池中

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

//達(dá)到指定條件后開(kāi)始訓(xùn)練

14 learn（step）

//在經(jīng)驗(yàn)池中選取經(jīng)驗(yàn)開(kāi)始訓(xùn)練

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

//當(dāng)前Q網(wǎng)絡(luò)對(duì)當(dāng)前所有狀態(tài)動(dòng)作對(duì)的Q值估計(jì)復(fù)制給目標(biāo)Q網(wǎng)絡(luò)

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

17 以目標(biāo)網(wǎng)絡(luò)更新頻率C更新目標(biāo)Q 網(wǎng)絡(luò)參數(shù)

18 endif

19s=s'//更新?tīng)顟B(tài)

20 step++

21 判斷訓(xùn)練是否繼續(xù)：到達(dá)終止?fàn)顟B(tài)（所有AGV 完成所有任務(wù)）或達(dá)到迭代次數(shù)

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

23 endfor

3 算法實(shí)施與結(jié)果分析

3.1 算法訓(xùn)練過(guò)程

仿真訓(xùn)練場(chǎng)景設(shè)置50*50的柵格地圖，經(jīng)過(guò)測(cè)試，約訓(xùn)練4000 個(gè)回合達(dá)到收斂，故設(shè)置訓(xùn)練次數(shù)為4000，學(xué)習(xí)率為2e-2，設(shè)置探索概率ε由0.05逐漸衰減為0.03，采樣容量大小為1000。

圖2和圖3 分別展示了訓(xùn)練過(guò)程中損失函數(shù)和獎(jiǎng)勵(lì)函數(shù)的變化情況。

圖2 訓(xùn)練過(guò)程中獎(jiǎng)勵(lì)函數(shù)變化情況

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

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

3.2 算法性能對(duì)比

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

表1 算法性能對(duì)比

4 結(jié)語(yǔ)

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