基于互斥鎖傳播的多智能體路徑規劃算法

岳榮康，丁 行，江 海，龍 吟

（1.西南科技大學 計算機科學與技術學院，四川 綿陽 621000；2.四川省煙草公司成都市公司，成都 610014）

0 概述

多智能體路徑規劃（Multi-Agent Pathfinding，MAPF）的目標是尋找出可使多個智能體無沖突地到達各自目的地的路徑集合［1］。多智能體路徑規劃算法在諸多領域得到廣泛應用，如智能倉庫［2］、機場托運［3］、自主導引車、機器人［4］以及數字游戲［5］等。在多智能體路徑規劃應用中，最常見的目標是使得多個智能體能夠以最短路徑或者最短時間到達各自的目的地。然而，無論是尋找最短路徑還是最短時間的方案，都是NP 難問題［6-7］。針對該問題，國內外學者在過去幾年內已經取得了一定的進展，即使是在超過100 個智能體的場景中，也能有效地尋找出合適的解決方案。

大多數方案在解決最優化MAPF 問題時，都假設時間被離散化為時間步以及每個操作的持續時間均為一個時間步，這些簡化假設削弱了多智能體路徑規劃算法在現實世界中的適用性［8］。本文的目標是解決一種更通用的多智能體路徑規劃問題，簡稱為MAPFR問題［9-10］。在MAPFR問題中，在連續時間線上的任意時刻智能體都占據了度量空間中的一個定義區 域。目前已 有算法（如E-ICTS［11］、ECBSCT［12］）解決了部分MAPFR問題，它們支持非均等時間成本的移動動作并考慮智能體占用的坐標區域。然而，這些算法仍然依賴于時間離散化來定義等待動作的持續時間，這可能會對解決方案的質量和運行時間產生負面影響［13］。最新提出的基于連續時間的沖突搜索（Continuous Conflict Base Search，CCBS）［14］算法雖然不依賴于時間離散化，但是它在面臨基數沖突時會在上層搜索中擴展過多的約束樹節點，繼而導致算法的空間復雜度與時間復雜度存在一定的瓶頸。

本文提出一種優化算法以進一步解決MAPFR問題。使用一種人工智能規劃領域中著名的互斥鎖傳播技術［15］，該技術是一種約束傳播的形式，對應于有向一致性，而有向一致性又是路徑一致性的截斷形式。互斥鎖傳播技術與所有約束傳播技術一樣，能夠高效地使隱式約束顯式化。在人工智能規劃中，互斥鎖傳播常應用于規劃圖，從而在多項式時間內緊密地近似從給定狀態到達的所有可達狀態的集合［16］，它已成功應用于設計狀態空間規劃器的可達性啟發式算法［17］和計劃空間規劃器的啟發式算法［18］中。規劃圖思想在多智能體路徑規劃研究中以多值決策圖（Multi-valued Decision Diagram，MDD）［19］的形式出現。MDD 是為每個智能體而單獨構建的，包含了它們的可達性信息［20］，但是，MDD 不包含智能體組合的可達性信息［21］。另一方面，直接為智能體組構建聯合MDD 在計算上是不可行的，因為聯合空間隨著智能體數量的增加呈指數增長［22］。互斥鎖傳播技術在人工智能規劃中緩解了上述困境［23］，本文將這種技術應用到多智能體路徑規劃研究中。在結合CBS 框架后，互斥鎖傳播能夠有效識別基數沖突，在算法運行中能夠取得更高的計算效率。現有工作只能在離散時間的假設下識別有限形式的基數沖突，并且需要手動設計對應的約束［24］，而互斥鎖傳播技術具有更強的遷移性，可以通過自動設計來打破對稱性的約束，從而在運行時間和成功率方面提高CCBS 的沖突解決能力。

1 背景知識

1.1 多智能體路徑規劃問題定義

本文通過六元組〈Γ,M,S,G,coord,A〉來定義多智能體路徑規劃問題，其中：Γ=(V,E)是一個圖；M是一個度量空間；S和G分別是起點和終點函數；coord 將Γ中的每個頂點映射到M中的一個坐標；A是有限移動動作的集合［15］。每個動作a?A都由一個持續時間aD和一個運動函數aφ定義。運動函數aφ是一個將時間映射到度量空間的函數aφ：[0,aD]→M。當執行動作a時，aφ(t)是智能體在時間t處在M中的坐標。值得注意的是，這些運動函數的定義允許模擬以非常數速度移動并遵循任意幾何曲線的智能體。

