林 敏，夏元清，吳 爽

（北京理工大學(xué)自動化學(xué)院，北京 100081）

1 引 言

隨著移動機(jī)器人技術(shù)的發(fā)展以及通訊技術(shù)、計算機(jī)小型化技術(shù)的日益成熟，將一個復(fù)雜的任務(wù)分配給多個結(jié)構(gòu)、功能都相對簡單的智能體來完成已經(jīng)成為了一個熱門的研究方向。多智能體協(xié)同完成一項(xiàng)任務(wù)在軍事、民用等領(lǐng)域都有很大的發(fā)展?jié)摿ΑＤ壳暗牡湫蛻?yīng)用有集合［1，2］、編隊(duì)控制［3，4］、集群［5，6］以及任務(wù)分配［7］等。

多智能體系統(tǒng)一般都具有智能體數(shù)量大、分布式感知、復(fù)雜通訊的特點(diǎn)，智能體之間經(jīng)常存在著彼此的信息交互，因此用圖論來描述這種信息交互渠道就顯得十分自然。在一個多智能體系統(tǒng)中，若一個智能體能將自身信息傳給另一個智能體，那么就可以將這種通訊關(guān)系描述成兩個結(jié)點(diǎn)間以一條有向邊連接。若這兩個智能體間能互相將自身信息傳給對方，這種通訊關(guān)系則可以描述成兩個結(jié)點(diǎn)間以一條無向邊連接。若兩個智能體間的通訊聯(lián)系關(guān)系隨著它們間距的增大而減弱，則可描述為兩結(jié)點(diǎn)間邊的權(quán)值減小。由此，多智能體通訊拓?fù)渚W(wǎng)絡(luò)就能完全用圖來描述，進(jìn)而用圖論中的代數(shù)方式來描述和研究通訊拓?fù)涞男再|(zhì)和編隊(duì)的性質(zhì)。

代數(shù)圖論借助矩陣代數(shù)的方式來描述圖及其變換與性質(zhì)。多智能體控制算法中經(jīng)常用到鄰接矩陣來描述編隊(duì)的通訊拓?fù)?，用拉普拉斯矩陣證明編隊(duì)的穩(wěn)定性［8］、收斂速率等關(guān)鍵性質(zhì)。

在基于圖論的方法中，剛性圖理論也得到了關(guān)注。“剛性”就是指當(dāng)無向圖頂點(diǎn)運(yùn)動后，每個頂點(diǎn)間距得以保持的性質(zhì)。剛性圖理論最早誕生于機(jī)械領(lǐng)域，后被應(yīng)用于多智能體編隊(duì)控制?；趧傂詧D論，可以方便地通過算子描述剛性編隊(duì)的分裂和重組［9，10］，還可以利用智能體間距設(shè)計編隊(duì)控制律以確保剛性。基于同樣的理論，Anderson團(tuán)隊(duì)研究了多智能體編隊(duì)的剛性保持和隊(duì)形切換，解決了隊(duì)形變形、分裂、合并問題［11］，做出了許多原創(chuàng)性理論貢獻(xiàn)。

本文在基于圖論的一致性編隊(duì)算法基礎(chǔ)上，加入人工勢能場避障方法，使得跟隨者收斂至領(lǐng)航者坐標(biāo)系下的理想位置時可以避開環(huán)境障礙物，且跟隨車輛之間不會相撞。同時，針對具有非完整性約束的輪式機(jī)器人模型設(shè)計了領(lǐng)航者軌跡跟蹤算法，使得領(lǐng)航車輛以期望的速度角和速度行駛在規(guī)定的軌跡上。最終實(shí)現(xiàn)“行星-衛(wèi)星”式編隊(duì)，即領(lǐng)航者為有固定軌跡的“行星”，跟隨者為“衛(wèi)星”，始終以一定的半徑圍繞領(lǐng)航者行駛。最后通過仿真驗(yàn)證了算法的有效性。

2 背景知識

2.1 圖 論

