基于多智能體強化學(xué)習(xí)的露天礦車輛調(diào)度方法

李新華

(國家能源集團 神東煤炭集團有限責(zé)任公司,陜西 榆林 719315)

近年來,無人駕駛作為結(jié)合人工智能與工程技術(shù)的最新技術(shù),在各種露天礦山得到廣泛應(yīng)用,實現(xiàn)了對露天礦區(qū)的智能化控制和管理,從而提高了生產(chǎn)效率和安全性。研究應(yīng)用于露天礦的無人駕駛卡車的運輸調(diào)度,不僅有助于企業(yè)提高經(jīng)濟效益,降低資源消耗,而且對于實現(xiàn)露天礦的自動化和智能化開采具有重要意義[1-3]。隨著露天礦無人駕駛技術(shù)的不斷發(fā)展,基于遺傳算法、模擬退火等元啟發(fā)式算法以及基于線性規(guī)劃、整數(shù)規(guī)劃等傳統(tǒng)優(yōu)化方法已經(jīng)不能滿足露天礦車輛實時調(diào)度、高能耗比和提高調(diào)度智能化水平等新需求[4-6]。因此,將工程技術(shù)手段和人工智能技術(shù)結(jié)合,提高車輛調(diào)度的精確度和智能化水平、實現(xiàn)自動化控制和優(yōu)化管理已成為智慧礦山建設(shè)過程中亟待解決的問題[7]。

露天礦車輛調(diào)度問題本質(zhì)上是一個運輸成本最小化的優(yōu)化問題,一般采用傳統(tǒng)優(yōu)化方法或元啟發(fā)式算法。隨著無人駕駛技術(shù)的發(fā)展,針對露天礦車輛調(diào)度問題,相關(guān)研究主要從排隊論、線性規(guī)劃及多目標(biāo)優(yōu)化等3個方面開展了研究。排隊論算法是將卡車視作運輸隊列中等待裝礦/卸載服務(wù)的個體,并建立排隊論模型明確卡車運輸目的地,即裝礦/卸載點。雖然可以配置卡車的最佳方案,但存在車輛同質(zhì)性的約束[8]。線性規(guī)劃方法目前已經(jīng)被廣泛應(yīng)用于露天礦卡車調(diào)度模型,但隨著卡車數(shù)量的增加,存在組合爆炸的風(fēng)險[9]。多目標(biāo)優(yōu)化模型是國內(nèi)外露天礦車輛調(diào)度從業(yè)者研究的重點,這是由于在露天礦調(diào)度問題上不能只考慮單個經(jīng)濟指標(biāo)作為車輛調(diào)度的目標(biāo)[10]。張明[11]等以礦車運輸總成本和等待時間作為優(yōu)化目標(biāo),運用多目標(biāo)遺傳算法求解了露天礦車輛調(diào)度問題。此外,阮順領(lǐng)[12]等除了考慮卡車運輸成本和等待時間外,還將卸礦站品位偏差率作為優(yōu)化目標(biāo),最終結(jié)合歷史調(diào)度數(shù)據(jù)使用改進的人工魚群算法求解。程平[10]等綜合考慮電池電量、車鏟生產(chǎn)能力及礦石品位等多種影響因素,構(gòu)建了基于碳排放成本的露天礦新能源純電動卡車多目標(biāo)調(diào)度優(yōu)化模型?；诙嗄繕?biāo)優(yōu)化模型的露天礦調(diào)度方法雖然能夠考慮多重因素,從而求解出較優(yōu)的解,但存在模型參數(shù)多及求解耗時的問題。現(xiàn)有研究方法在一定程度上改善了露天礦車輛調(diào)度問題,但存在難以兼顧調(diào)度精度和調(diào)度效率的問題。

