基于改進CBS 算法的多智能體路徑規劃

王卓然，文家燕,2，謝廣明,3，蔣文宇

（1. 廣西科技大學 自動化學院, 廣西 柳州 545616; 2. 廣西科技大學 廣西汽車零部件與整車技術重點實驗室, 廣西 柳州 545006; 3. 北京大學 工學院, 北京 100871）

隨著人工智能技術的不斷發展，多智能體路徑規劃[1]在自動倉庫[2-4]、數字游戲[5]、火車調度[6]、城市道路網絡[7]、多機器人系統[8]等方面有廣泛的應用前景。多智能體路徑規劃是指在給定地圖下，為給定的所有智能體，以最小路徑代價或者最小化最大完工時間為目標，求解無沖突路徑。其中，最大完工時間表示最后一個智能體到達目標點的時間。

基于沖突的搜索(conflict-based search,CBS)算法[9]是近年來多智能體路徑規劃備受關注的算法之一，許多已有文獻在它的基礎上進行了一系列研究[10-18]，包括優先解決關鍵沖突、繞過沖突、向高層添加啟發值、對稱推理技術等。CBS 算法的中心思想是低層使用解耦路徑規劃算法為每個智能體規劃路徑，高層在約束樹(constraint tree, CT)上檢測并解決路徑沖突。沖突的選擇會影響CBS 的運行效率，選擇一個“好”的沖突，能夠快速地增加約束樹的下界，避免陷入相同代價節點的泥潭，從而更快地擴展到目標節點找到最優解。針對這個問題，Boyarski 等[10]提出使用多值決策圖(multi-value decision diagram,MDD)將沖突分類，并先消解優先級高的沖突，被廣泛應用到其他改進CBS 算法的文獻中。Huang等[19]提出了一個新的沖突選擇策略，并首次采用新的機器學習框架來學習該策略，其效果相較于文獻[10]，表現更佳，有效地提高了算法的求解效率和成功率。為了進一步提高算法的求解效率，本文在文獻[19]的基礎上，針對使用其沖突選擇策略，可能會出現一個節點中所有沖突都應被選擇，即有時沖突的區分度不明顯的問題，提出一個新的沖突選擇策略，并采用RankNet 算法[20]學習該策略，改進算法使用學習得到的排序模型為CBS 算法選擇沖突，能更快地選擇“好”的沖突，能大幅縮短算法的總運行時間和縮小搜索空間，有效提高算法的求解效率。仿真驗證所提的改進算法在運行時間、搜索空間和成功率上的有效性。

1 預備知識

1.1 多智能體路徑規劃

MAP F)[21]是為一組智能體{a1,a2,···,ak}在指定的無多智能體路徑規劃(multi-agentpathfinding,向圖G=(V,E)下尋找一組無沖突的路徑，其中k為智能體的數量，V是圖中頂點的集合，E是圖中頂點之間連接邊的集合，用v∈V表示智能體可以在圖中占據的頂點，用e=(vi,vj)∈E表示智能體可以從vi移動到vj或相反。每個智能體ai都有其起始位置si∈V和終點位置gi∈V。時間被離散化為時間步，在每一個時間步，智能體可以移動到非障礙節點的鄰節點也可以停在原地等待，不論移動還是等待，路徑代價都增加1。單個智能體的路徑代價等于智能體從起點到達終點并且之后不再移動所花的總時間步長。本文考慮兩種智能體之間發生的沖突：頂點沖突和邊沖突。頂點沖突＜ai,aj,u,t＞，即智能體ai和aj在相同的時間t都處在位置u；邊沖突＜ai,aj,u,v,t＞，即智能體ai和aj相向而行，ai在時間t處在位置u，t+1時間處在位置v，而智能體aj在時間t處在位置v，t+1時間處在位置u。本文以最小路徑代價為目標，為所有智能體找到從起點到終點總路徑代價最小的一組無沖突路徑。

1.2 基于沖突的搜索

CBS 算法是兩層算法，高層檢測所有路徑中是否存在沖突，低層使用space-time A*算法[22]解耦地為智能體求解有約束下的最優路徑。高層對CT 進行搜索，CT 是一顆二叉樹，CT 中的每個節點N由以下信息組成：

1) 約束集Ncons：約束由沖突分裂而來，且每個約束都只與一個智能體有關。頂點沖突會分裂為＜ai,u,t＞ 和＜aj,u,t＞，表示為不允許智能體ai(aj)在時間t處在位置u。邊沖突則分裂為＜ai,u,v,t＞和＜aj,v,u,t＞，表示為不允許智能體ai(aj)在時間t→t+1從位置u(v)到位置v(u)。CT 中根節點的約束集為空，其他節點的約束集Ncons除繼承父節點的所有約束外，還包括一個新約束，它來自父節點所選沖突分裂生成的約束。

