Proceedings of the 25th Chinese Control Conference7-11 August, 2006, Harbin, Heilongjiang

itltStv'icsek+Pb m I'4"f

+ tTVWWKiZ1 , IY,> 100080E-mail: Lguo@iss.ac.cn

7;ZZ: *t:t ffAZ_f2Jt_fVicsekf'TfOt, 2offl ffX W % tRbA' T,l AM Me8&< 9H-1 P)T_Ah -/\- iTA)~hi 1t1 bt < tK4- Fp ol

)A1f jff: $+8>T,WT Jf, _fIVicsekf*)TO M 4--r<fltlW , lSA Laplace)JEPT, A ttR

Convergence Analysis of Linearized Vicsek's Model

Gongguo Tang, Lei GuoAcademy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080

E-mail: Lguo@iss.ac.cn

Abstract: In this paper, the linearized Vicsek's Model will be considered. A sufficient condition will be establishedto guarantee the convergence of the agents' fly headings in large probability when the number of agents in the model issufficiently large.

Key Words: multi-agent system, collective behavior, linearized Vicsek's Model, convergence in large probability, graphLaplacians , normalized algebraic connectivity

1 C 1 F (Introduction)

5iHEtK, #ff)V T)fSAit[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] o j -

}U{H4X:L o~ dXTh htLX { -XThIA iTht#*HR,*X<i A-7MA,~2M)Y-S rlalR4l+))H138 1TH,f

fltUiX flffiX9C4$ "}% ThLJAG

H IL,X W&T 4* -4if "iET

_H_ It o TFAt # ItXJ #4UV,tnLIA 1) AJ kln X$XpV 9 fW1-Wi gSx_

1*1@4@8T aungff)VAffM

SII'1A@J,;WA$4H4tb9tAXlJA@T I'tiST

IEEE Catalog Number: 06EX13106022130,6034f40A , ],

60221301,60334040.

1t[1, 2, 3, 4] 31tY ,4+ *I SPb-fl\ll*

i diM"l1J½4§}+W zh0 Ua$$;'9i4tjJATz)jPrb t, T.VicsekXg f3i ,tTAfTVcsek

jII htL-YTii1987.tf,Ci.Reyn1dsH t5t61 o A7I

Vicsekt1327WI3JTOX1EBit1t)LI7W T.Vicsekfff A a l4R\'tUAM(spontaneous symmetry breaking)Afg

~T~ HY1 AL198Vf, C.Reynolds,>,ttA T+tf

A,2+t%if--O 8BoidrJ-flt[7] Boid8%ftP9

t~~~~tT)KT -Lt_fidtt #n,ffV inE A a+, ff

tIA Wf[LtA ffAr, AfftLilJAflbFJt ,YItI i l1XA4A INXI-ft tf l

379

>QA.Jadbabaie%2003tEf jt t[8].0 C H' X4Vicsekt1 t

WPt [Lh2 -t[]&ft9at j_4-< LM , )Fl pIrqtJ*, AMk-,M T k-"*-, .auqs ifflT < n XII INJv *Ab9S

T1WT Fl1[T H4EfVicsek flttt-4-,ffln ,b 9 f-R)Y *I JtfL kVT cLtszekfy' o-- rtl

fl~~ I~~iN~~ ± 4~~~V L IL"ThVs:4a1q1 iRIY/f14 IN fi 'A' t121*X914 VTb 1

4AtVXtlQSfl kfl1X&bf+Tf1; iA H'Pfl1

F.Cucker4l S.Smalet-[ 1] ' 1: t 7 -W2~~~~~~~ ~~~~FPTAAbfWtyZ,t;s1W1 b YX

; tUini1X8ff4$NT Ifflt.i LA-ThThh,

f Wp )AiH L2*1 LA ffiiJ H1 flXThIX l rtIX bM

IvLT 4L V IAHIN/flIN n 23Yi,AQtt)- d dNn[8 nyu V, YKYJb K fl f

_, 4s VlA Ti)LITh{H flTh[X,iL,NiLtLL1,j-X LibN1iL b-LH.JF a

'frif 41 itLA TtA fnx4k4I4fl, Li XtA sI4 11 X14b932~~Ai, tn,,AiXlAMXj ,At - I # b9tH8 8 ,A M

%_X@,~v , sA11AIE9 st4V9 fiSY H tid<

2 Lt]QiLi(Problem Formulation)

Vicsek&INO.fLt x - y- ffi-bn 1MvX2)Sflh@,it$.4tJ, 2,.. , no n-'i}UJlWHF1WAX4AA itL tH J,q l 4b:MieIA VLEltbA

JVk(t) ={j (Xk(t) t))2 + (Yk (t) yt))2 < r}

W Xk(t), yk(t)±4LX - yYJt<i&§Wit*+64Hi,tM8g,rn > oA<>13 4?8 nkJX+2(t)=

