基于沖突分類與消解的多智能體路徑規(guī)劃算法設計

王 東，于連波，曹品釗，連 捷

(1.大連理工大學工業(yè)裝備智能控制與優(yōu)化教育部重點實驗室，大連 116024；2.大連理工大學控制科學與工程學院，大連 116024)

0 引言

多智能體路徑規(guī)劃問題是在已知的環(huán)境地圖中，為一組智能體規(guī)劃從各自的起始點到相應目標點的無沖突路徑，并實現(xiàn)路徑代價總和最小或者最大完工時間最小等優(yōu)化目標。多智能體路徑規(guī)劃已經(jīng)廣泛應用于各個領域，包括自主倉庫管理、多智能體運動規(guī)劃和無人機集群避障等。多智能體路徑規(guī)劃問題的求解困難程度遠大于多個單智能體路徑規(guī)劃問題的疊加，兩者的本質(zhì)區(qū)別是多智能體路徑規(guī)劃問題是在規(guī)劃單個智能體路徑的同時消解智能體間的路徑?jīng)_突。消解沖突是多智能體路徑規(guī)劃問題的關鍵。

目前主流的一類多智能體路徑規(guī)劃方法為：先分別規(guī)劃單個智能體的最優(yōu)路徑，然后再消解多智能體之間的路徑?jīng)_突。沖突消解方案主要有優(yōu)先級規(guī)劃法、基于行為的避碰方法、分層地圖法以及交通規(guī)則法等。這些沖突消解方案簡單易行，能夠有效消解多智能體間的路徑?jīng)_突。但上述方案多會犧牲路徑長度或智能體運行時間，難以保證多智能體路徑規(guī)劃方案的最優(yōu)性。

基于沖突搜索(Conflict-Based Search，CBS)的算法是一種經(jīng)典的多智能體路徑規(guī)劃方法，因其具有最優(yōu)性和完備性兩大優(yōu)點近年來受到廣泛研究。CBS是一種兩層搜索算法，算法高層用于找到多個智能體之間的沖突，算法低層將多智能體路徑規(guī)劃問題視為多個單智能體在滿足約束下的路徑規(guī)劃。CBS在大地圖和智能體耦合度不高的情況下具有較高的求解效率。文獻[13]提高了CBS算法的速度，但求得的解只能保證次優(yōu)性。E.Boyarski等提出了改進的基于沖突搜索算法(Improved Conflict-Based Se-arch，ICBS)，將路徑?jīng)_突分為關鍵沖突、半關鍵沖突和非關鍵沖突，并對沖突的消解順序進行優(yōu)化。ICBS算法保留了標準CBS算法的最優(yōu)性和完備性，該算法中使用多值決策圖對沖突類型進行判斷，計算量較大。A.Felner等在關鍵沖突的基礎上，設計了帶有啟發(fā)值的代價函數(shù)，減少算法中節(jié)點的擴展數(shù)量，從而降低算法的計算量。J.Li等規(guī)定了一種新的沖突類型，即在網(wǎng)格地圖內(nèi)的某些沖突將必然發(fā)生在一個矩形，并提出了相應的檢測和消解方法。上述算法多是在CBS的高層進行改進，文獻[17]在標準CBS的低層使用了增量式路徑規(guī)劃算法，從智能體的路徑重規(guī)劃方面減少了算法的計算量。

本文設計了一種基于沖突分類與消解的多智能體路徑規(guī)劃算法，以解決多智能體路徑規(guī)劃及路徑?jīng)_突問題。本文在ICBS算法的基礎上，做出以下改進：首先，將多智能體路徑中出現(xiàn)的關鍵沖突類別進一步分類出方向沖突，方向沖突包括相向沖突和交叉沖突；然后，提出方向沖突中相向沖突和交叉沖突的消解方式；最后，提出ICBS高層節(jié)點中的沖突搜索算法。本文算法保留了CBS算法的最優(yōu)性和完備性，并通過新提出的沖突分類及消解方式，減少了ICBS算法高層中約束樹的規(guī)模，從而減少算法在高層中搜索的時間，一定程度上降低了算法的計算量。

1 問題描述和算法簡介

1.1 多智能體路徑規(guī)劃問題模型

