基于強化和模仿學(xué)習(xí)的多智能體尋路干擾者鑒別通信機制

摘 要：現(xiàn)有的基于通信學(xué)習(xí)的多智能體路徑規(guī)劃（multi-agent path finding，MAPF）方法大多可擴展性較差或者聚合了過多冗余信息，導(dǎo)致通信低效。為解決以上問題，提出干擾者鑒別通信機制（DIC），通過判斷視場（field of view，F(xiàn)OV）中央智能體的決策是否因鄰居的存在而改變來學(xué)習(xí)排除非干擾者的簡潔通信，成功過濾了冗余信息。同時進一步實例化DIC，開發(fā)了一種新的高度可擴展的分布式MAPF求解器，基于強化和模仿學(xué)習(xí)的干擾者鑒別通信算法（disruptor identifiable communication based on reinforcement and imitation learning algorithm，DICRIA）。首先，由干擾者鑒別器配合DICRIA的策略輸出層識別出干擾者；其次，在兩輪通信中分別完成對干擾者與通信意愿發(fā)送方的信息更新；最后，DICRIA根據(jù)各模塊的編碼結(jié)果輸出最終決策。實驗結(jié)果表明，DICRIA的性能幾乎在所有環(huán)境設(shè)置下都優(yōu)于其他同類求解器，且相比基線求解器，成功率平均提高了5.2%。尤其在大尺寸地圖的密集型問題實例下，DICRIA的成功率相比基線求解器甚至提高了44.5%。

關(guān)鍵詞：多智能體； 路徑規(guī)劃； 強化學(xué)習(xí)； 模仿學(xué)習(xí)； 干擾者鑒別通信

中圖分類號：TP391 文獻標志碼：A

文章編號：1001-3695（2024）08-032-2474-07

doi：10.19734/j.issn.1001-3695.2023.11.0555

Disruptor identifiable communication based on reinforcement and

imitation learning for multi-agent path finding

Li Mengtian1a，1b， Xiang Yingcen1a， Xie Zhifeng1a，1b， Ma Lizhuang1b，2

（1.a.Dept. of Film & Television Engineering， b. Shanghai Film Special Effects Engineering Technology Research Center， Shanghai University， Shanghai 200072， China; 2.Dept. of Computer Science & Engineering， Shanghai Jiao Tong University， Shanghai 200240， China）

Abstract：Most of the existing MAPF methods based on communication learning have poor scalability or aggregate too much redundant information， resulting in inefficient communication. To solve these problems， this paper proposed disruptor identifiable communication（DIC）， which learned concise communication excluding non-disruptors by judging whether the agent in the center of the field of view would change its decision-making due to the presence of neighbors， and successfully filtered out redundant information. At the same time， this paper further instantiated DIC and developed a new highly scalable distributed MAPF solver： disruptor identifiable communication based on reinforcement and imitation learning algorithm（DICRIA）. Firstly， the disruptor discriminator and the policy output layer of DICRIA identified the disruptor. Secondly， the algorithm updated the information of the disruptor and the communication wish sender in two rounds of communication respectively. Finally， DICRIA output the final policy according to the coding results of each module. Experimental results show that DICRIA’s performance is better than other similar solvers in almost all environment settings， and the algorithm increases the success rate by 5.2% on average compared to the baseline solver. Especially in dense problem instances with large-size maps， the algorithm even increases the success rate of DICRIA by 44.5% compared to the baseline solver.

Key words：multi-agent; path finding; reinforcement learning; imitation learning; disruptor identifiable communication（DIC）

0 引言

多智能體路徑規(guī)劃（MAPF）是為多個智能體尋找從起始位置到目標位置的無沖突路徑集合的問題。MAPF在許多領(lǐng)域都有著廣泛的應(yīng)用，如城市道路網(wǎng)絡(luò)[1]、火車調(diào)度[2]、多機器人系統(tǒng)[3]等。

按照規(guī)劃方式不同，MAPF算法分為集中式規(guī)劃算法和分布式執(zhí)行算法。集中式規(guī)劃算法是經(jīng)典的MAPF算法，主要分為基于A*搜索[4～8]、基于沖突搜索[9～13]、基于代價增長樹[14～16]和基于規(guī)約[17，18]四種。然而，這些集中式規(guī)劃方法的局限性在于它們通常無法在保持高質(zhì)量解決方案的同時擴展到更大的問題規(guī)模（更大的地圖、更多的智能體），且由于計算成本較高，往往無法滿足實際應(yīng)用中的頻繁實時重新規(guī)劃的需求。關(guān)于傳統(tǒng)集中式規(guī)劃算法的詳細介紹可參考文獻[19]。

分布式執(zhí)行算法是人工智能領(lǐng)域興起的基于學(xué)習(xí)的MAPF算法，由于采取部分可觀測性下的去中心化規(guī)劃，而在解決實際部署中的頻繁重規(guī)劃問題上表現(xiàn)出了較大的潛力，近年來引起了越來越多的關(guān)注。僅依賴局部觀測的去中心化規(guī)劃能夠讓MAPF問題輕松地擴展到任意的世界大?。ǖ貓D尺寸），但也嚴重限制了智能體可用的信息量，使它們難以完成需要高度協(xié)作的密集型MAPF任務(wù)。部分學(xué)者將強化學(xué)習(xí)與模仿學(xué)習(xí)相結(jié)合，采用傳統(tǒng)集中式規(guī)劃算法作為專家算法為強化學(xué)習(xí)提供指導(dǎo)[20，21]，但由專家演示提供的著眼全局的指導(dǎo)信息不足以使智能體學(xué)會高效合作。另一部分學(xué)者則通過引入可學(xué)習(xí)的通信方法[22～25]，允許智能體共享其信息，以彌補局部觀測信息量受限的缺陷。這相當(dāng)于間接擴大了FOV的范圍，使智能體能夠獲取到其他智能體FOV內(nèi)的觀測信息，從而增加單個智能體可用的信息量并促進團隊合作。但大多數(shù)采用通信的基于學(xué)習(xí)的MAPF方法的可擴展性都非常有限，通常無法在大小為40×40的地圖上解決包含超過64個智能體的問題實例。先進的SCRIMP[26]通過基于改進Transformer的全局通信來聚合上一個時間步所有智能體的消息，雖然有效緩解了可擴展性的問題，卻也造成了通信冗余，而這會在一定程度上損害智能體間的合作。并且，通信過去的消息（上一個時間步的消息）還存在滯后性的問題。因此，為多智能體路徑規(guī)劃設(shè)計一個能夠解決以上問題的通信機制十分重要且必要。

