陳姚-具有傳感非線性的離散時(shí)間

1、1,具有傳感非線性的離散時(shí)間多主體系統(tǒng)的狀態(tài)趨同,陳姚 中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院,CCCN, 蘇州, 2010年10月16日,2,致謝合作者,中科院數(shù)學(xué)與系統(tǒng)科學(xué)研究院 呂金虎教授美國(guó)弗吉尼亞大學(xué) 林宗利教授,3,匯報(bào)提綱,引言問(wèn)題提出主要結(jié)果總結(jié),4,Part I: 引言,多主體系統(tǒng)的實(shí)例什么是多主體系統(tǒng) (MAS)?多主體系統(tǒng)的主要特征,5,例子: 鳥(niǎo)群的群體行為,,,6,例子:

2、魚(yú)群的運(yùn)動(dòng),7,例子: 螞蟻的覓食,8,例子: 細(xì)菌群落,9,例子: 社會(huì)和經(jīng)濟(jì)系統(tǒng),10,問(wèn)題: 如何在2維或3維空間中保持隊(duì)形,例子: 編隊(duì)控制,自治個(gè)體,,11,例子: 多機(jī)器人合作,12,什么是多主體系統(tǒng) (MAS)?,自治個(gè)體 昆蟲(chóng)、鳥(niǎo)、魚(yú)、社會(huì)人、機(jī)器人、 細(xì)菌、粒子、… 個(gè)體間的局部作用規(guī)則,13,多主體系統(tǒng)的主要特征,自治/自我驅(qū)動(dòng)的 個(gè)體 分布式 區(qū)域 局部的 相互作用 動(dòng)態(tài)變化的 鄰居 各

3、種不同的 連接 可變化的 行為,14,匯報(bào)提綱,引言問(wèn)題提出主要結(jié)果總結(jié)評(píng)論,,,,15,Part II: 問(wèn)題提出,已有的模型 —Vicsek模型、Boid模型、Couzin-Levin模型、…已有的分析方法 —趨同、收斂、自適應(yīng)、…我們的模型 —帶有非線性傳輸?shù)亩嘀黧w系統(tǒng),16,代表模型——Boids模型 (1987),Reynolds, Flocks, herd, and schools:

4、 A distributed behavioralmodel, Computer Graphics, 1987, 21(4): 15-24.[SCI引用3419次],基本局部規(guī)則：對(duì)齊：每個(gè)個(gè)體調(diào)整自己的運(yùn)動(dòng)方向使其接近其鄰居個(gè) 體的平均運(yùn)動(dòng)方向排斥：當(dāng)個(gè)體間靠得很近的時(shí)候相互排斥吸引：當(dāng)個(gè)體間靠得很遠(yuǎn)的時(shí)候相互吸引,17,代表模型——Vicsek粒子運(yùn)動(dòng)模型(1995),,Vicsek, et al.

5、, Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett., 1995, 75 (6): 1226. [SCI引用1013次],位置更新：,角度更新：,基本的局部規(guī)則：對(duì)齊 (最簡(jiǎn)單的模型),18,,Vicsek, et al., Novel type of phase transition in a system of

6、self-driven particles, Phys. Rev. Lett., 1995, 75 (6): 1226. [SCI引用1013次],(a) 初始化：隨機(jī)初始位置和速度(b)低密度/低噪聲：個(gè)體成群(c) 高密度/高噪聲：方向逐漸相關(guān)(d)高密度/低噪聲：有序運(yùn)動(dòng),代表模型——Vicsek粒子運(yùn)動(dòng)模型(1995),主要方法——多主體系統(tǒng)的分析,數(shù)值仿真 ——仿真平臺(tái)、數(shù)學(xué)或計(jì)算機(jī)模型實(shí)驗(yàn)觀測(cè) ——魚(yú)群、

