多智能體路徑規(guī)劃研究進展

劉慶周,吳 鋒

(中國科學技術(shù)大學 計算機科學與技術(shù)學院,合肥 230027)

0 概述

多智能體路徑規(guī)劃(Multi-Agent Path Planning,MAPP)問題是一類尋找多個智能體從起始位置到目標位置且無沖突的最優(yōu)路徑集合的問題,其在機場拖航[1]、物流倉儲[2]、交通控制[3]、機器人[4]、電子游戲[5]等領(lǐng)域都有廣泛的應(yīng)用。近年來,研究人員在多智能體路徑規(guī)劃問題的研究中取得了眾多突破性進展,但國內(nèi)對這些工作進行整理形成的綜述較少,最近的相關(guān)綜述[6]只給出該問題的形式化定義和相關(guān)算法的簡單分類,沒有涉及算法的具體原理和最新進展。

在機器人領(lǐng)域,存在一類被稱作多機器人路徑規(guī)劃的問題。多機器人路徑規(guī)劃與多智能體路徑規(guī)劃2類問題存在許多相似之處,例如,兩者都關(guān)注如何求解問題、提高求解效率與結(jié)果質(zhì)量等。但是,多機器人路徑規(guī)劃同時關(guān)注機器人的視覺、定位、通信、運動控制等實際約束和設(shè)定,而多智能體路徑規(guī)劃則將這些設(shè)定進行抽象化,其將研究的重點集中在問題的求解方式、求解效率和求解質(zhì)量上。

本文研究多智能體路徑規(guī)劃問題。首先給出多智能體路徑規(guī)劃的問題定義和問題屬性,概述主流的4類最優(yōu)多智能體路徑規(guī)劃算法,解析算法的基本原理,然后分析2類近似多智能體路徑規(guī)劃算法的優(yōu)缺點。在此基礎(chǔ)上,總結(jié)多智能體路徑規(guī)劃問題的現(xiàn)有求解算法并對未來的研究方向進行展望。

1 多智能體路徑規(guī)劃

1.1 問題定義

一個經(jīng)典的多智能體路徑規(guī)劃問題可以被定義為一個四元組〈G,k,S,T〉。其中,G=(V,E)是一個無向圖,無向圖中的節(jié)點v∈V是智能體可以占據(jù)的位置,邊e=(vi,vj)∈E是vi和vj之間的連線,表示智能體可以在vi和vj之間移動。k代表問題中的智能體數(shù)量,即智能體{a1,a2,…,ak}。每個智能體ai都有獨一無二的起始位置si∈S∈V和目標位置gi∈T∈V。S是所有智能體初始位置的集合,T是所有智能體目標位置的集合。

在多智能體路徑規(guī)劃問題中,時間被離散化為時間步的形式。在每個時間步中,每個智能體可以采取一次行動。一般來說,有等待和移動2種行動。在多智能體路徑規(guī)劃問題中,存在智能體之間的沖突,且沖突主要有2種,即圖1所示的碰撞沖突和圖2所示的交換沖突。

圖1 碰撞沖突

圖2 交換沖突

智能體ai從si移動到gi的行動序列構(gòu)成一條路徑pi。多智能體路徑規(guī)劃問題的一個可行解是k個智能體的k條路徑的集合P={p1,p2,…,pk},其中,智能體ai對應(yīng)于路徑pi,路徑集合中的任意2條路徑pi和pj之間不存在沖突。

多智能體路徑規(guī)劃問題通常都需要最小化某個全局累積代價函數(shù),常用的代價函數(shù)有如下4種:

(1)

(2)

(3)

(4)

代價函數(shù)式(1)表示最晚到達目標位置的智能體所花費的時間,代價函數(shù)式(2)表示路徑集合中長度最長的路徑長度,代價函數(shù)式(3)表示所有智能體分別從各自起始位置到達各自目標位置所花費時間之和,代價函數(shù)式(4)表示路徑集合中所有路徑長度之和。

1.2 問題屬性

多智能體路徑規(guī)劃問題的狀態(tài)空間隨著問題中智能體的增多而指數(shù)增長,該問題也被證明是NP-hard問題[7]。因此,最優(yōu)的多智能體路徑規(guī)劃算法只有在智能體相對較少的情況下才有較好的實際應(yīng)用價值。盡管如此,最優(yōu)的多智能體路徑規(guī)劃算法仍然有很大的研究價值。適當犧牲多智能體路徑規(guī)劃算法的最優(yōu)性可以大幅提高算法的執(zhí)行效率,這也是有邊界的次優(yōu)多智能體路徑規(guī)劃算法的核心思想。除此之外,對最優(yōu)多智能體路徑規(guī)劃算法的研究可以更深刻地揭示多智能體路徑規(guī)劃問題的特點。