2) 解決方案Nsol：含有每一個智能體ai的路徑，且每一條路徑都滿足Ncons中所有與ai有關的約束條件。

3) 沖突集Nconf：Nsol中存在的所有沖突。

4) 總路徑代價Ncost：Nsol中 所有路徑的代價總和。

CBS 算法首先生成根節點，根節點的Ncons為空，Nsol由低層算法為每個智能體規劃的路徑構成，并計算總路徑代價Ncost，而后檢測Nsol存在的路徑沖突并構成Nconf。每次都在CT 中選擇最小Ncost的節點進行擴展，并檢測當前擴展節點的Nconf是否為空，若Nconf為空也即無沖突存在，則CBS 算法停止運行并返回解Nsol；相反，CBS 算法默認情況下隨機在Nconf選擇一個沖突，將其分裂的兩個約束分別作為左右子節點的新約束，并繼承父節點的約束集構成兩個子節點的約束集Ncons。子節點只為新約束所涉及的智能體重新規劃滿足當前子節點Ncons的路徑，其余智能體的路徑不變，以此構成子節點的Nsol，若子節點有解則將其加入CT 中等待被擴展。CBS 算法具有完整性和最優性，它通過解決每個沖突的兩種情況來保證其完整性，通過在高層和低層中都使用最佳優先搜索來保證其最優性。

2 改進CBS 多智能體路徑規劃算法

對于CBS 算法，選擇一個“好”的沖突能更快地擴展到目標節點，從而有效地縮小搜索空間，提高算法在路徑規劃中的求解效率。由此提出一種改進沖突選擇策略，并驗證其消解沖突的有效性；然后，為了發揮改進沖突選擇策略的優勢和進一步縮短算法的運行時間，采用基于神經網絡的RankNet 算法學習該改進策略，用訓練好的排序模型為CBS 算法選擇沖突。

2.1 沖突選擇策略

為了與已有沖突選擇策略展開比較，也便于后續問題的闡述，事先給出以下2 種沖突選擇策略的定義。定義1 來自文獻[10]，將沖突劃分優先級，并優先選擇高優先級沖突進行消解。定義2 來自文獻[19]，通過假使每個沖突被選擇，其生成的相應兩個子節點的g+h的最小值作為該沖突的得分，優先選擇得分高的沖突。

定義1[10]對給定的CT中節點N，S0使用MDD[23]將Nconf中的沖突的優先級從高到低分類為關鍵沖突，半關鍵沖突及非關鍵沖突。存在相同優先級的沖突時，優先選擇沖突發生時間更小的沖突。

定義2[19]對給定的CT中節點N，S1計算Nconf中每個沖突的得分其中分別表示如果該沖突被選中，生成的左右兩個子節點的g+h值，g為Ncost，h由加權依賴圖(weighted pairwise dependency graph,WDG)[24]給出。并將得分由高到低進行排序，優先選擇得分最高的沖突。

使用S1作為沖突選擇策略求解實例的過程中有時會出現一個節點中所有的沖突得分都相同，而這些沖突對應的子節點的總路徑代價不同，包含的沖突數差異較大，未做進一步區分可能選擇的沖突會使其子節點包含更多的沖突數，以至于需要擴展更多節點來消解沖突的情況。

為了更直觀地展示這一情況，下面給出一個具體實例。如圖1(a)所示，智能體0、1、2 分別從起點B2、D2、D1出發，到目標點C2、B1、A2。使用CBS 的改進算法CBS+PC[10]+BP[25]+WDG[24]算法（以下仍簡寫為CBS 算法）求解，使用S1選擇沖突，得到的約束樹如圖1(b)所示。在調用低層算法單獨為每個智能體規劃最優路徑后，高層檢測到路徑間存在兩個沖突＜0,1,C1,2 ＞和＜0,2,C2,2 ＞。分別選擇這兩個沖突進行消解，得到相應的子節點信息位于沖突集一欄該沖突的右側。其中，l和r分別表示該沖突的左、右子節點的信息即子節點的g+h和子節點中包含的沖突數。可以看出使用S1計算得到兩個沖突的得分均為10，若不做進一步區分，選擇＜0,1,C1,2 ＞進行消解，則生成的左右兩個子節點中分別含有2 個和5 個沖突，需要擴展更多的節點來消解沖突，最終生成5 個節點才能找到目標節點。

圖1 多智能體路徑規劃實例及其約束樹Fig. 1 MAPF instance and its constraint tree

