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

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

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

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

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

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

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

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

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

關(guān)于MAPF問題有許多不同的定義和假設(shè)，以經(jīng)典的MAPF問題為例，對MAPF問題進(jìn)行闡述。

1.1 定義

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

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

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

1.2 沖突類型

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

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

1.3 目標(biāo)函數(shù)

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

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

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

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

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

2.1 基于A*搜索算法

2.1.1A*搜索算法

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

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

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

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

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

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

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

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

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

2.1.3A*搜索的擴(kuò)展

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

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

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

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

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

2.2 基于沖突搜索算法

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

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

2.2.1 經(jīng)典基于沖突搜索算法

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

2.2.2 增強(qiáng)的基于沖突搜索算法

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

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

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

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

2.3 代價(jià)增長樹搜索算法

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

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

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

2.4 基于規(guī)約算法

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

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

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

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

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

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

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

3.1 深度強(qiáng)化學(xué)習(xí)背景

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

3.1.1 強(qiáng)化學(xué)習(xí)

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

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

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

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

RL可分為以下基本方法：

（1）基于值方法（value-based methods）?；谥档姆椒ㄒ蕾囉谥悄荏w所處的狀態(tài)值，最優(yōu)策略是最大值函數(shù)。兩種最主要的方法是值迭代和Q-learning[64]，狀態(tài)轉(zhuǎn)移概率存在時(shí)使用值迭代方法，狀態(tài)轉(zhuǎn)移概率未知時(shí)使用Q-learning方法。Q-learning通過貝爾曼方程[65]來更新動(dòng)作值。

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

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

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

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

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

圖2 AC強(qiáng)化學(xué)習(xí)智能體Fig.2 Actor-Critic reinforcement larning agent

3.1.2 深度學(xué)習(xí)

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

CNN在計(jì)算機(jī)視覺和圖像處理等領(lǐng)域取得不錯(cuò)效果。它利用“卷積”的圖像相關(guān)特征自動(dòng)從數(shù)據(jù)中學(xué)習(xí)。通過增加CNN網(wǎng)絡(luò)的寬帶和深度可以使性能得到提高，但同時(shí)也會(huì)導(dǎo)致梯度消失等問題。

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

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

3.1.3 深度強(qiáng)化學(xué)習(xí)

深度強(qiáng)化學(xué)習(xí)利用神經(jīng)網(wǎng)絡(luò)來估計(jì)值函數(shù)和策略。下面介紹幾種主要單智能體強(qiáng)化學(xué)習(xí)算法。

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

基于策略函數(shù)：深度確定策略梯度（deep deterministic policy gradient，DDPG）[76]結(jié)合了DQN和AC方法來學(xué)習(xí)策DDPG包含四個(gè)神經(jīng)網(wǎng)絡(luò)：當(dāng)前Actor網(wǎng)絡(luò)、目標(biāo)Actor網(wǎng)絡(luò)、當(dāng)前Critic網(wǎng)絡(luò)、目標(biāo)Actor網(wǎng)絡(luò)。

DDPG的目標(biāo)是維護(hù)將狀態(tài)映射到動(dòng)作的Actor函數(shù)，并學(xué)習(xí)估計(jì)狀態(tài)動(dòng)作值的Critic函數(shù)。

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

單智能體強(qiáng)化學(xué)習(xí)主要算法在表6總結(jié)。

表6 單智能體強(qiáng)化學(xué)習(xí)算法對比Table 6 Comparison of single agent reinforcement learning algorithms

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

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

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

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

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

表7 多智能體深度強(qiáng)化學(xué)習(xí)算法對比Table 7 Comparison ofmulti-agent deep reinforcement learningalgorithms

3.2 強(qiáng)化學(xué)習(xí)在多智能體路徑規(guī)劃問題的適用性

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

3.2.1 環(huán)境

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

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

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

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

動(dòng)作空間：每個(gè)智能體的運(yùn)動(dòng)時(shí)間離散為每個(gè)時(shí)間步長，智能體在任一時(shí)間步長可采取行動(dòng)a,a∈[0,3]，分別表示智能體等待、向上、向下和向前運(yùn)動(dòng)。

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

目標(biāo)函數(shù)：強(qiáng)化學(xué)習(xí)的目標(biāo)就是每個(gè)智能體通過與環(huán)境互動(dòng)采取動(dòng)作來達(dá)到未來獎(jiǎng)勵(lì)之和最大化。從時(shí)間步長t+1到時(shí)間步T的回報(bào)定義為Gt，用公式（7）表示：

3.2.2 多智能體深度強(qiáng)化學(xué)習(xí)算法選擇與實(shí)現(xiàn)

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

3.3 基于強(qiáng)化學(xué)習(xí)的多智能體路徑規(guī)劃方法研究進(jìn)展

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

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

3.3.1 專家演示型

專家演示型方法主要采用強(qiáng)化學(xué)習(xí)和模仿學(xué)習(xí)（imitation learning，IL）和相結(jié)合的方法，這部分工作總結(jié)于表9。

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

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

圖4 RL/IL框架結(jié)構(gòu)圖Fig.4 Structure of hybrid RL/IL

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

3.3.2 改進(jìn)通信型

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

表10 改進(jìn)通信型算法Table 10 Improved communication algorithms

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

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

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

3.3.3 任務(wù)分解型

大型動(dòng)態(tài)環(huán)境的MAPF是一個(gè)非常具有挑戰(zhàn)性的問題，因?yàn)橹悄荏w需要有效達(dá)到目標(biāo)，同時(shí)避免與其他智能體或動(dòng)態(tài)對象的沖突。解決這一挑戰(zhàn)的重要方法是將任務(wù)進(jìn)行分解，相關(guān)工作總結(jié)于表11。

表11 任務(wù)分解型算法Table 11 Task decomposition algorithms

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

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

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

3.3.4 其他基于RL的MAPF算法

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

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

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

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

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

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

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

4 算法小結(jié)

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

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

5 研究展望

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

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

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

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

6 結(jié)束語

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