施曉航,徐勇勤

(1.95828部隊(duì),西安 710089; 2.上海機(jī)電工程研究所,上海 201109)

0 引言

隨著社會的不斷發(fā)展,無人機(jī)在其中的角色愈發(fā)重要,在載荷運(yùn)輸、攝影娛樂、戰(zhàn)場偵察等各方面發(fā)揮著重要作用。目前,隨著傳感器技術(shù)以及同時(shí)定位與建圖(simultaneous localization and mapping,SLAM)技術(shù)的發(fā)展,搭載了功能更高級、性能更先進(jìn)的傳感器后的無人機(jī)在室內(nèi)室外未知環(huán)境中的自主探索工作具有巨大的潛力,被廣泛應(yīng)用于地形測繪、災(zāi)后救援、環(huán)境偵察等領(lǐng)域。

自主探索是指智能體,依靠自身傳感器和機(jī)載處理器在未知環(huán)境中實(shí)時(shí)閉環(huán)地感知、決策并規(guī)劃,獲取未知地圖的環(huán)境信息。本文中智能體指具有自主能力的旋翼無人機(jī)。而旋翼無人機(jī)憑借其較小和敏捷的特點(diǎn),常被應(yīng)用于復(fù)雜的小范圍場景中,相比其他智能體平臺,對自主探索的實(shí)時(shí)性與自主性有更高要求。在探索過程中,無人機(jī)感知局部環(huán)境信息自主決策下一觀測點(diǎn),并進(jìn)行路徑規(guī)劃驅(qū)使無人機(jī)前往觀測點(diǎn)獲取環(huán)境信息。如何高效地進(jìn)行自主探索并獲取完整的地圖信息一直以來都是無人機(jī)領(lǐng)域的熱門研究問題。盡管自主探索技術(shù)在近年來取得了顯著進(jìn)展,但大多數(shù)的研究工作都只關(guān)注于單架無人機(jī)的探索。而隨著探索場景的復(fù)雜化與探索任務(wù)的高效化,多機(jī)協(xié)同探索系統(tǒng)的優(yōu)越性日漸凸顯。多機(jī)系統(tǒng)[1]與單機(jī)相比,不僅能夠極大提升探索效率,還能提升探索任務(wù)完成的成功率。

多機(jī)協(xié)同自主探索技術(shù)是一項(xiàng)系統(tǒng)工程,如圖1所示。其可被劃分為感知、決策(未知環(huán)境探索策略、多機(jī)任務(wù)分配策略)以及規(guī)劃方法。感知主要解決“我在哪”的問題,指智能體以機(jī)載傳感器的局部感知結(jié)果為輸入,在線處理建模,輸出定位以及周圍環(huán)境信息。決策則是解決“我去哪”問題,指智能體根據(jù)當(dāng)前環(huán)境信息,自主決定下一局部目標(biāo)點(diǎn),而在協(xié)同系統(tǒng)中,決策問題擴(kuò)展為“誰去哪”問題,即需要考慮各智能體的任務(wù)分配。規(guī)劃解決“怎么去”問題,指智能體根據(jù)當(dāng)前定位、環(huán)境信息以及下一局部目標(biāo)點(diǎn),高效規(guī)劃輸出安全避碰的高質(zhì)量航跡,從而能夠被控制器真正執(zhí)行。

圖1 多機(jī)協(xié)同自主探索工作構(gòu)成

決策作為多機(jī)協(xié)同自主探索系統(tǒng)中關(guān)鍵一環(huán),其水平極大程度地影響了整個(gè)系統(tǒng)的效率。未知環(huán)境探索策略指設(shè)計(jì)未知地圖表達(dá)方式以及觀測點(diǎn)決策標(biāo)準(zhǔn)使無人機(jī)自主決策下一觀測點(diǎn)獲取環(huán)境信息。多機(jī)任務(wù)分配策略指針對已確定多個(gè)觀測點(diǎn)的多機(jī)系統(tǒng),進(jìn)行合理的任務(wù)量分配,使最大限度發(fā)揮協(xié)同優(yōu)勢。

因此,以旋翼無人機(jī)為對象,重點(diǎn)從未知環(huán)境探索策略和多機(jī)任務(wù)分配策略詳細(xì)回顧了多機(jī)協(xié)同自主探索技術(shù)的發(fā)展現(xiàn)狀,系統(tǒng)性地總結(jié)了各策略方法的思路內(nèi)涵。在此基礎(chǔ)上,根據(jù)當(dāng)前發(fā)展現(xiàn)狀,對多機(jī)協(xié)同探索技術(shù)的未來研究重點(diǎn)進(jìn)行展望,對本領(lǐng)域的研究工作具有一定的參考意義。

1 多機(jī)協(xié)同自主探索技術(shù)內(nèi)涵

