劉志飛，曹 雷，賴 俊，陳希亮，陳 英

1.陸軍工程大學 指揮控制工程學院，南京 210007

2.東部戰(zhàn)區(qū)總醫(yī)院 博士后科研工作站，南京 210007

MAPF是對不同起始位置的多個智能體到他們各自目標位置的路徑規(guī)劃問題，關鍵約束是在保證智能體之間互相不碰撞的前提下到達目標位置，并保證路徑規(guī)劃的速度和質量。MAPF在實際場景中有許多應用，如大型倉庫管理[1-2]、數(shù)字游戲[3]、火車調度[4]、城市道路網絡[5]、多機器人系統(tǒng)[6]等，更多實際應用可參考文獻[7]。

近年來，越來越多的團隊對MAPF展開研究[8-11]，MAPF取得了突破性進展。然而環(huán)境的動態(tài)變化和智能體數(shù)量的增加，對傳統(tǒng)MAPF算法是一個較大的挑戰(zhàn)?；谒阉鞯腗APF算法通過引入優(yōu)先規(guī)劃、大領域搜索和復雜的啟發(fā)式函數(shù)來優(yōu)化改進MAPF算法的性能和適用性。基于強化學習的MAPF算法在解決動態(tài)變化環(huán)境的MAPF表現(xiàn)出較大的潛力。國外關于MAPF的詳細綜述有文獻[12-13]，國內關于MAPF的詳細綜述有文獻[14]，但是這些綜述只對經典MAPF算法進行歸類整理和介紹，對近年來人工智能領域興起的MAPF的算法沒有系統(tǒng)地整理和分類。

按照MAPF規(guī)劃方式不同，MAPF算法被分為集中式規(guī)劃和分布式執(zhí)行兩種算法。集中式規(guī)劃方法由一個中央控制器來為所有智能體規(guī)劃路徑，它的前提假設是中央規(guī)劃器掌握了所有智能體的起始位置、目標位置和障礙物位置等信息。集中式規(guī)劃算法是最經典和常用的MAPF算法，在求解的速度和質量上都達到較好的效果。分布式執(zhí)行算法主要是基于強化學習的算法，前提假設是每個智能體只掌握了視野內（一定范圍內）智能體和障礙物的位置等信息，智能體根據當前策略不斷和環(huán)境進行交互，獲取環(huán)境下一到達狀態(tài)和該動作獎勵，計算并更新策略，目標是最大化累積獎勵，最后找到一個最大化累積獎勵的動作序列，完成多智能體路徑規(guī)劃任務。這類算法可以擴展到高密度和動態(tài)的部分可觀察的環(huán)境中，高效解決現(xiàn)實世界中的多智能體路徑實時再規(guī)劃問題。

MAPF的研究主要有兩大方向，一是如何改進現(xiàn)有的算法，二是在實際應用中如何處理約束。在實際應用場景中要考慮機器的速度、加速度、轉角，以及各種干擾的約束，而多智能體路徑規(guī)劃將這些設定進行抽象化，將運動控制離散為時間步，將研究的重點集中在求解速度和質量上。

本文首先對MAPF問題進行了闡述，概述了經典的集中式規(guī)劃算法，詳細分析了經典算法的原理，然后概述了深度強化學習，解析了主流的強化學習算法原理，將MAPF問題描述為強化學習問題，介紹了基于強化學習的MAPF算法研究進展。在此基礎上，指出現(xiàn)有算法面臨的挑戰(zhàn)，指出了下一步要解決的問題和研究方向。

1 經典多智能體路徑規(guī)劃問題

關于MAPF問題有許多不同的定義和假設，以經典的MAPF問題為例，對MAPF問題進行闡述。

1.1 定義

首先描述經典的MAPF問題。k個智能體的經典MAPF問題[12]被定義為一個元組(G,s,t)。其中G=(V,E)是一個無向圖，無向圖中的節(jié)點v∈V是智能體可以占據的位置，邊(n,n′)∈E表示智能體從節(jié)點n移動到n′的連線。k代表問題中智能體的數(shù)量，即智能體{a1,a2,…,ak}，s是初始位置的集合，每個智能體都有一個起始位置si∈s，t是目標位置的集合，每個智能體都有一個和目標位置ti∈t。

在經典MAPF問題中，時間被離散為時間步長。在每個時間步長中，每個智能體可以執(zhí)行一個動作，一般有五種類型的動作：向上、向下、向左、向右和等待。

一個單智能體的路徑規(guī)劃是從起始位置到目標位置一系列動作的集合π=(a1,a2,…,an)，k個智能體的路徑規(guī)劃問題就是k條路徑的集合Π={π1,π2,…,πk}。其中第i個智能體對應路徑πi。

1.2 沖突類型

MAPF的首要目標是找到所有智能體的路徑規(guī)劃，且不存在沖突，為此引入了沖突的概念，常見沖突類型有4種，即圖1所示[12]。

圖1 沖突類型Fig.1 Illustration of conflicts

1.3 目標函數(shù)

MAPF問題有很多解決方案，在許多實際應用中，需要一個有效的目標函數(shù)來優(yōu)化MAPF問題。用來評估MAPF解決方案的最常見的三個目標函數(shù)是：

其中，目標函數(shù)（1）表示最晚到達目標位置的智能體所花費的時間，目標函數(shù)（2）表示所有智能體到達目標位置的時間總和，目標函數(shù)（3）表示所有智能體到達目標位置的路徑長度總和。

2 集中式規(guī)劃算法

MAPF集中式規(guī)劃算法的前提假設是中央規(guī)劃器掌握了全局信息，即所有智能體的起始位置、目標位置和障礙物位置信息等。MAPF集中式規(guī)劃算法可分為基于A*搜索、基于沖突搜索算法、代價增長樹搜索算法和基于規(guī)約四種算法。集中式規(guī)劃算法優(yōu)缺點分析如表1所列。

表1 集中式規(guī)劃算法對比Table 1 Comparison of centralized planning algorithms

2.1 基于A*搜索算法

2.1.1A*搜索算法

A*搜索算法[15]是啟發(fā)式搜索算法的代表，它是Dijikstra算法的擴展形式。A*算法通常用來解決最短路徑問題，相關工作總結于表2。

表2 基于A*搜索算法Table 2 Algorithms based on A*search

為了完整起見，先簡要介紹背景。A*在小規(guī)模智能體環(huán)境中是最佳搜索算法。它維護兩個頂點列表：開放列表和關閉列表。最初將開始節(jié)點放入開放列表中，在每次迭代中，在開放列表中搜索相鄰節(jié)點，并把起始節(jié)點放入關閉列表中。對于每個新生成的開放列表中的節(jié)點，A*算法計算以下幾個值：

（1）g(n)是從源節(jié)點到n節(jié)點的最短路徑代價值。

（2）parent(n)是該節(jié)點的前一個節(jié)點。

（3）h(n)是n節(jié)點到目標節(jié)點的啟發(fā)式路徑代價估計值。

假設h*(n)是n節(jié)點到目標節(jié)點的完美啟發(fā)式估計，如果已知每個節(jié)點h*(n)，就可以選擇從源節(jié)點到目標節(jié)點的最短路徑。A*算法選擇擴展開放列表里具有最小g(n)+h(n)節(jié)點。

2.1.2 用A*搜索解決MAPF的挑戰(zhàn)