針對上述方法的局限性，本文提出干擾者鑒別通信機制DIC，并進一步將其實例化，開發(fā)了一個新的基于強化和模仿學(xué)習(xí)的MAPF求解器DICRIA。DIC通過忽略其他鄰居，只與那些對自身決策有影響的干擾者鄰居進行通信，有效避免了聚合不相關(guān)的信息，從而避免了通信冗余問題;同時降低了通信頻率，能夠提高多智能體規(guī)劃任務(wù)中的通信效率，幫助智能體更好地學(xué)會合作。具體地，其核心組件干擾者鑒別器將原始局部觀測與掩蔽局部觀測編碼后的結(jié)果輸入到DICRIA的策略輸出層，根據(jù)決策差異識別出對中央智能體實際有影響的干擾者鄰居。而后通信將分為發(fā)送通信意愿與給予反饋的兩輪過程。首輪過程中，智能體向干擾者發(fā)送攜帶有自身信息的通信意愿，干擾者根據(jù)接收到的通信意愿更新信息并反饋更新后的結(jié)果。在第二輪中，完成對意愿發(fā)送方信息的更新。DICRIA結(jié)合兩輪通信所聚合的信息與其他組成部分的編碼結(jié)果，并據(jù)此輸出最終的決策。實驗結(jié)果表明，本文新MAPF求解器幾乎在所有環(huán)境下，均在規(guī)劃平均所耗時間步數(shù)、沖突率及成功率上優(yōu)于其他最先進的同類求解器，并通過消融實驗證明了本文提出的通信機制的有效性。本文的主要貢獻總結(jié)如下：

a）提出一種適用于MAPF問題的新通信機制：干擾者鑒別通信，簡稱DIC。其核心組件是干擾者鑒別器。在通信之前，由干擾者鑒別器為每個智能體鑒別其FOV內(nèi)的干擾者，通過只與干擾者進行通信，DIC有效避免了通信冗余。并且，DIC可與任意集中訓(xùn)練分散執(zhí)行的強化學(xué)習(xí)框架兼容。

b）實例化DIC，開發(fā)了一種新的高度可擴展的分布式MAPF求解器：基于強化和模仿學(xué)習(xí)的干擾者鑒別通信算法DICRIA。智能體根據(jù)其視場內(nèi)的局部觀測及由DIC聚合的干擾者信息獨立做決策。

c）本文在一系列具有不同團隊規(guī)模、環(huán)境規(guī)模、障礙物密度的問題實例中進行了多方面的對比實驗。實驗結(jié)果證明了DICRIA在三項標準MAPF指標上的性能普遍優(yōu)于其他先進的同類求解器。最突出的是，DICRIA成功地將基線求解器的成功率平均提高了5.2%，在密集型環(huán)境下，甚至提高了44.5%。

1 問題定義

1.1 MAPF問題定義

經(jīng)典的MAPF以無向圖G=（V，E）和智能體集合A={a1，…，an}作為輸入，A中包含n個智能體。V為可通行的位置頂點集合，E為V中相鄰點間的連通邊的集合。每一個ai∈A都有一個唯一的起始頂點si∈V和一個唯一的目標頂點gi∈V。時間被離散化為時間步，在每一個時間步長上，智能體可以移動到相鄰的頂點，也可以在當(dāng)前位置頂點等待。智能體的路徑是從si開始，到gi結(jié)束的由相鄰（表示移動動作）或相同（表示等待動作）的頂點組成的序列。通常假設(shè)智能體到達目標后便永遠停留在目標位置上。路徑的長度計算為智能體向目標移動的過程中執(zhí)行的動作總數(shù)（包括移動和等待兩種動作），即其消耗的時間步數(shù)。智能體必須避免頂點沖突和交換沖突。當(dāng)兩個智能體在同一個時間步上占據(jù)相同的頂點將發(fā)生頂點沖突，以相反的方向穿過同一條邊時將發(fā)生交換沖突。MAPF的解決方案是一組無沖突的路徑，由n個智能體的路徑組成。目標通常是最小化路徑成本總和，即所有智能體到達其目標所消耗的時間步數(shù)之和。有關(guān)MAPF問題更全面的定義可參考文獻[27]。

1.2 RL環(huán)境設(shè)置

與上述經(jīng)典MAPF問題一致，本文將RL環(huán)境設(shè)置為離散的2D四鄰域網(wǎng)格環(huán)境，其中智能體、目標和障礙物各自占據(jù)一個網(wǎng)格單元。環(huán)境地圖是一個L×L的矩陣，其中0代表空單元格，1代表障礙物，地圖邊界之外的所有點均被視為障礙。每個問題實例中，本文在環(huán)境地圖上為n個智能體從空單元格中隨機選擇非重復(fù)的起始位置和相應(yīng)的目標位置，并且確保每對起始-目標位置之間的連通性。動作空間的大小設(shè)置為5，包括原地等待和上下左右四個方向的移動動作。在每個時間步上執(zhí)行決策動作之前，先檢查動作是否會導(dǎo)致沖突，若存在沖突則觸發(fā)沖突處理機制（將在第3章闡述）對動作進行調(diào)整，并允許智能體同時執(zhí)行調(diào)整后的動作。當(dāng)所有智能體均到達目標，或達到預(yù)定義的時間限制時（256個時間步），終止對問題實例的求解。本文假設(shè)通信不受障礙物阻礙。