用有向圖或無向圖來對多智能體間的通訊拓?fù)溥M(jìn)行建模，可以將通訊拓?fù)浣Y(jié)構(gòu)代數(shù)化，從而能借用矩陣的性質(zhì)對通訊圖的連通性等關(guān)鍵性質(zhì)進(jìn)行研究。在這部分介紹一些圖論中的符號以供后續(xù)使用。

一個由n個智能體組成的多智能體系統(tǒng)，可以用圖中的n個頂點(diǎn)代表這n個智能體，用圖的邊代表這些智能體間的通訊拓?fù)溥B接關(guān)系。由于智能體間的通訊都是有向的，所以一般用有向圖來描述多智能體系統(tǒng)的通訊拓?fù)洹．?dāng)系統(tǒng)中有通訊關(guān)系的兩個智能體間的通訊都是雙向的時，可以將有向圖簡化成無向圖。

一個有向圖G由一個有限頂點(diǎn)集合以及一個邊集ε?V×V組成，其中邊是一對頂點(diǎn)的有序?qū)?。定義有向圖的鄰接矩陣為其中的元素都是非負(fù)的，表示V的基。如果(i,j)是G的一條邊，即(i,j)∈ε，意味著從i到j(luò)有一條有向路徑，那么元素aji是正數(shù)，否則為0。規(guī)定對任何都有(i,i)不屬于ε。記智能體i能通訊到的所有智能體的集合為稱作智能體i的通訊集。如果一幅有向圖中存在一個稱作根的頂點(diǎn)，使得它到其他所有頂點(diǎn)都有路徑連接，則稱這幅有向圖存在有向生成樹，該頂點(diǎn)稱作生成樹的根。頂點(diǎn)i的度di定義為用D表示di的N×N的對角陣，那么D就是圖G的度矩陣。圖G的拉普拉斯矩陣就用半正定矩陣L=D-A來定義，或也可以定義為其中：

拉普拉斯矩陣是圖論中十分重要的一個矩陣。從式（1）中可以看出拉普拉斯陣L的行和為0，因此一定有一個零特征根，且L的特征根總是非負(fù)實(shí)部的。L中有幾個零特征根，則代表圖中有幾個連通子圖（即獨(dú)立的子網(wǎng)）。若用表示拉普拉斯矩陣L的m個特征根，且

2.2 系統(tǒng)模型

考慮一個含有n個智能體的系統(tǒng)，為全局坐標(biāo)系下的位置，為速度方向與坐標(biāo)系x軸的夾角，為線速度，為角速度，則根據(jù)運(yùn)動學(xué)模型容易獲得領(lǐng)航者模型為：

對于跟隨者，為了簡化一致性控制算法，采用簡單的一階積分器模型如下：

3 領(lǐng)航者軌跡跟蹤算法

在實(shí)際應(yīng)用中，領(lǐng)航者的軌跡通常是很復(fù)雜的，為了讓領(lǐng)航者能以預(yù)期的角速度和線速度走在某個特定預(yù)期軌跡上，同時也為了讓其預(yù)期軌跡更加多樣，就需要對領(lǐng)航者施加軌跡跟蹤算法。即設(shè)計控制律使小車實(shí)現(xiàn)對參考位姿參考線速度vr和參考角速度ωr的跟蹤。軌跡跟蹤模型如圖1所示。

圖1 軌跡跟蹤模型示意圖

由圖1中的幾何關(guān)系，首先寫出小車當(dāng)前位姿與參考位姿之間的誤差模型：

對式（5）左右兩邊求導(dǎo)，結(jié)合小車運(yùn)動學(xué)模型式（2），可得：

注1.從式（6）中可以看出，當(dāng)參考角速度ωr為0的時候，ye的收斂依賴于θe。若在ωr=0的前提下，θe將早于ye收斂到0，那么ye將變得無法控制，這就是在設(shè)計軌跡跟蹤算法時要注意的控制奇異點(diǎn)的問題。為了解決這個問題，可以在設(shè)計控制律時采用引導(dǎo)角［13］，即在ye未收斂時先控制θe為某一非零角度，這樣就避免了控制奇異點(diǎn)的產(chǎn)生。本文中引導(dǎo)角設(shè)計為：

