基于沖突的搜索,以實現最佳的多智能體尋路

Submitted by neurta on Tue, 01/12/2021 - 16:31
啟發式搜索

1?。介紹

單主體尋路是在圖中兩個頂點之間找到路徑的問題。它是AI中一個基本而重要的問題,已經得到了廣泛的研究,因為這個問題可以在GPS導航[49],機器人路由[8],[3],計劃[6],[23]和網絡路由[ 7],以及許多組合問題(例如難題)[28],[27]。通常使用基于A *算法的搜索算法來最佳解決尋路問題[22]。此類算法執行由F(?)=G(?)+H(?),在哪里?G(?)是從開始狀態到狀態n的最短已知路徑的成本,并且H(?)是一個啟發式函數,用于估計從n到最接近目標狀態的成本。如果啟發式函數h可允許的,這意味著它永遠不會高估從n到目標的最短路徑,那么A *(以及由相同成本函數指導的其他算法)可以保證找到從開始狀態到目標的最佳路徑。目標狀態(如果存在)[11]。

多代理尋路(MAPF)的問題是單劑尋路問題為的推廣?>1個代理商。它由一個圖和許多代理組成。對于每個代理,給出了一個唯一的起始狀態和一個唯一的目標狀態,任務是在代理在其移動過程中不會發生沖突的約束下,查找所有代理從其起始狀態到目標狀態的路徑。在許多情況下,還有一個附加目標,即最小化累積成本函數,例如每個代理商達到其目標所需的時間步長之和。MAPF在視頻游戲,交通控制[43],[12],機器人技術[1]和航空[31]中具有實際應用。

求解MAPF的算法可以分為兩類:最優次優求解器。為MAPF問題找到最佳解決方案是NP-hard?[56],因為狀態空間隨代理的數量呈指數增長。當代理數量很大時,通常使用次優求解器。在這種情況下,目標是快速找到不同代理的路徑,并且通常很難保證給定的解決方案是最佳的。

本文解決的問題是找到MAPF問題的最佳解決方案。最佳求解器通常在代理數量相對較小且任務是找到最優,成本最低的解決方案時應用??梢詫⑵湫问交癁橐粋€全局的單代理搜索問題。因此,傳統的求解MAPF的最佳方法是使用基于A *的搜索[35],[45]。搜索樹中的節點由所有代理在時間t處的一組位置組成。起始狀態和目標狀態分別由不同代理的初始位置和目標位置組成。給定一個具有分支因子b的圖,有?(b)?任何單個代理的可能移動,因此A *搜索的分支因子為??(b?)這是代理商數量的指數。自然,基于A *的搜索算法可以最佳地解決此問題,但是它們可能運行很長時間或耗盡可用內存。

本文的第一部分對MAPF研究進行了調查。我們將所有現有工作分為兩個主要類別:最優和次優。然后,我們進一步對解決次優問題的不同方法進行了分類。這可以通過有助于這些分類的一致術語來完成。在本文的第二部分,我們介紹了一種用于最優求解MAPF的新方法。首先,我們提出了一種針對MAPF的新穎的基于沖突的形式化方法,以及一種相應的新算法,稱為基于沖突的搜索(CBS)。CBS是一種兩級算法,分為高級搜索和低級搜索。代理使用默認路徑初始化,其中可能包含沖突。在高級搜索是在執行約束樹(CT),其節點包含單個代理的時間和位置約束。在CT中的每個節點上,對所有代理執行低級搜索。低級搜索返回的單代理路徑與在任何CT節點上給出的約束集一致。如果在運行低級別代理之后仍存在沖突,即兩個或多個代理同時位于同一位置,則將關聯的高級節點聲明為非目標節點,然后進行高級搜索通過添加更多具有解決新沖突的約束的節點來繼續操作。

與基于A *的方法以及其他方法相比,我們研究了CBS算法的行為并討論了其優缺點?;趩栴}的特征,我們顯示了CBS比以前的方法有效得多的情況。我們還將討論CBS的局限性,并展示CBS劣于基于A *的方法的情況。提供的實驗結果支持了我們的理論理解。盡管CBS在某些情況下無效,但在許多情況下CBS優于EPEA *?[15],[20],這是針對此問題的基于A *的最新方法。具體來說,我們在開放式網格以及Sturtevant尋路數據庫中的許多基準游戲地圖上進行了實驗[47]。結果表明,在許多領域中,CBS優于基于A *的方法和最新的ICTS?[42]。

接下來,我們通過將CBS推廣到稱為元代理CBS(MA-CBS)的新算法中來緩解CBS的最壞情況性能。在MA-CBS中,任何一對代理之間允許的沖突數由預定義參數B限制。當沖突數超過B時,沖突代理將合并為元代理,然后由低級求解器將其視為聯合復合代理。在低級搜索中,MA-CBS使用任何可能的完整MAPF求解器來查找元代理的路徑。因此,MA-CBS可以看作是插入了低級求解器的求解框架。不同的合并策略會導致不同的特殊情況。原始的CBS算法對應于極端情況,其中乙=∞(永遠不會合并代理),而獨立檢測(ID)框架[45]是另一種極端情況,乙=0(總是在發生沖突時合并代理)。最后,我們介紹了MA-CBS的實驗結果,該結果表明MA-CBS在所有領域都比其他方法優越。另外,在附錄A中,我們介紹了CBS的一種變體,它的存儲要求在CT深度上是線性的。

該研究的初步版本先前已經出現[38],[39]。本文包含對CBS算法和MA-CBS框架的更全面描述,并與其他MAPF算法進行了更廣泛的理論分析和實驗比較。

2?。問題定義和術語

存在MAPF問題的許多變體?,F在,我們定義問題,并在問題的一般常用變體中描述算法[45],[46],[42],[38],[39]。此變體盡可能通用,以允許CBS適用,并且它包含許多子變體。然后,在第6.1節中,我們描述了在實驗環境中使用的特定子變量。最后,在第7節中,我們簡要討論了如何將我們的新算法修改為其他MAPF變體。

2.1?。問題輸入

輸入多代理尋路問題(MAPF)為:

(1)

有向圖?G(V,?)。圖的頂點是代理的可能位置,而邊是位置之間的可能過渡。

(2)

k個代理商已標記一種1個,一種2…一種?。每個代理商一種一世?有一個起始頂點?開始一世∈V?和目標頂點?目標一世∈V。

時間被離散為時間點。在時間點?0?代理人?一種一世?位于位置?開始一世。

2.2?。動作

在連續的時間點之間,每個代理可以執行到相鄰頂點的移動動作或等待動作,以使其當前頂點保持空閑。在給定的時間步長中,有很多方法可以解決一系列代理相互跟隨的可能性。這可能是不允許的,可能僅在鏈中的第一個代理移動到空位時才被允許,甚至在不包含任何空位的循環鏈中也可能被允許。我們的算法適用于所有這些變體。

2.3?。MAPF約束

MAPF中的主要限制在于,每個頂點在給定時間最多只能被一個代理占據。也可能存在一種約束,不允許多個代理在連續的時間步長之間穿越同一邊。一個沖突就是一個違反約束的情況下。

2.4?。MAPF任務

MAPF問題的解決方案是一組無沖突的路徑,每個代理一個路徑,其中一個代理路徑?一種一世?是一個序列?{移動,等待}?行動,如果?一種一世?從以下開始執行此一系列操作?開始一世,它將最終以?目標一世。

2.5?。成本函數

我們旨在解決給定的MAPF實例,同時最大程度地降低全局累計成本函數。我們在共同成本函數的上下文中描述了本文中的算法,我們稱其為成本總和?[12],[45],[42],[38],[39]。成本總和是所有業務代表對最后一次達到目標且不再離開目標所需的時間步長的總和。找到最優解決方案,即最小的成本總和,已經證明是NP難的[56]。

其他成本函數也已在文獻中使用。完工時間,例如,是另一種常見MAPF成本函數,直到最后劑到達其目的地,其最小化的總時間(即,最大的單個成本的)。另一個成本函數稱為燃料?[16],它對應于所有代理商行進的總距離(等于所消耗的燃料)。實際上,“燃料成本”功能是所有座席的成本總和,其中僅移動動作會產生成本,而等待動作是免費的。另外,也可以對不同的試劑賦予不同的權重。在第7節中,我們展示了如何針對此類成本函數修改算法。

MAPF的某些變體沒有要優化的全局成本函數,而是有一組單獨的成本函數,每個代理都一個[29]。在這樣的變體中,解決方案是成本的向量,每個代理一個。這種成本函數是多目標優化更廣泛領域的一部分,不在本文討論范圍之內。在其他MAPF變體中,代理可能是自私的,任務是設計一種機制,使他們合作[5]。在這項工作中,我們假設代理人是完全協作的,并不自私。

Yu和Lavelle?[54]研究了MAPF變體,在該變體中,不是給每個代理分配目標位置,而是給出一組目標位置,任務是找到一種將每個代理都帶到任何目標位置的解決方案。他們表明,使用網絡流可以在多項式時間內解決此MAPF變體。

2.6?。分布式與集中式

MAPF問題可以分為兩類:分布式集中式。在分布式設置中,每個代理都有其自己的計算能力,并且可以采用不同的通信模式(例如,消息傳遞,廣播等)。大量工作解決了分布式環境[18],[21],[2]。相比之下,集中式設置假定具有單個中央計算能力,需要為所有代理找到解決方案。同樣,集中式設置還包括以下情況:我們為每個代理提供了一個單獨的CPU,但假定完全共享知識,并且由集中式問題解決者控制所有代理。本文的范圍僅限于集中式方法,我們將在下一節中介紹許多方法。

2.7?。MAPF問題的示例

圖1顯示了一個示例2-agent MAPF實例,該實例將在本文中使用。每個代理商(鼠標)必須計劃一條通向其各自奶酪的完整路徑。代理商一種1個?必須從?小號1個?至?G1個?特工?一種2?必須從?小號2?至?G2。這兩個代理都有各自的長度為3的路徑:〈小號1個,一種1個,d,G1個〉?和?〈小號2,乙1個,d,G2〉, 分別。但是,這些路徑存在沖突,因為它們在時間點都包含狀態D?2。這些代理之一必須等待一步。因此,最佳的解決方案成本?C?在此示例中為7。

Image removed.

  1. 下載:下載全圖

圖1。具有2個代理的MAPF實例的示例。小鼠1和2必須分別到達奶酪1和2的碎片。

3?。集中式MAPF算法概述

假設采用集中式方法的工作可以分為三類。在最近的工作中使用的第一類求解器將MAPF簡化為計算機科學中已充分研究的其他問題。第二類求解器由MAPF特定的次優求解器組成。求解器的第三類是最優求解器。本文的重點是最優求解器,但是我們在下面包括對其他類的簡要調查。

3.1??;诩s簡的求解器

在最近的工作中使用的這類求解器將MAPF減少到計算機科學中已充分研究的其他問題。突出的例子包括降低到布爾可滿足性(SAT)[50],整數線性規劃(ILP)[55]和答案集編程(ASP)[13]。這些方法返回最佳解決方案,通常是針對制造成本函數設計的。它們效率較低,甚至不適用于成本函數的總和。另外,這些算法通常僅在小問題實例上才具有很高的效率。在大型問題實例上,從MAPF實例到所需問題的轉換過程具有非常大的多項式開銷,這使這些方法效率低下。

3.2?。MAPF特定的次優求解器

此類算法通常非常高效,但在某些情況下不能保證最優性甚至完整性。當代理數量很大且最佳解決方案難以解決時,通常使用它們。特定于MAPF的次優求解器可以進一步分類為子類。

3.2.1??;谒阉鞯拇蝺炃蠼馄?/h4>

基于搜索的求解器通常旨在提供高質量的解決方案(接近最佳),但是在許多情況下它們并不完整。這些求解器的不同之處在于它們對待代理之間的沖突的方式?;谒阉鞯拇蝺炈惴ǖ囊粋€突出示例是層次合作A *(HCA *)[43]。在HCA *中,根據某個預定義的順序一次計劃一個代理。一旦第一個代理找到到達其目標的路徑,就將該路徑寫入(保留)到全局保留表中。更具體地說,如果找到任何代理的路徑一種一世?是?v一世0=開始一世,v一世1個,v一世2,…,v一世升=目標一世,然后算法記錄該狀態?v一世??被代理商占用?一種一世?在時間點???。預留表可以實現為#v?[R?一世C?s×#?一世米?s??ps,或者使用更緊湊的表示形式,例如用于保留項目的哈希表。在搜索后繼代理的路徑時,前任代理選擇的路徑將被阻止。也就是說,代理程序可能無法遍歷與先前代理程序沖突的位置。先前已經提出了一種類似于HCA *的方法,用于多主體運動計劃[14]。Windowed-HCA *(WHCA *)[43]是幾種HCA *變體之一,僅在有限的窗口內執行協作尋路,此后其他代理將被忽略。完美的單一代理啟發法通常用于指導此搜索。因為HCA *是為內存有限的游戲而設計的,所以啟發式算法無法預先計算,必須在運行時進行計算。

