耿文浩, 陳年生, 宋曉勇, 程松林

(上海電機(jī)學(xué)院 電子信息學(xué)院, 上海 201306)

多智能體路徑規(guī)劃(Multi-Agent Path Finding, MAPF)[1]是涉及協(xié)調(diào)多個(gè)智能體在動(dòng)態(tài)環(huán)境中共享有限資源的路徑選擇問題,在實(shí)際場景中具有廣泛應(yīng)用,例如無人機(jī)編隊(duì)飛行[2]、物流系統(tǒng)中的貨物調(diào)度[3]和機(jī)器人協(xié)作[4]等。MAPF是非確定性多項(xiàng)式(Non-deterministic Polynomial, NP)問題[5],最優(yōu)解的MAPF算法執(zhí)行時(shí)間隨著智能體數(shù)量增加而指數(shù)級增長,而有界次優(yōu)的MAPF算法雖然可以在大型實(shí)例中執(zhí)行完成,但可能無法獲得完整無沖突的路徑結(jié)果。由于其復(fù)雜性和NP難度,有效解決MAPF問題仍然面臨巨大挑戰(zhàn)。

MAPF算法按照規(guī)劃方式[6]劃分為分布式和集中式兩種。前者主要基于強(qiáng)化學(xué)習(xí),在路徑重新規(guī)劃方面顯示出較大的潛力,但其訓(xùn)練時(shí)間較長;后者則要求中央規(guī)劃器掌握所有智能體的起始位置、目標(biāo)位置和障礙物位置等信息。集中式算法又可細(xì)分為以下類型:① 基于A*搜索算法[7-9],該類算法的空間代價(jià)高,求解速度慢,僅適用于小規(guī)模智能體環(huán)境;② 基于沖突搜索的算法[10-12],該類算法實(shí)現(xiàn)難度較大,并且存在著空間代價(jià)高和求解速度慢的問題;③ 基于代價(jià)增長樹的算法[13],該類算法實(shí)現(xiàn)簡單速度快,但在高密度智能體環(huán)境中易失效;④ 基于規(guī)約的算法[14],該類算法存在規(guī)約證明困難的問題。

MAPF-LNS2算法[15]是一個(gè)具有代表性的多算法融合類MAPF算法,它具有運(yùn)行速度快、資源占用率低以及適應(yīng)大規(guī)模問題等特點(diǎn)。但由于MAPF-LNS2算法中的自適應(yīng)大鄰域搜索算法在進(jìn)行自適應(yīng)大鄰域搜索策略修復(fù)時(shí),過分關(guān)注鄰域搜索策略的近期表現(xiàn),易陷入局部最優(yōu)解,導(dǎo)致某些策略在得到較高權(quán)值后被過度執(zhí)行,而其他更有潛力的策略則無法得到執(zhí)行,進(jìn)而出現(xiàn)“饑餓”現(xiàn)象,從而會增加算法的總運(yùn)行時(shí)間。

本文針對MAPF-LNS2算法存在的問題,通過引入改善率統(tǒng)計(jì)和時(shí)間窗口,提出MAPF-LNS2+算法。改進(jìn)算法在鄰域搜索策略調(diào)度過程中通過觀察其改善率趨勢,同時(shí)考慮到鄰域搜索策略的近期和長期表現(xiàn),以緩解原算法中出現(xiàn)的“饑餓”現(xiàn)象。經(jīng)對比實(shí)驗(yàn),證實(shí)了MAPF-LNS2+算法有效減少了額外運(yùn)行時(shí)間損耗,從而降低了算法總運(yùn)行時(shí)間。

1 MAPF-LNS2算法

MAPF-LNS2算法首先采用有界次優(yōu)的MAPF算法快速獲得初始路徑,如果該路徑存在沖突,則基于自適應(yīng)大鄰域搜索算法修復(fù)初始路徑。MAPFLNS2算法的基本流程如圖1所示。MAPF-LNS2算法所采用的路徑修復(fù)模塊為自適應(yīng)大鄰域搜索(Adaptive Large Neighborhood Search, ALNS)模塊,該模塊在路徑修復(fù)過程中會多次調(diào)用3種不同的鄰域搜索策略:① 基于碰撞的鄰域搜索策略,它所生成鄰域的方法是選擇當(dāng)前路徑相互碰撞的代理子集,這樣就有可能減少?zèng)_突個(gè)數(shù);② 基于失敗的鄰域搜索策略,該策略試圖通過分析失敗的多種原因來調(diào)整路徑規(guī)劃;③ 隨機(jī)的鄰域搜索策略,它基于當(dāng)前路徑隨機(jī)選擇周邊的其他代理。

