Constructing invariants for hybrid systems

We present a new method for generating algebraic invariants of hybrid systems. The method reduces the invariant generation problem to a constraint solving problem using techniques from the theory of ideals over polynomial rings. Starting with a template invariant—a polynomial equality over the system variables with unknown coefficients—constraints are generated on the coefficients guaranteeing that the solutions are inductive invariants. To control the complexity of the constraint solving, several stronger conditions that imply inductiveness are proposed, thus allowing a trade-off between the complexity of the invariant generation process and the strength of the resulting invariants. This research was supported in part by NSF grants CCR-01-21403, CCR-02-20134 and CCR-02-09237, by ARO grant DAAD19-01-1-0723, by ARPA/AF contracts F33615-00-C-1693 and F33615-99-C-3014, and by NAVY/ONR contract N00014-03-1-0939.     

Network invariants for real-time systems

We extend the approach of model checking parameterized networks of processes by means of network invariants to the setting of real-time systems. We introduce timed transition structures (which are similar in spirit to timed automata) and define a notion of abstraction that is safe with respect to linear temporal properties. We strengthen the notion of abstraction to allow a finite system, then called network invariant, to be an abstraction of networks of real-time systems. In general the problem of checking abstraction of real-time systems is undecidable. Hence, we provide sufficient criteria, which can be checked automatically, to conclude that one system is an abstraction of a concrete one. Our method is based on timed superposition and discretization of timed systems. We exemplify our approach by proving mutual exclusion of a simple protocol inspired by Fischer’s protocol, using the model checker TLV. Part of this work was done during O. Grinchtein’s stay at Weizmann Institute. This author was supported by the European Research Training Network “Games”.     

Quantifier-free logic for nondeterministic theories

We develop a quantifier-free logic for deriving consequences of multialgebraic theories. Multialgebras are used as models for nondeterminism in the context of algebraic specifications. They are many sorted algebras with set-valued operations. Formulae are sequents over atoms allowing one to state set-inclusion or identity of 1-element sets (determinacy). We introduce a sound and weakly complete Rasiowa–Sikorski (R–S) logic for proving multialgebraic tautologies. We then extend this system for proving consequences of specifications based on translation of finite theories into logical formulae. Finally, we show how such a translation may be avoided—introduction of the specific cut rules leads to a sound and strongly complete Gentzen system for proving directly consequences of specifications. Besides giving examples of the general techniques of R–S and the specific cut rules, we improve the earlier logics for multialgebras by providing means to handle empty carriers (as well as empty result-sets) without the use of quantifiers, and to derive consequences of theories without translation into another format and without using general cut.     

一般离散完整系统Mei对称性的精确不变量与绝热不变量

研究一般离散完整系统Mei对称性的精确不变量和绝热不变量.给出未受扰动时一般离散完整系统Mei对称性导致的精确不变量,讨论在小扰动作用下系统Mei对称性的摄动,得到一般离散完整系统Mei对称性的摄动导致的一类绝热不变量.最后举例说明结果的应用.     

Basis of invariants and canonical forms for linear dynamic systems

This paper is a study of the problem of how to parametrize the set of all finite order constant linear systems. The parameters are interpreted as independent invariants for the equivalence relation which defines two systems to be equivalent when they have the same impulse response. Two kinds of canonical representations of the systems are constructed from the invariants, one of the state-space equations type and the other of the transfer function type.     

Abstractions for hybrid systems

We present a procedure for constructing sound finite-state discrete abstractions of hybrid systems. This procedure uses ideas from predicate abstraction to abstract the discrete dynamics and qualitative reasoning to abstract the continuous dynamics of the hybrid system. It relies on the ability to decide satisfiability of quantifier-free formulas in some theory rich enough to encode the hybrid system. We characterize the sets of predicates that can be used to create high quality abstractions and we present new approaches to discover such useful sets of predicates. Under certain assumptions, the abstraction procedure can be applied compositionally to abstract a hybrid system described as a composition of two hybrid automata. We show that the constructed abstractions are always sound, but are relatively complete only under certain assumptions.     

Security invariants in discrete transition systems

The Shadow semantics is a qualitative model for noninterference security for sequential programs. In this paper, we first extend the Shadow semantics to Event-B, to reason about discrete transition systems with noninterference security properties. In particular, we investigate how these security properties can be specified and proved as machine invariants. Next we highlight the role of security invariants during refinement and identify some common patterns in specifying them. Finally, we propose a practical extension to the supporting Rodin platform of Event-B, with the possibility of having some properties to be invariants-by-construction.     

Definitions of invariants for n-dimensional traced vector fields of dynamic systems

In this paper, the method of definitions of invariants of n-dimensional vector fields of dynamic systems based on orthogonal decomposition of vector fields to tangential and gradient components has been studied. This method is meant for defining invariant characteristics at visualization of the vector fields of a dynamic system. Sergei Nikolaevich Chukanov was born in 1951. He graduated from Omsk State Pedagogical Institute in 1974. He received his candidate’s degree (05.07.09) in 1990 and his doctoral degree (05.07.09) in 2000. Currently, he is with the Omsk Department of the Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences as head of a laboratory. His scientific interests included the following: geometrical methods of investigation of control systems of complex dynamic systems and visualization of processes in complex dynamic systems. He is the author of 90 papers.     