#,V/k(t)o XSo;JJzyXlk£TZk(t) = Xk(t) + iyk(t) i 1 X4Thfu 4gfl VicsektfAy',N iYL-4Th+VA k-t M AffOj7, VllJ* k 7if[4j bflt<A JA:

{&;. X Xk(t 1Vn ) + V Ok(11t" 1)4- AF> )J :

Xk (t) = Xk (t 1) + Vn cos Ok (t -1 )

Yk (t) = Yk (t -1) + Vn sin Ok (t -1)

Zk(t) = Zk(t -1) + vCeiOk(t- 1)

nk (t 1 ) iA'k (t- 1)

(1)

1) (2)

Jr! % t H4AJ t = 0, n-i fl7J ,P 4L Wf{zk (0), 1 <k < n} -MKY *fAH"I-,-] n4 413SzJy4Jfbf{Ok(0),1 < k <n}2i (7 :7)2 ill *H -4It b9f1 'x' tO~ P 41hN R

A;iQ2J gBA:J$9(1)fH(2)x-AA, tt1 t#ArKjU4At,tEni JY*tKLfl n'V, t-Sf1*SH rp] NArAt3} (t) rb (+

IBflG(n, rn ,t);G(t) AHt.fJ1B.id SCN12]o rX49A[J G, -L ki-f/J\ 2tJdk,k

dmin min dk1<k<n

dmax max dk1<k<n

T = diag(dk)1<k<n

.f;+j [Vj A, Laplace){F [4 ) L,L ; 'ft 2KJLaplace4L = T-112LT-112, p T-1A. Lf n-/\r44TMk

0 = Ao K A1 AK An-1 A ; R\);ALIZaftLfl J4 Xfft;LI yt, L #ti'H~,,l-Ekwd>Amaxl<k<n-1 1 Ak 9a70 < rn <1,1 Th,k, i

fThWK{Thk ={z (1Tn1n)rn < |Z-Zk(0)l %(<+Tn)rn<i' k2,7JRk, Rmax = maxi k Rk o tF

G(n, rntTiPLEb ;l 4S4SVNXn, iXtL RJi mJb9A lJt o n t = 0 H49 ) );Xt k-C,XT 4 rFl6

o

idEZ(t) =(Zl (t), Z2 (t), Zn ()T0(t) = (O 1(t) 02 (t) Olnt)T o0/142(4k2J

{ 0(t)

Z(t)

P(t- 1)0(t 1)

Z(t -1) + ()

Ok (t) = arctan jcArk (t -1) Sin Oj (t- 1)ft fei.(t) =(.iOl(t) eiO2(t) iO,(t))Tftb iE-X

380

--.:44, dtttVic sekf--V',t JE riiin,Af. AFI )Fl 1] 0

3 ±IER(Main Results)iB(Ol(t)) = max1js,n fOj(t) -min1ijn lOj(t).

TtMM,13JJ' stL{LVicsek1%½yk ]Th#ti8 fly<Xs 1+1W fl,Wi)iX t [13]@X32 jp0LfiB;A4

Sl-X I {G(t),t to}0 I Ovti'4t§0,{O(t), t > to}442bA

O(t + 1) = P(t)O(t)

iUAt, Ci\AP(t) A P(t)-9-1 P(t)-- [N G(t)f4Vtfi-G,

6(O(t)) <22N2 d (Amin

- PAiLAP(t) K<,t >to,+fMP )fF4t tQ G,0(to)

{XD)t-to -

min

0(o)~

tdmax, dmin,Ai5tG

1iSS X1fI A11l 1XlRi +Wf I g11*LTH$>-b9'x'P$0Ffib9%2fWT

)T- 1 t Ak 4± itVicsekOi lt f2 kEQ G(n, rn: °)O'§1 1+ +Y++

dmin < dmax K 3dmin(I + o(l))Rmax = O(dmin)

2) Lt3( (9 + 43/ 1+2)Rmax/dmin, &nt'+-k

A + 3 < 1

3)

log 5(0(1))2 2 0(1)I1 + 1+

log(A+ £3)1 < r1n rn

(A+ £3) Vn6(O (1))

+%'~~lgn =o(rnrn), J41

Rmax = 47nT/nr2 (1 + o(1))

L'FG(n, in, O){LT t4p V)g AdHocKAlg %[14, 15], LL fifi+T Jvvrfi JX4i

-I=T 3 St;A4tVicseki%!, 4Xigrn"iA( 1On)1 6o(rn)Xfrn = o(l), 4245ih'kc, ±

r5 <C (nX¾JK)r5n- log n

A9A t, A,Kt4Vicsek4,qt] B)7- 4k O

jjj)j tRTM%LtW2, W bS4 4, AL=83 R..o2 d,,i

A = max {1-Aj~}mtnn1-<_j-<n- 1{

= max{fl-A1, |1-An-li}-1A 1-n (I + o(l))144

9/ Tin =2X 1 X rn , F>[]Rmax = o(dmin), -YtkJRT)2 1328 144'

4f(1ogn)1 6 o(rn)llrn = o(),I logn o(fnrn)13R--2 x = 664/in, kLnn¾KkKt, A +

,/IK7J9t: 2 23m0(1

<log 2( log(A+

)

4log log( + 0())

W~~4V i44Ah£SJ1W1 9f4WQ2A88+b,AatATE$ tH MsF~~~~~tflt Xft lk lr]~1 1-nSTbfIT$ o itL

TI 2 41Errn, i =ogn o(rn)>Trn o(l), )JQitPk G(n, rn,O) I Fi Kk&AfLk

dmin

dmaxnwrnwr(1 + o(1))

l2log 0(1) /(

K log 20(1) (

log(A+ 2))

log(1 288( + 0()))

< log 2Vn/288 (1 +o(1))w 288log ni

= 144 (I + o(1))n

1 288A+ £3 r2

41- 2 < An-, < 2(1

nrrr2 (1 + o(1)) < Al < 2rn (1 + O(1))144

log niVn x 27 X 145 < rnT/nr2'n

381

I(I + 0 (1))127

9JiiI0nn34%±Ct, tW1 b9ffif$3)itriiR M o[13] L. Guo, "Time-Varying Stochastic Systems-HVt}@ q Stability,Estimation and Control," Jilin Science and

1nI 1 1 1 1 1 [14Technology Press, 1993.v5 < (x (x (xx x [14] P. Gupta, P. R. Kumar, "Critical power for asymptotic con-

rn 27 145 2 1328 144 log n nectivity in wireless networks," Stochastic Analysis, Con-

2w1tt X X X 44-27 145 2 1328 144 of W.H.Fleming, pp. 547-566, 1998.

vn <1 [15] F. Xue, P. R. Kumar, "The number of neighbors needed for

r'% cugn connectivity of wireless networks," Wirel. Netw. vol. 10, no.r logn 2, pp. 169-181,2004.

JA8t 0t, 2&t Vicsekf-'t.)<fk F

4 ii (Conclusion Remarks)

tX472[IfLt4Vicsek1%Xt X~l4iiYKt

X1Q H VU1 l'1$LdbEIFS o f1AE2 3ee %-RHrp t

[1] E. Shaw, "Fish in schools", Natural History, vol. 84, no. 8,pp. 40-46, 1975.

[2] B. L. Partridge, "The structure and function of fish schools",Sci. Amer., vol. 246, no. 6, pp. 114-123, 1982.

[3] A. Okubo, "Dynamical aspects of animal grouping: Swarms,schools, flocks and herds," Adv. Biophys., vol. 22, pp. 1-94,1986.

[4] J. K. Parrish, S. V. Viscido, and D. Grunbaum, "Self-organized fish schools: An examination of emergent prop-erties," Biol. Bull., vol. 202, pp. 296-305, 2002.

[5] T. Vicsek, A. Czirok, E.Jacob, I. Cohen, and 0. Shochet,"Novel type of phase transition in a system of self-derivenparticles," Phys. Rev. Lett., vol. 75, no. 6, pp. 1226-1229,1995.

[6] A. Czirok, A. Barabasi, T. Vicsek, "Collective Motion of SelfPropelled Particles: Kinetic Phase Transition in One Dimen-sion", Phys. Rev. Lett., vol. 82(1), pp. 209-212, 1999.

[7] C. W. Reynolds, "Flocks, herds, and schools: A dis-tributed behavioral model," in Comput. Graph. (ACM SIG-GRAPH' 87 Conf. Proc.), vol. 21, pp. 25-34, Jul. 1987.

[8] A. Jadbabaie, J. Lin, and A. S. Morse, "Coordination ofgroups of mobile agents using nearest neighbor rules," IEEETrans. Autom. Control, vol. 48, no. 6, pp. 988-1001, Jun.2003.

[9] W. Ren and R. W. Beard, "Consensus seeking in multia-gent systems under dynamically changing interaction topolo-gies," IEEE Trans. Autom. Control, vol. 50, no. 5, pp. 655-661, May 2005.

[10] A. Jadbabaie, "On distributed coordination of mobile agentswith changing nearest neighbors," Technical Report, Univer-sity of Pennsylvania, Philadelphia, PA, 2003.

[11] F Cucker and S. Smale, "Emergent behaviorin flocks", Preliminary Version, http://www.tti-c.org/smale papers/flock.pdf

[12] F R. K. Chung, "Spectral Graph Theory," Providence,RI:AMS, 2000.

382