若根據沖突的子節點的信息進一步區分，在沖突的得分相同的情況下，優先選擇能使子節點更靠近目標節點的沖突，也即選擇能生成g更大，沖突數更少的子節點所對應的沖突。在此情況下，選擇＜0,2,C2,2 ＞進行消解，其約束樹如圖1(c)所示，則只需生成3 個節點就能夠找到目標節點。因此，從進一步對沖突進行區分的角度出發，對現有沖突選擇策略進行改進使其更具有優越性。

2.2 改進沖突選擇策略

接下來具體說明如何改進沖突選擇策略。

定義3 即改進沖突選擇策略仍按照定義2 優先考慮g+h，其次考慮g，g越大h越小則意味著生成的子節點的總代價更接近目標節點的總代價。在兩個子節點g+h相同的情況下優先擴展g更大的節點，更可能使整個約束樹更快地找到最優解。在此基礎上，為了充分利用子節點的信息，還考慮另一個子節點的g。其目的是向約束樹中添加g更大（更接近目標節點）的CT 節點，以加速求解最優解的過程。

定義3對給定的CT 中節點N，S2不僅計算Nconf中每個沖突c的得分vc（同定義2），還要收集該沖突c的得分vc對應的子節點的g值，與另一個子節點的g記為g′。首先將每個沖突的得分vc從高到低排序，再將相同的vc按g從高到低排序，再將相同的g按g′從高到低排序。優先選擇vc最高的沖突，其次選擇g最高的沖突，最后選擇g′最高的沖突。

為了驗證改進沖突策略的有效性，選擇CBS算法為多智能體規劃路徑，使用Python 語言編程和實現，仿真實驗在處理器為Intel(R) Core(TM)i5-12500H CPU @ 2.50 GHz，RAM 為16 GB 的計算機上運行，分別采用沖突選擇策略S0、S1和S2在隨機地圖上進行測試。隨機地圖大小為20×20，存在有25%的隨機障礙物，如圖2 所示。在此隨機地圖上生成50 組隨機起點和終點的實例，每個實例的運行時間限制為20 min，每個實例中智能體數固定為17。為了凸顯改進沖突策略和排序模型的優勢，大致將總的運行時間分為選擇時間和搜索時間。選擇時間精準記錄了算法在整個求解過程中所有用于運行沖突選擇策略的時間，而搜索時間等于運行時間減去選擇時間。搜索空間主要由CT 大小來衡量，它表示CBS算法成功求解實例時生成CT 節點的數量。仿真實驗結果如表1 所示，其中運行時間、CT 大小、選擇時間和搜索時間每一欄具體數值均為該50 組相應數據的平均值。可以看出，改進策略S2與S1的搜索時間和CT 都小于S0，均可有效縮小搜索空間和縮短搜索時間，且S2在CT 大小上優于S1，體現出改進策略的有效性。總的來說，改進策略S2表現更好。

表1 CBS 與不同沖突選擇策略的結果Table 1 Comparison of CBS with different conflict selection strategies

圖2 隨機地圖Fig. 2 Random map

2.3 機器學習算法學習沖突選擇策略

使用文獻[19]中使用的SVM 方法與本文所用RankNet 算法兩種機器學習算法來分別學習沖突選擇策略S1和S2。使用機器學習算法學習沖突選擇策略主要分為兩個部分：構建數據集和訓練排序模型。

2.3.1 構建數據集

需構建兩個數據集：訓練集Itrain和測試集Itest。Itrain和Itest是由若干實例I的數據集DI連接而成，每個實例均由在指定地圖上隨機生成的始末點構成。僅在數據收集和模型學習階段，固定實例的智能體數。CBS 算法在求解實例I時，需收集如下數據來構建數據集DI，具體步驟如下：

1) 收集CT 中所有生成的節點 N ；

2) ?N∈N，收集節點N的沖突集合Nconf；

3) ?N∈N，對每個沖突c∈Nconf收集其特征向量ΦN∶N∈N →[0,1]p，每個沖突c均有p個特征值；

4) ?N∈N，對每個沖突c∈Nconf收集其二值標簽yc∈{0,1}，對每個節點N，yN∈{0,1}|Nconf|。

對步驟3)和4)中的特征值和標簽值的具體說明如下：

特征值本文使用p維特征向量來表示一個沖突c，參考文獻[19]列出的特征指標對每個沖突生成其相應的特征值，一個沖突包含67 個特征值。這67 個特征值主要包括以下幾個方面：

1) 沖突的性質。主要有沖突的類型（頂點沖突和邊沖突）和優先級（關鍵沖突、半關鍵沖突和非關鍵沖突）。

