摘要
近年来,复杂动态网络受到来自物理、生物、数学、计算机、经济等不同学科领域的研究者越来越多的关注,其中基于群集智能的多智能体系统的协同控制已经成为一个研究热点。本论文对复杂动态网络的协同控制进行了多方面的研究,内容涉及到利用势函数的方法研究动态网络有leader和无leader时多智能体系统的运动。然后提出了基于图论和李亚普诺夫稳定性理论的方法来实现在复杂环境中多智能体系统在有限时间内达到预期状态的目的。最后利用卡尔曼滤波的方法,研究了多智能体系统的运动控制问题。每种研究方法都给出了有效的控制算法、稳定性分析及计算机仿真验证。研究结果有重要的理论意义与应用价值。
论文主要创新性工作如下:
(1)利用势函数的方法研究多智能体系统的协同控制,多智能体系统分为有leader和无leader的情况。多智能体系统的运动目的的是向预期位置聚集或编队并向目标位置移动。在势函数的构造中引入目标位置及环境信息对智能体的吸引能量,对预定运动目的的实现起到了积极的作用。
(2)研究多智能体系统有限时间协同控制,基于图论知识和李亚普诺夫稳定理论的控制方法来实现多智能体系统在有限时间内达到预期状态的目的。考虑在多智能体之间存在通讯延时,进行了多智能体系统一致性算法的设计,保证多智能体系统在有限时间内实现状态一致。
(3)研究多智能体系统有限时间协同控制,考虑在多智能体的运动环境中存在障碍的情况,多智能体系统的主要运动目的是能有效地避免与障碍物发生碰撞,并且绕过障碍物之后进行编队。通过计算机仿真,验证多智能体系统是否达到预期编队效果和避障的目的。
(4)研究基于卡尔曼滤波的多智能体系统的运动控制。考虑了智能体间的信号在传输与检测过程中受到外来干扰与传感设备内部噪声的影响,使用卡尔曼滤波的方法预测和判断下一步迁移的位置,实现动态迁移的目的,利用这种机制可以缩短实现目标的时间。
Recently, complex network has become an important interdisciplinary field, which attracts more and more researchers in physics, biology, mathematics, computer, etc, cooperative control of multi-agent system based on swarm-intelligence has become a hot topic in this area. In this paper, some research efforts are paid on the study on several problems in cooperative control of complex networks: movement of multi-agent system with leader and withoutleader is studied by using potential function approach. Then some control protocols based on algebraic graph theory and lyapunov stability theory are proposed to solve the finite-time reaching desired state of multi-agent system in complex entirvonment. Finally, movement of multi-agent system is studied by using kaermanfilter approach. Proper control and stability analysis and computer simulation are given in every research approach. The results have important theory significance and application value.
The main innovative work and key points are listed as follows:
(1) Movement of multi-agent system is studied by using potential function approach. The system are devided to two kinds: with leader and withoutleader. The movement object of system is to reach some desired or formation. In potential function, the attractive energy from desired situation or entirvonment to agents is used which has active to reach the object.
(2) Finite-time cooperative control of multi-agent system is studied. some control protocols based on algebraic graph theory and lyapunov stability theory are proposed to solve the finite-time reaching desired state of multi-agent system. In the design of finite-time protocol, the communication time-delays are taken into account. The protocols can guarantee finite-time agreement of multi-agent system.
(3) Finite-time cooperative control of multi-agent system is studied. Some obstacles are in the entirvonment. The movement object of system to. obstacle avoidance for multi-agent system and reach some desired formation is the main movement object. Through numerical simulations to show the effectiveness of the theoretical analysis results.
(4) Movement of multi-agent system based on kaermanfilter approach is studied. The effect of entirvonment disturbance and sensor noise are taken into account. So kaermanfilter approach is used to predict the next situation of some agent to reduce the movement time.
引文
[1]Watts D J,Strogatz S H.Collective dynamics of 'small-world' networks.Nature,1998,393:440-442
[2]Barabasi A L,Albert R.Emergence of scaling in random networks.Science,1999,289:509-512
[3]A.L.Barabsai,R.Albert,and H.Jeong.Mean-field theory for scale-free random networks.Phys.A.,1999,272:173-187
[4]Albert R and Barabasi A L.Statistical mechanics of complex networks.Reviews of Modern Physics,2002,74:47-97
[5]Newman M.E.J.Models of the Small World:A View.2000,1-9
[6]Newman M.E.J.The structure and function of complex networks.2003,1:58
[7]Dorogvtsev S.N.and J.F.F.Mendes.Evolution of Networks.Adv.Phys,2002,51(4):1079-1187
[8]X.F.Wang and G.Chen.Complex networks:small-world,scale-free and beyond.IEEE Trans.Circuits Syst,2003,3:6-20
[9]S.H.Strogatz.Exploring complex networks.Nature,2001,410:268-276
[10]Jinhu L(u|¨),Henry Leung and Guanrong Chen.Complex dynamical networks:modeling,synchronization and control.Dynamics of Continuous,Discrete and Impulsive Systems,Series B:Applications & Algorithms,2004,11a:70-77
[11]Hawoong Jeong.Complex scale-free networks.Physica A,2003,321:226-237.
[12]方锦清,江小帆,刘曾荣.略论复杂性问题和非线性复杂网络系统的研究.科技导报,2004,2:9-12,64
[13]Erd(o|¨)s P.,Renyi A.On random graphs.Publications Mathematic.1959,6,290-297.
[14]Albert R,Jeong H,Barabasi A L.The Internet's Achilles' Heel:Error and attack tolerance of complex networks.Nature(London),2000,406:378-382
[15]Newman M E J.Detecting community structure in networks.Euro.Phys.J.B,2004,38(2):321-330
[16]X.F.Wang,and G.Chen.Pinning control of scale-free dynamical networks.Phys.A,2002,310:521-531
[17]姚静,关治洪.拓扑切换网络的脉冲控制.复杂系统与复杂性科学,2005,2(2):24-29
[18]Zhi Li,Guanrong Chen.Robust adaptive synchronization of uncertain dynamical networks.Physics Letters A,2004,324:166-178
[19]郑毅,吴斌.由鸟群和蚂蚁想到的—基于主体的仿真和群集智能的研究.微电脑世界,2001,(1):7-13
[20]K E Parsopoulos,M N Vrahatis.Recent approaches to global optimization problems through particle swarm optimization.Natural Computing,2002,1(2):2352306
[21]J IN Wu-lun,GUO Yuan-lin.The sciences of complexity and their evolution.Complex Systems and Complexity Science,2004,1(1):125
[22]Cowan GA.Conference opening remarks.Complexity:Metaphors,model and reality.Cambridge:Addison-Wesley,1994,124.
[23]刘志新,韩靖,郭雷,基于vicsek模型的动态网络分析与调控,复杂网络,上海:上海科技教育出版社,2006
[24]http://automation.sjtu.edu.cn:81/cnc/webpage/cooperative.
[25]C.Reynolds.Flocks,herds,and schools:a distributed behavioral model.Computer Graphics,1987,21:24-34
[26]T.Vicsek,A.Czirok,E.B.Jacob,I.Cohen,and O.Schochet.Novel type of phase transition in a system of self-driven particles.Phs.Rev.Lett.,1995,75:1226-1229
[27]Adam T.Hayes,Parsa Dormiani-Tabatabaei.Self-organized Flocking with Agent Failure:Off-Line Optimization and Demonstration with Real Robots.Proceedings of the 2002 IEEE,2002,3900-3905
[28]Ali Raza Butt,Rongmei Zhang,and Y.Charlie Hu.A Self-Organizing Flock of Condors.Proceedings of the ACM/IEEE SC2003 Conference,2003,145-161
[29]Mitsunori Teruya,Zensho Nakao,Yen Wei Chen.A Boid-like Example of Adaptive Complex Systems,Proceedings of the 1999 IEEE,1999,Ⅳ:266-270
[30]Anthony Di Francol,Kumpati S.Narendra.A Simple Nearest-Neighbor Flocking Rule,Proceedings of the 2005 IEEE,2005,1-3
[31]Magnus Lindh'e,Petter Ogren,and Karl Henrik Johansson.Flocking with Obstacle Avoidance:A New Distributed Coordination Algorithm Based on Voronoi Partitions.Proceedings of the 2005 IEEE,2005,1985-1790
[32]Reza Olfati-Saber.Flocking for Multi-Agent Dynamic Systems:Algorithms and Theory.IEEE Transactions on Automatic Control,2006,51(3):401-420
[33]Veysel Gazi,Kevin M.Passino.Stability of a One-Dimensional Discrete-Time Asynchronous Swarm,IEEE Transactions on Systems,Man,and Cybernetics—Part B:Cybernetics,2005,35(4):834-841
[34]Veysel Gazi,Kevin M.Passino.Stability Analysis of Social Foraging Swarms,IEEE Transactions on Systems,Man,and Cybernetics—Part B:Cybernetics,2004,34(1):539-557
[35]Kassabalidis,M.A.El-Sharkawi,R.J.Marks,P.Arabshahi,A.A.Gray.Swarm Intelligence for Routing in Communication Networks.Proceedings of the 2001 IEEE,2001,3613-3617
[36]王玫,朱云龙,何小贤.群体智能研究综述.计算机工程,2005,31(22):194-196
[37]Benedikt Stefansson.Swarm- An Object Oriented Simulation Platform Applied to Markets and Organizations.Evolutionary Programming Ⅵ Lecture Notes in Computer Science,1997,1213:61
[38]Morgan M.Shepherd,Wm.Benjamin Martz,Jr.Group Consensus:Do We Know It When We See It?.Proceedings of the 37th Hawaii International Conference on System Sciences,2004,1-7
[39]Wei Ren,Randal W.Beard,Ella M.Atkins.A Survey of Consensus Problems in Multi-agent Coordination.2005 American Control Conference,2005,1859-1864
[40]Guangming Xie,Long Wang.Consensus Control for a class of Networks of Dynamic Agents:Switching Topology.Proceedings of the 2006 American Control Conference,2006,1382-1387
[41]Derek B.Kingston and Randal W.Beard.Discrete-Time Average-Consensus under Switching Network Topologies.Proceedings of the 2006 American Control Conference,2006,3551-3556
[42]Wen Yang,Xiao-Fan Wang,Consensus Problems in Networks of Multi-Agents,Second National Forum on Complex Dynamical Networks,2005:147-156.
[43]Wei Ren,Randal W.Beard,Derek B.Kingston.Multi-agent Kalman Consensus with Relative Uncertainty,2005 American Control Conference,2005,1865-1870
[44]J.Lin,A.S.Morse,B.D.O.Anderson.The Multi-Agent Rendezvous Problem-The Asynchronous Case.43rd IEEE Conference on Decision and Control,2004,1927-1931
[45]Jorge Cortes,Sonia Martinez,Francesco Bullo.Robust Rendezvous for Mobile Autonomous Agents via Proximity Graphs in Arbitrary Dimensions.IEEE Transactions on Automatic Control,2006,51(8):1289-1298
[46]李梦辉,樊瑛,狄增如.加权网络.见:郭雷等主编.复杂网络.上海:科教出版社,2006:27-47
[47]Almaas E,Kovacs B,Vicsek T,et al.Global organization of metabolic fluxes in the bacterium Escherichiacoli.Nature,2004(427):839
[48]Newman M E J.Scientific collaboration networks.I.network construction and fundamental results.Phys.Rev.E,2001(64):016131
[49]Newman M E J.Scientific collaboration networks.Ⅱ.Shortest paths,weighted networks,and centrality.Phys.Rev.E,2001(64):016132
[50]Newman M E J.The structure of scientific collaboration networks.Proc.Natl.Acad.Sci.USA,2001(98):404-409
[51]Li W,Cai X.Statistical analysis of airport network of China.Phys.Rev.E.,2004(69):046106
[52]Barrat A,Barthelemy M,Pastor-Satorras R,Vespignani A.The architecture of complex weighted networks.Proc.Natl.Acad.Sci.U.S.A.,2004,101:3747
[53]Yook S H,Jeong H,Barabasi A-L.Weighted evolving networks.Phys.R,ev.Lett.,2001,86(25):5835-5838.
[54]Barrat A,Barthelemy M,Vespignani A.Weighted evolving networks:coupling topology and weights dynamics.Phys.Rev.Lett.,2004,92:228701
[55]Wang W X,Wang B H,Hu B,et al.General dynamics of topology and traffic on weighted technological networks.Phys.Rev.Lett.,2005,94(18):188702.
[56]Wang W X,Hu B,Zhou T et al.Mutual selection model for weighted networks.Phys.Rev E,2005,72(4):046140
[57]Yang G,Zhou T,Wang J,Fu Wang W X,Hu B,Wang B H et ad.Mutual attraction model for both assortative and disassortative weighted networks.Phys.Rev.E,2006,73(1):016133
[58]Z Q,Wang B H.Epidemic spread in weighted scale-free networks.Chin.Phys.Lett.,2005,22(2):501
[59]Adilson E,Motter A E,Zhou C,Kurths J.Enhancing complex-network synchronization.Europhysics Letters,2005(69):334-340
[60]Motter A E,Zhou C S,Kurths J.Weighted networks are more synchronizable:how and why,AIP Conference Proceedings 2005,776:201
[61]Zhou C S,Motter A E,Kurths J.Universality in the synchronization of weighted random networks.Phys.Rev.Lett.,2006,96:034101
[62]Chavez M,Hwang D-U,Amann A,et al.Synchronization is enhanced in weighted complex networks.Phys.Rev.Lett.,2005(94):218707
[63]Dall'Asta L,Barrat A,Barthelemy M,Vespignani A.Vulnerability of weighted networks.Journal of Statistical Mechanics:Theory and Experiment,2006,P04006
[64]A.V.Savkin,Coordinated collective motion of groups of autonomous mobile robots:analysis of Vicsek's model,IEEE Transactions on Automatic Control,2004,39(6):981-983
[65]刘志新,郭雷.多个体系统的连通与同步.Proceedings of the 25th Chinese Control Conference,2006,7-11
[66]A.Jadbabaie,J.Lin,and A.S.Morse.Coordination of groups of mobile autonomous agents using nearest neighbor rules.IEEE Transactions on Automatic Control,2003,48(6):998-1001
[67]W.Ren and R.W.Beard,Consensus seeking in multiagent systems under dynamically changing interaction topologies,IEEE Transactions on Automatic Control,2005,50(5):655-661
[68]Luc Moreau,Stability of multiagent systems with time-dependent communication links,IEEE Transactions on Automatic Control,2005,50(2):169-182
[69]F.Cucker and S.Smale.Emergent behavior in flocks.[online]:http://www.tti-c.org/smale_papers/flock.pdf
[70]唐共国,郭雷.线性Vicsek模型的大概率同步.2006中国控制会议论文集,2006,4pp.|CD-ROM
[71]X.Liu and S.Zhang.Optimal incentive strategy for leader-follower games.IEEE Transactions on Automatic Control,1992,37(12):1957-1967
[72]H.Tanner,G.J.pappas,and V.Kumar.Leader-to-formation stability.IEEE Transactions on Automatic Control,2005,20(3):443-455
[73]L.D.Couzin,J.Krause,N.R.Franks,and S.A.Levin.Effective leadership and decision-making in animal groups on the move.Letters to Nature,2005,433:513-516
[74]N.Leonard and E.friorelli,Virtual leaders,artificial potentials and coordinated control of groups,Proceedings of 40th IEEE Conference on Decision Control,2001,2968-2976
[75]J.Han,M.Li,and L.Guo.Soft control on collective behavior of a group of autonomous agents by a shill agent.J.Systems Science and Complexity,2006,19(1):54-62
[76]李宗刚,贾英民.一种具有群体LEADER及利用局部信息的SWARM系统的聚集行为,第二十四届中国控制会议论文集,2006,323-327
[77]王凡,谭跃刚.改进人工势场法的多移动机器人路径规划.中国水运,2006,1
[78]C.Reynolds.Flocks,herds,and schools:a distributed behavioral model.Computer Graphics,1987,21:24-34
[79]Yanfei Liu and Kevin M.Passino.Stable Social Foraging Swarms in a Noisy Environment.IEEE Transactions on Automatic Control,2004,49(1):30-44
[80]Y.Hong,J.Hu and L.Gao.Tracking control for multi-agent consensus with an active leader and variable topology.Automatica,2006,42(7):1177-1182
[81]Jiangping Hu,Yiguang Hong.Coordination for a Group of Autonomous Mobile Agents with Multiple Leaders.Proceedings of the 25th Chinese Control Conference,2006,1502-1506
[82]X.P.Chen,A.Serrani,H.Ozbay.Control of leader-follower formations of terrestrial UAVs.IEEE Conference on Decision and Control,2003,498-503
[83]N.E.Leonard,E.Fiorelli.Virtual leader,artificial potentials and coordinated control of groups.IEEE Conference on Decision and Control,2001,2968-2973
[84]H.G.Tanner,A Jadbabaie,GJ.Pappas.Stable flocking of mobile agents,Part Ⅰ:Fixed Topology.Proceedings of the IEEE Conference on Decision and Control,2003,2010-2015
[85]Petter(O|¨)gren,Magnus Egerstedt,Xiaoming Hu.A Control Lyapunov Function Approach to Multiagent Coordination.IEEE Transactions on Robotics and Automatic,2002,18(5):847-851
[86]Qiuling Jia,Guangwen Li.Formation Control and Obstacle Avoidance Algorithm of Multiple Autonomous Underwater Vehicles(AUVs) Based on Potential Function and Behavior Rules.Proceedings of the IEEE International Conference on Automation and Logistics,2007,569-573
[87]J.Wang,X.B.Wu,Z.L.Xu.Decentralized formation control and obstacles avoidance based on potential field method.Proceedings of the Fifth International Conference on Machine Learning and Cybernetics,Dalian,2006,803-808
[88]Y.Hong,J.Hu,and L.Gao.Tracking control for multi-agent consensus with an active leader and variable topology.Automatica,2006,42:1177-1182
[89]A.Fax and R.Murray.Information flow and cooperative control of vehicle formations.IEEE Transactions on Automatic Control,2004,49(9):1453-1464
[90]R.Olfati-Saber.Flocking for multi-agent dynamic systems:algorithms and theory.IEEE Transactions on Automatic Control,2006,51(3):401-420
[91]E.Moulay,and W.Perruquetti.Finite time stability of nonlinear systems.Proceedings of IEEE Conference on Decision and Control,2006,3641-3646
[92]Olfati-Saber R,Murray R M.Consensus problems in networks of agents with switching topology and time-delays.IEEE Transactions on Automatic Control,2004,49(9):1520-1533
[93]M.Yu,L.Wang,and T.Chu.Stability analysis of networked systems with packet dropout and transmission delays. Asian J. of Control, 2005, 7(4): 433-439
[94] J. Cortes. Finite-time convergent gradient flows with applications to network consensus. Automatica, 2006,42:1993-2000
[95] E. Ryan. Finite-time stabilization of uncertain nonlinear planar systems. Dynamic Control, 1991, 1(1): 83-94
[96] X. Feng, and L. Wang. Reaching agreement in finite time via continuous local state feedback. Proceedings of Chinese Control Conference, 2007, 711-715
[97] Y. Hong, J. Huang and Y. Xu. On an output feedback finite-time stabilization problem. IEEE Transactions on Automatic Control, 2006,46(2): 305-309
[98] Z. Artstein. Linear systems with delayed controls: A reduction. IEEE Transactions on Automatic Control, 1982,27(4): 869-879
[99] Y. Hong. Finite-time stabilization and stabilizability of a class of controllable systems. Syst. Control Lett., 2002,46: 231-236
[100] Z. Artstein. Linear systems with delayed controls: A reduction. IEEE Transactions on Automatic Control, 1982, 27(4): 869-879
[101] J. A. Marshall, M. E. Broucke, and B. A. Francis. Formations of vehicles in cyclic pursuit. IEEE Transactions on Automatic Control, 2004,49: 1963-1974
[102] H. Tanner. Flocking with Obstacle avoidance in Switching Networks of Interconnected Vehicles. IEEE International Conference Robotics and Automation, 2004,3006-3011
[103] P. Ogren and N. E. Leonard. Obstacle Avoidance in Formation. IEEE International Conference Robotics and Automation, 2003,2492-2497
[104] S. P. Bhat and D. S. Bernstein. Nontangency-based Lyapunov tests for convergence and stability in systems having a continuum of equilibra. SIAM J. Control Optim., 2003, 42: 1745-1775
[105] Roumeliotis S I, Bekey G A. Collective localization: A distributed kalman filter approach to localization of groups of mobile robots. IEEE International Conference of Robotics Automation, 2000,2958-2965
[106] Schneider F E, Wildermuth D. Using an extended kalman filter for relative localization in a moving robot formation. Fourth International workshop on Robot Motion and Control, 2004, 85-90
[107] Godsil C, Royal G. Algebraic Graph Theory, Springer-Verlag, New York, 2001
[108] J. Hu and Y. Hong. Leader-following coordination of multi-agent systems with coupling time delays. Physica A, 2006, 372(2): 853-863
[109] R.O. Saber and R.M. Murray, Flocking with Obstacle Avoidance: Cooperations with Limited Communication in Mobile Networks, IEEE Conference on Decision and Control, 2003, 2022-2028
[110] Xiao L, Boyd S. Fast linear iterations for distributed averaging. Systems & Control Letters, 2006, 53: 65-78
[111] I. D. Couzin, J. Krause, R. James, G. D. Ruxton, and N. R. Franks. Collective memory and spatial sorting in animal group. J. Theor. Bio., 2002, 218: 1-11