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

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

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

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

7、鳥群、蟻群、…理論分析 ——Lyapunov函數(shù)構(gòu)造、特征值計算、凸分析、 隨機(jī)逼近、譜圖論、…,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)學(xué)會最佳論文獎]模型的分析依賴于Wolfowitz 定理: 給定有限個SIA 矩陣構(gòu)成的集合, 如果這個集合中的任何有限乘積也是SIA的, 那么從這個集合中生成的任何無限矩陣乘積是收斂的。 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ù)、特征值計算離散情形：構(gòu)造Lyapunov函數(shù)、特征值計算切換拓?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、則在過去若干年已被廣泛研究：,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,問題的挑戰(zhàn)性和難點(diǎn),挑戰(zhàn)性Stephen Smale (菲爾茲獎及沃爾夫獎得主)Brian Anderson (前國際

16、自動控制聯(lián)盟主席、前澳大利亞科學(xué)院院長)Stephen Morse (美國工程院院士)難點(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時刻形成的拓?fù)潢P(guān)系. .,狀態(tài)趨同:,擬解決的關(guān)鍵科學(xué)問題,31,匯報提綱,引言問題提出主要結(jié)果總結(jié)評論,,,,32,(A1): f 是一個定義于[a, b

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

20、 滿足 對任何的 是強(qiáng)聯(lián) 通的.(A4-2): 對任何的 是無向圖, 同時 ; 是聯(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,證明思想,定義如下符號：,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,選取個體

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