7、鳥(niǎo)群、蟻群、…理論分析 ——Lyapunov函數(shù)構(gòu)造、特征值計(jì)算、凸分析、 隨機(jī)逼近、譜圖論、…,20,通過(guò)線性化來(lái)簡(jiǎn)化Vicsek模型: A. Jadbabie, J. Lin, and A.S. Morse, Coordination of groups ofmobile autonomous agents using nearest neighbor rules, IEEETrans. Aut

8、omat. Contr., 2003, 48(6): 988-1001 [2005年IEEE 控制系統(tǒng)學(xué)會(huì)最佳論文獎(jiǎng)]模型的分析依賴于Wolfowitz 定理: 給定有限個(gè)SIA 矩陣構(gòu)成的集合, 如果這個(gè)集合中的任何有限乘積也是SIA的, 那么從這個(gè)集合中生成的任何無(wú)限矩陣乘積是收斂的。 J. Wolfowitz, Products of indecomposable, aperiodic,

9、 stochastic matrices, Proc. Amer. Math. Soc, 1963, 15: 733-737.,Vicsek模型的理論分析,21,方法比較（一）：連續(xù) vs. 離散,固定拓?fù)溥B續(xù)情形：構(gòu)造Lyapunov函數(shù)、特征值計(jì)算離散情形：構(gòu)造Lyapunov函數(shù)、特征值計(jì)算切換拓?fù)溥B續(xù)情形：Lyapunov函數(shù)構(gòu)造離散情形：凸分析、隨機(jī)逼近、譜圖論

10、二次Lyapunov函數(shù)不存在——困難！,A. Olshevsky, J. N. Tsitsiklis, On the nonexistence of quadratic Lyapunov function for consensus algorithms, IEEE Trans. Automat. Contr., 2008, 53(11): 2642-2645.,22,方法比較（二）： 凸性 vs. 非凸性,什么是凸性？,More

11、au, L. (2005). Stability of multiagent systems with time-dependent communication links, IEEE Trans. Automat. Contr., 50(2), 169-182.,23,方法比較（二） ： 凸性 vs. 非凸性,凸性模型大部分已有的多主體系統(tǒng)模型滿足凸性 Lyapunov 函數(shù)通常比較容易構(gòu)造 非凸性模型非

12、凸模型很少被研究Lyapunov函數(shù)很難找到——困難！,Moreau, L. (2005). Stability of multiagent systems with time-dependent communication links, IEEE Trans. Automat. Contr., 50(2), 169-182.,24,方法比較（三）： 線性 vs. 非線性,,,,,,,,,,,,,,,25,已有結(jié)果下面線性局部規(guī)

13、則在過(guò)去若干年已被廣泛研究：,26,已有結(jié)果,A. Jadbabaie, J. Lin and A. S. Morse, IEEE-TAC, 2003 R. Olfati-Saber and R. M. Murry, IEEE TAC, 2004 L. Moreau, IEEE TAC, 2005 W. Ren and R. W. Beard, IEEE TAC, 2005 J. Cortes, S. Martinez, and

14、 F.Bullo, IEEE TAC, 2006 R. Olfati-Saber, IEEE TAC, 2006 Z. Liu and L. Guo, Science in China Ser. F, 2007 J. Lin, A. S. Morse, and B. D. O. Anderson, SIAM, 2007 F. Cucker and S. Smale, IEEE TAC, 2007 M. Cao, A. S. M

15、orse, and B. D. O. Anderson, IEEE TAC, 2008 H. Su, X. Wang, and Z. Lin, IEEE TAC, 2009 W. Yu, G. Chen, M. Cao, J. Lü, 2009 T. Chen, W. Lu, 2009 ……,27,問(wèn)題的挑戰(zhàn)性和難點(diǎn),挑戰(zhàn)性Stephen Smale (菲爾茲獎(jiǎng)及沃爾夫獎(jiǎng)得主)Brian Anderson (前國(guó)際

16、自動(dòng)控制聯(lián)盟主席、前澳大利亞科學(xué)院院長(zhǎng))Stephen Morse (美國(guó)工程院院士)難點(diǎn)非凸系統(tǒng)的研究非線性系統(tǒng)的研究,28,,已有的文獻(xiàn)中很少有關(guān)于非線性局部規(guī)則的研究. Vicsek模型(PRL, 1995): 非線性L. Moreau, Stability o