在多智能體路徑規(guī)劃問題的研究中,有2個非常重要的性質(zhì),即完整性和最優(yōu)性。完整性指當問題存在解時,算法能夠找到可行解;當問題不存在解時,算法能夠終止。最優(yōu)性指當問題有解時,算法返回的一定是最優(yōu)解。一般來說,最優(yōu)的多智能體路徑規(guī)劃算法需要同時滿足完整性和最優(yōu)性,而近似算法沒有這種要求,一部分近似算法具有完整性,另一部分則不具備完整性。

2 最優(yōu)多智能體路徑規(guī)劃算法

如表1所示,最優(yōu)的多智能體路徑規(guī)劃算法可以分為A*搜索的擴展、代價增長樹搜索、基于沖突的搜索和基于規(guī)約的方法4類。

表1 最優(yōu)多智能體路徑規(guī)劃算法對比

2.1 A*搜索的擴展

2.1.1 多智能體路徑規(guī)劃中的A*搜索

A*搜索是一種經(jīng)典的搜索算法,也同樣適用于多智能體路徑規(guī)劃問題。A*搜索在多智能體路徑規(guī)劃中的狀態(tài)空間一般被稱為k-agent狀態(tài)空間,其狀態(tài)數(shù)等于將k個智能體分別放置在|V|個不同的節(jié)點上的狀態(tài)數(shù),一種放置方法對應(yīng)于一種狀態(tài)。A*搜索的初始狀態(tài)節(jié)點表示所有智能體都在各自的初始位置,目標狀態(tài)節(jié)點表示所有智能體都到達各自的目標位置。A*搜索中狀態(tài)的后繼表示所有智能體各自采取一組無沖突的行動從當前狀態(tài)轉(zhuǎn)移到新的狀態(tài)。

對A*搜索啟發(fā)式函數(shù)的研究在多智能體路徑規(guī)劃中非常重要。最簡單的全局啟發(fā)式函數(shù)是所有智能體各自的啟發(fā)式函數(shù)之和,這在格點圖上表現(xiàn)為曼哈頓距離之和,而在歐幾里得圖上表現(xiàn)為歐幾里得距離之和[8]。在很多的多智能體路徑規(guī)劃研究中,采用了更為復雜的全局啟發(fā)式函數(shù),如SIC[9]和基于模式-數(shù)據(jù)庫的啟發(fā)式函數(shù)[10-11]。然而,采用過于復雜的啟發(fā)式函數(shù)不一定具有積極意義,因為提高啟發(fā)式函數(shù)的計算復雜度可能會降低算法的執(zhí)行效率。

2.1.2 A*搜索的缺陷和改進

在多智能體路徑規(guī)劃問題的求解中,A*搜索主要有兩大缺陷,這些缺陷也使得A*的求解能力嚴重受到問題中智能體數(shù)量的制約。第1個缺陷是搜索狀態(tài)空間的指數(shù)增長,A*搜索的狀態(tài)空間隨著問題中智能體的增多而指數(shù)增長,這使得A*中的open-list在智能體過多的情況下會發(fā)生溢出;第2個缺陷是搜索分支因子的指數(shù)增長,由于每個智能體在每個時間步能夠采取b(b>1)種行動,擴展到多個智能體時,A*搜索的分支因子也會隨著智能體的增多而指數(shù)增長,即bk。上述缺陷導致A*搜索無法求解較多智能體的路徑規(guī)劃問題。

目前,對A*搜索的缺陷進行改進主要通過4種方法,即OD(Operator Decomposition)[9]、EPEA*(Enhanced Partial Expansion)[10-11]、ID(Independence Detection)[9]和M*[12],4種方法的對比見表2。

表2 A*算法的主要改進方法

OD改進的是A*搜索中分支因子指數(shù)增長的缺陷。當A*搜索擴展初始狀態(tài)(si,s2,…,sk)時,只考慮第1個智能體的下一步行動,這樣會生成當前狀態(tài)的一系列后繼狀態(tài),即一共b個后繼狀態(tài)。在這些后繼狀態(tài)中,只有第一個智能體執(zhí)行行動,其余的k-1個智能體仍然保持t=0時刻的位置。將生成的這些后繼狀態(tài)節(jié)點加入到open-list中,當擴展這些狀態(tài)節(jié)點時,只考慮第2個智能體的行動,并生成新的一系列后繼狀態(tài)。新生成的后繼狀態(tài)代表第1個和第2個智能體可能處于的所有位置,其他智能體仍然處于t=0時刻的位置。按照這樣的規(guī)則繼續(xù)進行搜索,直至搜索樹上的第k層狀態(tài)節(jié)點能夠表示所有智能體在t=1時刻的所有可能位置分布。第k層狀態(tài)節(jié)點表示同一時刻所有智能體的位置分布,這類狀態(tài)節(jié)點被稱為滿狀態(tài)節(jié)點,其他狀態(tài)節(jié)點被稱為中間狀態(tài)節(jié)點。搜索在到達滿狀態(tài)節(jié)點(gi,gi+1,…,gk)時終止。OD大幅減小了A*搜索的分支因子。原始A*的分支因子是bk,而ODA*的分支因子是b。相應(yīng)地,ODA*也引入了大量的中間狀態(tài)節(jié)點,并且使得A*搜索的深度加深了k倍。然而,在多智能體路徑規(guī)劃中,這些中間狀態(tài)節(jié)點一般會因為其啟發(fā)式函數(shù)值過大而被剪枝。因此,OD的引入起到了很大的作用。

