基于事件驅(qū)動的多智能體系統(tǒng)蜂擁控制

楊 誠 ，孔繁軍，戴 晶

（中國船舶重工集團公司 第 七一九研究所，湖北 武 漢 4 30064）

多智能體系統(tǒng)的協(xié)調(diào)控制是當(dāng)前控制領(lǐng)域研究的前沿方向，包含一致性、同步、編隊控制、分布式濾波等問題，在多機器人編隊系統(tǒng)[1]、無人飛機網(wǎng)絡(luò)系統(tǒng)[2]、傳感器網(wǎng)絡(luò)和分布式觀測與監(jiān)控[3]等領(lǐng)域有著重要的應(yīng)用前景。蜂擁是多智能體系統(tǒng)協(xié)調(diào)控制研究領(lǐng)域的一個重要問題，它描述的是大量個體朝著一個方向以相同的速度運動，且個體彼此之間保持一定的距離——既不分離，也不發(fā)生碰撞。由于蜂擁在人工仿生網(wǎng)絡(luò)系統(tǒng)等眾多工程領(lǐng)域有著廣泛的應(yīng)用，大量研究者對蜂擁行為進(jìn)行了深入的研究。

1987年，Reynolds給出了蜂擁控制的3個基本要求[4]，即分離（Separation）、聚合（Cohesion）和速度匹配（Alignment）。之后，Olfati-Saber[5]提出了一個理論上的蜂擁控制框架，設(shè)計了不同的數(shù)學(xué)算法并進(jìn)行了綜合性分析。文獻(xiàn)[6]中，作者對蜂擁控制算法中的人工勢函數(shù)重新進(jìn)行了構(gòu)造，利用加邊延遲規(guī)則結(jié)合新構(gòu)造的人工勢函數(shù)克服分裂現(xiàn)象。

目前，多智能體系統(tǒng)蜂擁控制研究大多采用的是連續(xù)的控制系統(tǒng)模型，即智能體通過與鄰居智能體之間進(jìn)行連續(xù)的通訊來獲得鄰居的狀態(tài)。然而在實際系統(tǒng)中，連續(xù)的信息傳輸必然帶來巨大的能源消耗。基于此，文中提出一種基于事件驅(qū)動的控制機制來實現(xiàn)多智能體系統(tǒng)的蜂擁行為。事件驅(qū)動控制機制是指在一個控制環(huán)中控制器和執(zhí)行器當(dāng)某個事件觸發(fā)時發(fā)起一次通訊的控制方法[7]。近年來，事件驅(qū)動機制作為一種替代傳統(tǒng)周期性時鐘驅(qū)動的控制方式被提出，這是因為，一方面事件驅(qū)動更符合實際網(wǎng)絡(luò)系統(tǒng)中個體交互和決策的行為特征；另一方面，事件驅(qū)動是按需驅(qū)動，即當(dāng)智能體有“需要”時，控制任務(wù)才執(zhí)行。從仿生學(xué)應(yīng)用的角度來看，這種控制機制更能夠適應(yīng)受通訊約束的分布式多智能體系統(tǒng)的設(shè)計需求，同時也有利于優(yōu)化系統(tǒng)資源。例如，在配備有微處理器的分布式無線傳感器/執(zhí)行器網(wǎng)絡(luò)中，應(yīng)用事件觸發(fā)的控制策略，可以降低處理器功率消耗，延長網(wǎng)絡(luò)壽命。

本文針對多智能體系統(tǒng)的蜂擁控制問題，首先結(jié)合傳統(tǒng)勢函數(shù)和速度一致性算法，設(shè)計了由事件驅(qū)動機制觸發(fā)速度信息交互的混雜控制算法；進(jìn)一步針對每個智能體，給出了基于誤差的分布式事件驅(qū)動條件。理論上證明了系統(tǒng)能實現(xiàn)穩(wěn)定的蜂擁運動，同時采用加邊延遲效應(yīng)設(shè)計了有界的勢函數(shù)保持網(wǎng)絡(luò)的連通性。最后，仿真驗證了方法的正確性。

1 符號說明

首先，介紹本文需要用到的符號。R和Z分別表示實數(shù)集和非負(fù)整數(shù)集，Z+表示正整數(shù)集。Rn表示維實向量空間，Rnxn表示n×n階實矩陣空間。In表示n維單位矩陣，In表示所有元素都為 1的 n維向量。對于對稱矩陣 A∈Rn×n，λmax(A)和 λmin(A)分別表示A的最大特征值和最小特征值。此外，用∩代表邏輯“或”運算，∪代表邏輯“與”運算。‖·‖表示矩陣的譜范數(shù)，?表示Kronecker積。