隨著強化學(xué)習(xí)(Reinforcement Learning,RL)算法的興起,也有一些基于強化學(xué)習(xí)的調(diào)度方法。葉則芳[13]等提出了一種改進的強化學(xué)習(xí)調(diào)度算法,在Spark調(diào)度模型中取得了良好的調(diào)度性能,有效解決了計算集群調(diào)度問題。朱家政[14]等針對傳統(tǒng)調(diào)度算法實時性較差而難以應(yīng)對復(fù)雜多變的實際生產(chǎn)調(diào)度環(huán)境的問題,提出了一種長短期記憶的近端策略優(yōu)化算法,用于解決復(fù)雜條件下的作業(yè)車間調(diào)度問題。強化學(xué)習(xí)模型能夠在短時間內(nèi)較好地給出復(fù)雜調(diào)度問題,是一個較優(yōu)的調(diào)度方法。

為實現(xiàn)對露天礦車輛的實時調(diào)度,擬提出基于多智能體強化學(xué)習(xí)的露天礦車輛調(diào)度方法。該方法基于集中式訓(xùn)練分布式執(zhí)行的范式構(gòu)建了一個多智能體強化學(xué)習(xí)模型,用于處理露天礦車輛調(diào)度問題。通過對露天礦車輛調(diào)度、裝礦點及卸礦點特征的分析,設(shè)計露天礦車輛調(diào)度仿真環(huán)境。構(gòu)建一個演員評論家框架的多智能體強化學(xué)習(xí)模型,用于對露天礦車輛調(diào)度。同時,對比分析所構(gòu)建的基于社交感知的多智能體深度確定性策略梯度(Socially aware-Multi-Agent Deep Deterministic Policy Gradient,S-MADDPG)模型與多智能體深度確定性策略梯度(Multi-Agent Deep Deterministic Policy Gradient,MADDPG)模型及深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG)模型等兩個典型模型的調(diào)度效率。最后,驗證所提方法的可行性。

1 相關(guān)理論基礎(chǔ)

1.1 強化學(xué)習(xí)

強化學(xué)習(xí)研究的是智能體在復(fù)雜環(huán)境下采取怎樣的動作最終獲取最大的獎勵。強化學(xué)習(xí)由智能體和環(huán)境兩部分組成。智能體通過對從環(huán)境中觀測到的狀態(tài)進行分析后做出動作,然后環(huán)境會給出執(zhí)行動作后的下一個狀態(tài)和該動作在復(fù)雜環(huán)境下獲得的獎勵。

在隨機過程中,馬爾科夫性[15]是指一個隨機過程在給定現(xiàn)在狀態(tài)st和過去狀態(tài)ht的情況下,未來狀態(tài)st+1的概率分布p僅依賴于當(dāng)前狀態(tài)的性質(zhì),其表達式為

p(st+1|st)=p(st+1|ht)

(1)

因此,智能體與環(huán)境的交互過程可以通過馬爾科夫決策過程(Markov Decision Process,MDP)表示。

通常情況下,智能體能觀測到的狀態(tài)都是部分信息,這種部分可觀測MDP通常被用一個七元組描述[S,A,T,R,Ω,O,γ][16]。其中:S表示狀態(tài)空間;A為動作空間;T(s′|s,a)表示狀態(tài)轉(zhuǎn)移概率;R為獎勵函數(shù);Ω(o,|s,a)表示觀測概率;O為觀測空間;γ為折扣因子。強化學(xué)習(xí)的狀態(tài)價值函數(shù)Vπ和動作價值函數(shù)Qπ可以分為即時獎勵和后續(xù)狀態(tài)折扣價值兩部分,分別定義為

Vπ(s)=

(2)

(3)

式中,π表示策略矩陣。

1.2 多智能體強化學(xué)習(xí)

