基于多智能體強(qiáng)化學(xué)習(xí)的多AGV路徑規(guī)劃方法

劉 輝，肖 克，王京擘

（青島大學(xué) 自動(dòng)化系，青島266071）

AGV路徑規(guī)劃是指為每個(gè)AGV 規(guī)劃一條從起始地址到目標(biāo)地址的無(wú)碰撞最優(yōu)路徑[1-2]。AGV路徑規(guī)劃方法有運(yùn)籌學(xué)模型優(yōu)化方法、A*算法[3]及其各種變體和各種智能優(yōu)化方法，如遺傳算法[4]，蟻群算法[5]，粒子群算法[6]等，強(qiáng)化學(xué)習(xí)通過(guò)獎(jiǎng)賞與懲罰來(lái)優(yōu)化馬爾科夫決策過(guò)程中的智能體的策略，它不依賴環(huán)境模型和先驗(yàn)知識(shí)，逐漸成為機(jī)器人在路徑規(guī)劃的研究熱點(diǎn)[7-8]，強(qiáng)化學(xué)習(xí)也被嘗試用于解決多智能體協(xié)作問(wèn)題，如多路口交通信號(hào)燈協(xié)調(diào)控制問(wèn)題[9]等。常見(jiàn)的多智能體強(qiáng)化學(xué)習(xí)有EMA Q-learning[10]、WoLF-PHC[11]、Nash Q-Learning[12]等，另外強(qiáng)化學(xué)習(xí)也被用來(lái)和其他算法結(jié)合解決路徑規(guī)劃問(wèn)題，文獻(xiàn)[13]將多智能體環(huán)境虛擬為人工勢(shì)能場(chǎng)，通過(guò)先驗(yàn)知識(shí)獲取相應(yīng)的勢(shì)能值，再利用分層強(qiáng)化學(xué)習(xí)進(jìn)行更新策略，文獻(xiàn)[14]在強(qiáng)化學(xué)習(xí)的基礎(chǔ)上使用神經(jīng)網(wǎng)絡(luò)來(lái)估計(jì)Q值，用以解決移動(dòng)機(jī)器人的避障問(wèn)題。

針對(duì)傳統(tǒng)多智能體強(qiáng)化學(xué)習(xí)在路徑規(guī)劃時(shí)容易陷入維數(shù)災(zāi)難和局部最優(yōu)等問(wèn)題，本文根據(jù)傳統(tǒng)的Q-learning 提出一種多智能體獨(dú)立強(qiáng)化學(xué)習(xí)MRF Q-learning算法，智能體不需要知道其他智能體動(dòng)作，減小了動(dòng)作空間，將Boltzmann 策略與ε-greedy策略結(jié)合，更好地協(xié)調(diào)探索與利用，通過(guò)獲得全局最大累積回報(bào)的頻率更新Q值公式，以獲得全局最大累積回報(bào)。

1 路徑規(guī)劃框架

1.1 環(huán)境建模

路徑規(guī)劃常用的建模方法有柵格法、可視圖法和拓?fù)涞貓D法等，本文采用柵格法對(duì)AGV 工作環(huán)境進(jìn)行離散化處理，如圖1所示。

圖1 AGV 運(yùn)輸任務(wù)環(huán)境Fig.1 Environment for AGV’s transport missions

在貨物運(yùn)輸多AGV 環(huán)境中，AGV 之間需要通過(guò)協(xié)調(diào)合作以最短的時(shí)間完成任務(wù)，地圖中的柵格通過(guò)坐標(biāo)來(lái)表示，根據(jù)AGV和工作站等坐標(biāo)位置來(lái)描述它們之間的聯(lián)系，整個(gè)環(huán)境被分為兩類(lèi)工作區(qū)，分別為智能體的獨(dú)自運(yùn)輸區(qū)（運(yùn)輸區(qū)域1、運(yùn)輸區(qū)域2）和公共運(yùn)輸區(qū)，圖中圓形圖標(biāo)代表AGV，方形圖標(biāo)代表工作站，工作站在地圖中隨機(jī)分布，但每個(gè)區(qū)域僅有2個(gè)工作站。

1.2 任務(wù)分配