在MAPFR問題中有2 種類型的動作，即移動動作和等待動作。對于一個移動動作a?A，限制aφ，使它從某個頂點v開始在另一個頂點v′結束，且(v,v′) 是E中的邊，即存在v和v′，使 得aφ(0)=coord(v)，aφ(aD)=coord(v′)，(v,v′) ?E。用from(a)和to(a)分別表示這些頂點。本文通過假設移動動作集合的有限性，將所提算法的完整性和最優性限制為僅與所選移動動作集合相關。如果一個算法在解決方案存在的前提下能夠保證從一組移動動作集合A中返回一個有效的解決方案，則認為它對于移動動作集合A來說是完備的。在同樣的移動動作集合A中，由不同動作組合而成的解決方案可以是非最優甚至是無效的。因此，如果一個算法能夠保證它從移動動作集合A中返回的解決方案一定是所有有效方案中路徑代價最小的，則認為它對于移動動作集合A來說是最優的。

對于等待動作a來說，存在一個頂點v?V，使得對于每 個t?[0,aD]，都 有aφ(t)=coord(v)。為了完整性，本文為等待動作定義from(a)和to(a)頂點。雖然移動動作的集合作為輸入被給出，但是等待動作的集合對于每個頂點v?V和任何正實數aD都是隱含定義的。因此，等待動作的集合是無限大的。當智能體在頂點v處時，它可以選擇在v開始的任何動作，如移動或等待，即from(a)=v。如果智能體的形狀重疊，則發生智能體之間的碰撞。為了檢測這種重疊，本文設計如下不同于傳統的碰撞檢測方法公式：

當智能體i和j分別占據位置mi和mj時，它們的形狀重疊時IsCollision(i,j,mi,mj)=true。例如，如果智能體是二維盤狀且半徑為r，則當智能體之間的距離小于2r時會發生碰撞。也就是說，在這種情況下，可以使用IsCollision(i,j,mi,mj)=dist(mi,mj) <2r來檢測智能體之間的碰撞，公式表達如下：

對于一個動作序列π=(a1,a2,…,an)，這里采用π[：j]表示前j個動作，π[：j]=(a1,a2,…,aj)。π的持續時間和運動函數分別稱為πD和πφ，它們的定義如下：

式（3）計算在執行π時每個時刻的位置，需要注意的是，運動函數是相對于相對時間而不是絕對時間定義的。例如，對于將智能體從v移動到v'的任何動 作a，有aφ(0)=v和aφ(aD)=v'。因 此，為了計 算πφ(t)，需要先確定在時間t計劃執行的動作。可以通過觀察π中的第i個動作從(π[：i-1])D的時間開始、在(π[：i])D的時間結束來計算。然后，通過該動作的開始時間校正t，以獲得智能體在該動作執行期間的位置。式（3）的最后一行定義了在計劃結束后智能體保持在其最后一個位置。

MAPFR與經典多車路徑規劃問題一樣，本文將單智能體的計劃定義為一個動作序列π=(a1,a2,…,an)，執行該序列會使智能體i從si移動到個單智能體計劃之間的沖突定義為：當2 個智能體同時執行各自的計劃時，則在某個時間點發生碰撞。

定義12 個智能體的路徑規劃有沖突，則有：

?t?[0,max(πiD,πjD)]，IsCollision(i,j,πiφ(t),πjφ(t))

當一個智能體的計劃路徑與其他智能體的路徑都不構成沖突時，則認為它的計劃路徑是有效的。單智能體的計劃路徑代價就是其持續時間，與經典多車路徑規劃問題類似，計劃路徑的代價總和是單一智能體計劃成本總和，而計劃路徑的完成時間是這些路徑代價的最大值。

1.2 基于沖突的搜索算法