多智能體路徑規(guī)劃問題包括一個給定的無向無權圖=(,)和多個智能體={,,…,}。無向無權圖=(,)中，是圖中頂點的集合，是圖中頂點間連接邊的集合。任意一個智能體∈，擁有唯一的起始頂點∈和目標頂點∈。在多智能體路徑規(guī)劃問題中，時間被離散化為時刻序列={0,1,2…}，在任意一個時刻智能體在當前頂點等待或者移動到相鄰頂點，移動和等待兩種動作都需要單位代價。智能體的路徑被描述為一個從時間序列到頂點集合映射的序列={(0),(1),…,(),…,()}，其中()表示智能體在時刻占用的頂點，表示路徑的長度，路徑重規(guī)劃后,的值會隨著路徑的變化而變化。本文假設智能體保持勻速運行，使用表示智能體的路徑代價。智能體路徑間不能發(fā)生沖突是多智能體路徑規(guī)劃問題的重要約束條件。沖突約束具體描述為：1)任意兩個智能體和不能在同一時刻占用同一個頂點，即()≠(),?,∈∧≠；2)任意兩個智能體和不能在時刻和+1時刻間交換彼此占用的頂點，即()≠(+1)∨(+1)≠(),?,∈∧≠。多智能體路徑規(guī)劃任務是為智能體={,,…,}規(guī)劃一組從起始頂點到目標頂點的無沖突路徑={,,…,}，同時實現(xiàn)路徑代價總和最小的優(yōu)化目標，其中優(yōu)化目標形式化可表示為

(1)

1.2 CBS算法

CBS算法是解決多智能體路徑規(guī)劃問題的重要算法之一。CBS算法擁有兩層結構，其中低層用于規(guī)劃多個單智能體的最優(yōu)路徑，高層用于解決多個智能體之間存在的路徑?jīng)_突。CBS算法引入了約束和沖突的概念，約束用一個元組(,,)表示，表示禁止智能體在時刻占用元素，可以是一個頂點或者是一個邊，如果表示一個頂點，則該約束表示不允許在時刻占用該頂點，進一步可以表示為(,,)；如果是一條邊(,)，則表示禁止在時刻到+1時刻采取的動作占用該邊，進一步可以表示為(,,,)。沖突用一個元組(,,,)表示，表示智能體和在時刻同時占用元素；相應地，沖突可以分為頂點沖突和邊沖突，分別表示為(,,,)和(,,,,)。

在CBS算法的高層構建一個二叉結構的約束樹，約束樹中的每個節(jié)點包括約束、解和代價三部分。約束樹中根節(jié)點的約束為空集，每個節(jié)點從父節(jié)點中繼承約束。高層搜索每次從優(yōu)先級隊列OPEN中選取代價值最低的節(jié)點進行擴展，若當前節(jié)點的解是一組無沖突路徑，則將當前節(jié)點作為目標節(jié)點，并將該節(jié)點的解作為問題的解；否則，針對當前節(jié)點中的路徑?jīng)_突，分別添加約束擴展出左右子節(jié)點，并添加到OPEN中，重復擴展和添加OPEN中的節(jié)點，直到得到具有無沖突解的目標節(jié)點。CBS算法低層規(guī)劃單個智能體滿足約束的最優(yōu)路徑，即為高層節(jié)點提供解。低層的單智能體路徑規(guī)劃使用任何路徑規(guī)劃算法理論上都可滿足CBS的需求，本文使用A算法。CBS算法對于優(yōu)化路徑而言代價是最優(yōu)的，證明可見文獻[12]。

1.3 ICBS算法

CBS算法高層隨機選擇沖突進行節(jié)點擴展，但不恰當?shù)倪x擇會增加約束樹的規(guī)模，從而增加算法的運行時間。ICBS通過兩項改進改善了約束樹節(jié)點規(guī)模較大的問題。不同于CBS算法的隨機選擇沖突進行節(jié)點擴展，ICBS算法將沖突進行優(yōu)先級劃分，分為關鍵沖突、半關鍵沖突和非關鍵沖突。CBS算法對關鍵沖突拆分出的兩個子節(jié)點的代價值均大于當前節(jié)點的代價值，對半關鍵沖突拆分出的兩個子節(jié)點中有且僅有一個子節(jié)點的代價值大于當前節(jié)點的代價值，對非關鍵沖突拆分出的兩個子節(jié)點的代價值均不大于當前節(jié)點的代價值。通過優(yōu)先解決關鍵沖突和半關鍵沖突，最后是非關鍵沖突，在一定程度上加快了算法求解速度。在遇到關鍵沖突時，ICBS和CBS一樣以拆分出該節(jié)點的左右子節(jié)點的方式來解決，在消解半關鍵沖突或非關鍵沖突時不直接將該節(jié)點進行拆分，而是試圖通過尋找有效的繞路使沖突得到解決。因此，在ICBS算法中，高層節(jié)點中除了CBS算法中包含的約束、解和代價三部分以外，還包括該節(jié)點中存在沖突個數(shù)。

