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

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

（1.西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽 621000；2.四川省煙草公司成都市公司，成都 610014）

0 概述

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

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

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

1 背景知識(shí)

1.1 多智能體路徑規(guī)劃問題定義

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

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

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

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

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

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

MAPFR與經(jīng)典多車路徑規(guī)劃問題一樣，本文將單智能體的計(jì)劃定義為一個(gè)動(dòng)作序列π=(a1,a2,…,an)，執(zhí)行該序列會(huì)使智能體i從si移動(dòng)到個(gè)單智能體計(jì)劃之間的沖突定義為：當(dāng)2 個(gè)智能體同時(shí)執(zhí)行各自的計(jì)劃時(shí)，則在某個(gè)時(shí)間點(diǎn)發(fā)生碰撞。

定義12 個(gè)智能體的路徑規(guī)劃有沖突，則有：

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

當(dāng)一個(gè)智能體的計(jì)劃路徑與其他智能體的路徑都不構(gòu)成沖突時(shí)，則認(rèn)為它的計(jì)劃路徑是有效的。單智能體的計(jì)劃路徑代價(jià)就是其持續(xù)時(shí)間，與經(jīng)典多車路徑規(guī)劃問題類似，計(jì)劃路徑的代價(jià)總和是單一智能體計(jì)劃成本總和，而計(jì)劃路徑的完成時(shí)間是這些路徑代價(jià)的最大值。

1.2 基于沖突的搜索算法

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

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

1.3 基于動(dòng)作序列的多值決策圖

在多智能體路徑規(guī)劃中，傳統(tǒng)的多值決策圖是由離散的時(shí)間步表示的層級關(guān)系及節(jié)點(diǎn)坐標(biāo)頂點(diǎn)而構(gòu)成的［19］，無法直接應(yīng)用于連續(xù)時(shí)間下的多智能體路徑規(guī)劃問題。本文將傳統(tǒng)地圖中的邊替換為智能體實(shí)際執(zhí)行的動(dòng)作，并添加相應(yīng)的動(dòng)作執(zhí)行時(shí)間窗。

在本文所提出的多值決策圖中，每個(gè)節(jié)點(diǎn)擁有l(wèi)evel、time 和loc 屬性，level 代表在該智能體當(dāng)前的動(dòng)作規(guī)劃中到達(dá)該節(jié)點(diǎn)對應(yīng)loc 的序列，time 則是到達(dá)對應(yīng)loc 并停留的時(shí)間。每條邊還額外帶有執(zhí)行時(shí)間窗，代表這條邊對應(yīng)動(dòng)作的開始執(zhí)行時(shí)間與結(jié)束時(shí)間。

1.4 基于規(guī)劃圖的互斥鎖傳播

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

在第i層，如果2 個(gè)動(dòng)作節(jié)點(diǎn)互斥，則滿足以下條件：1）一個(gè)動(dòng)作的效果為另一個(gè)動(dòng)作效果的否定；2）一個(gè)動(dòng)作刪除了另一個(gè)動(dòng)作的先決條件；3）一個(gè)動(dòng)作的先決條件和另一個(gè)動(dòng)作的先決條件在第i-1層互斥。如果2 個(gè)命題節(jié)點(diǎn)互斥，則滿足以下條件：1）一個(gè)命題是另一個(gè)命題的否定；2）第i-1 層中實(shí)現(xiàn)一個(gè)命題的所有動(dòng)作與第i-1 層中實(shí)現(xiàn)另一個(gè)命題的所有動(dòng)作之間均為互斥。

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

2 互斥鎖傳播在多值決策圖中的應(yīng)用

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

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

圖1 基數(shù)沖突Fig.1 Cardinality conflict

圖2 位于圖1（a）中的2 個(gè)智能體對應(yīng)的MDDFig.2 The MDD corresponding to the two agents in Fig.1（a）

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

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

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

算法1互斥鎖的生成

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

證明當(dāng)ni與nj是一對初始互斥鎖時(shí)，結(jié)論則顯而易見。因此，本文著重論述當(dāng)ni與nj是一對傳播互斥鎖的情況，假設(shè)此時(shí)存在一對這樣的可用路徑pi與pj且是無沖突的，定義ni,t表示pi中時(shí)間t時(shí)智能體ai所對應(yīng)的到達(dá)節(jié)點(diǎn)ni，nj,t表示pj中時(shí)間t時(shí)智能體aj所對應(yīng)的到達(dá)節(jié)點(diǎn)nj。由定義有ni,0.loc=si，nj,0.loc=sj，ni,l=ni，nj,l=nj。通過互斥鎖的定義，接下來證明ni與nj不是一對傳播互斥鎖。首先，可以知道si≠sj，因 此，ni,0與nj,0一定不 構(gòu)成互斥鎖，又因?yàn)榇藭r(shí)存在一對可用路徑pi與pj，所以可以知道在t

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

