多智能體備用領(lǐng)導(dǎo)者避障方法

田寶國，吳尚燁

(海軍航空大學(xué)， 山東 煙臺(tái) 264001)

自然界存在著大量的群體，比如蜂群、鳥群、魚群、蟻群，這些群體的個(gè)體擁有的智能相對(duì)簡(jiǎn)單，但通過群體協(xié)作卻能讓整個(gè)種群很好地適應(yīng)自然界的各種復(fù)雜情況[1]，近年來，隨著各種具有相對(duì)簡(jiǎn)單功能的機(jī)器面世，如無人機(jī)、無人車、仿生魚等智能化群體在農(nóng)業(yè)[2]、物流[3]、軍事[4]等領(lǐng)域有了重要作用，因此將具有簡(jiǎn)單智能個(gè)體集合成多智能體系統(tǒng)，研究多智能體系統(tǒng)群體運(yùn)動(dòng)的協(xié)作方式和效能在對(duì)提高機(jī)器群體共同完成任務(wù)有重要意義。

多智能體集群運(yùn)動(dòng)是當(dāng)前多智能體系統(tǒng)的研究重點(diǎn)之一，其中多智能體集群避障問題在多智能體集群運(yùn)動(dòng)中具有基礎(chǔ)的研究意義，如：群體跟蹤、群體編隊(duì)、群體覆蓋等，只要涉及到群體運(yùn)動(dòng)的問題，都要考慮到避障問題，然而在自然環(huán)境中，障礙物復(fù)雜多變，需要設(shè)計(jì)合理簡(jiǎn)潔的適應(yīng)性避障算法。文獻(xiàn)[5]提出了速度障礙法，通過個(gè)體和障礙的運(yùn)動(dòng)速度計(jì)算個(gè)體運(yùn)動(dòng)的安全區(qū)域，從而判斷個(gè)體是否需要采取避障措施。文獻(xiàn)[6]將其運(yùn)用于大規(guī)模個(gè)體的情況，并體現(xiàn)出較好的避障效能。Tanner[7]、Olfati[8]、Murray[9]等提出了基于一致性與人工勢(shì)能函數(shù)相結(jié)合的群體控制算法，并且討論仿真了在有障礙時(shí)的集群運(yùn)動(dòng)情況。文獻(xiàn)[10]提出了基于人工勢(shì)場(chǎng)和極限環(huán)方法改進(jìn)群體編隊(duì)避障算法。李皎潔[11]基于Olfati-Saber等提出的人工勢(shì)能框架，系統(tǒng)研究了部分智能體具有全局信息時(shí)群體避障的算法。文獻(xiàn)[12]基于勢(shì)能函數(shù)和行為規(guī)則設(shè)計(jì)了智能群體在滿足避障能力的同時(shí)能有效追蹤目標(biāo)的群體控制方法。為簡(jiǎn)化群體控制，Sakai[13]提出不區(qū)分相鄰智能體與障礙物的群體算法，簡(jiǎn)化了算法設(shè)計(jì)時(shí)需要用到的勢(shì)能函數(shù)，仿真結(jié)果表明群體在有虛擬領(lǐng)導(dǎo)的情況下能有效避開障礙物。

上述論文的工作多數(shù)探討的是關(guān)于凸形障礙物的避障方法，部分雖然探討了凹形障礙物的避障方法，但這些方法都需部分智能體具有障礙物的中心點(diǎn)，或最大半徑等障礙物的幾何信息或者全局障礙信息。但在很多實(shí)際情況中，障礙物的幾何信息難以得到。為簡(jiǎn)化智能體的信息需求，本文針對(duì)部分簡(jiǎn)單凹形障礙設(shè)計(jì)了備用領(lǐng)導(dǎo)者更換機(jī)制，能在智能群體陷入凹形勢(shì)能陷阱的時(shí)候根據(jù)自身群體具備的信息生成只影響新的領(lǐng)導(dǎo)者智能體的虛擬障礙，通過新領(lǐng)導(dǎo)者帶領(lǐng)群體繞過凹形障礙。

1 問題描述