EPEA*改進的也是分支因子指數(shù)增長的缺陷。EPEA*和A*的不同之處在于,在擴展一個狀態(tài)節(jié)點時,EPEA*生成的后繼狀態(tài)節(jié)點不完整,也就是只將一部分的后繼狀態(tài)節(jié)點加入open-list中。文獻[10]證明了OD是EPEA*的特例,EPEA*的實現(xiàn)細節(jié)可以參考文獻[11]。

ID改進了A*搜索狀態(tài)空間的指數(shù)增長缺陷,其本質(zhì)上是一種智能體之間的獨立性檢測。ID嘗試將包含k個智能體的多智能體路徑規(guī)劃問題分解成多個包含更少智能體的子問題。在開始階段,每個智能體不考慮其他智能體,各自計算自己的最優(yōu)路徑,然后對計算出的k條最優(yōu)路徑進行獨立性檢測,如果兩組路徑之間發(fā)生了沖突,就將對應(yīng)的智能體合并為一組,不斷地進行合并分組,直到剩下的智能體分組對應(yīng)的路徑組之間不存在沖突,檢測終止。使用ID的A*在最壞情況下等于樸素的A*,當不是最壞情況時,ID將原來包含k個智能體的多智能體路徑規(guī)劃問題成功分解,大幅提高了A*算法的執(zhí)行效率。ID在多智能體路徑規(guī)劃中是一種常用的方法,可以提高多數(shù)多智能體路徑規(guī)劃算法的效率。

M*同時改進了狀態(tài)空間的指數(shù)增長和分支因子的指數(shù)增長缺陷,其核心思想和ID類似。M*大幅提高了A*算法的性能上限,可以較快地求解規(guī)模為20個左右智能體的路徑規(guī)劃問題。M*中存在一個重要的數(shù)據(jù)結(jié)構(gòu)——沖突集合,沖突集合初始為空,當開始擴展狀態(tài)節(jié)點時,M*中所有智能體依照不考慮其他智能體的各自的最優(yōu)路徑行動,這意味著搜索狀態(tài)空間的維度是1,分支因子的維度也是1。這樣的擴展會使q≥2個智能體在節(jié)點v發(fā)生沖突時中止。此時,發(fā)生沖突的這q個智能體會被加入到?jīng)_突集合中,然后重啟整個搜索過程。在搜索重啟時,沖突集合中的q個智能體會執(zhí)行樸素的多智能體A*搜索,其余的k-q個智能體依舊按照各自的最優(yōu)路徑參與全局狀態(tài)擴展,這時狀態(tài)空間的維度是q,分支因子為bq。M*在所有智能體到達目標位置時終止,M*的最壞情況仍然是回歸到樸素的A*。M*的改進型rM*[12]將沖突的智能體分割為沒有沖突的分組,遞歸地解決生成的子問題,從而加速了算法執(zhí)行。另一種改進型ODrM*[13]在搜索層面上采用ODA*取代樸素的A*,將A*類最優(yōu)算法求解問題的規(guī)模擴大到30個智能體。

上述A*的改進方法之間并非互斥,所有方法都可以同時使用。這些方法仍然是在k-agent狀態(tài)空間中求解,這也是這類方法的一個顯著特征。

2.2 代價增長樹搜索

與基于A*的算法不同,代價增長樹搜索[14]沒有直接在k-agent狀態(tài)空間中進行搜索。代價增長樹搜索分為高層次搜索和低層次搜索2層。高層次搜索的目的是找到每個智能體ai在問題的最優(yōu)解中所花費的代價ci,即(c1,c2,…,ck)。低層次搜索的目的是驗證對于給定的(c1,c2,…,ck),是否存在一組最優(yōu)解(π1,π2,…,πk),使得?i∈{1,2,…,k},πi=ci。

2.2.1 高層次搜索

高層次搜索是在代價增長樹上進行搜索。代價增長樹的狀態(tài)節(jié)點是一組k維向量(c1,c2,…,ck),代表每個智能體ai從起始位置si到目標位置gi花費代價為ci的所有可能的路徑集合。代價增長樹的根節(jié)點是(o1,o2,…,ok),oi是智能體ai不考慮其他智能體的最優(yōu)路徑的代價。(o1,o2,…,ok)是全局最優(yōu)解的下限。代價增長樹通過選取當前狀態(tài)節(jié)點中的一個智能體ai,令ci+1,生成后繼的狀態(tài)節(jié)點。對于代價搜索樹的一個狀態(tài)節(jié)點(c1,c2,…,ck),如果通過低層次搜索的驗證,那么(c1,c2,…,ck)就是一個可行解。因為代價增長樹中同一層次的狀態(tài)節(jié)點的代價總和相等,所以在高層次搜索中可以采用寬度優(yōu)先搜索來找到全局最優(yōu)解。因此,當找到第一個通過低層次搜索驗證的狀態(tài)節(jié)點(c1,c2,…,ck)時,(c1,c2,…,ck)就是全局最優(yōu)解,算法終止。