CBS 是一個具有兩層結構的多智能體尋路算法。在CBS 的上層算法中維護著一棵約束樹，樹中每一個節點包含了約束和滿足該節點所有約束的路徑［17］。CBS 的下層算法則是針對單智能體的尋路算法，它的任務是為每一個智能體找到滿足當前約束樹節點中所有約束的最短路徑，通過它得到的路徑只考慮了約束，未將其他智能體的影響納入計算范圍內，因此，生成的路徑之間很可能存在頂點沖突或者邊沿沖突。當搜索完成后，若現有節點中的路徑集合無沖突，則會返回這個路徑集合作為最終的解；當路徑集合中存在沖突時，CBS 上層算法會選擇一個沖突擴展子節點，并為產生沖突的2 個智能體添加約束，直到找到無沖突的路徑集合為止。

根據文獻［18］的定義，CBS 算法中的沖突可以分為3 類，當2 個智能體分別滿足當前約束樹節點的約束后，有以下3 種情況：1）智能體ai和aj都無法找到小于等于路徑代價為li和lj的無沖突路徑對，則稱它們之間的沖突是重要沖突；2）次要沖突意味著2 個智能體中有且僅有1 個智能體可以找到使得彼此無沖突的路徑；3）一般沖突則是指2 個智能體均可找到無沖突的路徑。

1.3 基于動作序列的多值決策圖

在多智能體路徑規劃中，傳統的多值決策圖是由離散的時間步表示的層級關系及節點坐標頂點而構成的［19］，無法直接應用于連續時間下的多智能體路徑規劃問題。本文將傳統地圖中的邊替換為智能體實際執行的動作，并添加相應的動作執行時間窗。

在本文所提出的多值決策圖中，每個節點擁有level、time 和loc 屬性，level 代表在該智能體當前的動作規劃中到達該節點對應loc 的序列，time 則是到達對應loc 并停留的時間。每條邊還額外帶有執行時間窗，代表這條邊對應動作的開始執行時間與結束時間。

1.4 基于規劃圖的互斥鎖傳播

規劃圖一般包含命題節點和動作節點這2 種類型的節點，這些節點按級別劃分，偶數級別只包含命題節點，奇數級別只包含動作節點，零級別表示起始狀態。如果命題是下一級動作的先決條件，則命題節點與動作節點之間會連接一條邊。此外，如果命題由該動作變成真，則動作節點與命題節點之間也會連接一條邊［20］。規劃圖表示并行動作的效果，但這種方法非常粗略。為了更好地近似可達狀態集，使用以下規則在規劃圖上進行互斥傳播。

在第i層，如果2 個動作節點互斥，則滿足以下條件：1）一個動作的效果為另一個動作效果的否定；2）一個動作刪除了另一個動作的先決條件；3）一個動作的先決條件和另一個動作的先決條件在第i-1層互斥。如果2 個命題節點互斥，則滿足以下條件：1）一個命題是另一個命題的否定；2）第i-1 層中實現一個命題的所有動作與第i-1 層中實現另一個命題的所有動作之間均為互斥。

在多智能體路徑規劃的背景下，MDD 是一種有向的分層數據結構，類似于規劃圖。但是，由于每個智能體在執行動作時都可以在當前頂點u處等待或者經過邊，因此每個動作都有一個前提條件，即智能體在該動作開始執行時處于頂點u。因此，無需顯式表示動作層，為每個智能體單獨構建的MDD集合可以看作是規劃圖的特殊情況。同樣地，在MDD 中，互斥鎖傳播規則也可以簡化。如果MDDi中 的MDD 節 點ni和MDDj中 的MDD 節 點nj在t層是互斥的，則不存在沖突的子路徑，該子路徑將智能體ai和aj從其在時間步0 處的起始頂點移動到時間步t處的頂點ni.loc 和nj.loc。由于互斥傳播可以在多項式時間內進行，因此可以有效且緊密地近似可達頂點集，從而獲得有用的信息。

2 互斥鎖傳播在多值決策圖中的應用

本文根據多值決策圖的構成定義了2 種初始互斥鎖，分別是節點互斥鎖與邊沿互斥鎖。在一組多值決策圖中，2 個節點(ni.time ∩nj.time)≠?且ni.loc=nj.loc，則認定它們是一對節點互斥鎖。類似地，在一組多值決策圖中，2 條邊同時滿足(ei.time ∩ej.time)≠?、ei.from.loc=ej.to.loc 和ei.to.loc=ej.from.loc 時，則認為它們是一對邊沿互斥鎖。

