基于討價還價博弈機制的B-IHCA* 多機器人路徑規劃算法

張凱翔 毛劍琳 向鳳紅 宣志瑋

當前,智能機器人的集群協作技術越來越受到國內外學者的廣泛關注[1].多機器人路徑規劃 (Multiagent path finding,MAPF) 作為集群協作的一項關鍵性問題[2],其主要任務是為群體中的每一個機器人找到一條從起點到終點且彼此間無沖突的路徑[3].MAPF 對提升集群協作的效率、質量和安全性有直接作用,因此在倉儲系統、交通控制、機場運營、軍資運輸等各領域都展現出了巨大的研究潛力和價值[4-5].

MAPF 問題是典型的NP-Hard 問題[6],其解空間規模與機器人數Nrobot、時間步Tstep均呈指數關系.當前,針對該問題的求解方法按擴展狀態的組合形式主要可分為耦合型算法和解耦型算法[7].其中,耦合型算法在求解思路上將所有機器人視為一個整體問題,擴展時考慮到每個機器人的潛在狀態組合,并在該狀態組合中搜尋可行路徑方案.耦合型算法具有完備性和最優性的特點,但其求解效率通常較低[8].如單機器人路徑規劃中使用廣泛的A*算法[9],若將其直接擴展到MAPF 問題,將由于搜索空間隨機器人數量和時間步的指數級增長而出現搜索空間爆炸現象,從而在很大程度上削弱了算法的求解能力.為改善搜索空間爆炸對耦合型算法造成的求解效率低、占用內存量大等突出問題[10],Standley[11]提出算子分解 (Operator decomposition,OD) 方法,通過引入單機擴展的中間態,對MAPF問題的搜索過程進行引導和剪枝,在一定程度上縮小了搜索空間規模.Sharon 等[12]提出增值樹搜索算法 (Increasing cost tree search,ICTS),以遞增的路徑代價為引導標準,對搜索過程進行剪枝,提升了算法的求解效率.但耦合型算法始終受限于搜索規模指數級增長的固有問題,隨著機器人數量的進一步增加,其在有限時間內的求解成功率將在很大程度上被削弱.

解耦型算法應用于求解更多機器人數量的問題場景,該類型算法將MAPF 問題在某種程度上降維到了多個獨立機器人的單機規劃問題[13],在獲得的單機器人路徑基礎上再進行路徑間的沖突判斷與處理.如Sharon 等[14]提出的基于沖突搜索算法(Conflict-cased search,CBS),將MAPF 問題分為沖突處理和單機路徑規劃兩個子問題,并構造了一個雙層框架分別在上下層對所屬子問題進行求解[15].在此基礎上,Li 等[16]針對CBS 算法在頂層沖突樹擴展時可能出現的子節點重復問題,提出不相交分割 (Disjoint splitting) 方法對沖突樹進行剪枝,從而避免了大量重復搜索工作,進一步提升了搜索效率.CBS 算法具備最優性特點,并提供了一個清晰的問題求解框架用于后續的研究和改進工作[17-18].然而,當存在沖突時,該類型算法在上層僅對沖突的雙方作單獨的帶約束重新規劃,并沒有考慮到其他機器人對兩者的影響.當在窄道環境或問題場景高度耦合時,容易陷入解決完一個沖突又生成新沖突的狀態,由此反復循環,從而導致該方法難以得到可行解.