1.1 自主探索

如圖2所示,自主探索的輸入是機(jī)載傳感器提供的當(dāng)前定位結(jié)果以及周圍局部環(huán)境信息,在提前給定的探索任務(wù)區(qū)域大小限制及牽引下,無人機(jī)通過自主決策,決定下一觀測點(diǎn)并高效規(guī)劃前往路徑實(shí)現(xiàn)未知區(qū)域環(huán)境信息的獲取,如此往復(fù),不斷擴(kuò)充已知環(huán)境區(qū)域,直到完成任務(wù)。

自主探索則強(qiáng)調(diào)未知環(huán)境中的自主性,即要求無人機(jī)閉環(huán)、在線地完成探索任務(wù),其評價(jià)指標(biāo)可大致被分為兩類:覆蓋率和效率(路徑長度和時(shí)間)。而根據(jù)探索環(huán)境表達(dá)方式不同,自主探索一般被劃分為基于邊界(Frontier-based)[2-3]、基于采樣(Sampling-based)[4-6]2類,近年來,也涌現(xiàn)出了一批邊界和采樣結(jié)合[7-8]的方法。

1.2 多機(jī)協(xié)同自主探索系統(tǒng)

多機(jī)協(xié)同自主探索的核心是通過合理分配任務(wù)避免目標(biāo)重復(fù)沖突,高效規(guī)劃探索路徑,使每個(gè)無人機(jī)同時(shí)探索不同的區(qū)域得到特定目標(biāo)信息,最大程度發(fā)揮多機(jī)系統(tǒng)的優(yōu)勢。多機(jī)系統(tǒng)可根據(jù)控制決策機(jī)制的不同(見圖3),被分為集中式或分布式2種協(xié)同體系。

圖3 多機(jī)系統(tǒng)

在集中式的協(xié)同探索系統(tǒng)中,文獻(xiàn)[9-11]使用迭代分配方法,根據(jù)距離和環(huán)境信息增益通過貪婪策略選取無人機(jī)與對應(yīng)目標(biāo)配對。然而,這種策略只給每個(gè)無人機(jī)分配一個(gè)目標(biāo),當(dāng)多個(gè)無人機(jī)被分配到鄰近的目標(biāo)時(shí),該策略產(chǎn)生沖突無法有效分配目標(biāo)。為了解決該問題,文獻(xiàn)[12-13]提出了基于分割的目標(biāo)分配方法,將目標(biāo)區(qū)域進(jìn)行分割再分配。文獻(xiàn)[12]使用Voronoi圖將已偵察區(qū)域劃分為若干部分。通過將無人機(jī)分配到不同的部分區(qū)域而不是單個(gè)目標(biāo),使無人機(jī)在環(huán)境中分布得更均勻。類似地,文獻(xiàn)[13]使用廣度優(yōu)先探索的聚類算法對劃分區(qū)域進(jìn)行分組,并將它們分配給相應(yīng)無人機(jī)。此外,文獻(xiàn)[14-15]將目標(biāo)分配問題建模為多旅行商問題(multiple travelling salesman problem,mTSP)。因?yàn)槎嗦眯猩虇栴}實(shí)質(zhì)上是NP-hard問題,因此使用子問題劃分來求解得到近似最優(yōu)解。文獻(xiàn)[14]使用基于K-means的分類算法將所有目標(biāo)進(jìn)行分組并分配給各無人機(jī)。文獻(xiàn)[15]通過求解一個(gè)離散的最優(yōu)運(yùn)輸問題來找到所有目標(biāo)對于各無人機(jī)的分配,而每個(gè)無人機(jī)的最優(yōu)路徑則建模為TSP問題求解。而文獻(xiàn)[16]采用貪婪TSP算法,為每個(gè)無人機(jī)貪婪地分配一個(gè)偵察點(diǎn)集群。以上方法均是在集中式體系且假定通信完美的情況下成立的。