2) 在當前CT 節點之前已經擴展的所有CT 節點中，統計與沖突有關的智能體或點被選中的頻率。

3) 與當前CT 節點Nsol相關的，CT 節點N、與沖突有關的兩個智能體ai和aj以及頂點u或邊(u,v)的信息。

4) 沖突的MDD 特性和WDG。

5) 對于當前沖突中的頂點u或邊(u,v)，統計地圖G中距離u（距離u或v）最短路徑為1～5 的所有頂點的數量。

由上述5 個方面可知，生成特征值所需要的信息有部分依賴于所處的地圖環境，但生成特征值的方法并不依賴于地圖環境。因此，可以使用同樣的方法在其他地圖上收集相應的特征值與標簽值，經訓練得到與其他地圖有關的排序模型。

對于每個沖突c的特征值，需以Nconf為一組將特征值歸一化為[0,1]，以消除奇異樣本數據導致的不好影響。

標簽值標簽值由選定的沖突選擇策略生成，并將其二值化。本文使用的標簽二值化策略參考文獻[19]，將排序后Nconf中前20%的沖突的標簽為1，其余標簽為0，若其他的沖突和標簽已經轉化為1 的沖突都有著相同的得分，則將其他沖突的標簽也設置為1。這樣設置使得排序模型能更專注于評分較高的沖突，盡可能少被不相關的沖突干擾。

將收集好的特征數據和標簽數據一一對應，以一定的格式構建數據集。

2.3.2 訓練排序模型

訓練SVM 排序模型的方法與文獻[19]類似，這里不做贅述，下面重點介紹使用RankNet 算法訓練排序模型。

RankNet 算法[20]是一個經典的排序學習算法，本文使用該算法預測每個沖突和它所屬節點的相關性大小，并依此來對沖突進行排序，進而選擇“好”的沖突。訓練出較為準確的排序模型具體來說是要確定函數f(x,w)，其中x為沖突特征，w為排序模型參數。通過多次訓練，使f所計算出的結果盡可能和真實值接近，即讓訓練集中所有沖突的偏序對P經計算后排序概率誤差最小：

其損失函數Cij為交叉熵損失函數：

其中，因RankNet 算法是基于pairwise 的排序學習方法，故需將數據集中的沖突轉換為沖突的偏序對P作為輸入。P由PN連接而成，PN={(ci,cj)|ci,cj∈Nconf∧Sij=1}，Sij=1表示沖突ci比沖突cj真實更相關。n為沖突的偏序對的總數，yˉij為沖突ci比沖突cj排序更靠前的真實概率，yˉij=0.5×(Sij+1)，yij為經模型計算后沖突ci比沖突cj排序更靠前的預測概率。

2.4 排序模型指導CBS 算法選擇沖突

利用得到的排序模型為CBS 算法選擇沖突的具體步驟如下：對每個當前節點N，當其沖突集Nconf中所含沖突數大于1 時，先計算每個沖突的特征向量，并將其歸一化后輸入到排序模型中，經排序模型打分得到Nconf中所有沖突的得分，因排序模型打分越高代表該沖突與當前節點相關性越高，即分數越高的沖突標簽為1 的可能性越大，故選擇排序模型打分最高的那個沖突c。

2.5 機器學習算法的選擇

2.5.1 SVM 參數設定

為了與文獻[19]對照，SVM 參數設定與文獻[19]相同，即選擇線性核， c為0.01。

2.5.2 RankNet 模型設計

采用Python 語言以及PyTorch 框架實現RankNet 算法。網絡參數設置如表2 設置。使用Xavier 初始化，使用momentum 為0.9 的SGD 優化器，將初始學習率設為0.01，使用L2 正則化和dropout 減少過擬合。

表2 RankNet 的網絡參數Table 2 Network parameters for RankNet

2.5.3 訓練結果

分別構建使用S1和S2策略的數據集，訓練集收集5 000 個節點，訓練集與測試集的比例為3∶2。訓練結果如表3 所示。主要從測試集的P@1 來考慮，P@1 表示經排序模型選取的沖突，標簽為1 的概率。

表3 SVM 和RankNet 分別學習 S1、 S2的結果Table 3 Comparison of SVM and RankNet with conflict selection strategie S1,S2

從結果上看，在相同機器學習算法不同沖突選擇策略的情況下，學習S1的效果整體上優于S2；在相同沖突選擇策略不同機器學習算法的情況下，使用RankNet 得到的排序模型，其P@1 均比SVM 高。

下面對比分析訓練的模型應用到CBS 算法中表現，分別將訓練好的排序模型為CBS 算法選擇沖突。使用NET1表示利用RankNet 算法學習沖突選擇策略S1得到的排序模型，其余類似。得到的結果如表4 所示。