單AGV路徑規(guī)劃任務(wù)中的AGV 僅需要最大化自己的利益，而本文主要研究多智能體之間合作任務(wù)，完成運(yùn)送任務(wù)的路徑規(guī)劃問(wèn)題，需要智能體最大化整體利益，我們?cè)O(shè)置除了公共運(yùn)輸區(qū)兩個(gè)AGV 都可進(jìn)入外，AGV1和AGV2分別只能在運(yùn)輸區(qū)域1和運(yùn)輸區(qū)域2內(nèi)移動(dòng)，我們并不指定每個(gè)AGV運(yùn)輸貨物所經(jīng)過(guò)的工作站數(shù)量，任務(wù)的目標(biāo)為協(xié)調(diào)優(yōu)化兩個(gè)AGV 在各自運(yùn)輸區(qū)和公共運(yùn)輸區(qū)運(yùn)送貨物的行駛軌跡，要在避免碰撞的情況下，使用最少的時(shí)間步長(zhǎng)將足量的貨物運(yùn)送至所有的工作站。

1.3 路徑規(guī)劃算法

靜態(tài)路徑規(guī)劃問(wèn)題中，對(duì)全局信息已經(jīng)掌握，單AGV路徑規(guī)劃時(shí)不會(huì)受到其他AGV的影響，能夠較好地找到理論的最優(yōu)路徑，但對(duì)于多AGV路徑規(guī)劃，多個(gè)AGV 之間相互影響，難以獲取整個(gè)全局信息，另外，由于需要多智能體相互配合完成任務(wù)，對(duì)于常見(jiàn)的一些路徑規(guī)劃算法難以處理智能體之間聯(lián)系，獲得時(shí)間最優(yōu)路徑，因此本文提出一種多智能體強(qiáng)化學(xué)習(xí)MRF Q-learning 方法來(lái)解決多AGV 合作路徑規(guī)劃問(wèn)題，目標(biāo)為獲得全局最大累積回報(bào)，從而以最短的時(shí)間步長(zhǎng)完成任務(wù)。

2 多智能體強(qiáng)化學(xué)習(xí)路徑規(guī)劃算法

2.1 Q 學(xué)習(xí)

Q-learning（Q 學(xué)習(xí)）是一種經(jīng)典的強(qiáng)化學(xué)習(xí)算法，它將智能體在每個(gè)狀態(tài)下采取的動(dòng)作的Q值用Q_table 進(jìn)行存儲(chǔ)，通過(guò)不斷迭代更新，逼近目標(biāo)函數(shù)Q*，而且不需要環(huán)境的先驗(yàn)知識(shí)，是一種modelfree（無(wú)模型）算法，其Q值更新公式如下：

式中：r為狀態(tài)s 下選擇動(dòng)作a時(shí)獲得的立即回報(bào)；A為智能體的動(dòng)作集；α為學(xué)習(xí)率，表示Q值更新的程度；γ是折扣因子，γ越小則越注重當(dāng)前的回報(bào)。由于Q-learning為單智能強(qiáng)化學(xué)習(xí)方法，而多AGV路徑規(guī)劃為多智能體環(huán)境并且需要AGV相互合作，因此我們?cè)谄浠A(chǔ)上，設(shè)計(jì)出一種能夠解決合作問(wèn)題的多智能體強(qiáng)化學(xué)習(xí)方法。

2.2 多智能體強(qiáng)化學(xué)習(xí)

多智能體強(qiáng)化學(xué)習(xí)模型在元素組成上與單智能體強(qiáng)化學(xué)習(xí)類(lèi)似，包含智能體、環(huán)境狀態(tài)、動(dòng)作、回報(bào)，模型如圖2所示，多個(gè)智能體之間相互作用與環(huán)境進(jìn)行交互，根據(jù)獲取的狀態(tài)和回報(bào)來(lái)學(xué)習(xí)改善自己的策略。

圖2 多智能體強(qiáng)化學(xué)習(xí)模型Fig.2 Multi-agent reinforcement learning model

2.3 MRF Q-learning路徑規(guī)劃算法設(shè)計(jì)

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

多智能體系統(tǒng)中狀態(tài)轉(zhuǎn)變受到其他智能體影響，另外本任務(wù)需要AGV 將貨物送至多個(gè)工作站，所以環(huán)境狀態(tài)的定義與AGV是否經(jīng)歷過(guò)工作站息息相關(guān)，因此我們根據(jù)每個(gè)智能體的位置，工作站是否收到貨物來(lái)定義系統(tǒng)的狀態(tài)，狀態(tài)定義為

式中：si為AGVi的位置；vj為工作站j的收到貨物的狀態(tài)；vj∈｛0，1｝，0代表未收到貨物，1代表已收到貨物，此時(shí)狀態(tài)空間大小為10000×2j。