相比于集中式,分布式協(xié)同探索系統(tǒng)主要考慮通信質(zhì)量,即通信范圍和通信帶寬的問題,在共享定位和局部地圖的范圍和大小方面重點(diǎn)優(yōu)化。文獻(xiàn)[17]提出了第一個(gè)分布式的協(xié)同探索系統(tǒng),其中所有無人機(jī)共享地圖信息并分別移動到對應(yīng)最近的邊界中,但由于多個(gè)無人機(jī)可能移動到同一位置,協(xié)同效果并不好。因此,文獻(xiàn)[17-19]提出了基于拍賣機(jī)制的分布式協(xié)同方法。文獻(xiàn)[17-18]使用分布式單獨(dú)競價(jià)本地拍賣策略解決無人機(jī)間的沖突。而為了考慮無人機(jī)間共同的多個(gè)目標(biāo)的分配問題,文獻(xiàn)[19]制定了組合拍賣策略。除了基于拍賣的方法,文獻(xiàn)[20]將貪婪算法拓展應(yīng)用于分布式協(xié)同上,然而該過程通常需要無人機(jī)間進(jìn)行數(shù)輪通信。文獻(xiàn)[21]在文獻(xiàn)[20]的基礎(chǔ)上討論了不同目標(biāo)函數(shù)對分布式協(xié)同的效果。文獻(xiàn)[22]利用多無人機(jī)多目標(biāo)勢場將無人機(jī)分配到不同邊界。文獻(xiàn)[21]提出兩兩優(yōu)化方案,即通過無人機(jī)兩兩交互重新分配目標(biāo)。該方法由文獻(xiàn)[21]演化而來,而文獻(xiàn)[21]最初被用于解決無人機(jī)的協(xié)同控制問題。以上方法的一個(gè)共同缺點(diǎn)是需要多個(gè)無人機(jī)同時(shí)穩(wěn)定連接,故容易受到網(wǎng)絡(luò)不穩(wěn)定或延遲的影響使偵察效率降低。為了簡化對通信質(zhì)量的要求,減少無人機(jī)交互共享的數(shù)量極為關(guān)鍵。

綜上所述,從單機(jī)的自主探索發(fā)展到多機(jī)的協(xié)同探索,未知環(huán)境探索以及多機(jī)任務(wù)分配是研究的重點(diǎn)。本文將主要針對以上兩部分對多無人機(jī)的協(xié)同探索工作進(jìn)行介紹。

2 未知環(huán)境探索策略

2.1 基于邊界的自主探索

邊界是指未知區(qū)域與已知區(qū)域的邊界。其概念首先由Yamauchi[24]提出。如圖4所示,其基本思想是根據(jù)當(dāng)前的局部環(huán)境信息生成對應(yīng)的邊界輪廓,根據(jù)邊界生成一個(gè)或一系列的觀測點(diǎn),通過一定策略決定下一觀測點(diǎn)并通過路徑規(guī)劃導(dǎo)航至該觀測點(diǎn)。當(dāng)?shù)竭_(dá)該觀測點(diǎn)后,邊界信息更新,又更新生成新的觀測點(diǎn),如此往復(fù)驅(qū)動無人機(jī)完成整個(gè)環(huán)境的探索任務(wù)。早期的基于邊界的自主探索方法具有一定的局限性,其不僅邊界生成效率低,且通過邊界生成觀測點(diǎn)的策略不夠完善導(dǎo)致觀測點(diǎn)環(huán)境信息獲取效率低下。

圖4 基于邊界的自主探索方法

文獻(xiàn)[25]通過驗(yàn)證證明了邊界生成速度過慢會直接導(dǎo)致自主探索效率變低,其原因是當(dāng)邊界更新速度跟不上無人機(jī)運(yùn)動速度時(shí),無人機(jī)仍向上一次決定的觀測點(diǎn)移動,導(dǎo)致無人機(jī)可能會重復(fù)探索已知區(qū)域。為解決以上問題,出現(xiàn)了更多適用性更強(qiáng)的邊界檢測探索方法。文獻(xiàn)[26]利用三維占據(jù)地圖的八叉樹數(shù)據(jù)結(jié)構(gòu)提高邊界檢測效率。其本質(zhì)是憑借八叉樹葉子節(jié)點(diǎn)與根節(jié)點(diǎn)的連通性,將位于同一八叉樹分支的邊界視為一個(gè)簇,從而提高邊界的聚類效率。

在生成邊界后,觀測點(diǎn)的評估策略對探索效率亦十分重要。觀測點(diǎn)評估是指根據(jù)邊界信息決策一個(gè)或一系列觀測點(diǎn),這些觀測點(diǎn)往往作為路徑規(guī)劃的局部目標(biāo)點(diǎn)。

傳統(tǒng)的基于邊界的自主探索方法[24]最早貪婪地選擇邊界中距離當(dāng)前無人機(jī)位置歐氏距離最近的點(diǎn)作為下一觀測點(diǎn)。在此基礎(chǔ)上,文獻(xiàn)[27-29]考慮地圖的不確定性因素,提出采用歐氏距離和觀測點(diǎn)處可獲得的期望環(huán)境信息量組合作為觀測點(diǎn)的評估指標(biāo)。觀測點(diǎn)處可獲得的期望環(huán)境信息量實(shí)質(zhì)上是無人機(jī)在觀測點(diǎn)位置在傳感器視角限制下能夠覆蓋的邊界數(shù)量。但是,該策略由于使用的是歐式距離來表示代價(jià),容易產(chǎn)生不正確的代價(jià)估計(jì),因此在復(fù)雜環(huán)境中不太適用,尤其是當(dāng)無人機(jī)與觀測點(diǎn)之間存在較多障礙物時(shí)。因此,如圖5所示,文獻(xiàn)[26]采用A*算法規(guī)劃無人機(jī)當(dāng)前位置到觀測點(diǎn)的近似最優(yōu)無碰路徑,以此路徑長度作為距離懲罰項(xiàng)。在此基礎(chǔ)上,文獻(xiàn)[25]引入了方向改變代價(jià)懲罰項(xiàng),使無人機(jī)盡量保持連續(xù)飛行,進(jìn)而提高探索效率。