后來的工作通過抽象狀態空間的大小擴展了HCA *,以減少構建啟發式算法的運行時成本[48]。最后,對WHCA *進行了增強,以便僅將窗口動態地放置在已知的沖突周圍,并根據參與沖突的可能性對代理進行優先級排序[4]。。HCA *的想法有一些缺點。首先,當代理程序太多時,可能會發生死鎖,并且不能保證HCA *是完整的。其次,HCA *無法為其解決方案的質量提供任何保證,因此解決方案可能遠非最佳。最后,HCA *甚至可能大大降低搜索速度。對于HCA *,WHCA *的窗口變體尤其如此。由于各個代理程序都在獨立尋找最小長度的解決方案,因此,在有大量可用空間時,代理程序可能會不必要地發生沖突,從而需要花費大量計算成本才能解決。保留表的想法也已用于管理交通路口,在該路口,汽車(代理人)必須越過路口而不會引起碰撞[12]。該系統解決了該問題的在線版本,即汽車到達路口后,一旦駛過路口便消失了。

3.2.2??;谝巹t的次優求解器

基于規則的方法包括針對不同場景的特定移動規則,通常不包括大量搜索。代理商根據特定規則計劃其路線?;谝巹t的求解器比計算質量更傾向于以較低的計算成本實現完整性。

TASS?[25]和Push and Swap(及其變體)[30],[37],[10]是兩個最近提出的基于規則的MAPF次優算法,它們在多項式時間內運行。1兩種算法都使用一組“宏”運算符。例如,推送和交換算法使用“交換”宏,該宏是在兩個相鄰代理之間交換位置的一組運算符。TASS和Push and Swap都不返回最佳解決方案,僅保證特殊情況下的完整性。TASS僅對于樹圖是完整的,而Push和Rotate?[10]是Push和Swap的變體,對于至少兩個頂點始終未被占用的圖,即TASS是完整的。?≤|V|-2。

在完成所有這些工作之前,需要完成多項式時間算法,該算法對于所有圖形[9],[34]都是完整的。之前的工作重點是MAPF的一個特定變體,稱為卵石運動協調問題(PMC)。PMC與MAPF相似,在MAPF中,每個代理都被視為一個小卵石,每個小卵石都需要移動到其目標位置。

3.2.3??;旌锨蠼馄?/h4>

一些次優的求解器是混合求解器,包括特定的運動規則以及重要搜索。例如,如果圖形是網格,則建立類似于交通法規的流量限制可以簡化問題[52],[24]。網格中的每個行/列都分配有兩個方向。建議或迫使代理在每個位置朝指定方向移動,以顯著減少沖突的機會和每個頂點的分支因子。這些方法將避免碰撞的優先級放在更短的路徑上,并在具有較大開放區域的狀態空間中很好地工作。對于一般情況,這些方法并不完整,因為可能會在瓶頸中發生死鎖。

Wang和Botea?[53]提出了另一種混合求解器?;舅枷胧穷A先計算完整路徑(P一世),每個代理商(一種一世)。對于每對連續的步驟(p?,p?+1個∈P)替代子路徑也已預先計算。如果代理的原始計算路徑一種一世?被其他代理商阻止?一種?,我們重定向代理?一種一世通過替代路徑之一進入旁路。這種方法的主要局限性在于,僅對具有可滑動屬性(在[53]中定義)的網格證明它是完整的。目前尚不清楚如何將這種算法推廣到不可滑動的網格。

Ryan引入了一種基于搜索的方法來解決MAPF問題,該方法使用抽象來減少狀態空間的大小[35]。輸入圖G分為具有特殊結構的子圖,例如集團,大廳和圓環。每個結構代表某種拓撲(例如,大廳是具有任意數量的入口和出口的單鏈接點的鏈)。每個結構都有一組基于規則的運算符,例如EnterLeave。一旦在抽象空間中找到了計劃,就可以使用基于規則的運算符來得出解決方案。使用這些抽象的一般方法是將整個MAPF問題作為約束滿足問題(CSP)解決。每個特殊的子圖為CSP求解器增加了約束,使CSP求解器更快[36]。子圖分解的效率(就運行時而言)取決于輸入圖的分區。尋找最佳分區是一個難題,并非總是可行的。開放空間不適用于按定義的結構進行劃分,因此該算法在具有開放空間的圖上效果較差。

3.3?。最佳MAPF求解器

最佳MAPF求解器通常會搜索一個全局搜索空間,該空間組合了所有k個代理的各個狀態。該狀態空間被稱為k-agent狀態空間。在各州??-agent狀態空間是不同的方式來放置?特工潛入|V|頂點,每個頂點一個代理。在開始狀態和目標狀態中一種一世?位于頂點?開始一世?和?目標一世, 分別。狀態之間的運算符是所有代理具有的所有不沖突的動作(包括wait)。給定這個一般狀態空間,任何基于A *的算法都可以用來最佳地解決MAPF問題。

我們用這個詞?b基礎表示單個代理的分支因子,即單個代理可以在一個時間步中移動到的位置數。本文重點介紹4連通網格b基礎=5,因為每個特工都可以朝四個基本方向移動或在其當前位置等待。k個代理的最大可能分支因子為b潛在=b基礎?。當在k?-agent狀態空間中擴展狀態時,所有b潛在可以考慮合并,但只有沒有沖突(與其他代理或障礙)的是合法鄰居。合法鄰居的數量表示為b法律。?b法律=?(b基礎?),因此對于最壞情況的分析,可以考慮?b法律?與...的順序相同?b潛在,即代理數量(k)呈指數形式。另一方面,在密集圖(具有許多代理且具有少量空狀態)中,b法律?可以比?b潛在。通常,確定b法律?可能的鄰居?b潛在鄰居是約束滿足問題(CSP),其中變量是代理,值是他們采取的行動,約束是為了避免沖突。此后,我們僅表示b法律由b。

3.3.1?。MAPF的允許啟發式

為了使用A *更有效地解決MAPF,需要一種非平凡的可允許試探法。一個簡單的可允許的啟發式方法是對單個代理的單個啟發式求和,例如對于4個連接網格的曼哈頓距離或對于歐式圖的歐式距離[35]。HCA *通過計算每個代理到目標的最佳距離而忽略了其他代理,從而對此進行了改進。由于此任務嚴格比使用其他代理進行搜索容易,因此可以將其用作允許的啟發式方法。HCA *對每個代理增量執行此計算,而Standley在解決MAPF問題之前先驗性地窮舉執行計算[45]。

我們將這種啟發式表示為個人成本啟發式(SIC)的總和。形式上,SIC啟發式計算如下。對于每個代理一種一世?我們假設不存在其他代理,并計算從狀態空間中的所有狀態到?目標一世;?這通常是通過反向搜索目標來完成的。多代理A *搜索中采用的啟發式方法是所有代理上這些成本的總和。對于圖1中的示例問題,SIC啟發式為3+3=6。注意,對于上述制造期變體,單個成本的最大值是可允許的啟發式方法,其中任務是使經過總時間最小化。

對于較小的輸入圖,可以通過預先計算輸入圖G所有對最短路徑矩陣,將任何問題配置的SIC啟發式存儲為查找表。對于較大的圖,我們計算從每個狀態到給定實例的目標狀態的最短路徑。但是,必須針對每個目標狀態集針對每個問題實例重新計算該值。

3.3.2?。MAPF的A *的缺點

A *總是從擴展狀態并將其后繼項插入打開列表(表示為OPEN)開始。所有展開的狀態都保存在一個封閉列表中(表示為CLOSED)。因此,用于MAPF的A *具有兩個缺點。首先,狀態空間的大小與代理程序的數量(k)成指數關系,這意味著對于大問題,無法在內存中維持CLOSED。其次,給定狀態的分支因子在k中可能是指數的??紤]一個在4個連接的網格上具有20個代理的狀態。每個特工最多可以進行5個動作(4個基本方向并等待)。完全生成所有520=9.53×1014甚至起始狀態的鄰居在計算上也不可行。已經提出以下增強來克服這些缺點。

3.3.3?。通過獨立檢測減少代理的有效數量

由于MAPF的狀態空間在代理數量上是指數級的,因此可以通過減少問題中的代理數量來獲得指數級加速。為此,斯坦德利介紹了獨立檢測框架(ID)[45]。

如果每個組都有一個最佳解決方案,則兩組代理是獨立的,以使兩個解決方案不會沖突。ID嘗試檢測獨立的代理組。算法1提供ID的偽代碼。首先,每個業務代表都放在自己的組中(第1行)。每個組使用A *(第2行)分別求解。對于給定的一組代理,由A *返回的解決方案是最佳的。然后檢查所有組的路徑相對于彼此的有效性。如果發現沖突,則將沖突的組合并為一組,并使用A *(第6-7行)進行最佳求解。重復進行重新計劃和合并組的過程,直到所有組的計劃之間沒有沖突為止。產生的組彼此獨立。請注意,ID并不完美,因為在ID返回的組中可能沒有發現更多獨立的子組。

Image removed.

  1. 下載:下載全圖

算法1。ID框架。

由于MAPF問題的復雜性通常是代理數量的指數,因此,求解具有ID的MAPF問題的時間取決于解決最大的獨立子問題的運行時間[45]。ID可以識別出可以由幾個獨立子問題的解決方案來構成對k-?agent MAPF問題的解決方案。我們用?′表示代理有效數量,即最大獨立子問題中的代理數量(?′≤?)。由于問題是代理數量的指數,ID將指數從k減少到?′。

考慮?一種*+ID關于我們在圖1中的示例問題(第2.7節),但帶有其他代理。假設第三代理一種3位于狀態D,其目標狀態為小號1個。ID將按以下方式工作。為代理商找到成本3的各個最佳路徑一種1個?(路徑?〈小號1個,一種1個,d,G1個〉)和?一種2?(路徑?〈小號2,乙1個,d,G2〉),并為代理商找到了成本為2的路徑?一種3?(路徑?〈d,一種2,小號1個〉)。驗證代理路徑時一種1個?和?一種2,狀態D發生沖突,并且代理一種1個?和?一種2被合并為一組。在該組上調用A *并返回成本為7的解決方案(代理一種2?在等?乙1個)。該解決方案現已通過代理解決方案進行驗證一種3。找不到沖突,算法停止。A *調用的最大組的大小為2。如果沒有ID,則A *必須解決3個代理的問題。因此,最壞情況的分支因子從b基礎3?至?b基礎2。

重要的是要注意,ID框架可以在第7行的任何最佳MAPF求解器(可以保證返回最佳解決方案)的頂部實現。因此,ID可以看作是利用MAPF求解器的通用框架。因此,ID也適用于本文提出的算法(CBS),而不適用于A *。確實,在CBS的實驗評估中,我們在CBS之上運行了ID。

3.3.4?。增強ID

為了提高識別獨立座席組的機會,Standley提出了使用避免沖突表(CAT)的平局決勝規則,如下所述。為代理找到的路徑存儲在CAT中。當新成立的合并組使用A *(第7行)求解時,A *搜索會打破聯系,而有利于將與其他組(不屬于合并的業務代表)的現有計劃路徑產生最少沖突的州組),存儲在CAT中。這種改進的結果是,A *使用避免沖突平局打破的解決方案不太可能引起與其他代理的沖突。結果,代理程序路徑更可能是獨立的,從而導致實質性的加速。

Standley還提出了ID(EID)的增強版本[45]。在此版本中,一旦發現兩組代理發生沖突,則在合并這些組之前調用解決沖突過程。EID嘗試通過嘗試重新計劃一個小組以避免另一小組的計劃來解決沖突,反之亦然。為了保持最佳狀態,在重新計劃期間發現的計劃成本必須與該組原始最佳解決方案的成本完全相同。如果組之間的沖突沒有解決,則將組合并并一起解決,就像在基本ID中一樣。如果解決過程能夠解決沖突,則不合并組,并且主循環繼續。

3.3.5?。M *

與ID相關的算法是M *?[51]。它是基于A *的算法,可根據沖突動態更改分支因子。通常,擴展節點僅生成一個子節點,每個代理都在該子節點中向目標最佳移動。這一直持續到q≥2節點n上的代理。在這種情況下,需要局部增加搜索維數。M *跡線從備份?通過所有的祖先向上?直到根節點和所有這些節點放回OPEN。如果這些節點之一再次擴展,它將生成bq孩子們在q沖突的代理人作出一切可能的行動和?-q?無沖突的代理人將采取最佳行動。

稱為遞歸M *(RM *)[51]的增強版本將q個沖突的代理分為多個代理子組,每個代理具有獨立的沖突。然后,在每個組上遞歸調用RM *。名為ODRM *?[17]的變體在RM *的基礎上結合了Standley的算子分解(請參閱第3.3.7節)。

3.3.6?。避免多余的節點

在某些限制下,已知A *會擴展找到最佳解決方案所需的最少節點數[11]。關于由A *生成的節點數,沒有這樣的陳述。為了找到最佳解決方案,必須生成某些節點。具有的節點?F>C?稱為剩余節點?[15]?,不需要為了找到一個最佳的解決方案。

剩余節點是所有已生成但從未擴展的節點。生成的節點數是擴展的節點數乘以分支因子。因此,在MAPF中,分支因子在代理程序數量上是指數級的,而剩余節點的數量則可能很大,避免生成它們會大大提高速度[20],[19]。挑戰在于如何在搜索過程中識別多余的節點。接下來,我們描述嘗試檢測剩余節點的現有技術。

3.3.7?。算子分解

