基于深度強化學習的多智能體動態尋路算法

段偉浩，趙 瑾，梁家瑞，曹 銳

(太原理工大學軟件學院，山西 晉中 030600)

1 引言

近年來，在機器人尋路領域、虛擬仿真系統以及游戲等領域，對路徑規劃的要求越來越高，普通、單一的尋路方式已經無法滿足需要。一個優秀的尋路算法不僅要保證路線最優，時間、空間消耗低，同時也需要路線更加智能、合理。不能出現路線單一、碰撞、擁堵、死鎖等現象。

目前，在尋路領域，A*算法及其改進算法，因實時性，搜索效率高等特點被廣泛應用于各個領域[1]。大量學者為了提高算法的效率、可靠性，在A*算法的基礎上衍生出其它算法，如A-STAR-Dijkstra-integrated算法[4]可以避免死鎖問題，IBAS算法[5]降低了時間復雜度以及空間復雜度。但是由于A*算法本身無法避免擁堵、碰撞、路線單一等問題，因此這些算法無法完全滿足路線智能化的需求。

而隨著深度強化學習(deep reinforcement learning)成為學者們的研究熱點。在尋路領域，也出現了大量研究成果。Martinsen A B，Lekkas A M等人使用深度強化學習解決曲線路徑跟隨問題[6]；Li M，Gao J，Zhao L等人在復雜城市交通網絡中尋找最佳解決方案[7]；Gutiérrez-Maestro E，López-Sastre R J，Maldonado-Bascón S提出了一個基于地圖的模型，將獎勵函數設計為具有碰撞感知的功能[8]。Song W，Zhou Y，Hu X等人提出了使用MRNS q-learning提高處理效率和收斂速度[9]。

然而，上述研究與應用無法完全解決多智能體動態尋路所遇到的問題。例如，多個智能體在環境未知的情況下，能否避免相互碰撞、擁堵等情況；面對突發的道路阻擋問題，是否可以有效避讓，重新規劃路線。

近年來，多智能體尋路研究取得了一定的突破，例如Okoso A，Otaki K，Nishi T針對停車場短缺的問題提出CBS-Pri和CA+-Pri兩種方法為車輛自動規劃路線[10]。Barták R，vancara J，kopková V等人使用機器人在避免碰撞的前提下抵達目標位置[11]，但仍存在問題。

在虛擬領域的多智能體尋路也存在碰撞、擁堵、路線單一等問題。以目前十分流行的3D開發引擎Unity為例，其提供的NavMesh導航系統的核心算法是基于A*算法的擴展算法，可以很好的適應三維環境尋路。但是無法檢測環境的變化，依舊存在擁堵問題、道路交通變化等問題[12]。更為關鍵的是，NavMesh系統所規劃的路線，在起點、終點以及環境不變時，多次規劃的路線完全相同，與現實不符。雖然Unity官方曾經發布動態規劃的工具，但是依舊無法靈活的根據環境自行調整路線。針對NavMesh存在的問題，很多學者也提出了優化方法。例如ANavMG[12]，HNA*[14]等，但是這些大都是對NavMesh本身進行優化，依舊無法解決上述問題。針對其它方面的改進，很多學者都提出了自己的想法。例如He Z，Shi M，Li C等人在其文中提出了在特殊游戲場景中的一些改進與應用[15]，以及動態加權BDBOP[16]等方法。

本文中利用深度強化學習的優勢，提出了一種基于全連接神經網絡的近端策略優化算法應用于多智能體動態尋路領域。為了解決訓練過程慢、效果差、稀疏獎勵等問題，本文還將采取好奇心驅動(Curiosity-driven)以及生成對抗性模仿學習(Generative Adversarial Imitation Learning)加快訓練進程。通過將訓練成功的模型與Unity提供的NavMesh系統對比，以證明本文所使用的基于全連接神經網絡的近端策略優化算法可以解決路線單一、擁堵、相互碰撞等問題，更加適合于多智能體動態尋路。

2 本文算法

2.1 近端策略優化算法

近端策略優化(Proximal Policy Optimization，PPO)算法是Schulman J，Wolski F，Dhariwal P等人提出的一種策略梯度(Policy Gradient，PG)算法的改進算法[17]，通過與環境交互進行數據抽樣。PG算法訓練的目標就是找到具有最大期望獎勵的序列[18]。采取梯度上升(gradient ascent)的方法，求出期望獎勵的梯度，并不斷更新。

但PG算法通常因為對步長的選擇很敏感而無法取得良好的效果。如果步長太小，可能導致訓練進程非常慢；如果步長過大，可能會出現信號被噪聲淹沒的情況。不僅如此，PG算法的效率往往也不會太高。

為選擇合適的步長，定義目標函數為

(1)