除此之外,文獻(xiàn)[24]采用基于隨機(jī)微分方程的策略,實(shí)現(xiàn)了在三維空間中的邊界搜尋。與文獻(xiàn)[24]不同,文獻(xiàn)[25]選擇傳感器視場范圍(field of view,FOV)內(nèi)的局部邊界信息而并非直接選擇最近的邊界作為觀測點(diǎn)。該策略的目的是使無人機(jī)的速度變化最小,即使因?yàn)橹匾?guī)劃頻率太高亦能使無人機(jī)一直保持較高的飛行速度。文獻(xiàn)[23]等對多無人機(jī)的協(xié)同探索問題進(jìn)行了深入研究,其基本思想是:首先通過構(gòu)建邊界的距離與角度的吸引函數(shù),然后構(gòu)建無人機(jī)間距離的分散函數(shù),優(yōu)化了探索環(huán)境的效率,改進(jìn)了邊界的自主探索算法。

2.2 基于采樣的自主探索

基于采樣的自主探索方法通過隨機(jī)采樣產(chǎn)生候選偵察點(diǎn),并評估其信息增益。其與下一最佳觀測點(diǎn)(next best view,NBV)思想類似,關(guān)鍵都在于通過重復(fù)計(jì)算獲得觀測點(diǎn)來獲取場景中的環(huán)境信息。

如圖6所示,該方法通常采用基于快速擴(kuò)展隨機(jī)樹(rapidly-exploring random tree,RRT)原理的算法在探索空間進(jìn)行采樣。利用RRT本身的節(jié)點(diǎn)擴(kuò)展特性進(jìn)行觀測點(diǎn)采樣,在隨機(jī)采樣確定節(jié)點(diǎn)的過程中,各節(jié)點(diǎn)之間的路徑也隨之確定,這些路徑還能被用作后續(xù)的規(guī)劃路徑。文獻(xiàn)[5]首先將NBV的概念引入三維環(huán)境的探索工作中,使用RRT算法以無人機(jī)當(dāng)前位置作為樹的根節(jié)點(diǎn),通過隨機(jī)采樣進(jìn)行支的隨機(jī)擴(kuò)展,在此同時(shí),計(jì)算采樣觀測點(diǎn)處的信息增益。預(yù)先設(shè)定采樣次數(shù)閾值,當(dāng)采樣次數(shù)達(dá)到最大次數(shù)后停止采樣,并對各分支的信息增益進(jìn)行評估,選擇增益最大的分支作為被使用的探索路徑。而在真正執(zhí)行中,當(dāng)無人機(jī)執(zhí)行完探索路徑的第一段后,將其他分段上的采樣觀測點(diǎn)作為種子重新進(jìn)行以上隨機(jī)采樣擴(kuò)展過程,如此往復(fù),直到覆蓋整個(gè)探索空間。由于整個(gè)過程與控制領(lǐng)域中的滾動時(shí)域理論相似,以上策略方法被稱為滾動時(shí)域NBV規(guī)劃器(receding horizon next best view planner,RH-NBVP)。在此基礎(chǔ)上,文獻(xiàn)[31]考慮了定位的不確定性,文獻(xiàn)[32]考慮了視覺感知限制,文獻(xiàn)[33]考慮了檢測的不穩(wěn)定性。

圖6 基于采樣的自主探索方法

RH-NBVP方法相比基于邊界的自主探索方法效率更高,但是,隨機(jī)采樣的思路難以獲得最佳偏航角導(dǎo)致遍歷偏航角的方法算力要求大且運(yùn)行速度慢。此外,RH-NBVP本質(zhì)上仍是RRT隨機(jī)采樣不斷重復(fù)構(gòu)建分支的思路,這使其在狹窄空間中易陷入局部最優(yōu)而在大范圍空間中擴(kuò)展效率較低。

針對RH-NBVP方法觀測點(diǎn)評估效率低的問題,文獻(xiàn)[30]通過降采樣方法減少信息增益計(jì)算需遍歷的體素?cái)?shù)量,由此加速觀測點(diǎn)的評估速度。針對RH-NBVP方法偏航角采樣效率低的問題。