Standley在他的算子分解技術(OD)中引入了減少多余節點數量的第一步[45]。代理被分配了任意(但固定)的順序。擴展常規A *節點后,OD將僅考慮并應用第一個特工的移動。這樣做會引入一個中間節點。在中間節點,僅考慮單個代理的移動,從而生成其他中間節點。將運算符應用于最后一個代理時,將生成一個常規節點。一旦找到解決方案,OPEN中的中間節點就不會進一步發展為常規節點,因此,常規剩余節點的數量將大大減少。

3.3.8?。增強部分擴展

增強的局部擴展A *(EPEA *)[20]是一種避免生成多余節點的算法,據我們所知,它是MAPF的最佳基于A *的求解器。EPEA *使用先驗領域知識來避免生成多余節點。擴展節點N時,EPEA *僅生成子級?C?與?F(?C)=F(?)。N的其他子項(與F(?C)≠F(?))被丟棄。這是借助域相關的操作員選擇功能(OSF)來完成的。OSF返回的運算符的確切列表將生成具有所需f值的節點(即,F(?))。然后將N重新插入到打開列表中,其f成本等于下一個最好的孩子的f成本。當N的新f值在打開列表中變為最佳時,N可能會在以后重新擴展。這避免了多余節點的生成,并大大減少了所生成節點的數量。

在MAPF問題中,當使用SIC啟發式方法時,可以有效地計算在給定方向上移動單個代理對f值的影響。在[20]中可以找到有關如何計算和實現用于MAPF的OSF的確切細節。

3.3.9?。不斷增加的成本樹搜索

我們最近提出了一種解決MAPF實例的新穎方法,該方法使用相應的搜索算法(稱為增加成本樹搜索(ICTS)[40],[42])來最佳地搜索稱為增加成本樹(ICT)的。ICTS是一種兩級搜索算法。

高層次:?ICTS在較高層次上搜索不斷增長的成本樹(ICT)。ICT中的每個節點都包含一個k矢量[C1個,…C?]代表所有可能的解決方案,其中代理的個人路徑成本一種一世?正是?C一世。ICT的根源是[選擇1個,。。。,選擇?],在哪里?選擇一世?是代理商的最佳個人路徑成本?一種一世,即距離的最短路徑長度?s一世?至?G一世而忽略其他代理商。通過將其中一位特工的成本限制增加一個(或某個單位成本)來產生ICT中的孩子。ICT節點[C1個,。。,C?]如果有一個完整的,無沖突的解決方案是一個目標,那么一種一世?正是?C一世。圖2說明了具有3個代理的ICT,所有代理的最佳單個路徑成本均為10。節點的總成本為C1個+…+C?。對于根,這恰好是起始狀態的SIC啟發式,即集成電路(開始)=選擇一世+選擇2+…+選擇?。我們使用Δ表示成本最低的ICT目標節點的深度。ICT樹的大小是Δ的指數。由于處于相同高度的所有節點的總成本相同,因此對ICT進行廣度優先搜索將找到最佳解決方案。

Image removed.

  1. 下載:下載全圖

圖2。ICT的三個代理商。

低級別:低級別充當高級別的目標測試。對于每個ICT節點[C1個,。。,C?]在高層訪問時,將調用較低級別。低層次的任務是找到一個無沖突的完整解決方案,以使代理的單個路徑的成本一種一世?正是?C一世。對于每個代理一種一世,ICTS會存儲所有單代理成本路徑C一世在稱為多值決策圖(MDD)的特殊緊湊數據結構中[44]。底層搜索MDD的叉積,以便為不同代理找到一組k條非沖突路徑。如果存在這樣一組無沖突的路徑,則低級別返回true,并且搜索暫停。否則,將返回false,并且高級繼續到下一個高級節點(具有不同的成本組合)。

修剪規則:針對高級節點引入了特殊的修剪技術[42]。這些技術為i代理搜索子解決方案,其中一世<?。如果存在不存在有效解決方案的子組,那么就不可能對所有k個代理都存在有效解決方案。因此,無需在k代理路徑空間中搜索解決方案,就可以將高級節點聲明為非目標。ICTS的增強版(信息技術委員會+修剪)[41],[42]比Standley的A *方法(最多)提高了兩個數量級(一種*+外徑+ID)[45]。

4??;跊_突的搜索算法(CBS)

現在我們來描述我們的新算法,即基于沖突的搜索算法(CBS)。稍后,在第8節中,我們將介紹對CBS的概括,稱為基于元代理沖突的搜索(MA-CBS)。另外,附錄A中介紹了CBS的內存有效變體。

回想一下,MAPF中A *所跨越的狀態空間以k(代理數)為指數。相比之下,在單主體尋路問題中,?=1個,并且狀態空間在圖形大小中僅是線性的。CBS通過將MAPF分解為大量受約束的單代理尋路問題來解決它。這些問題中的每一個都可以在時間上與圖的大小和解決方案的長度成比例地解決,但是這種單代理問題的數量可能成倍增加。

4.1?。CBS的定義

本文的其余部分使用以下定義。

?

我們僅在單個代理的上下文中使用術語路徑,并使用術語解決方案來表示給定的k個代理集合的k個路徑集合。

?

一個約束是一個元組(一種一世,v,?)?哪里代理?一種一世被禁止在時間步t占據頂點v。在算法過程中,代理將與約束關聯。代理的一致路徑一種一世是一條滿足其所有約束的路徑。同樣,一致的解決方案是由路徑組成的解決方案,例如,任何代理的路徑一種一世?與...的約束一致?一種一世。

?

一個沖突是一個元組(一種一世,一種?,v,?)?哪里代理?一種一世?和代理?一種?在時間點t占據頂點v。如果其所有路徑都沒有沖突,則(k個路徑)解決方案有效。如果盡管單個路徑與其代理關聯的約束一致,但這些路徑仍然存在沖突,則一致的解決方案可能無效。

CBS的關鍵思想是增加一組約束并找到與這些約束一致的路徑。如果這些路徑有沖突,因此是無效的,則可以通過添加新的約束來解決沖突。CBS分為兩個級別。在高層次上,發現了沖突并添加了約束。低層級為各個代理查找與新約束一致的路徑。接下來,我們將更詳細地描述此過程的每個部分。

4.2?。高水平

在以下部分中,我們將介紹CBS的高級過程及其搜索的搜索樹。

4.2.1?。約束樹

在較高級別,CBS搜索一棵稱為約束樹(CT)的。CT是二叉樹。CT中的每個節點N包括:

1。

一組約束(?。約束)。這些約束中的每一個都屬于一個代理。CT的根包含一組空約束。CT中節點的子節點繼承父節點的約束,并為一個代理添加一個新約束。

2。

解決方案(?。解)。一組k條路徑,每個代理一個路徑。代理之路一種一世?必須符合以下約束?一種一世。這些路徑是通過低級搜索找到的。

3。