多智能體強化學(xué)習(xí)是強化學(xué)習(xí)和多智能體體系結(jié)合而成的新領(lǐng)域。多智能體的核心是把系統(tǒng)分成若干智能體及自治的子系統(tǒng),在物理和地理上既可以分散且可以獨立執(zhí)行任務(wù),多智能體之間又可以相互通信、相互協(xié)調(diào)及共同完成任務(wù)。多智能體強化學(xué)習(xí)目前有集中式學(xué)習(xí)、獨立式學(xué)習(xí)和集中式訓(xùn)練分布式執(zhí)行等3種通用范式。集中式學(xué)習(xí)是將整個系統(tǒng)視為一個整體,與單智能體強化學(xué)習(xí)模型類似;獨立式學(xué)習(xí)是讓每個智能體獨立訓(xùn)練自己的策略,其建模簡單,但忽視了多智能體之間的聯(lián)系;集中式訓(xùn)練分布式執(zhí)行作為前兩者的折中選擇,在訓(xùn)練時利用全局視角,執(zhí)行過程中各自獨立。多智能體強化學(xué)習(xí)系統(tǒng)描述為

[N,E,a1,a2,…,aN,T,γ,r1,…,rN]

(4)

式中:N為智能體個數(shù);E為系統(tǒng)狀態(tài),一般指多智能體的聯(lián)合狀態(tài),例如可以是(x1,y1),(x2,y2),…,(xN,yN),即表示運輸卡車的位置坐標(biāo);a1,a2,…,aN表示智能體的動作合集;T表示狀態(tài)轉(zhuǎn)移函數(shù),可以根據(jù)當(dāng)前系統(tǒng)狀態(tài)和聯(lián)合動作給出下一狀態(tài)的概率分布;r1,…,rN表示智能體在多智能體采取聯(lián)合動作后各智能體分別獲得的獎勵。多智能體強化學(xué)習(xí)架構(gòu)示意圖如圖1所示。

圖1 多智能體強化學(xué)習(xí)架構(gòu)示意圖

2 露天礦車輛調(diào)度問題

在露天礦的實際開采過程中,系統(tǒng)需要協(xié)調(diào)多個裝礦點和卸載點之間的工作。礦車將礦物從裝礦點運輸?shù)揭粋€或多個卸載點進行作業(yè)[17]。裝礦點到卸載點距離不同,礦車產(chǎn)生的運輸成本也不同。因此,這里將露天礦車輛調(diào)度問題看作是求解礦車最小運輸成本的問題。

在露天礦車輛運輸過程中,礦車狀態(tài)可簡單地分為空載、待載、載入、運輸、帶卸、卸載及故障7種狀態(tài)。假設(shè)礦車從第i個裝礦點Mi載入到第i個裝礦點裝車再到第j個卸載點卸載,再回到Mi為一次完整的運輸調(diào)度過程,則該過程中產(chǎn)生的運輸成本為燃油成本、啟動成本及故障維修成本之和。其中:i=1,2,…,I,I為裝礦點數(shù)量;j=1,2,…,J,J為卸載點數(shù)量。

2.1 燃油成本

在一次調(diào)度過程中產(chǎn)生的燃油成本z1為礦車空載、運輸及卸載時所消耗的成本之和,其表達式為

(5)

2.2 啟動成本

礦車一次完整調(diào)度運輸過程中的啟動成本的表達式為

(6)

式中,P2表示每輛礦車的啟動成本。

2.3 故障維修成本

故障維修費用為

(7)

式中,P3表示每輛礦車的平均故障維修成本。因此,露天礦車輛運輸調(diào)度優(yōu)化模型為

minZ=min(z1+z2+z3)

(8)

式中:Vk表示第k輛礦車的裝載量;Qi表示對應(yīng)裝礦點的總礦量;S表示一次生產(chǎn)計劃中總調(diào)度次數(shù);gi表示對應(yīng)卸載點的卸載總量。

3 S-MADDPG模型構(gòu)建

3.1 強化學(xué)習(xí)環(huán)境

結(jié)合露天礦車輛調(diào)度的特點,設(shè)計了強化學(xué)習(xí)仿真環(huán)境,具體如圖2所示。其中,實心方框為裝載點,空心方框為卸載點。

圖2 露天礦強化學(xué)習(xí)仿真環(huán)境