基于采樣的自主探索方法因其單次查詢特性,導(dǎo)致該方法在探索大范圍復(fù)雜空間時(shí)易陷入局部最優(yōu)問題。針對該問題,文獻(xiàn)[34]提出保存已采樣獲得的節(jié)點(diǎn)并構(gòu)成歷史圖,在無人機(jī)進(jìn)行探索時(shí)亦實(shí)時(shí)維護(hù)更新該歷史圖,當(dāng)無人機(jī)在狹窄區(qū)域中陷入局部最優(yōu)時(shí),可通過歷史節(jié)點(diǎn)作為種子“跳出”局部最優(yōu)。但是,隨著地圖的不斷擴(kuò)大,尤其在大范圍場景中進(jìn)行探索任務(wù)時(shí),維護(hù)歷史圖的更新將會消耗巨大算力。因此,文獻(xiàn)[34]又通過構(gòu)建歐式有向距離場(Euclidean signed distance field,ESDF)[35-36]將節(jié)點(diǎn)向障礙物之間的空閑區(qū)域推進(jìn),由此將位置相近的類似節(jié)點(diǎn)融合,在減少樹節(jié)點(diǎn)規(guī)模的同時(shí)也保留了環(huán)境的骨架結(jié)構(gòu)。

除了使用RRT進(jìn)行采樣,文獻(xiàn)[37]提出將概率路線圖(probabilistic roadmap,PRM)用于基于采樣的自主探索工作中。其思路是在無人機(jī)傳感器范圍內(nèi)的區(qū)域進(jìn)行隨機(jī)采樣以實(shí)現(xiàn)增量式擴(kuò)展全局路線圖的生成,進(jìn)而構(gòu)建出能夠表達(dá)環(huán)境特征的三維拓?fù)浣Y(jié)構(gòu)圖,以此快速找到未知區(qū)域。在此基礎(chǔ)上,文獻(xiàn)[38]通過局部-全局相結(jié)合的采樣策略,增量式地構(gòu)建概率路線圖,能夠在具有簡單動態(tài)障礙物的環(huán)境中實(shí)現(xiàn)高效探索覆蓋。為了使飛行速度更快,文獻(xiàn)[39]提出對動態(tài)可行的運(yùn)動語義進(jìn)行隨機(jī)采樣的策略,首次將運(yùn)動語義應(yīng)用于自主探索工作中。

2.3 基于邊界和采樣組合的自主探索

基于邊界的方法簡單直接,但其必須首先生成完邊界后再通過評估決策觀測點(diǎn),效率較低。而基于采樣的方法通過隨機(jī)采樣產(chǎn)生候選觀測點(diǎn)再評估其信息增益篩選,該方法可顯式地量化每個(gè)候選觀測點(diǎn)的信息增益,但缺點(diǎn)是算力要求較高。因此,諸多研究者提出了將邊界和采樣方法相結(jié)合的自主探索思路。

文獻(xiàn)[40]提出基于邊界生成全局路徑再通過路徑采樣需探索局部區(qū)域的方法。文獻(xiàn)[41]討論了一種對邊界周圍進(jìn)行采樣來生成觀測點(diǎn)的方法,該方法能夠找到全局最短探索路徑。文獻(xiàn)[42]通過采樣方法找到能夠完全覆蓋邊界的探索路徑。

3 多機(jī)任務(wù)分配策略

相比于單機(jī)執(zhí)行任務(wù),多無人機(jī)系統(tǒng)由于執(zhí)行任務(wù)的智能體數(shù)量提升以及共享機(jī)制的加入,增加了最能體現(xiàn)多機(jī)協(xié)同優(yōu)勢的任務(wù)分配環(huán)節(jié)。

在多無人機(jī)協(xié)同探索未知環(huán)境任務(wù)中,各無人機(jī)獲取周圍環(huán)境信息并更新迭代觀測點(diǎn),再通過各無人機(jī)之間的協(xié)調(diào)策略將一系列觀測點(diǎn)統(tǒng)籌再分配給系統(tǒng)中特定的成員,使探索效率最大化。該問題常被建模為多機(jī)任務(wù)分配問題(multi-robot task allocation,MRTA)。

MRTA問題的實(shí)質(zhì)是解決系統(tǒng)中哪個(gè)無人機(jī)去執(zhí)行哪個(gè)特定任務(wù)效率最高的問題,是發(fā)揮系統(tǒng)協(xié)同效率的關(guān)鍵[43]隨著探索任務(wù)難度的升級、協(xié)同智能體數(shù)目的增加以及通信限制等各類因素,解決多機(jī)協(xié)同任務(wù)分配問題的關(guān)鍵在于如何對問題進(jìn)行準(zhǔn)確的建模。

3.1 基于物流模型的任務(wù)分配

