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

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

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

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

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

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

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

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

1 問題描述

1.1 MAPF 問題定義

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

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

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

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

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

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

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

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

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

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

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

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

2.1 HCA* 算法

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

CA*算法在單機(jī)A*搜索過程中使用曼哈頓距離作為啟發(fā)函數(shù),然而該方式在復(fù)雜環(huán)境中的表現(xiàn)較差.因此,Silver[19]在CA*框架下增設(shè)啟發(fā)函數(shù)計算層構(gòu)造HCA*算法,并使用RRA*從目標(biāo)點到當(dāng)前點進(jìn)行反向A*搜索,以獲得當(dāng)前點到目標(biāo)點的實際距離,將該距離作為啟發(fā)函數(shù),進(jìn)一步提高了算法的搜索效率.

2.2 降約束求解

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

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

2.3 討價還價博弈機(jī)制

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

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

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

1)基本思想

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

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

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

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

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

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

表1 單點單封堵類型路徑規(guī)劃結(jié)果Table 1 Solution of the single-site and single-blocking

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

表3 多點多封堵類型路徑規(guī)劃結(jié)果Table 3 Solution of the multi-site and multi-blocking

2)單點多封堵問題

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

3)多點多封堵問題

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

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

2.4 HCA* 搜索熔斷機(jī)制

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

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

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

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

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

在此基礎(chǔ)上,通過設(shè)置靜態(tài)熔斷機(jī)制來限制單機(jī)規(guī)劃層A*搜索的總次數(shù),以對動態(tài)熔斷機(jī)制進(jìn)行補(bǔ)充,并與其形成“或” 邏輯關(guān)系.A*算法在搜索過程中將逐輪地不斷執(zhí)行節(jié)點擴(kuò)展,并對擴(kuò)展點進(jìn)行是否與其他機(jī)器人路徑存在沖突的有效性檢測,直至找到目標(biāo)點或Open 表為空.因此,以該過程中A*算法所執(zhí)行的輪數(shù)為對象,設(shè)置搜索輪數(shù)限制,當(dāng)輪數(shù)超過最大限制RL時,則跳出本次任務(wù)進(jìn)入下一機(jī)器人的規(guī)劃任務(wù)中,即

式中,Fs用于標(biāo)識搜索過程是否到達(dá)靜態(tài)熔斷閾值,R為本次單機(jī)任務(wù)中A*算法搜索主循環(huán)所執(zhí)行的輪數(shù),RL為最大輪數(shù)限制,可根據(jù)場景復(fù)雜度和任務(wù)規(guī)模進(jìn)行設(shè)置和調(diào)整,一般設(shè)為6 000～15 000之間.

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

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

算法1.B-IHCA＊ 算法

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

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

3 仿真實驗結(jié)果

3.1 實驗設(shè)置

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

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

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

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

表4 不同 Nrobot 規(guī)模對應(yīng)的求解限制時間Table 4 Time limits for different sizes of Nrobot

3.2 實驗I.小規(guī)模固定任務(wù)測試

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

表5 實驗I 參數(shù)設(shè)置Table 5 Parameters for Experiment I

圖10 8×8 地圖[11]及任務(wù)設(shè)置Fig.10 8×8 map[11] and its tasks

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

表6 實驗I 求解結(jié)果Table 6 Results of Experiment I

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

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

3.3 實驗II.大規(guī)模隨機(jī)任務(wù)測試

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

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

圖11 大規(guī)模隨機(jī)任務(wù)實驗地圖Fig.11 Maps for large scale randomized tasks

1)求解能力分析

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

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

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

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

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

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

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

2)求解質(zhì)量分析

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

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

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

4 結(jié)束語

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