A*搜索在MAPF中的狀態(tài)一般被稱為k-agent狀態(tài)空間，其狀態(tài)數(shù)等于將v個智能體分別放置在v個不同節(jié)點狀態(tài)數(shù)，一種放置方法對應于一種狀態(tài)。一種最簡單的方法將A*搜索啟發(fā)式函數(shù)應用到MAPF中，是全局啟發(fā)式函數(shù)等于所有智能體各自啟發(fā)式函數(shù)之和。在k-agent搜索空間，最壞的情況下，搜索空間大小為|V|k，分支因子為(|E||V|)k，以一個20個智能體的200×200單元柵格四聯(lián)通MAPF為例，搜索空間大小為40 00020，分支因子為420。對于A*算法來說，分支因子尤其是問題，因為A*必須沿著最優(yōu)路徑擴展所有的節(jié)點，因此A*算法在解決大規(guī)模智能體的MAPF問題時效率和質量都不高。

2.1.3A*搜索的擴展

Standley[16]對A*提出了兩個非常有效的擴展來解決MAPF問題：因子分解和獨立檢測。

因子分解：第一個擴展稱為算子分解（operator decomposition，OD）。OD設計用于改進k-agent搜索空間的分支因子指數(shù)增長的缺陷。在OD中，智能體按照任意的順序進行排序。當展開源頂點(s(1),s(2),…,s(k))時，只考慮一個智能體的行為，這將生成一組頂點，這些頂點表示時間步1中第一個智能體的可能位置，以及時間步0中所有其他智能體所占據的位置。這些頂點被添加到open列表中，當展開其中一個頂點時，只考慮第二個智能體的動作，生成一組新的頂點。這些頂點表示時間步1中第一個和第二個智能體的可能位置，其他智能體處在時間步0的位置。搜索工作繼續(xù)以這種方式進行，直到搜索樹上第k層狀態(tài)節(jié)點能夠表示所有智能體在時間步1的所有可能位置分布。第k層狀態(tài)節(jié)點表示同一時間步長的所有智能體位置的節(jié)點稱為full節(jié)點，而其他所有頂點稱為中間節(jié)點。繼續(xù)搜索，直到到達表示目標(t(1),t(2),…,t(k))的full節(jié)點。有OD的A*與無OD的A*相比，其明顯優(yōu)勢在于分支因子。OD大幅縮減了A*搜索的分支因子，OD A*引入了大量的中間狀態(tài)節(jié)點，使得A*搜索的深度加深了k倍。在MAPF中，由于加入啟發(fā)式函數(shù)對中間狀態(tài)節(jié)點進行剪枝，因此OD的引入是有益的。

獨立檢測：Standley提出的第二個A*擴展稱為獨立檢測（independence detection，ID）。ID試圖將帶有kagent的MAPF問題分解為含有更少智能體的更小的MAPF問題。它的工作原理如下：首先，每個智能體為自己找到一個最優(yōu)路徑方案，同時忽略所有其他智能體，然后開始獨立檢測，如果一對智能體的計劃之間存在沖突，這些智能體就合并為一個單一的元智能體。然后，用A*+OD求出其中兩個智能體的最優(yōu)解，忽略其他所有智能體。這個過程以迭代的方式繼續(xù)，在每次迭代中檢測到單個沖突，合并沖突（元）智能體，然后用A*+OD進行最優(yōu)解決。當智能體的計劃之間沒有沖突時，進程停止。在最壞的情況下，ID最終會將所有智能體合并到一個元智能體，并解決生成智能體的MAPF問題。ID是一個非常通用的框架的MAPF求解器，ID能夠提高多數(shù)MAPF問題求解的效率。

M*算法[17]也像A*一樣搜索k-agent搜索空間。為了改進分支因子，M*動態(tài)地改變搜索空間的分支因子。最初，每當擴展一個節(jié)點時，它只生成一個節(jié)點，該節(jié)點對應于所有單個智能體最優(yōu)路徑，這將在k個智能體搜索空間中生成k條路徑。由于智能體沿著各自的最優(yōu)路徑移動，可能會生成一個節(jié)點來表示一對智能體i和j之間的沖突。如果發(fā)生這種情況，智能體i和j將會加入到沖突集合中，然后重新展開搜索。在重啟搜索時，智能體i和j會執(zhí)行樸素的A*搜索。一般情況下，M*中的一個節(jié)點存儲沖突集，沖突集是一組智能體，它將為這些智能體生成所有動作組合。對于不在沖突集中的智能體，M*只考慮單個智能體其最優(yōu)路徑上的動作。遞歸M*(rM*)是M*的一個顯著改進版本。rM*試圖將沖突的智能體分割為沒有沖突的智能體集，遞歸的解決生成的子問題。M*與OD相似，它限制了某些節(jié)點的分支因子。rM*與ID也有一些相似之處，因為它試圖識別哪些智能體可以單獨求解。然而，M*、OD和ID可以一起使用，rM*可以通過ID來尋找沖突元智能體的最優(yōu)解，rM*可以用帶有OD的A*來搜索k-agent搜索空間，而不是簡單的A*，后者被稱為OD rM*。

現(xiàn)有基于搜索的方法，大部分工作都集中在如何處理智能體之間的沖突，文獻[18]采取不同的方法，通過改進每個智能體的個人計劃來減少沖突的數(shù)量，從而提高整體搜索效率。它在規(guī)劃單個智能體同時關注地圖結構和可能發(fā)生沖突的其他智能體，然后通過將這種基于學習的單智能體規(guī)劃器與M*集成，開發(fā)了一種稱為LM*的新型多智能體規(guī)劃器。LM*需要解決的沖突更少，運行速度更快，成功率更高。文獻[19]針對多目標最短路徑問題，開發(fā)了MOA*算法，該方法在搜索過程的每個節(jié)點處維護一個邊界集，以跟蹤到達該節(jié)點的非支配、部分路徑。通過在MOA*搜索框架內逐步構建平衡二叉搜索樹，有效維護多個目標的邊界，該方法比現(xiàn)有技術運行速度快一個數(shù)量級。文獻[20]針對目前幾乎所有基于A*方法都假設每個智能體同時執(zhí)行一個動作的問題，提出一種松散同步搜索的方法（LSS），LSS擴展可基于A*的MAPF以處理異步操作，其中智能體不一定同時啟動和停止。LSS是完整的，并且如果存在最優(yōu)解，則可以找到最優(yōu)解。EPEA*（enhanced partial expansion）[21-22]對分支因子指數(shù)增長進行改進，與A*不同之處在于EPEA*在擴展一個狀態(tài)節(jié)點時只將一部分的后繼狀態(tài)節(jié)點加入open列表中。

2.2 基于沖突搜索算法

基于沖突搜索算法是目前最常用的算法，目前求解MAPF速度和質量最好的算法大都是在基于沖突搜索算法上進行改進和優(yōu)化，相關工作總結于表3。

表3 基于沖突搜索算法Table 3 Conflict based search algorithms

2.2.1 經典基于沖突搜索算法

基于沖突搜索方法（CBS）[23]是解決MAPF最熱門的方法之一，它包含高層搜索和低層搜索，它構建一棵二叉搜索樹查找解。在根節(jié)點為所有智能體單獨規(guī)劃路徑，然后通過添加限制的方式消解沖突，每個節(jié)點規(guī)劃路徑考慮節(jié)點被添加的限制并忽略其他智能體。它的特點在于求解速度快，相比其他方法能夠求解更大規(guī)模的問題，缺點是實現(xiàn)難度較高。原有的用A*整體規(guī)劃求解MAPF問題需要在擴展同時考慮各個智能體之間的沖突，生成大量無意義的節(jié)點，影響搜索的效率。CBS通過添加限制解決沖突，求解速度更快。

2.2.2 增強的基于沖突搜索算法

