基于迁移系统分析的线性混成系统安全验证

混成自动机行为中既包含离散行为又包含连续行为,非常复杂。其安全性验证问题难以解决,即使是线性混成自动机,它的可达性问题也被证明是不可判定的。现有工具大都使用多面体计算来计算线性混成自动机的可达状态空间集,复杂度高,可处理问题规模非常有限。为了避免这类问题,实现了一种新的工具。该工具将线性混成自动机表达为等价的迁移系统,并利用迁移系统上不变式生成相关工作对混成自动机进行验证。实验数据表明,方法有效可行,工具具有良好的性能。     

BACH:线性混成系统有界可达性模型检验工具

混成自动机的模型检验问题非常困难,即使是其中相对简单的一个子类--线性混成自动机,它的可达性问题仍然是不可判定的.现有的相关工具大都使用多面体计算来判定线性混成自动机状态空间的可达集,复杂度高、效率低,无法解决实际应用规模的问题.描述了一个面向线性混成系统有界可达性模型检验工具--BACH(bounded reacha...     

LDPChecker一个实时和混成系统模型检验工具

混成系统是一类复杂系统,线性混成系统作为其重要子类,在形式方法中,人们通常使用线性混成自动机来对它建模．虽然线性混成自动机的模型检验问题总的来说还是不可判定的,但对于其中的正环闭合自动机．其对于线性时段性质的满足性能够通过线性规划方法加以检验．为了实现自动检验正环闭合自动机对线性时段性质的满足性,设计并实现了工具LDPChecker．工具LDPChecker能够识别正环闭合自动机并对其进行相应的检验,其主要特色在于它能够对实时和混成系统检验包含可达性在内的许多实时性质,并且能够自动给出诊断信息．     

1种多面体描述的非线性预测控制器综合

针对工业过程中的非线性计算量大,实时性低等问题,提出了1种计算非线性预测控制的新方法。该方法将神经网络与线性微分包含(LDI)相结合对非线性系统建模,从而将非线性系统转换成多面体描述的线性时变系统。对于多面体描述系统的各个顶点构成的多个线性模型,在线求得不同状态下的控制器。最后通过证明多面体描述的线性系统的稳定性来保证原非线性的稳定性。通过仿真看出此算法在处理复杂系统的控制问题具有良好的控制效果。     

混合系统的符号化可达性分析

定义了一种称作混合区域的形式化结构表示矩形混合系统的状态集,它实际上是由一组特殊形式的线性不等式联立表示的多面体空间.证明了混合区域对于矩形混合系统的可达性操作的封闭性.此外,用矩形混合系统近似模拟非线性混合系统,相应地解决了非线性混合系统的可达性问题.使用混合区域,可以直接计算由某个正则的混合区域开始的可达集,这样,混合系统的可达性问题主要是求解混合区域的正则型问题,而这问题是一种线性规划问题,可以使用经典的线性规划算法加以解决.     

混成系统研究综述

混成系统是一类既包含连续动态行为又包含离散动态行为的系统,这类系统在实际应用中显得越来越重要,对这类系统需要探索新的模型和研究方法。从建模、分析与验证三个方面综述了混成系统的研究现状和需要进一步研究的课题。     

基于多面体终端域的Hammerstein-Wiener非线性预测控制

许多实际系统都可以表示成一种中间为线性动态子系统、输入输出端为非线性静态子系统的Hammerstein-Wiener型非线性模型. 针对输入和输出受约束的Hammerstein-Wiener型非线性系统, 提出一种基于多面体终端域的预测控制综合算法. 离线设计时, 通过构造一系列多面体不变集, 扩大了终端域; 在多面体不变集内, 设计非线性控制律, 减少了常规线性控制律设计的保守性. 在线计算时, 通过求解有限个线性矩阵不等式(Linear matrix inequalities, LMIs)优化问题, 不仅可以满足实时性要求, 而且能够改善控制性能. 仿真结果表明了采用多面体不变集的优越性.     

基于Volterra级数的一类非线性系统性能评估

化工过程多具有非线性特征,针对用线性系统性能评估方法处理非线性系统会存在过估计的情况,研究了一类叠加线性干扰的非线性系统的性能评估问题。通过使用Volterra级数近似非线性环节,把最小方差性能评估问题转化成一类模型辨识问题,并从辨识误差中得到非线性系统的最小方差估计值。通过数值仿真,将新方法所得结果和现有线性性能评估方法进行了比较,验证了设计算法的优越性。     

线性混成系统的参数分析

针对线性混成系统中存在的一类典型未知参数问题,如实时系统的验证通常局限于给定矍体数值,未考虑系统中任何时间参数或物理特征参数的计算等,给出了具体的计算过程,实例应用表明,该计算过程可以有效地求解线性混成系统中这类未知参数,并能保证系统按照规约的要求正确运行。     

基于XYZ/E的混成系统

混成系统是由计算机和物理设备组成的嵌入式实时计算系统.它允许在交互式实时系统中引入连续变化的单元.XYZ/E 是基于Manna-Pnueli的线性时序逻辑的程序设计语言.它将程序的动态语义与静态语义统一在同一框架中,支持从抽象的程序规范到可执行代码的逐步求精的全过程.该文使用XYZ/E语言描述和验证混成系统.首先介绍了计算模型,然后介绍了XYZ语言对混成系统的形式化描述,最后介绍了混成系统的验证.与同类工作相比,XYZ/E支持状态转换,从而可以方便地描述复杂的控制算法.     

Computational Methods for Verification of Stochastic Hybrid Systems

Stochastic hybrid system (SHS) models can be used to analyze and design complex embedded systems that operate in the presence of uncertainty and variability. Verification of reachability properties for such systems is a critical problem. Developing sound computational methods for verification is challenging because of the interaction between the discrete and the continuous stochastic dynamics. In this paper, we propose a probabilistic method for verification of SHSs based on discrete approximations focusing on reachability and safety problems. We show that reachability and safety can be characterized as a viscosity solution of a system of coupled Hamilton-Jacobi-Bellman equations. We present a numerical algorithm for computing the solution based on discrete approximations that are derived using finite-difference methods. An advantage of the method is that the solution converges to the one for the original system as the discretization becomes finer. We also prove that the algorithm is polynomial in the number of states of the discrete approximation. Finally, we illustrate the approach with two benchmarks: a navigation and a room heater example, which have been proposed for hybrid system verification.     

Duality between reachability and observability for adjoint systems

The Kalman duality between the reachability and observability of finite-dimensional linear systems is generalized to adjoint systems (in the sense of Arbib-Manes). The theory includes previous results on infinite-dimensional linear systems and linear systems over rings, and yields new results for classes of nonlinear systems such as bilinear and polynomial systems.     

Towards an Efficient Path-Oriented Tool for Bounded Reachability Analysis of Linear Hybrid Systems using Linear Programming

The existing techniques for reachability analysis of linear hybrid automata do not scale well to problem sizes of practical interest. Instead of developing a tool to perform reachability check on all the paths of a linear hybrid automaton, a complementary approach is to develop an efficient path-oriented tool to check one path at a time where the length of the path being checked can be made very large and the size of the automaton can be made large enough to handle problems of practical interest. This approach of symbolic execution of paths can be used by design engineers to check important paths and thereby, increase the faith in the correctness of the system. Unlike simple testing, each path in our framework represents a dense set of possible trajectories of the system being analyzed. In this paper, we develop the linear programming based techniques towards an efficient path-oriented tool for the bounded reachability analysis of linear hybrid systems.     

Periodic-polynomial interpretation for structural properties of linear periodic discrete-time systems

The structural properties of linear periodic discrete-time systems are analyzed in the periodic polynomial representation. It is shown that the classical polynomial approach for linear time-invariant systems can be extended to periodic systems. New definitions and properties are given in terms of skew polynomial rings and periodic difference algebra. Necessary and sufficient conditions for the characterization of reachability, controllability, observability and reconstructibility are given in this framework.     

Analysis of Hybrid Systems Based on Hybrid Net Condition/Event System Model

In thispaper, hybrid net condition /event systems are introducedas a model for hybrid systems. The model consists of a discretetimed Petri net and a continuous Petri net which interact eachother through condition and event signals. By introducing timeddiscrete places in the model, timing constraints in hybrid systemscan be easily described. For a class of hybrid systems that canbe described as linear hybrid net condition /eventsystems whose continuous part is a constant continuous Petrinet, two methods are developed for their state reachability analysis.One is the predicate-transformation method, which is an extensionof a state reachability analysis method for linear hybrid automata.The other is the path-based method, which enumerates all possiblefiring seqenences of discrete transitions and verifies if a givenset of states can be reached from another set by firing a sequenceof discrete transitions. The verification is performed by solvinga constraint satisfaction problem. A technique that adds additionalconstraints to the problem when a discrete state is revisitedalong the sequence is developed and used to prevent the methodfrom infinite enumeration. These methods provide a basis foralgorithmic analysis of this class of hybrid systems.     

Equilibria, stability and reachability of Leslie systems withnonnegative inputs

Leslie systems, a particular class of positive systems used in population dynamics and control, are defined and analyzed. A simple property relating sign and stability of their equilibria, and some geometric characteristics of their reachability set (in cases of bounded and unbounded inputs) are proved. All the properties do not hold, in general, in other classes of positive systems. It is shown that Leslie systems have strictly positive equilibria if and only if they are asymptotically stable. Their reachability set in the case of unbounded inputs is the positive cone generated by the reachability vectors, while in the case of bounded inputs, it is a polyhedron whose vertices can be easily computed. All of these properties follow from the nonpositiveness of the coefficients of the characteristic polynomial of the system     

External estimates of the reachability sets of nonlinear controlled systems

Consideration was given to formation of the external estimates of the reachability sets of the nonlinear controlled systems in the form of the level sets of the functions satisfying the differential Hamilton-Jacobi inequalities. The trajectories of the nonlinear system are estimated by modifying the estimates of its linear part. The constructions proposed are based on comparing the systems of differential inequalities. Applications of the reachability sets of the multivariable controlled systems with nonlinear cross connections to the ellipsoidal estimates were examined.