定義 G =(V，E，A）表示 n 維空間的無向圖，其中 V =是個智能體體的集合。Ni={j∈V，(j，i)∈E}表示頂點的鄰居集合，ni表示集合Ni的基數(shù)。E是由V中的無序點對構(gòu)成的邊集， 可表示為 E ?{(i，j):i，∈V,j≠i}（簡單圖），{j，i}∈E?(i，j}∈E，那么這個圖被稱為對稱的(Symmetric)或者無向圖 (Undirected)，若圖中任意兩個節(jié)點之間都存在一條路徑，則稱圖G為連通圖，否則為非連通圖。A={aij}N×N表示鄰接矩陣，其所有元素都是非負(fù)實數(shù)，當(dāng)(i，j}∈E 時，aij＞0，否則 aij=0。度矩陣D=diag｛ dij｝是N×N階對角陣，其中那么，Laplacian矩陣L可以表示為

引理2.1[5]：是無向圖G的Laplacian矩陣，鄰接矩陣A=AT且為非負(fù)的，那么：

1)L 的特征值滿足 0=λ1(L)≤λ2(L)≤…≤λN(L)，當(dāng)且僅當(dāng)圖G是連通的，有代數(shù)相關(guān)性λ2(L)＞0，且

2)矩陣L是半正定的矩陣，滿足下面的性質(zhì)：

引理2.2[8]：假設(shè)圖G是一個n維的無向圖，在圖 G中加入一些邊構(gòu)成圖 G1。 那么，λ2(L(G1))≥λ2(L(G))，其中 L(G)，L(G1)分別表示圖G和G1的Laplacian矩陣。

2 模型描述

考慮N智能體在n維的歐式空間中運行，可以假設(shè)第i個智能體的運動方程如下：

其中 xi∈Rn，vi∈Rn，ui∈Rn分 別 代表 智 能 體 i 的 位 置 向量，速度向量和控制輸入。

2） 如果(i,j)?E(t-)并且則智能體 i 和智能體j之間在時刻t產(chǎn)生一條連邊；

對每個智能體i，速度信息通訊只需在事件驅(qū)動時刻點處觸動，因此控制輸入為

定義‖xi-xj‖=‖xij‖，Ψxij(‖xij(t)‖)為非負(fù)光滑有界的分段人工勢函數(shù)，勢函數(shù)的梯度表示為▽Ψxij(‖xij(t)‖)，滿足

3 主要結(jié)果

定義4-1：對于一個多智能體系統(tǒng)，如果說系統(tǒng)可以實現(xiàn)穩(wěn)定的蜂擁狀態(tài)，那么當(dāng)且僅當(dāng)對于任意的初始狀態(tài)，滿足

滿足時被驅(qū)動。其中 θi∈(0,1)，?i=1,2,…,N,ni是 t時刻智能體 i鄰域內(nèi)個體數(shù)。常數(shù) a＜λ2(L(0))/(N-1)，λ2(L(0))是初始時刻系統(tǒng)的代數(shù)相關(guān)性。假設(shè)初始能量Q0為一個有限值，并且網(wǎng)絡(luò)是初始連通的。那么可以得到如下結(jié)論：

1)對于任意的t≥0，圖G(t)是連通的并且整個運動過程中沒有碰撞發(fā)生；

2)統(tǒng)漸進(jìn)的實現(xiàn)穩(wěn)定的蜂擁狀態(tài)。

證明：對于系統(tǒng)（7），定義一個類似能量的Lyapunov函數(shù))

由于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是時變的，Q是一個分段連續(xù)函數(shù)。定義系統(tǒng)的拓?fù)淝袚Q時間系列為t是它的不連續(xù)點。另外，控制輸入的更新序列為失一般性，假設(shè)T0=0。在區(qū)間t∈[T0,T1]上，對Lyapunov函數(shù)Q求導(dǎo)，可得

其中，ni是智能體i在t時刻鄰域內(nèi)智能體的個數(shù)，并且有可以得到

即Q˙(t)≤0,tk時刻沒有邊會斷開。因此整個運動過程中網(wǎng)絡(luò)是保持連通的。再根據(jù)引理2.2有，對于?t≥0，λ2(L(0))≤λ2(L(t)),那么事件條件式(8)可以應(yīng)用于整個運動過程中。進(jìn)一步，根據(jù)人工勢函數(shù)的定義，同樣可以得到對于?t＞0智能體之間的距離不會趨近于0，因此在整個運動過程中智能體之間沒有碰撞發(fā)生。