表4 CBS 與不同排序模型的結果Table 4 Comparison of CBS with different sort models

由表4 可知，在學習相同的沖突選擇策略的情況下，運行RankNet 排序模型的時間多于運行SVM 排序模型的時間。這是因為RankNet 排序模型實質為網絡層的權重參數，沖突的特征值要通過三層網絡的計算才能得到得分。而SVM 排序模型實質為1 個一維權重列表，沖突的特征值只需與其一一對應相乘就能夠得到沖突的得分。盡管使用RankNet 排序模型會產生額外的時間開銷，但由于其選擇沖突標簽為1 的準確率往往較高，從而在求解實例的過程中表現優于SVM 排序模型。不論是選擇SVM 排序模型還是RankNet排序模型，學習改進沖突選擇策略S2的整體表現均優于S1。故選擇RankNet 算法學習改進沖突策略S2來為CBS 算法選擇沖突。

3 仿真結果與分析

為驗證改進CBS 算法的有效性，進行多組仿真實驗。首先對比分析在指定地圖下訓練得到的排序模型，在相同地圖不同智能體數的情況下，所提改進算法與已有改進算法的表現；其次對比分析在指定地圖下訓練得到的排序模型，在其他地圖上，所提改進算法與已有改進算法的表現。

3.1 相同地圖不同智能體數的實驗對比

與2.2 節仿真實驗部分設置相同，仍使用相同的CBS 算法，使用圖2 所示的隨機地圖。為防止實例過于簡單，無法明顯地突出所提改進算法的優勢，或者過于復雜，每次求解的時間太長，故設置智能體數分別為18、20、22 和24，并在該地圖上隨機生成相應智能體數的100 組實例，分別使用CBS+NET1和CBS+NET2求解。每個實例的運行時間均限制為10 min。表5 為兩個算法在運行時間、CT 大小，成功率方面的數據對比。其中，成功率為算法在指定時間內成功求解的實例總數占總實例數的比例。運行時間和CT 大小均為共同求解實例數據的平均值。

表5 兩組算法在不同智能體數下的表現Table 5 Comparison of CBS and improved CBS with different number of agents

由表5 可知，與CBS+S0相比，CBS+NET2能夠使運行時間縮短61.9%，搜索空間縮小80.1%并有效提高算法的成功率；與CBS+NET1相比，CBS+NET2能夠使運行時間縮短46.2%，搜索空間縮小51.9%。所提改進算法在智能體數不同的實例下，仍能有效地提高了算法在路徑規劃方面的求解效率。

3.2 不同地圖不同智能體數的實驗對比

使用學到的排序模型在不同地圖不同智能體數的情況下為CBS 算法選擇沖突，驗證所訓練的模型是否依賴于地圖。地圖選擇標準地圖的Maze 地圖，其大小為32×32，如圖3 所示。選擇由圖1 學習到的排序模型，智能體數分別設置為6、8、10 和12 在上隨機生成50 組實例，分別使用CBS+S0、CBS+NET1和CBS+NET2求解。每個實例的運行時間均限制為10 min。表6 為兩個算法在運行時間、CT 大小、成功率方面的數據對比。

由表6 可知，與CBS+S0相比，CBS+NET2能夠使運行時間縮短39.2%，搜索空間縮小59.6%并能夠有效地提高算法的成功率；與CBS+NET1相比，CBS+NET2能夠使運行時間縮短15.2%，搜索空間縮小25.4%。由此可知，所學模型在未學習過的地圖上，仍能有效提高路徑規劃的求解效率。

此外，本文所提的方法均可應用到其他地圖中，因為排序模型與沖突的特征值和沖突的得分密切相關。而獲取特征值和得分的方法均為獨立的，因此該方法在不同地圖中也具有很好的適應性。

4 結束語

本文主要聚焦于如何優化CBS 算法中沖突選擇的問題，提出一種改進CBS 算法的多智能體路徑規劃算法。首先提出一種新的沖突選擇策略，縮小了搜索空間。其次使用RankNet 算法學習該策略，得到一個既快速又準確的排序模型，該模型能選到“好”的沖突。最后改進算法使用該排序模型為CBS 算法選擇沖突。仿真實驗結果表明，當在同一地圖下，所提改進算法在不同智能體數的情況下，總體表現比之前的改進算法好，求解效率和成功率得到有效提升。當地圖變化時，相較于之前的改進算法，本文所提改進算法仍有很高的求解效率和成功率。未來工作考慮實際場景的動態性，開展在動態環境下提高多智能體路徑規劃效率的研究。