例如，圖1 所示為4 種基數沖突，圖2 中展示了智能體a1和a2陷入圖1（a）所示的矩形沖突時的一組多值決策圖。多值決策圖中節點的標簽代表其所對應的地址坐標，虛線連接的一對節點指它們互為節點互斥鎖。在第1 層，MDD1的B2 與MDD2的B2 就明顯是一對節點互斥鎖，代表的實際意義是2 個智能體可能在第1 個動作執行完成后在坐標B2 處陷入沖突。

圖1 基數沖突Fig.1 Cardinality conflict

圖2 位于圖1（a）中的2 個智能體對應的MDDFig.2 The MDD corresponding to the two agents in Fig.1（a）

基于互斥鎖的傳播特性，本文定義2 種傳播互斥鎖在多值決策圖中的傳播方法，分別是基于節點的前饋傳播和基于邊的前饋傳播。在基于節點的前饋傳播中，當2 個節點(ni.time ∩nj.time)≠?且圖中所有滿足ei.to=ni和ej.to=nj的邊構成邊沿互斥鎖時，2 個節點構成傳播互斥鎖。在基于邊的前饋傳播中，當2 條邊(ei.time ∩ej.time)≠?且ei.from 和ej.from 互為互斥鎖時，則這2 條邊構成傳播互斥鎖。

例如，圖2 中實線連接的節點都是傳播節點互斥鎖。很明顯可以知道，MDD1的B2 與MDD2的B2就是一對初始節點互斥鎖，因此，MDD1中B2 到C2的邊與MDD2中B2 到B3 的邊是一組傳播互斥鎖。在第2 層，2 個MDD 中都只有1 條邊可以前往MDD1中 的C2 和MDD2中 的B3，正 是MDD1中 的B2 到C2以及MDD2中的B2 到B3。因此，MDD1中的C2 和MDD2中的B3 構成傳播互斥鎖，使用實線連接。

本文采用算法1 在一對MDD 中識別出初始互斥鎖與傳播互斥鎖，該算法類似于AC-3 算法。值得注意的是，這里的算法流程僅用于闡釋整個算法的核心想法，看起來可能效率略有不足。首先將所有的初始互斥鎖加入隊列中，然后逐一判斷所有互斥鎖能否向后傳播。傳播互斥鎖形成后也會加入隊列中，在MDD 的每一層總是先檢測節點的互斥關系再檢測邊的互斥關系。

算法1互斥鎖的生成

推論1如果MDDi中的ni與MDDj中的nj是一對互斥鎖，且有ni.level=nj.level=l，那么對于2 個智能體ai和aj，不存在一對可用的路徑pi與pj。具體來說，這對路徑的起始時間是0，起點分別是si與sj，且它們會在時間l分別到達ni與nj。

證明當ni與nj是一對初始互斥鎖時，結論則顯而易見。因此，本文著重論述當ni與nj是一對傳播互斥鎖的情況，假設此時存在一對這樣的可用路徑pi與pj且是無沖突的，定義ni,t表示pi中時間t時智能體ai所對應的到達節點ni，nj,t表示pj中時間t時智能體aj所對應的到達節點nj。由定義有ni,0.loc=si，nj,0.loc=sj，ni,l=ni，nj,l=nj。通過互斥鎖的定義，接下來證明ni與nj不是一對傳播互斥鎖。首先，可以知道si≠sj，因 此，ni,0與nj,0一定不 構成互斥鎖，又因為此時存在一對可用路徑pi與pj，所以可以知道在t

推論2如果MDDi中的ni與MDDj中的nj滿足ni.level=nj.level，但不構成互斥鎖，那么一定存在一對可用路徑pi與pj，使得智能體ai和aj可以在時間l時無沖突地到達ni與nj。

證明因為ni與nj不構成互斥鎖，所以一定存在一組終節點是ni與nj的邊不構成互斥鎖。因此，不斷反饋傳播可以一直推到智能體ai和aj的起點si與sj，則傳播得到的路徑就是這一對可用路徑pi與pj。