解耦型算法的另一類模式是在單機規劃的同時即考慮沖突的避免,而不對兩者做分層處理.Silver[19]提出協作A*(Cooperative A*,CA*) 算法,按優先級順序[20]依次為每個機器人進行單機路徑規劃,并將前面規劃的高優先級路徑信息作為約束加入到后面機器人的規劃中.在此基礎上,為獲得更有效的單機規劃啟發函數,Silver[19]進一步提出了層級協作A*(Hierarchical CA*,HCA*) 算法,在增加的啟發函數計算層中執行反向搜索操作以獲得更為準確的距離啟發值,提高了搜索效率.由于在單機規劃的同時就考慮對其他機器人的沖突避免,該類型算法通常具有更高的求解效率,但無法保證求解結果的最優性[21],且求解成功率和路徑質量對機器人的優先級順序較為敏感[22].Li 等[23]通過建立無人機群的耦合度矩陣,再根據耦合度指標的高低進行各機器人的優先級分配,提高了算法在多機耦合場景中的解耦能力與穩定性.Wu 等[24]在分布式系統中分析了路徑的同調類 (Homology classes) 數量,并以備選路徑的多少來安排機器人的優先級順序,起到了平衡路徑總耗費與最大完工時間的作用,但求解過程未涉及終點封堵的類型,很可能因為前面高優先級機器人在終點位置阻擋了低優先級機器人的通過而使算法求解失敗.Yakovlev 等[25]提出加權的安全區間路徑規劃算法 (Weighted safe-interval path planning,WdSIPP),通過引入次優權重系數,提高了算法在大規模多機問題中的解耦效率.然而,在路徑高耦合的密集場景中,機器人間的擁塞與封堵問題更加凸顯,固定的排序規則往往難以適應問題場景的動態變化.

近年來,在多機協作問題中引入了博弈機制,為MAPF 問題的求解擴展了新的思路.李珣等[26]針對紡織車間中多搬運機器人的任務分配問題,引入博弈論中的Nash 均衡理論,在定義智能體對任務的偏好關系基礎上,通過多輪博弈和迭代過程,建立了全局最優的Nash 穩定分區.Wu 等[27]針對多智能體的動態任務分配問題,基于勢博弈法,設計了一種新的動態環境下分布式多智能體任務分配框架,并保證了任意Nash 均衡解的次優性在50%以內.鄭延斌等[28]在兩階段的路徑規劃算法中,采用博弈論構建多智能體之間的動態避障模型,并利用虛擬行動法來解決多個機器人在沖突位點的博弈問題及多Nash 均衡的選擇問題,減小了路徑總代價并提高了算法的收斂速度.

本文針對密集場景中的高耦合MAPF 問題,采用降約束求解策略并結合討價還價博弈機制,動態調整沖突機器人間的優先級順序以提高問題求解成功率.針對HCA*算法在求解過程中受到封堵的機器人,降低部分約束條件獲得一條降約束路徑并將其作為對高優先級沖突方的還價.在后續幾輪的討價還價過程中,以降約束路徑作為基準價,進而使得與之沖突的高優先級機器人妥協并變更路徑.由此間接調整沖突機器人間的優先級順序,并使得整體路徑沖突逐漸消解,獲得可行解.進一步,在HCA*底層中加入熔斷機制,避免原始HCA*在單機搜索過程中陷于過長搜索或死循環狀態.通過熔斷機制與討價還價博弈機制相結合,對規劃過程中的過長路徑進行熔斷和重新規劃,以使路徑總代價指標獲得改善.通過多種算例仿真實驗對算法的性能進行驗證.

1 問題描述

1.1 MAPF 問題定義

MAPF 問題定義為: 在無向連通圖G=(V,E)中,存在由Nrobot個機器人組成的機器人群體A,如圖1 所示,每個機器人{ai A|i1,2,···,Nrobot}均有各自的起點si和終點gi.系統需為每個機器人ai規劃出一條從起點到終點的路徑pi,且任意機器人ai與aj的路徑pi與pj間不能發生沖突[29].在此基礎上,令所有機器人的路徑代價總和最小[30]是本文的優化目標.

圖1 MAPF 問題描述Fig.1 MAPF problem description

考慮勻速離散場景,MAPF 問題的沖突類型主要分為兩類: 位置沖突和相向沖突[31].其中,位置沖突指兩個機器人在相同的時刻占據相同的位置,如圖1 中a2與a3將在t1時刻共同占據地圖點v(2,2)的位置.相向沖突指兩個機器人在前后時間步內發生相向移動,如點vi(2,3)與點vj(2,4) 構成的邊e(vi,vj)上,a1與a3將在t[2,3] 時間段內發生相向移動,從而造成兩者的對撞.由此,MAPF問題的數學描述如下[32]:

式中,xi(e)為決策變量,表示ai是否經過邊e.δ+(v)(δ-(v))表示流入(流出)節點v的邊集.T為時間步t的最大值.VT為有向網絡圖的節點集,由地圖點集V隨時間步t不斷擴展所構成,ET為VT對應的有向圖邊集,其指向為下一個時間步的地圖鄰域.Li表示實際地圖中ai從起點si到終點gi的最短路徑長度,uf表示任意具有最小總代價解的最大完工時間上界.由該模型可知,MAPF 問題構造了帶時間維的多物網絡流,其網絡規模以實際地圖為基礎,并隨著時間步t不斷擴增.其中,式(2)為各機器人的起點和終點約束;式(3)為容量約束,式(4)為流守恒約束,兩者共同構成機器人在運動過程中的位置沖突與相向沖突約束;式(6)定義了各機器人的實際路徑代價值.

1.2 密集場景中的占位與擁塞問題

根據機器人到達終點后是否始終停留在終點位置,MAPF 問題分為One-shot和Long-term 兩種類型[32].本文針對典型的One-shot 類型開展研究,其在路徑規劃過程將發生占位問題,即部分機器人到達終點后將獨占該位置而持續影響其他機器人的通行,從而使得MAPF 問題的場景復雜度隨著過程的推進而動態增加.如圖2 所示,隨著a2和a3陸續到達指定位置,地圖將衍生出只容許單個機器人通過的關隘地形.而在更為密集的環境中,地圖的動態演變過程中將出現各類復雜地形甚至全封閉地形.

圖2 One-shot 類型MAPF 問題的終點占位現象Fig.2 Goal occupations in one-shot MAPF problem

在地圖的可通行區域被動態縮減的同時,路徑間的耦合度也在急劇升高.這將在很大程度上增加擁塞發生的概率.擁塞問題的出現將導致算法的求解效率和求解成功率顯著下降,并直接影響求解方案的路徑代價.

如圖3 的案例中,均存在一個擁塞點致使各機器人的路徑產生耦合.圖3(a)中,若按 (a1?a2) 的優先級順序,即先1 號后2 號,則a2將由于a1移動至關隘內部并占據通道而導致無法求解.反之,若采用 (a2?a1) 順序則可完成求解.圖3(b)中,若優先級順序為 (a1?a2?a3),則通過HCA*算法規劃所得路徑方案的總代價為24;若優先級順序為(a2?a1?a3),則HCA*所得總代價為21.

圖4 約束表使用與更新Fig.4 Use and update of constraint tables

綜上所述,在MAPF 問題中,場景復雜度和路徑耦合度隨過程的推進而動態增加.尤其在機器人數量更多的密集場景中,其對算法的擁塞處理能力和沖突處理效率提出了更高的要求.優先級順序不再僅僅是影響現有算法的求解效率,而是更關系著問題能否順利求解.因此,在現有算法的基礎上,如何動態調整優先級順序以提高密集場景中MAPF問題的求解成功率和路徑工時質量是本文的研究目標.

2 基于討價還價博弈機制的B-IHCA*算法

2.1 HCA* 算法

HCA*是基于A*搜索的解耦型MAPF 算法,由CA*和反向回溯A*(Reverse resumable A*,RRA*)算法構成[19].其中,CA*在求解思路上將MAPF 問題分解為有前后聯系的單機路徑規劃問題,按優先級順序依次對機器人a1,a2,···,aNrobot做單機路徑規劃,并把前面規劃的機器人路徑信息作為障礙約束添加到后面的機器人規劃當中.即在單機A*搜索基礎上額外設立了一個約束表,當完成第i個機器人ai的路徑規劃后,便將該路徑信息pi放入約束表并與前面已有的列表項共同組成下一個機器人ai+1的帶時限障礙物約束,按順序依次執行上述操作,直至完成全部機器人的規劃方案.