增強的基于沖突搜索算法（ICBS）[24]在CBS的基礎上總結和提出了優(yōu)化為Meta-Agent和規(guī)避沖突，此外ICBS進一步提出合并后重新搜索和有限消解關鍵沖突兩種優(yōu)化方法。Meta-Agent主要思想是將沖突的兩個智能體合并成一個Meta-Agent來重新規(guī)劃以消解沖突，代替了通過分裂操作為兩個智能體添加新約束的方法。合并后的Meta-Agent被當作一個復合的智能體，由于其他智能體都沒有發(fā)生變化，只需要為新生成的Meta-Agent重新規(guī)劃路徑。ICBS進一步減少了現(xiàn)有基于CBS方法的運行時間。

2.2.3 基于沖突搜索算法的變體

CBS是優(yōu)化多智能體路徑規(guī)劃的有效方法。然而，在具有許多智能體的高度競爭圖中，CBS的性能會迅速下降。發(fā)生這種情況的原因之一是CBS沒有檢測到獨立的子問題。文獻[25]提出惰性CBS（Lazy-CBS），這是一種新的MAPF方法，它使用惰性構造的約束規(guī)劃模型替換了CBS的高級求解器。它使用核心引導的深度優(yōu)先搜索來探索沖突空間，并沿著每個分支檢測可重復使用的分支，這有助于快速確定可行的解決方案。Lazy-CBS可以顯著改進成本度量下的最優(yōu)MAPF問題。文獻[26]引入了一種擴展的沖突分類，首先解決子節(jié)點成本值大于待拆分節(jié)點成本值的沖突，并提出一種識別這種沖突的方法，通過使用解決某些沖突的成本的信息來增強所有已知的CBS啟發(fā)式算法，而這些信息值需要很小的計算開銷，擴展的沖突分類和改進的啟發(fā)式方法都是CBS更加高效。HCBS[27]為高層搜索增加了一個啟發(fā)式函數(shù)，以更好地對約束樹進行剪枝。增強型基于沖突搜索（ECBS）[28]是近似最優(yōu)MAPF算法，它在低層搜索和高層搜索中引入次優(yōu)性，在CBS的低層搜索中可以是任何最優(yōu)路徑算法，比如A*。文獻[29]提出靈活的ECBS（FECBS），通過在低層搜索中使用更寬松的次優(yōu)邊界，進一步減少需要在高層解決的沖突數(shù)量，同時仍提供有界次優(yōu)解決方案。FECBS不要求每條路徑的成本是有界次優(yōu)的，而是要求路徑的總成本是有界次優(yōu)的，因此可以根據需要在不同智能體之間自由分配成本。FECBS可以在5 min內解決比ECBS更多的MAPF實例。ECBS算法將解決方案質量折中到一個常數(shù)因子，以獲得顯著的運行時間的改進，但是ECBS對所有的智能體都使用固定的全局次優(yōu)界限，而不管他們的偏好如何。實際上，隨著智能體的增加，運行時性能會下降。文獻[30]針對此問題提出了一種自適應智能體特定的次優(yōu)邊界方法（ASB-ECBS），可以靜態(tài)或者動態(tài)執(zhí)行，可以根據單個智能體的要求分配次優(yōu)界限。ASB-ECBS顯著改善了運行時間，同時減少了搜索空間。EECBS[31]算法對ECBS進行了改進，它包含了顯示估計搜索和三個啟發(fā)式函數(shù)。第一個啟發(fā)式函數(shù)是A*中的h(n)，第二個啟發(fā)式函數(shù)計算沖突的個數(shù)，第三個是啟發(fā)式函數(shù)是在線學習方法，在搜索過程中觀察前面的h(n)和沖突個數(shù)的誤差，然后反饋矯正。此外EECBS還增加了近年來一些新的CBS改進技術。通過實驗對比分析，CBS能解決智能體的個數(shù)小于200，而EECBS可以達到1 000個以上，而且解的質量與最優(yōu)解只有2%的誤差。文獻[32]提出一種用于選擇沖突選擇的機器學習框架：ML-guide CBS。該方法由一個用于沖突選擇的預言機做出決策，并學習一種由線性排序函數(shù)表示的沖突選擇策略，該函數(shù)可以準確快速地模仿預言機的決策。ML-guide CBS算法顯著提高了CBS求解器的成功率、搜索樹大小和運行時間。文獻[33]提出了一種非連續(xù)時間、非網格域和非離散時間步長假設下的基于沖

突的搜索算法（CCBS），CCBS是一種可以處理非單元動作持續(xù)時間、連續(xù)時間、非網格域和具有集合形狀的智能體的MAPF算法。由于CCBS考慮了智能體的幾何形狀和連續(xù)時間，它可能比基于網格的解決方案慢，但求解結果仍然是最優(yōu)和完整的。基于沖突的搜索CBS變體通常使用某種形式的A*搜索類計算MAPF解決方案。然而，這種方法經常受到嚴格的時間限制，以避免耗盡可用內存。文獻[34]提出一種CBS的迭代延伸變體（IDCBS），它可以在不耗盡內存且沒有嚴格時間限制情況下執(zhí)行，由于在處理CBS節(jié)點時使用了增量方法，IDCBS比CBS要快得多。

2.3 代價增長樹搜索算法

代價增長樹搜索（increasing cost tree search，ICTS）[35]算法將MAPF問題分解為兩個問題：找到每個智能體的代價和找到這些代價的有效解決問題方案，這部分工作總結于表4。

表4 代價增長樹搜索算法Table 4 Algorithms of increasing cost tree search

ICTS不直接搜索k-agent搜索空間。它將兩個搜索過程結合在一起：高層搜索和低層搜索。高層搜索的目的是找出所有智能體的單個最優(yōu)路大小，低層搜索目的是對高層搜索的狀態(tài)節(jié)點(c1,c2,…,ck)進行驗證是否存在一組最優(yōu)解。低層搜索首先計算每個智能體從起始位置到目標位置花費代價ci，使用MDD存儲。所有MDD的交叉乘積結果就是所有滿足狀態(tài)節(jié)點(c1,c2,…,ck)的路徑集合。MDD交叉乘積是k-agent搜索空間的一個子空間。ICTS搜索MDD交叉乘積以獲得有效的解決方案。由于搜索方法是解決滿足問題而不是優(yōu)化問題，所以通常采用簡單的深度優(yōu)先搜索來實現(xiàn)。擴展的增加成本搜索（E-ICTS）[36]是ICTS的擴展。E-ICTS是一種兩級算法，它在高層搜索遞增成本樹，在低層搜索k個MDD的所有時間重疊的動作，以找到一組k個不沖突路徑。E-ICTS在具有離散運動模型中可以在短時間內實現(xiàn)比ICTS更高質量的次優(yōu)解。ICTS在處理連續(xù)時間域內的對稱沖突仍然難以解決，文獻[37]引入了一種新的算法，即基于沖突的增加成本樹搜索（CBICS），該算法結合了CBS和ICTS的優(yōu)勢，在單位時間和連續(xù)時間域中，CBICS通常比CBS和ICTS更快地找到解決方案。

2.4 基于規(guī)約算法