CBS算法及其改進算法側重消解多智能體間的路徑?jīng)_突，通過智能體間中心互聯(lián)式的通信拓撲結構由算法高層直接進行沖突檢測。該類算法注重規(guī)劃滿足約束的無沖突路徑的最優(yōu)性，即路徑長度最短。文獻[18-19]中的適航性、使用Bezier曲線處理單個智能體路徑的平滑性等，本文算法暫不進行研究。

2 沖突分類與消解算法

CBS算法和ICBS算法能夠為多智能體路徑規(guī)劃問題求解出最優(yōu)解，但算法單獨地處理當前沖突，沒有考慮當前沖突的處理與后續(xù)路徑或其他路徑?jīng)_突的關系。本章基于當前沖突處理對后續(xù)沖突的影響以及優(yōu)先處理關鍵沖突對其他路徑?jīng)_突的影響，對路徑?jīng)_突進行更加詳細的分類并提出相應沖突消解方案。

2.1 沖突分類

在四連通二維柵格地圖中，現(xiàn)有的CBS算法消解關鍵頂點沖突的最佳方案是某一個智能體在沖突發(fā)生時刻前進行等待。該方案在消解當前沖突的同時，對于某些特殊類型的關鍵頂點沖突可能會引起一個新的可預見的沖突，而該新發(fā)生的沖突是完全可以避免的。關鍵沖突具有優(yōu)先消解權限，智能體在沖突發(fā)生前的任意一個時刻等待，均能夠消解關鍵頂點沖突。選擇合適的等待時刻，能夠在消解當前關鍵頂點沖突的同時消解其他的半關鍵沖突或非關鍵沖突。根據(jù)上述分析，本文在ICBS算法的基礎上，根據(jù)發(fā)生沖突的兩個智能體的運行方向，將關鍵頂點沖突進一步分為相向頂點沖突和交叉頂點沖突。本文將沖突定義為={,}，其中=(,,,)表示傳統(tǒng)CBS算法中定義的沖突，={,}用于描述沖突類型，表示優(yōu)先級沖突類型，表示方向沖突類型。

2.1.1 相向頂點沖突

頂點沖突(,,,)中，若智能體和的運行方向完全相反，即智能體和通過沖突頂點后交換占用的頂點，則在本文中該類沖突被定義為相向頂點沖突。通過等待的方式消解該類沖突后，必然會引發(fā)一個新的邊沖突。下面以圖1所示的案例及圖2中對應的約束樹直觀展示相向頂點沖突。

圖1中，智能體從起始頂點出發(fā)去往目標頂點，智能體從起始頂點出發(fā)去往目標頂點。使用CBS算法及ICBS算法為智能體和智能體規(guī)劃路徑，分別為智能體初始規(guī)劃最優(yōu)路徑={,,,}，為智能體初始規(guī)劃最優(yōu)路徑={,,,}。智能體和智能體在1時刻共同占用頂點，發(fā)生沖突=(,,,1)；在0時刻智能體占用頂點，智能體占用頂點；在2時刻智能體占用頂點，智能體占用頂點，即智能體和智能體在沖突發(fā)生的前后時刻交換彼此占用的頂點。

圖1 相向頂點沖突案例Fig.1 A case of the opposite vertex conflict

圖2 相向頂點沖突案例的約束樹Fig.2 A constraint tree of the opposite vertex conflict case