CA*算法在單機A*搜索過程中使用曼哈頓距離作為啟發函數,然而該方式在復雜環境中的表現較差.因此,Silver[19]在CA*框架下增設啟發函數計算層構造HCA*算法,并使用RRA*從目標點到當前點進行反向A*搜索,以獲得當前點到目標點的實際距離,將該距離作為啟發函數,進一步提高了算法的搜索效率.

2.2 降約束求解

HCA*算法由于在單機規劃的同時已考慮了沖突避免,因此具有較好的求解效率.但其求解過程對機器人的優先級順序較為敏感,尤其在密集場景下,頻繁地占位與擁塞所產生的封堵問題將直接導致算法無法求解.對此,提出降約束求解策略.即在HCA*順序求解過程中,若當前機器人遇到約束表中高優先級機器人路徑的阻塞而無法抵達終點時,則去除約束表中的部分內容,降低約束條件再對其進行求解,以獲得該機器人的一條不完全滿足約束條件的路徑方案.

通過降約束求解方式,可使求解過程中遇到阻塞的機器人去除部分阻塞性約束以獲得或兩類降約束路徑.由此,順序求解過程得以繼續,并最終獲得所有機器人包含全約束路徑或降約束路徑在內的初步方案.

2.3 討價還價博弈機制

在降約束求解的基礎上,算法進一步的目標是通過討價還價博弈,調整沖突各方的妥協解,以期將方案中的降約束路徑或在進行多次協商后均轉為全約束路徑pi,B(B為最終求解總輪數),由此獲得全局無沖突的可行路徑方案.

以圖5 中3 類常見的封堵問題為例,闡述討價還價博弈機制.其中,單點單封堵問題為一個機器人在關隘封堵了后續一個機器人的通過;單點多封堵為一個機器人封堵了后續多個機器人的通過;多點多封堵為多個機器人分占關隘口封堵后續多個機器人的通過.

圖5 密集場景中典型封堵問題Fig.5 Typical blocking problems in dense scenarios

1)基本思想

如圖6 所示,對于單點單封堵問題,首先使用HCA*算法對各機器人進行順序求解,獲得a1的路徑p1,0并加入約束表,對a2出價p1,0.由于路徑p1,0在終點處對關隘通道進行封堵,導致a2在該約束下無法求解,則a2不同意a1的p1,0路徑方案,轉而采取降約束求解的方式.

圖6 討價還價博弈基本思路Fig.6 Basic example of bargaining game process

圖7 單點多封堵求解過程Fig.7 Solving process of the single-site and multi-blocking

圖8 多點多封堵問題降約束個體二次規劃Fig.8 Replanning of reduced constraint individuals for the multi-site and multi-blocking

采用不包含p1,0的欠約束表進行a2的降約束求解,獲得欠約束路徑,則a2以對a1進行還價.保留上述過程獲得的全約束表,清空欠約束表,進入討價還價環節.

從a1開始依次求解,與順序求解環節不同的是: 討價還價過程中每個待求機器人ai不再僅考慮高優先級的路徑約束,而需考慮除自身以外的其他所有機器人的全局約束,即在全約束表中包含除當前機器人外的所有路徑{?pj Pb ∪Pu ∪Pn|ji}.討價還價環節可進行多個輪次(文中設置上限BL10),下一輪開始時將繼承上一輪獲得的全約束表,并將欠約束表清零.如圖6 中,在繼承順序求解環節所得全約束表的基礎上,a1放棄原先的p1,0路徑方案,轉而在考慮a2的基礎上重新規劃路徑得p1,1,并再次向a2出價.此時的新路徑方案p1,1由于考慮了的行進路徑,因此在封堵關隘前為a2預留了一定的行動間隙.在p1,1基礎上,a2得以重新規劃并獲得與a1無沖突的全約束路徑p2,1.由此,滿足所有路徑均為全約束路徑pi,B的條件,獲得最終結果 (p1,1,p2,1),如表1 所示.

表1 單點單封堵類型路徑規劃結果Table 1 Solution of the single-site and single-blocking

表2 單點多封堵類型路徑規劃結果Table 2 Solution of the single-site and multi-blocking