在二維平面中運(yùn)動(dòng)的群體可用N+2個(gè)智能體描述，其中一個(gè)智能體為當(dāng)前領(lǐng)導(dǎo)者，一個(gè)智能體為備用領(lǐng)導(dǎo)者，剩余N個(gè)智能體跟隨當(dāng)前領(lǐng)導(dǎo)者。將群體中每個(gè)個(gè)體抽象成質(zhì)點(diǎn)，每個(gè)智能體質(zhì)點(diǎn)的運(yùn)動(dòng)方程滿足如下動(dòng)力學(xué)方程：

(1)

式(1)中：xi(t)∈R2代表第i個(gè)智能體的二維位置向量；vi(t)∈R2代表第i個(gè)智能體的速度向量；ui(t)∈R2代表其控制量。為描述方便，令xl(t)=xn+1(t)表示領(lǐng)導(dǎo)者的位置坐標(biāo)，xsl(t)=xn+2(t)表示備用領(lǐng)導(dǎo)者的位置坐標(biāo)。

根據(jù)olfaite的群體算法框架[8]，定義單個(gè)智能體鄰居集，從而描述每個(gè)智能體的影響源，并定義智能體的鄰居集合如下：在t時(shí)刻每個(gè)智能體的探測(cè)半徑為r，其探測(cè)到的其他智能體(包括領(lǐng)導(dǎo)者和備用領(lǐng)導(dǎo)者)集合為：

Ni(t)={j|‖xi(t)-xj(t)‖≤r,j≠i}

(2)

障礙物在智能體探測(cè)范圍之內(nèi)時(shí)，將會(huì)產(chǎn)生該智能體對(duì)應(yīng)的β智能體，其位置為障礙物表面距離智能體最近的點(diǎn)，其坐標(biāo)可表述為：

(3)

對(duì)應(yīng)探測(cè)到的障礙智能體集合為：

(4)

式(4)中，No為障礙智能體個(gè)數(shù)。

為確保函數(shù)處處可微分，令參數(shù)ε>0，定義智能體之間的距離范數(shù)為：

(5)

為使群體運(yùn)動(dòng)模型更為簡(jiǎn)潔，本文根據(jù)文獻(xiàn)[13]只考慮智能體之間排斥力的思想設(shè)計(jì)群體控制算法。定義所有種類智能體之間的排斥函數(shù)為：

φ(Z)=ρh(z/df)(σ1(z-df)-1)

(6)

(7)

由此可定義每對(duì)智能體之間的排斥勢(shì)能為：

(8)

2 控制輸入設(shè)計(jì)

本文定義3種智能體，領(lǐng)導(dǎo)者能探測(cè)到運(yùn)動(dòng)方向信息，領(lǐng)導(dǎo)跟隨者智能體朝預(yù)定方向運(yùn)動(dòng)。跟隨者智能體具有領(lǐng)導(dǎo)者狀態(tài)信息，跟隨領(lǐng)導(dǎo)者運(yùn)動(dòng)，并且能探測(cè)到一定范圍內(nèi)其他智能體信息和障礙信息。備用領(lǐng)導(dǎo)者智能體與領(lǐng)導(dǎo)者智能體保持相對(duì)位置，在領(lǐng)導(dǎo)者陷入凹形障礙產(chǎn)生的局部勢(shì)能陷阱時(shí)，成為新領(lǐng)導(dǎo)者，之前的領(lǐng)導(dǎo)者成為備用領(lǐng)導(dǎo)者，新的領(lǐng)導(dǎo)者根據(jù)之前領(lǐng)導(dǎo)者的位置產(chǎn)生虛擬障礙，同時(shí)根據(jù)探測(cè)到的運(yùn)動(dòng)方向和實(shí)際障礙帶領(lǐng)群體離開局部勢(shì)能陷阱。

令第i個(gè)跟隨者智能體的控制輸入為uf,i，領(lǐng)導(dǎo)者的控制輸入為ul，備用領(lǐng)導(dǎo)者的控制輸入為usl，分別定義其具體控制輸入形式如下。