MAPF環(huán)境被設(shè)置為部分可觀察，這更符合現(xiàn)實應(yīng)用中機器人視野受限的實際情況。每個智能體只能訪問其視場（FOV）內(nèi)的信息，F(xiàn)OV的大小為l×l，本文實驗中將l設(shè)置為奇數(shù)，以確保智能體位于FOV的中心。

本文獎勵設(shè)計同SCRIMP[26]，如表1所示。對除了位于目標位置之外的所有狀態(tài)都給予負獎勵以促進目標的達成。

2 干擾者鑒別通信機制DIC

受I2C[28]的啟發(fā)，本文提出了一種新的通信機制，稱為干擾者鑒別通信機制DIC。DIC有效彌補了現(xiàn)有MAPF求解器通信機制的缺陷，避免了聚合過多無用信息而造成通信冗余、降低通信效率的問題。

I2C通過兩個決策概率（考慮影響者時，被影響者的決策概率；掩蔽影響者時，被影響者的決策概率）之間的KL散度來度量一個智能體對另一個智能體決策的影響程度。當(dāng)KL散度很小時，被影響的智能體選擇不與影響者通信；當(dāng)KL散度較大，超過預(yù)定義的閾值時，則進行通信。然而，I2C的局限性在于KL散度閾值的設(shè)置高度依賴于經(jīng)驗實驗，且在不同的問題中差異較大，具有偶然性。此外，I2C還需要已知所有其他智能體的聯(lián)合觀測和動作，而在現(xiàn)實的MAPF問題中，具有局部觀測性的智能體通常只能觀察到有限范圍內(nèi)其他智能體的存在，且無法預(yù)測它們的動作。為此，本文提出DIC，其不依賴聯(lián)合觀測和動作，更適用于MAPF問題。