表3 多點多封堵類型路徑規劃結果Table 3 Solution of the multi-site and multi-blocking

2)單點多封堵問題

通過欠約束表添加前后的約束關系,單點多封堵問題中的被封堵對象形成彼此間無沖突的降約束路徑方案,并以此作為一個整體與單一的封堵方形成對立,使得問題得以簡化為單點單封堵類型,進而得以求解.

3)多點多封堵問題

二次規劃作為一個獨立模塊,位于主體求解環節即順序求解或每一輪的討價還價之后.其求解過程參照討價還價環節,并設置二次規劃全約束表和零約束表.其中,二次規劃全約束表繼承本輪主體求解環節所得的欠約束表信息.二次規劃將執行單輪的求解任務,求解過程中每個降約束個體ai需考慮除自身以外的其他所有降約束路徑的約束,即在二次規劃全約束表中包含除當前機器人以外的所有降約束路徑{?pj Pu ∪Pn|ji},依次對降約束個體進行求解,并在求解完成后用所得結果對本輪主體求解結果中對應個體的路徑進行更新.

通過二次規劃,可將降約束路徑中的沖突問題轉換為單點多封堵問題,從而獲得無沖突的降約束路徑整體方案.在此基礎上逐層遞進,使得多點多封堵問題最終簡化為單點單封堵問題,并獲得求解.

2.4 HCA* 搜索熔斷機制

在原始HCA*算法的單機路徑搜索過程中加入熔斷機制,以改善因長時繞道而造成的路徑總體代價增加以及關口死循環而造成的求解效率下降等問題.

如圖9(a)所示,由于高優先級的a1,a2到達終點并阻礙a3的通過,因此a3需繞道左邊關口通行,在很大程度上增加了路徑代價.更進一步,若形成圖9(b)的全封閉地形,則a3由于無法通過該關口,將返回之前搜索過的位置并以時間步為區分進行反復搜索和擴展,形成死循環狀態.因此,需要在HCA*算法的單機規劃過程中設置相應的熔斷機制.當發現長時繞道,尤其是死循環時將其強制退出,并進入到下一個單機規劃任務中.

圖9 HCA* 底層算法低效搜索狀態Fig.9 Inefficient searching in underlying of HCA*

通過對比單機規劃層中A*算法的已擴展節點數 (Ns)和啟發函數計算層中RRA*算法的已擴展節點數 (Nr),為HCA*算法設置動態熔斷機制.其中,單機規劃層使用時空A*算法,對于相同坐標位置的節點可重復擴展并以時間步作為區分;啟發函數計算層的RRA*只有空間維度,相同位置的節點不重復擴展.由于單機規劃層A*算法的新增節點需先調用RRA*以獲得該坐標位置的啟發函數值,因此,單機規劃A*中的已擴展節點(close-sp)是由RRA*中的已擴展節點(close-rra)的子集以時間步擴展的方式組合而成.在正常沒有阻塞的情況下,Ns要小于Nr;而在路徑發生部分堵塞的情況下,Ns將隨著時間維的擴展而激增.由此,通過對比Ns和Nr的數值關系而為HCA*算法設置動態熔斷機制,即

式中,Fd為True 時,表示到達動態熔斷閾值,A*算法將停止本次搜索任務并進入下一個任務;Fd為False 時,A*算法將繼續本次搜索任務直至求解完畢或到達動態熔斷閾值.ω為擁堵緩沖系數,用于緩沖暫時性的擁堵以減小誤判的概率,ω可根據地圖場景的復雜度和機器人數量進行設置和動態調整,一般設為 2 ～12 之間.

在此基礎上,通過設置靜態熔斷機制來限制單機規劃層A*搜索的總次數,以對動態熔斷機制進行補充,并與其形成“或” 邏輯關系.A*算法在搜索過程中將逐輪地不斷執行節點擴展,并對擴展點進行是否與其他機器人路徑存在沖突的有效性檢測,直至找到目標點或Open 表為空.因此,以該過程中A*算法所執行的輪數為對象,設置搜索輪數限制,當輪數超過最大限制RL時,則跳出本次任務進入下一機器人的規劃任務中,即