從圖2所示約束樹的角度來看，依據(jù)初始化路徑構建約束樹的根節(jié)點后,檢測到根節(jié)點中存在頂點沖突=(,,,1)，如圖2根節(jié)點中紅色邊框標注所示。為消解頂點沖突，添加約束(,,1)和(,,1)拆分根節(jié)點，擴展出左右子節(jié)點和。雖然子節(jié)點和不存在頂點沖突=(,,,1)，但兩個子節(jié)點中都產(chǎn)生了新的邊沖突=(,,,1)或′=(,,,,1)。為消解該沖突必須再一次進行添加約束和擴展節(jié)點的操作，如圖2中由節(jié)點和擴展出節(jié)點、、和所示。

本文將圖1和圖2展示的在沖突時刻前后交換彼此占用的頂點，并且無法通過一次節(jié)點擴展而消解的特殊頂點沖突稱為相向頂點沖突=(,,,,,)，表示智能體和在時刻共同占用頂點，在-1時刻和+1時刻交換占用頂點和，下面給出相向頂點沖突的定義。如果一個沖突滿足以下條件，那么稱其為相向頂點沖突：

1)沖突=(,,,,,)中智能體和將在時刻同時占用頂點，即沖突為頂點沖突；

2)沖突=(,,,,,)是關鍵沖突；

3)沖突=(,,,,,)中智能體和將交換彼此在-1時刻和+1時刻占用頂點和，即智能體將在+1時刻占用智能體在-1時刻占用的頂點，并且智能體將在+1時刻占用智能體在-1時刻占用的頂點。

2.1.2 交叉頂點沖突

圖3 交叉頂點沖突案例Fig.3 A case of the intersect vertex conflict

下面給出交叉頂點沖突的定義，如果一個沖突滿足以下條件，那么稱其為交叉頂點沖突：

2.2 沖突消解

2.2.1 相向頂點沖突消解方案

消解相向頂點沖突=(,,,,,)時，若采用CBS算法或者其改進算法,則首先針對其中的頂點沖突(,,,)添加一個頂點約束(,,)(或(,,))進行一次節(jié)點擴展，然后對隨之產(chǎn)生的邊沖突(,,,,)(或(,,,,))添加約束(,(,),)(或(,(,),))進行第二次的節(jié)點擴展。簡言之，CBS算法及其改進算法至少需要進行兩次連續(xù)的節(jié)點擴展才能將相向頂點沖突完全消解，如圖2所示。本文消解相向頂點沖突的主要思想是提前為沖突整體添加一個約束，僅進行一次節(jié)點擴展便可完全消解相向頂點沖突。具體步驟描述為：

1)檢測沖突并判斷其為相向頂點沖突=(,,,,,)。

2)針對相向頂點沖突=(,,,,,)，直接分別添加4個組合約束(,,,)、(,,,)、(,;,,,)和(,;,,,)拆分相向頂點沖突所在的節(jié)點，擴展出4個子節(jié)點。其中，組合約束(,,,)表示智能體在時刻不得占用頂點和；組合約束(,,,)表示智能體在時刻不得占用頂點和；組合約束(,;,,,)表示智能體在時刻不得占用頂點，并且智能體在時刻不得占用頂點和；組合約束(,;,,,)表示智能體在時刻不得占用頂點，并且智能體在時刻不得占用頂點和。

3)新生成的子節(jié)點分別調(diào)用低層路徑規(guī)劃算法，得到消解相向頂點沖突后的路徑。

下面以圖1中的案例具體展示相向頂點沖突的消解方案。約束樹根節(jié)點的構建與ICBS算法相同。檢測沖突，進一步判斷出其為相向頂點沖突=(,,,,,1)，如圖4中節(jié)點的紅色邊框標注部分。對沖突現(xiàn)有的頂點沖突和下一步必然會發(fā)生的邊沖突直接整體添加兩頂點約束(,,,1)和(,,,1)以拆分根節(jié)點，擴展出左右子節(jié)點，分別如圖4中的′和′所示。圖4明確展現(xiàn)出經(jīng)過上述一次節(jié)點擴展，即可將相向頂點沖突完全消解。

圖4 相向頂點沖突案例的本文方案約束樹Fig.4 A constraint tree of the designed scheme for the opppsite vertex conflict case

對比圖2和圖4可知，本文設計的沖突消解方案與ICBS算法所求目標節(jié)點的路徑代價值相同，并且本文設計方案的約束樹節(jié)點擴展數(shù)量小于ICBS算法。表1在算法的高層擴展節(jié)點數(shù)、高層生產(chǎn)節(jié)點數(shù)以及低層算法調(diào)用次數(shù)方面具體展示本文設計方案的優(yōu)勢。

