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

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

0 引言

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

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

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

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

1 問題描述和算法簡(jiǎn)介

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

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

(1)

1.2 CBS算法

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

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

1.3 ICBS算法

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

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

2 沖突分類與消解算法

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

2.1 沖突分類

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

2.1.1 相向頂點(diǎn)沖突

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

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

圖1 相向頂點(diǎn)沖突案例Fig.1 A case of the opposite vertex conflict

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

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

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

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

2)沖突=(,,,,,)是關(guān)鍵沖突；

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

2.1.2 交叉頂點(diǎn)沖突

圖3 交叉頂點(diǎn)沖突案例Fig.3 A case of the intersect vertex conflict

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

2.2 沖突消解

2.2.1 相向頂點(diǎn)沖突消解方案

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

1)檢測(cè)沖突并判斷其為相向頂點(diǎn)沖突=(,,,,,)。

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

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

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

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

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

表1 相向頂點(diǎn)沖突案例算法指標(biāo)對(duì)比

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

2.2.2 交叉頂點(diǎn)沖突消解方案

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

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

交叉頂點(diǎn)沖突的消解方案描述如下：

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

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

表2 交叉頂點(diǎn)沖突案例算法指標(biāo)對(duì)比

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與仿真

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

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

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

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

圖8 ICBS-DC和Ant-PP路徑代價(jià)對(duì)比Fig.8 Path costs of ICBS-DC and Ant-PP algorithms

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

圖10 三種算法運(yùn)行時(shí)間對(duì)比Fig.10 Run times of three algorithms

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

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

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

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

4 結(jié)論

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

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