為簡化強化學(xué)習(xí)模型,將隨時間的連續(xù)變化轉(zhuǎn)換為按時間片逐幀變化。也就是說,環(huán)境中的所有信息都會在每個時間片更新一次,時間片是環(huán)境的一個超參數(shù),可以進行調(diào)節(jié)。露天礦車輛調(diào)度環(huán)境可分為獎勵設(shè)置、裝載點礦量變化、車輛位置及車輛可選擇的路徑變化。

對于復(fù)雜問題而言,強化學(xué)習(xí)的獎勵設(shè)置通常都是較為稀疏的。為削弱強化學(xué)習(xí)模型獎勵的稀疏性,設(shè)置當(dāng)?shù)V車裝有礦物并執(zhí)行卸礦操作時,進行一次獎勵。這樣可激勵智能體執(zhí)行裝礦和卸礦操作,而不是進行無用的調(diào)度。在實際的露天礦生產(chǎn)過程中裝載點的礦量會實時發(fā)生變化,這種變化與裝礦點產(chǎn)礦能力相關(guān)。因此,需要對每個裝礦點的產(chǎn)礦速度進行設(shè)置,而不是將裝礦點的礦量假設(shè)為無限。

車輛的位置在該環(huán)境中用二維x-y坐標(biāo)表示。考慮到當(dāng)所有智能體走的路徑都是最優(yōu)的條件下礦車不會走回頭路,因此假設(shè)所有礦車類型相同,都不走回頭路,即只有當(dāng)?shù)V車走到卸載點或者裝載點的時候才能選擇路徑,當(dāng)走到路中間時不可回頭。此時,裝礦和卸礦時間各消耗一個時間片。

3.2 強化學(xué)習(xí)智能體

強化學(xué)習(xí)智能體是一種能夠通過與環(huán)境進行交互來學(xué)習(xí)最優(yōu)決策的人工智能系統(tǒng),其多智能體訓(xùn)練網(wǎng)絡(luò)如圖3所示[18]。其中,Q表示Q-學(xué)習(xí)模型。每個智能體網(wǎng)絡(luò)的輸入為當(dāng)前礦車的位置、裝貨狀態(tài)及所有裝礦點的礦量輸出礦車的行駛方向,評論家網(wǎng)絡(luò)的輸入為所有礦車的位置、裝貨情況及所有裝礦點的礦量。

圖3 多智能體訓(xùn)練網(wǎng)絡(luò)

4 實驗結(jié)果及分析

4.1 仿真環(huán)境

編程環(huán)境設(shè)置為Python3.9、Pytorch1.13,顯卡為Rtx3090,電腦環(huán)境為I9-12900k,搭建一個基于Tkinter0.1.0框架的仿真環(huán)境。

4.2 強化學(xué)習(xí)仿真環(huán)境

根據(jù)強化學(xué)習(xí)方法構(gòu)建強化學(xué)習(xí)仿真環(huán)境,為后續(xù)智能體網(wǎng)絡(luò)訓(xùn)練做準(zhǔn)備?；诙嘀悄荏w強化學(xué)習(xí)的露天礦無人車調(diào)度實驗仿真過程如圖4所示。環(huán)境中實心圓點為裝有礦物的礦車,空心圓點為沒有礦物的礦車。

圖4 露天礦無人車調(diào)度實驗仿真過程

(續(xù))圖4 露天礦無人車調(diào)度實驗仿真過程

4.3 模型訓(xùn)練過程分析

MADDPG模型是集中式學(xué)習(xí)的代表,其訓(xùn)練過程獎勵變化情況如圖5所示。該模型權(quán)重多、信息冗余,難以收斂。將整個系統(tǒng)視為一個整體,采用單智能體強化學(xué)習(xí)算法訓(xùn)練,解決了環(huán)境非平穩(wěn)問題,但需要全局通信,不可擴展,且在解決無通信、大規(guī)模和大動作空間方面存在不足。

圖5 MADDPG模型訓(xùn)練過程獎勵變化情況