總費用(?。成本(目前所有解決方案的總費用)。該成本稱為節點Nf值。

CT中的節點N是目標節點,當?。解是有效的,即所有代理的路徑集沒有沖突。高級別在CT上執行最佳優先搜索,其中CT節點按其成本排序。在我們的實現中,打破了聯系,而使用了關聯的解決方案包含較少沖突的CT節點。進一步的聯系以FIFO方式中斷。

4.2.2?。在CT中處理節點

給定CT節點N的約束列表,將調用低級搜索。低級搜索(下面將詳細介紹)為每個代理返回一條最短路徑,一種一世,這與與?一種一世在節點N中。一旦找到了每個代理的一致路徑(關于其自身的約束),就可以相對于其他代理驗證這些路徑。該驗證是通過所有的時間步長的迭代和匹配由所有代理保留的位置上進行。如果沒有兩個代理計劃同時位于同一位置,則將該CT節點N聲明為目標節點,并且當前解決方案(?。解)(包含此路徑集)將返回。但是,如果在執行驗證時發生沖突C=(一種一世,一種?,v,?)?找到兩個或更多代理商?一種一世?和?一種?,驗證暫停,并且該節點被聲明為非目標節點。

4.2.3?。解決沖突

給定非目標CT節點N,其解?。解包括沖突?C?=(一種一世,一種?,v,?)?我們知道,在任何有效的解決方案中,最多只有一個沖突的代理(一種一世?和?一種?)在時間t可能占據頂點v。因此,至少有一個約束(一種一世,v,?)?要么?(一種?,v,?)?必須添加到??。約束。為了保證最優性,檢查了兩種可能性,并將節點N分為兩個子節點。兩個孩子都從N繼承約束集。左孩子通過添加約束來解決沖突(一種一世,v,?)?合適的孩子增加了約束?(一種?,v,?)。

注意,對于給定的CT節點N,不必保存其所有累積約束。相反,它只能保存其最新約束,并通過其祖先遍歷從N到根的路徑來提取其他約束。同樣,除了根節點,低級搜索僅應針對代理執行一種一世與新添加的約束相關聯。其他代理的路徑保持不變,因為沒有為它們添加新的約束。

4.2.4?。的沖突?>2?代理商

在不同路徑之間執行驗證時,可能會發現k-agent沖突?>2。有兩種方法可以處理這種k代理沖突。我們可以生成k個子元素,每個子元素都對?-1個代理(即,每個孩子在時間t僅允許一個代理占據沖突的頂點v)?;蛘?,等效的形式化是僅關注發現沖突的前兩個代理,并且僅根據它們的沖突進行分支。這為樹的更深層次留下了進一步的沖突。這在圖3中示出。頂部的樹表示CT的一種變體,其中對于單個沖突,允許k向分支,其中包括k個代理,?=3。每個新的繼任者都添加?-1個(= 2)個新約束(除一個以外的所有代理)。底部的樹顯示了針對同一問題的二進制CT。請注意,底部中間狀態是重復狀態,如果不應用重復檢測,則此節點將出現兩次,而不是一次??梢钥闯?,兩棵樹中最深層的大小是相同的。兩種方法的復雜度相似,因為它們都將以k個節點結束,每個節點具有?-1個新的限制。為簡單起見,我們僅實現和描述了第二個選項。

Image removed.

  1. 下載:下載全圖

圖3。對于同一問題,(k??=??3)路分支CT(上)和二進制CT(下)。

4.2.5?。邊緣沖突

為簡單起見,我們僅描述了在頂點中發生的沖突。但是,如果根據問題定義,不允許代理以相反的方向越過相同的邊緣,則也會發生邊緣沖突。我們定義一個邊緣沖突為元組(一種一世,一種?,v1個,v2,?)?兩個代理商“交換”位置的位置(一種一世?從?v1個?至?v2?而?一種??從?v2?至?v1個)在時間步長t至時間步長之間?+1個。邊緣約束定義為(一種一世,v1個,v2,?),哪里代理?一種一世?禁止從邊緣開始沿邊緣移動?v1個?至?v2在時間步t(并達到v2?在時間步??+1個)。如果適用,邊緣沖突將以與頂點沖突相同的方式由高層處理。

4.2.6?。偽代碼和示例

算法2給出了CBS的偽代碼,以及稍后將在第8節中介紹的更高級的MA-CBS?。第11–18行僅與MA-CBS有關?,F在,假設應該合并()函數(第11行)始終返回false,跳過第11-18行。高級別具有最佳優先搜索的結構。

Image removed.

  1. 下載:下載全圖

算法2。高水平的CBS(和MA-CBS)。

我們使用圖1(第2.7節)中的示例描述CBS?,在此示例中,小鼠需要拿到各自的奶酪塊。對應的CT在圖4中示出。根包含一組空約束。在第2行中,低級別返回了每個代理的最佳解決方案,〈小號1個,一種1個,d,G1個〉?對于?一種1個?和?〈小號2,乙1個,d,G2〉?對于?一種2。因此,該節點的總成本為6。所有這些信息都保留在該節點內。然后將根插入OPEN,然后將其展開。

Image removed.

  1. 下載:下載全圖

圖4。約束樹(CT)的示例。

驗證由兩條單獨路徑給出的雙重代理解決方案(第7行)時,兩個代理在時間步驟2到達頂點D時都會發現沖突。這會產生沖突(一種1個,一種2,d,2)(第10行)。結果,根被聲明為非目標,并生成了兩個子節點以解決沖突(第19行)。左孩子,添加約束(一種1個,d,2)?而合適的孩子增加了約束?(一種2,d,2)?,F在為左孩子調用低級搜索(第23行),以找到一條也滿足新約束的最佳路徑。為了這,一種1個?必須在以下位置等待一個時間步長?一種1個?或?小號1個?和路徑?〈小號1個,一種1個,一種1個,d,G1個〉?返回?一種1個。的路徑一種2,?〈小號2,乙1個,d,G2〉左孩子保持不變?,F在,左子項的總成本為7。以類似的方式,生成了右子項,其成本也為7。兩個子項均插入OPEN(第26行)。在while循環的下一次迭代(第5行)中,選擇左子級進行擴展,并驗證基礎路徑。由于不存在沖突,因此將左子節點聲明為目標節點(第9行),并將其解決方案作為最佳解決方案返回。

4.3?。低級:查找CT節點的路徑

低級搜索被賦予一個代理,?一種一世,以及與?一種一世。它在基礎圖形中執行搜索以找到代理的最佳路徑一種一世在完全忽略其他代理的情況下滿足所有約束。低級搜索的搜索空間具有兩個維度:空間維度和時間維度。2可以使用任何單代理尋路算法來查找代理的路徑一種一世,同時驗證是否滿足約束條件。我們使用A *實施CBS的低級搜索,該搜索處理了以下約束。每當一個狀態(v,?)生成,其中v是位置,t是時間步長,并且存在約束(一種一世,v,?)在當前CT(高級別)節點中被丟棄。我們使用的啟發式方法是空間維度中最短的路徑,而忽略了其他代理和約束。

對于兩個低級A *狀態具有相同f值的情況,我們使用了基于Standley的平局決勝沖突避免表(CAT)的平局決勝策略(在3.3.4節中進行了介紹)。與其他代理數量較少的國家/地區應優先考慮。例如,如果狀態s1個=(v1個,?1個)?和?s2=(v2,?2)具有相同的f值,但是v1個?被其他兩個代理同時使用??1個?而?v2?當時未被任何其他代理使用??2, 然后?s2將首先擴展。與任意打破平局相比,該打破平局策略將總運行時間縮短了2倍。重復狀態檢測和修剪(DD)加快了底層過程的速度。與單代理尋路不同,低級狀態空間還包括時間維度和由約束引起的動態“障礙”。因此,如果兩個位置的兩個位置都被視為重復,一種一世?兩種狀態下的時間步長相同。

5?。理論分析

在本節中,我們討論CBS的理論方面。我們首先從CBS返回最佳解決方案的證明開始,然后再是完整性的證明。然后,我們將討論與其他算法相比時CBS的優缺點。本節中的所有索賠均采用成本總和成本函數。在第7節中討論了如何將這些索賠適用于其他成本函數。

5.1?。CBS的最優性

我們首先提供一些證明最優性的證明。

?

定義1

對于約束樹中的給定節點N,令簡歷(?)是滿足以下條件的所有解決方案的集合:(1)與N的約束集合一致,并且(2)也是有效的(即,無沖突)。

如果N不是目標節點,則N處的解決方案將不屬于簡歷(?)因為解決方案無效。例如,考慮根節點。根沒有約束因此簡歷(根)等于所有可能的有效解的集合。如果為根選擇的解決方案無效,因此不屬于簡歷(根),則不會將根聲明為目標。

?

定義2

我們說點?允許的解決方案p如果p∈簡歷(?)。

例如,CT的根具有一組空約束。任何有效的解決方案都滿足空約束集。因此,根節點允許所有有效的解決方案。

解決方案的成本?簡歷(?)是各個代理商費用的總和。讓minCost(簡歷(?))?是所有解決方案中的最低成本?簡歷(?)。如果是簡歷(?)=??然后?minCost(簡歷(?))=∞。

?

引理1

CT中節點N的成本是?minCost(簡歷(?))。

?

證明

以來??。成本是所有最佳一致單代理解決方案的總和,在所有一致解決方案中成本最低。相比之下,minCost(簡歷(?))在所有一致且有效的解決方案中成本最低。由于所有一致和有效解決方案的集合是所有一致解決方案的子集,因此必須?。成本≤minCost(簡歷(?))?!?/p>

?

引理2

對于每個有效解p,在?OPEN?中至少存在一個節點N,使得N允許p。

證明

通過對擴展周期的歸納:在基本情況下,OPEN僅包含沒有約束的根節點。因此,根節點允許所有有效的解決方案?,F在,假設在第一次一世-1個擴展。在擴展過程中,假設節點N被擴展。節點N的后繼者–?1個?和??2生成。令p為有效解。如果OPEN中的另一個節點允許p,我們就完成了。否則,假設pN允許。我們需要證明p必須由其至少一個后繼者允許。的新約束?1個?和??2共享相同的時間和位置,但限制了不同的特工。假設N所允許的解p有代理一種1個在約束的位置。代理商一種1個?只能限制在??1個?和??2,但不能同時使用兩者,因此這些節點之一必須允許p。因此,歸納成立?!?/p>

結果:在所有時間中的至少一個節點CT?OPEN?允許最優解(作為一種特殊情況引理2)。

?

定理1

CBS返回最佳解決方案。

證明

當節點中的目標?被選擇用于由高電平擴展,所有有效的解決方案是允許由至少一個節點從OPEN(引理2)。令p是一個有效的解決方案(含成本p。成本) 然后讓??(p)是該節點允許p在OPEN。讓?。成本是節點N的成本。?(p)。成本≤p。成本(引理1)。由于G是目標節點,G。成本是有效解決方案的成本。由于高級搜索根據那里的成本以最佳優先的方式探索節點,因此我們得到G。成本≤?(p)。成本≤p。成本?!?/p>

5.2?。CBS的完整性

CBS高層搜索的狀態空間是無限的,因為可以為無限數量的時間步添加約束。這就提出了完整性問題。CBS的完整性包括兩個主張:

聲明a:如果存在,CBS將返回解決方案。

要求b:?CBS將確定一個無法解決的問題。

現在我們將證明,要求a始終是正確的,而要求b需要獨立于CBS的測試。

5.2.1?。要求

?

定理2

對于每個成本C,都有數量有限的CT節點。

證明

假定一個CT節點?成本?。在時間步驟C之后,所有代理均位于其目標位置。因此,在時間步驟C之后不會發生沖突。由于約束是從沖突得出的,因此對于大于C的時間步長不會生成約束。由于每一個CT節點的成本是單調非減,所有的CT節點的前身?具有成本≤??。因此,N或其任何前任都不能為大于C的時間步長生成約束。由于此類約束的數量有限(最多??|V|?C?頂點約束和???|?|?C邊緣約束),也有有限數量的CT節點包含此類約束?!?/p>

?

定理3

如果存在,CBS將返回一個解決方案。

證明

CBS使用系統的最佳優先搜索,并且CT節點的成本單調不變。因此,對于每對成本XY,如果X<?然后CBS將在擴展成本Y的節點之前擴展所有具有成本X的節點。由于對于每種成本,都有有限數量的CT節點(定理2),因此必須在擴展有限數量的CT節點后找到最佳解決方案?!?/p>

5.2.2?。要求b

索賠b并不總是適用于CBS。例如,考慮圖5中提出的問題,其中兩個代理需要切換位置。CT將無限增長,增加越來越多的約束,永遠無法達成有效的解決方案。幸運的是,Yu和Rus?[57]最近提出了一種算法,該算法可以檢測給定MAPF實例是否可求解的天氣。在CBS之前運行其算法將滿足權利要求b,因為僅當實例可解決時才會調用CBS。

Image removed.

  1. 下載:下載全圖

圖5。無法解決的MAPF實例的示例。

5.3?。與其他算法的比較

本節將CBS和A *的工作進行了比較,這兩個工作都是為了使成本和功能最小化并且都使用SIC啟發式方法。假設我們對MAPF使用A *。令χ為具有以下項的(多主體)A *節點的集合?F<C?當使用SIC啟發式方法執行A *時。另外,讓X=|χ|。眾所周知,A *必須擴展χ中的所有節點才能保證最優性[11]。

在先前的工作中,我們分析了A *和ICTS的最壞情況行為[42]。在最壞的情況下,A *最多生成X×(b基礎)?節點。在最壞的情況下,ICTS最多搜索X×?Δ低層節點(其中Δ是成本最低的ICT目標節點的深度)。注意,ICTS訪問的低級節點是k代理MDD搜索空間中的狀態,與A *訪問的節點相似但不相同。有關更多詳細信息,請參見[42]。我們將討論限制在僅將CBS與A *進行比較,因為已經研究了A *和ICTS之間的關系[42]。令?為具有?成本<C??在CT中,讓??=|?|。作為由節點成本指導的最佳優先搜索,并且由于成本單調不變,CBS必須擴展?中的所有節點。我們限制自己給Y的上限。由于CT的分支因子為2,2d在最壞的情況下必須擴展節點,其中d是找到解的CT深度。在CT的每個節點上,恰好添加了一個約束。在最壞的情況下,將限制代理避免在解決方案的每個時間步中都避開每個頂點。所有座席合計的時間步驟總數為?C?。因此,CBS必須擴展的CT節點數Y的上限為?2|V|×C?。對于這些節點中的每個節點,最低級別都會被調用并最多擴展?|V|×C?(單個代理)每個時間步的狀態。讓?ˉ?是基礎圖中擴展的狀態數(低級狀態)。????ˉ=?(2|V|×C?×|V|×C?)。注意,我們計算了在擴展的高級節點內擴展的低級節點。如果我們也要考慮生成的高級節點,則應將其乘以2,因為每個擴展的CT節點都會生成2個新節點。同樣,在實踐中,Y和?ˉ?可以大大縮小。

CBS在CT中執行高級搜索,然后在基礎圖形中執行低級搜索,并擴展??ˉ低級狀態。因此,如果?ˉ?X,也就是說,如果在所有單代理搜索中擴展的狀態數量遠小于具有以下條件的(多代理)A *狀態的數量:??F<C?,則CBS的表現將優于A *,反之亦然。人們可能會對這一結果感到驚訝,這表明CBS可能考慮的狀態少于A *,因為已知A *是“最佳有效的”,因為A *僅擴展了尋找最佳解決方案所需的節點集。但是,只有將A *與搜索相同狀態空間,使用相同,一致,啟發式函數的另一個BFS進行比較,并且忽略具有相同狀態的平局決勝的影響時,A *的“最佳有效”屬性才成立f[11]。CBS搜索與傳統A *完全不同的狀態空間,因此可以比A *更好。

接下來我們展示一些特殊情況??ˉ?X?(瓶頸)和位置?X??ˉ(開放空間)。對于MAPF而言,總體趨勢似乎很典型,因為該領域的拓撲會極大地影響算法的行為。

5.3.1?。CBS表現優于A *(瓶頸)的示例

我們的圖1(第2.7節)示例演示了一種情況,其中?ˉ?X也就是說,CBS擴展的節點數少于A *的情況。如上所述,CBS總共生成三個CT節點(如第4.2.6節的圖4所示)。從根本上說,兩個代理都調用了低級。低層搜索為兩個代理(長度均為3)中的每一個找到一條最佳路徑,并為CT根擴展了總共8個低層狀態?,F在,在D發現沖突。生成兩個新的CT子節點。在左孩子中,低層級搜索代理的替代路徑一種1個在步驟2中沒有通過D。小號1個加上所有m個州一種1個,…,一種米?用擴展?F=3。然后,D和G1個?用擴展?F=4?搜索停止并返回路徑?〈小號1個,一種1個,一種1個,d,G1個〉。

因此,在左側的孩子總共?米+3節點被擴展。類似,米+3狀態會針對合適的孩子展開。將所有這些添加到從根開始擴展的8個狀態中,我們總共得到?ˉ=2米+14?低級狀態被擴展。

現在,考慮在2代理狀態空間中運行的A *。根 (小號1個,小號2) 具有?F=6。它產生米2?節點,所有形式?(一種一世,乙?)?對于?(1個≤一世,?≤米)。所有這些節點都用F=6?,F在,節點(一種1個,d)?與?F=7?展開(代理?一種1個?等待在?一種1個)。然后節點(d,G2)?和?(G1個,G2)展開并返回解決方案。因此,總A *擴大了X=米2+3節點。對于米≥5?這個比?2米+14因此,CBS將擴展更少的節點。A *必須擴展單代理路徑的笛卡爾積F=3。相比之下,CBS僅嘗試了兩條這樣的路徑來認識到成本6的解決方案無效。

此外,CBS每個(低級)節點的恒定時間比A *每個節點的恒定時間小得多,這有兩個原因:A *擴展多主體節點,而CBS擴展單主體狀態。其次,CBS維護的開放列表要小得多,因為單個代理搜索空間在輸入圖的大小上是線性的。相比之下,A *的開放列表處理的是多代理狀態空間,該空間呈指數增長。因此,在CBS中,從打開列表中插入和提取節點更快。CBS還直接在高層節點上產生開銷。每個非目標高層節點都需要驗證給定的解決方案并生成兩個后繼節點。與低層節點相比,高層節點的數量非常少。因此,高層的開銷可以忽略不計。

5.3.2?。A *表現優于CBS(開放空間)的示例

圖6展示了一種情況?ˉ?X而A *將勝過CBS。中間有一個空白區域(灰色),所有特工都必須越過該區域。對于每個代理,有四個長度為4的最佳路徑,因此起始狀態的SIC啟發式為8。但是,這些路徑的16種組合中的每一種在一個灰色單元格中都有沖突。所以,?C?=9因為一個特工必須至少等待一步才能??避免沖突。對于這個問題,A *將擴展5個節點F=8:?{(d2,C1個),(d3,C2),(d3,乙1個),(C2,乙1個),(C3,乙2)}?和3個節點?F=9?{(乙3,乙2),(一種3,乙3),(一種3,乙4)}?直到找到目標并擴展了總共8個節點。

Image removed.

  1. 下載:下載全圖

圖6。CBS效率極低的病理情況。

現在,考慮CBS。CBS將建立一個CT,如圖7所示。CT由5個成本為8的非目標CT節點和6個成本為9的目標CT節點(虛線框)組成。根CT節點將對每個代理執行低級搜索,總共進行8個低級擴展。除根節點外,每個非目標CT節點都將對單個代理進行低級搜索,以進行總共4個低級擴展。每個目標CT節點將擴展5個低層節點??傮w而言,CBS將擴大8+4?4+6?5=54?低層節點。

Image removed.

  1. 下載:下載全圖

圖7。對于CBS效率極低的病理病例的CT。

由于沖突樹在遇到的沖突數量中呈指數增長,因此,當一組座席緊密耦合時,即,當組中的座席之間內部沖突發生率很高時,CBS的行為將很差。

雖然很難預測算法在實際域中的性能,但以上觀察可以提供一些指導。如果存在更多瓶頸,則CBS將比基于A *的方法更具優勢,因為它將排除代理很快在瓶頸中發生沖突的f值,然后轉向繞過瓶頸的解決方案。如果有更多開放空間,A *將比CBS具有優勢,因為它將很快排除沖突的解決方案。接下來,我們顯示支持兩種情況的實驗結果。

6?。CBS實證評估

CBS以及本文介紹的其他算法都適用于MAPF問題的許多變體。接下來,我們描述用于經驗分析的MAPF變量和實驗設置。選擇該特定的MAPF變體和設置以符合先前的工作[42],[38],[39],[45],[46]。

6.1?。實驗性問題設定

在每個時間步驟,所有座席都可以同時執行移動或等待動作。我們的實現假設移動和等待都具有單位成本。我們還做出以下兩個假設:

1。

代理商永遠不會消失。即使一個代理達到了目標,它也會阻止其他代理通過它。

2。

僅當代理程序以后再也沒有離開目標時,以目標為目標的等待操作的成本為零。否則,它們將花費一。

另外,在我們的實驗環境中,允許試劑相互跟隨。即代理一種一世如果同時代理可以將xy移到y一種?也從y移到z。在[45],[42],[55],[13]之后,我們允許代理在循環鏈中互相跟隨。我們認為,此策略更適合表示多機器人場景,因為實際上機器人可以同時在一個圓圈內移動(沒有空白)。在卵石運動文獻[9]中,不允許順著鏈條運動是很普遍的,卵石一個接一個地運動,因此至少需要一個空白空間來啟動運動。邊緣沖突也被禁止。那是代理一種一世如果同時代理,則禁止從x移到y一種?從y移到x。我們的實現沒有在高層使用重復的檢測和修剪過程(DD),因為我們發現它的開銷很大,而改進卻可以忽略不計。另一方面,低級確實使用DD。

我們的實驗中使用的特定全局累積成本函數是2.4節中說明的成本總和函數。例如,如果需要代理商一種1個?和?一種2?2個和3個時間步驟分別達到其目標,則這兩個代理商的費用總和為?2+3=5。請注意,對于每個業務代表,要計算時間步長,直到到達目標的時間步長為止。一個達到目標但后來又被迫離開的代理商可能會導致總成本的急劇增加。為了解決這個問題,我們使用了EPEA *?[15]的相同機制,該機制根據它們的f值一次生成一個高級節點。

對于低級搜索的可允許啟發式方法,我們在所有實驗中均使用了SIC啟發式方法(請參閱第3.3.1節)。

6.2?。實驗結果

我們實施并嘗試了A *,EPEA *,?信息技術委員會+修剪(表示為ICTS)和CBS。對于ICTS,我們使用了所有三元組修剪?[42],已發現它非常有效。除ICTS之外,所有算法均基于SIC啟發式算法。ICTS使用了更高級的修剪功能,將來有可能將其應用于CBS和A *作為高級啟發式方法。盡管如此,沒有這種高級啟發式方法的CBS在許多情況下仍勝過ICTS。

6.2.1?。8×8?4聯電網

我們從?8×84連接的開放式網格,代理人數從3到21。我們將時間限制設置為5分鐘。如果算法無法在時限內解決實例,則會將其暫停并返回失敗。我們的目的是研究給定數量的代理程序不同算法的行為。當ID框架應用于k個代理(起始位置和目標位置是隨機的)時,所產生的有效代理數?′嘈雜,其差異很大。因此,對于本實驗,我們遵循[42]并根據ID框架創建了所有代理都依賴的問題實例。3在這種情況下?′≡??并且運行ID框架是多余的。

圖8顯示了成功率,即當代理程序數量增加時,在5分鐘內可以通過不同算法解決的實例百分比。在這些簡單的問題中,A *明顯較差,而CBS相對于其他方法而言則略占優勢。

Image removed.

  1. 下載:下載全圖

圖8。成功率與代理數量8??×??8網格的關系。

表1列出了生成的節點數和100多個實例的平均運行時間。對于CBS,報告了高級(hl)節點和低級(ll)狀態?!?NA”表示對于給定數量的代理,A *獲得的成功率小于80%(失敗的大于20%)的問題。計數列說明了所有算法在該時限內解決的實例數。僅針對那些實例顯示平均結果。與[42]類似,我們沒有報告ICTS變體的節點數量,因為該算法并非僅基于搜索。

表1。在8??×??8網格上生成節點并運行時間。

?′#生成的節點運行時間(毫秒)

計數一種*EPEA *CBS(hl)CBS(ll)一種*EPEA *信息技術委員會哥倫比亞廣播公司p值

31006401510490801個70.01

41003965252410482071個1個140.02

510021,85135512385395031個320.01

68992,3213945135437,39848200.09

7100不適用881173994不適用1520600.00

8100不適用2932668644不適用751001480.00

9100不適用1053136245,585不適用4447578790.01

1099不適用23723225111,571不適用1340315224290.02

1194不適用79238789321,704不適用8157731877120.44

1292不適用13,17812,980451,770不適用13,78719,00212,3630.36

1386不適用14,98915,803552,939不適用18,67628,38116,4810.50

1483不適用13,87221,068736,278不適用15,40735,80124,4410.14

1571不適用2296724,871826,725不適用33,56954,81830,5090.45

1664不適用26,80524,602822,771不適用41,36065,57834,2300.32

1749不適用25,61517,775562,575不適用42,38275,04025,6530.22

EPEA *和CBS的結果相對相似。為了研究它們之間差異的統計顯著性,我們對這兩種算法的運行時結果進行了配對t檢驗。所得的p值顯示在“ p-val”列中??梢钥闯?,對于較大的問題,算法之間差異的顯著性變?。ǜ遬值對應于較小的顯著性)。這是因為某些問題很難解決,而其他問題很容易并且可以快速解決。這一事實,加上MAPF的指數性質,導致運行時結果差異很大。顯然,純A *是最差的算法,而EPEA *是最強的A *變體。對于11個以上的座席,CBS比ICTS更快。請注意,盡管CBS生成的節點多于EPEA *,?′>14),因為低級CBS的每個節點的恒定時間(單代理狀態,小的打開列表)比EPEA *(多個代理,大的打開列表)要小得多。CBS的速度分別比EPEA *和ICTS快2倍和3倍。

