下载文档原格式
MPC特点原理以及各项参数的选择--引⽤别⼈的博客⽹址参见：MATLAB techtalk 中关于MPC的讲解视频：或者：下⾯是转载别⼈参照视频所作的笔记记录：参见⽹址：https:///u013414501/article/details/51772672MPC的三⼤要素：预测模型——对未来⼀段时间内的输出进⾏预测；滚动优化——滚动进⾏有限时域在线优化(最优控制)；反馈校正——通过预测误差反馈，修正预测模型，提⾼预测精度。
Mo(measured output): 当前可测量的输出信号Ref(Reference signa): 参考信号Md(optional measured disturbance signa): 可选的测量⼲扰信号Mv（optimal manipulated variables ）：最优操纵变量MPC⼀般通过求解⼀个⼆次规划来计算最优操纵变量MPC作⽤机理为：在每⼀个采⽤时刻，根据获得的当前测量信息，在线求解⼀个有限时间开环优化问题，并将得到的控制序列的第⼀个元素作⽤于被控对象。
在下⼀个采样时刻，重复上述过程：⽤新的测量值作为此时预测系统未来动态的初始条件，刷新优化问题并重新求解。
即MPC算法包括三个步骤：（1）预测系统未来动态；（2）（数值）求解开环优化问题；（3）将优化解的第⼀个元素（或者说第⼀部分）作⽤于系统这三步是在每个采样时刻重复进⾏的，且⽆论采⽤什么样的模型，每个采样时刻得到的测量值都作为当前时刻预测系统未来动态的初始条件在线求解开环优化问题获得开环优化序列是MPC和传统控制⽅法的主要区别，因为后者通常是离线求解⼀个反馈控制律，并将得到的反馈控制律⼀直作⽤于系统。
在这⾥给出两点说明：1.MPC是⼀个反馈控制策略，但是之前不是说将得到的控制序列中的第⼀个元素作⽤于被控对象，求解开环问题。
那么哪来的反馈呢？实际上在下⼀个采样周期，下⼀时刻的测量值⼜被使⽤上了，⽤下⼀时刻的测量值求解下⼀时刻的控制值。
一专业词汇（红色字体为新课本的单词，14、17章不考）人工智能artificial intelligence电子绩效支持系统（EPSS ）electronic performance support systems教学技术instructional technology面向媒体media-oriented 面向过程process-oriented系统化systematic 利用utilization媒体特性attribute of media函授课程correspondence course 主机，大型机mainframe 无显著差异no significant difference媒体大争论the great media debate视盘videodisk 绩效技术performance technology情境认知situated cognition视听传播audiovisual communication智能代理intelligent agent 虚拟现实virtual reality经验之塔cone of experience 一般系统论general system 教学系统设计( ISD ) instructional systems design知识管理系统knowledge management systems学习者为中心的学习环境learner-centered learning environments程序教学programmed instruction学科内容专家(SME) Subject Matter Experts任务分析task analysis 言语主义verbalism传播，传播学communications 操作性条件反射operant conditioning进步主义progressivism 强化reinforcement远程教育distance education实时的real-time 直观概念intuitive notion图式理论schema theory 精细化理论elaboration theory元认知metacognition经典型条件反射classical conditioning操作性条件反射operant conditioning言语行为verbal behavior 认知科学cognitive science长时记忆long-term memory 短时记忆short-term memory 乘法表multiplication table 学习分类taxonomy of learning行为主义behaviorism 认知主义cognitivism建构主义constructivism个性化教学individualized instructional教学开发instructional development咨询系统advisory system 著作工具authoring tools信息管理information management知识管理knowledge management智能导师系统intelligent tutoring system交互式仿真模拟interactive simulations系统化教学开发systematic instructional development学习管理系统learning management system客观主义objectivism 后现代注意postmodernism发现学习discovery learning信息加工理论information-processing theory教学策略instructional strategy 绩效潜能performance potential 问题解决problem solving核心传播理论core communication theory社会动力学societal dynamics传播理论communication theory群体传播group communication人际传播interpersonal communication大众传播mass communication 收文incoming message 协作网络cooperative network发送者和接收者sender and receiver创新推广理论（IDT）Innovation Diffusion Theory混沌理论chaos theory复杂性和相互依赖性complexity and interdependence自然科学natural science 系统动力学system dynamics系统思考systems thinking学习结果分类category of learning outcome认知信息加工理论cognitive information processing theory建构主义学习理论constructivism learning theory教育目标educational objective 教学事件event of instruction 智慧技能intellectual skill 学习条件learning conditions动作技能motor skill 程序教学programmed instruction 言语信息verbal information 认知策略cognitive strategy机械学习rote learning 非随意性non-arbitrary先有知识prior knowledge 迭代过程iterative process同化assimilation 逐字回忆verbatim recall评价/测量策略measurement strategy社会学习理论social learning theory教学机器teaching machine 教学事件event of instruction学习目标分析analysis of learning goal评价工具evaluation instrument教学模式instructional model形成性评价formative evaluation总结性评价summative evaluation 前端分析front-end analysis学习环境learning environment以学生为中心的学习student-centered learning技术支持的学习环境technology-supported learning environment教学设计自动化系统AID system（The teaching design automation system）Automated I D智能代理intelligent agent 知识对象knowledge object 认知技能cognitive skil 协作学习cooperative learning信息素养information literacy信息高速公路information highway关键技能critical skills终身学习lifelong learning技术素养technological literacy应用型研究applied research批判性探究critical inquiry经验材料empirical material定量研究quantitative research基于问题的problem-based实施阶段Implementation phase确定目标State objectives通信革命communication revolution九段教学法Nine event of instruction学习者特征Learner Characteristics视听教学audiovisual instruction案例研究case study应用性研究applied research因果关系cause-effect relationships控制组control group经验材料empirical materials实验组experimental group实验处理experimental treatment形成假设hypothesis formulation独立变量independent variable数据资料numerical data定量研究quantitative research准实验的quasi-experimental社会调查social survey主题subject matter元认知metacognition知识库knowledge base心智模型mental model知识迁移knowledge transfer高阶技能higher order skills自我意识self-awareness教学干预instructional intervention视频会议videoconferencing录像带videotape独立学习independent study学习结果learning outcome人种超媒体二、缩写20分（红色字体为已考）AECT（Association for Educational Communications and Technology）教育传播与技术协会DA VI（Department of Audiovisual Instruction）视听教学部ECIT（Educational Communications and Instructional Technology）教育传播和教学技术EPSS（Electronic Performance Support Systems）电子绩效支持系统Committee on Definitions and Terminology 定义与术语委员会ISD（instructional system design）教学系统设计ID（instructional design）教学设计SME（Subject Matter Expert）学科内容专家VR（virtual reality）虚拟现实DVI（Department of Visual Instruction）视觉教学部CAI(computer-assisted instruction)电脑辅助教学LMS(learning management system)学习管理系统CD（Compact Disk）光盘DVD（digital video disk）数字化视频光盘VCR（Video Cassette Recorder）录像机WWW（World Wide Web）万维网HBO（Home Box Office）家庭影院DVR（Digital Video Recorder）数字录像机MPC（multimedia personal computer）个人多媒体计算机AI（Artificial Intelligence）人工智能AR（Artificial reality）人工现实CD-ROM（Compact Disk Read－Only Memory）光盘只读存储器CMC（Computer－Mediated Communication）计算机媒介沟通，计算机传媒通信LCD (Liquid Crystal Display) 液晶显示器NIR（Network Information Retrieval）网络信息搜索系统ID1（The First Generation Instruction Design）第一代教学设计ID2（The Second Generation Instruction Design）第二代教学设计AID（Automated Instruction Design）自动化教学设计IDE（Instructional Design Environment）教学设计环境CBI（computer-based instruction）计算机辅助教学ICT（Information and Communication Technology）信息与通信技术ALA（The American Library Association）美国图书馆协会OTEN（Open Training and Education Network）开放式培训与教育网络ODL（Open and Distance Learning）开放和远程学习COL（The Commonwealth of Learning）学习共同体ICDE（International Council for Open and Distance Education）国际开放与远程教育协会JTA（Job Task Analysis）工作任务分析ZPD（Zone Of Proximal Development）最近发展区LAN 局域网。
传播政治经济学常用学术用语中英文1.供给和需求(Supply and Demand)- The principle of supply and demand determines the equilibrium price of a good or service.-供给与需求的原理决定了商品或服务的均衡价格。
2.边际效应(Marginal Effect)- Marginal effect refers to the change in the outcome resulting from a one-unit change in an independent variable.-边际效应是指独立变量的一单位变化所引起的结果变化。
3.地租(Rent)- Rent is the payment made to the owner of a property or resource for its use.-地租是用于租赁房地产或资源的产权所有人的支付。
4.货币供应(Money Supply)- Money supply refers to the total amount of money in circulation within an economy.-货币供应指的是经济体内流通的总货币数量。
5.资本积累(Capital Accumulation)- Capital accumulation refers to the growth of a nation's stock of capital goods, such as factories, machinery, and infrastructure.-资本积累指的是一个国家资本货物库存的增长，如工厂、机械和基础设施等。
6.社会福利(Social Welfare)- Social welfare refers to the well-being and quality of life of individuals within a society.-社会福利指的是一个社会中个体的福祉和生活质量。
⽂献徐胜元简介：徐胜元，男，南京理⼯⼤学⾃动化学院教授、博⼠、博⼠⽣导师。
毕业于南京理⼯⼤学控制理论与控制⼯程专业，获得博⼠学位。
研究⽅向：1、鲁棒控制与滤波2、⼴义系统3、⾮线性系统2017年SCI1.Relaxed conditions for stability of time-varying delay systems ☆TH Lee，HP Ju，S Xu 《Automatica》, 2017, 75:11-15EI1.Relaxed conditions for stability of time-varying delay systems ☆TH Lee，HP Ju，S Xu 《Automatica》, 2017, 75:11-152.Adaptive Tracking Control for Uncertain Switched Stochastic Nonlinear Pure-feedback Systems with Unknown Backlash-like HysteresisG Cui，S Xu，B Zhang，J Lu，Z Li，...《Journal of the Franklin Institute》, 20172016年SCI1..Finite-time output feedback control for a class of stochastic low-order nonlinear systemsL Liu，S Xu，YZhang《International Journal of Control》, 2016:1-162.Universal adaptive control of feedforward nonlinear systems with unknown input and state delaysX Jia，S Xu，Q Ma，Y Li，Y Chu《International Journal ofControl》, 2016, 89(11):1-193.Robust adaptive control of strict-feedback nonlinear systems with unmodeled dynamics and time-varying delaysX Shi，S Xu，Y Li，W Chen，Y Chu《International Journal of Control》, 2016:1-184.Stabilization of hybrid neutral stochastic differential delay equations by delay feedback controlW Chen，S Xu，YZou《Systems & Control Letters》, 2016, 88(1):1-135.Multi-agent zero-sum differential graphical games for disturbance rejection in distributed control ☆Q Jiao，H Modares，S Xu，FL Lewis，KG Vamvoudakis《Automatica》, 2016, 69(C):24-346.Semiactive Inerter and Its Application in Adaptive Tuned Vibration AbsorbersY Hu，MZQ Chen，S Xu，Y Liu《IEEE Transactions on Control Systems Technology》, 2016:1-77.Decentralised adaptive output feedback stabilisation for stochastic time-delay systems via LaSalle-Yoshizawa-type theoremT Jiao，S Xu，J Lu，Y Wei，Y Zou《International Journal of Control》, 2016, 89(1):69-838.Coverage control for heterogeneous mobile sensor networks on a circleC Song，L Liu，G Feng，S Xu《Automatica》, 2016, 63(3):349-358EI1.Finite-time output feedback control for a class of stochastic low-order nonlinear systemsL Liu，S Xu，YZhang《International Journal of Control》, 2016:1-162.Unified filters design for singular Markovian jump systems with time-varying delaysG Zhuang，S Xu，B Zhang，J Xia，Y Chu，...《Journal of the FranklinInstitute》, 2016, 353(15):3739-37683.Improvement on stability conditions for continuous-time T–S fuzzy systemsJ Chen，S Xu，Y Li，Z Qi，Y Chu《Journal of the Franklin Institute》, 2016, 353(10):2218-22364.Universal adaptive control of feedforward nonlinear systems with unknown input and state delaysX Jia，S Xu，Q Ma，Y Li，Y Chu《International Journal ofControl》, 2016, 89(11):1-195.H∞ Control with Transients for Singular Systems Z Feng，J Lam，S Xu，S Zhou 《Asian Journal of Control》, 2016,18(3):817-8272015年SCI1.Pinning control for cluster synchronisation of complex dynamical networks withsemi-Markovian jump topologyTH Lee，Q Ma，S Xu，HP Ju《International Journal of Control》, 2015, 88(6):1223-12352..Anti-disturbance control for nonlinear systems subject to input saturation via disturbance observer ☆Y Wei，WX Zheng，S Xu《Systems & ControlLetters》, 2015, 85:61-693.Exact tracking control of nonlinear systems with time delays and dead-zone inputZ Zhang，S Xu，B Zhang《Automatica》, 2015, 52(52):272-276EI1.Further studies on stability and stabilization conditions for discrete-time T–S systems with the order relation information of membership functionsJ Chen，S Xu，Y Li，Y Chu，Y Zou《Journal of the Franklin Institute》, 2015, 352(12):5796-5809 .2 .Stability analysis of random systems with Markovian switching and its application T Jiao，J Lu，Y Li，Y Chu，SXu《Journal of the Franklin Institute》, 2015, 353(1):200-220 3.Exact tracking control of nonlinear systems with time delays and dead-zone inputZ Zhang，S Xu，B Zhang《Automatica》, 2015, 52(52):272-2764.Event-triggered average consensus for multi-agent systems with nonlinear dynamics and switching topologyD Xie，S Xu，Y Chu，Y Zou《Journal of the Franklin Institute》, 2015, 352(3):1080-1098葛树志简介：葛树志，男，汉族，1963年9⽉20⽇⽣于⼭东省安丘县景芝的葛家彭旺村。
收稿日期:2008-05-31作者简介:敖 锋(1980-),男,四川泸州人,国防科技大学人文与社科学院外语系讲师,博士,研究方向为心理语言学及自然语言处理;胡卫星(1975-),女,湖南益阳人,国防科技大学人文与社科学院外语系副教授,博士研究生,研究方向为心理语言学及二语习得。
双语词汇识别中的联结主义模型敖 锋,胡卫星(国防科技大学人文与社科学院,湖南长沙410073)摘 要:本文探讨了计算模型在双语词汇识别研究中的作用并介绍了两种得到应用的联结主义模型:局域式网络模型和分布式网络模型。
这两种模型在结构和功能上既有相同之处,又存在差异。
尽管这两种模型对双语研究的理论发展有积极作用,但目前研究者们仍倾向于利用不同的模型来研究不同的语言现象,因此该领域还存在很大的研究空间尚待开发。
关键词:双语词汇识别;联结主义;计算模型中图分类号:H 087 文献标识码:A 文章编号:10022722X (2010)04200122050.引言从上世纪80年代开始,联结主义(Connecti o n 2is m)¹(即人工神经网络)模型被广泛用于研究母语的理解与产出,其机制在于模拟成年人的语言系统以及该系统的发展过程。
在双语词汇识别领域也有一部分研究采用了联结主义模型的方法。
本文主要介绍其中的两种模型,即局域式网络模型和分布式网络模型。
1.双语词汇识别中的计算模型计算模型在双语词汇识别研究中具有一定优势。
首先,建立计算模型必须使理论本身足够清晰以满足计算机应用的需要;其次,当某种理论的预测结果很难确定时(比如理论中各因素之间的相互影响非常复杂时),计算模型通过训练后能够生成可检验的结果,将模型的计算结果和实验数据进行对比即可分析理论的解释力水平;最后,计算模型可以模拟一些语言研究中的特殊情况,比如脑损伤造成的语言缺失,而这很难通过实验的方法来研究。
但是,在双语词汇识别研究中应用计算模型仍有一些值得考虑的问题。
第39卷第5期自动化学报Vol.39,No.5 2013年5月ACTA AUTOMATICA SINICA May,2013分散式MPC经济性能评估刘苏1冯毅萍1荣冈1摘要近年来,学术界对集中式模型预测控制(Model predictive control,MPC)性能评估进行了广泛的研究.对于大规模化工过程,工业现场通常采用分散式MPC的控制结构.由于各子系统间存在复杂的耦合关系,针对集中式MPC的性能评估方法不能客观反映分散式MPC的性能.本文基于线性矩阵不等式(Linear matrix inequality,LMI)的方法对分散式MPC进行经济性能评估.首先提出了一种迭代方法求解分散式线性二次型调节器(Linear quadratic regulator,LQR)问题,该方法显著降低了已有求解方法的保守性.再利用LQR基准建立了一组随机优化命题对MPC进行经济性能评估,评估方法对集中式MPC与分散式MPC均适用,评估结果可以指导MPC参数调整,也可以为集中式与分散式MPC结构选择提供重要参考.通过对重油分馏塔控制问题的仿真验证了本文方法的有效性与应用价值.关键词模型预测控制,经济性能评估,分散式控制,线性二次型调节器,线性矩阵不等式引用格式刘苏,冯毅萍,荣冈.分散式MPC经济性能评估.自动化学报,2013,39(5):548−555DOI10.3724/SP.J.1004.2013.00548Economic Performance Assessment of Decentralized Model Predictive ControlLIU Su1FENG Yi-Ping1RONG Gang1Abstract In recent years,performance assessment of centralized model predictive control(MPC)has attracted a lot of academic interest.In fact,large-scale complex chemical processes are usually controlled by decentralized MPC in the industrialfield.Due to the complex interactions between subsystems,most performance assessment methods regarding centralized control structure cannot be applied to the performance assessment of decentralized MPC.In this paper,a linear matrix inequality(LMI)based approach is proposed to assess the economic performance of decentralized MPC. First,an iterative method is proposed to obtain the decentralized linear quadratic regulator(LQR)benchmark.A probabilistic optimization problem is then formulated to assess the economic performance of MPC.The proposed approach can be applied to assessment of both centralized MPC and decentralized MPC.The assessment result provides guidance for parameter tuning as well as control structure selection.The simulation result of Shell control problem shows the effectiveness of the proposed method.Key words Model predictive control(MPC),economic performance assessment,decentralized control,linear quadratic regulator(LQR),linear matrix inequality(LMI)Citation Liu Su,Feng Yi-Ping,Rong Gang.Economic performance assessment of decentralized model predictive control.Acta Automatica Sinica,2013,39(5):548−555模型预测控制(Model predictive control, MPC)因其处理多变量、约束等能力,得到了广泛的工业应用.典型的化工过程通常是由一系列相互作用的子系统组成,各子系统之间存在着复杂的物料流、能量流以及信息流.针对复杂的大规模工收稿日期2012-05-13录用日期2012-10-08Manuscript received May13,2012;accepted October8,2012国家基础研究发展计划(973计划)(2012CB720500),国家高技术研究发展计划(863计划)(2012BAE05B03)资助Supported by National Basic Research Program of China(973 Program)(2012CB720500)and National High Technology Re-search and Development Program of China(863Program)(2012 BAE05B03)本文客座编委王宏Recommended by Guest Editor WANG Hong1.浙江大学工业控制技术国家重点实验室智能系统与控制研究所杭州3100271.State Key Laboratory of Industrial Control Technology, Institute of Cyber-System and Control,Zhejiang University, Hangzhou310027业过程,虽然集中式控制结构能够提供最优性能指标,但是由于计算机能力和通讯能力的限制,难以应用.因此,在工业实际中通常采用分散式控制结构,即忽略装置间的相互作用,对每个子系统单独设计MPC控制器.但是,当各子系统之间的相互作用较强时,分散式MPC的控制性能会大打折扣,甚至导致系统不稳定[1].为了结合集中式与分散式MPC 的优势,近年来学术界对分布式MPC进行了广泛的研究,提出了多种分布式MPC策略[2].其中文献[3]提出的分布式协同方案在收敛时可以达到与集中式控制方案相同的控制效果.但分布式MPC增加了控制系统的复杂度与成本,对通信存在较高要求,目前工业应用较少.为选择合理的控制器结构,就需要对集中式MPC与分散式MPC进行性能评估.自从Harris的早期论文[4]之后,学术界对控制器性5期刘苏等:分散式MPC经济性能评估549能评估进行了广泛而深入的研究,许多评估方法被应用到集中式MPC的性能评估[5].例如最小方差控制(Minimum variance control,MVC)基准[6−7]、线性二次型高斯(Linear quadratic Gaussian,LQG)基准[8]、用户自定义基准[9]、模型验证[10]、设计目标与实际对比[11]等.其中,LQG基准被认为具有较高的参考价值,因为LQG基准同时考虑了系统的输入方差和输出方差.由于各子系统之间存在耦合关系,以上针对集中式MPC的性能评估方法不能直接应用于分散式MPC的性能评估.分散式MPC的性能评估必须考虑到控制器的块对角结构特性.目前学术界对于分散式控制系统的性能评估研究相对较少,主要关注于分散式MVC基准[12−14].由于控制器的块对角结构约束给优化命题带来非凸的特性,此类问题目前还没有一个完善的解决方法,只能通过一些简化假设求得分散式MVC基准的上界或下界.然而,由于只考虑了输出方差,而未考虑输入作用,分散式MVC基准无法客观反映分散式MPC的控制性能.本文的核心工作就是将LQG基准应用于分散式MPC的经济性能评估.主要贡献包括:1)在系统状态已知的情况下,提出了一种基于线性矩阵不等式(Linear matrix inequality,LMI)的迭代方法处理控制器块对角约束,得到了分散式线性二次型调节器(Linear quadratic regulator,LQR)基准.本文的迭代方法显著降低了现有方法的保守性.2)建立了一组随机优化命题,利用集中式与分散式LQR基准分别对MPC进行经济性能评估.评估结果既可以为分散式MPC的参数调整提供参考,也可以表明用集中式MPC代替分散式MPC能取得的潜在经济效益.下文如下展开:第1节介绍系统描述以及本文需要的基础数学工具,第2节介绍如何基于LMI利用迭代的方法求解分散式LQR基准,第3节介绍如何利用集中式与分散式LQR基准进行MPC经济性能评估,第4节通过两个仿真例子分别说明本文提出的分散式LQR基准与经济性能评估方法的价值.1系统描述与数学工具1.1系统描述假设整个化工过程由m个相互关联的线性子系统构成,每个子系统可表示为如下的离散状态空间模型:x i(k+1)=A ii x i(k)+B ii u i(k)+M i w i(k)+m,j=ij=1(A ij x j(k)+B ij u j(k))y i(k)=C i x i(k)+N i w i(k)(1)其中,x i∈R n i,u i∈R l i,y i∈R p i,i=1,···,m,分别代表各子系统的状态、输入和输出变量.A ij,B ij,M i,C i,N i,i=1,···,m,j=1,···,m,是具有相应维数的系统矩阵.w i(k)∈R q i是均值为零、协方差为Ωi的高斯白噪声.m,j=ij=1(A ij x j(k)+B ij u j(k))代表各子系统之间的状态耦合与输入耦合.设整个过程的状态变量为x=[x T1···x Ti···x Tm]T∈R n,输入变量为u=[u T1···u Ti···u Tm]T∈R l,输出变量为y=[y T1···y Ti···y Tm]T∈R p.则集中式的系统可以表示为x(k+1)=Ax(k)+Bu(k)+Mw(k)y(k)=Cx(k)+Nw(k)(2)集中式的系统矩阵A,B,M,C,N由分散式系统矩阵对应组合而成,这里不再赘述.本文假定集中式系统(A,B)为能控对,(A,C)为能观对.式(1)与式(2)所表述的对象是完全等价的,分开列写是为了便于下文描述分散式MPC与集中式MPC.1.2分散式MPC与集中式MPC采用分散式MPC结构时,针对式(1)表示的化工过程,为简化问题形式,本文假设每个子系统对应的MPC为minNt=112y i(t)T Q i y i(t)+u i(t)T R i u i(t)s.t.x i(t+1)=A ii x(t)+B ii u i(t)y i(t)=C i x i(t)u mini≤u i(t)≤u maxi(3)其中,Q i,R i为对称权重矩阵,u mini,u maxi为控制上、下限,N为预测时域和控制时域.从式(3)可以看出,每个子系统在设计MPC时忽略了互相之间的状态耦合与输入耦合.式(3)表达的是一个常规控制问题,设定点追踪问题可以通过简单的坐标变换转化为常规控制问题.采用集中式MPC时,针对式(2)表示的整个过程模型设计的MPC为minNt=112y(t)T Qy(t)+u(t)T Ru(t)s.t.x(t+1)=Ax(t)+Bu(t)y(t)=Cx(t)u min≤u(t)≤u max(4)其中,Q=diag{Q1,Q2,···,Q m},R=diag{R1,R2,···,R m}.550自动化学报39卷1.3LQR基准MPC 性能评估的一类重要的参考基准就是LQG 基准.由于LQG 基准不考虑输入约束,只有当工作点距离输入输出约束边界较远时,LQG 基准才可以客观反映MPC 性能.系统状态可测时,LQG 问题退化为LQR 问题.本文基于LQR 基准对分散式MPC 进行性能评估.以下首先给出求解LQR 基准的数学工具.对于式(2)表达的集中式系统,忽略输入约束,采用状态反馈控制器u (k )=Kx (k ),定义系统的控制目标为J =min E {x T Qx +u T Ru },则性能指标J 与对应的状态反馈增益K 可通过如下的优化命题求解[15]:J =min K,P,Φy ,Φu ,Gtr(Q Φy )+tr(R Φu )s .t .Φy CG N ∗G +G T −P0∗∗Ω−1>0 Φu KG∗G +G T −P>0P AG M∗G +G T −P 0∗∗Ω−1>0(5)其中,Φy ,Φu 分别代表系统输出与输入的协方差,P是n ×n 对称正定矩阵,G 是n ×n 满秩矩阵(G 是一个扩展参数,起到了辅助变量的作用[15]).Ω代表噪声w (k )的协方差,∗表示矩阵的对称部分.式(5)中的优化命题得到的就是集中式系统的LQR 性能基准.只需要通过简单的非线性变换L =KG ,优化命题(5)就可以转化为LMI 问题,目前已经有许多成熟的算法可以求解LMI.利用LQR 基准可以对集中式MPC 的控制性能进行评估.而对分散式MPC 进行控制评估,由于各子系统间存在状态耦合与输入耦合,不能直接利用LQR 基准对每个子系统的MPC 控制器进行评估,应该采用分散式的LQR 基准,即在优化命题(5)中,对状态反馈控制器u (k )=Kx (k ),加入块对角约束K =diag {K 1,K 2,···,K m },K i 表示第i 个子系统的状态反馈增益.第3节中将提出一种迭代的方法处理控制器的块对角约束,得到分散式LQR 基准.2分散式LQR 基准自从LQR 基准问世以来,学术界一直没有停止对分散式LQR 基准的研究,但是目前尚未有一套完善的解决方法.由于问题本身非凸的特性,主要的研究成果都是获得LQR 基准的上界或下界.文献[16]提出一种迭代的方法处理Riccati 方程中的块对角结构,迭代结果会根据不同的初值收敛到不同的局部最优点.文献[17]提出了一种参数空间优化方法处理分散式控制问题,所得结果不依赖于迭代初始值,但通常情况下收敛不到最优值.文献[15]基于LMI 的方法,通过对扩展参数加入块对角约束实现控制器的块对角约束,不需要进行迭代.由于扩展参数释放了一定的自由度,文献[15]的方法进一步减小了文献[17]结果的保守性,但文献[15]的方法仍然是相当保守的.第2节的主要贡献就是提出了一种基于LMI 的迭代方法求解分散式LQR 基准,该方法显著降低了现有方法的保守性.在优化命题(5)中,当K 具有块对角结构K =diag {K 1,K 2,···,K m }时,若令L =KG ,则有: L 1L 2...L m = K 10···00K 2···0............00···K m G 1G 2...G m(6)其中,L i ,G i 分别表示L 和G 的行块.显然,L i 的每一行L i (j )都是G i 各行G i (1),···,G i (n i )的线性组合,即L i (j )∈span {G i (1),···,G i (n i )}.又因为G 是满秩方阵,G 的各行线性不相关,所以只要满足L i (j )∈span {G i (1),···,G i (n i )},就必然存在唯一的块对角矩阵K =LG −1满足式(6).以上分析说明,K 的块对角结构与L i (j )∈span {G i (1),···,G i (n i )}等价.由此本文提出以下的迭代方法求解分散式LQR 基准.算法1.步骤1.设n =1,选择任意一个合适的状态反馈增益K (1).步骤2.计算优化命题:J (n )=min P,Φy ,Φu ,G tr(Q Φy )+tr(R Φu )s .t . Φy CG N ∗G +G T −P 0∗∗Ω−1>0Φu K (n )G ∗G +G T−P >0 PAG M ∗G +G T P0∗∗Ω−1>0(7)5期刘苏等:分散式MPC经济性能评估551再令G(n)=G,G为式(7)优化命题的计算结果.步骤3.计算优化命题:J(n)=minL,P,Φy,Φu,Gtr(QΦy)+tr(RΦu)s.t.Φy CG N∗G+G T−P0∗∗Ω−1>0Φu L∗G+G T−P>0P AG M∗G+G T−P0∗∗Ω−1>0(8)L i(j)∈span{G i(1),···,G i(ni ) }span{G i(1),···,G i(ni )}=span{G(n)i(1),···,G(n)i(n i)},i=1,···,m(9)再令n=n+1,K(n)=LG−1,其中L,G为以上优化命题的计算结果.步骤4.如果|J(n−1)−J(n)|< ( 是给定的很小的正数),停止,J(n)为分散式LQR能取得的性能指标,否则返回步骤2.在上述迭代过程中,步骤2和步骤3中的优化命题都是LMI问题.步骤3中首先根据已知的状态反馈增益K(n)计算出对应的G(n),步骤4再在G(n)的行空间约束下求出对应最优的状态反馈增益K(n+1),如此反复迭代.注意步骤3中优化命题加入的行空间约束L i(j)∈span{G i(1),···,G i(ni )}和span{G i(1),···,G i(ni )}=span{G(n)i(1),···,G(n)i(n i)}为线性约束.由于增加了变量L与G的行空间约束,步骤3中得到的状态反馈增益K必定具有块对角结构.在每一步迭代中,优化命题的目标函数相同,且上一次优化求得的解同时是新的优化命题的可行解,因此每一步迭代目标函数必定下降或不变,所以上述迭代过程必然收敛.第4节中将通过一个简单的例子说明本文提出的迭代方法显著降低了现有方法计算分散式LQR性能基准的保守性.3经济性能评估近年来,一些学者利用LQG基准对MPC进行经济性能评估,采用一组随机优化命题同时确定稳态工作点与输入输出方差.由于LQG基准中输入输出方差关系只能通过调节权重隐式地表达为一组Riccati方程,为了获得输入输出方差的解析关系,文献[18−20]中通过改变LQG问题的输入输出权重“逐点求解”一系列Pareto最优解,再用数值拟合的方法确定输入输出方差关系曲线(Trade-offcurve),这导致了较大的计算成本以及一定的计算精度问题.尤其对于多变量的情况,拟合一个复杂关系曲面的计算代价是十分庞大的.一种较为合理的简化方法[8]是按照重要程度固定输入之间的相对权重与输出之间的相对权重,再通过改变输入输出间的权重确定方差关系曲线.然而由于约束的存在,不同局部输入输出间的实际相对权重可能是不同的,一个全局最优的相对权重是难以确定的.文献[21]给出了一个综合的框架分析约束与波动对MPC经济性能的影响,采用基于线性矩阵不等式(LMI)的方法确定LQG基准,并以“最小能量”基准的形式通过迭代求解MPC经济指标.文献[21]的迭代过程避免了对多变量方差关系的拟合,具有一定的优势,但由于问题本身非凸的特性,文献[21]的迭代方法同样不能保证最优性.并且,文献[21]的评估方法只能指出控制性能的调整方向,但不能计算最大的潜在经济效益.本节采用相同的框架进行MPC 经济性能评估,提出了一种迭代方法求解经济性能评估的随机优化问题,可以从一定程度上克服已有方法的不足,迭代结果可以收敛到局部最优点,但同样不能保证全局最优.以下首先利用LQR基准对集中式MPC进行经济性能评估,在此基础上再利用第2节给出的迭代方法处理控制器的块对角约束,得到分散式MPC的经济性能结果.第4节中将通过对重油分馏塔控制的仿真说明本节方法的有效性.首先考虑集中式MPC的经济性能评估.LP-MPC(Linear programming MPC)[22]的工业应用十分广泛,其稳态优化层求解如下的线性规划问题:J=maxy upi=1a i y i−mj=1b j u js.t.∆y=K∆u,y=y0+∆y,u=u0+∆u L yi≤y i≤H yiL uj≤u j≤H uj(10)其中,y i,i=1,2,···,p和u j,j=1,2,···,m,是需要优化的被控变量与操作变量的稳态工作点,a i 与b j为相应的经济指标参数,K代表稳态增益,y0和u0代表当前的工作点,L yi,H yi,L uj,H uj是对应被控变量与操作变量的边界约束.当过程噪声满足高斯白噪声假设时,稳态操作点y i与u j满足正态分布.性能指标的期望值可以表示为E[J]=a i¯y i−b j¯u j(11)552自动化学报39卷其中,¯y i 与¯u j 分别表示被控变量与操作变量的均值.工作点边界约束可以表示为概率约束:P r {L yi ≤¯y i ≤H yi }>αi P r {L uj ≤¯u j ≤H uj }>βj(12)其中,αi 与βj 为置信度(通常取95%).式(12)表达的含义是¯y i 位于其约束边界(L yi ,H yi )内的概率为αi ,¯u j 位于其约束边界(L uj ,H uj )内的概率为βj .由于y i 与u j 满足正态分布,式(11)可以进一步改写为L yi +F −1(αi ) Φyi ≤¯y i ≤H yi −F −1(αi ) ΦyiL uj +F −1(βj ) Φuj ≤¯u j ≤H uj −F −1(βj ) Φuj(13)其中,F −1表示高斯分布函数的逆函数,Φyi ,Φuj 表示对应各输出与输入的方差,即协方差矩阵Φy 与Φu 的对角线上第i 或第j 个元素.当Φy 与Φu 满足式(5)中的LQR 基准时,可以通过如下的随机优化命题进行MPC 性能评估:E c =max ¯y ,¯u ,Φy ,Φu ,P,G,La i ¯y i −b j ¯u js .t .∆y =K ∆u,y =y 0+∆y,u =u 0+∆uL yi +F −1(αi ) Φyi ≤¯y i ≤H yi −F −1(αi )ΦyiL uj +F −1(βj ) Φuj ≤¯u j ≤H uj −F −1(βj )Φuj Φy CG N ∗G +G T −P 0∗∗Ω−1>0 Φu KG ∗G +G T−P>0 PAG M ∗G +G T −P0∗∗Ω−1>0式(14)中的随机优化命题同时考虑了过程的控制性能与经济性能,求解的结果既可以得到集中式MPC 最优的工作点以及能取得的经济性能(这里定义为E c ),同时可以得到对应的输入与输出方差,为控制参数调节提供参考.但是,由于约束中同时存在方差与标准差,式(14)中的优化命题不是LMI 问题,事实上,式(14)是一个非凸的优化命题.要完善地求解优化命题(14)具有较大的难度,本文提出如下的迭代方法得到式(14)的局部最优解.算法2.步骤1.确定初始可行的输出输入方差Φ(0)y ,Φ(0)u ,可以用当前工况计算.置n =0.步骤2.计算优化命题:E c =max ¯y ,¯u ,Φy ,Φu ,P,G,La i ¯y i −b j ¯u js .t .∆y =K ∆u,y =y 0+∆y,u =u 0+∆uL yi +F −1(αi )ΦyiΦ(n )yi ≤¯y i ≤H yi −F −1(αi )Φyi Φ(n )yi L uj +F −1(βj )Φuj Φ(n )uj ≤¯u j ≤H uj −F −1(βj )ΦujΦ(n )ujΦy CG N ∗G +G T −P0∗∗Ω−1>0 Φu KG∗G +G T −P >0P AG M ∗G +G T −P 0∗∗Ω−1>0步骤3.如果|Φ(n )y −Φ(n −1)y |+|Φ(n )u −Φ(n −1)u|< ( 是给定的很小的正数),停止计算,E (n )c 为最终的评估结果.否则返回步骤2.评估分散式MPC 的经济性能相当于在集中式MPC 的经济性能评估问题(14)中加入控制器的块对角约束,即:L =KGK =diag {K 1,K 2,···,K m }(14)第2节中已经提出了处理控制器的块对角约束的迭代方法,因此,利用算法2对分散式MPC 进行经济性能评估,只需要在每次迭代计算式(15)中的优化命题时利用第2节的迭代算法处理控制器的块对角约束即可.4案例分析例1.分散式LQR 基准.为说明第2节中的迭代方法求解分散式LQR 基准具有较小的保守性,本例采用与文献[15]中相同的数值仿真案例.考虑式(2)表达的系统,其中:A = 0.81890.08630.09000.08130.25241.00330.03130.2004−0.05450.01020.7901−0.2580−0.1918−0.10340.16020.86045期刘苏等:分散式MPC 经济性能评估553B =0.00450.00440.10010.01000.0003−0.0136−0.00510.0936,C =1000010*********M = 0.09530.01450.0862−0.0011 ,N = 0000,Ω=1要求对上述系统设计一个分散式状态反馈控制器,第1个控制输出通过前两个状态反馈,第2个输出通过后两个状态反馈,即u 1u 2 = K 100K 2 x 1x 2x 3x 4T其中,K 1,K 2∈R 1×2.设分散式系统控制的性能指标为J =min E {x T Qx +u T Ru },其中,Q = 10−100000−10100000,R = 1001 应用文献[15]中的方法得到的控制器与对应的性能指标为K d 1=−1.4891−1.66000000−0.1211−0.0137J d 1=0.1580采用第3节提出的迭代方法求解,对应的控制器与性能指标为K d 2=−0.4724−0.30030000−0.3772−0.1852J d 2=0.0744从计算结果可以看出,本文提出的迭代方法明显改善了文献[15]中方法求解分散式LQR 基准的保守性.为进一步说明本文迭代方法的优势,用式(5)计算集中式LQR 性能基准,得到的结果为J c =0.0733.J d 2与J c 相当接近,又考虑到J d 2必然大于J c ,说明本文的迭代方法具有较小的保守性.例2.MPC 经济性能评估.壳牌重油分馏塔的控制问题受到学术界广泛研究[19,21].过程模型和扰动模型分别为T (s )=4.0550s +1e −27s1.7760s +1e −28s5.8850s +1e −27s5.3950s +1e −18s5.7260s +1e −14s6.9040s +1e −15s 4.3833s +1e −20s4.4244s +1e −22s7.219s +1N (s )=1.2045s +1e −27s1.4440s +1e −27s1.5325s +1e −15s1.8320s +1e −15s1.1427s +11.2632s +1其中,被控变量:y 1代表分馏器顶部产品成分,y 2代表分馏器侧线产品成分,y 3代表分馏器底部回流温度.操作变量:u 1代表分馏器顶部产品抽出率,u 2代表分馏器侧线产品抽取率,u 3代表分馏器底部回流热负荷.扰动变量:d 1为塔中部回流热负荷,d 2为塔顶的回流热负荷.设该过程由三个分散式MPC 控制,T (s )对角线上的传递函数.利用Matlab MPC 工具箱设计控制器,取预测时域P =120,控制时域M =5,输入输出约束都为[−1,1],扰动是均值为0,标准差为2的相互独立的高斯白噪声.假设稳态优化的目标函数为E c =min(−¯y 1−¯y 2+¯u 3).利用第3节中的方法分别对集中式MPC,分散式MPC 进行经济性能评估,并根据评估结果分别调整MPC 参数,仿真验证经济性能评估结果.设输入输出概率约束的置信度为95.4%,即F −1(αi )=F −1(βj )=2.对应的评估结果与仿真验证结果见表1.表1当前工况、评估结果与验证结果Table 1Current working condition,assessment results,and verification¯y 1¯y 2¯y 3¯u 1¯u 2¯u 3E c 当前工况0.38680.1547−0.46170.8221−0.2124−0.4170−0.1245集中式MPC 评估0.90800.7884−0.0329 1.0000−0.2511−0.4588−1.2376分散式MPC 评估0.59050.2791−0.5062 1.0000−0.2886−0.5015−0.3681集中式MPC 验证0.74060.4628−0.16610.9041−0.2505−0.3988−0.8046分散式MPC 验证0.48880.2166−0.45900.9115−0.2435−0.4518−0.2536554自动化学报39卷从表1可以看出,评估结果对于参数调整具有积极的指导意义.当前工况是指当前正在运行的分散式MPC的稳态工况,此时被控变量y1与y2的波动范围均已接近约束边界,取得的经济目标为−0.1245.利用第3节中的方法进行经济性能评估,得到分散式MPC能取得的潜在经济目标为−0.3681,根据评估结果调整各子控制器参数后,得到的经济目标为−0.2536.评估集中式MPC能取得的经济目标为−1.2376,通过仿真验证得到的经济目标为−0.8046.以上结果表明本文提出的经济性能评估方法可以从一定程度上表明分散式MPC 与集中式MPC的潜在经济效益.仿真结果明显劣于评估结果,主要原因在于:1)评估方法采用的LQR 基准中状态已知,而本例中状态是未知的;2)评估方法中输入与输出约束是概率约束,而MPC中输入约束为硬约束;3)参数调整不到位.值得注意的是,集中式MPC与分散式MPC的经济性能评估结果之比为3.36,通过仿真验证得到的比值为3.17,这说明本文的经济性能评估方法对控制结构的选择具有较高的参考价值.5结论本文研究了分散式MPC的性能评估.首先提出了一种基于LMI的迭代方法求解分散式LQR基准,本文的迭代方法显著降低了现有方法的保守性.再通过一组随机优化命题将LQR基准引入MPC 稳态优化,对集中式MPC与分散式MPC进行经济性能评估.仿真结果表明本文提出的评估方法对控制器参数调整与结构选择具有重要的参考价值.References1Cui H,Jacobsen E W.Performance limitations in decentral-ized control.Journal of Process Control,2002,12(4):485−4942Scattolini R.Architectures for distributed and hierarchical model predictive control—a review.Journal of Process Control,2009,19(5):723−7313Stewart B T,Venkat A N,Rawlings J B,Wright S J,Pan-nocchia G.Cooperative distributed model predictive con-trol.Systems&Control Letters,2010,59(8):460−4694Harris T J.Assessment of control loop performance.The Canadian Journal of Chemical Engineering,1989,67(5): 856−8615Huang B,Kadali R.Dynamic Modeling,Predictive Control and Performance Monitoring:A Data-driven Subspace Ap-proach.Vol.374.New York:Springer Verlag,20086Gao J P,Patwardhan R,Akamatsu K,Hashimoto Y,Emoto G,Shah S L,Huang B.Performance evaluation of two indus-trial MPC controllers.Control Engineering Practice,2003, 11(12):1371−13877Yang M Y,Jin X M,Chen F.Performance assessment of model predictive control in industrial distillation column.In:Proceedings of the5th World Congress on Intelligent Control and Automation.Hangzhou,China:IEEE,2004.637−6418Huang B,Shah S L.Performance Assessment of Control Loops:Theory and Applications.New York:Springer Ver-lag,19999Shah S L,Patwardhan R,Huang B.Multivariate controller performance analysis:methods,applications and challenges.AIChE Symposium Series,New York,USA,2002.190−207 10Shah S L,Mitchell W,Shook D.Challenges in the detection, diagnosis and visualisation of controller performance data.Computing and Control Engineering Journal,2005,16(4): 30−3411Patwardhan R S,Shah S L,Qi K Z.Assessing the perfor-mance of model predictive controllers.The Canadian Jour-nal of Chemical Engineering,2002,80(5):954−96612Jain M,Lakshminarayanan S.Estimating performance enhancement with alternate control strategies for multi-loop control systems.Chemical Engineering Science,2007, 62(17):4644−465813Kariwala V,Forbes J F,Meadows E S.Minimum variance benchmark for decentralized controllers.In:Proceedings of the2005American Control Conference.Portland,OR,USA: IEEE,2005.1437−144214Kariwala V.Fundamental limitation on achievable decen-tralized performance.Automatica,2007,43(10):1849−185415De Oliveira M C,Geromel J C,Bernussou J.Extended H2 and H∞norm characterizations and controller parametriza-tions for discrete-time systems.International Journal of Control,2002,75(9):666−67916Geromel J C,Peres P L D.Decentralized load-frequency control.IEE Proceedings D(Control Theory and Applica-tions),1985,132(5):225−23017Geromel J C,Bernussou J,Peres P L D.Decentralized control through parameter space optimization.Automatica, 1994,30(10):1565−157818Zhao C,Zhao Y,Su H Y,Huang B.Economic performance assessment of advanced process control with LQG bench-marking.Journal of Process Control,2009,19(4):557−5695期刘苏等:分散式MPC经济性能评估55519Zhao C,Su H Y,Gu Y,Chu J.A pragmatic approach for assessing the economic performance of model predictive con-trol systems and its industrial application.Chinese Journal of Chemical Engineering,2009,17(2):241−25020Xu Q L,Zhao C,Zhang D F,An A M,Zhang C.Data-driven LQG benchmarking for economic performance assess-ment of advanced process control system.In:Proceedings of the2011American Control Conference.San Francisco,CA, USA:AACC,2011.5085−509021Xu F W,Huang B,Akande S.Performance assessment of model predictive control for variability and constraint tun-ing.Industrial and Engineering Chemistry Research,2007, 46(4):1208−121922Ying,C M,Joseph B.Performance and stability analysis of LP-MPC and QP-MPC cascade control systems.AIChE Journal,1999,45(7):1521−1534刘苏浙江大学智能系统与控制研究所硕士研究生.2010年获北京理工大学化工与环境学院学士学位.主要研究方向为MPC性能评估.E-mail:*************.cn(LIU Su Master student at the Insti-tute of Cyber-System and Control,Zhe-jiang University.He received his bache-lor degree from Beijing Institute of Technology in2010.His main research interest is performance assessment of model predictive control.)冯毅萍浙江大学智能系统与控制研究所高级工程师.2008年获浙江大学控制系工学博士学位.主要研究方向为复杂工业系统建模及优化,智能工厂仿真技术.E-mail:***************(FENG Yi-Ping Senior engineer atthe Institute of Cyber-System and Con-trol,Zhejiang University.She received her Ph.D.degree from Zhejiang University in2008.Her research interest covers complex system modeling and op-timization,and smart plant simulation technology.)荣冈浙江大学智能系统与控制研究所教授.1989年获浙江大学工业自动化专业博士学位.主要研究方向为智慧供应链和智能工厂整体解决方案,流程工业生产执行系统,数据校正与数据挖掘,复杂工业过程的虚拟现实与信息可视化,先进控制理论及其应用.本文通信作者.E-mail:************** (RONG Gang Professor at the Institute of Cyber-System and Control,Zhejiang University.He received his Ph.D.degree from Zhejiang University in1989.His re-search interest covers intelligent supply chain and the total solution of smart plant,manufacturing execution systems, data reconciliation and data mining,virtual reality and in-formation visualization of complex industrial process,and advanced control theory and application.Corresponding author of this paper.)。
Consensus and Cooperation in Networked Multi-Agent SystemsAlgorithms that provide rapid agreement and teamwork between all participants allow effective task performance by self-organizing networked systems.By Reza Olfati-Saber,Member IEEE,J.Alex Fax,and Richard M.Murray,Fellow IEEEABSTRACT|This paper provides a theoretical framework for analysis of consensus algorithms for multi-agent networked systems with an emphasis on the role of directed information flow,robustness to changes in network topology due to link/node failures,time-delays,and performance guarantees. An overview of basic concepts of information consensus in networks and methods of convergence and performance analysis for the algorithms are provided.Our analysis frame-work is based on tools from matrix theory,algebraic graph theory,and control theory.We discuss the connections between consensus problems in networked dynamic systems and diverse applications including synchronization of coupled oscillators,flocking,formation control,fast consensus in small-world networks,Markov processes and gossip-based algo-rithms,load balancing in networks,rendezvous in space, distributed sensor fusion in sensor networks,and belief propagation.We establish direct connections between spectral and structural properties of complex networks and the speed of information diffusion of consensus algorithms.A brief introduction is provided on networked systems with nonlocal information flow that are considerably faster than distributed systems with lattice-type nearest neighbor interactions.Simu-lation results are presented that demonstrate the role of small-world effects on the speed of consensus algorithms and cooperative control of multivehicle formations.KEYWORDS|Consensus algorithms;cooperative control; flocking;graph Laplacians;information fusion;multi-agent systems;networked control systems;synchronization of cou-pled oscillators I.INTRODUCTIONConsensus problems have a long history in computer science and form the foundation of the field of distributed computing[1].Formal study of consensus problems in groups of experts originated in management science and statistics in1960s(see DeGroot[2]and references therein). The ideas of statistical consensus theory by DeGroot re-appeared two decades later in aggregation of information with uncertainty obtained from multiple sensors1[3]and medical experts[4].Distributed computation over networks has a tradition in systems and control theory starting with the pioneering work of Borkar and Varaiya[5]and Tsitsiklis[6]and Tsitsiklis,Bertsekas,and Athans[7]on asynchronous asymptotic agreement problem for distributed decision-making systems and parallel computing[8].In networks of agents(or dynamic systems),B con-sensus[means to reach an agreement regarding a certain quantity of interest that depends on the state of all agents.A B consensus algorithm[(or protocol)is an interaction rule that specifies the information exchange between an agent and all of its neighbors on the network.2 The theoretical framework for posing and solving consensus problems for networked dynamic systems was introduced by Olfati-Saber and Murray in[9]and[10] building on the earlier work of Fax and Murray[11],[12]. The study of the alignment problem involving reaching an agreement V without computing any objective functions V appeared in the work of Jadbabaie et al.[13].Further theoretical extensions of this work were presented in[14] and[15]with a look toward treatment of directed infor-mation flow in networks as shown in Fig.1(a).Manuscript received August8,2005;revised September7,2006.This work was supported in part by the Army Research Office(ARO)under Grant W911NF-04-1-0316. R.Olfati-Saber is with Dartmouth College,Thayer School of Engineering,Hanover,NH03755USA(e-mail:olfati@).J.A.Fax is with Northrop Grumman Corp.,Woodland Hills,CA91367USA(e-mail:alex.fax@).R.M.Murray is with the California Institute of Technology,Control and Dynamical Systems,Pasadena,CA91125USA(e-mail:murray@).Digital Object Identifier:10.1109/JPROC.2006.8872931This is known as sensor fusion and is an important application of modern consensus algorithms that will be discussed later.2The term B nearest neighbors[is more commonly used in physics than B neighbors[when applied to particle/spin interactions over a lattice (e.g.,Ising model).Vol.95,No.1,January2007|Proceedings of the IEEE2150018-9219/$25.00Ó2007IEEEThe common motivation behind the work in [5],[6],and [10]is the rich history of consensus protocols in com-puter science [1],whereas Jadbabaie et al.[13]attempted to provide a formal analysis of emergence of alignment in the simplified model of flocking by Vicsek et al.[16].The setup in [10]was originally created with the vision of de-signing agent-based amorphous computers [17],[18]for collaborative information processing in ter,[10]was used in development of flocking algorithms with guaranteed convergence and the capability to deal with obstacles and adversarial agents [19].Graph Laplacians and their spectral properties [20]–[23]are important graph-related matrices that play a crucial role in convergence analysis of consensus and alignment algo-rithms.Graph Laplacians are an important point of focus of this paper.It is worth mentioning that the second smallest eigenvalue of graph Laplacians called algebraic connectivity quantifies the speed of convergence of consensus algo-rithms.The notion of algebraic connectivity of graphs has appeared in a variety of other areas including low-density parity-check codes (LDPC)in information theory and com-munications [24],Ramanujan graphs [25]in number theory and quantum chaos,and combinatorial optimization prob-lems such as the max-cut problem [21].More recently,there has been a tremendous surge of interest V among researchers from various disciplines of engineering and science V in problems related to multia-gent networked systems with close ties to consensus prob-lems.This includes subjects such as consensus [26]–[32],collective behavior of flocks and swarms [19],[33]–[37],sensor fusion [38]–[40],random networks [41],[42],syn-chronization of coupled oscillators [42]–[46],algebraic connectivity 3of complex networks [47]–[49],asynchro-nous distributed algorithms [30],[50],formation control for multirobot systems [51]–[59],optimization-based co-operative control [60]–[63],dynamic graphs [64]–[67],complexity of coordinated tasks [68]–[71],and consensus-based belief propagation in Bayesian networks [72],[73].A detailed discussion of selected applications will be pre-sented shortly.In this paper,we focus on the work described in five key papers V namely,Jadbabaie,Lin,and Morse [13],Olfati-Saber and Murray [10],Fax and Murray [12],Moreau [14],and Ren and Beard [15]V that have been instrumental in paving the way for more recent advances in study of self-organizing networked systems ,or swarms .These networked systems are comprised of locally interacting mobile/static agents equipped with dedicated sensing,computing,and communication devices.As a result,we now have a better understanding of complex phenomena such as flocking [19],or design of novel information fusion algorithms for sensor networks that are robust to node and link failures [38],[72]–[76].Gossip-based algorithms such as the push-sum protocol [77]are important alternatives in computer science to Laplacian-based consensus algorithms in this paper.Markov processes establish an interesting connection between the information propagation speed in these two categories of algorithms proposed by computer scientists and control theorists [78].The contribution of this paper is to present a cohesive overview of the key results on theory and applications of consensus problems in networked systems in a unified framework.This includes basic notions in information consensus and control theoretic methods for convergence and performance analysis of consensus protocols that heavily rely on matrix theory and spectral graph theory.A byproduct of this framework is to demonstrate that seem-ingly different consensus algorithms in the literature [10],[12]–[15]are closely related.Applications of consensus problems in areas of interest to researchers in computer science,physics,biology,mathematics,robotics,and con-trol theory are discussed in this introduction.A.Consensus in NetworksThe interaction topology of a network of agents is rep-resented using a directed graph G ¼ðV ;E Þwith the set of nodes V ¼f 1;2;...;n g and edges E V ÂV .TheFig.1.Two equivalent forms of consensus algorithms:(a)a networkof integrator agents in which agent i receives the state x j of its neighbor,agent j ,if there is a link ði ;j Þconnecting the two nodes;and (b)the block diagram for a network of interconnecteddynamic systems all with identical transfer functions P ðs Þ¼1=s .The collective networked system has a diagonal transfer function and is a multiple-input multiple-output (MIMO)linear system.3To be defined in Section II-A.Olfati-Saber et al.:Consensus and Cooperation in Networked Multi-Agent Systems216Proceedings of the IEEE |Vol.95,No.1,January 2007neighbors of agent i are denoted by N i ¼f j 2V :ði ;j Þ2E g .According to [10],a simple consensus algorithm to reach an agreement regarding the state of n integrator agents with dynamics _x i ¼u i can be expressed as an n th-order linear system on a graph_x i ðt Þ¼X j 2N ix j ðt ÞÀx i ðt ÞÀÁþb i ðt Þ;x i ð0Þ¼z i2R ;b i ðt Þ¼0:(1)The collective dynamics of the group of agents following protocol (1)can be written as_x ¼ÀLx(2)where L ¼½l ij is the graph Laplacian of the network and itselements are defined as follows:l ij ¼À1;j 2N i j N i j ;j ¼i :&(3)Here,j N i j denotes the number of neighbors of node i (or out-degree of node i ).Fig.1shows two equivalent forms of the consensus algorithm in (1)and (2)for agents with a scalar state.The role of the input bias b in Fig.1(b)is defined later.According to the definition of graph Laplacian in (3),all row-sums of L are zero because of P j l ij ¼0.Therefore,L always has a zero eigenvalue 1¼0.This zero eigenvalues corresponds to the eigenvector 1¼ð1;...;1ÞT because 1belongs to the null-space of L ðL 1¼0Þ.In other words,an equilibrium of system (2)is a state in the form x üð ;...; ÞT ¼ 1where all nodes agree.Based on ana-lytical tools from algebraic graph theory [23],we later show that x Ãis a unique equilibrium of (2)(up to a constant multiplicative factor)for connected graphs.One can show that for a connected network,the equilibrium x üð ;...; ÞT is globally exponentially stable.Moreover,the consensus value is ¼1=n P i z i that is equal to the average of the initial values.This im-plies that irrespective of the initial value of the state of each agent,all agents reach an asymptotic consensus regarding the value of the function f ðz Þ¼1=n P i z i .While the calculation of f ðz Þis simple for small net-works,its implications for very large networks is more interesting.For example,if a network has n ¼106nodes and each node can only talk to log 10ðn Þ¼6neighbors,finding the average value of the initial conditions of the nodes is more complicated.The role of protocol (1)is to provide a systematic consensus mechanism in such a largenetwork to compute the average.There are a variety of functions that can be computed in a similar fashion using synchronous or asynchronous distributed algorithms (see [10],[28],[30],[73],and [76]).B.The f -Consensus Problem and Meaning of CooperationTo understand the role of cooperation in performing coordinated tasks,we need to distinguish between un-constrained and constrained consensus problems.An unconstrained consensus problem is simply the alignment problem in which it suffices that the state of all agents asymptotically be the same.In contrast,in distributed computation of a function f ðz Þ,the state of all agents has to asymptotically become equal to f ðz Þ,meaning that the consensus problem is constrained.We refer to this con-strained consensus problem as the f -consensus problem .Solving the f -consensus problem is a cooperative task and requires willing participation of all the agents.To demonstrate this fact,suppose a single agent decides not to cooperate with the rest of the agents and keep its state unchanged.Then,the overall task cannot be performed despite the fact that the rest of the agents reach an agree-ment.Furthermore,there could be scenarios in which multiple agents that form a coalition do not cooperate with the rest and removal of this coalition of agents and their links might render the network disconnected.In a dis-connected network,it is impossible for all nodes to reach an agreement (unless all nodes initially agree which is a trivial case).From the above discussion,cooperation can be infor-mally interpreted as B giving consent to providing one’s state and following a common protocol that serves the group objective.[One might think that solving the alignment problem is not a cooperative task.The justification is that if a single agent (called a leader)leaves its value unchanged,all others will asymptotically agree with the leader according to the consensus protocol and an alignment is reached.However,if there are multiple leaders where two of whom are in disagreement,then no consensus can be asymptot-ically reached.Therefore,alignment is in general a coop-erative task as well.Formal analysis of the behavior of systems that involve more than one type of agent is more complicated,partic-ularly,in presence of adversarial agents in noncooperative games [79],[80].The focus of this paper is on cooperative multi-agent systems.C.Iterative Consensus and Markov ChainsIn Section II,we show how an iterative consensus algorithm that corresponds to the discrete-time version of system (1)is a Markov chainðk þ1Þ¼ ðk ÞP(4)Olfati-Saber et al.:Consensus and Cooperation in Networked Multi-Agent SystemsVol.95,No.1,January 2007|Proceedings of the IEEE217with P ¼I À L and a small 90.Here,the i th element of the row vector ðk Þdenotes the probability of being in state i at iteration k .It turns out that for any arbitrary graph G with Laplacian L and a sufficiently small ,the matrix P satisfies the property Pj p ij ¼1with p ij !0;8i ;j .Hence,P is a valid transition probability matrix for the Markov chain in (4).The reason matrix theory [81]is so widely used in analysis of consensus algorithms [10],[12]–[15],[64]is primarily due to the structure of P in (4)and its connection to graphs.4There are interesting connections between this Markov chain and the speed of information diffusion in gossip-based averaging algorithms [77],[78].One of the early applications of consensus problems was dynamic load balancing [82]for parallel processors with the same structure as system (4).To this date,load balancing in networks proves to be an active area of research in computer science.D.ApplicationsMany seemingly different problems that involve inter-connection of dynamic systems in various areas of science and engineering happen to be closely related to consensus problems for multi-agent systems.In this section,we pro-vide an account of the existing connections.1)Synchronization of Coupled Oscillators:The problem of synchronization of coupled oscillators has attracted numer-ous scientists from diverse fields including physics,biology,neuroscience,and mathematics [83]–[86].This is partly due to the emergence of synchronous oscillations in coupled neural oscillators.Let us consider the generalized Kuramoto model of coupled oscillators on a graph with dynamics_i ¼ Xj 2N isin ð j À i Þþ!i (5)where i and !i are the phase and frequency of the i thoscillator.This model is the natural nonlinear extension of the consensus algorithm in (1)and its linearization around the aligned state 1¼...¼ n is identical to system (2)plus a nonzero input bias b i ¼ð!i À"!Þ= with "!¼1=n P i !i after a change of variables x i ¼ð i À"!t Þ= .In [43],Sepulchre et al.show that if is sufficiently large,then for a network with all-to-all links,synchroni-zation to the aligned state is globally achieved for all ini-tial states.Recently,synchronization of networked oscillators under variable time-delays was studied in [45].We believe that the use of convergence analysis methods that utilize the spectral properties of graph Laplacians willshed light on performance and convergence analysis of self-synchrony in oscillator networks [42].2)Flocking Theory:Flocks of mobile agents equipped with sensing and communication devices can serve as mobile sensor networks for massive distributed sensing in an environment [87].A theoretical framework for design and analysis of flocking algorithms for mobile agents with obstacle-avoidance capabilities is developed by Olfati-Saber [19].The role of consensus algorithms in particle-based flocking is for an agent to achieve velocity matching with respect to its neighbors.In [19],it is demonstrated that flocks are networks of dynamic systems with a dynamic topology.This topology is a proximity graph that depends on the state of all agents and is determined locally for each agent,i.e.,the topology of flocks is a state-dependent graph.The notion of state-dependent graphs was introduced by Mesbahi [64]in a context that is independent of flocking.3)Fast Consensus in Small-Worlds:In recent years,network design problems for achieving faster consensus algorithms has attracted considerable attention from a number of researchers.In Xiao and Boyd [88],design of the weights of a network is considered and solved using semi-definite convex programming.This leads to a slight increase in algebraic connectivity of a network that is a measure of speed of convergence of consensus algorithms.An alternative approach is to keep the weights fixed and design the topology of the network to achieve a relatively high algebraic connectivity.A randomized algorithm for network design is proposed by Olfati-Saber [47]based on random rewiring idea of Watts and Strogatz [89]that led to creation of their celebrated small-world model .The random rewiring of existing links of a network gives rise to considerably faster consensus algorithms.This is due to multiple orders of magnitude increase in algebraic connectivity of the network in comparison to a lattice-type nearest-neighbort graph.4)Rendezvous in Space:Another common form of consensus problems is rendezvous in space [90],[91].This is equivalent to reaching a consensus in position by a num-ber of agents with an interaction topology that is position induced (i.e.,a proximity graph).We refer the reader to [92]and references therein for a detailed discussion.This type of rendezvous is an unconstrained consensus problem that becomes challenging under variations in the network topology.Flocking is somewhat more challenging than rendezvous in space because it requires both interagent and agent-to-obstacle collision avoidance.5)Distributed Sensor Fusion in Sensor Networks:The most recent application of consensus problems is distrib-uted sensor fusion in sensor networks.This is done by posing various distributed averaging problems require to4In honor of the pioneering contributions of Oscar Perron (1907)to the theory of nonnegative matrices,were refer to P as the Perron Matrix of graph G (See Section II-C for details).Olfati-Saber et al.:Consensus and Cooperation in Networked Multi-Agent Systems218Proceedings of the IEEE |Vol.95,No.1,January 2007implement a Kalman filter [38],[39],approximate Kalman filter [74],or linear least-squares estimator [75]as average-consensus problems .Novel low-pass and high-pass consensus filters are also developed that dynamically calculate the average of their inputs in sensor networks [39],[93].6)Distributed Formation Control:Multivehicle systems are an important category of networked systems due to their commercial and military applications.There are two broad approaches to distributed formation control:i)rep-resentation of formations as rigid structures [53],[94]and the use of gradient-based controls obtained from their structural potentials [52]and ii)representation of form-ations using the vectors of relative positions of neighboring vehicles and the use of consensus-based controllers with input bias.We discuss the later approach here.A theoretical framework for design and analysis of distributed controllers for multivehicle formations of type ii)was developed by Fax and Murray [12].Moving in formation is a cooperative task and requires consent and collaboration of every agent in the formation.In [12],graph Laplacians and matrix theory were extensively used which makes one wonder whether relative-position-based formation control is a consensus problem.The answer is yes.To see this,consider a network of self-interested agents whose individual desire is to minimize their local cost U i ðx Þ¼Pj 2N i k x j Àx i Àr ij k 2via a distributed algorithm (x i is the position of vehicle i with dynamics _x i ¼u i and r ij is a desired intervehicle relative-position vector).Instead,if the agents use gradient-descent algorithm on the collective cost P n i ¼1U i ðx Þusing the following protocol:_x i ¼Xj 2N iðx j Àx i Àr ij Þ¼Xj 2N iðx j Àx i Þþb i (6)with input bias b i ¼Pj 2N i r ji [see Fig.1(b)],the objective of every agent will be achieved.This is the same as the consensus algorithm in (1)up to the nonzero bias terms b i .This nonzero bias plays no role in stability analysis of sys-tem (6).Thus,distributed formation control for integrator agents is a consensus problem.The main contribution of the work by Fax and Murray is to extend this scenario to the case where all agents are multiinput multioutput linear systems _x i ¼Ax i þBu i .Stability analysis of relative-position-based formation control for multivehicle systems is extensively covered in Section IV.E.OutlineThe outline of the paper is as follows.Basic concepts and theoretical results in information consensus are presented in Section II.Convergence and performance analysis of consensus on networks with switching topology are given in Section III.A theoretical framework for cooperative control of formations of networked multi-vehicle systems is provided in Section IV.Some simulationresults related to consensus in complex networks including small-worlds are presented in Section V.Finally,some concluding remarks are stated in Section VI.RMATION CONSENSUSConsider a network of decision-making agents with dynamics _x i ¼u i interested in reaching a consensus via local communication with their neighbors on a graph G ¼ðV ;E Þ.By reaching a consensus,we mean asymptot-ically converging to a one-dimensional agreement space characterized by the following equation:x 1¼x 2¼...¼x n :This agreement space can be expressed as x ¼ 1where 1¼ð1;...;1ÞT and 2R is the collective decision of the group of agents.Let A ¼½a ij be the adjacency matrix of graph G .The set of neighbors of a agent i is N i and defined byN i ¼f j 2V :a ij ¼0g ;V ¼f 1;...;n g :Agent i communicates with agent j if j is a neighbor of i (or a ij ¼0).The set of all nodes and their neighbors defines the edge set of the graph as E ¼fði ;j Þ2V ÂV :a ij ¼0g .A dynamic graph G ðt Þ¼ðV ;E ðt ÞÞis a graph in which the set of edges E ðt Þand the adjacency matrix A ðt Þare time-varying.Clearly,the set of neighbors N i ðt Þof every agent in a dynamic graph is a time-varying set as well.Dynamic graphs are useful for describing the network topology of mobile sensor networks and flocks [19].It is shown in [10]that the linear system_x i ðt Þ¼Xj 2N ia ij x j ðt ÞÀx i ðt ÞÀÁ(7)is a distributed consensus algorithm ,i.e.,guarantees con-vergence to a collective decision via local interagent interactions.Assuming that the graph is undirected (a ij ¼a ji for all i ;j ),it follows that the sum of the state of all nodes is an invariant quantity,or P i _xi ¼0.In particular,applying this condition twice at times t ¼0and t ¼1gives the following result¼1n Xix i ð0Þ:In other words,if a consensus is asymptotically reached,then necessarily the collective decision is equal to theOlfati-Saber et al.:Consensus and Cooperation in Networked Multi-Agent SystemsVol.95,No.1,January 2007|Proceedings of the IEEE219average of the initial state of all nodes.A consensus algo-rithm with this specific invariance property is called an average-consensus algorithm [9]and has broad applications in distributed computing on networks (e.g.,sensor fusion in sensor networks).The dynamics of system (7)can be expressed in a compact form as_x ¼ÀLx(8)where L is known as the graph Laplacian of G .The graph Laplacian is defined asL ¼D ÀA(9)where D ¼diag ðd 1;...;d n Þis the degree matrix of G with elements d i ¼Pj ¼i a ij and zero off-diagonal elements.By definition,L has a right eigenvector of 1associated with the zero eigenvalue 5because of the identity L 1¼0.For the case of undirected graphs,graph Laplacian satisfies the following sum-of-squares (SOS)property:x T Lx ¼12Xði ;j Þ2Ea ij ðx j Àx i Þ2:(10)By defining a quadratic disagreement function as’ðx Þ¼12x T Lx(11)it becomes apparent that algorithm (7)is the same as_x ¼Àr ’ðx Þor the gradient-descent algorithm.This algorithm globallyasymptotically converges to the agreement space provided that two conditions hold:1)L is a positive semidefinite matrix;2)the only equilibrium of (7)is 1for some .Both of these conditions hold for a connected graph and follow from the SOS property of graph Laplacian in (10).Therefore,an average-consensus is asymptotically reached for all initial states.This fact is summarized in the following lemma.Lemma 1:Let G be a connected undirected graph.Then,the algorithm in (7)asymptotically solves an average-consensus problem for all initial states.A.Algebraic Connectivity and Spectral Propertiesof GraphsSpectral properties of Laplacian matrix are instrumen-tal in analysis of convergence of the class of linear consensus algorithms in (7).According to Gershgorin theorem [81],all eigenvalues of L in the complex plane are located in a closed disk centered at Áþ0j with a radius of Á¼max i d i ,i.e.,the maximum degree of a graph.For undirected graphs,L is a symmetric matrix with real eigenvalues and,therefore,the set of eigenvalues of L can be ordered sequentially in an ascending order as0¼ 1 2 ÁÁÁ n 2Á:(12)The zero eigenvalue is known as the trivial eigenvalue of L .For a connected graph G , 290(i.e.,the zero eigenvalue is isolated).The second smallest eigenvalue of Laplacian 2is called algebraic connectivity of a graph [20].Algebraic connectivity of the network topology is a measure of performance/speed of consensus algorithms [10].Example 1:Fig.2shows two examples of networks of integrator agents with different topologies.Both graphs are undirected and have 0–1weights.Every node of the graph in Fig.2(a)is connected to its 4nearest neighbors on a ring.The other graph is a proximity graph of points that are distributed uniformly at random in a square.Every node is connected to all of its spatial neighbors within a closed ball of radius r 90.Here are the important degree information and Laplacian eigenvalues of these graphsa Þ 1¼0; 2¼0:48; n ¼6:24;Á¼4b Þ 1¼0; 2¼0:25; n ¼9:37;Á¼8:(13)In both cases, i G 2Áfor all i .B.Convergence Analysis for Directed Networks The convergence analysis of the consensus algorithm in (7)is equivalent to proving that the agreement space characterized by x ¼ 1; 2R is an asymptotically stable equilibrium of system (7).The stability properties of system (7)is completely determined by the location of the Laplacian eigenvalues of the network.The eigenvalues of the adjacency matrix are irrelevant to the stability analysis of system (7),unless the network is k -regular (all of its nodes have the same degree k ).The following lemma combines a well-known rank property of graph Laplacians with Gershgorin theorem to provide spectral characterization of Laplacian of a fixed directed network G .Before stating the lemma,we need to define the notion of strong connectivity of graphs.A graph5These properties were discussed earlier in the introduction for graphs with 0–1weights.Olfati-Saber et al.:Consensus and Cooperation in Networked Multi-Agent Systems220Proceedings of the IEEE |Vol.95,No.1,January 2007。