證明因?yàn)閚i與nj不構(gòu)成互斥鎖，所以一定存在一組終節(jié)點(diǎn)是ni與nj的邊不構(gòu)成互斥鎖。因此，不斷反饋傳播可以一直推到智能體ai和aj的起點(diǎn)si與sj，則傳播得到的路徑就是這一對可用路徑pi與pj。

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

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

3 基于互斥鎖傳播的基數(shù)沖突識(shí)別

在實(shí)踐中可以得知不同智能體的路徑長度并不總是等長的，因此，很可能出現(xiàn)智能體ai已經(jīng)到達(dá)目的地并始終停留在gi處而智能體aj與之產(chǎn)生沖突的情況。針對智能體之間的可能沖突發(fā)生在智能體到達(dá)目的地之前，以及發(fā)生在其中一個(gè)智能體到達(dá)目的地之后的2 種情況，互斥鎖傳播需要不同的方式來進(jìn)行處理。本文將這2 種沖突區(qū)分開來，并在后續(xù)做出不同處理。

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

算法2基數(shù)沖突的識(shí)別

引理2當(dāng)且僅當(dāng)算法2 返回非基數(shù)沖突時(shí)，中存在一對路徑代價(jià)分別為li與lj的可用子路徑pi與pj。

證明 假設(shè)此時(shí)存在一對可用路徑pi與pj，通過引理1 可以知道中第li層存在一個(gè)節(jié)點(diǎn)nj與的終節(jié)點(diǎn)不構(gòu)成互斥鎖，又因?yàn)槁窂絧i與pj是無沖突的，所以智能體aj在li時(shí)間后不會(huì)穿過智能體ai的目標(biāo)節(jié)點(diǎn)gi。綜上，此時(shí)存在一條從nj到gj的可用路徑，且其不會(huì)穿過智能體ai的目標(biāo)節(jié)點(diǎn)gi，此時(shí)算法2 會(huì)返回沖突種類為非基數(shù)沖突。假設(shè)算法2返回非基數(shù)沖突，容易知道中存在一條路徑p可從nj到達(dá)終節(jié)點(diǎn)，并且中途不會(huì)穿過的終節(jié)點(diǎn)gi。通過引理1 可以得知，存在一對可用路徑pi與pj可使智能體ai和aj從起點(diǎn)移到gi與nj。如果智能體ai到達(dá)gi后一直停留在gi處，那么pj結(jié)合路徑p即可構(gòu)成一條使得智能體aj從sj移動(dòng)到gj且與pi無沖突的路徑。

綜上所述，當(dāng)且僅當(dāng)算法2 返回的沖突類型為終點(diǎn)前基數(shù)沖突或終點(diǎn)后基數(shù)沖突時(shí)，智能體ai和aj之間存在基數(shù)沖突。

4 基于互斥鎖傳播的基數(shù)沖突解決

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

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

推論4當(dāng)沖突類型是終點(diǎn)后基數(shù)沖突時(shí)，如果智能體ai的路徑pi短于代價(jià)約束的限制，且智能體aj的路徑pj違背了約束集合Ci，那么路徑pi與pj一定存在沖突。

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

5 實(shí)驗(yàn)結(jié)果分析

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

5.1 基數(shù)沖突

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

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

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

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

由于缺少對應(yīng)的規(guī)則生成具有針對性的約束，CCBS 不能有效地解決基數(shù)沖突。對于矩形沖突、走廊沖突和目標(biāo)頂點(diǎn)沖突，CCBS-MP 在找到最優(yōu)解之前僅展開1 個(gè)約束樹節(jié)點(diǎn)；對于交換沖突，CCBS-MP在約束樹底部僅展開3 個(gè)具有基數(shù)沖突的約束樹節(jié)點(diǎn)，而在約束樹的其余部分僅展開具有半基數(shù)和非基數(shù)沖突的約束樹節(jié)點(diǎn)。

5.2 基準(zhǔn)環(huán)境

本文使用文獻(xiàn)［15］提供的4 個(gè)基準(zhǔn)地圖，包括如下：

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

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

為了測試算法的求解極限，本文改變智能體的數(shù)量進(jìn)行對比，對于不同的智能體數(shù)量，統(tǒng)計(jì)基準(zhǔn)集中25 個(gè)不同場景下的平均成功率，將其作為最終的實(shí)驗(yàn)結(jié)果之一。

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

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

圖4 4 種場景下的算法運(yùn)行時(shí)間對比結(jié)果Fig.4 Comparison results of algorithms runtime in four scenarios

6 結(jié)束語

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