6.2.2?。DAO地圖

我們還在《龍騰世紀:起源》?[47]游戲中測試了3張基準地圖。在這里,我們旨在展示評估算法的整體性能。與上面的結果不同,這里我們在每個評估算法的頂部執行ID。給不同的算法一個具有給定數量的k個代理的問題實例,其中開始和目標位置被統一隨機化。ID將這些問題分解為子問題,并分別在每個子問題上執行關聯的算法。我們僅顯示三種最強算法的結果:EPEA *,ICTS和CBS。

圖9(右)顯示了給定三個地圖的座席人數的成功率。在這里結果好壞參半,沒有全球冠軍??梢郧宄乜吹?,ICTS總是比EPEA *好。CBS在這些地圖上的性能支持了我們的理論主張,即CBS在處理走廊和瓶頸時非常有效,而在開放空間中效率很低。對于den520d(上),沒有瓶頸,但是有很大的開放空間;CBS排名第三。對于ost003d(中),幾乎沒有瓶頸和小的開放空間;在大多數情況下,CBS處于中間水平。最后,對于brc202b(底部),有許多狹窄的走廊和瓶頸,但只有很少的開放空間,因此CBS是最好的。請注意,雖然den520和ost003都有開放空間,但瓶頸數量有所不同。

Image removed.

  1. 下載:下載全圖

圖9。對于不同的DAO映射den520d(頂部),ost003d(中間),brc202d(底部),所有算法都在ID之上運行的不同算法的成功率。

圖10說明了CBS解決過程中遇到的沖突。發生沖突的單元格顯示為紅色。紅色的暗處對應于單元中發生的沖突數。深紅色表示更多沖突。如在開放空間(den520d,ost003d)中可以看到的,沖突蔓延并覆蓋了地圖的很大一部分。相比之下,在brc202d中,沖突集中在走廊和瓶頸處。這說明了開放空間如何引發更多沖突,因此不太適合CBS。

Image removed.

  1. 下載:下載全圖

圖10。DAO映射den520d(左),ost003d(中),brc202d(右)及其沖突的位置。

7?。使用不同成本函數的CBS

讓SoC表示第2.4節中定義的成本總和函數。到目前為止,我們一直專注于最小化SoC功能的任務。盡管如此,CBS仍可以歸納為以下其他成本函數。

7.1?。高水平

將CBS泛化為制造成本函數需要對高層進行一次更改-根據其相應解決方案的制造期而不是SoC計算CT節點的成本(算法2中的第24行,第4.2.6節)。更一般而言,讓Φ為將成本分配給MAPF解決方案的函數。找到最小化的解決方案Φ,我們修改CBS計算每CT節點,成本?,要Φ(?。解)。我們表示CBS的成本函數的執行Φ為哥倫比亞廣播公司Φ。

7.2?。低級

回想一下,每個高級節點N都有一個多代理解決方案,?。解。每個多主體解決方案均由k條單主體路徑組成。如上針對我們的成本函數(SoC)定義的低級求解器,將返回給定代理的單個代理路徑。從低級返回的單代理路徑必須保持最佳狀態Φ(?。解)最小。但是,可以針對給定的成本函數改善低電平。在低級搜索過程中,我們建議根據與其他特工遇到的最少沖突來打破關系。這可以使用上述沖突避免表(CAT)來完成。

7.3?。最優性

稍作修改,成本函數之和的最優性證明(見第5.1節)適用于哥倫比亞廣播公司Φ適用于各種成本函數。Φ被認為是允許的Φ(?)≤minCost(簡歷(?))對于每個CT節點?。

定理4

如果允許Φ,則?哥倫比亞廣播公司Φ?保證返回最佳解決方案。

證明

哥倫比亞廣播公司Φ根據Φ執行最佳優先搜索。根據定義,CT子樹中N以下的任何解決方案的成本都不能小于minCost(簡歷(?))。保證了由可接受的評估函數指導的BFS返回最優解[11]?!?/p>

SoC,makepan和燃料成本功能都是可以接受的,因為在后續CT節點中添加更多約束不能導致成本更低的解決方案。因此,根據定理4,哥倫比亞廣播公司Φ?將為所有這些成本函數返回最佳解決方案。

7.4?。完整性

5.2節中提供的完整性證明適用于任何成本函數Φ,只要根據Φ每給定成本存在有限數量的解決方案即可。此條件適用于沒有零成本操作的任何成本函數。SoC和makepan是此類功能的示例。另一方面,燃料成本函數不具有此屬性。對于燃料成本函數,可以有無數個具有給定成本的高級節點,因為等待動作不會花費任何成本。由于燃料成本函數不滿足上述條件,因此需要一種稍微不同的方法。Yu和Rus?[57]在他們的論文中建議,對于任何可解決的MAPF實例,最多不超過?(|V|3)所有代理商都必須達到單一代理商的步驟才能實現其目標。這個事實可以用于我們的需求,如下所述。對于每個節點N,如果片上系統(?)>|V|4,則可以安全地忽略該節點。解決方案大于|V|4(根據SoC)必須包含一個時間步,所有代理同時執行等待操作。在這種情況下,有一個更便宜的解決方案,其中刪除了此時間步驟。

8??;谠頉_突的搜索(MA-CBS)

現在我們來解釋一個稱為Ceta的通用框架,該框架稱為基于元代理沖突的搜索(MA-CBS)。首先,我們通過關注上述基本版本的CBS的行為來為MA-CBS提供動力。

8.1?。元代理CBS的動機

如前所述,CBS對于某些MAPF問題非常有效(與其他方法相比),而對其他問題則非常低效。先前已經討論了不同的MAPF算法在不同的環境或拓撲下表現不同的一般趨勢[42],[38],[39]。此外,給定域可能具有具有不同拓撲的不同區域。這就需要一種算法,該算法將根據確切的任務及其當前搜索的區域動態更改其策略。在理解地圖拓撲與MAPF算法性能之間的關系方面,還有大量的研究空間。MA-CBS是朝著動態適應算法邁出的第一步。

如上一節中所示,當一組特工緊密耦合時,即,當該組特工之間的內部沖突發生率很高時,CBS的表現較差。在這種情況下,基本CBS可能必須處理大量沖突才能產生最佳解決方案。MA-CBS通過自動識別強耦合代理集并將它們合并為元代理來糾正CBS的這種行為。然后,高級CBS繼續進行,但是從CBS角度來看,此元代理被視為單個代理。因此,MA-CBS的低級求解器必須是MAPF求解器,例如,一種*+外徑?[45],EPEA *?[15],M *?[51]。因此,MA-CBS實際上是可以在另一個MAPF求解器之上使用的框架。接下來,我們提供MA-CBS的技術細節。

8.2?。將代理合并為元代理