DDPG模型是獨立式學(xué)習(xí)的代表,其訓(xùn)練過程獎勵變化情況如圖6所示。由圖6可以看出,平均獎勵隨著交互次數(shù)的增加波動較為明顯,但整體呈現(xiàn)出穩(wěn)定趨勢。但是,DDPG模型的獨立式學(xué)習(xí)策略忽視了多個智能體之間的聯(lián)系,這對于一些合作任務(wù)會增加學(xué)習(xí)過程的不穩(wěn)定性。

圖6 DDPG模型訓(xùn)練過程獎勵變化情況

S-MADDPG模型訓(xùn)練過程獎勵變化情況如圖7所示。作為折中,訓(xùn)練時擁有全局通信,提高學(xué)習(xí)效率,執(zhí)行時各自獨立決策,這在一定程度上改善了多智能體學(xué)習(xí)問題。S-MADDPG模型在改善環(huán)境非平穩(wěn)問題的同時,在合作任務(wù)中可以更好地適應(yīng)于協(xié)作的情況,通過訓(xùn)練智能體之間的合作和協(xié)調(diào)實現(xiàn)了較優(yōu)的運輸策略。

圖7 S-MADDPG模型訓(xùn)練過程獎勵變化情況

4.4 模型測試過程分析

不同模型測試過程獎勵變化情況如圖8所示。由圖8可以看出,所構(gòu)建的S-MADDPG模型的范式模型較其他模型效果更優(yōu)。該模型能夠在合作任務(wù)中通過協(xié)作、競爭和協(xié)調(diào)等機制,使得多個智能體能夠相互合作,有效地完成任務(wù)。

圖8 不同模型測試過程獎勵變化情況

4.5 多智能體礦車調(diào)度的實時性和能耗比分析

基于多智能體強化學(xué)習(xí)構(gòu)建的露天礦車輛調(diào)度方法能夠根據(jù)車輛自身信息和所有裝載點信息對車輛的路徑進行導(dǎo)引。在實驗過程中,計算出車輛路徑過程只需1 s,因此理論上完全能夠達到實時調(diào)度。

在強化學(xué)習(xí)的環(huán)境中車輛除了在裝載和卸載過程中是處于停車狀態(tài)外,其他狀態(tài)都保持在行進狀態(tài)中?？梢酝ㄟ^總的時間片減去裝載和卸載消耗的時間片得到車輛運行的時間片,表達式為

T=Tsum-Tstop

在每個時間片中,研究人員記錄了每輛車的位置、速度和油量等信息。通過計算每個時間片中每輛車消耗的油量,并將其與總時間片相乘,得出了測試過程中所有車輛的總耗油量。此外,在獎勵分析中,每卸礦一次進行一次獎勵,對每輛車在卸煤時進行了記錄和統(tǒng)計,并據(jù)此計算出每輛車的總裝載量和運礦量。由此可以發(fā)現(xiàn),通過該多智能體強化學(xué)習(xí)模型的應(yīng)用,不僅可以優(yōu)化車輛調(diào)度系統(tǒng),還可以提高運輸效率并降低成本。

5 結(jié)語

針對露天礦車輛調(diào)度問題,提出了一種基于多智能體強化學(xué)習(xí)的露天礦車輛調(diào)度方法,旨在通過協(xié)同決策和資源共享提高車輛調(diào)度效率和成本效益。該方法的核心是將多個智能體進行耦合,并使其在任務(wù)執(zhí)行中實現(xiàn)協(xié)調(diào)和協(xié)作,從而能夠更好地應(yīng)對復(fù)雜的調(diào)度環(huán)境和動態(tài)變化的任務(wù)需求。為了驗證所提方法的有效性,將所構(gòu)建的S-MADDPG模型與MADDOG模型、DDPG模型等兩個經(jīng)典模型在實時性和能耗比等方面進行對比。驗證結(jié)果表明,所提方法能夠改善卡車調(diào)度的實時性問題,并能提高露天礦車輛調(diào)度能耗比。通過該多智能體強化學(xué)習(xí)模型的應(yīng)用,可以實現(xiàn)車輛的自主調(diào)度、多智能體協(xié)同決策、動態(tài)資源分配和成本優(yōu)化等功能。