其中πθold(at|st)表示更新之前的動作出現的概率，πθ(at|st)表示當前動作出現的概率；上標CPI指保守策略迭代(conservative policy iteration)；At表示在t時的優勢函數(advantage function)的估計量。

式(1)中引入了概率比的概念，可以看出：如果不對概率比率進行約束，CPI的最大化會使梯度更新過大。因此，還需要對其進行約束，使概率比rt(θ)不能過大。綜上所述，PPO的目標函數為

LCLIP(θ)=Et[min(rt(θ)At，clip(rt(θ)，1-ε，1+ε)At)]

(2)

其中ε是超參數，通常為0.1或0.2。clip( )是截斷函數，作用是使第一項的值在第二項和第三項中間。也就是使概率比在1-ε和1+ε之間，不會和1相差太大。若策略更新過大，則會受到懲罰。

PPO算法約束了策略更新的大小，使其不會更新過大，有效解決了PG算法中因步長敏感而導致訓練效果不佳的問題，而且應用起來更加簡單。

2.2 基于全連接神經網絡的PPO算法

雖然上文提到的PPO算法為行為提供了一種范式，能夠讓整個系統做正確的決策，但是想要在三維場景中實現動態尋路，首先要對場景中的環境信息進行處理，使得智能體可以感知到環境。然而這些原始的、非結構化的真實世界的感知信號并不是為機器的運行而設計的。雖然對人類來講識別這些很容易，但是機器卻很難識別。而深度學習是目前處理非結構化的環境的最好工具之一，它的一個主要優勢是端到端，可以自動提取環境的特征、屬性。而且使用端到端的訓練得到的特征可能要比自己想得到的特征更加有效。

因此，本文在PPO算法的基礎上，引入全連接神經網絡。智能體通過自身搭載的射線組件探測周圍陌生的環境，將射線信息傳入全連接神經網絡，使用深度學習的方法提取特征，并傳入PPO網絡中，最終輸入五個動作的概率。其中，全連接神經網絡的隱藏層層數為2，每層神經元的個數為512。具體結構如圖1所示。

2.2.1 智能體行為

圖1 算法結構

在實驗過程中，每個智能體的行為(behavior)決定了其如何做決定。其中，行為參數是重要的屬性，包括矢量觀測空間(Vector Observation Space)、矢量動作空間(Vector Action Space)。

本文使用的矢量觀測空間包括：智能體在空間坐標系中運動時三個正方向的速度，掛載在智能體上的7條射線，以及射線需要檢測的三個對象(墻、智能體、目標)。

本文使用的矢量動作空間為一個離散的動作分段，矢量動作空間分為五個動作，分別為：前進、后退、左旋、右旋、無動作。通過變量控制移動速度以及旋轉角度。

2.2.2 獎懲函數

在本文所使用的基于全連接神經網絡的近端策略優化算法中，智能體需要不斷與環境交互，得到環境給予的獎勵或者懲罰，通過使獎勵最大化而不斷優化自己的尋路路線。

由于環境要根據智能體的行為動作給予反饋。在這里，定義了獎懲函數：

1) 每走一步則懲罰1/最大步長；

2) 若碰撞到障礙物懲罰0.01；

3) 中途若碰撞其它智能體，則懲罰0.1；

4) 到達目標之后，獎勵1。

其中，每走一步設置懲罰是為了使智能體減少動作數量，盡量尋找最優路徑。碰撞到障礙物以及其它智能體懲罰是為了避免相撞，避免擁堵。智能體到達目標位置后，則獲得完整獎勵。通過獎懲函數，智能體會減少產生懲罰的動作的概率，增加獲得獎勵的動作的概率，不斷向獲得更大的獎勵靠近。

3 實驗與結果分析

為驗證本文所提出的基于全連接神經網絡的近端策略優化算法的優越性與魯棒性，特搭建簡單、復雜兩種實驗場景進行仿真，并與Unity中NavMesh系統的算法進行對比。針對訓練過程中存在的稀疏獎勵問題，本文使用好奇心驅動及生成對抗性模仿學習完成模型訓練。

本文實驗使用CPU訓練模型。所使用的軟件、硬件信息如下所示：

引擎版本為Unity2018.4.10。CPU型號為Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz，內存為16GB。

3.1 場景搭建

在實驗中，首先使用Unity提供的工具，搭建實驗環境，簡單場景如圖2所示：

其中，圖2右側的九個正方體為智能體，左側圓球為目標位置。在場景正中設置了5個障礙物，智能體無法直接穿過。

圖2 簡單場景

簡單場景中場景規模較小，智能體距離目標初始位置較近，且障礙物數量為五個，因此，智能體可選擇的路線較少。為了證明本文算法不只適用于簡單場景，特搭建復雜場景，如圖3所示。