基本CBS和MA-CBS之間的主要區別是將代理合并為元代理的新操作。元代理由M個代理組成。因此,單個代理只是大小為1的元代理?;氐?a >算法2(第4.2.6節),我們介紹了在發現新沖突后立即發生的合并動作(第10行)。此時,MA-CBS有兩種選擇:

?

分支:在此選項中,我們根據新的沖突(第19–26行)分為兩個節點。這是基本CBS始終執行的選項。

?

合并:?MA-CBS還有另一個選擇,可以將兩個有沖突的(元)代理合并為一個元代理(第12-18行)。

合并過程如下。假設有k個代理的CT節點N。假設在代理之間發現了沖突一種1個?和?一種2,并且選擇了這兩個代理進行合并?,F在我們有?-1個其中包括一個新的大小為2的新元代理,標記為一種{1個,2}。此元代理將永遠不會在CT的N之下的子樹中再次分裂;但是,它可以與其他(元)代理合并以形成新的元代理。由于其他未合并的代理沒有任何變化,因此我們現在僅再次調用該新的元代理的低級搜索(第14行)。實際上,對大小為M的元代理進行低級搜索實際上是M個代理的最佳MAPF問題,應使用最佳MAPF求解器解決。注意,由于元代理的最優路徑可能大于這些代理中的每個代理的最優路徑之和,因此此CT節點的f成本可能會由于此合并動作而增加。因此,f重新計算并存儲此節點的值(第15行)。然后將該節點再次添加到OPEN中(第17行)。

MA-CBS具有兩個重要組件(除了CBS組件之外):決定選擇(分支或合并)選項的合并策略(第11行),以及用于定義對新元數據施加的約束的約束合并機制。?-agent(第13行)。必須設計此約束合并機制,以使MA-CBS仍能返回最佳解決方案。接下來,我們討論如何實現這兩個組件。

8.3?。合并政策

我們實施了以下合并政策。兩名特工一種一世,一種??被合并為元代理?一種{一世,?}?如果之間的沖突次數?一種一世?和?一種?在搜索過程中記錄超過一個參數。我們稱B沖突約束參數,并使用符號MA-CBS(B)表示邊界為B的MA-CBS?。請注意,基本CBS實際上是MA-CBS(∞)。也就是說,我們從不選擇合并并且總是根據沖突進行分支。

為了實現該面向沖突約束的合并策略,維護沖突矩陣CM。厘米[一世,?]?累積代理之間的沖突數量?一種一世?和?一種??到目前為止,MA-CBS可以看到。?厘米[一世,?]?每當之間發生新的沖突時,將增加1?一種一世?和?一種?找到(算法2,第4.2.6節,第10行)?,F在,如果厘米[一世,?]>乙?的?應該合并()?函數(第11行)返回true,?一種一世?和?一種??合并成?一種{一世,?}。如果兩個元代理之間發生沖突,一種1個?和?一種2,由于有兩個簡單的代理,?一種?∈一種1個?和?一種?∈一種2,?厘米[?,?]?增加1,并且?應該合并()?如果函數將返回true?∑厘米[X,?]>乙?總體?X∈一種1個,?∈一種2。此政策簡單有效。但是,其他合并策略也是可能的,并且可能會顯著提高速度。

為了說明MA-CBS,請再次考慮圖1所示的示例(第2.7節)。假設我們正在使用MA-CBS(0)。在這種情況下,一旦出現沖突,(一種1個,一種2,d,2)?被發現?應該合并()返回true,代理一種1個?和?一種2?合并到新的元代理中?一種{1個,2}。

接下來,調用低級求解器來求解新創建的元代理,并找到兩個代理的(無沖突)最佳路徑。如果使用A *,將為此執行2-agent A *?,F在,將高級節點重新插入OPEN,將其f值從8更新為9。由于它是OPEN中唯一的節點,因此接下來將對其進行擴展。在第二個擴展中,由于不存在沖突,因此搜索停止了–根據定義,只有一個meta-agent不包含任何沖突。因此,返回來自根節點的解決方案。相比之下,對于MA-CBS(B)乙>0根節點將根據上述第4.2.6節中所述的沖突進行拆分。

8.4?。合并約束

表示元代理?Xˉ。我們使用以下定義:

?

元約束的元代理Xˉ?是一個元組?(Xˉ,X?,v,?)?代理商的子集?X??Xˉ被禁止在時間步t占據頂點v。

?

同樣,元沖突就是元組(Xˉ,?ˉ,v,?)?個別代理商?X′∈Xˉ?和個人代理??′∈?ˉ兩者都在時間點t占據頂點v。

考慮與(元)代理相關的一組約束?一種一世?和?一種?合并之前。它們是由于代理之間的沖突而生成的。這些沖突(以及由此產生的約束)可以分為三類。

1。

內部:之間的沖突一種一世?和?一種?。

2。

external(i):之間的沖突一種一世?和其他代理商?一種??(哪里??≠?)。

3。

external(j):之間的沖突一種??和其他代理商?一種??(哪里??≠一世)。

以來?一種一世?和?一種??現在將要合并,不應將內部沖突視為?一種一世?和?一種?將通過低級耦合解決。因此,從那時起,我們僅考慮外部約束。

8.4.1?。合并外部約束

假設代理商?一種一世?和?一種??將合并到新的元代理中?一種{一世,?}?然后?一種一世?有外部約束?(一種一世,v,?)。這種限制意味著在CT的更遠處,一種一世?與其他特工有沖突?一種[R在時間t在位置v處,因此一種一世不允許在時間t處位于位置v。

新的元代理必須包括所有外部約束。假設一個外部約束(一種一世,v,?)。合并后一種一世?和?一種??此約束應僅適用于原始代理,?一種一世,并且不適用于整個meta-agent,即?{一種一世}∪{一種?}。因此,合并約束的形式為(一種{一世,?},一種一世,v,?)。這是在算法2(第4.2.6節)的第13行中完成的。

合并時?一種一世?和?一種??人們很想引入一個元約束?(一種{一世,?},{一種一世}∪{一種?},v,?)?兩位代理商?一種一世?和?一種?在時間t禁止進入位置v。但是,由于以下情況,這可能會破壞算法的最優性。假設一個3代理問題,在最佳解決方案代理中一種3必須在時間步t穿過頂點v。調用MA-CBS解決此問題將創建根CT節點。假設在為根CT節點中的每個代理選擇的路徑中,兩個代理一種1個?和?一種2在時間步長t被分配了頂點v。接下來,MA-CBS根據沖突分支(一種1個,一種2,v,?)。生成兩個新的CT節點{?1個,?2}。在?1個?(?2)代理?一種1個?(一種2)限制在時間tv。接下來,代理一種1個?(一種2)與代理合并?一種3?在節點??1個?(?2)。如果我們允許對代理商施加約束一種1個?和?一種2?申請代理?一種3?我們將在這兩個方面阻止最佳解決方案??1個?和??2?這是OPEN中僅有的兩個節點。

相比之下,假設有沖突?(Xˉ,?ˉ,v,?)?被檢測到之間?Xˉ?和??ˉ,在元代理之后?Xˉ已創建。沖突代理的確切身份X′∈Xˉ?和??′∈?ˉ是無關緊要的。對兩個元代理的約束應包括整個元代理,即(Xˉ,v,?)?或類似地??ˉ(算法2的第20行,第4.2.6節)。這樣做將保留完整性,因為所有可能的解決方案都存在于其中的所有代理中。Xˉ?要么??ˉ限制在時間t處于v處。

8.5?。低級求解器

底層查找給定代理的路徑。在使用元代理的情況下,底層需要解決由組成元代理的內部代理提供的MAPF實例。具有以下三個屬性的任何MAPF求解器都可以在低級別使用:

1。

完整性–如果一個解決方案存在,則求解器必須返回一個解決方案,否則必須返回false。

2。

約束處理–求解器絕不能返回違反約束的解決方案。

3。

最優性–求解器必須返回最優解。

許多已知的MAPF算法適用于低級MA-CBS,例如,?一種*+外徑?[45],EPEA *?[15],M *?[51]?;拘问降腎CTS?[42]和CBS不適合低層次的人員,因為它們無法檢測到無法解決的問題實例。在5.2節中,我們提出了一種通過應用檢測無法解決的MAPF實例的算法來解決此問題的方法[57]。但是,此方法不適用于傳遞給低級求解器的受約束MAPF實例。有趣的是,可以將合并邊界小于無窮大的MA-CBS配置為充當低級求解器,從而生成MA-CBS的遞歸結構。為避免MA-CBS求解器無限期調用另一個MA-CBS求解器的情況,將MA-CBS用作低級求解器需要增加連續遞歸調用之間的合并閾值。增加閾值的方式是一個深層次的問題,需要大量研究。

8.6?。MA-CBS的完整性和最優性

5.2節中提供的完整性證明也適用于MA-CBS。為了證明MA-CBS的最優性,我們將使用第5.1節中定義和證明的支持性聲明和引理。5.1節中的所有引理適用于MA-CBS案例。合并選項不會影響證明。唯一的例外是引理2,它說:“對于每個有效解p,至少存在一個節點N,使得N允許p?!?證明是通過對分支作用的歸納。但是,對于MA-CBS,擴展高級節點可能會導致合并代理而不是分支。因此,我們通過處理合并動作案例來完成證明。在這種情況下,節點N展開,執行合并操作,然后將節點N重新插入OPEN。中的任何有效解決方案VS(?)?必須保留在新的?VS(?)?擴展過程之后,因為沒有添加新的約束。

8.7?。MA-CBS作為連續體

如上所述,MA-CBS的極端情況(∞)等同于基本CBS?,F在我們注意到,另一個極端情況MA-CBS(0)等同于Standley?[45]引入的基本獨立性檢測機制(請參閱第3.3.3節)。在MA-CBS(0)中,一旦發生沖突,我們就會合并代理。在根節點中,MA-CBS(0)分別解決每個代理。然后,MA-CBS(0)展開CT根節點。驗證此節點時,會發現單個代理的解決方案之間存在沖突(如果存在)。沖突的代理將合并為乙=0。合并的組將使用低級MAPF求解器求解。接下來,將根重新插入OPEN并進行驗證。以來乙=0分支選項將永遠不會被選擇,并且沖突總是通過合并有沖突的(元)代理來解決。因此,此變體將僅具有一個CT節點,該節點將重新插入OPEN,合并發生沖突的代理,直到沒有沖突發生為止。這與ID的行為相同。

3.3.4節中介紹的增強ID版本嘗試通過重新計劃到其中一個沖突代理的路徑來解決沖突。這種重新計劃讓人想起MA-CBS(1),因為一旦發現沖突,我們將嘗試通過分支繞過它。如果發現更多沖突,則合并代理。

因此,MA-CBS(B)是一個連續體,具有這兩個先前算法作為極端情況。然而,MA-CBS()具有變化值可以顯著優于ID,當它解決了僅松耦合,通過分別添加約束到這些藥劑。例如,在瓶頸(例如圖1,第2.7節)中,個體的解決方案發生沖突時,ID(≡MA-CBS(0))會將這些個體合并為一個組,并在耦合的方式。相比之下,MA-CBS(B)(乙>0)可以通過向其中一個代理添加單個約束來避免此瓶頸。因此,使用MA-CBS(B)并選擇合適的乙≥0增加了更多的靈活性,并且可能大大勝過ID。在下面描述的實驗結果部分中可以清楚地看到這一點。

9?。MA-CBS實驗結果

在本節中,我們在游戲《龍騰世紀:起源》?[47]中的三個標準基準地圖上以經驗方式研究MA-CBS的行為?;叵胍幌?,再次在圖11中顯示的三個映射中的每個映射都表示不同的拓撲。地圖den520d(頂部)具有許多大的開放空間,沒有瓶頸,地圖ost003d(中部)具有一些開放空間和一些瓶頸,而地圖brc202d(底部)幾乎沒有開放空間和許多瓶頸。我們的主要目標是研究沖突綁定參數B對MA-CBS性能的影響。我們在實驗中使用MA-CBS(B)乙=0,1個,5,10,100,500和∞。由于MA-CBS是可以在任何基于A *的求解器之上運行的框架,因此我們嘗試了兩個這樣的求解器:A *和增強的部分擴展A *(EPEA *)[15]。兩個求解器都使用了SIC啟發式(如上定義)。選擇A *作為基準,而選擇EPEA *是因為它是當前基于A *的最先進的MAPF求解器。

Image removed.

  1. 下載:下載全圖

圖11。使用IDEA *作為低級求解器,MA-CBS在ID之上的成功率。

對于每張地圖,我們都改變了代理商人數k。我們針對k的每個值在100個隨機實例上運行算法。如果算法在五分鐘內沒有解決給定的問題實例,則將其暫停。報告的數字是所有能夠解決70%以上實例的算法所解決的所有實例的平均值。如果算法求解的結果少于70%,我們將其平均結果報告為下限(包括由于時間限制而導致求解器停止運行的情況)。這些情況在下表中用“>”表示。

表2表3顯示了上述實驗的運行時間(以毫秒為單位)。所述?欄表示的在實驗中的代理的數量。MA-CBS(x)由B(x)表示。對于給定數量的代理,最佳性能算法的結果以粗體顯示。表3顯示了使用A *進行低級搜索時的結果,而表2報告了使用EPEA *時的結果。表格中的每一幀都呈現不同的地圖。

表2。DAO問題的運行時間(毫秒)。EPEA *作為低級求解器。

?den520d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5899190180181180180256

1016331782470467469469632

151621224117081702171317381807

203393372515271515155315551867年

257675832717011620173120713264

3012,57413,30839553773527616,191> 38,707

3515,73612,65549744993719918,998> 50,050

4014,63515,45248604971768620,860> 50,891

?ost003d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5187231168168169169222

1017181983年764753757757935

154888459315971592156815701909年

2010,46313,42637013654362335984119

25> 60,140> 58,902> 28,88115,10918,15935,536> 73,860

30> 84,473> 80,248> 30,78125,86027,52546,328> 92,209

35> 90,703> 81,633> 39,66021,46628,24147,544> 95,262

?brc202d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

51834年235112861276126812671664

106034805945804530449845085495

1512,35415,38969036871682067938685

20> 70,003> 73,51135,09521,72919,84631,229> 43,625

表3。DAO問題的運行時間(毫秒)。A *作為低級求解器。

?den520d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5223273218220219222219

1010991458553552549552546

15118216201838年1810182917031672

20479243751996年2011年2020年1857年1708

25763314,74921932255232028883046

30> 62,717> 60,21480828055810780137745

35> 65,947> 51,81513,67013,58715,98128,274> 45,954

40> 81,487> 82,86018,4731839920,39131,189> 45,857

?ost003d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5470631220218220219222

10819216,2701006995981977935

15897115,67916401619162415511458

2029,50747,20432933234320830743000

25> 122,166> 125,417> 73,014> 53,48128,44338,422> 59,923

30> 162,290> 170,094> 63,963> 51,16729,91243,405> 69,681

?brc202d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5738212,20016821665年164016571664

1022,55439,34653725312526352265318

1547,82284,46088518746873687018681

20> 116,675> 159,039> 51,59224,01124,81731,069> 34,726

25> 197,268> 223,838> 146,301> 85,89163,16263,835> 66,178

結果清楚地表明,隨著問題變得越來越難(解決時間更長),具有非極值的MA-CBS,即?乙≠0?和?乙≠∞,比MA-CBS(0)(ID)和MA-CBS(∞)(基本CBS)能夠更快地解決大多數實例。新的變體在MA-CBS(∞)上達到了一個數量級的加速(例如,在使用EPEA *作為低級求解器的35和40個代理的den520d中),在MA-CBS上達到了4倍。 (0)(例如,在具有25個代理的ost003d中)。

接下來,考慮增加使用EPEA *的den520d圖的代理數k的效果(表2第一幀)。代理很少的實例(?<25)可使用具有大B值的MA-CBS更快地解決。隨著問題變得越來越嚴重(?>30)B值較小的MA-CBS速度更快。此外,相對于最佳變體,基本CBS(∞MA-CBS(∞))和MA-CBS(500)的相對性能下降。解釋如下。在密集的問題實例中,相對于地圖大小有許多代理,會發生許多沖突?;叵胍幌?,基本的CBS在遇到的沖突數量上是指數級的。因此,與具有較小B值的變體相比,增加代理數量會降低具有較大B值(其行為更接近于基本CBS)的MA-CBS的相對性能。在極端情況下的單獨實驗(此處未報告)中,?=|V|-1個,我們觀察到MA-CBS(0)表現最佳。

現在,考慮將A *用作低級求解器的結果(表3)。在這里,我們看到了與EPEA *結果相同的總體趨勢。但是,B的最佳性能值大于帶有EPEA *的MA-CBS(表2)。例如,在具有30個代理的den520d映射中,以A *作為低級求解器的MA-CBS(5)并未獲得比CBS明顯的加速。對于EPEA *作為低級求解器,MA-CBS(5)比CBS獲得了數量級的加速。在其他地圖中也可以觀察到相同的趨勢。原因是對于相對較弱的MAPF求解器(例如A *),求解大量代理是非常低效的。因此,我們希望避免合并代理并以更分離的方式運行。對于這些情況,更高B是優選的。另一方面,使用速度更快的MAPF求解器(例如EPEA *),較低的B值將表現更好。在MA-CBS(∞)中,永遠不會為元代理調用低級別(僅對于單個代理)。因此,以低水平運行A *或EPEA *不會有任何區別。運行時的差異是由于考慮了一組不同的問題造成的。對于B(5),EPEA *比A *可以解決更多問題(較難的問題)。由于這些問題在表1中得到了解決,因此運行時結果要比表2更高。

圖11顯示了具有以下條件的MA-CBS的成功率,即超時之前解決的實例數:乙=0,1個,10,100和∞。低層求解器設置為EPEA *,因此乙=0用EPEA *表示。另外,為了進行比較,我們還報告了最佳ICTS變體的成功率[42]。請注意,圖例是根據給定地圖中的性能排序的。

可以看出,在所有具有中間值的MA-CBS實驗中,?0<乙<∞,與EPEA *(* MA-CBS(0))和基本CBS(≡MA-CBS(∞))兩種極端情況相比,它能夠解決更多實例。此外,具有中間值的MA-CBS也優于ICTS求解器??紤]MA-CBS變體的性能乙<∞?與基本CBS相比(乙=∞)?;綜BS在den520d(頂部)中的性能非常差,在ost003d(中部)的性能中有些差,而在brc202d(底部)的性能則很差。這是因為在沒有瓶頸和較大開放空間的地圖(例如den520d)中,CBS效率低下,因為在許多不同位置都會發生許多沖突。在圖6中給出的CBS病理示例中對此現象進行了解釋(第5.3.2節))。因此,由于避免了很多沖突,因此在den520d中合并代理程序的好處很高。相比之下,對于沒有較大開放空間和許多瓶頸的地圖(例如brc202d),CBS遇到的沖突很少,因此合并代理僅會減少很小的沖突。實際上,如結果所示,對于brc202d,基本CBS(MA-CBS(∞))的性能幾乎與設置B的較低值相同。