圖1 MAPF-LNS2算法基本流程

ALNS模塊的3種鄰域搜索策略在路徑的搜索和修復(fù)過程中具有不同的表現(xiàn)效果,ALNS模塊會根據(jù)鄰域搜索策略執(zhí)行完成后的沖突解決個(gè)數(shù)為其更新權(quán)重。更新權(quán)重的表達(dá)式為

式中:wi為更新后策略的權(quán)重(初始時(shí)所有被設(shè)置為1);wold,i為每個(gè)鄰域搜索策略的上一次權(quán)重;c-、c+分別為鄰域搜索策略執(zhí)行前后路徑上的沖突個(gè)數(shù);γ為一個(gè)用戶指定的反應(yīng)因子,控制權(quán)重對沖突代價(jià)變化的敏感程度,γ取值在[0,1]內(nèi),代表權(quán)重相對成功變化的快慢程度,較小的γ值表示權(quán)重更快地適應(yīng)變化。

ALNS模塊根據(jù)解決的沖突個(gè)數(shù)來更新3種鄰域策略的權(quán)重,這使得解決沖突個(gè)數(shù)較多的鄰域搜索策略在接下來的選擇中獲得較高的權(quán)重。如果某個(gè)鄰域策略的表現(xiàn)下降,其他更具潛力的鄰域搜索策略必須等待權(quán)重值持平或超越后才能被執(zhí)行。在權(quán)重值平衡的過程中,其他鄰域搜索策略可能會出現(xiàn)短暫的“饑餓”現(xiàn)象,這種現(xiàn)象會增加算法的總運(yùn)行時(shí)間。

2 MAPF-LNS2+算法

針對MAPF-LNS2算法中的ALNS模塊存在的“饑餓”現(xiàn)象,引入改善率統(tǒng)計(jì)機(jī)制和時(shí)間窗口,在ALNS模塊為鄰域搜索策略分配權(quán)值時(shí),同時(shí)考慮其長期表現(xiàn),以確保算法在短期和長期時(shí)間效率之間取得平衡。

2.1 改善率統(tǒng)計(jì)機(jī)制

在MAPF-LNS2算法中,最為核心的模塊是基于自適應(yīng)大鄰域搜索算法的ALNS模塊。它首先初始化3種鄰域搜索策略的權(quán)重為1,并基于概率隨機(jī)選擇一個(gè)鄰域搜索策略執(zhí)行。該概率基于3種鄰域搜索策略的權(quán)重,假設(shè)每個(gè)鄰域搜索策略的權(quán)重為wi,則其被選中的概率為wi∑wj。當(dāng)某鄰域搜索策略執(zhí)行完成后,其解決路徑上的沖突個(gè)數(shù)被用來更新權(quán)重。如果某鄰域搜索策略在一次改善中取得較為顯著的沖突個(gè)數(shù)減少,那么它將被獎(jiǎng)勵(lì)以更高的權(quán)重。即使其在隨后的執(zhí)行中表現(xiàn)出解決沖突個(gè)數(shù)呈下降的趨勢,其他鄰域搜索策略也必須等待,直至正在執(zhí)行的鄰域搜索策略的權(quán)重逐漸降低,降低至與其他鄰域搜索策略權(quán)重相當(dāng),其他策略才會被執(zhí)行。這就是ALNS模塊存在的“饑餓”現(xiàn)象,即過多關(guān)注于當(dāng)前或近期表現(xiàn)最好的鄰域搜索策略。

本文的改進(jìn)思想是使ALNS模塊在為鄰域搜索策略分配權(quán)值時(shí),同時(shí)考慮其長期表現(xiàn),以確保算法在短期和長期時(shí)間效率之間取得平衡。為此采用兩個(gè)策略:引入改善率統(tǒng)計(jì)機(jī)制和時(shí)間窗口。改善率統(tǒng)計(jì)用于評估鄰域搜索的效果,通過記錄每次鄰域搜索后沖突個(gè)數(shù)的改善情況,來動(dòng)態(tài)調(diào)整鄰域搜索策略,以提高算法性能;時(shí)間窗口則用來限制判斷改善率變化趨勢的策略。當(dāng)選定某個(gè)鄰域搜索策略時(shí),通過歷史鄰域搜索策略的改善率和一個(gè)大小為N的時(shí)間窗口,來判斷改善率的變化趨勢。