1) 跟隨者智能體的控制輸入

(9)

2) 領(lǐng)導(dǎo)者智能體的控制輸入

(10)

3) 備用領(lǐng)導(dǎo)者智能體的控制輸入

(11)

式(11)中，第一項(xiàng)表示備用領(lǐng)導(dǎo)者受到障礙物的排斥力。第二項(xiàng)表示備用領(lǐng)導(dǎo)者與領(lǐng)導(dǎo)者之間的排斥力。第三項(xiàng)確保備用領(lǐng)導(dǎo)者與領(lǐng)導(dǎo)者保持相對(duì)位置，其中xp為領(lǐng)導(dǎo)者和備用領(lǐng)導(dǎo)者期望相對(duì)位置向量。最后一項(xiàng)使備用領(lǐng)導(dǎo)者與領(lǐng)導(dǎo)者保持速度一致。

當(dāng)領(lǐng)導(dǎo)者遇到障礙，并且陷入凹形障礙的局部勢(shì)能陷阱時(shí)，備用領(lǐng)導(dǎo)者變換成為新的領(lǐng)導(dǎo)者，通過生成只有新的領(lǐng)導(dǎo)者能探測(cè)到的虛擬障礙填補(bǔ)凹形勢(shì)能陷阱區(qū)域，使新領(lǐng)導(dǎo)者繞過舊領(lǐng)導(dǎo)者進(jìn)入的勢(shì)能陷阱區(qū)，同時(shí)其他智能體，由于探測(cè)不到虛擬障礙，它們將跟隨新領(lǐng)導(dǎo)者從之前凹形勢(shì)能陷阱區(qū)域撤出并繞過實(shí)際的凹形障礙。

3 穩(wěn)定性分析

智能體控制輸入可根據(jù)勢(shì)能函數(shù)求導(dǎo)，如下表述：

(12)

(13)

考慮到領(lǐng)導(dǎo)者一直以常數(shù)vr(t)作為運(yùn)動(dòng)參考方向，可定義一個(gè)虛擬參考點(diǎn)xr(t)，其中xr(t)=xl(t)，vr(t)為常數(shù)。

定義跟隨者智能體和領(lǐng)導(dǎo)者相對(duì)虛擬參考點(diǎn)的總能量函數(shù)為：

(vi(t)-vr(t))Τ(vi(t)-vr(t))]+Ul,o+

(14)

式(14)中：

對(duì)于滿足上述運(yùn)動(dòng)方程的智能體組成的系統(tǒng)，在沒有遇到障礙物且系統(tǒng)能量有限Qf(t0)=C0的情況下，對(duì)t0時(shí)刻以后的系統(tǒng)可以有以下結(jié)論：

結(jié)論(2)系統(tǒng)中跟隨者智能體與領(lǐng)導(dǎo)者智能體的速度將收斂到同一速度值。

證明：

當(dāng)智能體沒有遇到障礙物時(shí)Ui,o=0，Ul,o=0，同時(shí)另備用智能體與群體具有相對(duì)較遠(yuǎn)的距離，此時(shí)可不考慮其對(duì)跟隨者智能體的影響，即Ui,sl=0。

此時(shí)，令

(15)

(16)

由對(duì)稱性可知

(17)

能量函數(shù)對(duì)時(shí)間求導(dǎo)數(shù)得到：

(18)

由式(18)得式(19)與式(20)，有：

(19)

(20)

式(19)、式(20)相加除以2可得：

(21)

(22)

因此智能體系統(tǒng)函數(shù)Qf(t)是一個(gè)隨時(shí)間單調(diào)遞減的系統(tǒng)，令初始系統(tǒng)能量為Qf(t0)，則對(duì)于任意時(shí)刻t>t0，Qf(t)≤Qf(t0)成立。

由式(16)可知：

(23)

可得到：

(24)

同理得到

令：

(25)

(26)

4 仿真實(shí)驗(yàn)與結(jié)果分析