規(guī)約方法是從理論到實踐的各種計算機領域中使用的最突出的技術之一。MAPF問題是NP-hard的問題[38]，可以將MAPF問題規(guī)約為其他已解決的標準問題，如布爾可滿足性（satisfaction fiability，SAT）、約束滿足問題（constraint satisfaction problems，CSP）、約束優(yōu)化問題（constraint optimization problems，COP）、答案集編程（answer set programming，ASP）。許多MAPF問題可建模為CSP或者COP。使用規(guī)約算法的主要好處是當前通用的規(guī)約求解器非常高效，并且變得越來越好。特別是現(xiàn)在的SAT求解器非常高效，能處理上萬個變量。Surynek[39]探索了使用五種不同的SAT建模MAPF的方法，展示了不同的建模方法對SAT求解器運行時間的影響。文獻[40]使用一種更高級的規(guī)約方法Picat[41]建模了集中MAPF的變體。一種用Picat編寫的規(guī)約方法可以用SAT自動求解。文獻[42]將MAPF問題規(guī)約為ASP問題，文獻[43]將MAPF問題規(guī)約為SAT module theory（SMT），文獻[44]將MAPF問題規(guī)約為多物品網絡流問題。

2.5 其他集中式規(guī)劃算法

其他集中式規(guī)劃算法主要是兩種或者兩種以上算法的相融合算法。特別是將基于搜索的算法和機器學習相結合，使算法在性能上有很大提升，相關工作總結于表5。

表5 其他集中式規(guī)劃算法Table 5 Other centralized planning algorithms

文獻[45]首先快速找到初始解決方案，然后通過大領域搜索（LNS）反復重新規(guī)劃智能體子集。它通過隨機破壞啟發(fā)式生成重新規(guī)劃的智能體子集，但并非所有的智能體子集都能顯著提高解決方案的質量。文獻[46]在MAPF-LNS算法基礎加以改進，使用機器學習（ML）來學習如何從子集集合中選擇智能體子集，以便找到更高質量的解決方案。MAPF-ML-LNS在改進解決方案的速度和質量方面均優(yōu)于MAPF-LNS。文獻[47]提出一種基于大領域搜索的新算法（MAPF-LNS2），從一組包含沖突的路徑開始，MAPF-LNS2重復選擇一個沖突智能體子集并重新規(guī)劃他們的路徑以減少沖突的數(shù)量，直到路徑變得無沖突。MAPF-LNS2與最先進的隨機重啟的優(yōu)先規(guī)劃和EECBS相比，運行速度明顯較快。MAPF-LNS2在大多數(shù)MAPF實例中，運行時間限制為5 min。文獻[48]提出協(xié)作時間路線圖方法（CTRMs），CTRMs使每個智能體能夠以考慮其他智能體的行為來避免智能體之間沖突的方式關注潛在解決方案路徑周圍的重要位置。CTRMs開發(fā)了一種機器學習的方法，從相關問題實例和解決方案中學習生成模型，然后使用學習到的模型對CTRMs的頂點進行采樣，以獲得新的問題實例。文獻[49]提出一種交通流預測算法來估計未來視野中的機器人密度分布，并在扇區(qū)級路徑規(guī)劃中考慮這些信息，通過平衡整個環(huán)境的交通流量來減少機器人擁堵并提高大型倉庫工作效率。以最優(yōu)方式求解MAPF是NP-Hard問題，因此現(xiàn)有最優(yōu)和有界次優(yōu)MAPF求解器通常無法擴展到大型MAPF實例。文獻[50]提出一種新穎的MAPF求解器，分層多智能體路徑規(guī)劃器（HMAPP），它通過將環(huán)境劃分為多個區(qū)域并將MAPF實例分解為每個區(qū)域的較小MAPF子實例來創(chuàng)建空間層次結構。對每個子實例，它使用有界次優(yōu)MAPF求解器對其進行求解。HMAPP能夠在各種地圖上獲得更好的解決方案。MAPF經典方法假設智能體在執(zhí)行過程中盲目遵循無碰撞路徑，然而在實際執(zhí)行過程中可能會發(fā)生沖突情況，文獻[51]提出一種魯棒性概念，它使智能體在延遲的情況下轉移到潛在路徑。這種方法與之前的K步延遲計劃相比，到達目標的概率要高很多。文獻[52]提出基于協(xié)作沖突搜索的合作MAPF算法（Co-CBS），智能體不干擾彼此，而且還幫助彼此實現(xiàn)目標。這個擴展自然地模擬了許多現(xiàn)實世界需要協(xié)作才能完成任務的應用程序。文獻[53]針對大型倉庫分揀機器人控制問題，提出一種擴展的帶有回溯優(yōu)先級集成方法（PIBT），使其更適用于一般環(huán)境。它提出的方法使倉庫分揀任務能夠在具有一些樹形路徑的環(huán)境中執(zhí)行而不會出現(xiàn)死鎖，同時保留PIBT的特性，它通過允許智能體具有臨時優(yōu)先級并限制智能體在樹形路徑的移動來做到這一點。經典MAPF問題假設所有智能體都是同質的，具有固定的大小和行為。然而，實際應用中有些智能體是異構的。文獻[54]將MAPF推廣到異構智能體（G-MAPF）的情況，提出G-CBS算法，它不會導致顯著的額外開銷。

3 分布式執(zhí)行算法

近年來，經典的MAPF算法已經能夠解決大部分路徑規(guī)劃問題。然而這些問題的前提假設都是中央規(guī)劃器掌握完整的地圖信息和所有智能體的位置等信息，并且集中式方法需要收集地圖信息和所有智能體的信息以規(guī)劃最優(yōu)路徑，導致消耗大量的計算資源。隨著技術的發(fā)展，去中心化的方法越來越流行，智能體在與環(huán)境交互過程中，通過和一定距離范圍內的其他智能體通信來規(guī)劃路徑，泛化性較好，可以擴展到大規(guī)模智能體的環(huán)境。本章先對強化學習、深度學習和深度強化學習進行概述，然后介紹深度強化學習用于解決多智能體路徑規(guī)劃的算法，分析現(xiàn)有算法的優(yōu)缺點，并提出了現(xiàn)有算法面臨的挑戰(zhàn)。

3.1 深度強化學習背景

近年來，深度強化學習（deep reinforcement learning，DRL）[55-56]取得顯著成績，這導致了DRL的應用場景和方法的數(shù)量激增。最近的研究也從單智能體到多智能體系統(tǒng)。盡管在復雜的多智能體領域面臨許多挑戰(zhàn)，但在一些復雜的游戲領域取得了許多成功，如圍棋[57-58]、撲克[59-60]、DOTA2[61]和星際爭霸（StarCraft）[62]。這些領域的成功都依賴于兩個技術的組合：強化學習（reinforcement learning，RL）和深度學習（deep learning，DL）。

3.1.1 強化學習

RL是一項通過不斷試錯來學習的技術。智能體通過一系列的步數(shù)與環(huán)境進行交互，在每一步，智能體基于當前的策略來獲取環(huán)境狀態(tài)，到達下一個狀態(tài)并獲得該動作獎勵，智能體的目標是更新自己的策略以最大化累計獎勵。如果環(huán)境滿足馬爾可夫性質，如公式（4）所示，RL可以建模為一個馬爾可夫決策過程（Markov decision process，MDP）[63]。

其中st表示時間步t時的狀態(tài)。

MDP可以用公式（5）來表示：

其中，S表示狀態(tài)空間(st∈S),A表示動作空間，at∈A,R表示獎勵空間(rt∈R),ρ表示狀態(tài)轉移矩陣(ρSS′=P[st+1=s′|st=s])，γ表示折扣因子，它用于表示及時獎勵對未來獎勵的影響程度。在RL中，有兩個重要的概念：狀態(tài)價值函數(shù)和動作價值函數(shù)。

RL可分為以下基本方法：