在多智能體合作任務(wù)中，由于AGV 之間需要進(jìn)行交互，因此許多多智能體強(qiáng)化學(xué)習(xí)算法需要智能體之間分享動(dòng)作信息來(lái)更新策略，因此聯(lián)合動(dòng)作集為A=A1×A2，…，×An，其中Ai為智能體i的可行動(dòng)作集，此時(shí)每個(gè)智能體都需要小的空間存儲(chǔ)Q值，隨著智能體數(shù)的增多，占用的空間會(huì)以指數(shù)級(jí)增長(zhǎng)，因此本文采用一種獨(dú)立強(qiáng)化學(xué)習(xí)方法解決聯(lián)合維數(shù)災(zāi)問(wèn)題，每個(gè)智能體只需要使用自己的動(dòng)作和其他信息來(lái)更新策略，因此Q值存儲(chǔ)空間減小為在本任務(wù)中每個(gè)AGV的動(dòng)作集都為包含上、下、左、右4個(gè)動(dòng)作。

2.3.2 獎(jiǎng)勵(lì)函數(shù)

獎(jiǎng)勵(lì)函數(shù)代表了智能體所選擇的策略的價(jià)值，因此智能體是根據(jù)獎(jiǎng)勵(lì)函數(shù)的指導(dǎo)來(lái)完成任務(wù)的。獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)的優(yōu)劣會(huì)直接影響學(xué)習(xí)到的策略的好壞，常用的設(shè)置獎(jiǎng)勵(lì)函數(shù)的方法有稀疏獎(jiǎng)勵(lì)、分布獎(jiǎng)勵(lì)、形式化獎(jiǎng)勵(lì)等，本文使用的為稀疏獎(jiǎng)勵(lì)函數(shù)，如式（3）所示：

式中：r1，r2，r3，r4>0，在路徑規(guī)劃任務(wù)中，由于AGV之間有著部分相同的工作領(lǐng)域，因此可能會(huì)發(fā)生碰撞以及出界的情況，為了避免AGV 發(fā)生碰撞或者出界，我們?cè)O(shè)置當(dāng)發(fā)生以上2種情況時(shí)，AGV 會(huì)獲得一定的懲罰，即負(fù)的回報(bào)，當(dāng)智能體完成目標(biāo)時(shí)會(huì)給智能體較多的獎(jiǎng)勵(lì)，以確保智能體能夠完成任務(wù)，另外，為了使智能體學(xué)到完成任務(wù)的最短時(shí)間步長(zhǎng)，我們?cè)O(shè)置AGV每次采取行動(dòng)都會(huì)獲得一定的負(fù)的回報(bào)，因此AGV 會(huì)學(xué)習(xí)以較快的速度完成任務(wù)。

2.3.3 動(dòng)作選擇策略

強(qiáng)化學(xué)習(xí)算法常常面臨探索與利用的問(wèn)題，探索是嘗試不同的動(dòng)作以獲得一些更好的策略，利用則是采取當(dāng)前狀態(tài)下的最優(yōu)策略，探索更加注重于長(zhǎng)期利益，而利用則是對(duì)短期利益的最大化，因此需要平衡兩者之間的關(guān)系，常用的探索與利用策略有ε-greedy 策略、Boltzmann 策略、ucb 策略等。

由于多AGV路徑規(guī)劃受到多個(gè)智能體的影響，容易陷入局部最優(yōu)的情況，為了避免錯(cuò)過(guò)一些短期表現(xiàn)一般而有著較好的長(zhǎng)期表現(xiàn)的動(dòng)作，本文將ε-greedy 探索策略與Boltzmann 策略結(jié)合，具體決策方法如下所示：

式中：αi為智能體i 選擇的動(dòng)作；ε∈[0，1]為探索率，設(shè)置以ε的概率選擇隨機(jī)選擇一個(gè)動(dòng)作，以1-ε的概率根據(jù)Boltzmann 探索策略進(jìn)行動(dòng)作選擇，Boltzmann 動(dòng)作選擇的概率如下所示：

式中：pi（ai）為智能體i 選擇動(dòng)作ai的概率；Qi（ai）為智能體i 選擇動(dòng)作ai的Q值；∣Ai∣為智能體i的動(dòng)作集。

2.3.4 最大回報(bào)頻率價(jià)值更新函數(shù)

由于多AGV路徑規(guī)劃問(wèn)題為多狀態(tài)優(yōu)化任務(wù)，目標(biāo)為最大化全局累積回報(bào)，我們據(jù)此設(shè)計(jì)了一種全局最大累積回報(bào)頻率強(qiáng)化學(xué)習(xí)方法來(lái)解決路徑規(guī)劃問(wèn)題，首先，每個(gè)智能體分享其回報(bào)，智能體i 獲得的立即回報(bào)為ri，則全局立即回報(bào)為