定義1改善率是指鄰域搜索策略迭代完成后,每次迭代中鄰域搜索策略對于沖突數(shù)量的改進(jìn)程度,改善率的計(jì)算公式如下:

定義2時(shí)間窗口是一種工具,若其大小為N則可以提取某個(gè)鄰域搜索策略最近N次的改善率記錄。

改善率公式在一定程度上反映了算法的改善效果。改善率統(tǒng)計(jì)機(jī)制就是在鄰域搜索策略迭代完成后,通過計(jì)算其改善率,以決定下一輪執(zhí)行的鄰域搜索策略。一旦鄰域搜索策略存在歷史改善率并且數(shù)量不小于時(shí)間窗口大小,那么隨后的迭代過程中ALNS模塊會考慮其歷史改善率,如若出現(xiàn)改善率下降趨勢,則會選擇其他最近改善率最高的鄰域搜索策略執(zhí)行,這個(gè)過程使得ALNS模塊考慮了鄰域搜索策略的長期表現(xiàn)并不斷修復(fù)了鄰域搜索策略的權(quán)重。

2.2 改善率趨勢的判斷

在ALNS模塊完成策略的權(quán)值更新后,需要判斷要執(zhí)行的策略是否呈現(xiàn)下降趨勢。為此,引入改善率趨勢判斷函數(shù),通過提供時(shí)間窗口的大小N和改善率記錄來檢測鄰域搜索策略最近N次的改善率趨勢。

定義3改善率趨勢函數(shù)

式中:r為策略最后一次執(zhí)行的改善率。

改善率趨勢函數(shù)內(nèi)部根據(jù)時(shí)間窗口的大小來截取最近次的歷史改善率記錄,計(jì)算得到其平均值與最后一次執(zhí)行的改善率r比較,若結(jié)果為真,則表明該鄰域搜索策略出現(xiàn)了改善率下降趨勢,此時(shí)則在另外兩個(gè)策略中進(jìn)行決策。改善率趨勢函數(shù)的主要作用是幫助ALNS模塊修正權(quán)重分配,當(dāng)ALNS模塊為某個(gè)鄰域搜索策略分配了過高的權(quán)重時(shí),考慮該鄰域搜索策略其長期表現(xiàn),使得其他更有“潛力”的鄰域搜索策略仍然有機(jī)會被執(zhí)行并修正權(quán)重,改善率趨勢函數(shù)在一定程度上緩解了ALNS模塊的權(quán)重分配失衡。

2.3 MAPF-ALNS2+算法流程

本文基于MAPF-LNS2算法,通過增強(qiáng)ALNS模塊得到改進(jìn)算法MAPF-LNS2+,其中增強(qiáng)后的ALNS模塊稱為ALNS+模塊。MAPF-LNS2+保留了MAPF-LNS2算法的基礎(chǔ)框架,其具體流程為:首先,采用MAPF解搜索器獲得初始路徑,若該初始路徑上存在沖突,則調(diào)用ALNS模塊啟動(dòng)路徑的修補(bǔ)過程。在該過程中,ALNS模塊維護(hù)了3個(gè)鄰域搜索策略(基于碰撞的鄰域搜索策略、基于失敗的鄰域搜索策略、隨機(jī)的鄰域搜索策略)的權(quán)重(初始權(quán)重為1),并隨機(jī)選中某一鄰域搜索策略執(zhí)行,當(dāng)其執(zhí)行完成后更新權(quán)重。若路徑修補(bǔ)未完成,則重復(fù)該過程:ALNS模塊根據(jù)權(quán)重較高者選中鄰域搜索策略執(zhí)行,執(zhí)行完成后根據(jù)式(1)更新權(quán)重。ALNS+模塊的改進(jìn)在該重復(fù)過程中,具體而言,ALNS+模塊在鄰域搜索策略執(zhí)行完成后額外記錄了此次結(jié)果的改善率,在下次迭代過程中若某鄰域搜索策略被選中,則根據(jù)大小為N的時(shí)間窗口截取其最近N次改善率,并傳遞給改善率趨勢函數(shù)判斷其改善率是否呈現(xiàn)下降趨勢。若出現(xiàn)下降趨勢則進(jìn)行下一步?jīng)Q策,具體的決策過程如下:

(1) 如果其他兩個(gè)鄰域搜索策略都沒有被執(zhí)行過,則隨機(jī)選擇一個(gè)鄰域搜索策略。

(2) 如果其他兩個(gè)鄰域搜索策略都最近被執(zhí)行過,則選擇改善率較高的鄰域搜索策略。