（1）基于值方法（value-based methods）。基于值的方法依賴于智能體所處的狀態(tài)值，最優(yōu)策略是最大值函數(shù)。兩種最主要的方法是值迭代和Q-learning[64]，狀態(tài)轉移概率存在時使用值迭代方法，狀態(tài)轉移概率未知時使用Q-learning方法。Q-learning通過貝爾曼方程[65]來更新動作值。

（2）基于策略方法（policy-based methods）[66]?；诓呗缘姆椒ú皇怯嬎阒岛瘮?shù)，而是直接搜索最優(yōu)策略。最常用的基于策略的方法REINFORCE[67]，該方法的模型是關于θ(πθ(a|s))的函數(shù)，通過梯度上升來更新參數(shù)時收益最大化。

（3）演員評論家方法（actor-critic methods，AC）[68]。AC是一種混合方法，它學習策略和值函數(shù)。該算法由兩個共享參數(shù)的模型組成：

Critic：更新值函數(shù)的參數(shù)（狀態(tài)值函數(shù)或者動作值函數(shù)）。

Actor：更新策略參數(shù)。

該方法依賴于時序差分法（temporal difference，TD）：計算動作的值的TD誤差來更新動作值參數(shù)，圖2表示了AC方法。

圖2 AC強化學習智能體Fig.2 Actor-Critic reinforcement larning agent

3.1.2 深度學習

深度學習是機器學習的一個領域，它使用含有幾個隱藏層的神經網絡（neural networks）從數(shù)據中提取有用的模型。它在人臉識別、圖像識別、語言識別等領域都取得不錯的效果。深度學習中最重要三種網絡模型是卷積神經網絡（convolutional neural network，CNN）、循環(huán)神經網絡（recurrent neural network，RNN）和生成對抗網絡（generative adversarial network，GAN）。

CNN在計算機視覺和圖像處理等領域取得不錯效果。它利用“卷積”的圖像相關特征自動從數(shù)據中學習。通過增加CNN網絡的寬帶和深度可以使性能得到提高，但同時也會導致梯度消失等問題。

RNN在自然語言處理和時間序列方面表現(xiàn)較好的性能。它的主要優(yōu)點是可以處理任意長度的輸入，計算過程中考慮歷史信息。雖然RNN是一個非常有用的工具但是也有缺點，計算速度慢并且難以從較早的過去獲取信息。

GAN主要由兩部分組成：一個生成模型G和一個判別模型D。這兩個模型互相博弈學習產生較好的輸出。判別模型估計來自輸入數(shù)據樣本的概率，生成模型生成一個接近真實樣本的新樣本。

3.1.3 深度強化學習

深度強化學習利用神經網絡來估計值函數(shù)和策略。下面介紹幾種主要單智能體強化學習算法。

基于值函數(shù)：deep Q-network（DQN）[69-70]使用神經網絡來估計動作值函數(shù)，用神經網絡代替Q-learning的Q表格。DQN采用經驗回放（experience replay buffer）來降低數(shù)據之間的關聯(lián)性，將與環(huán)境互動的數(shù)據D=e1,e2,…,eT,其中et=(st,at,rt,st+1),t∈[1,T]，存放在經驗回放池中。在每次迭代中，使用基于TD的損失函數(shù)見公式（6）所示：

基于策略函數(shù)：深度確定策略梯度（deep deterministic policy gradient，DDPG）[76]結合了DQN和AC方法來學習策DDPG包含四個神經網絡：當前Actor網絡、目標Actor網絡、當前Critic網絡、目標Actor網絡。

DDPG的目標是維護將狀態(tài)映射到動作的Actor函數(shù)，并學習估計狀態(tài)動作值的Critic函數(shù)。

基于策略的經典深度強化學習算法還有近端策略優(yōu)化算法PPO[77]、置信域策略優(yōu)化算法TRPO[78]、分布式策略梯度PPO算法[79]、異步優(yōu)勢算法（A3C）[80]、雙延遲確定性策略梯度算法（TD3）[81]。

單智能體強化學習主要算法在表6總結。

表6 單智能體強化學習算法對比Table 6 Comparison of single agent reinforcement learning algorithms

3.1.4 多智能體深度強化學習

RL已經應用到許多具有挑戰(zhàn)性的問題，如Alpha Go和Alpha Zero。然而實際應用場景中往往需要多個智能體之間的通信協(xié)調與合作。目前多智能體深度強化學習（multi-agent DRL，MADRL）正成為研究的熱點。

分布式部分可觀測馬爾可夫決策過程：一個完全合作的多智能體強化學習任務可以用分布式部分可觀測馬爾可夫決策過程（Dec-POMDP）[82]來描述。Dec-POMDP可由元組G=(n,S,U,P,r,Z,O,γ)表示。其中n表示智能體的數(shù)量；s∈S表示狀態(tài)；ua∈U表示智能體的動作；ua∈U≡Un表示智能體的聯(lián)合動作集合，P(s′|s,u):S×U×S→[0,1]表示狀態(tài)s下采取聯(lián)合動作u轉移到s′狀態(tài)轉移概率；r(s,u):S×U→R表示獎勵函數(shù)；z∈Z表示每個智能體的觀察值由O(s,a):S×A→Z來描述；γ∈(0,1)表示折扣因子。

基于值函數(shù)分解的算法：將聯(lián)合值函數(shù)分解為每個智能體的值函數(shù)。代表算法有VDN[83]、QMIX[84]、QTRAN[85]、NDQ[86]、CollaQ[87]、IQL[88]、QPLEX[89]、QPD[90]。

基于策略函數(shù)的算法：每個智能體通過自身觀察的歷史信息學習策略，大多采用集中式訓練分布式執(zhí)行方法，代表算法有MADDPG[91]、COMA[92]、IPPO[93]、MAPPO[94]、MAAC[95]。MADRL主要算法在表7總結。

表7 多智能體深度強化學習算法對比Table 7 Comparison ofmulti-agent deep reinforcement learningalgorithms

3.2 強化學習在多智能體路徑規(guī)劃問題的適用性

探索RL在MAPF上的應用，需要對MAPF問題進行建模，并且該建模環(huán)境允許使用RL方法和傳統(tǒng)集中式規(guī)劃算法，以進行算法對比分析。

3.2.1 環(huán)境

MAPF所需環(huán)境需要滿足適合訓練RL智能體和集中式規(guī)劃算法，以便對各種算法性能進行對比。2020年的NeurlPS Flatland挑戰(zhàn)賽中使用的火車調度模擬環(huán)境[96]就是一種用于MAPF的簡單環(huán)境，通常用于測試和比較各種MAPF算法。環(huán)境可視化如圖3所示。

圖3 7輛火車到達不同火車站的簡單環(huán)境Fig.3 Simple environment in which 7 trains arrive at different railway stations

在鐵軌上的7輛不同火車從不同位置出發(fā)，去往不同的火車站。每個火車相當于一個智能體，火車站相當于目標位置。

狀態(tài)空間：每個智能體有一個位置(x,y)，其中x∈[0,w-1]，y∈[0,h-1]，w是網格環(huán)境的寬度，h是網格環(huán)境的高度。每個智能體的位置和目的地以及路徑組成狀態(tài)空間。

動作空間：每個智能體的運動時間離散為每個時間步長，智能體在任一時間步長可采取行動a,a∈[0,3]，分別表示智能體等待、向上、向下和向前運動。

獎勵函數(shù)：每個智能體接受局部獎勵和全局獎勵。在每個時間步長內，如果智能體沿著鐵軌移動或者停止，獎勵為rl，如果智能體達到目的地，則獎勵為rm，如果智能體之間發(fā)生碰撞，則獎勵為rn，如果所有智能體都到達目標位置，則全局獎勵為ro，最后總的獎勵ri(t)為四者之和：Ri(t)=rl(t)+rm(t)+rn(t)+ro(t)。