圖3中，左側圓球為目標點初始位置。右側設置了12個智能體，場景中間擺放了大小不等的若干障礙物。從圖3中可以看出：復雜場景相比簡單場景不僅面積更廣，智能體數量、障礙物數量更多，并且障礙物更加雜亂、無序，可選路線更多，出現碰撞、擁堵的幾率更大。為智能體訓練增加了難度。

圖3 復雜場景

3.2 仿真研究

在Unity提供的NavMesh系統中，想要使智能體到達目標位置，目標位置和環境信息都必須是已知的。然而，本文使用的基于全連接神經網絡的近端策略優化算法可以在環境、目標點未知的情況下尋找合理路線，更符合真實情況。

訓練開始前，環境對于智能體來說是未知的。智能體需要自行探測周圍環境。直至找到目標，并且到達目標位置。

3.2.1 訓練參數

實驗中，智能體按照上述方法不斷接受信息，做出反應，并大量重復訓練。當智能體的步長達到5000步還沒有找到目標位置，則重新開始。

其中，訓練時使用PPO算法所需配置的主要參數如表1所示：

表1 PPO算法中的參數信息

其中β代表熵正則化的強度，可確保代理在訓練期間正確地探索動作空間；ε的大小則影響著訓練過程中策略演化的速度；正則化參數的大小會影響訓練的穩定性；學習率代表更新步驟的強度。

3.2.2 好奇心驅動

上文中提到的獎勵通常是由環境提供，可以認為這種獎勵是外部獎勵，因為這些獎勵的規則是在訓練模型之前就確定好的。相應的，也有內部獎勵，目的是希望通過內部獎勵的方式，使智能體可以積極地探索更廣闊的空間，以便獲取更大的外部獎勵。

由于只有碰到目標物體才有獎勵，當面對地圖規模較大的場景時，在訓練的初期階段，智能體很難獲得獎勵。在這里，本文將這種情況叫做稀疏獎勵任務。

針對這種情況，本文引入好奇心驅動(Curiosity-driven)來解決這一問題[19]，在其論文中，他們建議訓練兩個獨立的神經網絡，一個正向的(forward)和一個反向的模型(inverse model)。對反向模型進行訓練，用于接收智能體當前和下一個觀察值，并用結果去預測兩個觀察值之間采取的行為。對正向模型進行訓練，對下一個觀測進行預測。預測與真實之間的差異被用在內部獎勵中，更大的差異就意味著更大的內部獎勵。

使用好奇心驅動的主要配置參數如表2所示。

表2 好奇心驅動中的參數信息

其中，強度表示好奇心驅動模塊產生的獎勵增加的幅度；gamma表示獎勵的折扣系數。

使用好奇心驅動后，訓練過程如圖4所示。

在圖2的簡單場景中使用好奇心驅動后，訓練過程中智能體累積獎勵如圖4(a)所示，好奇心驅動使用與否并不影響累積獎勵的走勢。原因是簡單場景面積較小，智能體與目標初始位置相距較近，即使在不使用好奇心驅動的情況下依舊可以順利找到目標。不屬于稀疏獎勵任務。然而，在圖3的復雜場景中使用好奇心驅動后，從圖4(b)中可以看到，若不使用好奇心驅動，在訓練了2000000步后，依舊無法找到目標。而使用好奇心驅動后，500000步時，累積獎勵變為正值，900000步時，累積獎勵達到峰值，完成訓練。

圖4 好奇心驅動對累積獎勵影響對比圖

3.2.3 模仿學習

在使用強化學習訓練的過程中，智能體通過不斷試錯的方式來探索環境，通過向獲得獎勵的方向靠近從而不斷改良路徑。然而，如果有一個簡單的演示，告訴智能體如何執行，那么將大大減少前期的探索。在此，本文引入模仿學習的概念，使用生成對抗性模仿學習(Generative Adversarial Imitation Learning，GAIL)的方法[20]。其中主要配置參數如表3所示。

表3 模仿學習中的參數信息

在使用生成對抗性模仿學習之前，需要錄制一個演示(demo)。本實驗將Unity自帶的錄制工具掛載在智能體上，手動錄制。由于演示是人為錄制，其路線可能不會非常完美。為了避免因演示不完美而造成學習效果欠佳的情況，在此，將強度(strength)的值調小，控制在0.01。具體的訓練進程如圖5所示。

在圖5(a)所示的簡單場景中，智能體在80000步后獎勵已經為正，200000步后獎勵值保持穩定，相比于不使用模仿學習，獎勵達到峰值提前了約200000步。在圖5(b)所示的復雜場景中，單單使用PPO算法在訓練了2000000步后依舊無法順利找到目標，使用模仿學習之后，400000步后累積獎勵成為正值。可以看出不論是在簡單場景還是復雜場景中，使用生成對抗性模仿學習都可以加快訓練進程。