在每個(gè)episode 都記錄每個(gè)時(shí)刻的立即回報(bào)、選擇的動(dòng)作、狀態(tài)等，每個(gè)狀態(tài)被經(jīng)歷到達(dá)一定次數(shù)后，在每個(gè)episode 結(jié)束后根據(jù)每個(gè)狀態(tài)s 下的全局累積回報(bào)R 獲取全局最大累積回報(bào)Rmax，全局折扣累積回報(bào)定義如下：

式中：γ為折扣因子，γ越小則越注重當(dāng)前的回報(bào)；K代表一個(gè)episode所用的時(shí)間；r（t+1）代表在t+1時(shí)刻的全局立即回報(bào)，由式（6）獲得，根據(jù)全局最大累積回報(bào)Rmax更新最大累積回報(bào)獲取的頻率，獲得全局最大累積回報(bào)的頻率公式如下：

式中：nai為智能體i 在狀態(tài)s 選擇動(dòng)作ai的次數(shù)；nmax_ai為智能體i 在狀態(tài)s 選擇動(dòng)作ai獲得全局最大累積回報(bào)的次數(shù)。根據(jù)頻率f（s，ai）更新Q值，如下：

通過(guò)引入全局最大累積回報(bào)頻率更新Q值，能使得智能體能最大化整體的利益，找到完成任務(wù)整體耗時(shí)最短路徑。

算法步驟如下所示：

步驟1定義所有AGV的立即回報(bào)之和為全局立即回報(bào)

步驟2初始化每個(gè)AGV的Q值、動(dòng)作選擇次數(shù)、全局最大累積回報(bào)及獲取次數(shù)等變量；

步驟3根據(jù)式（4）Boltzmann與ε-greedy 結(jié)合策略進(jìn)行動(dòng)作選擇；

步驟4記錄每個(gè)時(shí)間步長(zhǎng)的動(dòng)作、狀態(tài)、立即回報(bào)等變量；

步驟5每種狀態(tài)被經(jīng)歷一定次數(shù)后，在每個(gè)episode 結(jié)束后，根據(jù)記錄獲取每個(gè)狀態(tài)s 下的全局最大累積回報(bào)Rmax；

步驟6統(tǒng)計(jì)AGV 選擇動(dòng)作ai時(shí)獲得歷史全局最大累積回報(bào)的次數(shù)，根據(jù)式（8）更新獲得全局最大累積回報(bào)的頻率f；

步驟7根據(jù)式（9）更新Q值函數(shù)；

步驟8若到達(dá)預(yù)先設(shè)置的學(xué)習(xí)次數(shù)，進(jìn)入步驟9，否則繼續(xù)執(zhí)行步驟3；

步驟9每個(gè)AGV 選擇具有最大Q值的動(dòng)作。

2.4 MRF Q-learning算法重復(fù)博弈驗(yàn)證

為了驗(yàn)證MRF Q-learning算法的性能，我們?cè)O(shè)置了2種最優(yōu)納什均衡（具有全局最大立即回報(bào)的納什均衡點(diǎn)）不同分布的兩人兩動(dòng)作重復(fù)博弈，最優(yōu)納什均衡點(diǎn)用括號(hào)標(biāo)記，如圖3所示，由于重復(fù)博弈為只含有一個(gè)狀態(tài)，因此在重復(fù)博弈中，MRF Q-learning算法中相關(guān)的全局最大累積回報(bào)為全局最大立即回報(bào)。

圖3 重復(fù)博弈支付矩陣Fig.3 Repeated game payoff matrices

我們?cè)O(shè)置12 組不同的初始概率及Q值（初始概率如圖4和圖5中圓點(diǎn)所示）每次實(shí)驗(yàn)運(yùn)行了20000步，最終結(jié)果如圖4和圖5所示，圖中pa0代表智能體1 選擇動(dòng)作a0的概率，pb0代表智能體2 選擇動(dòng)作b0概率，可以看出MRF Q-learning算法在兩種情況的重復(fù)博弈中都收斂到了最優(yōu)納什均衡。

圖4 Case 1 動(dòng)作選擇概率Fig.4 Probability of choosing action in Case 1

圖5 Case 2 動(dòng)作選擇概率Fig.5 Probability of choosing action in Case 2