目標函數(shù)：強化學習的目標就是每個智能體通過與環(huán)境互動采取動作來達到未來獎勵之和最大化。從時間步長t+1到時間步T的回報定義為Gt，用公式（7）表示：

3.2.2 多智能體深度強化學習算法選擇與實現(xiàn)

MADRL在MAPF上的算法實現(xiàn)主要有三種方式：（1）獨立學習，每個智能體把其他智能體當做環(huán)境的一部分獨立的使用單智能體RL算法來與環(huán)境互動執(zhí)行動作，以使獎勵最大化；（2）集中式訓練分散式執(zhí)行，這種方法有效解決信用分配問題，并且使智能體有效學會協(xié)作；（3）差異化通信，這種方法區(qū)別于完全分散式執(zhí)行算法的隱式協(xié)調，可以直接通信，從而可以共享智能體之間的行動意圖。

3.3 基于強化學習的多智能體路徑規(guī)劃方法研究進展

使用RL方法解決MAPF問題面臨的許多挑戰(zhàn)，例如環(huán)境獎勵稀疏、環(huán)境動態(tài)復雜等。任何一種強化學習算法直接應用于MAPF問題都會出現(xiàn)學習速度慢和學習質量不高的問題。針對以上問題，研究人員采用了各種組合技術對基于強化學習的MAPF方法進行改進，使得強化學習的MAPF方法能夠擴展到上千個智能體的環(huán)境，并且求解的質量和效率得到大大的提高。按照改進技術的特點，大致將基于RL的MAPF方法分為專家演示型、改進通信性和任務分解型三類，不同類型算法的優(yōu)缺點總結于表8。

表8 分布式執(zhí)行算法對比Table 8 Comparison of distributed execution algorithms

3.3.1 專家演示型

專家演示型方法主要采用強化學習和模仿學習（imitation learning，IL）和相結合的方法，這部分工作總結于表9。

表9 專家演示型算法Table 9 Expert demonstration algorithms

PRIMAL（pathfinding via reinforcement and imitation multi-agent learning）[97]，一種新的MAPF框架，它的算法原理如圖4所示。在每一回合開始，隨機選擇是基于RL或者基于IL進行學習，在基于RL學習中，在每個時間步長，每個智能體從環(huán)境中獲取其觀察值和獎勵值并輸入到神經網絡，神經網絡輸出一個動作。不同智能體的動作按照隨機順序依次執(zhí)行。基于IL的方法中，由經典的MAPF規(guī)劃器作為專家經驗，對所有智能體動作進行協(xié)調規(guī)劃。它結合了RL和IL去學習完全去中心化的策略。在這個框架中，智能體處在一個部分可觀察的環(huán)境中，智能體只能觀察到有限的視野內的信息。智能體學習考慮其他智能體的位置對自己的影響，從而有利于整個集體而不僅僅是自己的最優(yōu)路徑。通過同時學習單個智能體路徑（主要是采用RL的方法）和模仿集中式專家經驗（IL），智能體最終學習到一個去中心化策略，同時包含了智能體之間的協(xié)調合作。最終學習到的策略可以擴展到更大規(guī)模智能體的環(huán)境中。文獻[98]將PRIMAL的工作由2D擴展到3D搜索空間，提出PRIMALc算法，通過獎勵塑性和梯度裁剪，將通信引入PRIMAL，使模仿?lián)p失穩(wěn)定地收斂到相對較低的值。文獻[99]提出PRIMAL2框架，該方法用于解決MAPF的一個變體：終身MAPF（lifelong MAPF，LMAPF），當智能體到達目標后立即被分配一個新的目標任務。PRIMAL2是一個分布式強化學習框架，智能體學習分散的策略，這樣有利于智能體在一個部分可觀察的環(huán)境中在線的規(guī)劃路徑。該方法通過構建新的局部觀察和各種訓練輔助工具將低密度的環(huán)境中學習到的經驗擴展到高度結構化和高度約束的環(huán)境中。PRIMAL2在完成時間和接的質量與最先進的MAPF求解器比較都有了明顯的提升，并且能擴展到2 000多個智能體。

圖4 RL/IL框架結構圖Fig.4 Structure of hybrid RL/IL

文獻[100]提出一個組合模型架構，該架構由一個局部觀察值中提取特征的卷積神經網絡（CNN）和在智能體之間交流這些特征信息的圖神經網絡（GNN）組成。該模型訓練階段模仿專家知識，然后用訓練好的策略來在線規(guī)劃路徑。文獻[101]提出一種基于進化強化學習方法MAPPER（multi-agent path planning with evolutionary reinforcement learning in mixed dynamic environments）在動態(tài)混合環(huán)境中來有效學習路徑規(guī)劃策略。強化學習方法應用到動態(tài)混合環(huán)境中，往往由于任務時間長和環(huán)境獎勵稀疏等原因造成算法性能下降，MAPPER算法在中央規(guī)劃器的指導下將長時間的任務分解為多個簡單任務，以此來提高智能體在大規(guī)模環(huán)境中的性能。該文獻的主要貢獻是提出一種基于圖像的表示方法來提高智能體處理不同障礙的魯棒性和一種基于進化的MADRL方法來提高訓練過程中的訓練效率。文獻[102]在MAPPER算法上進行了改進，在AC強化學習框架下引入注意力機制和BicNet[103]相結合的AB-MAPPER算法。在這個框架中，一方面利用具有通信功能的BicNet來實現(xiàn)團隊內部協(xié)調，另一方面，集中的評論家網絡可以選擇性地將注意力權重分配給周圍的智能體。在動態(tài)擁擠的場景中，AB-MAPPER算法性能顯著優(yōu)于MAPPER算法。文獻[104]提出GLAS（global-to-local autonomy synthesis）算法結合了避免局部最小值的集中規(guī)劃優(yōu)勢和可擴展的分布式執(zhí)行的優(yōu)勢。GLAS主要有三部分組成：（1）使用全局規(guī)劃器生成演示軌跡并從中提取局部觀察結果；（2）使用模仿學習來訓練高效的分散策略；（3）引入可微分的安全模塊，以確保智能體無碰撞操縱。

3.3.2 改進通信型

在高密度智能體的MAPF中，系統(tǒng)需要多個智能體在環(huán)境不完全可知的情況下相互關聯(lián)，這就需要智能體之間通信，相關工作總結于表10。

表10 改進通信型算法Table 10 Improved communication algorithms

在大規(guī)模智能體的MAPF中，為了加強協(xié)調與合作，智能體之間往往會進行通信，多智能體強化學習往往采用廣播通信的方式，信息被傳播到一定范圍內的其他所有智能體。經驗表明，這種廣播通信的方法與非通信方法相比有較大的改進，但缺點是廣播通信需要大量的帶寬，并在實踐中引起額外的系統(tǒng)開銷和延遲。在廣播通信中，并不是每個智能體的信息都對中央智能體有用。文獻[105]提出一種消息感知圖注意網絡（message-aware graph attention networks，MAGAT）。近年來，圖神經網絡（GNN）在分布式多智能體系統(tǒng)中學習同行策略的能力越來越流行，然而一般的GNN依賴于簡單的信息聚合機制，這種機制阻止了智能體對重要信息的優(yōu)先排序。MAGAT方法使用基于一鍵查詢類似機制，該機制可以確定鄰近智能體信息的相對重要性。MAGAT接近集中式規(guī)劃的專家性能，在不同智能體密度和不同通信帶寬下都是非常有效的，并且能夠很好解決之前未解決的MAPF實例，在大規(guī)模智能體的實例中，比基準成功率提高了47%。主要貢獻是：（1）將圖神經網絡和一鍵查詢機制相結合，提高智能體之間通信的有效性；（2）通過減少共享特征的大小來減少通信寬帶以提高通信的有效性；（3）在小地圖模型上訓練策略，在大地圖上進行測試，證明了此模型具有較好的泛化性和更高的效率。