式中,Fs用于標識搜索過程是否到達靜態熔斷閾值,R為本次單機任務中A*算法搜索主循環所執行的輪數,RL為最大輪數限制,可根據場景復雜度和任務規模進行設置和調整,一般設為6 000～15 000之間.

2.5 基于討價還價博弈機制的B-IHCA* 算法

綜合上述分析,通過討價還價博弈機制構造求解框架并加入帶熔斷機制的改進HCA*算法作為內核,形成基于討價還價博弈機制的改進HCA*(Bargaining game based improving HCA*,B-IHCA*)多機器人路徑規劃算法,如算法1 所示.

算法1.B-IHCA＊ 算法

算法1 整體由外層的討價還價博弈框架嵌套多個內層帶熔斷機制的A*算法(算法2)構成.算法1 中,各機器人首先進行全約束求解(步驟4和步驟5),若無法求解,再進行降約束求解(步驟6～10),并對欠約束表和全約束表進行更新(步驟11～13).在完成每1 輪的主體求解環節后,執行二次規劃(步驟18～ 26),對獲得的降約束路徑進行再調整.其中,pi為機器人ai的路徑,P為全體路徑集,At為求解過程中的降約束個體集;Fr用于保存全約束表中各機器人的路徑信息,Fc用于保存全約束表中各機器人的終點信息,兩者共同構成全約束表;Ur和Uc共同構成欠約束表.

算法2 (子模塊).帶熔斷A* 搜索

3 仿真實驗結果

3.1 實驗設置

為分析算法對不同密集度地圖的求解性能,采用參考文獻中的典型地圖算例進行仿真實驗,分別為 8×8地圖[11],20×20地圖[16]和32×32 地圖[33].這些典型地圖展示了不同的密集程度和地形特征.

為更好地體現地圖及其測試算例的特征,設定環境密集指數α和機器密集指數β,定義如式(9)和式(10)所示.式中,Ntotal為地圖柵格總數,Nobstacle為障礙柵格數量,Nrobot為機器人總數.

由此,設置兩類實驗,實驗I 為固定任務,被測試算例Nrobot固定且起點、終點由人為設定;實驗II 為隨機任務,分別在各實驗地圖上測試6 組不同Nrobot規模的任務,且起點、終點均隨機生成.

分別采用CBS[14]、CBS-DS[16]、HCA*[19]、Wd-SIPP[25]算法與本文的B-IHCA*算法對測試算例進行求解.其中,為平衡求解成功率與路徑質量,Wd-SIPP 算法次優權重系數設置為w1.75,并設置w1.01作為路徑質量對照[25].所有算法均在AMD Ryzen 4800 處理器,內存為16 GB 的PC 機上以Python 程序運行.針對任務Nrobot的不同規模,設置相應求解限制時間如表4 所示,所有算法需在限制時間內完成對問題的求解,超出限制時間則視為求解失敗.

表4 不同 Nrobot 規模對應的求解限制時間Table 4 Time limits for different sizes of Nrobot

3.2 實驗I.小規模固定任務測試

采用8×8地圖[11],并設定10 個機器人的起始點和終點如圖10 所示,其他相關實驗參數設置及其指標如表5 所示.該算例中,可以發現(2,5)為一個關隘且被a2占據,阻擋了低優先級的a3,a4通過.同時,a8,a10的起點各占據一個通道,在它們到達終點后將使圖中(4,2),(7,1)等位置點成為地圖的新增關隘,對任務環境造成進一步的擁塞和限制.

表5 實驗I 參數設置Table 5 Parameters for Experiment I

圖10 8×8 地圖[11]及任務設置Fig.10 8×8 map[11] and its tasks

各算法對圖10 算例的測試結果如表6 所示.表6 中,若算法在限制時間內無法完成對該算例的求解,則結果以NA 表示;若在限制時間內完成求解任務,則記錄實際的路徑總代價指標.

表6 實驗I 求解結果Table 6 Results of Experiment I

