基于多智能體強化學習的多AGV路徑規劃方法

劉 輝，肖 克，王京擘

（青島大學 自動化系，青島266071）

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

針對傳統多智能體強化學習在路徑規劃時容易陷入維數災難和局部最優等問題，本文根據傳統的Q-learning 提出一種多智能體獨立強化學習MRF Q-learning算法，智能體不需要知道其他智能體動作，減小了動作空間，將Boltzmann 策略與ε-greedy策略結合，更好地協調探索與利用，通過獲得全局最大累積回報的頻率更新Q值公式，以獲得全局最大累積回報。

1 路徑規劃框架

1.1 環境建模

路徑規劃常用的建模方法有柵格法、可視圖法和拓撲地圖法等，本文采用柵格法對AGV 工作環境進行離散化處理，如圖1所示。

圖1 AGV 運輸任務環境Fig.1 Environment for AGV’s transport missions

在貨物運輸多AGV 環境中，AGV 之間需要通過協調合作以最短的時間完成任務，地圖中的柵格通過坐標來表示，根據AGV和工作站等坐標位置來描述它們之間的聯系，整個環境被分為兩類工作區，分別為智能體的獨自運輸區（運輸區域1、運輸區域2）和公共運輸區，圖中圓形圖標代表AGV，方形圖標代表工作站，工作站在地圖中隨機分布，但每個區域僅有2個工作站。

1.2 任務分配

單AGV路徑規劃任務中的AGV 僅需要最大化自己的利益，而本文主要研究多智能體之間合作任務，完成運送任務的路徑規劃問題，需要智能體最大化整體利益，我們設置除了公共運輸區兩個AGV 都可進入外，AGV1和AGV2分別只能在運輸區域1和運輸區域2內移動，我們并不指定每個AGV運輸貨物所經過的工作站數量，任務的目標為協調優化兩個AGV 在各自運輸區和公共運輸區運送貨物的行駛軌跡，要在避免碰撞的情況下，使用最少的時間步長將足量的貨物運送至所有的工作站。

1.3 路徑規劃算法

靜態路徑規劃問題中，對全局信息已經掌握，單AGV路徑規劃時不會受到其他AGV的影響，能夠較好地找到理論的最優路徑，但對于多AGV路徑規劃，多個AGV 之間相互影響，難以獲取整個全局信息，另外，由于需要多智能體相互配合完成任務，對于常見的一些路徑規劃算法難以處理智能體之間聯系，獲得時間最優路徑，因此本文提出一種多智能體強化學習MRF Q-learning 方法來解決多AGV 合作路徑規劃問題，目標為獲得全局最大累積回報，從而以最短的時間步長完成任務。

2 多智能體強化學習路徑規劃算法

2.1 Q 學習

Q-learning（Q 學習）是一種經典的強化學習算法，它將智能體在每個狀態下采取的動作的Q值用Q_table 進行存儲，通過不斷迭代更新，逼近目標函數Q*，而且不需要環境的先驗知識，是一種modelfree（無模型）算法，其Q值更新公式如下：

式中：r為狀態s 下選擇動作a時獲得的立即回報；A為智能體的動作集；α為學習率，表示Q值更新的程度；γ是折扣因子，γ越小則越注重當前的回報。由于Q-learning為單智能強化學習方法，而多AGV路徑規劃為多智能體環境并且需要AGV相互合作，因此我們在其基礎上，設計出一種能夠解決合作問題的多智能體強化學習方法。

2.2 多智能體強化學習

多智能體強化學習模型在元素組成上與單智能體強化學習類似，包含智能體、環境狀態、動作、回報，模型如圖2所示，多個智能體之間相互作用與環境進行交互，根據獲取的狀態和回報來學習改善自己的策略。

圖2 多智能體強化學習模型Fig.2 Multi-agent reinforcement learning model

2.3 MRF Q-learning路徑規劃算法設計

2.3.1 狀態空間和動作空間設計

多智能體系統中狀態轉變受到其他智能體影響，另外本任務需要AGV 將貨物送至多個工作站，所以環境狀態的定義與AGV是否經歷過工作站息息相關，因此我們根據每個智能體的位置，工作站是否收到貨物來定義系統的狀態，狀態定義為

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