文獻[106]提出一種請求應答機制（DCC），其訓練過程如圖5所示。選擇通信流程共分為四個模塊：第一個模塊是局部觀察輸入，智能體在每個時間步獲得一個6×6的方格形狀作為輸入；第二個模塊是觀察編碼，智能體的局部觀察輸入通過卷積網絡GRU進行編碼；第三個模塊是選擇判斷單元，觀察編碼修改局部觀察后輸入到Q網絡中，比較去掉該智能體和有該智能體的Q值變化來判斷鄰居智能體的信息是否對自己有用；第四個單元是通信模塊，智能體選擇通信后，將信息進行聚合，隨后輸入Q網絡得到下一步的動作。文獻[107]將通信與深度Q學習相結合，為MAPF提供了一種新的基于RL的方法（DHC），其中智能體通過圖卷積網絡實現(xiàn)協(xié)作。為了指導RL算法處理面向目標的長期任務，DHC嵌入了來自單一來源的最短路徑的潛在選擇作為啟發(fā)式指導。在障礙物密度大的環(huán)境中的實驗表明DHC方法的成功率高，平均步長小。基于RL的MAPF算法在高密度智能體環(huán)境中可能會產生更多的頂點沖突，從而導致成功率低或者學習時間更長，文獻[108]提出一種優(yōu)先通信學習方法（PICO），該方法將隱式規(guī)劃優(yōu)先級結合到分散式MARL框架中，可以利用隱式優(yōu)先級學習模塊形成動態(tài)通信拓撲，從而建立有效的避碰機制。PICO包括兩個階段，即隱式優(yōu)先學習階段和優(yōu)先通信學習階段。在隱式優(yōu)先學習中，PICO構建一個輔助模仿學習任務，通過模仿經典來預測每個智能體的局部優(yōu)先級。在優(yōu)先通信中，PICO獲得本地優(yōu)先級用于生成有智能體集群組成的時變通信拓撲，每個智能體都可以通過接受到的消息來學習減少碰撞的策略。

圖5 選擇通信流程圖Fig.5 System flow of decision communication

3.3.3 任務分解型

大型動態(tài)環(huán)境的MAPF是一個非常具有挑戰(zhàn)性的問題，因為智能體需要有效達到目標，同時避免與其他智能體或動態(tài)對象的沖突。解決這一挑戰(zhàn)的重要方法是將任務進行分解，相關工作總結于表11。

表11 任務分解型算法Table 11 Task decomposition algorithms

文獻[109]提出一種混合策略方法（HPL），將MAPF問題分解為兩個子任務：到達目標和避免沖突。為了完成每一項任務，利用RL的方法，如深度蒙特卡洛樹搜索、Q混合網絡和策略梯度方法，來設計智能體觀察值到動作的映射，最后將學習到達目標策略和避免碰撞策略混合為一個策略。接下來，引入策略混個機制，最終得到一個單一的混合策略，該策略允許每個智能體表現(xiàn)出兩類行為-個人行為（到達目標）和合作行為（避免與其他智能體發(fā)生沖突），其訓練框架流程圖如圖6所示。

圖6 混合策略方法Fig.6 Hybrid policy approach

文獻[110]提出G2RL算法（globally guided reinforcement learning approach）。該算法改進了經典算法中對動態(tài)障礙規(guī)劃效率不高的缺陷，此外，該算法引入了一種新的獎勵結構，具有良好的泛化能力，優(yōu)于現(xiàn)有的分布式方法。該算法的主要貢獻是：（1）提出一種分層框架，結合了全局規(guī)劃和局部基于RL的規(guī)劃以利于動態(tài)環(huán)境中學習到端到端策略。局部RL規(guī)劃器利用局部觀察信息來學習避免潛在的碰撞和不必要的繞行策略。（2）提出新的獎勵結構，提供密集的獎勵而不要求智能體在每一步嚴格遵守全局規(guī)劃，以此激勵智能體探索更多有潛力的路徑。（3）該算法在不同類型地圖和不同規(guī)模障礙環(huán)境中保持著較好的性能，具有較好的泛化性。文獻[111]使用視覺數(shù)據的多機器人協(xié)作導航任務構建了RL框架（VRL），利用深度學習技術從原始視覺觀察中提取高維特征，并將它們壓縮成有效的表示。其次使用圖神經網絡來學習相鄰機器人之間的信息共享和聚合，以實現(xiàn)有效的局部運動協(xié)調。該方法在大型機器人網絡和大型環(huán)境中具有很好的可擴展性。

3.3.4 其他基于RL的MAPF算法

其他基于RL的MAPF算法主要有：（1）針對MAPF環(huán)境的特點，在MADRL基礎上進行改進的MAPF算法；（2）將基于RL的MAPF算法和傳統(tǒng)算法或者其他領域先進技術相結合的算法；（3）針對MAPF應用在機場調度、自動倉庫和無人機等實際應用場景，如何處理實際約束而提出的解決方案。

盡管基于RL的MAPF算法提高了算法的擴展性，但解決組合域仍然具有挑戰(zhàn)性，因為智能體的隨機探索不太可能產生有用的獎勵信號，文獻[112]將知識編譯與RL相結合，將知識編譯集成到基于策略梯度和Q值的各種MARL算法中，所得到的算法在樣本復雜性和解決方案質量方面都顯著優(yōu)于原始算法。文獻[113]從全局靜態(tài)規(guī)劃和局部動態(tài)規(guī)劃兩個方面分析無人機路徑規(guī)劃，在A*算法基礎上，改進搜索策略、步長和代價函數(shù)，從而縮短規(guī)劃時間，大大提高算法的執(zhí)行效率。此外，在Q-learning的探索機制中加入動態(tài)探索因子，解決了Q-learning的探索困境，以適應無人機的局部動態(tài)路徑調整。將兩者結合形成全局和局部相混合的無人機路徑規(guī)劃算法。文獻[114]采用多步前進樹搜索方法來做出有效的決策，隨著智能體數(shù)量的增加，以更短路徑長度和求解時間優(yōu)于原有算法。文獻[115]提出了一種改進自動化倉庫中多個移動機器人學習路徑的稀疏獎勵問題的雙分段獎勵模型，使學習高效穩(wěn)定的進行，該文獻作為一個實例案例研究，具有較大意義。文獻[116]采用無模型的在線Q學習算法，多個智能體重復“探索-學習-利用”過程，積累歷史經驗評估動作策略并優(yōu)化決策，完成未知環(huán)境下的多智能體路徑規(guī)劃任務。文獻[117]提出將隨機探索與Q表探索相結合，在探索未知路徑和利用已有路徑中進行協(xié)調，提高探索效率。文獻[118]提出一種分層強化學習及人工勢場的多智能體路徑規(guī)劃算法，利用分層強化學習方法的無環(huán)境模型學習以及局部更新能力將策略更新過程限制在規(guī)模較小的局部空間或維度較低的高層空間上，提高算法的性能。文獻[119]提出基于慣性權重的雞群優(yōu)化算法，有效解決傳統(tǒng)路徑規(guī)劃算法收斂精度不高、容易陷入局部最優(yōu)的問題。文獻[120]針對智能體添加通信通道時智能體體輸出大小隨消息位數(shù)呈指數(shù)增長的限制，提出一個獨立的按位消息策略參數(shù)化，允許智能體輸出大小隨信息內容線性縮放。這個改進顯著提高了樣本效率并導致改進最終策略。文獻[121]提出一種在MARL背景下通過反向傳播學習稀疏離散通信的方法，激勵智能體盡可能少地進行通信，同時仍然獲得高回報。文獻[122]假設智能體在任意有向圖上運行，而不是通常假設的網格世界，這擴展可對環(huán)境無法以網格形狀建模的用例的支持。