在任務(wù)分配中,任務(wù)即為輸入,是各無人機(jī)已初步確定的對應(yīng)觀測點(diǎn);分配即為輸出,是共享信息后重分配的各無人機(jī)對應(yīng)觀測點(diǎn)。此外,一些研究工作還關(guān)注無人機(jī)探索路途中能夠獲得的環(huán)境增益[44],各無人機(jī)初步確定的觀測點(diǎn)不止一個(gè),于是還涉及這一系列觀測點(diǎn)按照何種順序前往的問題。該問題常被建模為多旅行商問題[45],其原理為約束每一個(gè)無人機(jī)至少分配一個(gè)目標(biāo)點(diǎn),并使得總成本最小化,成本可以被設(shè)計(jì)為距離或時(shí)間。如圖7所示,多旅行商問題的目標(biāo)是找到一組路徑,使得所有旅行商(各無人機(jī))訪問各自的城市(觀測點(diǎn))集合,并且每個(gè)城市只被一個(gè)旅行商訪問一次,并且最小化總路徑長度或最小化最長路徑長度。這個(gè)問題在實(shí)際應(yīng)用中具有很高的復(fù)雜性,因?yàn)樵诙鄠€(gè)旅行商之間需要合理地分配城市,并且需要考慮到各個(gè)旅行商的路徑長度。

圖7 多旅行商問題示意

在此基礎(chǔ)上,如圖8所示,通過考慮各無人機(jī)的工作量使任務(wù)負(fù)載分配更為合理,文獻(xiàn)[46]將多無人機(jī)協(xié)同探索中的任務(wù)分配問題建模為負(fù)載車輛運(yùn)送問題(capacitated vehicle routing problem,CVRP)以使系統(tǒng)中各無人機(jī)任務(wù)量平衡。相比mTSP問題,CVRP的建模思路可以將負(fù)載即工作量納入到約束中。

圖8 負(fù)載車輛運(yùn)送問題示意

近年來,任務(wù)分配算法發(fā)展迅速,大體上可被分為基于市場的方法和基于優(yōu)化的方法。在此基礎(chǔ)上,針對目前熱點(diǎn)研究問題和關(guān)注應(yīng)用實(shí)際,本文還將單獨(dú)討論考慮通訊限制的任務(wù)分配。

3.2 基于市場模型的任務(wù)分配

受經(jīng)濟(jì)學(xué)理論中重要的拍賣機(jī)制啟發(fā),基于市場的任務(wù)分配方法是協(xié)同系統(tǒng)中各無人機(jī)根據(jù)自身“處境”進(jìn)行競標(biāo)參與拍賣?！芭馁u商品”是各任務(wù),“競價(jià)價(jià)格”通常由“收益”和“成本”共同衡量,而“收益”和“成本”通過制定的“拍賣標(biāo)準(zhǔn)”決定。在拍賣市場理論指導(dǎo)下,整體系統(tǒng)通過優(yōu)化目標(biāo)函數(shù)以實(shí)現(xiàn)“利潤”的最大化。合同網(wǎng)協(xié)議[53]以及Trader-Bots方法[54]是拍賣方法中重要的兩類方法。

1) 基于合同網(wǎng)協(xié)議的拍賣算法

合同網(wǎng)協(xié)議(contract net protocal,CNP)是多智能體系統(tǒng)中的一種任務(wù)共享協(xié)議,其確定了系統(tǒng)中各無人機(jī)間進(jìn)行“談判競標(biāo)”時(shí)共同遵守的準(zhǔn)則?；诤贤W(wǎng)的拍賣算法的過程一般被劃分為以下4個(gè)階段:

a.招標(biāo):其中至少一個(gè)無人機(jī)擔(dān)任“拍賣商”,對其他無人機(jī)發(fā)布被競標(biāo)的任務(wù)。

b.投標(biāo):其他無人機(jī)接收到發(fā)布的任務(wù)信息后,擔(dān)任“投標(biāo)者”,根據(jù)目標(biāo)函數(shù)求得可出“競價(jià)”,并將此價(jià)格發(fā)送回“拍賣商”。

c.評價(jià):“拍賣商”接收各“投標(biāo)者”的出價(jià)后,根據(jù)優(yōu)化策略對各投標(biāo)者進(jìn)行評價(jià),最終確定“中標(biāo)者”。

d.履行:“中標(biāo)者”即為被選定的該任務(wù)分配的無人機(jī),接收任務(wù)并履行。重復(fù)以上過程,直到?jīng)]有新任務(wù)產(chǎn)生。