通常,在沖突率較高的問題中,合并代理會更有幫助,因此B的值越低越好。B-CBS(10)的成功率最高,例如den520d(上)。相比之下,B-CBS(100)在ost003d和brc202d中獲得了最高的成功率。

9.1?。實驗結論

實驗清楚地表明,沒有普遍的贏家。每個已知算法的性能在很大程度上取決于問題特征,例如:密度,地圖拓撲,初始啟發式錯誤以及CBS解決過程中遇到的沖突數量。尚不完全了解這些不同功能與每種算法的性能之間的關系,這是我們將來打算研究的重點。同時,我們正在嘗試提出新功能,以在搜索之前評估每種算法的性能。但是,我們提出了以下觀察到的一般趨勢:

?

具有中間B值的MA-CBS(0<乙<∞)優于以前的算法A *,EPEA *和CBS。在大多數情況下,它也勝過ICTS。

?

密度。在具有許多代理的密集地圖中,較低的B值更為有效。

?

拓撲結構。在開放空間較大且瓶頸很少的地圖中,較低的B值更為有效。

?

低級求解器。如果將弱MAPF求解器(例如,純A *)用于低級搜索,則B的高值是首選。

10???偨Y,結論和未來工作

在本文中,我們處理了多智能體尋路問題(MAPF)。我們提供了關于MAPF問題的先前工作的簡短調查,并引入了一個分類,該分類有助于將所有先前的工作歸為以下幾類:

1。

最佳求解器[45],[15],[42],[38],[39]

2。

基于次優搜索的求解器[43],[12]

3。

基于次優過程的求解器[9],[30],[25],[37],[10]

4。

次優混合求解器[52],[24],[53],[35]

接下來,介紹了CBS算法。CBS是一種新穎的最佳MAPF求解器。CBS的獨特之處在于,所有低級別搜索都作為單代理搜索執行,但它可以產生最佳解決方案。CBS的性能取決于問題的結構。我們已經證明了CBS表現良好的瓶頸(圖1,第2.7節)和CBS表現較差的開放空間(圖6,第5.3.2節)的情況。我們分析并解釋了這些情況以及它們如何影響CBS的績效。

然后,我們轉向介紹MA-CBS框架,這是CBS算法的概括。MA-CBS可以在任何MAPF求解器的頂部使用,它將用作低級求解器。此外,MA-CBS可以看作是Standley?[45]引入的獨立檢測(ID)框架的概括。