由表6 可知,由于該算例的任務構造了多個動態關隘,形成較為復雜的地形結構,只有CBS-DS與B-IHCA*算法在限定時間內完成了求解任務.從結果來看,B-IHCA*相較于CBS-DS 算法在路徑總代價上有所增加,但在求解時間上具有明顯優勢.此外,B-IHCA*算法對該任務的求解過程共經過兩輪,各階段的路徑約束情況及沖突信息如表7 所示.

上述結果表明,B-IHCA*算法在其他算法難以有效求解的高耦合算例中,通過討價還價間接調整了沖突機器人的優先級順序,有效提高了求解成功率.此外,結合表7 的兩輪求解過程可知,在原始HCA*對a3,a4的單機規劃陷入死循環時,本文設置的熔斷機制及時地進行了熔斷操作,并進入下一個規劃任務,有效避免了計算資源和時間的浪費.

3.3 實驗II.大規模隨機任務測試

采用 20×20、32×32 等不同規格且環境密集度依次增加的4 類地圖如圖11 所示,每類地圖各設置6 組機器人,每組機器人均測試20 次隨機任務.其中,圖11(b)由本文方法根據隨機機制生成.此外,若圖內存在不可達點,則視為障礙物.各地圖的環境密集指數α與B-IHCA*算法RL參數設置如表8 所示,其余各數量組設置及其對應的相關參數如表9 所示.

表8 實驗II 參數設置 (1)Table 8 The parameters for Experiment II (1)

圖11 大規模隨機任務實驗地圖Fig.11 Maps for large scale randomized tasks

1)求解能力分析

各算法的求解成功率以及求解時間的離散分布統計結果如圖12 所示.其中,若算例在限制時間內無法求解,則以限制時間作為統計時間.同時,為驗證所提二次規劃模塊的作用,圖12 在求解成功率的測試中加入B-IHCA*算法不帶二次規劃模塊的求解結果: B-IHCA*(NR).

圖12 各算法測試成功率及求解時間離散分布統計Fig.12 Statistics on success rate and solution time of the tested algorithms

從圖12 中可以看出,B-IHCA*算法相較于對比算法在求解成功率和穩定性上均有較大優勢.其中,CBS 與CBS-DS 算法由于在密集場景中,上層最優搜索的擴展節點數量激增,求解能力限制在50 個以內.HCA*算法求解成功率則相對更高,這是由于HCA*算法以損失路徑質量作為代價,求解能力得到增強.但隨著機器人數量增加到80 個以上時,HCA*算法的求解成功率出現明顯下降.Wd-SIPP 算法在HCA*的基礎上有進一步改善,表明其對較大規模問題具有更為高效和靈活的解空間探索能力,但當問題規模增加到上百個機器人時,由于機器人間擁塞和封堵概率的增加,其求解成功率也降到60%以下.本文的B-IHCA*算法通過動態消解機器人間的封堵問題,在上百個機器人的任務規模中,始終能夠保證80%以上的求解成功率.

同時,從B-IHCA*(NR)與B-IHCA*的對比中可以發現,不帶二次規劃模塊的B-IHCA*(NR) 在圖12(c)和圖12(d)的高數量段中,求解成功率較B-IHCA*出現下降.表明在α值更大的blocked-20與room 等地圖環境中,更易出現多點多封堵問題,而二次規劃起到了進一步提升算法求解能力的作用.

此外,CBS和CBS-DS 算法對機器密集度參數β更為敏感,即在β較大的blocked-10 與random-15 地圖的測試組上,CBS和CBS-DS 算法的求解成功率下降更快,這是由于其所需處理的沖突節點數量隨β激增所致.而HCA*、WdSIPP和B-IHCA*算法在β參數升高時下降趨勢較平緩,因為其所需避免的沖突約束量與β只呈比例關系,說明該類型算法對高密集度場景中可調度空間的探索度更好.