2.2.2 低層次搜索

低層次搜索是對高層次搜索的狀態(tài)節(jié)點(c1,c2,…,ck)的驗證。低層次搜索首先計算每個智能體ai從起始位置si到目標位置gi花費代價為ci且不考慮其他智能體的所有路徑集合,分別使用MDD[15]存儲。所有MDD的交叉乘積結(jié)果就是所有滿足(c1,c2,…,ck)的全局路徑集合,這其實是k-agent狀態(tài)空間中的一個子空間。低層次搜索對MDD叉乘的結(jié)果進行搜索,尋找可行解。低層次搜索是驗證的過程而非最優(yōu)化的過程,因此,可以采用有界深度優(yōu)先搜索來實現(xiàn)。

2.2.3 剪枝加速

代價增長樹搜索存在的一個問題是不能很快地驗證給定狀態(tài)節(jié)點是否存在解。這個問題可以通過在低層次搜索中驗證其子問題是否存在可行解來改進。常用的一種策略是選取所有的智能體對(ai,aj),i,j∈{1,2,…,k},i≠j,當某對智能體(ai,aj)之間不存在無沖突的路徑組合時,低層次搜索就可以返回(c1,c2,…,ck)無解。

2.3 基于沖突的搜索

基于沖突的搜索(CBS)[16]和代價增長樹搜索有些相似,同樣分為高層次搜索和低層次搜索,不同之處在于,CBS求解的是一系列的單智能體路徑規(guī)劃問題。

2.3.1 約束與一致路徑

在基于沖突的搜索中,智能體會受到一些約束。對智能體ai的一組約束可以表示為〈ai,v,t〉,表示智能體ai在t時刻不能處于位置v。智能體ai的一致路徑指的是滿足關(guān)于ai的所有約束的路徑。全局可行解中每個智能體的路徑必須是一致路徑,反之則不成立,原因是無法保證智能體的一致路徑之間不存在沖突。

2.3.2 高層次搜索

基于沖突的搜索的高層次搜索是在約束樹上進行的。約束樹是一棵二叉樹,樹上的每個狀態(tài)節(jié)點包含一個約束集合、一組智能體的一致路徑(每個智能體對應(yīng)一條一致路徑)和目前為止的全局代價。約束樹根節(jié)點中的約束集合是空集。CBS中當前狀態(tài)節(jié)點的后繼狀態(tài)節(jié)點會繼承當前狀態(tài)節(jié)點的約束集合并加入對某個智能體的一組新約束。一組智能體的一致路徑只有在任意一組路徑之間都不存在沖突時才是全局可行解。

對于約束樹中的某個狀態(tài)節(jié)點,低層次搜索為其尋找一組智能體的一致路徑,然后按照時間步模擬每個智能體的行動。如果整個模擬過程中沒有發(fā)生沖突,那么當前狀態(tài)節(jié)點就是目標狀態(tài)節(jié)點;如果發(fā)生了沖突,就需要進行分割操作。分割操作指當約束樹中的某個狀態(tài)節(jié)點中的一致路徑包含一個沖突〈ai,aj,v,t〉時,需要生成2個約束〈ai,v,t〉和〈aj,v,t〉。對于這2個約束,當前狀態(tài)節(jié)點會分別生成2個后繼狀態(tài)節(jié)點,它們的約束集合相比于當前狀態(tài)節(jié)點的約束集合分別增加了〈ai,v,t〉和〈aj,v,t〉。2個后繼狀態(tài)節(jié)點將繼承當前狀態(tài)節(jié)點中新加入約束中的智能體之外的其他智能體的一致路徑,擁有新約束的智能體將會通過低層次搜索生成新的一致路徑。

CBS的高層次搜索一般采用最優(yōu)優(yōu)先搜索,優(yōu)先擴展全局代價最小的狀態(tài)節(jié)點。

2.3.3 低層次搜索

CBS的低層次搜索根據(jù)約束樹節(jié)點中的約束集合,尋找滿足每個智能體相關(guān)約束的一組一致路徑。但是低層次搜索無法保證一致路徑之間不存在沖突。在低層次搜索中,所有的單智能體路徑規(guī)劃算法都適用。

2.3.4 改進的基于沖突搜索

在加入了上述這些對CBS的優(yōu)化之后,CBS能夠求解30個～60個智能體的路徑規(guī)劃問題?；跊_突的搜索是多智能體路徑規(guī)劃領(lǐng)域中比較新穎的方法,也是目前研究的熱點。