17、f multiagent systems with time-dependent communication links, IEEE TAC, 2005, 50(2): 169-182. L. Fang, P.J. Antsaklis, Asynchronous consensus protocols using nonlinear paracontractions theory, IEEE TAC, 2008, 53(10): 23

18、51-2355.,非線性局部規(guī)則,,29,非線性模型,,,,,,,,,,,,,,,30,,什么樣的非線性函數(shù) f 和拓?fù)?G(t) 能保證如下多主體系統(tǒng)的狀態(tài)趨同?,*G(t)=(V, E(t)) 是結(jié)點(diǎn)V在t時(shí)刻形成的拓?fù)潢P(guān)系. .,狀態(tài)趨同:,擬解決的關(guān)鍵科學(xué)問(wèn)題,31,匯報(bào)提綱,引言問(wèn)題提出主要結(jié)果總結(jié)評(píng)論,,,,32,(A1): f 是一個(gè)定義于[a, b

19、]上的連續(xù)函數(shù)(A2): 存在某個(gè) 滿足: 當(dāng) 時(shí) ; 當(dāng) 時(shí) .(A3): 存在某個(gè)整數(shù) 滿足對(duì)任何的 有 ; 對(duì) 有 .(A4-1): 存在某個(gè)

20、 滿足 對(duì)任何的 是強(qiáng)聯(lián) 通的.(A4-2): 對(duì)任何的 是無(wú)向圖, 同時(shí) ; 是聯(lián)通的.,,若干假設(shè),33,Theorem 1: Suppose that (A1), (A2), (A3),

21、 (A4-1) hold for a given MAS (1). For any given initial states in [a,b], the states of all agents can reach consensus.,主要結(jié)果,Theorem 2: Suppose that (A1), (A2), (A3), (A4-2) hold for a given MAS (1). For any given initial

22、 states in [a,b], the states of all agents can reach consensus.,34,證明思想,定義如下符號(hào)：,35,Lemma 1: If assumptions (A1), (A2), (A3), (A4-1) hold for the MAS (1). Then for any and .,證明思想,Lemma 2: If assumption

23、s (A1), (A2), (A3), (A4-1) hold for the MAS (1). Then there exists some such that and .,Lemma 3: If assumptions (A1), (A2), (A3), (A4-1) hold for the MAS (1). Then where

24、 is defined in Lemma 2 .,Suppose c=a in A2 and take Theorem 1 for example.,36,Lemma 4: If satisfying assumptions A1 and A2. Then, for any given and any positive integer N, there exist some and a sequen

25、ce with such that hold for any and .,證明思想,Lemma 5:There exists a subsequence of natural numbers satisfying and

26、 .,BASIC IDEA: Show that m(t) is nondecreasing and M(t) is upper bounded (the monotonicity of M(t) can not be got), then prove that m(t) and M(t) have a same limit by reduction to absurdity.,37,證明思想,38,令：,仿真結(jié)果,39,選取個(gè)體

27、間的拓?fù)錇槿缦滦问? 選取 同時(shí)隨機(jī)地從 中選取 的值.,仿真結(jié)果,40,,,,仿真結(jié)果 (1),初始狀態(tài)從 [0,6] 中選取.,41,,,,仿真結(jié)果 (2),初始狀態(tài)從 [6,12] 中選取.,42,,,,仿真結(jié)果 (3),初始狀態(tài)從 [0,12] 中選取.,43,匯報(bào)提綱,引言問(wèn)題提出主要結(jié)果總結(jié),,,,44,Part IV: 總結(jié)—主要?jiǎng)?chuàng)新點(diǎn),首次研究了