在求解時間上,由圖12 中可以發現,B-IHCA*算法在中位數值和數據波動方面較CBS和CBSDS 算法均有更好的表現,表明B-IHCA*繼承了HCA*算法高效的特點.在低數量段上,B-IHCA*與HCA*算法的時間分布基本一致,并在中位數上接近求解效率最高的WdSIPP (1.75)算法.在高數量段上,B-IHCA*算法的數據波動小于WdSIPP (1.01)和WdSIPP (1.75) 算法,同時可以看出,B-IHCA*的下四分位和下邊緣接近HCA*算法,甚至在某些數量段要低于HCA*算法.這是因為熔斷機制對長時繞道的問題進行了及時處理,提高了算法的求解效率,表明B-IHCA*在大規模問題中具有更好的效率表現.

圖13 展示了B-IHCA*算法在4 類地圖最高數量段其中一個算例的求解結果.圖13 中,為避免同一柵格內的路徑重疊顯示,對各路徑做了偏移處理,每個機器人路徑在柵格內均有固定且彼此不重疊的顯示位置.從圖13 中可以發現,部分窄通道或關隘位置的路徑耦合度極高,成為限制HCA*算法求解性能的重要因素.通過討價還價博弈機制,B-IHCA*將擁塞機器人的優先級順序進行調整,逐步消解封堵,獲得可行解,充分表明了該算法對密集場景中高耦合MAPF 問題的求解優勢.

2)求解質量分析

在此基礎上,進一步對各算法所規劃方案的路徑總代價進行分析.由于求解成功率的差異,平均總代價需在公共算例的基礎上做統計分析.公共算例為同一數量段的20 個測試算例中,至少2 種算法能共同求解的算例.統計結果如表10 所示,表中,“NA” 表示該項目可統計數量為0,“—” 表示該項目可統計數量小于5 個.此外,對B-IHCA*求解輪數的統計分為兩類: 一類為所對比的公共算例的平均求解輪數;另一類為剩余未進行對比且可求解的算例的平均求解輪數.

由表10 可知,B-IHCA*在各個數量段上的規劃方案平均總代價相較于HCA*、WdSIPP (1.75)算法均有一定程度的改善,并普遍優于WdSIPP (1.01)所得結果,表明B-IHCA*通過熔斷和調解,有效地優化了路徑的長時繞道問題.在與CBS、CBS-DS兩類具有最優性的算法對比中,B-IHCA*的路徑代價與其差距均在2.2%以內.

從B-IHCA*算法的求解輪數中可以發現,公共算例平均經過1 輪的討價還價博弈即可完成求解.而對于其他算法難以求解的非公共算例,B-IHCA*也只需要經過平均2 輪次的博弈與調解,便可獲得求解.表明本文的博弈機制在高度擁塞的密集環境中,具有較高的沖突化解效率.同時,路徑優化效果與求解輪數呈正相關,求解輪數越多,則算法對過長路徑的調整程度越大,優化效果也越明顯.由于本文在測試中的主要目標是在限定的時間內以最快的方式獲得可行解,因此在求解輪數方面并未充分利用給定的限制時間.若在限制時間內,通過適當調整熔斷閾值、增加求解輪數,路徑優化效果可進一步提高.

4 結束語

針對密集場景中的MAPF 問題,在HCA*算法基礎上,引入降約束求解策略、討價還價博弈機制和搜索熔斷機制構造B-IHCA*算法.對順序求解過程中遇到阻礙的機器人采取降約束求解策略獲得降約束解,以該解作為還價方案,結合多輪討價還價過程,間接對沖突機器人的優先級順序進行動態調整,消解沖突,提高了算法的求解成功率.通過設置底層A*算法的搜索熔斷機制,有效避免了由于高優先級機器人的阻擋而使搜索陷于過長或反復無效搜索的狀態,減少了HCA*算法的平均無效求解時間.仿真結果表明,通過討價還價博弈與熔斷機制的相互配合,使得B-IHCA*算法對多類地圖的測試算例較現有方法在求解成功率上更具優勢,在機器人數量達到上百個的高度耦合環境中依舊具有較好的求解性能,并在路徑總代價指標上較HCA*、WdSIPP等算法有所改善,驗證了算法的有效性.