2.4 基于規(guī)約的方法

上述3類最優(yōu)多智能體路徑規(guī)劃算法本質(zhì)上都是基于搜索的算法,而基于規(guī)約的方法與它們不同。因為多智能體路徑規(guī)劃問題是NP-hard的問題,可以將多智能體路徑規(guī)劃問題規(guī)約為其他的標準問題,如SAT、CSP和ASP等。完成規(guī)約的正確性證明后,便可以利用這些問題已有的高質(zhì)量求解器來求解多智能體路徑規(guī)劃問題。

文獻[21]將多智能體路徑規(guī)劃問題規(guī)約成了CSP問題,但是該過程對問題中的地圖有所要求,只有地圖可以被抽象為已知的子圖,如環(huán)和團等形狀時,規(guī)約才是正確的。文獻[22]將多智能體路徑規(guī)劃問題規(guī)約為SAT問題,將問題中地圖的結(jié)構(gòu)、智能體的位置和約束編碼為布爾變量,然后用這些布爾變量生成標準的SAT問題來驗證是否存在全局代價為C的可行解,遍歷所有可能的全局代價C就能夠生成全局最優(yōu)解。文獻[23]通過改進問題的編碼方式,成為較早能夠解決求和代價函數(shù)的多智能體路徑規(guī)劃問題的SAT求解器。文獻[24]將ID用于基于SAT的方法中來求解問題。文獻[25]提出新的代價估計方法并減少SAT模型中變量的數(shù)量,從而加速了算法執(zhí)行。文獻[26]通過將多智能體路徑規(guī)劃問題中2個智能體之間的約束轉(zhuǎn)化為ASP中的程序P來求解問題,P的答案集就是問題的解集。文獻[27-28]將多智能體路徑規(guī)劃問題規(guī)約為一個網(wǎng)絡(luò)流問題,規(guī)約后網(wǎng)絡(luò)流中流的深度和多智能體路徑規(guī)劃中的時間步相關(guān),然后將多智能體路徑規(guī)劃問題的形式轉(zhuǎn)變?yōu)橐幌盗械仁胶鸵粋€目標函數(shù),利用整數(shù)線性規(guī)劃來求解最優(yōu)解。文獻[29]將多智能體路徑規(guī)劃問題規(guī)約為TSP問題,改進了IPL模型,提出了有效的模型績效評價指標,利用已有的ILP求解器求解變形之后的問題。

基于規(guī)約的方法的難點在于規(guī)約的證明,一般需要極強的數(shù)理功底。在一般情況下,這類方法的求解速度高于上述基于搜索的最優(yōu)算法,但是它們無法保證完成規(guī)約證明之后使用相應(yīng)求解器時的高效性。

3 近似的多智能體路徑規(guī)劃算法

因為多智能體路徑規(guī)劃問題是NP-hard問題,求解最優(yōu)解的算法需要很長的執(zhí)行時間,為了加速問題的求解,往往需要犧牲一些結(jié)果的最優(yōu)性。近似的多智能體路徑規(guī)劃算法可以分為無邊界次優(yōu)的和有邊界次優(yōu)的算法。多數(shù)近似算法都是無邊界次優(yōu)的,而有邊界的次優(yōu)算法一般都是最優(yōu)算法的衍生算法。一般來說,有邊界的次優(yōu)算法的速度會快于最優(yōu)算法,但是慢于無邊界次優(yōu)的算法;在結(jié)果的最優(yōu)性上,有邊界的次優(yōu)算法會略遜于最優(yōu)算法,但是優(yōu)于無邊界的次優(yōu)算法。

3.1 無邊界次優(yōu)的多智能體路徑規(guī)劃算法

無邊界次優(yōu)的多智能體路徑規(guī)劃算法能夠快速地計算出一個可行解,但是無法保證結(jié)果的質(zhì)量。早期研究的局限性都較大,比如文獻[30]能夠保證算法具備完整性,但是結(jié)果的質(zhì)量可能遠低于最優(yōu)結(jié)果,并且在每個時間步中只允許一個智能體采取行動。無邊界次優(yōu)算法分類與對比如表3所示。

表3 各類無邊界次優(yōu)的多智能體路徑規(guī)劃算法對比

3.1.1 基于搜索的無邊界次優(yōu)算法