下面對(duì)基于變換領(lǐng)導(dǎo)者機(jī)制的避障算法進(jìn)行仿真驗(yàn)證。對(duì)凹形障礙情況下，22個(gè)智能體構(gòu)成的系統(tǒng)在二維平面內(nèi)運(yùn)動(dòng)，其中包括1個(gè)領(lǐng)導(dǎo)者智能體、1個(gè)備用領(lǐng)導(dǎo)者智能體及20個(gè)跟隨者智能體。令單位長(zhǎng)度為1 m。

初始時(shí)，領(lǐng)導(dǎo)者坐標(biāo)為[0,0]，跟隨者和備用領(lǐng)導(dǎo)者位于[-20,20]×[-20,20]的空間內(nèi)，速度隨機(jī)分布在[-5,5]×[-5,5]的區(qū)間內(nèi)，令‖vr‖=10 m/s，vr=[10,0]。智能體之間探測(cè)半徑和探測(cè)障礙物范圍半徑相等，即r=r′=6，智能體之間和智能體與β智能體之間排斥力最大作用距離為d=4，σ范數(shù)中ε=0.5，函數(shù)ρh(z)中h=0.9。生成的虛擬障礙物半徑長(zhǎng)度為εsl||xl(t)-xsl(t)||，其中εsl=0.95。考慮到系統(tǒng)內(nèi)作用力大小跟系統(tǒng)整體參考速度vr有關(guān)，所以設(shè)計(jì)各智能體控制輸入的參數(shù)分別為：

以下描述為在該狀態(tài)下，仿真8 000步的結(jié)果，其中一步代表0.01 s。初始狀態(tài)圖如圖1所示，在二維平面上，智能體由圓點(diǎn)表示，運(yùn)動(dòng)方向及大小用紅色箭頭表示。圖2表示智能體最終狀態(tài)，可明顯看到其速度方向保持一致，并且能夠形成統(tǒng)一行動(dòng)的群體。兩圖中橫縱坐標(biāo)單位為米。

圖1 初始智能體狀態(tài)示意圖

圖2 最終狀智能體狀態(tài)示意圖

圖3為多智能體避障路線圖，由圖3可看到跟隨智能體在領(lǐng)導(dǎo)者的帶領(lǐng)下能夠順利繞過局部勢(shì)能陷阱實(shí)現(xiàn)避障功能。圖4為單獨(dú)畫出領(lǐng)導(dǎo)者和備用領(lǐng)導(dǎo)者智能體的避障路線，由圖4可知，其互換了兩次領(lǐng)導(dǎo)權(quán)，最初的備用領(lǐng)導(dǎo)者在陷入新的勢(shì)能陷阱后，被再次變換領(lǐng)導(dǎo)位置，從而使群體最終順利繞過障礙。

圖3 避障路線

圖4 領(lǐng)導(dǎo)者和備用領(lǐng)導(dǎo)者路線

圖5、圖6為智能體在X軸和Y軸方向的速度曲線，由圖5、圖6可知，在第2 000步到4 500步時(shí)速度變化較為劇烈，處于避障過程，之后速度收斂到同一數(shù)值，表明智能群體繞過障礙物后，智能體系統(tǒng)逐漸達(dá)到穩(wěn)定狀態(tài)。

圖5 X軸方向速度曲線

圖6表示智能個(gè)體之間最短距離的變化圖，在2 000～5 000 步，最短距離變化最為劇烈，但最小距離都大于0.5，表明系統(tǒng)內(nèi)部智能體之間具有較好的避碰性能，滿足群體避障算法的基本要求。

圖6 Y軸方向速度曲線

5 結(jié)論

本文針對(duì)凹形障礙易使智能體陷入局部最小勢(shì)能陷阱和避障信息簡(jiǎn)化的問題，設(shè)計(jì)了基于領(lǐng)導(dǎo)者互換和虛擬障礙機(jī)制的多智能體避障算法，該算法不需要智能體事先知道障礙物的幾何信息或全局障礙信息，就能實(shí)現(xiàn)對(duì)凹形障礙物的群體避障功能，通過理論分析該算法的穩(wěn)定性，仿真驗(yàn)證該算法能夠有效避開簡(jiǎn)單凹形障礙。