An algorithm for determining a class of invariants in quasi-polynomial systems

In this paper an algorithm is proposed for the retrieval of a wide class of invariants in quasi-polynomial systems. The invariance properties of the algorithm under different transformations are discussed. The application of the algorithm is illustrated on physical and numerical examples. The algorithm has been implemented in the MATLAB computing environment.     

Gronwall inequality for hybrid systems

The Gronwall inequality, a well-known and useful result both for continuous-time and discrete-time signals, is extended to hybrid signals, namely those that combine continuous time and discrete time. An application of the result to establishing a bounded energy bounded state property for hybrid systems with inputs is provided.     

Taylor approximation for hybrid systems

We propose a new approximation technique for Hybrid Automata. Given any Hybrid Automaton H, we call Approx(H, k) the Polynomial Hybrid Automaton obtained by approximating each formula ϕ in H with the formulae ϕ_k obtained by replacing the functions in ϕ with their Taylor polynomial of degree k. We prove that Approx(H, k) is an over-approximation of H. We study the conditions ensuring that, given any ϵ > 0, some k₀ exists such that, for all k > k₀, the “distance” between any vector satisfying ϕ_k and at least one vector satisfying ϕ is less than ϵ. We study also conditions ensuring that, given any ϵ > 0, some k₀ exists such that, for all k > k₀, the “distance” between any configuration reached by Approx(H, k) in n steps and at least one configuration reached by H in n steps is less than ϵ.     

Output-to-state stability for hybrid systems

Output-to-state stability (OSS) is a dual notion of input-to-state stability for dynamical systems. This paper presents Lyapunov and asymptotic characterizations of OSS for hybrid dynamical systems, emphasizing that a globally detectable (i.e. nonuniformly OSS) hybrid system admits a smooth OSS-Lyapunov function.     

混杂系统的预测控制

因混杂系统预测控制（PC-HS）具有在线处理控制量和状态量的约束等优点,而成为学术界研究的一个热点．系统地论述了PC-HS的发展和研究现状,在介绍混杂系统的背景和模型的基础上,重点讨论了PC-HS的各种算法、性能等几个前沿问题,并对PC-HS目前研究中存在的问题进行了分析,对未来的一些研究方向进行了展望．     

Error encoding algorithms for networked control systems

A networked control system is characterized by having a feedback loop closed through a local area network. This paper considers methods for scheduling the use of the network to guarantee both stability and controller performance. We propose and validate algorithms for choosing message identifiers for dynamically scheduled networked control systems. Two schemes for selecting priority levels are proposed: a fixed arbitrary grid and an auto-scaling grid. We prove that the system is uniformly ultimately bounded in the case of the fixed encoding scheme, and asymptotically stable with auto-scaling. An inverted pendulum is used to illustrate the encoding methods.     

A microvalve for hybrid microfluidic systems

A hybrid valve for lab on chip applications is presented. The valve is assembled by bonding poly (methyl methacrylate), PMMA, and silicon-based elastomers. The process used to promote the hybrid bonding includes the deposition of an organosilane (TMSPM) on the thermoplastic polymer, PMMA to interface PMMA and elastomers. For this study, a membrane in ELASTOSIL^? is bonded in correspondence of the end of two microfluidic channels of a fabricated PMMA microfluidic chip. Prior the bonding, a plasma etching process has been used to remove the TMSPM in a confined circular area. This process made possible to bond selectively the edge of a membrane leaving free to move its central part. Actuating the membrane with an external positive pressure or vacuum is possible, respectively, to obstruct or to connect the microfluidic channels. The microvalve may be simply integrated in microfluidic devices and permits the control of microvolumes of fluid in processes such as transport, separation, and mixing. The deposition of the TMSPM, the bonding of the valve and its actuation has been characterized and tested. The flow rate control of liquids through the valve has been characterized. The results have been discussed and commented. The valve can stand up to 14 psi without showing leakages.     

Kalman filter for controlled hybrid systems

The linear partially observed discrete-continuous (hybrid) stochastic controllable system described by differential equations with measures is considered. The optimal filtering equations in the form of generalized Kalman filter are obtained in the case of non-anticipating control. This result could be a theoretical basis for the optimal control in stochastic hybrid systems with incomplete information.     

Model simplification for switched hybrid systems

This paper is concerned with the problem of model reduction for switched system, which is an important class of hybrid systems frequently encountered in practical situations. Two sharply different approaches are proposed to solve this problem. The first approach casts the model reduction into a convex optimization problem, which is the first attempt to solve the model reduction problem by using linearization procedure. The second one, based on the cone complementarity linearization idea, casts the model reduction problem into a sequential minimization problem subject to linear matrix inequality constraints. Both approaches have their own advantages and disadvantages concerning conservatism and computational complexity. A numerical example illustrates the effectiveness of the proposed theories.     

Control design for integrator hybrid systems

The authors define controllability for hybrid systems as the existence of correct control laws that transfer the hybrid plant between predefined subsets of the hybrid state space. A methodology for analyzing controllability and synthesizing control laws for a class of hybrid systems, applicable especially in batch control, is proposed. They use a framework consisting of a hybrid plant and a hybrid controller that interact in a feedback fashion