文獻[31]提出了CA*及其改進型HCA*和WHCA*。這類算法順序地為每個智能體單獨規(guī)劃路徑,已經(jīng)規(guī)劃的路徑會被記錄在留存表中,后續(xù)在智能體規(guī)劃路徑時不能和留存表中的路徑發(fā)生沖突,但上述算法并不具備完整性。文獻[32]提出了一種具備完整性的無邊界次優(yōu)算法,其本質(zhì)上是對A*算法的約束放松。文獻[33]將狀態(tài)空間進行抽象化來減少啟發(fā)式函數(shù)的計算時間。文獻[34]提出了一種動態(tài)修改路徑的2段協(xié)調(diào)方法,在第1階段使用A*搜索每個智能體的最優(yōu)路徑,在第2階段采用增量式A*算法解決路徑之間的沖突問題。文獻[35]在文獻[31]的基礎(chǔ)上,將窗口放置于已知的沖突位置附近,并將所有智能體根據(jù)參與到?jīng)_突中的可能性大小進行優(yōu)先級排序,按照優(yōu)先級來為智能體規(guī)劃路徑。文獻[36]提出了一種基于保留區(qū)域的分布式多智能體路徑規(guī)劃算法,解決了多智能體路徑之間高度耦合的問題。一般而言,與基于規(guī)則的算法相比,基于搜索的無邊界次優(yōu)算法的速度沒有特別大的優(yōu)勢,但是結(jié)果的質(zhì)量會更好。

3.1.2 基于規(guī)則的無邊界次優(yōu)算法

在基于規(guī)則的無邊界次優(yōu)算法中,智能體在不同的場景下有不同的行動規(guī)則,并且不需要進行大規(guī)模的搜索?；谝?guī)則的無邊界次優(yōu)算法能夠很快地求解問題,但是其結(jié)果質(zhì)量可能遠遜于最優(yōu)解。

基于規(guī)則的無邊界次優(yōu)算法的一個重要性質(zhì)就是完整性,但是這類算法的完整性往往對問題中地圖的性質(zhì)有特殊的要求。文獻[37]提出一種基于規(guī)則且具備完整性的無邊界次優(yōu)算法,但是其實際實現(xiàn)時難度極大。文獻[38]算法只有在樹形圖上才具備完整性。文獻[39]算法只有在雙連通圖上才具備完整性。文獻[40]算法只有在強雙連通圖上才具備完整性。

文獻[41- 43]只有在地圖中至少存在2個未被智能體占據(jù)的空位置節(jié)點時才具備完整性。文獻[41]引入2個macro操作符,macro可以將智能體推到空位置節(jié)點,還可以交換2個智能體的位置。文獻[42]提出文獻[41]的改進算法,不同于文獻[41]中每個時間步內(nèi)只允許一個智能體行動,文獻[42]可以并行地為所有智能體規(guī)劃路徑。文獻[43]通過引入新的旋轉(zhuǎn)操作符來改進文獻[41]算法。

此外,還存在一些混合類型的算法,即算法中既存在智能體行動的規(guī)則也存在大規(guī)模的搜索,比如文獻[44]通過引入交通規(guī)則來減少搜索。目前,對混合方法的研究較少,但是這類混合方法給多智能體路徑規(guī)劃的研究帶來了很大的啟發(fā)。

上述基于規(guī)則的無邊界次優(yōu)算法的求解速度一般較快,但是無法保證其結(jié)果的質(zhì)量。

3.1.3 基于規(guī)約的無邊界次優(yōu)算法

文獻[45]通過將問題規(guī)約為CSP問題,即令每個智能體對應(yīng)一個變量,變量的值域就是智能體從起始位置到目標位置的所有可能路徑的集合,則問題的約束就是智能體的路徑之間不能存在沖突。文獻[46]通過使用矩陣計算加速變量值域的縮減,引入動態(tài)變量排序和快速隨機重啟等技巧,取得了較好的效果。文獻[47]提出了一種基于ASP的無邊界近似分布式多智能體路徑規(guī)劃算法,其能夠處理很大規(guī)模的多智能體路徑規(guī)劃問題。文獻[48]提出基于SAT的無邊界次優(yōu)算法,其通過移除文獻[23]中的數(shù)量約束,從而將文獻[23]算法從最優(yōu)算法轉(zhuǎn)變?yōu)闊o邊界次優(yōu)的算法。

3.1.4 其他無邊界次優(yōu)算法

其他無邊界次優(yōu)算法主要包括基于強化學習、基于遺傳算法、基于協(xié)同進化和基于蟻群算法的算法。

國內(nèi)近期提出了一類基于強化學習的多智能體路徑規(guī)劃算法。文獻[49]通過采用無模型的在線Q學習方法,使得多個智能體重復“探索-學習-利用”過程,積累歷史經(jīng)驗評估動作策略并優(yōu)化決策。文獻[50]提出了一種基于分層強化學習和人工勢場的多智能體路徑規(guī)劃算法,其將多智能體的所在環(huán)境虛擬為一個人工勢能場,根據(jù)先驗知識確定每個節(jié)點的勢能值,代表最優(yōu)策略可獲得的最大回報,利用分層強化學習方法中的無環(huán)境模型學習和局部更新能力,將策略更新過程限制在規(guī)模較小的局部空間或維度較低的高層空間中。

在早期的基于遺傳算法中,文獻[51]采用鏈接圖法建立了智能體工作空間模型,采用遺傳算法規(guī)劃多智能體運動路徑,引入適應(yīng)值調(diào)整矩陣的新概念,實現(xiàn)了對多智能體路徑的全局優(yōu)化。近期,文獻[52]以多智能體執(zhí)行任務(wù)的自身代價與任務(wù)間的關(guān)聯(lián)代價為優(yōu)化目標,使用遺傳算法求解問題。

