陳姚-具有傳感非線性的離散時間

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

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

3、種不同的 連接 可變化的 行為,14,匯報提綱,引言問題提出主要結果總結評論,,,,15,Part II: 問題提出,已有的模型 —Vicsek模型、Boid模型、Couzin-Levin模型、…已有的分析方法 —趨同、收斂、自適應、…我們的模型 —帶有非線性傳輸?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ī)則：對齊：每個個體調整自己的運動方向使其接近其鄰居個 體的平均運動方向排斥：當個體間靠得很近的時候相互排斥吸引：當個體間靠得很遠的時候相互吸引,17,代表模型——Vicsek粒子運動模型(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ī)則：對齊 (最簡單的模型),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) 初始化：隨機初始位置和速度(b)低密度/低噪聲：個體成群(c) 高密度/高噪聲：方向逐漸相關(d)高密度/低噪聲：有序運動,代表模型——Vicsek粒子運動模型(1995),主要方法——多主體系統(tǒng)的分析,數(shù)值仿真 ——仿真平臺、數(shù)學或計算機模型實驗觀測 ——魚群、

7、鳥群、蟻群、…理論分析 ——Lyapunov函數(shù)構造、特征值計算、凸分析、 隨機逼近、譜圖論、…,20,通過線性化來簡化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)學會最佳論文獎]模型的分析依賴于Wolfowitz 定理: 給定有限個SIA 矩陣構成的集合, 如果這個集合中的任何有限乘積也是SIA的, 那么從這個集合中生成的任何無限矩陣乘積是收斂的。 J. Wolfowitz, Products of indecomposable, aperiodic,

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

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ù)通常比較容易構造 非凸性模型非

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,已有結果下面線性局部規(guī)

13、則在過去若干年已被廣泛研究：,26,已有結果,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,問題的挑戰(zhàn)性和難點,挑戰(zhàn)性Stephen Smale (菲爾茲獎及沃爾夫獎得主)Brian Anderson (前國際

16、自動控制聯(lián)盟主席、前澳大利亞科學院院長)Stephen Morse (美國工程院院士)難點非凸系統(tǒng)的研究非線性系統(tǒng)的研究,28,,已有的文獻中很少有關于非線性局部規(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 和拓撲 G(t) 能保證如下多主體系統(tǒng)的狀態(tài)趨同?,*G(t)=(V, E(t)) 是結點V在t時刻形成的拓撲關系. .,狀態(tài)趨同:,擬解決的關鍵科學問題,31,匯報提綱,引言問題提出主要結果總結評論,,,,32,(A1): f 是一個定義于[a, b

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

20、 滿足 對任何的 是強聯(lián) 通的.(A4-2): 對任何的 是無向圖, 同時 ; 是聯(lián)通的.,,若干假設,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.,主要結果,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,證明思想,定義如下符號：,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,令：,仿真結果,39,選取個體

27、間的拓撲為如下形式: 選取 同時隨機地從 中選取 的值.,仿真結果,40,,,,仿真結果 (1),初始狀態(tài)從 [0,6] 中選取.,41,,,,仿真結果 (2),初始狀態(tài)從 [6,12] 中選取.,42,,,,仿真結果 (3),初始狀態(tài)從 [0,12] 中選取.,43,匯報提綱,引言問題提出主要結果總結,,,,44,Part IV: 總結—主要創(chuàng)新點,首次研究了