基于拍賣的任務(wù)分配方法在集中式和分布式系統(tǒng)中均適用。在集中式系統(tǒng)中,中央處理器作為“拍賣商”協(xié)調(diào)整個(gè)系統(tǒng),該系統(tǒng)具有全局優(yōu)勢但穩(wěn)定性不好,若中央處理器故障,那整個(gè)拍賣機(jī)制就整個(gè)癱瘓。因此,集中式的方法僅適合于小型環(huán)境的協(xié)同探索任務(wù)分配。而分布式系統(tǒng)中,每一個(gè)成員既能擔(dān)任“拍賣商”又能擔(dān)任“投標(biāo)者”,對環(huán)境變化和故障問題有較好的容錯(cuò)能力,但局部優(yōu)化不一定能夠?qū)崿F(xiàn)全局較優(yōu)解。因此,分布式的方法一般適用于大型環(huán)境的協(xié)同探索任務(wù)分配。

2) 基于Trader-Bots方法的拍賣算法

Trader-Bots方法借鑒了市場經(jīng)濟(jì)中個(gè)體能夠自由交換商品或服務(wù)并自由簽訂合同的核心思想,將整個(gè)無人機(jī)系統(tǒng)看作是一個(gè)經(jīng)濟(jì)體,系統(tǒng)中各智能體都被建模為“自由交易者”。在本方法中,目標(biāo)函數(shù)一方面要保證團(tuán)隊(duì)能夠順利完成所有任務(wù),并使“總利潤”最大化,另一方面各無人機(jī)間要保證自己的“個(gè)人利潤”最大化。

因此,整個(gè)系統(tǒng)需要在整體和個(gè)人之間尋求平衡,即“自由交易者”之間能夠相互協(xié)商進(jìn)而產(chǎn)生最終的任務(wù)分配結(jié)果。協(xié)商的方法一般為分包和轉(zhuǎn)移2種。分包指“招標(biāo)者”向“投標(biāo)者”發(fā)放任務(wù),并在任務(wù)完成后向“投標(biāo)者”發(fā)放對應(yīng)酬勞。轉(zhuǎn)讓指“投標(biāo)者”主動以一定價(jià)格出售任務(wù)執(zhí)行代價(jià),在簽訂合同之時(shí),“招標(biāo)者”即向投標(biāo)者“付款”支付報(bào)酬。協(xié)商和分包行為的實(shí)質(zhì)是允許了無人機(jī)在任務(wù)執(zhí)行過程中將無法處理或不便處理的任務(wù)再次進(jìn)行拍賣,實(shí)現(xiàn)任務(wù)遷移,提升任務(wù)分配結(jié)果的質(zhì)量。

相比于合同網(wǎng)協(xié)議,Trader-Bots方法具有更強(qiáng)的適應(yīng)性與魯棒性,其允許協(xié)商過程中發(fā)生分包或轉(zhuǎn)讓行為的機(jī)制能夠更加明確任務(wù)優(yōu)先級以及提升任務(wù)容錯(cuò)性。

3.3 考慮通訊限制的任務(wù)分配

通訊在協(xié)同系統(tǒng)中具有重要地位,其作用于協(xié)同探索工作的整個(gè)過程,尤其對任務(wù)分配的決策具有重要影響。

在美國國防部高級研究計(jì)劃局(defense advanced research projects agency,DARPA)舉辦的地下挑戰(zhàn)賽(subterranean challenge competition,SubT)中,研究人員使用多種異構(gòu)機(jī)器人(包括無人機(jī)、地面機(jī)器人等)[51]進(jìn)行了地下極端環(huán)境的協(xié)同探索。然而,這些系統(tǒng)現(xiàn)大多數(shù)仍舊屬于集中式方法,即依賴于某一臺中央處理器進(jìn)行任務(wù)分配,任務(wù)分配方式也一般采用貪婪算法進(jìn)行簡單處理?？梢?在實(shí)際應(yīng)用中,因通訊限制,有許多問題仍待解決。

如圖9所示,通常將通訊限制具體劃分為以下兩類:(1)帶寬限制,即系統(tǒng)內(nèi)無人機(jī)間無法對占用空間較大的數(shù)據(jù)進(jìn)行瞬時(shí)傳輸,造成數(shù)據(jù)延遲甚至丟包的問題;(2)距離限制,即系統(tǒng)內(nèi)無人機(jī)間只能在一定物理范圍內(nèi)進(jìn)行通訊。針對以上兩大限制,各種方法從不同角度努力改善探索系統(tǒng)的穩(wěn)定性。

圖9 協(xié)同探索系統(tǒng)面臨的通訊限制問題