在基于協(xié)同進化的算法中,文獻[53]通過采用協(xié)同進化算法、設(shè)計適應(yīng)度評價函數(shù)和引入一系列新的變異操作算子,以求解問題。

在基于蟻群的算法中,文獻[54]通過建立有權(quán)圖模型,采用蟻群算法求解多智能體路徑規(guī)劃問題。文獻[55]提出了一種多步長的改進蟻群算法,以改進文獻[54]算法收斂速度慢、容易陷入局部最優(yōu)的缺陷。

上述算法的主要問題是容易陷入局部最優(yōu),并且無法保證結(jié)果的質(zhì)量與算法的完整性。

3.2 有邊界次優(yōu)的多智能體路徑規(guī)劃算法

有邊界次優(yōu)的多智能體路徑規(guī)劃算法指對于常量ε>0,算法給出結(jié)果的代價最多是最優(yōu)結(jié)果代價的1+ε倍,一般稱這類算法為ε次優(yōu)的算法。理論上而言,當ε變大,算法的速度也會變快。因此,在算法的速度和結(jié)果質(zhì)量上存在均衡。現(xiàn)有有邊界次優(yōu)的多智能體路徑規(guī)劃算法都是在前述最優(yōu)算法的基礎(chǔ)上犧牲最優(yōu)性得來的次優(yōu)算法。4種主要的有邊界次優(yōu)算法的對比結(jié)果如表4所示。

表4 有邊界次優(yōu)的多智能體路徑規(guī)劃算法對比

3.2.1 基于A*的有邊界次優(yōu)算法

多數(shù)基于A*的有邊界次優(yōu)算法都是通過修改A*搜索的啟發(fā)式函數(shù)來實現(xiàn)的。文獻[56]通過使用g+(1+ε)h的啟發(fā)式函數(shù)來選擇待擴展的狀態(tài)節(jié)點。前述所有基于A*的最優(yōu)算法都可以使用這種估計函數(shù)轉(zhuǎn)變?yōu)橛羞吔绱蝺?yōu)算法,比如文獻[12]提出的inflated M*。

文獻[57]使用(C-g)/h的啟發(fā)式函數(shù),并且將算法次優(yōu)的邊界改進為問題要求的次優(yōu)邊界與open-list中最小的啟發(fā)式函數(shù)值的積。

3.2.2 基于代價增長樹搜索的有邊界次優(yōu)算法

因為代價增長樹搜索的高層次搜索是寬度優(yōu)先搜索,低層次搜索只是高層次搜索的驗證,不存在啟發(fā)式函數(shù),所以對于基本的多智能體路徑規(guī)劃問題不存在有邊界次優(yōu)的算法。但是如果在多智能體路徑規(guī)劃問題的定義中加入新的約束,比如保證問題中地圖的所有邊權(quán)值不同,則文獻[58]算法可以看作是代價增長樹搜索的一個有邊界次優(yōu)衍生算法。

3.2.3 基于沖突搜索的有邊界次優(yōu)算法

CBS的低層次搜索通常是最優(yōu)的單智能體最短路徑算法,比如A*。因此,所有基于A*的有邊界次優(yōu)算法都可以在CBS的低層次搜索中實現(xiàn),這是實現(xiàn)基于CBS的有邊界次優(yōu)算法的一種途徑。

如果要在高層次搜索中引入次優(yōu)性,比較常用的方法是引入FS(Focal Search)[59]。FS在每次擴展時從focal-list中選擇狀態(tài)節(jié)點,而不是從open-list中選擇。對于常數(shù)ω,focal-list中存儲的是open-list中代價小于等于ω倍open-list中最優(yōu)狀態(tài)節(jié)點代價的狀態(tài)節(jié)點。因此,在引入FS之后,高層次搜索就有2個啟發(fā)式函數(shù)可以引入次優(yōu)性,即open-list的啟發(fā)式函數(shù)和focal-list的啟發(fā)式函數(shù)。

文獻[60]在CBS的高層次搜索和低層次搜索中引入了次優(yōu)性,為ω1次優(yōu)。文獻[61]算法是文獻[60]算法的改進,其加入了直連邊,使得算法是ω1ω2次優(yōu)。文獻[62]算法在文獻[61]的基礎(chǔ)上進行優(yōu)化,使得算法仍然是ω1次優(yōu)。

3.2.4 基于規(guī)約的有邊界次優(yōu)算法

在多智能體路徑規(guī)劃算法中,單獨研究基于規(guī)約的有邊界次優(yōu)算法的工作較少,因為只要證明了規(guī)約的正確性,那么相關(guān)規(guī)約的有邊界次優(yōu)算法都可以應(yīng)用于多智能體路徑規(guī)劃問題的求解中。比如,文獻[48]通過放松文獻[23]中的數(shù)量約束,賦予其更松弛的代價邊界,將最優(yōu)算法轉(zhuǎn)變?yōu)橛羞吔绱蝺?yōu)的算法。