綜合推論1 與推論2，可以得到引理1。

引理1當且僅當MDDi中的ni與MDDj中的nj滿足ni.level=nj.level 且不構成互斥鎖時，存在一對可用路徑pi與pj，使得智能體ai和aj可以在時間l時無沖突地到達ni與nj。

3 基于互斥鎖傳播的基數沖突識別

在實踐中可以得知不同智能體的路徑長度并不總是等長的，因此，很可能出現智能體ai已經到達目的地并始終停留在gi處而智能體aj與之產生沖突的情況。針對智能體之間的可能沖突發生在智能體到達目的地之前，以及發生在其中一個智能體到達目的地之后的2 種情況，互斥鎖傳播需要不同的方式來進行處理。本文將這2 種沖突區分開來，并在后續做出不同處理。

終點前基數沖突（Pre-goal Conflict，PC）指不考慮智能體會在終點停留這一假設時，仍然無法在現有的一組MDD 中找出一對可用路徑，使得智能體ai和aj能夠無沖突地到達各自目的地。與之相對應的是終點后基數沖突（After-goal Conflict，AC），代表在給定的運動時長范圍內，存在一組可用路徑，可以使得2 個智能體無沖突地到達各自的目的地，但是無論哪一組可用路徑，總是會在另一智能體到達目的地后穿過其目的地。

算法2基數沖突的識別

引理2當且僅當算法2 返回非基數沖突時，中存在一對路徑代價分別為li與lj的可用子路徑pi與pj。

證明 假設此時存在一對可用路徑pi與pj，通過引理1 可以知道中第li層存在一個節點nj與的終節點不構成互斥鎖，又因為路徑pi與pj是無沖突的，所以智能體aj在li時間后不會穿過智能體ai的目標節點gi。綜上，此時存在一條從nj到gj的可用路徑，且其不會穿過智能體ai的目標節點gi，此時算法2 會返回沖突種類為非基數沖突。假設算法2返回非基數沖突，容易知道中存在一條路徑p可從nj到達終節點，并且中途不會穿過的終節點gi。通過引理1 可以得知，存在一對可用路徑pi與pj可使智能體ai和aj從起點移到gi與nj。如果智能體ai到達gi后一直停留在gi處，那么pj結合路徑p即可構成一條使得智能體aj從sj移動到gj且與pi無沖突的路徑。

綜上所述，當且僅當算法2 返回的沖突類型為終點前基數沖突或終點后基數沖突時，智能體ai和aj之間存在基數沖突。

4 基于互斥鎖傳播的基數沖突解決

本文提出2 種用于生成約束集合的算法，分別用來解決終點前基數沖突與終點后基數沖突。

推論3當沖突類型是終點前基數沖突時，如果智能體ai的路徑pi違背約束集合Ci以及智能體aj的路徑pj違背約束集合Cj，那么路徑pi與pj一定存在沖突。

推論4當沖突類型是終點后基數沖突時，如果智能體ai的路徑pi短于代價約束的限制，且智能體aj的路徑pj違背了約束集合Ci，那么路徑pi與pj一定存在沖突。

證明約束集合Cj中包含了第li層中與的終節點構成互斥鎖的節點以及中大于li層但滿足n.loc=gi的節點。如果智能體aj違背了約束集合Cj，那么它一定會與停留在gi處的智能體ai產生沖突。通過引理1 可知，此時智能體ai和aj對應的路徑pi與pj一定存在沖突。

5 實驗結果分析

將CCBS 與互斥鎖傳播(Mutex Propagation)相結合的方法簡稱為CCBS-MP。首先將CCBS-MP 與CCBS 在圖1 所示的基數沖突實例上進行比較，然后列出在不同柵格地圖環境下CCBS-MP 與CBS 框架中現有最前沿算法CCBS、SMT-CBS 以及A*算法中最前沿版本EPEA*的性能對比。在實驗中，除了沖突分類和約束生成之外，3 種算法采用相同的代碼庫。本文在亞馬遜云服務器中選用內存為8 GB 的EC2 虛擬機進行所有實驗。