其中D＞0是引導(dǎo)角參數(shù)，

定理1.對于具有非完整性約束的輪式機(jī)器人，可設(shè)計如下控制器（8）和（9）保證系統(tǒng)穩(wěn)定。

證.首先針對xe,ye的收斂，設(shè)計如下Lyapunov函數(shù)：

對式（10）求導(dǎo)，代入式（6）可得

將控制器（8）帶入式（11）可得

由于k1,vr＞0，所以則當(dāng)θe為一特定角度時，ye可以收斂。

接下來針對θe的收斂，設(shè)計Lyapunov函數(shù)：

對式（13）求導(dǎo)得

將控制器（9）和式（14）帶入式（15）可得

將式（18）帶入式（17）可得：

結(jié)合式（16）與式（19）可得：

由此解得：

4 跟隨者一致性算法

引理1.一階積分器模型在有向固定/切換拓?fù)湎碌倪B續(xù)時間基本一致性算法如下［14］：

式（22）達(dá)成一致性的條件為無向圖連通或者有向圖存在生成樹，在拓?fù)浣Y(jié)構(gòu)切換的情況下，達(dá)到一致性的條件為拓?fù)浣Y(jié)構(gòu)圖的并集對應(yīng)的無向圖連通或者有向圖存在生成樹。具體的證明可見文獻(xiàn)［15］。

定理2.當(dāng)系統(tǒng)存在領(lǐng)航者，且領(lǐng)航者位置時變時，為使跟隨者與領(lǐng)航者的位置量保持一個可時變的偏差，可設(shè)計如下控制器：

證.令式（23）可化簡為：

注意到，因?yàn)榈趎+1個智能體是領(lǐng)航者，不需要接收其他節(jié)點(diǎn)的信息，所以對應(yīng)鄰接矩陣An+1的最后一行全為0。又因?yàn)橛邢驁DGn+1存在有向生成樹，所以An+1沒有其他全為0的行。于是對應(yīng)的拉普拉斯矩陣Ln×(n+1)的秩為n。將Ln×(n+1)寫成由于Ln×(n+1)有行和為0的性質(zhì)，所以其第n+1列取決于前n列，即：

所以，有向圖Gn+1存在有向生成樹的充要條件是

于是式（25）可以寫成：

由于矩陣M滿秩，所以可逆，因此有：

即：

由上式可看出當(dāng)t→∞時，也就是當(dāng)且僅當(dāng)有向圖Gn+1存在有向生成樹。

5 基于人工勢能場的避障算法

對于避障控制，最廣為采用的方法就是由Khatib于1986年提出的人工勢能場方法［16］。機(jī)器人在人工勢能場中的運(yùn)動可以類比于帶電粒子在電場中的運(yùn)動。在電場中，帶電粒子沿著電場的梯度向量方向運(yùn)動，由高勢能點(diǎn)向低勢能點(diǎn)運(yùn)動，梯度可以看作是作用于帶電粒子上的力。在機(jī)器人的運(yùn)動過程中，可以將機(jī)器人看作在勢能場中運(yùn)動的粒子，障礙物對這個粒子產(chǎn)生排斥力，運(yùn)動的目標(biāo)點(diǎn)對這個粒子產(chǎn)生吸引力，在引力和斥力的作用下，粒子就能在向目標(biāo)點(diǎn)前進(jìn)的過程中避開障礙物。

在本文討論的情況中，由于每個智能體都有自己需要跟蹤的軌跡，不需要額外設(shè)置產(chǎn)生吸引力的勢能函數(shù)，只需設(shè)置產(chǎn)生斥力的勢能場進(jìn)行避障即可。對于運(yùn)動的車輛來說，產(chǎn)生斥力的勢能場來自于與之鄰近的其他車輛。只有其他車輛進(jìn)入到其避障范圍內(nèi)時，勢能場就迅速升高，產(chǎn)生排斥力，而在避障范圍外，勢能場就為0。圖2是這種勢能場的示意圖。