4 研究展望

近年來,傳統(tǒng)的基于搜索的算法雖然仍然是研究熱點,但是基于規(guī)約的方法以及其他方法也引起了學者們的關(guān)注,比如文獻[63]使用深度強化學習和卷積神經(jīng)網(wǎng)絡(luò)來求解多智能體路徑規(guī)劃問題,文獻[64]將基于搜索的方法和基于SAT的方法相結(jié)合,以求解多智能體路徑規(guī)劃問題。值得注意的是,現(xiàn)有所有多智能體路徑規(guī)劃算法都不能在所有類型的問題中取得超過其他所有算法的性能,即不同算法適用的問題類型不同。本文將未來的研究方向歸納為以下5個方面:

1)多智能體路徑規(guī)劃理論需要系統(tǒng)地對問題中相應(yīng)參數(shù)(比如智能體數(shù)量、智能體密度和地圖尺寸等)對問題求解難度的影響進行量化分析,上述研究可以采用控制變量法來實現(xiàn)。在相關(guān)參數(shù)中,本文認為智能體密度和地圖中的障礙物密度可能是影響問題求解的主要因素。

2)新算法逐漸涌現(xiàn),但是對于目標函數(shù)之間的差異,目前研究比較少,多數(shù)研究都只針對其中一種來驗證算法的性能。在前述的4種目標函數(shù)中,求和形式的目標函數(shù)在研究中被廣泛應(yīng)用,但是求最值形式的目標函數(shù)才是最具有實際應(yīng)用價值的,這就使得在理論研究和實際應(yīng)用中存在鴻溝。求和形式的目標函數(shù)在研究中最受歡迎,是因為該類型的目標函數(shù)容易求導并證明算法的最優(yōu)性,這也意味著部分最優(yōu)的算法可能無法適用最值型的目標函數(shù)。因此,需要對不同目標函數(shù)在不同算法中的兼容性進行研究。

3)不同算法擅長求解的問題一般不同,需要對已有算法之間的關(guān)聯(lián)性和性能差異做出量化分析,目前也缺少被廣泛接受的標準測試集。由于多智能體路徑規(guī)劃算法的開源較少,且論文一般不會提供相關(guān)代碼,在算法之間進行比較的工作量會非常大。

4)對于經(jīng)典多智能體路徑規(guī)劃問題的變形進行研究正在逐漸受到重視。經(jīng)典模型對現(xiàn)實生活中問題的建模能力比較弱,在實際生活中,路徑規(guī)劃問題可能會包含信號燈、優(yōu)先級、概率等因素,使得經(jīng)典算法不再適用。因此,為了更好地在實際問題中應(yīng)用多智能體路徑規(guī)劃算法,主流的研究不能只局限于經(jīng)典模型。

5)類似于機器學習中的模型融合,考慮到各類多智能體路徑規(guī)劃算法對不同特點問題的求解性能差異,可以對各類算法的融合進行研究。本文認為,多智能體路徑規(guī)劃算法之間的融合主要有2種方法:第1種方法是對于給定的問題,可以利用多線程使用各種算法來求解,當某種算法求解成功之后終止所有算法,但是,考慮到這些算法對計算資源的需求較大,融合算法的計算代價可能極高;第2種方法是在求解問題之前,先分析問題以獲得問題參數(shù),然后根據(jù)參數(shù)來選取求解算法,問題中的部分參數(shù)如智能體數(shù)量、地圖尺寸等一般已知,但是在問題中還會存在一些未知的參數(shù),如智能體密度、障礙物密度等,對于這類參數(shù)可以通過采樣來估計。在獲得上述參數(shù)之后,通過建立決策樹模型來決定采取何種算法求解問題。

5 結(jié)束語

本文介紹多智能體路徑規(guī)劃問題以及最優(yōu)算法、無邊界的次優(yōu)算法和有邊界的次優(yōu)算法3類求解算法。最優(yōu)算法能夠保證結(jié)果的最優(yōu)性,但是速度最慢,無邊界的次優(yōu)算法速度最快,但是結(jié)果質(zhì)量無法保證,有邊界的次優(yōu)算法能夠保證結(jié)果的質(zhì)量,速度處于最優(yōu)算法與無邊界的次優(yōu)算法之間。在實際應(yīng)用中,只有當問題規(guī)模較小時,才適合使用最優(yōu)算法,而當問題規(guī)模較大時,可以根據(jù)對結(jié)果質(zhì)量的需求使用有邊界或無邊界的次優(yōu)算法。鑒于不同算法適用問題的類型不同,下一步除了探究性能更好的算法之外,還將深入分析已有算法適用問題的差異性,量化問題參數(shù)對規(guī)劃結(jié)果影響的大小,推動融合算法的進一步發(fā)展。