表1 相向頂點沖突案例算法指標對比

對于相向頂點沖突=(,,,,,)，CBS算法及其改進算法至少需要兩次連續(xù)的節(jié)點擴展才能完全消解沖突。本文設計方案僅需一次節(jié)點擴展便能完全消解沖突。本文設計方案在路徑代價方面與ICBS算法具有相同的最優(yōu)性，并且對計算量要求較低，能夠減小算法搜索空間規(guī)模和算法搜索時間。

2.2.2 交叉頂點沖突消解方案

圖5 交叉頂點沖突案例的約束樹Fig.5 A constraint tree for the intersect vertex conflict case

本文設計了針對交叉頂點沖突的消解方案，選擇合適的智能體，讓其在恰當?shù)却龝r刻進行等待，保證在消解當前交叉頂點沖突的同時消解其他半關鍵沖突或者非關鍵沖突，進而減小算法搜索空間以及算法搜索時間。

交叉頂點沖突的消解方案描述如下：

圖6 交叉頂點沖突案例的本文方案約束樹Fig.6 A constraint tree of the designed scheme for the intersect vertex conflict case

對比圖5和圖6可知,本文設計的交叉頂點沖突消解方案與ICBS算法所求目標節(jié)點的路徑代價值相同，并且本文設計方案的約束樹節(jié)點擴展數(shù)量小于ICBS算法。表2在算法的高層擴展節(jié)點數(shù)、高層生成節(jié)點數(shù)以及低層算法調(diào)用次數(shù)方面具體展示本文設計方案的優(yōu)勢。

表2 交叉頂點沖突案例算法指標對比

2.3 基于沖突分類與消解的多智能體路徑規(guī)劃算法

綜合本文提出的相向頂點沖突和交叉頂點沖突分類與消解方案，根據(jù)CBS算法及其改進算法，現(xiàn)給出基于沖突分類與消解的多智能體路徑規(guī)劃算法，如算法1所示。輸入一個多智能體路徑規(guī)劃實例后，首先用低層A算法分別為每個智能體規(guī)劃最優(yōu)路徑并計算路徑代價，進而構建出根節(jié)點，將根節(jié)點插入到OPEN列表，如算法第1～2行所示。第3～14行是算法檢測沖突和添加約束消解沖突的主體部分。第5行調(diào)用搜索高層節(jié)點中的沖突算法檢測沖突，并根據(jù)本文給出的相向頂點沖突和交叉頂點沖突分類判斷沖突類型，具體見算法2。第9～13行根據(jù)本文所提的方向沖突添加不同的約束進行沖突消解，其中第9、10行是相向頂點沖突的檢測與約束添加，第11、12行是交叉頂點沖突的檢測與約束添加，第13行生成新的子節(jié)點，具體見算法3。算法1最終為輸入的多智能體路徑規(guī)劃實例輸出一組無沖突最優(yōu)路徑。

算法2展示了高層節(jié)點沖突檢測與類型判斷方案，檢測本文所提的方向沖突并將沖突返回給算法1。算法2中增加了半關鍵和非關鍵沖突列表以及智能體沖突表。半關鍵和非關鍵沖突列表分別保存各智能體發(fā)生的半關鍵和非關鍵沖突，智能體沖突表保存各智能體的等待時刻，為消解交叉頂點沖突提供相應信息。

算法1:基于改進沖突搜索的沖突分類與消解算法輸入:一個多智能體路徑規(guī)劃實例輸出:該實例的一個最優(yōu)解1調(diào)用低層A*算法為每個智能體規(guī)劃初始最優(yōu)路徑2生成根節(jié)點R,并將其放入OPEN列表3while OPEN列表非空時 then4 從OPEN中取出代價值最低的節(jié)點,作為當前節(jié)點N5 調(diào)用搜索高層節(jié)點中的沖突算法檢測沖突6 if節(jié)點N中沒有沖突且不是關鍵沖突then7 調(diào)用低層A*算法重規(guī)劃繞行路徑8 else節(jié)點N中存在沖突且是關鍵沖突then9 if相向頂點沖突then10 添加組合約束11 else交叉頂點沖突then12 添加約束并確定智能體等待時刻13 生成子節(jié)點N'并將其放入OPEN列表14節(jié)點N中沒有沖突15返回路徑規(guī)劃的解