3.4 基于RL的MAPF算法的挑戰(zhàn)

目前，基于RL的MAPF面臨大量挑戰(zhàn)[123]。這些挑戰(zhàn)來源于RL本身的特點以及外部環(huán)境。在實現(xiàn)基于RL的MAPF算法應用到實際場景中還要考慮許多因素。本節(jié)主要分析和總結這些挑戰(zhàn)，并對未來的研究方向給出建議。

（1）獎勵稀疏問題：多智能體路徑規(guī)劃過程通常是目標驅動的，環(huán)境給予的獎勵通常在智能體到達目標終點。在環(huán)境尺寸較大的環(huán)境中，智能體很難獲得最終的獎勵信號。此外，為了促進智能體快速到達目標，給予每個時間步負獎勵，但這也導致智能體在長期負獎勵信號下產生異常的動作，例如智能體在原地保持不動。稀疏的獎勵問題還會導致學習效率低下和收斂速度慢。解決獎勵稀疏問題的主要方法有好奇心驅動、獎勵塑形和分層強化學習等。好奇心驅動[124-126]主要思想是構建內在好奇心模塊，以從環(huán)境中提取額外的內在獎勵信號，鼓勵智能體進行更有效的探索。獎勵塑造[127]的主要思想是手動調整和修改智能體在不同狀態(tài)下的獎勵信號。獎勵塑造更為直觀，但是高度依賴于專家經驗。分層強化學習[128]的主要思想是將任務分解為多個離散或連續(xù)且易于解決的子任務，然后分而治之。

（2）樣本效率低：RL智能體每次面對新的任務，都要從頭開始學習。在訓練初期，過多的無用數(shù)據導致智能體低效的學習和更新策略。因此，如何更好地探索有價值的策略和提高有價值的經驗采樣效率是研究的熱點方向，也是提高基于RL的MAPF算法性能的關鍵。文獻[129-130]將優(yōu)先經驗重放技術應用與路徑規(guī)劃。文獻[131]構造無監(jiān)督表示作為輔助任務來提高樣本效率。文獻[132]提出自我預測表示，訓練智能體來預測自己的潛在狀態(tài)表示到未來的多個步驟，提高了在有限的交互中來收集數(shù)據的能力。

（3）環(huán)境動態(tài)復雜：多智能體路徑規(guī)劃任務需要多個智能體同時參與，且智能體之間需要相互配合并且決策的結果會相互影響。在多智能體系統(tǒng)中，各個智能體需要在環(huán)境不完全可知的情況下互相關聯(lián)完成任務。在MAPF場景中的環(huán)境是復雜的、動態(tài)的。這些特性給學習過程帶來很大的困難，例如，隨著智能體數(shù)量的增長，聯(lián)合狀態(tài)及動作空間的規(guī)模呈現(xiàn)出指數(shù)增長；多個智能體同時學習，每個智能體策略改變都會影響其他智能體策略改變。針對上述困難，可以在動態(tài)環(huán)境中借助一些輔助信息彌補其不可見信息，從而提高學習的效率。為了達到這個目的，研究者們提出一些方法，例如，智能體之間的通信，即智能體通過發(fā)送和接受抽象的通信信息來分析環(huán)境中其他智能體的情況從而協(xié)調各自的策略。文獻[133]提出使用注意力通信模型學習何時需要通信，以及如何整合共享信息以進行合作決策。文獻[134]提出獨立推斷通信，使智能體能夠學習智能體與智能體通信的先驗知識。

4 算法小結

經典的集中式規(guī)劃算法是目前最常用的也是效率最高的算法，如2020年的NeurlPS Flatland挑戰(zhàn)賽（一種火車調度大賽），獲得比賽第一名的是南加州大學的李嬌陽團隊，她們使用的是經典的基于搜索的MAPF算法，能同時對上千輛火車進行高效調度。這種算法特點是在解決固定環(huán)境和智能體密度小障礙物密度低的MAPF問題速度快?；诙嘀悄荏w深度強化學習的分布式執(zhí)行算法在實時解決路徑重新規(guī)劃問題上展示了較大的潛力，缺點是訓練時間較長。用集中式規(guī)劃算法作為專家知識來加速強化學習的訓練的方法在多智能體路徑規(guī)劃問題上收到較好效果。MAPF算法對比分析見表12所列。

表12 MAPF算法對比Table 12 Comparison of MAPF algorithms

5 研究展望

近年來，解決MAPF問題最常見的方法是集中式規(guī)劃算法，但隨著AlphaGo和AlphaZero的橫空出世，采用強化學習方法來解決MAPF中的路徑沖突問題成為研究熱點。2020年NeurlPS Flatland挑戰(zhàn)賽[96]，雖然提交最好算法是經典集中式規(guī)劃算法，但發(fā)現(xiàn)了許多有前途的基于MADRL的MAPF算法，使用RL方法實現(xiàn)了多樣的協(xié)調機制。未來的研究方向歸納為以下3個方面：

（1）為所有智能體在任意環(huán)境中規(guī)劃最優(yōu)路徑是NP-hard問題，因此使用實時的MAPF算法并不保證所有的智能體都成功規(guī)劃路徑?？梢酝ㄟ^實驗來確定在一組具有代表性的MAPF實例中最好的MAPF算法，但在什么時候使用哪個MAPF算法可以做得更好，在解決一些實際環(huán)境中必須快速做出決定，可以使用機器學習中的分類算法來定義一個快速計算映射，從MAPF實例的特征到性能最好的MAPF算法，以提高完成率，而不是使用單一算法解決每個問題。

（2）對于一個實際的MAPF問題，沒有那種算法最有效?；贏*和規(guī)約算法對于智能體密度小的環(huán)境最有效，CBS和ICTS算法對大型地圖環(huán)境最有效，基于強化學習的分布式執(zhí)行算法對部分可觀察的環(huán)境最有效。未來工作的一個具有吸引力的方向是創(chuàng)建混合算法，以促進不同MAPF求解器的優(yōu)勢互補。

（3）現(xiàn)在MAPF問題假設智能體的動作是離散的，只有前后左右和等待五個動作，且沒有考慮智能體運動的速度以及智能體體力消耗的因素，而真實世界的MAPF問題的智能體大多都是連續(xù)動作的，且智能體運動速度是連續(xù)變化，如何將離散動作升級到連續(xù)動作和節(jié)省智能體運動體力是未來工作的一個研究方向。

6 結束語

本文介紹了經典的MAPF集中式規(guī)劃算法和人工智能領域興起的基于強化學習的MAPF分布式執(zhí)行算法。經典算法在求解靜態(tài)環(huán)境的MAPF問題達到較高的求解速度和質量，基于RL的MAPF算法在實時重新再規(guī)劃的場景中具有較好的擴展性。下一步研究工作的重點是運用模仿學習和強化學習的方法將兩種類型算法相結合，以提高MAPF算法的效率和適用性。