DIC的核心思想是，在訓(xùn)練和執(zhí)行期間有選擇的與部分鄰居進行通信。本文認為，距離較近的智能體彼此之間并不總是相關(guān)的，并不是所有鄰居都能提供有效信息。如果對鄰居的信息不作篩選和判斷，同SCRIMP一樣全盤接收，容易獲取到來自其他智能體的不相關(guān)且冗余的信息，聚合過多無用信息會間接降低實際有效的信息的正向指導(dǎo)效力，甚至?xí)`導(dǎo)模型，從而導(dǎo)致不明智的決策，損害智能體之間的合作。因此，有必要在通信之前對鄰居的信息進行篩選，為每個智能體找出那些能夠為其決策提供有效信息的相關(guān)鄰居，只與它們進行通信，能有效過濾冗余信息，降低通信成本，且有助于智能體更好地學(xué)習(xí)合作。而只有當(dāng)鄰居智能體的存在引起FOV中央智能體的決策調(diào)整時，DIC才確定該鄰居是相關(guān)的和有影響力的。本文將那些會對中央智能體的決策產(chǎn)生影響的鄰居稱為干擾者（disruptor）。對干擾者的判斷僅基于智能體的局部觀測來學(xué)習(xí)，因此能夠在大規(guī)模的多智能體規(guī)劃問題中通過分散執(zhí)行的方式有效部署。

DIC對干擾者的判斷由干擾者鑒別器來完成，圖1顯示了鑒別器的結(jié)構(gòu)與完整的鑒別流程。在3×3的FOV中，灰色方格代表障礙物，彩色方格代表智能體，紅色的“×”表示從智能體i的局部觀測中掩蔽掉智能體j（參見電子版）。以簡單的局部場景為例，假設(shè)智能體i的FOV內(nèi)只有一個鄰居智能體j。智能體i的局部觀測表示為oi（原始局部觀測），從oi中掩蔽掉智能體j，得到i的掩蔽局部觀測oi-j。通過在oi中將j對應(yīng)位置處的信息設(shè)置為某個特殊的值（例如0）來實現(xiàn)這種掩蔽。然后，智能體i分別基于oi和oi-j，使用決策模型（跳過通信塊）計算出兩個臨時的決策，對應(yīng)生成兩個臨時的動作。具體地，利用本文決策模型中觀測編碼器的第一個分支（將在第3.1節(jié)闡述），oi和oi-j作為其輸入值，將該分支的輸出結(jié)果經(jīng)過一個全連接（FC）層處理后直接輸入到策略輸出頭（將在第3.4節(jié)闡述），為i的兩種局部觀測分別計算出對應(yīng)動作空間中所有動作的概率分布，并將概率最大的動作確定為最終的臨時動作aitemp和ai-jtemp。如果aitemp和ai-jtemp相互匹配，則意味著智能體j的存在不會影響i的決策，即j與i不相關(guān)，不是i的干擾者，i不與j通信；否則，j確定為i的干擾者，i需要與j進行通信。

當(dāng)為智能體i鑒別出所有干擾者j之后，DIC的通信將分兩輪進行。本文將這兩輪的通信過程形象化地描述為智能體之間發(fā)送通信意愿（wish）以及給予反饋（feedback）的信息交流過程。在第一輪中，智能體i向其所有干擾者j發(fā)送wish，wish中包含自身信息以及鄰居的相對位置。干擾者可能收到來自不同意愿發(fā)送者的wish，并根據(jù)收到的所有wish更新自身的信息。在第二輪中，所有干擾者j將feedback回復(fù)給智能體i，feedback中包含更新后的自身信息及鄰居的相對位置。智能體i根據(jù)接收到的feedback完成信息的更新。

3 MAPF求解算法DICRIA

本文參考SCRIMP[26]，為解決 MAPF問題開發(fā)了一種新的求解器：DICRIA，其實例化了在第2章詳細介紹的新通信機制。DICRIA的網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示，由觀測編碼器（綠色）、干擾者鑒別器（黃色）、通信模塊（紫色）和輸出頭（藍色）四個主要部分組成（參見電子版）。干擾者鑒別器的詳情如圖1所示。FOV內(nèi)8通道的局部觀測以3×3的網(wǎng)格示例，其中彩色方塊表示智能體，彩色圓形表示顏色對應(yīng)的智能體的目標，灰色方塊表示障礙物。本章將分別描述這四個組成部分。

3.1 觀測編碼器

觀測編碼器由7個卷積層、2個最大池化層、3個全連接（FC）層和1個LSTM單元組成。在LSTM單元之前，被分成了兩條并行的分支，分別處理當(dāng)前時間步智能體的局部觀測和智能體的觀測向量兩個不同的輸入值。

分支1的輸入，即當(dāng)前時間步智能體的局部觀測oti（i=1，…，n）的形狀為l×l×8，由8個二進制矩陣組成。前四個是DHC[23]提出的啟發(fā)式通道，分別對應(yīng)上下左右四個移動動作，當(dāng)且僅當(dāng)智能體通過采取該動作更接近其目標時，對應(yīng)通道上的相應(yīng)位置被標記為1，以此編碼單智能體最短路徑的多種選擇。其余四個通道分別表示智能體的位置、中心智能體自己的目標位置（如果在FOV內(nèi)）、FOV內(nèi)其他智能體目標的投影位置以及FOV內(nèi)的障礙物。分支2的輸入是智能體的觀測向量ti，包含7個分量：智能體當(dāng)前位置與其目標沿x軸的歸一化距離dxti、沿y軸的歸一化距離dyti、總歐氏距離dti、外在獎勵ret-1i、內(nèi)在獎勵rit-1i、智能體上一個時間步的位置與其在緩沖區(qū)中存儲的歷史位置間的最小歐氏距離dmint-1i（均在第3.4節(jié)介紹）以及上一個時間步的動作at-1i。

智能體i的局部觀測oti首先通過分支1被編碼為ti，具體經(jīng)過了兩個相同的子模塊（3個卷積和1個最大池化層）和一個單獨的卷積層。同時，長度為7的觀測向量ti在分支2中由一個FC層獨立編碼，然后將分支2的輸出與ti串連得到o=ti。接著，o=ti與其自身經(jīng)過兩個FC層編碼后的結(jié)果相加，并和上一個時間步LSTM的輸出ht-1i一起輸入LSTM單元，從而賦予了智能體跨時間步聚合過去信息的能力。

3.2 干擾者鑒別器

該鑒別器需要當(dāng)前時間步智能體的局部觀測oti和當(dāng)前位置pti作為輸入，根據(jù)oti計算出掩蔽局部觀測oti-j（j∈Ni，Ni是i的FOV內(nèi)所有鄰居智能體的集合），根據(jù)pti計算鄰居智能體在FOV內(nèi)的相對位置eti。然后，按照第2章中描述的鑒別流程，為每個智能體找出各自的干擾者，由此確定t時刻，i的通信范圍為Ci={j|aitemp≠ai-jtemp}j∈Ni，aitemp和ai-jtemp為第2章中描述的臨時動作。Ci最終被編碼為通信掩膜，并和eti一起作為干擾者鑒別器的輸出值饋入通信模塊。

3.3 通信模塊

通信模塊由兩個相同的計算塊組成，分別對應(yīng)兩輪通信。通信采用圖卷積，以多頭點積注意力[29]作為卷積核，后跟一個GRU。本文將兩輪通信描述為智能體之間發(fā)送通信意愿（wish）和給予反饋（feedback）的過程。

在第一輪中，智能體i向所有的干擾者j∈Ci發(fā)送wish，wish中包含自身信息，即oti和ti經(jīng)過觀測編碼器處理后的輸出信息mti∈mt（mt是LSTM單元的輸出值），以及鄰居智能體的相對位置eti。干擾者可能收到來自不同意愿發(fā)送者的多條wish，由此干擾者j的wish接收范圍可表示為C～j={i|j∈Ci}。然后，干擾者j根據(jù)收到的所有wish使用多頭點積注意力更新自身信息mtj∈mt，同時保持意愿發(fā)送方i的信息在本輪不變，得到第一輪通信的輸出結(jié)果t。具體地，在每個獨立的注意力頭h中，首先將i∈j的自身信息mti通過矩陣WhQ映射為query，再將mti與eti的串連分別通過矩陣WhK和WhV映射為key和value。干擾者j與i∈j在第h個注意力頭中的關(guān)系則可以計算為

whji=softmax（WhQmtj·（WhK［mti，eti］）TdK）（1）

其中：dK是keys的維度。在每個注意力頭h中，以whji為權(quán)重對value進行加權(quán)求和，并將所有頭的輸出串連后通過一個神經(jīng)網(wǎng)絡(luò)層fnn，得到干擾者j的注意力輸出值tj：

tj=fnn（concat（∑i∈jwhjiWhV［mti，eti］，h∈Euclid Math OneHAp））（2）

最后，將干擾者j計算注意力前的自身信息mtj與tj經(jīng)過GRU聚合，得到最終更新后的信息tj。

在第二輪中，所有干擾者j將feedback回復(fù)給智能體i，feedback中包含更新后j的自身信息（j的第一輪通信結(jié)果tj）及etj。同理，意愿發(fā)送方i根據(jù)收到的所有feedback（來自j∈Ci）完成對自身信息的更新，更新方法與第一輪相同。與此同時，干擾者的信息在本輪保持不變。經(jīng)過兩輪通信之后，通信模塊的最終輸出為m=t。

3.4 輸出頭

輸出頭由5個全連接（FC）層組成。其中，一個是公共FC層，用于編碼LSTM單元的輸入（不包括ht-1i），LSTM單元的輸出mt以及通信模塊的輸出m=t三者的串連。余下的FC層用于將公共FC層的輸出分別編碼成策略（policy）、外在獎勵的預(yù)測狀態(tài)值（extrinsic value）、內(nèi)在獎勵的預(yù)測狀態(tài)值（intrinsic value）及可學(xué)習(xí)的阻塞預(yù)測值（blocking）四個不同的輸出值。

policy是模型的決策，即當(dāng)前時間步智能體的策略。具體為動作空間中每個動作的概率值，概率值最大的動作便是模型為智能體選出的在當(dāng)前時間步的最佳動作。

本文采用了SCRIMP對沖突決策的處理機制和用于鼓勵探索的內(nèi)在獎勵設(shè)計。當(dāng)模型輸出的決策將導(dǎo)致沖突時，則會觸發(fā)沖突處理機制。該機制以使未來收益最大化為準則，進行比較判斷，選出一個勝者智能體來執(zhí)行其首選動作，與之沖突的其他智能體則重新選擇一個新動作，以此來解決智能體間的沖突。當(dāng)與障礙物沖突時，則使智能體停留在原地并給予懲罰。而內(nèi)在獎勵是指遠離熟悉的區(qū)域所獲得的獎勵，相對地，執(zhí)行動作空間中的動作而獲得的獎勵被稱為外在獎勵。當(dāng)智能體的當(dāng)前位置與其歷史位置間的距離超過一個閾值時，便給予內(nèi)在獎勵，以此鼓勵探索，從而增大其到達目標的可能性。外在和內(nèi)在獎勵的預(yù)測狀態(tài)值便是模型對當(dāng)前時間步所能獲得的真實外在和內(nèi)在獎勵的估計，這兩個輸出值同時也在沖突處理機制中用于打破對稱性，幫助選擇最終被允許執(zhí)行首選動作的勝者智能體。

最后，blocking用于指示一個智能體是否阻礙其他智能體更早到達其目標，并隱式地幫助智能體理解它們可能受到的額外阻塞懲罰（表1）。

關(guān)于沖突處理機制和內(nèi)在獎勵的詳細介紹、兩個預(yù)測狀態(tài)值和blocking更具體的用法及作用請參見SCRIMP[26]。訓(xùn)練使用的損失函數(shù)及超參數(shù)的設(shè)置均同SCRIMP，具體見下一節(jié)。

3.5 訓(xùn)練設(shè)置

在MAPF問題中，一個問題實例的完整求解過程被稱為一個episode。設(shè)置一個episode的最大求解時間為256個時間步，超過時限仍未完成求解的問題實例被判定為求解失敗。訓(xùn)練的截止時間為3×107個時間步，由外層while循環(huán)來判斷是否達到訓(xùn)練的終止條件。在每一輪while循環(huán)開始之前，根據(jù)預(yù)定的比例隨機選擇網(wǎng)絡(luò)是通過IL還是RL進行訓(xùn)練，IL被選中的概率設(shè)置為0.1。在每一輪while循環(huán)中，本文借助Ray 1.2.0使用16個進程并行收集數(shù)據(jù)，并將epoch設(shè)置為10，batch size設(shè)置為1 024。優(yōu)化器選用Adam優(yōu)化器，lr為10-5。策略優(yōu)化的損失函數(shù)如下：

Lπ（θ）=1T1n∑Tt=1∑ni=1min（rti（θ）AtiEuclid ExtravBp，clip（rti（θ），1-，1+）AtiEuclid ExtravBp）（3）

rti（θ）=πθi（ati∣oti，ti，ht-1i，mt1，…，mtn）πθoldi（ati∣oti，ti，ht-1i，mt1，…，mtn）（4）

其中：θ表示神經(jīng)網(wǎng)絡(luò)的參數(shù)；rti（θ）是裁剪概率比；πθi和πθoldi分別是智能體i的新舊策略；是裁剪超參數(shù)，值為0.2；AtiEuclid ExtravBp是優(yōu)勢函數(shù)的截斷版。

4 實驗評估

本文模型在第1章描述的環(huán)境中進行訓(xùn)練和測試。訓(xùn)練時，每個問題實例中環(huán)境地圖的尺寸被隨機確定為10、25或40，障礙物的密度從0～0.5的三角分布中隨機采樣，峰值為0.33（與基線算法相同），且智能體個數(shù)固定為8。本文為測試設(shè)置了5種不同的地圖尺寸和智能體個數(shù)的組合：{[8，10]，[16，20]，[32，30]，[64，40]，[128，40]}，前者是智能體個數(shù)，并將每種組合的障礙物密度固定為0、0.15和0.3（DHC[23]和PICO[25]的最高測試密度）。為每種組合的每個障礙物密度各隨機生成100個問題實例，總共在100×3×5=1500個問題實例上進行了實驗評估。除非特別說明，在訓(xùn)練和測試階段FOV的大小均被設(shè)置為3×3。

本文使用PyTorch 1.11.0編寫代碼，Python版本為3.7。全部實驗在配備有兩個NVIDIA GeForce RTX 4090 GPUs和一個Intel Xeon Gold 6133 CPU @ 2.50 GHz（80核，160線程）的服務(wù)器上運行，系統(tǒng)環(huán)境為Ubuntu 20.04。

4.1 與基線求解器比較

本文測試了DICRIA與基線求解器SCRIMP在EL、CR和SR三項指標上的性能。其中：EL表示求解一個問題實例所消耗的時間步數(shù)（最晚到達目標的智能體的路徑長度）；CR表示與包括地圖邊界的靜態(tài)障礙物的沖突率，計算方式為式（5）；SR表示成功求解（所有智能體均在時限內(nèi)到達目標）的實例在全部測試實例中的占比，衡量在給定時限內(nèi)完成MAPF任務(wù)的能力。EL和CR越小代表策略越好，SR越大越好。SCRIMP的FOV大小設(shè)置為其原工作中的3×3，與本文設(shè)置相同。

CR=沖突數(shù)EL×智能體數(shù)×100%（5）

表2展示了在各項指標上的比較結(jié)果。在不同環(huán)境配置中，智能體個數(shù)在8、16、32、64和128之間變動；地圖大小在10～40變動；障礙物密度在0、0.15和0.3之間變動。所有數(shù)據(jù)均為相應(yīng)環(huán)境配置下隨機生成的100個問題實例上測試結(jié)果的平均值。表中，EL的計算排除了求解失敗的情況（超過256個時間步）；“—”表示無有效結(jié)果。每種環(huán)境配置下，各項指標最好的結(jié)果以粗體顯示。

如表2所示，在EL和SR這兩項指標上，DICRIA在所有情況下均優(yōu)于SCRIMP。在其無法解決的環(huán)境配置下，DICRIA仍然具有相當(dāng)?shù)某晒β?。尤其在地圖大小為40×40，障礙物密度為0.15，包含128個智能體的密集型實例下，本文求解器的成功率是91%，而SCRIMP僅為2%，DICRIA的成功率相比SCRIMP甚至提高了44.5%。在地圖尺寸（40×40）和智能體個數(shù)（128）保持不變時，將障礙物的密度從0.15增加到0.3，SCRIMP將無法完成任何任務(wù)，成功率為0%，而DICRIA仍然具有34%的成功率。這主要是因為SCRIMP采用全局通信機制，無論距離遠近，無論是否相關(guān)，每個智能體都會與環(huán)境中的所有其他智能體進行通信，而這顯然會聚合大量冗余信息。雖然其通信機制中的可學(xué)習(xí)權(quán)重能夠區(qū)分信息的重要性，在一定程度上緩解這一問題，但在全局通信所引入的大量無關(guān)信息面前，這一點補救措施所起的作用十分有限。尤其在此密集型的問題實例下，SCRIMP全局通信機制的缺陷更是加倍體現(xiàn)了出來，最終導(dǎo)致了0%成功率這一糟糕的結(jié)果。與之相反，全局通信的劣勢正是本文新通信機制的優(yōu)勢所在。DIC在局部FOV內(nèi)篩選通信對象，只與實際相關(guān)的干擾者鄰居交換信息。不僅從距離上摒除了“遠房親戚”無關(guān)信息的干擾，而且還會對近鄰是否影響自身決策作進一步的判斷，故而能夠有效過濾冗余信息，并以顯著的優(yōu)勢超越全局通信機制，獲得可觀的成功率。統(tǒng)計結(jié)果顯示，本文成功將基線求解器的SR平均提高了5.2%。

在CR方面，DICRIA在絕大多數(shù)情況下優(yōu)于SCRIMP，但在[128，40，0.15]和[128，40，0.3]的環(huán)境配置下略高于SCRIMP的CR值。造成這種情況的一個可能的原因是，在密集型環(huán)境中，大量智能體試圖搶占有限的可移動的位置節(jié)點，導(dǎo)致彼此的決策具有較強的相關(guān)性，SCRIMP通過全局通信而引入的更完備的信息將更有利于智能體在此環(huán)境下進行全局范圍內(nèi)的協(xié)調(diào)，而DICRIA基于局部FOV的通信機制卻不可避免地具有一定程度上的局部最優(yōu)性問題。但這種差異僅在個別情況下存在，且微乎其微，并不影響最終的成功率。

4.2 與其他MAPF求解器比較

本文將DICRIA與其他先進的基于學(xué)習(xí)的MAPF求解器進行了比較，包括DHC[23]、PICO[25]以及SCRIMP-local[26]。其中，DHC和PICO的實現(xiàn)來自各自的文獻，且FOV的大小均保留其工作中的原始設(shè)置，分別為9×9和11×11。SCRIMP-local是本文通過限制通信范圍得到的SCRIMP的擴展版本，規(guī)定只與歐氏距離不超過5的鄰居進行通信，其FOV大小同SCRIMP，為3×3。此外，本文還額外測試了傳統(tǒng)集中式算法ODrM*[6]，作為性能參考。

表3顯示了在不同環(huán)境配置的問題實例下，不同算法的三項標準MAPF指標的平均性能。與表2相同，EL的計算排除了求解失敗的情況（基于學(xué)習(xí)的方法超過256個時間步，ODrM*超過5 min未完成求解）；“—”表示無有效結(jié)果。除了ODrM*，其他算法在各項指標上的最好結(jié)果以粗體顯示?？傮w而言，DICRIA幾乎在所有情況下都具有最低的EL值，這意味著相比其他求解器，DICRIA獲得了路徑最短即質(zhì)量最高的解。

關(guān)于CR，DICRIA的CR始終低于SCRIMP-local，但大多數(shù)情況下還是高于DHC和PICO的。這可能是因為本文的內(nèi)在獎勵設(shè)置鼓勵智能體探索新的區(qū)域，在此過程中遇到障礙的可能性會不可避免地增加。相比之下，DHC和PICO傾向于讓智能體留在熟悉的區(qū)域，以此逃避探索未知可能帶來的懲罰，因為長期停留在安全區(qū)會具有更低的CR值。然而，在成功率上DICRIA完勝DHC與PICO。尤其當(dāng)智能體增加到32個以上，環(huán)境規(guī)模擴大到30×30時，DHC與PICO表現(xiàn)出了明顯的性能下降，PICO幾乎無法完成任何實例的求解。

本文注意到在[128，40，0.15]和[128，40，0.3]的環(huán)境配置下，DICRIA的SR低于SCRIMP-local。本文懷疑這是因為在密集型環(huán)境中，由于智能體決策的強相關(guān)性，個體的決策對更遠處的其他智能體仍會造成影響。DICRIA依靠3×3的FOV范圍來篩選通信對象，可能并沒有覆蓋到全部潛在的干擾者，所能獲取到的信息量在該情況下也顯得不夠充分，不足以支持智能體學(xué)會良好的配合。而SCRIMP-local由于額外設(shè)置了更大的通信范圍（歐氏距離不超過5），更能滿足密集環(huán)境下的通信需求，又因為減輕了原版SCRIMP全局通信冗余的問題，從而獲得了更高的成功率。在第4.3節(jié)中，當(dāng)FOV的大小調(diào)整為5×5時，在同樣的環(huán)境配置（128個智能體，地圖大小40×40，障礙物密度0.15和0.3）下， DICRIA的SR分別為99%和55%，均超越了SCRIMP-local（98%和45%），驗證了這一猜想。

此外，DICRIA在大多數(shù)情況下與傳統(tǒng)算法ODrM*具有相似的性能。特別是在需要智能體高度協(xié)作的最困難任務(wù)中（128個智能體，地圖大小40×40，障礙物密度0.3），DICRIA的成功率（34%）明顯超越了ODrM*（20%）。

4.3 FOV大小的影響

本文進一步測試了不同F(xiàn)OV的大小對模型性能的影響。根據(jù)測試結(jié)果發(fā)現(xiàn)，相較于SR，改變FOV的大小對EL和CR的影響并不明顯，因此圖3只展示了在SR上的對比結(jié)果。圖中，8、16、32、64、128是智能體個數(shù)，括號中為對應(yīng)的環(huán)境地圖的尺寸。圖3（a）～（c）分別是障礙物密度為0、0.15和0.3時的結(jié)果。如圖3所示，當(dāng)FOV的大小為5×5時，DICRIA實現(xiàn)了最佳性能。值得注意的是，隨著FOV尺寸的增大，訓(xùn)練和測試時間也明顯增長，因此需要在模型性能與時間成本之間有所權(quán)衡。

4.4 通信的消融

為了驗證本文通信機制的有效性，通過完全刪除干擾者鑒別器及通信模塊，開發(fā)了DICRIA的無通信版本——DICRIA-withoutComm。同時為了提高訓(xùn)練和評估的速度，仍然將FOV的大小設(shè)置為3×3（與訓(xùn)練原始DICRIA的設(shè)置相同），而不是采用在第4.3節(jié)確定的性能最佳的5×5。圖4只展示在對比最明顯且最重要的指標SR上的結(jié)果。障礙物密度固定為0.3。顯然，在智能體分布較密集的大型環(huán)境中，DICRIA-withoutComm表現(xiàn)出了性能的急劇下降，該結(jié)果充分證明了DIC的有效性。

5 結(jié)束語

在基于RL或IL的MAPF求解方案中引入通信的學(xué)習(xí)被證明是一種有效的方法，可以解決部分可觀測性下完全去中心化規(guī)劃導(dǎo)致的可用信息量受限的問題。本文考慮到現(xiàn)有基于學(xué)習(xí)的MAPF求解器通信方法的局限性，提出干擾者鑒別通信機制DIC。DIC憑借由干擾者鑒別器根據(jù)原始局部觀測與掩蔽局部觀測求得的決策差異來識別FOV內(nèi)的干擾者，通過排除非干擾者的簡潔通信過程而有效過濾掉了不相關(guān)的信息，避免了通信冗余。本文又進一步實例化了DIC，開發(fā)了一種新的基于強化和模仿學(xué)習(xí)的MAPF求解器：DICRIA，既保留了DIC能夠?qū)崿F(xiàn)高效通信的優(yōu)點，還具有較高的可擴展性。在一系列具有不同環(huán)境配置的問題實例上的實驗結(jié)果表明，DICRIA在三項標準MAPF指標上的性能普遍優(yōu)于其他最先進的同類求解器。幾乎在所有環(huán)境配置中，本文模型具有比基線求解器及其擴展版本更低的CR值。這說明通過篩選和收集相關(guān)的、實際有影響力的干擾者的信息進行通信，DICRIA有效加強了智能體間的合作，使得它們能夠以更協(xié)調(diào)的方式完成任務(wù)。本文還成功地將基線求解器的SR平均提高了5.2%。特別在大尺寸地圖的密集型問題實例下，DICRIA的成功率相比基線求解器，提升高達44.5%。此外，對通信機制的消融實驗充分證明了DIC的有效性。

最后，需要說明的一點是，雖然本文的干擾者鑒別通信機制給模型帶來了實際的性能提升，且具有諸多上述優(yōu)點，但干擾者鑒別器篩選通信對象、過濾冗余信息的過程也將產(chǎn)生額外的計算成本。將在未來的工作中，探尋能夠更好地平衡成本與性能的優(yōu)化方案。

參考文獻：

[1]Choudhury S， Solovery K， Kochenderfer M，et al. Coordinated multi-agent pathfinding for drones and trucks over road networks[C]//Proc of the 21st International Conference on Autonomous Agents and Multiagent Systems. London： AAMAS Press， 2022： 272-280.

[2]Mohanty S， Nygren E， Laurent F， et al. Flatland-RL： multi-agent reinforcement learning on trains[EB/OL]. （2020-12-11）. https：//arxiv.org/abs/2012.05893.

[3]Cartucho J， Ventura R， Veloso M. Robust object recognition through symbiotic deep learning in mobile robots[C]//Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE Press， 2018： 2336-2341.

[4]Ferguson D， Likhachev M， Stentz A. A guide to heuristic-based path planning[C]//Proc of International Workshop on Planningunder Uncertainty for Autonomous Systems： International Conference on Automated Planning and Scheduling. Palo Alto， CA： AAAI Press， 2005： 9-18.

[5]Standley T. Finding optimal solutions to cooperative pathfinding problems[C]//Proc of the 24th AAAI Conference on Artificial Intelligence. Palo Alto，CA： AAAI Press， 2010： 173-178.

[6]Wagner G， Choset H. Subdimensional expansion for multirobot path planning[J]. Artificial Intelligence， 2015， 219（2）： 1-24.

[7]Ren Zhongqiang， Rathinam S， Likhachev M， et al. Enhanced multi-objective A* using balanced binary search trees[C]// Proc of the 15th International Symposium on Combinatorial Search. Palo Alto， CA： AAAI Press， 2022： 162-170.

[8]Ren Zhongqiang， Rathinam S， Choset H. Loosely synchronized search for multi-agent path finding with asynchronous actions[C]//Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE Press， 2021： 9714-9719.

[9]Sharon G， Stern R， Felner A，et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial Intelligence， 2015， 219（2）： 40-66.

[10]Barer M， Sharon G， Stern R，et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem[C]//Proc of the 21st European Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2014： 961-962.

[11]Rahman M， Alam M A， Islam M M，et al. An adaptive agent-specific sub-optimal bounding approach for multi-agent path finding[J]. IEEE Access， 2022， 10： 22226-22237.

[12]Li Jiaoyang， Ruml W， Koening S. EECBS： a bounded-suboptimal search for multi-agent path finding[C]//Proc of AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2021： 12353-12362.

[13]Andreychuk A， Yakovlev K， Surynek P，et al. Multi-agent pathfin-ding with continuous time[J]. Artificial Intelligence， 2022， 305： 103662.

[14]Shaaron G， Stern R， Goldenberg M，et al. The increasing cost tree search for optimal multi-agent pathfinding[J]. Artificial Intelligence， 2013， 195： 470-495.

[15]Walker T T， Sturtevant N R， Felner A. Extended increasing cost tree search for non-unit cost domains[C]//Proc of the 27th International Joint Conference on Artificial Intelligence.Palo Alto， CA： AAAI Press， 2018： 534-540.

[16]Walker T T， Sturtevant N R，F(xiàn)elner A， et al. Conflict-based increa-sing cost search[C]//Proc of the 31st International Conference on Automated Planning and Scheduling. Palo Alto， CA： AAAI Press， 2021： 385-395.

[17]Yu Jingjin， LaValle S M. Planning optimal paths for multiple robots on graphs[C]//Proc of International Conference on Robotics and Automation.Piscataway， NJ： IEEE Press， 2013： 3612-3617.

[18]Surynek P， Felner A， Stern R，et al. Efficient SAT approach to multi-agent path finding under the sum of costs objective[C]//Proc of the 22nd European Conference on Artificial Intelligence. [S.l.]： IOS Press， 2016： 810-818.

[19]劉志飛， 曹雷， 賴俊， 等. 多智能體路徑規(guī)劃綜述[J]. 計算機工程與應(yīng)用， 2022， 58（20）： 43-62. （Liu Zhifei， Cao Lei， Lai Jun， et al. Summary of multi-agent path planning[J]. Computer Engineering and Applications， 2022， 58（20）： 43-62.）

[20]Sartoretti G， Kerr J， Shi Yunfei， et al. PRIMAL： pathfinding via reinforcement and imitation multi-agent learning[J]. IEEE Robotics and Automation Letters， 2019，4（3）： 2378-2385.

[21]Lin Chen， Wang Yaonan， Yang Mo，et al. Multi-agent path finding using deep reinforcement learning coupled with hot supervision con-trastive loss[J]. IEEE Trans on Industrial Electronics， 2023， 70（7）： 7032-7040.

[22]Li Qingbiao， Lin Weizhe， Liu Zhe，et al. Message-aware graph attention networks for large-scale multi-robot path planning[J]. IEEE Robotics and Automation Letters， 2021， 6（3）： 5533-5540.

[23]Ma Ziyuan， Luo Yudong， Ma Hang. Distributed heuristic multi-agent path finding with communication[C]//Proc of IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE Press， 2021： 8699-8705.

[24]Ma Ziyuan， Luo Yudong， Pan Jia. Learning selective communication for multi-agent path finding[J]. IEEE Robotics and Automation Letters， 2021，7（2）： 1455-1462.

[25]Li Wenhao， Chen Hongjun， Jin Bo，et al. Multi-agent path finding with prioritized communication learning[C]//Proc of International Conference on Robotics and Automation. Piscataway， NJ： IEEE Press， 2022： 10695-10701.

[26]Wang Yutong， Xiang Bairan， Huang Shinan，et al. SCRIMP： scalable communication for reinforcement and imitation learning based multi-agent pathfinding[C]//Proc of International Conference on Autonomous Agents and Multiagent Systems. London： AAMAS Press， 2023： 2598-2600.

[27]Stern R， Sturtevant N， Felner A，et al. Multi-agent pathfinding： definitions， variants， and benchmarks[C]//Proc of the 12th Annual Symposium on Combinatorial Search. Palo Alto， CA： AAAI Press， 2019： 151-159.

[28]Ding Ziluo， Huang Tiejun， Lu Zongqing. Learning individually inferred communication for multi-agent cooperation[C]//Proc of the 34th Annual Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2020： 22069-22079.

[29]Vaswani A， Shazeer N， Parmar N，et al. Attention is all you need[C]//Proc of the 31st International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2017： 5998-6008.