圖5 模仿學習對累積獎勵影響對比圖

綜上所述，本文使用基于全連接神經網絡的近端策略優化算法，并且同時使用好奇心驅動、生成對抗性模仿學習，將三者結合后，智能體訓練速度更快，與其單獨使用的對比如圖6所示。

圖6(a)中表示簡單場景中的訓練過程，可以看出好奇心驅動和生成對抗性模仿學習以及PPO同時使用比其單獨使用更早達到累積獎勵的峰值。不同方法在復雜場景的區別更加明顯。如(b)中所示，三種方法同時使用比使用好奇心驅動和PPO算法兩種方法效果更好，累積獎勵變為正值提早了400000步。三種方法同時使用時，達到峰值后累積獎勵變化浮動小，更加穩定。

圖6 不同方法對累積獎勵影響對比圖

圖6中可以看出不論簡單還是復雜場景，同時使用好奇心驅動和模仿學習可以有效地將訓練步長縮短。

3.3 結果分析

3.3.1 NavMesh尋路結果

NavMesh是Unity提供的導航系統，在普通三維尋路中操作簡單，可以實現大部分簡單的尋路功能。

在圖3復雜場景中，指定目標位置后，使用NavMesh尋路具體路線如圖7所示。

圖7中線條為智能體尋路軌跡，智能體根據事先給定的目標位置，可以在避免碰撞障礙物的前提下快速抵達目標位置。

圖7 NavMesh尋路結果圖

雖然在上述實驗中，NavMesh實現了尋路功能，而且使用方便，但是從圖7中可以看出，多個智能體尋找目標的路徑單一，所有智能體尋路軌跡一模一樣。會出現擁堵情況，如圖8所示。

由于NavMesh無法檢測到路面是否擁堵，也無法避免碰撞。當多個智能體同時向一個目標點運動時，所有智能體只能同時擁擠在一處，無法根據實際情況尋找其它通路。

圖8 NavMesh擁堵情況圖

而在虛擬仿真系統以及游戲中，NPC(Non-Player Character)路線不可能完全一致。而且如果出現擁堵、碰撞等情況，既會大大降低用戶體驗，也不符合實際情況，破壞了沉浸式體驗。因此應當避免此類事件發生。

3.3.2 使用本文算法訓練結果

從NavMesh尋路結果中可以看出，NavMesh雖然在普通三維導航過程中表現良好，但是在多智能體尋路方面存在問題。從實際效果來看，NavMesh實現多智能體動態尋路時，無法判斷前方是否擁堵，無法避免碰撞，也無法根據擁堵情況和其它智能體突然出現而調整自己的路線。

使用基于全連接神經網絡的近端策略優化算法訓練完成的模型可以避免上述問題。使用好奇心驅動、模仿學習以及PPO訓練完成的模型的運動路線如圖9所示：

圖9中，多個智能體的路線并不相同，智能體會根據前方是否有其它智能體、障礙物做出判斷，避免擁堵、碰撞。當前方有智能體阻擋通道時，智能體會選擇其它路口通行，具體情況如圖10所示。

圖9 本文模型路線圖

圖8中NavMesh的尋路結果會使所有智能體擁堵在同一路口，造成擁堵和碰撞。使用本文方法訓練出的模型可以有效避免這一問題，如圖10所示，智能體會自主尋找其它通道，避免擁堵，避免碰撞。

圖10 智能體自主選擇路線示意圖

通過對比，證明了使用本文算法訓練出的模型在多智能體動態尋路上的優勢：所規劃的路線更加符合真實情況；智能體的尋路過程也更加智能，符合多元化的需求。

4 結語

本文在多智能體尋路領域，提出了使用基于全連接神經網絡的近端策略優化算法解決尋路問題。通過射線檢測周圍環境，使智能體可以根據環境的實時情況改變自己的行動軌跡，避免擁堵，尋找目標。此外，還通過使用好奇心驅動的方法增加內部獎勵，使訓練模型的速度更快，適應性更廣。實驗結果表明，使用本文方法訓練出的模型在多智能體尋路方面具有很好的適應性，可以很好的解決目前多智能體尋路時出現的無法避免擁擠，路線單一等問題。而且本文使用的方法不僅僅局限于虛擬領域，同時也可應用于機器人、無人機、汽車等現實世界的尋路。本文旨在針對多智能體動態尋路中存在的缺陷進行改進，以Unity引擎為例實現多智能體尋路，說明本文方法在多智能體尋路領域的可行性、優越性。同時也為解決其他類似問題提供了一種新的思路。

后續工作中，可對本算法中使用的全連接神經網絡進行優化，或者使用更優的神經網絡，進一步縮短訓練時間、步數，提高訓練的穩定性。