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

(上海電機學院 電子信息學院, 上海 201306)

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

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

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

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

1 MAPF-LNS2算法

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

圖1 MAPF-LNS2算法基本流程

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

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

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

2 MAPF-LNS2+算法

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

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

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

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

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

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

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

2.2 改善率趨勢的判斷

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

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

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

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

2.3 MAPF-ALNS2+算法流程

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

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

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

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

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

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

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

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

圖2 ALNS+模塊流程

3 MAPF-LNS2+算法的性能驗證

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

表1 5種策略的運行時間對比 s

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

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

圖3 5種策略的運行時間變化趨勢

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

表2 算法成功率對比結果

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

4 結 論

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