被執(zhí)行的鄰域搜索策略會被重新分配權(quán)重,此時(shí)可能出現(xiàn)3種情況:

(1) 如果被執(zhí)行的鄰域搜索策略解決沖突的數(shù)量降低,則該策略的權(quán)值降低,被選擇的概率降低。

(2) 如果被執(zhí)行的鄰域搜索策略解決沖突的數(shù)量增加,則將該策略的權(quán)值提高至K。如果K比其他兩個(gè)策略的權(quán)重更高,則下一次迭代該鄰域搜索策略被執(zhí)行的概率最高。

(3) 如果被執(zhí)行的鄰域搜索策略解決沖突的數(shù)量保持不變,則權(quán)值保持不變。

由于改進(jìn)后的ALNS+模塊相比ALNS+模塊考慮了鄰域搜索策略最近N次的表現(xiàn)趨勢,因此可以及時(shí)修復(fù)過高的權(quán)重分配,從而避免其他更有“潛力”的鄰域搜索策略出現(xiàn)“饑餓”現(xiàn)象,ALNS+模塊的流程如圖2所示。

圖2 ALNS+模塊流程

3 MAPF-LNS2+算法的性能驗(yàn)證

為了分析驗(yàn)證ALNS+模塊以及MAPFLNS2+算法整體的改進(jìn)效果,本文設(shè)置了相關(guān)實(shí)驗(yàn):其中安排第1組實(shí)驗(yàn)對ALNS+與ALNS以及ALNS單獨(dú)運(yùn)行3種鄰域搜索策略的情況進(jìn)行了對比。實(shí)驗(yàn)使用MAPF基準(zhǔn)測試套件[1]中的隨機(jī)場景實(shí)例,在地圖“random-32-20”上生成了25個(gè)實(shí)例,每個(gè)實(shí)例具有不同的映射和代理數(shù)量。實(shí)驗(yàn)在阿里云ECS服務(wù)器“ecs.c8i.24xlarge”上進(jìn)行,服務(wù)器配置為16GB內(nèi)存,并設(shè)置了5min的運(yùn)行時(shí)間限制。其中選取隨機(jī)場景實(shí)例為25個(gè),時(shí)間窗口大小設(shè)置為8。實(shí)驗(yàn)結(jié)果如表1所示。表中,R、F、C分別為ALNS模塊在單一運(yùn)行基于碰撞鄰域搜索策略、基于失敗鄰域搜索策略、基于隨機(jī)鄰域搜索策略的情況,后文簡稱R、F、C 3種策略;A表示ALNS模塊,后文簡稱A 策略;A+表示ALNS+模塊,后文簡稱A+策略。其中,算法的運(yùn)行時(shí)間為25個(gè)場景實(shí)例中成功實(shí)例運(yùn)行時(shí)間的平均值。

表1 5種策略的運(yùn)行時(shí)間對比 s

由表1可知,R、F、C、A、A+ 5種策略在智能體數(shù)量設(shè)置不同的場景中,A+策略始終保持了最低運(yùn)行時(shí)間,相較于A 策略,其運(yùn)行時(shí)間降低了9%至65%。此現(xiàn)象證實(shí)了ALNS+模塊相較于ALNS模塊本身在運(yùn)行時(shí)間方面的優(yōu)勢。橫向?qū)Ρ缺?中的數(shù)據(jù)可以發(fā)現(xiàn),5種策略的運(yùn)行時(shí)間在智能體數(shù)量不同的場景下各有其優(yōu)勢,而隨著智能體數(shù)量逐漸增加,A 和A+策略的優(yōu)勢更加顯現(xiàn),且在運(yùn)行時(shí)間方面A+策略始終優(yōu)于A策略。