3 實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證MRF Q-learning算法解決路徑規(guī)劃問(wèn)題的有效性，通過(guò)路徑規(guī)劃仿真進(jìn)行測(cè)試，并與多智能體強(qiáng)化學(xué)習(xí)算法EMA Q-learning 進(jìn)行對(duì)比。兩種地圖環(huán)境如圖6和圖7所示，具體任務(wù)在第一節(jié)中做出了詳細(xì)介紹，另外，我們?cè)O(shè)置當(dāng)AGV 行動(dòng)超過(guò)500個(gè)單位時(shí)間步長(zhǎng)時(shí)任務(wù)結(jié)束，任務(wù)完成或結(jié)束記為一個(gè)episode，若兩個(gè)AGV 發(fā)生碰撞或出界，則它們保持上一時(shí)刻的位置，每種環(huán)境下我們都運(yùn)行了20000 episodes，我們對(duì)此任務(wù)的具體的獎(jiǎng)勵(lì)函數(shù)做如下設(shè)置：

并設(shè)置學(xué)習(xí)率α=0.4，折扣因子γ=0.9，在episode 開(kāi)始時(shí)需要對(duì)動(dòng)作進(jìn)行大量探索，設(shè)置探索率ε為一個(gè)較大的值，然后逐漸減小，T=1 并隨著episode 不斷衰減，探索率設(shè)置如下：式中：n為當(dāng)前episode 數(shù)；M為最大episode 數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析

我們根據(jù)程序運(yùn)行結(jié)果，評(píng)價(jià)階段最終路線如圖6和圖7所示，圖中實(shí)線表示MRF Q-learning的最終路徑，虛線表示EMA Q-learning的最終路徑。

圖6 環(huán)境1 實(shí)驗(yàn)結(jié)果示意圖Fig.6 Experimental results diagram in environment 1

圖7 環(huán)境2 實(shí)驗(yàn)結(jié)果示意圖Fig.7 Experimental results diagram in environment 2

兩種環(huán)境中每種算法在評(píng)價(jià)階段的時(shí)間步長(zhǎng)與最優(yōu)時(shí)間步長(zhǎng)如圖8所示。

圖8 評(píng)價(jià)階段的時(shí)間步長(zhǎng)Fig.8 Time steps in the evaluation phase

可以看出本文的MRF Q-learning 在兩種環(huán)境中都找到了時(shí)間步長(zhǎng)最短路徑，而EMA Q-learning雖然在第一種環(huán)境中也以最短的時(shí)間步長(zhǎng)完成了任務(wù)，但在環(huán)境2 中兩個(gè)AGV 之間沒(méi)能相互配合，左邊的AGV1 經(jīng)過(guò)了4個(gè)工作站，而AGV2 僅經(jīng)過(guò)2個(gè)工作站，延長(zhǎng)了運(yùn)輸時(shí)間，且在兩處產(chǎn)生了出界的情形，雖然也完成了運(yùn)送任務(wù)，但沒(méi)能找到時(shí)間最短路徑。

圖9為兩種算法在環(huán)境2 中學(xué)習(xí)階段的平均步長(zhǎng)，可以看出EMA Q-learning 一開(kāi)始學(xué)習(xí)速度較快，MRF Q-learning 由 于 將Boltzmann與ε-greedy結(jié)合，學(xué)習(xí)過(guò)程中會(huì)較多地探索其他動(dòng)作，因此前期學(xué)習(xí)速度相對(duì)較慢。兩種算法在最后都收斂到了較短路徑，但MRF Q-learning最終收斂到了比EMA Q-learning時(shí)間步長(zhǎng)更短的路徑。

圖9 學(xué)習(xí)階段的平均時(shí)間步長(zhǎng)Fig.9 Average time steps in the learning phase

4 結(jié)語(yǔ)

本文針對(duì)工作站貨物運(yùn)輸多AGV的路徑規(guī)劃問(wèn)題，提出一種多智能體強(qiáng)化學(xué)習(xí)MRF Q-learning算法，算法采用全局最大累積回報(bào)頻率進(jìn)行更新Q值公式，以獲得全局最大累積回報(bào)，每個(gè)智能體不需要其他智能體的動(dòng)作，避免了聯(lián)合動(dòng)作維數(shù)災(zāi)，將Boltzmann 策略與ε-greedy 策略結(jié)合，更好地協(xié)調(diào)探索與利用，多AGV路徑規(guī)劃仿真結(jié)果說(shuō)明，與其他多智能體強(qiáng)化學(xué)習(xí)算法相比，本文提出的MRF Qlearning算法能夠找到最優(yōu)路徑使總運(yùn)輸時(shí)間最短。