算法2:搜索高層節(jié)點中的沖突算法輸入:一個約束樹中的節(jié)點N的解輸出:節(jié)點N中存在的沖突C1for智能體中的任意一個組合對(ai,aj)then2 if智能體ai和aj間存在沖突C then3 if沖突C是關鍵沖突then4 判斷相向頂點沖突或交叉頂點沖突5 返回 C6 else if沖突C是半關鍵沖突then7 將C放入半關鍵沖突列表8 else then9 將C放入非關鍵沖突列表10 更新智能體沖突表11 返回第一個半關鍵或非關鍵沖突

算法3展示了用約束集合生成新的子節(jié)點的算法，和ICBS算法不同之處在于添加的約束是本文設計的針對沖突類型消解方案的組合約束。

算法3:生成新的子節(jié)點輸入:一個約束樹中的節(jié)點N和對智能體添加的約束輸出:生成的新的子節(jié)點1將對智能體添加的約束加入到節(jié)點N原有的約束2調(diào)用低層路徑規(guī)劃算法更新智能體路徑3生成新的子節(jié)點N'

3 實驗與仿真

本章進行對比實驗，以驗證本文設計算法求解多智能體路徑規(guī)劃問題的優(yōu)越性。首先，本文設計的基于沖突分類與消解的多智能體路徑規(guī)劃算法(ICBS-DC)與采用優(yōu)先級方法消解路徑?jīng)_突、使用蟻群算法規(guī)劃智能體路徑的多智能體路徑規(guī)劃方法(Ant-PP)相比，展現(xiàn)出求解結果質(zhì)量的優(yōu)越性，即求解結果路徑代價方面的優(yōu)越性。然后，將本文算法與CBS算法以及ICBS算法進行對比，體現(xiàn)本文算法在計算量方面的優(yōu)勢。本章所有實驗的代碼均采用Python編寫，均在參數(shù)為2.3GHz Intel Core i5-6300HQ 8GB RAM的筆記本電腦上進行。使用大小為8×8的四連通二位柵格地圖，其中障礙物占比為地圖大小的20%，在每次實驗中障礙物均隨機生成。對比實驗中智能體數(shù)量從1到15逐個增加，并且在每個智能體數(shù)量下隨機生成100個多智能體路徑規(guī)劃案例，取各項實驗數(shù)據(jù)的平均值作為最終數(shù)據(jù)。

圖7和圖8分別展示了本文ICBS-DC算法和使用優(yōu)先級的Ant-PP算法的成功率與路徑規(guī)劃方案的路徑代價。其中，成功率采用文獻[12]中描述的在5min時間限制內(nèi),算法能夠求解出結果的案例數(shù)量與案例總數(shù)量的比值。由圖7和圖8可知，本文的ICBS-DC算法的成功率與路徑規(guī)劃方案的路徑代價均優(yōu)于Ant-PP算法，并且隨著智能體數(shù)量的增加，ICBS-DC算法的優(yōu)勢越加明顯。

為了驗證本文算法在計算量方面的優(yōu)勢，將本文ICBS-DC算法與CBS及ICBS進行對比實驗，分別比較三種算法的成功率、運行時間、高層約束樹節(jié)點擴展數(shù)量以及低層路徑規(guī)劃算法平均調(diào)用的次數(shù)，結果如圖9～圖12所示。

圖7 ICBS-DC和Ant-PP成功率對比Fig.7 Success rates of ICBS-DC and Ant-PP algorithms

圖8 ICBS-DC和Ant-PP路徑代價對比Fig.8 Path costs of ICBS-DC and Ant-PP algorithms

圖9 三種算法成功率對比Fig.9 Success rates of three algorithms

圖10 三種算法運行時間對比Fig.10 Run times of three algorithms

圖11 三種算法節(jié)點擴展數(shù)量對比Fig.11 Number of extension nodes of three algorithms

圖12 三種算法調(diào)用低層路徑規(guī)劃次數(shù)對比Fig.12 Number of calls for low-level of three algorithms

