一種多智能體網(wǎng)絡(luò)牽引蜂擁擠控制算法

一種多智能體網(wǎng)絡(luò)牽引蜂擁擠控制算法

自經(jīng)典團(tuán)隊(duì)系統(tǒng)的集群模型提出以來，團(tuán)隊(duì)動(dòng)態(tài)和協(xié)調(diào)控制的研究引起了人們的關(guān)注。在傳統(tǒng)的集群動(dòng)態(tài)控制模型中，通過在多智能網(wǎng)絡(luò)上的每個(gè)節(jié)點(diǎn)上配置控制器，我們可以完成大規(guī)模行為的協(xié)調(diào)和運(yùn)動(dòng)。對(duì)于工程應(yīng)用，所有節(jié)點(diǎn)的生產(chǎn)過程都需要花費(fèi)大量成本來滿足現(xiàn)代工業(yè)發(fā)展的需要。隨著近年來牽制控制研究的發(fā)展,將牽制的思想引入蜂擁控制研究已經(jīng)取得了一些非常重要的成果,文獻(xiàn)針對(duì)隨機(jī)多智能體網(wǎng)絡(luò)提出少數(shù)個(gè)體具有虛擬領(lǐng)導(dǎo)者信息的蜂擁控制算法;文獻(xiàn)進(jìn)一步基于人工勢(shì)場(chǎng)法實(shí)現(xiàn)多智能體網(wǎng)絡(luò)的牽制蜂擁同步;文獻(xiàn)研究了具有社團(tuán)結(jié)構(gòu)的多智體網(wǎng)絡(luò)牽制控制,而其中一個(gè)關(guān)鍵的問題是多智能體網(wǎng)絡(luò)在演化過程中其拓?fù)浣Y(jié)構(gòu)是時(shí)變的,某一時(shí)刻相互之間可感知的智能體或者社團(tuán)之間的智能體在下一時(shí)刻不再可感知時(shí),會(huì)使得網(wǎng)絡(luò)在演化過程中的連通性降低,甚至可能導(dǎo)致網(wǎng)絡(luò)不連通,若沒有有效連通控制策略的,則最終會(huì)產(chǎn)生部分智能體不能跟隨虛擬領(lǐng)導(dǎo)者運(yùn)動(dòng)即出現(xiàn)“分裂”現(xiàn)象.由此可見:保持網(wǎng)絡(luò)在演化過程中的整體連通性要求對(duì)于智能體網(wǎng)絡(luò)蜂擁任務(wù)的完成是尤為關(guān)鍵的.已有研究中多智能體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的連通性沒有考慮或是通過假設(shè)予以保證的,而通過增大智能體感知半徑以實(shí)現(xiàn)網(wǎng)絡(luò)連通的方法存在代價(jià)消耗問題,不具有普適性.為解決現(xiàn)有牽制蜂擁控制算法在保持網(wǎng)絡(luò)連通性上的缺陷,提出一種基于局部?jī)?yōu)化的牽制蜂擁控制算法,僅對(duì)網(wǎng)絡(luò)中的信息智能體施加跟隨虛擬領(lǐng)導(dǎo)者的牽制控制,并為信息智能體及其鄰居組成的子網(wǎng)絡(luò)設(shè)計(jì)局部?jī)?yōu)化策略,通過不斷優(yōu)化子網(wǎng)絡(luò)在運(yùn)行過程中的局部連通性,達(dá)到提高整個(gè)多智能體網(wǎng)絡(luò)全局連通性的目的,進(jìn)而保證所有智能體都跟隨虛擬領(lǐng)導(dǎo)者運(yùn)動(dòng),實(shí)現(xiàn)位置的聚集與方向的同步.1算法2t面元2vi考慮N個(gè)相同的智能體在二維平面上運(yùn)動(dòng),忽略智能體的尺寸(將智能體視作質(zhì)點(diǎn)),記t時(shí)刻智能體i的位置為xi(t),速度為vi(t),則智能體在二維坐標(biāo)系下的動(dòng)力學(xué)方程為{˙xi(t)=vi(t);˙vi(t)=ui(t)?式中:ui(t)為控制輸入;xi(t),vi(t),ui(t)∈R2.另外,假設(shè)多智能體網(wǎng)絡(luò)中存在一個(gè)虛擬領(lǐng)導(dǎo)者,虛擬領(lǐng)導(dǎo)者作為網(wǎng)絡(luò)的全局目標(biāo),以期望的速度引導(dǎo)整個(gè)網(wǎng)絡(luò)朝著預(yù)想的方向運(yùn)動(dòng),其運(yùn)動(dòng)行為按公式{˙xγ(t)=vγ(t);˙vγ(t)=fγ(xγ(t),vγ(t))更新,式中xγ(t),vγ(t)∈R2分別表示位置和速度.假設(shè)虛擬領(lǐng)導(dǎo)者的初始值為(xγ(0),vγ(0))=(xd,vd),且沿著一個(gè)固定速度vd運(yùn)動(dòng),則有˙xγ(t)=vd,xγ(0)=xd.將虛擬領(lǐng)導(dǎo)者作為網(wǎng)絡(luò)的全局目標(biāo),控制目的是使部分智能體具有虛擬領(lǐng)導(dǎo)者的信息,通過局部?jī)?yōu)化保持網(wǎng)絡(luò)在演化過程中的全局連通性,使網(wǎng)絡(luò)中所有智能體都達(dá)到虛擬領(lǐng)導(dǎo)者的速度,且實(shí)現(xiàn)位置的聚集與避碰.對(duì)于智能體i,其控制輸入算法包括4項(xiàng),即ui=fγi+fdi+fgi+fli.第1項(xiàng)fγi=hi[c1(xγ(t)-xi(t))+c2(vγ(t)-vi(t))]為引導(dǎo)反饋項(xiàng),用于實(shí)現(xiàn)跟隨虛擬領(lǐng)導(dǎo)者.若i是信息智能體,則hi=1;否則hi=0,即fγi=0.第2項(xiàng)fdi=∑j∈Νi(t)aij(t)(vj(t)-vi(t))為速度一致算法,以實(shí)現(xiàn)智能體之間的速度匹配.其中A=[aij(t)]N×N為鄰接矩陣,智能體i的鄰居集合Ni={{i}∪{j:aij≠0;j=1,2,…,N}}.第3項(xiàng)fgi=∑j∈Νi(t)?xi(t)Ψα(|xj(t)-xi(t)|σ)是人工勢(shì)函數(shù)梯度項(xiàng),用于實(shí)現(xiàn)分離和聚合規(guī)則,智能體沿著人工勢(shì)函數(shù)梯度方向運(yùn)動(dòng)并最終穩(wěn)定在勢(shì)函數(shù)局部最小的位置上運(yùn)動(dòng),式中人工勢(shì)函數(shù)Ψα(z)與其對(duì)應(yīng)作用力函數(shù)φα(z)關(guān)系為Ψα(z)=∫zdφα(s)ds,則fgi=∑j∈Νi(t)φα(|xj(t)-xi(t)|σ)nij,nij=(xj(t)-xi(t))/[1-ε∥xj(t)-xi(t)∥2]1/2是由xi(t)指向xj(t)的矢量.作用力函數(shù)φα(z)定義為φα(z)=ρh(z/∥r∥σ)φ(z-∥d∥σ),φ(z)=[(a+b)σ1(z+c)+(a-b)]/2,式中:ρh為切換函數(shù);d為智能體之間的期望距離;r為智能體的感知半徑;σ1t(z)=z/1+z2;˙φ(z)是非均勻的S型函數(shù),且φ(0)=0;參數(shù)滿足0<a≤b,c=|a-b|/√4ab.如圖1所示.當(dāng)智能體之間的距離小于‖d‖σ時(shí),φα(z)<0,表現(xiàn)為智能體之間的排斥力作用,且距離越小作用力函數(shù)的絕對(duì)值越大,即排斥力越大;當(dāng)智能體之間的距離在‖d‖σ和‖r‖σ之間時(shí),φα(z)>0,表現(xiàn)為智能體之間的吸引力作用;當(dāng)智能體之間的距離大于‖r‖σ時(shí),φα(z)=0,智能體之間無作用力.第4項(xiàng)是基于局部?jī)?yōu)化的保持連通策略.定義1在二維空間中,以智能體i為圓心,感知半徑r為半徑所構(gòu)成的區(qū)域稱為智能體i的鄰域范圍.將智能體i看作網(wǎng)絡(luò)中的節(jié)點(diǎn)Vi,與其鄰域范圍內(nèi)節(jié)點(diǎn)Vj之間的邊記為eij,可以得到無向圖G=(V,E),其中V={V1,V2,…,Vn}為多智能體網(wǎng)絡(luò)中節(jié)點(diǎn)的集合,E={eij=(Vi,Vj):Vi,Vj∈V}為多智能體網(wǎng)絡(luò)中邊的集合.定義2信息智能體p的所有鄰居組成的網(wǎng)絡(luò)定義為子網(wǎng)絡(luò).子網(wǎng)絡(luò)中除p以外所有智能體的集合定義為Up={Vi∈V:(Vp,Vi)∈E},t時(shí)刻Up(t)中所有智能體組成的網(wǎng)絡(luò)的代數(shù)連通度記為λ2p(t),λ2p(t+1)表示Up(t)∪Up(t+1)中所有智能體組成的網(wǎng)絡(luò)的代數(shù)連通度.保持連通算法描述為fli=bi1(xpd(t+1)-xi(t))+bi2(xp(t)-xi(t)),式中:bi1{>0(i為信息智能體?記為p(t)>0)?=0(i為信息智能體?記為p(t)=0)；bi2{>0(i為非信息智能體?是信息智能體p的鄰居個(gè)體?且0≤λ2p(t)<λc),=0(i為非信息智能體?是信息智能體p的鄰居個(gè)體?且λ2p(t)≥λc),λc為λ2p(t)的閾值;xi(t)為智能體i的位置;xp(t)為信息智能體p的位置;xpd(t+1)為使λ2p(t+1)最大的信息智能體p的目標(biāo)位置;bi1和bi2為反饋系數(shù).λ2p(t)≥λc時(shí)子網(wǎng)絡(luò)中智能體之間連接緊密,網(wǎng)絡(luò)的連通性能較優(yōu);0<λ2p(t)<λc時(shí)子網(wǎng)絡(luò)由g個(gè)并不完全獨(dú)立的社團(tuán)組成,社團(tuán)內(nèi)部連接緊密,社團(tuán)之間通過少數(shù)的幾條邊相連,子網(wǎng)絡(luò)仍連通,但代數(shù)連通度較小;λ2p(t)=0時(shí)子網(wǎng)絡(luò)由g個(gè)完全獨(dú)立的社團(tuán)組成,社團(tuán)之間沒有連接,只有社團(tuán)內(nèi)部才存在邊,代數(shù)連通度為0,子網(wǎng)絡(luò)不連通.通過局部?jī)?yōu)化實(shí)現(xiàn)保持連通的策略如下.A.若智能體i是信息智能體,則將其記為p.根據(jù)t時(shí)刻p鄰域范圍內(nèi)所有智能體的分布情況計(jì)算λ2p(t),并選擇相應(yīng)的保持連通策略.a.若λ2p(t)>0,如圖2(a)和2(b)所示,則xp(t)表示信息智能體p的位置,其感知半徑為r,為提高網(wǎng)絡(luò)的連通性,使信息智能體朝著代數(shù)連通度λ2p(t+1)最大的方向運(yùn)動(dòng),具體實(shí)施方法為:首先以xp(t)為圓心、步長ξ為半徑畫圓(如圖2(a)中細(xì)虛線圓所示),設(shè){?xpθ(t+1)}為t+1時(shí)刻信息智能體p在圓上的位置集合,而后利用粒子群算法在圓上尋找滿足λ2p(t+1)最大的信息智能體p的位置xpd(t+1),且xpd(t+1)∈{?xpθ(t+1)},ˉxp(t)?xpθ(t+1)與向量(i+0j)的夾角記為θ,在粒子群算法中,將粒子位置設(shè)置為θ,粒子的初始速度隨機(jī)產(chǎn)生為間的任意數(shù),粒子位置的搜索空間為θ∈(0,2π],在每次迭代中,以粒子群中個(gè)體每次搜索到的局部極值pbest(θ)所對(duì)應(yīng)的目標(biāo)位置px為圓心,感知半徑r為半徑,依次求解Up(t)∪Up(t+1)中智能體組成的網(wǎng)絡(luò)的代數(shù)連通度λ2p(t+1),進(jìn)而求出粒子群的全局最優(yōu)解gbest(θ),該角度所對(duì)應(yīng)的圓上的點(diǎn)即為使λ2p(t+1)最大的信息智能體p的目標(biāo)位置xpd(t+1),最后得出代數(shù)連通度增大的方向?yàn)椤p(t)xpd(t+1).b.若λ2p(t)=0,如圖2(c)所示,則網(wǎng)絡(luò)劃分為g個(gè)完全獨(dú)立的社團(tuán),社團(tuán)之間不存在邊,只有社團(tuán)內(nèi)部才存在邊.此時(shí)信息智能體的局部?jī)?yōu)化項(xiàng)為零,保持連通的方法是使信息智能體p將代數(shù)連通度λ2p(t)的信息發(fā)送給其鄰域范圍內(nèi)的普通智能體,普通智能體繼而向信息智能體p運(yùn)動(dòng)以使網(wǎng)絡(luò)的連通性增強(qiáng).B.若智能體i為普通智能體,則在t時(shí)刻首先識(shí)別其鄰居中是否有信息智能體.若沒有則該智能體僅須按照牽制蜂擁控制算法中與其鄰居間的局部交互規(guī)則運(yùn)動(dòng);若有信息智能體p,則根據(jù)信息智能體p鄰域范圍內(nèi)智能體組成的子網(wǎng)絡(luò)的λ2p(t)值確定優(yōu)化策略.a.若智能體i鄰域范圍內(nèi)有信息智能體p,且0≤λ2p(t)<λc,則認(rèn)為該智能體位于信息智能體p鄰域內(nèi)子網(wǎng)絡(luò)的某個(gè)社團(tuán)中,如圖2(b)和(c)所示,為提高子網(wǎng)絡(luò)的代數(shù)連通度,該智能體朝著信息智能體p運(yùn)動(dòng).b.若λ2p(t)≥λc,則認(rèn)為信息智能體p鄰域內(nèi)智能體之間連接緊密,如圖2(a),為保證該智能體與其鄰居處于一個(gè)相對(duì)穩(wěn)定的狀態(tài),該智能體的局部?jī)?yōu)化項(xiàng)為零.基于局部?jī)?yōu)化的多智能體網(wǎng)絡(luò)牽制蜂擁控制策略的虛擬控制過程可以表述為:虛擬領(lǐng)導(dǎo)者將其位置和速度信息傳遞給信息智能體,信息智能體一方面跟隨虛擬領(lǐng)導(dǎo)者運(yùn)動(dòng);另一方面虛擬控制其鄰居個(gè)體,而普通智能體在個(gè)體之間的局部交互作用下,不斷地實(shí)現(xiàn)位置聚集和速度匹配,會(huì)直接或間接地受控于信息智能體,因此普通智能體也間接地受控于虛擬領(lǐng)導(dǎo)者.此外,在局部?jī)?yōu)化策略下,信息智能體在保持其鄰域內(nèi)子網(wǎng)絡(luò)連通性的基礎(chǔ)上,不斷朝著其在當(dāng)前時(shí)刻和下一時(shí)刻所有鄰居的并集所組成網(wǎng)絡(luò)的代數(shù)連通度最大的方向運(yùn)動(dòng),同時(shí)為提高子網(wǎng)絡(luò)的代數(shù)連通度,普通智能體不斷朝著其鄰域范圍內(nèi)信息智能體運(yùn)動(dòng),從而實(shí)現(xiàn)整個(gè)多智能網(wǎng)絡(luò)的協(xié)調(diào)運(yùn)動(dòng),且保持并不斷提高整個(gè)網(wǎng)絡(luò)在演化過程中的連通性.2不同智能體間的網(wǎng)絡(luò)初始合作在相同的初始網(wǎng)絡(luò)分布和仿真條件下,分別對(duì)未加保持連通策略以及基于局部?jī)?yōu)化的的牽制蜂擁算法進(jìn)行仿真,具體參數(shù)設(shè)置如下.多智能體總數(shù)N=80,信息智能體個(gè)數(shù)n=8,智能體的位置和方向角分別在[0,60]×[0,60]和(-π,π]的范圍內(nèi)隨機(jī)生成,初始速率v∈;虛擬領(lǐng)導(dǎo)者的初始位置xr(0)=和速度vγ(0)=0.4×[1,√3].圖3(a)～(c)反映了牽制蜂擁控制網(wǎng)絡(luò)演化過程,圖中:空心和實(shí)心等腰三角形符號(hào)分別表示多智能體網(wǎng)絡(luò)中的普通智能體和信息智能體;三角形方向表示智能體速度的方向;圓形符號(hào)和箭頭表示虛擬領(lǐng)導(dǎo)者的位置和速度;可互相感知的智能體之間以虛線相連.設(shè)定智能體間的期望距離d=6,感知半徑r=1.5d,參數(shù)ε=0.1,a=5,b=20,h=0.9.反饋系數(shù)c1=0.5,c2=0.5.當(dāng)演化代數(shù)t=0時(shí),多智能體網(wǎng)絡(luò)初始化隨機(jī)生成的演化如圖3(a)所示;由圖3(b)可知當(dāng)t=20時(shí)多智能體網(wǎng)絡(luò)中的智能體相互之間形成類α格子,距離保持一定并有規(guī)則的排列,網(wǎng)絡(luò)由初始的不連通圖演變成連通圖,但網(wǎng)絡(luò)中某些處于網(wǎng)絡(luò)中間位置的智能體之間連接關(guān)系相對(duì)較薄弱;當(dāng)t=100時(shí)(圖3(c)),由于某些關(guān)鍵位置的智能體之間局部關(guān)系鏈斷裂,因此整個(gè)網(wǎng)絡(luò)被分成了幾個(gè)小網(wǎng)絡(luò)而導(dǎo)致失去連通,即出現(xiàn)了“分裂”現(xiàn)象.圖4(a)～(c)所示為基于局部?jī)?yōu)化的牽制蜂擁控制網(wǎng)絡(luò)演化圖,在相同的仿真參數(shù)設(shè)置下,t=0時(shí)多智能體網(wǎng)絡(luò)初始分布與圖3(a)一致;t=20時(shí)圖4(b)中所有智能體形成一個(gè)連通的網(wǎng)絡(luò),且在局部?jī)?yōu)化策略的作用下,智能體之間聚集比圖3(b)更緊密;如圖4(c)所示,最后在t=100時(shí)所有智能體都聚集在虛擬領(lǐng)導(dǎo)者周圍很小的范圍內(nèi),實(shí)現(xiàn)位置聚集,且速度大小和方向與虛擬領(lǐng)導(dǎo)者趨于一致.圖5中給出了優(yōu)化前和施加局部?jī)?yōu)化后的多智能體網(wǎng)絡(luò)牽制蜂擁過程中的代數(shù)連通度變化曲線.由圖可知:優(yōu)化前的多智能體網(wǎng)絡(luò)在人工勢(shì)場(chǎng)的作用下,智能體之間通過局部感知會(huì)形成一定的隊(duì)形,但由于網(wǎng)絡(luò)中某些關(guān)鍵位置的智能體間的關(guān)系鏈較薄弱,在演化過程中出現(xiàn)斷裂,最后λ2恒為零即多