下面分析定理4-1中的結(jié)論2)。假設(shè)在時刻tˉkα，有mk條邊增加到網(wǎng)絡(luò)中來，因此，系統(tǒng)(7)的拓?fù)淝袚Q次數(shù)是有限的，那么網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)最終將保持不變。假設(shè)網(wǎng)絡(luò)的最后一個拓?fù)淝袚Q時刻是tˉk′α，那么對于 t∈是連續(xù)的且單調(diào)遞減的。接下來的分析可以限制到區(qū)域因此，集合｝是一個正的不變集。其中

注釋4-1：由于系統(tǒng)的平均速度v=v(0)，假設(shè)每個智能體能獲得系統(tǒng)的初始全局平均速度，那么事件驅(qū)動條件式(9)可以寫為

定理4-2：考慮一個具有個智能體的系統(tǒng)，它們的運動方程為(4)，每個智能體的控制輸入為式(5)并由集中式事件驅(qū)動更新，在如下事件條件

滿足時被驅(qū)動。假設(shè)初始的能量Q0為一個有限值并且網(wǎng)絡(luò)是初始連通的。那么：

1)對于任意的t≥0，圖G(t)是連通的并且整個運動過程沒有碰撞發(fā)生；

2)系統(tǒng)漸進(jìn)的實現(xiàn)穩(wěn)定的蜂擁狀態(tài)。

5 數(shù)值仿真

考慮10個智能體在二維平面上的運動。它們的初始位置和速度分別隨機產(chǎn)生于[-25,10]×[-25,10]和[-10,10]×[-10,10]。鄰域半徑R=30,智能體之間的理想距離為[8,10]，延遲距離為 τ=5，常數(shù) a可取 a=0.1＜λ2(L(0))/(N-1)。 仿真的結(jié)果如圖1和2所示。圖1繪出了所有智能體從t=0到t=20 s的運動軌跡。xi1,xi2分別是位置沿x,y坐標(biāo)軸的分量，箭頭代表速度的方向。圖2顯示了每個智能體速度模值的收斂情況并用垂直于時間軸的實線表示事件驅(qū)動時刻。

6 結(jié)論

本文采用事件驅(qū)動控制方法，研究了多智能體系統(tǒng)的蜂擁問題。提出了一種分布式事件驅(qū)動混雜控制算法，利用鄰域內(nèi)其他個體的位置信息和事件驅(qū)動時刻點處的速度信息，設(shè)計相應(yīng)的控制策略實現(xiàn)了系統(tǒng)的蜂擁行為。算法設(shè)計中，考慮到控制能量的有界性和網(wǎng)絡(luò)的連通性，利用加邊延遲效應(yīng)人工勢函數(shù)進(jìn)行了改進(jìn)。最后仿真驗證了結(jié)果的有效性。

圖1 10個智能體從t=0 s到t=20 s的運動軌跡Fig.1 The moving trajectories of 10 agents from 0 to 20s

圖2 10個智能體速度模值的收斂情況和事件驅(qū)動時刻Fig.2 The convergence trajectories of the modulus of velocity and the event-triggered instants of 10 agents

[1]Hayes A T，Dormiani-Tabatabaei P.Self-organized flocking with agent failure:off-line optimization and demonstration with real robots[C]//Robotics and Automation,Proceedings.ICRA'02,2002:3900-3905.

[2]Butt A R,Zhang R,Hu Y C.A self-organizing flock of condors[J].Journal of Parallel and Distributed Computing,2006,66(1):145-161.

[3]Schenato L,Fiorentin F.Average timesync:A consensus-based protocol for time synchronization in wireless sensor networks[J].Estimation and Control of Networked Systems,2009,1(1):30-35.

[4]Reynolds C W.Flocks,herds and schools:A distributed behavioral model[J].ACM SIGGRAPH Computer Graphics,1987,21(4):25-34.

[5]Olfati-Saber R.Flocking for multi-agent dynamic systems:algorithms and theory[J].IEEE Transactions on Automatic Control,2006,51(3):401-420.

[6]Zavlanos M M,Jadbabaie A,Pappas G J.Flocking while preserving network connectivity[C]//46thIEEE Conference on Decision and Control,2007:2919-2924.

[7]Stocker C,Lunze J.Event-based control of nonlinear systems:An input-output linearization approach [C]//Decision and Control and European Control Conference (CDC-ECC),2011:2541-2546.

[8]Merris R.Laplacian matrices of graphs:a survey[J].Linear Algebra and Its Applications,1994(197):143-176.

[9]Ji M Egerstedt M.Distributed Coordination control of multiagent systems while preserving connectedness[J].IEEE Transactions on Robotics,2007,23(4):693-703.