文獻(xiàn)[52]通過各無人機(jī)與中心處理器建立通信樹的回歸策略提升任務(wù)分配的穩(wěn)定性。文獻(xiàn)[54]采用高斯混合模型建立全局地圖,使地圖共享占用內(nèi)存縮小。文獻(xiàn)[55]使用基于群體梯度信息的bug算法,采用沿墻飛行和實(shí)時(shí)接收信號強(qiáng)度的策略來避免碰撞,但其效率較低無法獲得準(zhǔn)確且全面的地圖信息。以上算法均屬于集中式的任務(wù)分配方法,在實(shí)際應(yīng)用中往往受通訊限制而導(dǎo)致效果不佳。

文獻(xiàn)[50]在通信帶寬限制方面,對包含局部地圖、已探索區(qū)域以及定位等共享信息進(jìn)行優(yōu)化壓縮,降低內(nèi)存占用。而針對通信距離限制,文獻(xiàn)[50]通過預(yù)先設(shè)定下一匯合點(diǎn)使無人機(jī)分散再集合,確保通信共享的穩(wěn)定性。而文獻(xiàn)[46]通過限制并減少同時(shí)共享無人機(jī)的數(shù)量降低通訊要求,即通過設(shè)計(jì)請求-響應(yīng)的任務(wù)分配方案,僅支持無人機(jī)之間成對進(jìn)行交互實(shí)現(xiàn)信息共享。

綜上所述,考慮通訊限制的任務(wù)分配方法在實(shí)際應(yīng)用中具有重要意義,也越來越受到學(xué)者們的關(guān)注。

4 結(jié)論

未知環(huán)境探索策略和多機(jī)任務(wù)分配策略是多機(jī)協(xié)同自主探索工作中的重點(diǎn),影響著整體探索效率。本文中詳細(xì)介紹了未知環(huán)境探索策略以及多機(jī)任務(wù)分配策略,并對當(dāng)前工作進(jìn)行了分析評價(jià)。

當(dāng)前未知環(huán)境探索策略可分為基于邊界、采樣以及兩者結(jié)合的方法。其中,基于邊界的方法簡單易用,但效率較低,而基于采樣的方法效率高但較易陷入局部最優(yōu),且在大場景中較費(fèi)算力。而兩者結(jié)合的方法取長補(bǔ)短,具有較高的研究意義與價(jià)值。

當(dāng)前多機(jī)任務(wù)分配策略可分為基于物流和市場模型的方法。其中,基于物流的方法是將一系列觀測當(dāng)作旅行商問題中的城市,意在求取訪問城市的先后順序從而決策各無人機(jī)的下一觀測點(diǎn)。而基于市場的方法參考人類社會中的拍賣機(jī)制,通過投標(biāo)、競標(biāo)、中標(biāo)的方式進(jìn)行任務(wù)分配。需要注意的是,在本文中特別討論了通訊限制下的任務(wù)分配方法研究,意在強(qiáng)調(diào)通訊在現(xiàn)實(shí)世界協(xié)同探索工作的重要影響,這也是協(xié)同探索當(dāng)前急需考慮的問題之一。

綜上所述,多機(jī)協(xié)同自主探索系統(tǒng)仍存在較多待改進(jìn)和擴(kuò)展之處:

1) 多機(jī)協(xié)同優(yōu)勢的提升

當(dāng)前的多無人機(jī)協(xié)同探索系統(tǒng),一般僅共享各智能體之間的局部地圖和定位信息,協(xié)同優(yōu)勢還未完全發(fā)揮。在后續(xù)的研究工作中,可嘗試在無人機(jī)之間加入其他更智能的協(xié)同約束,進(jìn)一步發(fā)揮多無人機(jī)的協(xié)同優(yōu)勢,提高探索效率。

2) 分布式協(xié)同探索系統(tǒng)的優(yōu)化

當(dāng)前實(shí)際應(yīng)用的多機(jī)協(xié)同探索系統(tǒng)大多數(shù)仍是集中式結(jié)構(gòu)。隨著個(gè)體智能化、無人化水平的日漸提升,分布式協(xié)同探索系統(tǒng)的優(yōu)勢將會日益凸顯。因此,在當(dāng)前研究基礎(chǔ)上,需研究更適用于當(dāng)前個(gè)體智能化水平的分布式系統(tǒng),發(fā)揮個(gè)體無人化優(yōu)勢,提升整體系統(tǒng)效率。

3) 考慮實(shí)際應(yīng)用的協(xié)同探索方法設(shè)計(jì)

在本文中以現(xiàn)實(shí)世界中的通信限制作為典型討論了協(xié)同探索在實(shí)際應(yīng)用中需考慮的問題。除此之外,為了使協(xié)同探索方法能夠真正在現(xiàn)實(shí)生活中應(yīng)用落地,還需對諸如協(xié)同定位建圖誤差、智能體工作時(shí)長限制、故障魯棒性(抗毀能力)等問題加以考慮,設(shè)計(jì)出實(shí)際應(yīng)用價(jià)值更高的協(xié)同探索系統(tǒng)。