MA-CBS充當CBS與其他最佳MAPF求解器(例如A *,?一種*+外徑?[45]和EPEA *?[15]。它從常規CBS求解器開始,其中一次由單個代理執行低級搜索。如果MA-CBS識別出一對座席經常發生沖突,則將它們分組在一起。低級求解器將此組視為一個復合代理,并使用給定的MAPF求解器(例如A *)找到該組的解決方案。因此,MA-CBS具有靈活性,并且可以通過選擇何時將座席分組在一起來享受CBS和傳統最佳求解器的互補優勢。作為一種簡單而有效的機制,在決定要組業務,我們介紹了沖突的約束參數。的參數對應于MA-CBS的傾向來創建的代理大基團和解決它們作為一個單元。什么時候乙=0?MA-CBS收斂到ID,何時收斂?乙=∞MA-CBS等效于CBS。設置0<乙<∞提供了MA-CBS的靈活性,因此,在僅發生少量沖突的情況下,MA-CBS可以像CBS一樣工作,而如果沖突很普遍,則MA-CBS可以收斂到一個包含所有或大部分沖突的元代理問題代理商。試驗臺地圖問題的實驗結果支持了我們的理論主張。呈現的域具有不同的開放空間和瓶頸率。在走廊和瓶頸更為主要的情況下,具有高B值(100、500)的MA-CBS優于其他算法。此外,實驗結果表明,MA-CBS的B非極值(即乙=0?也不?乙=∞)的性能優于CBS和其他最新的MAPF算法。結果得出結論,在一般情況下,在一定程度上對代理進行分組最有利。與從不對代理進行分組(如在CBS中)和對所有代理進行分組(如在所有先前的最佳求解器中)相比,這導致更快的求解過程。

總體上,關于MAPF以及CBS和MA-CBS算法的工作面臨許多公開挑戰:

1。

當前,沒有啟發式方法可指導高級約束樹中的搜索。提出允許的高級別啟發法可能會導致顯著提高速度。

2。

可以做進一步的工作來了解B參數對MA-CBS的影響,這可以深入了解B如何動態變化。

3。

使用單個B參數合并代理相對簡單。一個開放的問題是否是更復雜的合并策略是否可以顯著提高性能。例如,合并可能基于地圖區域而不是單個代理。

4。

繼費納等。[17]有必要進行實驗和比較不同的低層求解器,包括ICTS?[42],ODrM *?[17],布爾可滿足性(SAT)[50],整數線性規劃(ILP)[55]和答案集編程(ASP)[13]。

5,

在更大的范圍內,約束的使用與CSP和SAT的工作重疊,這種聯系尚未得到很好的探索。這些領域之間存在理論聯系[33],需要進一步研究。

致謝

這項研究是由支持以色列科學基金會(ISF)撥款305/09至阿里爾Felner。

附錄A?。內存受限的CBS

最近提出的許多最佳MAPF求解器都需要指數級的內存。對于A *變型,內存用于存儲OPEN和CLOSED。對于ICTS,內存用于ICT。兩者都是指數的(Δ中的ICTS和k中的A *變體)。在沒有換位的域中,可以通過運行迭代加深A *(IDA *)輕松解決此內存問題[26]。但是,IDA *的效率會因為遇到更多重復節點而大大降低。在地圖和網格等領域(MAPF最常見的領域)中,重復節點非常頻繁。例如,在4個連接的網格中,距給定位置半徑r處的唯一狀態數為?([R2)?但是路徑數是??(4[R)。因此,所有先前的最佳MAPF求解器都占用大量內存。接下來,我們描述如何將MA-CBS修改為需要內存大小的有效最優求解器??(??C??|V|),即代理商數量k的乘積,即最佳解決方案費用的費用,?C??以及輸入圖的大小?|V|。

與A *及其變體不同,CBS搜索概念上不同的狀態空間–約束空間。但是,在此空間中也可能會遇到重復狀態。圖12顯示了MAPF實例(左)和具有重復狀態的對應CT(右)。在此問題中,存在三個代理。每個都有一個起始位置,小號一世,以及目標位置,?G一世。CT的根無限制,并且為代理找到了解決方案(一種1個,?一種2,?一種3)是?{〈小號1個,一種,G1個〉,〈小號2,一種,G2〉,〈小號3,乙,G3〉}。根包含沖突(一種1個,一種2,一種,1個)?和一個新的CT節點??1個?用約束創建?(一種1個,一種,1個)。??1個?包含沖突?(一種1個,一種3,乙,1個)。因此,另一個CT節點?2?用約束創建?(一種2,一種,1個)?但它包含了沖突?(一種2,一種3,乙,1個)。接下來,CT節點?1個?展開,創建CT節點??3?有約束?(一種1個,一種,1個),?(一種3,乙,1個)。然后,CT節點?2?擴展生成CT節點??4?有約束?(一種2,一種,1個),?(一種3,乙,1個)。CT節點?3?創建CT節點??5?有約束?(一種1個,一種,1個),?(一種3,乙,1個),?(一種2,一種,1個)。CT節點?4?創建CT節點??6?有約束?(一種2,一種,1個),?(一種3,乙,1個),?(一種1個,一種,1個)??梢钥闯鯟T節點?5?和??6?包含相同的約束集,因此是重復的。

Image removed.

  1. 下載:下載全圖

圖12。CBS具有周期的MAPF實例示例。

即使上面的示例證明約束樹中可能存在重復項,但實際上在4個連接的網格上,我們遇到的重復項很少。我們使用重復檢測機制運行了本文報道的所有實驗。由于有少量重復數據,有和沒有重復檢測的結果在所有參數上幾乎相同。因此,我們嘗試使用迭代加深作為高級搜索算法。迭代加深是深度優先搜索,需要深度與解決方案深度成線性關系。與作為高級求解器的最佳優先搜索相比,迭代加深的平均運行時間高出約12%。

A.1?。具有許多重復狀態的域

盡管4連通網格幾乎沒有重復狀態,但其他域(例如隨機圖)可能包含許多重復狀態。對于這些域,DFID作為高級求解器將效率低下。為了解決這個問題,我們開發了一種新的CT分支技術,它將完全防止重復。在CBS中,當發生沖突時(一種1個,一種2,v,?)?發現在添加約束的同時將節點拆分為兩個子節點?(一種1個,v,?)?一個孩子?(一種2,v,?)在另一個孩子。對于內存高效型,我們定義了一個新約束(一種一世,v,?ˉ)?這意味著那個代理?一種一世?在時間步t必須位于位置v?,F在,當沖突(一種1個,一種2,v,?)被發現產生了三個孩子。第一個孩子添加約束{(一種1個,v,?),(一種2,v,?ˉ)},即?一種1個在時間t不能位于v中,但是一種2?必須在時間t處在v處。第二個增加了約束{(一種2,v,?),(一種1個,v,?ˉ)},即?一種2在時間t不能位于v中,但是一種1個?必須在時間t處在v處。第三個孩子增加了約束{(一種1個,v,?),(一種2,v,?)},即兩者都不?一種1個?也不?一種2允許在時間t處在v中。

這種機制可防止重復發生的可能性,同時仍保持最佳性和完整性。對于包含許多重復項的受內存限制的環境和域,我們建議將此格式與DFID一起用作高級CT搜索算法。

參考文獻

[1]

麻仁?Bennewitz?,鎢?Burgard?,塞巴斯蒂安·?史朗為移動機器人團隊的去耦路徑規劃技術找到并優化可解決的優先級方案

機器人。自動。Syst。,41?(2?)(2002?),第89?-?99

文章下載PDF查看Scopus中的記錄谷歌學術

[2]

Subhrajit?Bhattacharya?,Vijay?Kumar?,Maxim?Likhachev成對約束的分布式優化及其在多機器人路徑規劃中的應用

機器人:科學和系統(2010?),第87?-?94

查看Scopus中的記錄谷歌學術

[3]

Subhrajit?查亞,美心?利哈喬夫,維杰?·庫馬爾基于搜索的機器人路徑規劃中的拓撲約束

自動。機器人,33?(3?)(2012?),第273?-?290

交叉引用查看Scopus中的記錄谷歌學術

[4]

Zahy?Bnaya和Ariel?Felner面向沖突的窗口式分層合作社A *

國際機器人與自動化會議(ICRA)(2014?)

谷歌學術

[5]

Zahy?Bnaya?,Roni?Stern?,Ariel?Felner?,Roie?Zivan?,Steven?Okamoto自利代理的多代理路徑查找

組合搜索(SOCS)研討會(2013?)

谷歌學術

[6]

Blai?Bonet的,??送?Geffner規劃啟發式搜索

Artif。智力?,129?(1?)(2001?),第5?-?33

文章下載PDF查看Scopus中的記錄谷歌學術

[7]

喬希?石塔,大衛·?馬爾茲,戴維·?約翰遜,弘毅春?虎,Jorjeta?Jetcheva多跳無線自組織網絡路由協議的性能比較

在移動計算和網絡國際會議論文集,ACM?(1998年),第85?-?97

交叉引用查看Scopus中的記錄谷歌學術

[8]

本杰明·?科恩,薩欽?Chitta?,馬克西姆?利哈喬夫具有啟發式搜索的單臂和雙臂運動計劃

詮釋?J.機器人。Res。(2013年)

谷歌學術

[9]

保羅·?斯皮拉基斯(Paul?Spirakis),丹尼爾·科恩豪斯(Daniel?Kornhauser),加里·?米勒協調圖上的卵石運動,排列組的直徑和應用

研討會計算機科學基礎,IEEE?(1984?),第241?-?250

谷歌學術

[10]

鮑里斯·?德·王爾德,阿德里安·W·?之三MORS?,塞斯·?維特芬推動和旋轉:協作式多智能體路徑規劃

AAMAS?(2013?),第87?-?94

查看Scopus中的記錄谷歌學術

[11]

麗娜?Dechter?,猶太?珍珠廣義最佳優先搜索策略和A *的最優性

J. ACM?,32?(3?)(1985?),第505?-?536

查看Scopus中的記錄谷歌學術

[12]

庫爾特M.?Dresner?,彼得·?斯通多主體自治路口管理方法

J.Artif。智力?Res。,31?(2008?),第591?-?656

查看Scopus中的記錄谷歌學術

[13]

ESRA?埃德姆,多加G.?克薩,了Umut?Oztok?,彼得·?舒萊爾解決多主體問題的通用形式框架

AAAI?(2013?)

谷歌學術

[14]

邁克爾·?埃德曼(Tom?Lozano-Perez)在多個運動物體上

Algorithmica?,2?(1-4?)(1987?),第477?-?521

交叉引用查看Scopus中的記錄谷歌學術

[15]

Ariel?Felner?,Meir?Goldenberg?,Guni?Sharon?,Roni?Stern?,Tal?Beja?,Nathan?R.Sturtevant?,Jonathan?Schaeffer?,Robert?Holte具有選擇性節點生成的部分擴展A *

AAAI?(2012?)

谷歌學術

[16]

阿里爾?Felner?,羅尼?斯特恩,沙立?克勞斯,亞薩?奔亞伊爾,彌敦道S.?內塔尼亞胡PHA *:在未知的物理環境中找到具有A *的最短路徑

J.Artif。智力?Res。,21?(2004年),第631?-?670

交叉引用查看Scopus中的記錄谷歌學術

[17]

Cornelia?Ferner?,Glenn?Wagner?,Howie?Choset低維搜索空間中的ODrM *最優多機器人路徑規劃

國際會議機器人與自動化(ICRA)?(2013?),第3854?-?3859

交叉引用查看Scopus中的記錄谷歌學術

[18]

嫩?吉爾博亞,阿姆農?Meisels?,林依晨?Felner未知物理環境中的分布式導航

AAMAS?,ACM?(2006年),第553?-?560

交叉引用查看Scopus中的記錄谷歌學術

[19]

梅爾?·戈登伯格,阿里爾·?費爾納,羅尼?·斯特恩,喬納森·?舍弗A *變體可實現最佳的多智能體尋路

組合搜索(SOCS)研討會(2012?)

谷歌學術

[20]

梅厄?登堡,阿里爾?Felner?,羅尼?斯特恩,尼?沙龍,彌敦道R.?斯特蒂文特,羅伯特·?霍爾特,喬納森·?謝弗增強的局部擴展A *

J.Artif。智力?Res。,50?(2014?),第141?-?187

交叉引用查看Scopus中的記錄谷歌學術

[21]

德文K.?格雷迪,科斯塔斯E.?Bekris?,莉迪亞E.?Kavraki二階動力學下具有安全保證的異步分布式運動計劃

機器人IX的算法基礎,施普林格(2011?),第53?-?70

谷歌學術

[22]

彼得·?哈特(Peter?E.Hart),尼爾斯·?尼爾森(Nils?J.Nilsson),貝特拉姆?·拉斐爾(Bertram?Raphael)啟發式確定最小成本路徑的正式基礎

Syst??茖W?賽伯恩。,4?(2?)(1968?),第100?-?107

交叉引用查看Scopus中的記錄谷歌學術

[23]

馬爾特·?赫爾默特了解計劃任務:領域復雜性和啟發式分解

卷?4929?,施普林格(2008?)

谷歌學術

[24]

蕾妮?詹森,彌敦道R.?斯特蒂文特協作尋路的新方法

AAMAS?(2008年),第1401?-?1404中

查看Scopus中的記錄谷歌學術

[25]

穆赫塔爾M.?Khorshid?,羅伯特·?霍爾特,彌敦道R.?斯特蒂文特非最優多智能體尋路的多項式時間算法

組合搜索(SOCS)研討會(2011?)

谷歌學術

[26]

理查德·?科夫深度優先迭代加深:最佳可允許樹搜索

Artif。智力?,27?(1?)(1985?),第97?-?109

文章下載PDF查看Scopus中的記錄谷歌學術

[27]

理查德·?科夫使用模式數據庫找到魔方的最佳解決方案

AAAI / IAAI?(1997年),第700?-?705

查看Scopus中的記錄谷歌學術

[28]

理查德·?科夫(Richard?E.Korf),拉里·?泰勒(Larry?A.Taylor)尋找二十四個難題的最佳解決方案

AAAI?(1996年),第1202?-?1207

查看Scopus中的記錄谷歌學術

[29]

史蒂文·?拉瓦勒(Steven?M.LaValle),賽斯·?哈欽森(Seth?A.Hutchinson)具有獨立目標的多個機器人的最佳運動計劃

機器人。自動?,14?(6?)(1998?),第912?-?925

查看Scopus中的記錄谷歌學術

[30]

瑞安?月神,科斯塔斯·E.?Bekris高效,完整的集中式多機器人路徑規劃

《智能機器人與系統(IROS)(2011?)》,第3268至3275頁

查看Scopus中的記錄谷歌學術

[31]

露西婭·帕洛蒂諾(Lucia?Pallottino),文森佐(Vincenzo?Giovanni Scordio),安東尼奧·比基(Antonio?Bicchi),埃米利奧·弗拉佐利(Emilio?Frazzoli)多車系統中解決沖突的分散合作策略

機器人學,23?(6?)(2007?),第1170至1183頁

交叉引用查看Scopus中的記錄谷歌學術

[32]

麥克·?皮斯古德(Mike?Peasgood),約翰·?麥克菲(John?McPhee),克里斯托弗·?克拉克(Christopher?M.Clark)隧道環境中完整且可擴展的多機器人規劃

計算?科學?軟。。(2006?),p。75

查看Scopus中的記錄谷歌學術

[33]

朱西·?林塔寧(Jussi?Rintanen)使用SAT進行規劃,可允許的啟發式方法和A *

IJCAI?(2011?),頁。到2015年-到2020年

查看Scopus中的記錄谷歌學術

[34]

加布里埃爾·?勒格(GabrieleR?ger),馬爾特·?赫爾默特(Malte?Helmert)解決了非最優的多智能體尋路(自1984年)

組合搜索(SOCS)研討會(2012?)

谷歌學術

[35]

馬爾科姆RK?瑞安在多機器人路徑規劃中利用子圖結構

J.Artif。智力?Res。,31?(2008?),第497?-?542

查看Scopus中的記錄谷歌學術

[36]

馬爾科姆RK?瑞安基于約束的多機器人路徑規劃

國際會議機器人與自動化(ICRA)?(2010?),第922?-?928

查看Scopus中的記錄谷歌學術

[37]

Qandeel?Sajid?,Ryan?Luna?,Kostas?E.Bekris同時執行單代理原語的多代理尋路

組合搜索(SOCS)研討會(2012?)

谷歌學術

[38]

尼?沙龍,羅尼?斯特恩,阿里爾?Felner?,彌敦道R.?斯特蒂文特基于沖突的搜索,以實現最佳的多智能體路徑查找

AAAI?(2012?)

谷歌學術

[39]

尼?沙龍,羅尼?斯特恩,阿里爾?Felner?,彌敦道R.?斯特蒂文特基于元代理沖突的搜索,用于最佳多代理路徑查找

組合搜索(SOCS)研討會(2012?)

谷歌學術

[40]

尼?沙龍,羅尼?斯特恩,梅厄?登堡,林依晨?Felner成本增加樹搜索以實現最佳多智能體尋路

IJCAI?(2011?),第662?-?667

查看Scopus中的記錄谷歌學術

[41]

尼?沙龍,羅尼?斯特恩,梅厄?登堡,林依晨?Felner用于增加成本樹搜索的修剪技術,以實現最佳多智能體尋路

組合搜索(SOCS)研討會(2011?)

谷歌學術

[42]

尼?沙龍,羅尼?斯特恩,梅厄?登堡,林依晨?Felner成本增加樹搜索以實現最佳多智能體尋路

Artif。智力?,195?(2013?),第470?-?495

文章下載PDF查看Scopus中的記錄谷歌學術

[43]

戴維·?西爾弗合作尋路

人工智能和互動數字娛樂(AIIDE)?(2005年),第117?-?122

查看Scopus中的記錄谷歌學術

[44]

Arvind?Srinivasan?,Timothy?Ham?,Sharad?Malik?,Robert?K.Brayton離散函數操縱的算法

計算機國際會議計算機輔助設計(ICCAD)?(1990年),第92?-?95

查看Scopus中的記錄谷歌學術

[45]

特雷弗·?斯坦德利尋找合作尋路問題的最佳解決方案

AAAI?(2010?)

冯仰妍破处门