在多智能體合作任務中，由于AGV 之間需要進行交互，因此許多多智能體強化學習算法需要智能體之間分享動作信息來更新策略，因此聯合動作集為A=A1×A2，…，×An，其中Ai為智能體i的可行動作集，此時每個智能體都需要小的空間存儲Q值，隨著智能體數的增多，占用的空間會以指數級增長，因此本文采用一種獨立強化學習方法解決聯合維數災問題，每個智能體只需要使用自己的動作和其他信息來更新策略，因此Q值存儲空間減小為在本任務中每個AGV的動作集都為包含上、下、左、右4個動作。

2.3.2 獎勵函數

獎勵函數代表了智能體所選擇的策略的價值，因此智能體是根據獎勵函數的指導來完成任務的。獎勵函數設計的優劣會直接影響學習到的策略的好壞，常用的設置獎勵函數的方法有稀疏獎勵、分布獎勵、形式化獎勵等，本文使用的為稀疏獎勵函數，如式（3）所示：

式中：r1，r2，r3，r4>0，在路徑規劃任務中，由于AGV之間有著部分相同的工作領域，因此可能會發生碰撞以及出界的情況，為了避免AGV 發生碰撞或者出界，我們設置當發生以上2種情況時，AGV 會獲得一定的懲罰，即負的回報，當智能體完成目標時會給智能體較多的獎勵，以確保智能體能夠完成任務，另外，為了使智能體學到完成任務的最短時間步長，我們設置AGV每次采取行動都會獲得一定的負的回報，因此AGV 會學習以較快的速度完成任務。

2.3.3 動作選擇策略

強化學習算法常常面臨探索與利用的問題，探索是嘗試不同的動作以獲得一些更好的策略，利用則是采取當前狀態下的最優策略，探索更加注重于長期利益，而利用則是對短期利益的最大化，因此需要平衡兩者之間的關系，常用的探索與利用策略有ε-greedy 策略、Boltzmann 策略、ucb 策略等。

由于多AGV路徑規劃受到多個智能體的影響，容易陷入局部最優的情況，為了避免錯過一些短期表現一般而有著較好的長期表現的動作，本文將ε-greedy 探索策略與Boltzmann 策略結合，具體決策方法如下所示：

式中：αi為智能體i 選擇的動作；ε∈[0，1]為探索率，設置以ε的概率選擇隨機選擇一個動作，以1-ε的概率根據Boltzmann 探索策略進行動作選擇，Boltzmann 動作選擇的概率如下所示：

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

2.3.4 最大回報頻率價值更新函數

由于多AGV路徑規劃問題為多狀態優化任務，目標為最大化全局累積回報，我們據此設計了一種全局最大累積回報頻率強化學習方法來解決路徑規劃問題，首先，每個智能體分享其回報，智能體i 獲得的立即回報為ri，則全局立即回報為

在每個episode 都記錄每個時刻的立即回報、選擇的動作、狀態等，每個狀態被經歷到達一定次數后，在每個episode 結束后根據每個狀態s 下的全局累積回報R 獲取全局最大累積回報Rmax，全局折扣累積回報定義如下：

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

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

通過引入全局最大累積回報頻率更新Q值，能使得智能體能最大化整體的利益，找到完成任務整體耗時最短路徑。

算法步驟如下所示：

步驟1定義所有AGV的立即回報之和為全局立即回報

步驟2初始化每個AGV的Q值、動作選擇次數、全局最大累積回報及獲取次數等變量；

步驟3根據式（4）Boltzmann與ε-greedy 結合策略進行動作選擇；

步驟4記錄每個時間步長的動作、狀態、立即回報等變量；

步驟5每種狀態被經歷一定次數后，在每個episode 結束后，根據記錄獲取每個狀態s 下的全局最大累積回報Rmax；

步驟6統計AGV 選擇動作ai時獲得歷史全局最大累積回報的次數，根據式（8）更新獲得全局最大累積回報的頻率f；

步驟7根據式（9）更新Q值函數；