5.1 基數沖突

本文在圖1 中給出了基數沖突的一些實例。表1～表3 分別顯示了CCBS-MP 和CCBS 算法在不同類型沖突中運行時的約束樹節點展開數。表中的前綴“>”表示求解器在5 min 內未能解決該實例，“>”后面的數字表示運行時限到達時的約束樹節點展開數。從中可以看出，CCBS-MP 在1 s 內就能解決所有實例。

表1 在不同長度的對稱沖突下約束樹節點生成數量對比Table 1 Comparison of the number of constraint tree nodes generated under symmetric conflicts of different lengths

表2 在不同面積的基數沖突下約束樹節點生成數量對比Table 2 Comparison of the number of constraint tree nodes generated under cardinality conflicts of different areas

表3 在不同面積的非基數沖突下約束樹節點生成數量對比Table 3 Comparison of the number of constraint tree nodes generated under non cardinality conflicts of different areas

由于缺少對應的規則生成具有針對性的約束，CCBS 不能有效地解決基數沖突。對于矩形沖突、走廊沖突和目標頂點沖突，CCBS-MP 在找到最優解之前僅展開1 個約束樹節點；對于交換沖突，CCBS-MP在約束樹底部僅展開3 個具有基數沖突的約束樹節點，而在約束樹的其余部分僅展開具有半基數和非基數沖突的約束樹節點。

5.2 基準環境

本文使用文獻［15］提供的4 個基準地圖，包括如下：

1）2 個小地圖，分別是16×16 的空地圖和擁有20%隨機障礙的32×32 地圖。

2）2 個大地 圖，分別是194×194 的游戲 地圖和128×128 的迷宮地圖，走廊寬度均為1［25］。

為了測試算法的求解極限，本文改變智能體的數量進行對比，對于不同的智能體數量，統計基準集中25 個不同場景下的平均成功率，將其作為最終的實驗結果之一。

圖3 顯示了CCBS-MP、CCBS、EPEA*［26］和SMT-CBS的成功率，分別統計它們在5 min 的時間限制內解決的實例數。圖4 顯示了每個求解器在所有已解決的實例上的平均運行時間。從中可以看出：在16×16的空地圖中有許多基數沖突，CCBS-MP 和SMTCBS 的效果都優于CCBS；在其他3 種環境更為復雜的地圖中，CCBS-MP 在運行時間和成功率方面均優于CCBS 和SMT-CBS。同時，可以觀察到EPEA*算法在環境較為簡單的空地圖中與CCBS 算法表現相當，而在較為復雜的地圖環境中且智能體數目較多時，EPEA*會出現成功率與運行時間性能急劇降低的情況，這主要是由于EPEA*算法空間復雜度過高，受限于實驗設備的內存空間，從而導致這樣劇烈的性能變化。針對CBS 框架中的算法，CCBS 無法識別出基數沖突與對稱沖突，且沒有生成對應的特殊約束，而SMT-CBS 在矩形沖突之外沒有更多的規則來應對基數沖突。在CBS 算法框架中，無法提前識別出基數沖突，導致的直接結果是過多地擴展約束樹節點，既延長了無沖突路徑集合的計算時間還占用了內存空間，每擴展一個約束樹節點，不僅需要下層算法重新根據約束規劃最優路徑，還需要上層算法重新檢測新路徑組合中可能存在的沖突。

圖3 4 種場景下的算法成功率對比結果Fig.3 Comparison results of algorithms success rates in four scenarios

圖4 4 種場景下的算法運行時間對比結果Fig.4 Comparison results of algorithms runtime in four scenarios

6 結束語

互斥鎖傳播技術可以有效推理2 個智能體之間的相互作用并從產生的互斥中推斷可應用的約束。基于互斥鎖傳播技術，本文提出一種新的算法框架，用于自動識別基數沖突并生成強約束集以對約束樹進行分支，同時保證CBS 的最優性與完備性。實驗結果表明，與目前前沿的MAPF 求解器相比，該算法的運行時間和成功率有一定優勢。下一步將利用互斥鎖傳播技術來解決半基數沖突和非基數沖突，同時在MAPF 的不完整布爾模型中使用互斥鎖傳播技術。