當智能體數(shù)量較少時，各個智能體的路徑之間發(fā)生沖突的可能性較小，由圖9～圖12所示結果可以看出，三種算法在成功率、平均運行時間、高層約束樹節(jié)點擴展數(shù)量和低層路徑規(guī)劃算法調(diào)用的次數(shù)等方面幾乎具有相當?shù)男阅?。當智能體數(shù)量較多時，各智能體的路徑在環(huán)境中發(fā)生更多的沖突，由圖9報告的結果可知，CBS算法在智能體數(shù)量較多時，其解決多智能體路徑規(guī)劃問題的成功率下降速度最快，其次是ICBS。ICBS-DC相比CBS和ICBS而言，在智能體密度較大的情況下具有更高的成功率。而就圖10報告的平均運行時間而言，ICBS-DC運行速度雖然比CBS快，但相較于ICBS在某些情況下速度稍慢，然而隨著智能體數(shù)量的不斷增加，智能體的路徑之間沖突的可能性增加，ICBS-DC算法的平均運行時間的增長速度與CBS和ICBS相比較為平緩，說明ICBS-DC在智能體比較密集的環(huán)境下展現(xiàn)出更好的運行時間優(yōu)勢。

由圖11和圖12展現(xiàn)的高層和低層的指標來看，ICBS-DC在高層約束樹節(jié)點擴展數(shù)量及低層路徑規(guī)劃次數(shù)方面均少于CBS和ICBS，但這正是ICBS-DC在一些情況下耗時增加和平均運行時間增長速度稍慢的原因。ICBS-DC為了能使高層約束樹節(jié)點擴展的數(shù)量減少，在算法2中對產(chǎn)生的關鍵沖突再判斷其是否屬于本文提出的方向沖突，并在算法1中對沖突進行捕捉。當環(huán)境中產(chǎn)生的關鍵沖突較多時，判斷方向沖突又在一定程度上增加了運行時間。圖11和圖12報告的結果符合ICBS-DC的主要目的：一方面減少了高層約束樹節(jié)點擴展數(shù)量，使得約束樹的規(guī)模減??；另一方面使得低層路徑規(guī)劃調(diào)用次數(shù)減少。因為算法高層每生成一個節(jié)點就會給相應智能體添加約束，調(diào)用低層路徑規(guī)劃算法對該智能體進行重新規(guī)劃，所以圖11和圖12具有相似的曲線走勢。當高層約束樹中節(jié)點數(shù)量不是很多時，ICBS算法的運行速度與ICBS-DC相當，甚至在一些情況下要快于ICBS-DC；但當智能體數(shù)量較多時，使用本文所提的沖突消解方案可以有效對約束樹的規(guī)模進行限制，從而減小高層算法的搜索時間，這與圖10中報告的ICBS-DC的平均運行時間在智能體數(shù)量大于12時增長速度相比ICBS較為緩慢是一致的，說明ICBS-DC在智能體密集的環(huán)境下能展現(xiàn)出更好的求解速度優(yōu)勢。

4 結論

本文設計了一種基于沖突分類與消解的多智能體路徑規(guī)劃算法，以解決多智能體路徑規(guī)劃中的路徑?jīng)_突問題。本文將多智能體路徑?jīng)_突中的關鍵沖突進一步分類出相向頂點沖突和交叉頂點沖突，并針對這兩類沖突類型提出相應的消解方案：1)相向頂點沖突的消解方案以添加兩點約束的方式，避免了在消解該類沖突的過程中引發(fā)的新沖突，減少算法高層約束樹節(jié)點擴展數(shù)量，減小約束樹規(guī)模，降低算法運行時間；2)交叉頂點沖突的消解方案通過選擇恰當?shù)闹悄荏w等待時刻，在消解該類沖突的同時消解其他沖突，提高算法的搜索效率。最后通過仿真實驗驗證了本文提出的沖突分類與消解方案能夠為多智能體路徑規(guī)劃問題求解出路徑代價最優(yōu)的解，并且能夠有效減少算法高層約束樹節(jié)點的數(shù)量以及低層路徑規(guī)劃算法的調(diào)用次數(shù)，進而加快算法的求解速度。

未來的研究工作包括以下兩點：1)本文算法是基于四連通二維柵格地圖設計的，未來考慮將本文算法擴展到三維空間的其他類型地圖；2)在二維及三維環(huán)境中進行實物實驗，驗證本文算法的有效性。