圖2 人工勢能場示意圖

設(shè)計勢能函數(shù)如下：

其中，Ra＞ra＞0，||·||表示向量的范數(shù)，若無特殊說明，默認(rèn)是2-范數(shù)。此勢能函數(shù)取值如下：

那么小車受到的力就是沿著勢函數(shù)的負(fù)梯度方向，作為小車的避障輸入：

則跟隨車輛的控制器可在式（23）的基礎(chǔ)上重新設(shè)計為：

6 仿真結(jié)果及分析

本節(jié)選取了一輛領(lǐng)航車和兩輛跟隨車對上文中提到的算法分別進(jìn)行數(shù)值仿真，三輛車之間的網(wǎng)絡(luò)拓?fù)潢P(guān)系由鄰接矩陣表示為：

對于領(lǐng)航者的軌跡跟蹤算法（8）和（9），在具體仿真時，選擇k1=k2=1，L=0.5，使領(lǐng)航者以vr=1，ωr=0.6行走在一個圓形軌跡上。得到仿真結(jié)果如下：圖3為領(lǐng)航者期望軌跡與實(shí)際軌跡，圖4為x,y與θ方向上的跟蹤誤差，圖5、圖6分別為期望速度、角速度與實(shí)際速度和角速度的比較情況。由仿真結(jié)果可得，算法（8）、（9）可保證領(lǐng)航者以期望的速度角速度行駛在規(guī)定軌跡上。

對于帶有人工勢能場避障的跟隨者一致性算法（29），令γ=2，Ra=0.5，ra=0.25，先任意給定領(lǐng)航者速度vr=0.5，ωr=0.3，當(dāng)期望誤差δi=δj=0時，可得到圖7軌跡，表明算法（29）可使跟隨者位置達(dá)到一致，為了便于觀察給出圖8為x方向上位置收斂情況。

將領(lǐng)航者軌跡跟蹤算法（8）和（9）與跟隨者一致性和避障算法（29）結(jié)合，同時令即跟隨者以領(lǐng)航者為圓心畫圓。其中最終可實(shí)現(xiàn)“行星-衛(wèi)星”式編隊(duì)，仿真效果如圖9。

圖3 領(lǐng)航者期望軌跡與實(shí)際軌跡

圖4 領(lǐng)航者追蹤誤差

圖5 領(lǐng)航者期望速度與實(shí)際速度

圖6 領(lǐng)航者期望角速度與實(shí)際角速度

圖7 期望誤差為零時跟隨者軌跡

圖8 期望誤差為零時跟隨者x坐標(biāo)收斂情況

圖9 “行星-衛(wèi)星”式編隊(duì)效果

7 結(jié) 論

本文研究了一種“行星-衛(wèi)星”式編隊(duì)方式，即領(lǐng)航者以期望的速度和角速度行駛在規(guī)定軌跡上，跟隨者保持在領(lǐng)航者坐標(biāo)系下一特定圓形軌跡上。首先對領(lǐng)航者的軌跡跟蹤算法進(jìn)行了研究，設(shè)計了領(lǐng)航者控制器并對其穩(wěn)定性進(jìn)行了證明。然后在傳統(tǒng)一致性算法基礎(chǔ)上，結(jié)合人工勢能場避障方法，給出了領(lǐng)航者時變情況下的跟隨者控制器與穩(wěn)定性證明。最后通過數(shù)值仿真證明了所提算法的有效性。

后續(xù)還可圍繞文中所提算法進(jìn)行以下研究：

（1）在實(shí)際應(yīng)用中，當(dāng)輸入達(dá)到一定程度時，再增加輸入常常不會影響輸出的變化，現(xiàn)有算法并未考慮這種輸入飽和問題，可以考慮增加飽和限制。

（2）對于很多智能體，速度信息常常難以獲得，即使裝有速度傳感器也可能出現(xiàn)失效等情況，因此可以考慮設(shè)計不需要速度信息的控制器，以提高系統(tǒng)魯棒性。