步驟8若到達預先設置的學習次數，進入步驟9，否則繼續執行步驟3；

步驟9每個AGV 選擇具有最大Q值的動作。

2.4 MRF Q-learning算法重復博弈驗證

為了驗證MRF Q-learning算法的性能，我們設置了2種最優納什均衡（具有全局最大立即回報的納什均衡點）不同分布的兩人兩動作重復博弈，最優納什均衡點用括號標記，如圖3所示，由于重復博弈為只含有一個狀態，因此在重復博弈中，MRF Q-learning算法中相關的全局最大累積回報為全局最大立即回報。

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

我們設置12 組不同的初始概率及Q值（初始概率如圖4和圖5中圓點所示）每次實驗運行了20000步，最終結果如圖4和圖5所示，圖中pa0代表智能體1 選擇動作a0的概率，pb0代表智能體2 選擇動作b0概率，可以看出MRF Q-learning算法在兩種情況的重復博弈中都收斂到了最優納什均衡。

圖4 Case 1 動作選擇概率Fig.4 Probability of choosing action in Case 1

圖5 Case 2 動作選擇概率Fig.5 Probability of choosing action in Case 2

3 實驗仿真與分析

3.1 實驗設置

為了驗證MRF Q-learning算法解決路徑規劃問題的有效性，通過路徑規劃仿真進行測試，并與多智能體強化學習算法EMA Q-learning 進行對比。兩種地圖環境如圖6和圖7所示，具體任務在第一節中做出了詳細介紹，另外，我們設置當AGV 行動超過500個單位時間步長時任務結束，任務完成或結束記為一個episode，若兩個AGV 發生碰撞或出界，則它們保持上一時刻的位置，每種環境下我們都運行了20000 episodes，我們對此任務的具體的獎勵函數做如下設置：

并設置學習率α=0.4，折扣因子γ=0.9，在episode 開始時需要對動作進行大量探索，設置探索率ε為一個較大的值，然后逐漸減小，T=1 并隨著episode 不斷衰減，探索率設置如下：式中：n為當前episode 數；M為最大episode 數

3.2 實驗結果分析

我們根據程序運行結果，評價階段最終路線如圖6和圖7所示，圖中實線表示MRF Q-learning的最終路徑，虛線表示EMA Q-learning的最終路徑。

圖6 環境1 實驗結果示意圖Fig.6 Experimental results diagram in environment 1

圖7 環境2 實驗結果示意圖Fig.7 Experimental results diagram in environment 2

兩種環境中每種算法在評價階段的時間步長與最優時間步長如圖8所示。

圖8 評價階段的時間步長Fig.8 Time steps in the evaluation phase

可以看出本文的MRF Q-learning 在兩種環境中都找到了時間步長最短路徑，而EMA Q-learning雖然在第一種環境中也以最短的時間步長完成了任務，但在環境2 中兩個AGV 之間沒能相互配合，左邊的AGV1 經過了4個工作站，而AGV2 僅經過2個工作站，延長了運輸時間，且在兩處產生了出界的情形，雖然也完成了運送任務，但沒能找到時間最短路徑。

圖9為兩種算法在環境2 中學習階段的平均步長，可以看出EMA Q-learning 一開始學習速度較快，MRF Q-learning 由 于 將Boltzmann與ε-greedy結合，學習過程中會較多地探索其他動作，因此前期學習速度相對較慢。兩種算法在最后都收斂到了較短路徑，但MRF Q-learning最終收斂到了比EMA Q-learning時間步長更短的路徑。

圖9 學習階段的平均時間步長Fig.9 Average time steps in the learning phase

4 結語

本文針對工作站貨物運輸多AGV的路徑規劃問題，提出一種多智能體強化學習MRF Q-learning算法，算法采用全局最大累積回報頻率進行更新Q值公式，以獲得全局最大累積回報，每個智能體不需要其他智能體的動作，避免了聯合動作維數災，將Boltzmann 策略與ε-greedy 策略結合，更好地協調探索與利用，多AGV路徑規劃仿真結果說明，與其他多智能體強化學習算法相比，本文提出的MRF Qlearning算法能夠找到最優路徑使總運輸時間最短。