圖3為5種策略的運(yùn)行時(shí)間變化趨勢。在智能體數(shù)量逐漸上升過程中,算法運(yùn)行時(shí)間的改進(jìn)有下降趨勢,圖中折線的斜率反映了算法運(yùn)行時(shí)間的變化增速,由于是最小化問題,更大的斜率則表明了算法具有更低的改進(jìn)效果。尤其在智能體數(shù)量為360至400時(shí),斜率出現(xiàn)了最明顯的增大趨勢。上述實(shí)驗(yàn)現(xiàn)象可以解釋說明:ALNS+由于在改進(jìn)上增加了“改善率統(tǒng)計(jì)”和“改善率趨勢判斷”機(jī)制,因而產(chǎn)生了額外的開銷。在智能體數(shù)量較少時(shí),算法本身運(yùn)行時(shí)間較短,因此無法呈現(xiàn)明顯優(yōu)勢。隨著智能體數(shù)量的增加,額外開銷與算法本身運(yùn)行時(shí)間的比重會大大降低,則體現(xiàn)了明顯的改進(jìn)效果。當(dāng)繼續(xù)增大場景中智能體的數(shù)量使其達(dá)到某一閾值時(shí),ALNS+模塊的改進(jìn)效果則會有所下降。通過參數(shù)調(diào)整可以保持ALNS+模塊在不同場景中的優(yōu)勢,過高或過低的時(shí)間窗口大小都會影響“改善率趨勢”的判斷,因而直接影響ALNS+模塊的改進(jìn)效果,但減少時(shí)間窗口大小會降低改進(jìn)機(jī)制的計(jì)算開銷。通過參數(shù)修正對算法進(jìn)行調(diào)優(yōu),能夠找到性能提升和額外開銷的平衡,保證ALNS+模塊的最大優(yōu)勢。多次實(shí)驗(yàn)發(fā)現(xiàn),在改善效果較為明顯的場景中,時(shí)間窗口大小的合理值在4到8之間;對于無明顯改進(jìn)效果的場景中,時(shí)間窗口大小為0時(shí),額外開銷最小。由表1最后一行數(shù)據(jù)可知,單獨(dú)執(zhí)行R、F、C 3種策略時(shí),解決智能體密集場景的能力有所不足。由于ALNS+模塊依賴于3種基本的鄰域搜索策略,某一時(shí)刻只執(zhí)行單一的鄰域搜索策略,因而會降低改進(jìn)效果。

圖3 5種策略的運(yùn)行時(shí)間變化趨勢

第2 組實(shí)驗(yàn)對比了MAPF-LNS2+算法和MAPF-LNS2算法在更短限制時(shí)間下的成功率。本組實(shí)驗(yàn)的最大限制時(shí)間分別設(shè)置為30、60、90s,其他參數(shù)與第1組實(shí)驗(yàn)的設(shè)置相同。表2展示了對比結(jié)果,其中算法的成功率為成功的實(shí)例數(shù)量與場景實(shí)例總數(shù)的比值。

表2 算法成功率對比結(jié)果

由表2可知,① 在同一智能體數(shù)量下,逐漸增加算法運(yùn)行限制時(shí)間,以及同一限制時(shí)間下,若逐漸增加智能體的數(shù)量,算法的成功率都會有所降低;② 當(dāng)設(shè)置智能體數(shù)量為400時(shí),MAPF-LNS2和MAPF-LNS2+算法的成功率最低為28%和44%;③ 相同限制時(shí)間和智能體數(shù)量下,在成功率方面,MAPF-LNS2+始終優(yōu)于MAPF-LNS2。實(shí)現(xiàn)現(xiàn)象②③表明了MAPF-LNS2+相比MAPFLNS2算法具有較好的成功率表現(xiàn),但當(dāng)場景中智能體較為密集時(shí),其表現(xiàn)效果較差。此外實(shí)驗(yàn)現(xiàn)象①額外說明了:增加限制時(shí)間或降低智能體數(shù)量可有效增加算法的成功率。上述實(shí)驗(yàn)現(xiàn)象可以解釋說明:MAPF-LNS2+算法由于引入了ALNS+模塊,因此一定程度上降低了算法的運(yùn)行時(shí)間,在相同智能體數(shù)量和時(shí)間限制下,其成功率更高。但在智能體數(shù)量較為密集的場景中,參考表2數(shù)據(jù)可知“ALNS+模塊在智能體較為密集場景下表現(xiàn)有所不足”,造成了算法的成功率降低。

4 結(jié) 論

針對MAPF-LNS2算法中的ALNS模塊,存在分配鄰域搜索策略權(quán)重時(shí)產(chǎn)生額外算法運(yùn)行時(shí)間損耗的問題。通過引入改善率統(tǒng)計(jì)和時(shí)間窗口等機(jī)制提出MAPF-LNS2+算法。對比實(shí)驗(yàn)結(jié)果顯示,MAPF-LNS2+算法在運(yùn)行時(shí)間和成功率方面均表現(xiàn)最佳,其運(yùn)行時(shí)間最高降低了65.1%,成功率最大提升了16%。改進(jìn)效果表明,在對任務(wù)實(shí)時(shí)性要求較高的應(yīng)用場景,例如自動(dòng)化倉儲系統(tǒng)中,MAPF-LNS2+算法展現(xiàn)出顯著的優(yōu)越性,能夠迅速找到解決方案,并有效縮短訂單完成時(shí)間。