Search

We address the problem of synthesizing provably correct controllers for linear systems with reach-avoid specifications. Discrete abstraction-based controller synthesis techniques have been developed for linear and nonlinear systems with various types of specifications. However, these methods typically suffer from the state space explosion problem. Our solution decomposes the overall synthesis problem into two smaller, and more tractable problems: one synthesis problem for an open-loop controller, which can produce a reference trajectory, and a second for synthesizing a tracking controller, which can enforce the other trajectories to follow the reference trajectory. As a key building-block result, we show that, once a tracking controller is fixed, the reachable states from an initial neighborhood, subject to any disturbance, can be overapproximated by a sequence of ellipsoids, with shapes that are independent of the open-loop controller. Hence, the open-loop controller can be synthesized independently to meet the reach-avoid specification for an initial neighborhood. Moreover, we are able to reduce the problem of synthesizing open-loop controllers to satisfiability problems over quantifier-free linear real arithmetic. The number of linear constraints in the satisfiability problem is linear to the number of hyperplanes as the surfaces of the polytopic obstacles and goal sets. The overall synthesis algorithm, computes a tracking controller, and then iteratively covers the entire initial set to find open-loop controllers for initial neighborhoods. The algorithm is sound and, for a class of robust systems, is also complete. We implement this synthesis algorithm in a tool RealSyn ver 2.0 and use it on several benchmarks with up to 20 dimensions. Experiment results are very promising: RealSyn ver 2.0 can find controllers for most of the benchmarks in seconds. [ABSTRACT FROM AUTHOR]

In this work, we study the stability of an autonomous discrete-time linear switched system whose switching sequences are generated by a Muller automaton. This system arises in various engineering problems such as distributed communication and automotive engine control. The asymptotic stability of this system, referred to as regular asymptotic stability (RAS), generalizes two well-known definitions of stability of autonomous discrete-time linear switched systems, namely absolute asymptotic stability (AAS) and shuffle asymptotic stability (SAS). We also extend these stability definitions to robust versions. We show that absolute asymptotic stability, robust absolute asymptotic stability and robust shuffle asymptotic stability are equivalent to exponential stability. In addition, by using the Kronecker product, we prove that a robust regular asymptotic stability problem is equivalent to the conjunction of several robust absolute asymptotic stability problems. [ABSTRACT FROM PUBLISHER]

Pre-orders and equivalence relations between processes, like simulation and bisimulation, have played a central role in the minimization and abstraction based verification and analysis of discrete-state systems for modal and temporal properties. In this paper, we investigate the pre-orders and equivalence relations on hybrid systems which preserve stability. We first show that stability with respect to reference trajectories is not preserved by either the traditional notion of bisimulation or the more recently proposed stronger notions with additional continuity constraints. We introduce the concept of uniformly continuous simulation and bisimulation—namely, simulation and bisimulation with some additional uniform continuity conditions on the relation—that can be used to reason about stability of trajectories. Finally, we show that uniformly continuous simulations and bisimulations are widely prevalent, by recasting many classical results on proving stability of dynamical and hybrid systems as establishing the existence of a simple, obviously stable system that (bi)-simulates the given system through uniformly continuous (bi)-simulations. We also discuss briefly a new abstraction method for stability analysis which is based on the foundations developed in the paper. [ABSTRACT FROM PUBLISHER]

We consider the class of o-minimally definable hybrid automata with a bounded discrete-transition horizon. We show that for every hybrid automata in this class, there exists a bisimulation of finite index, and that the bisimulation quotient can be effectively constructed when the underlying o-minimal theory is decidable. More importantly, we give natural specifications for hybrid automata which ensure the boundedness of discrete-transition horizons. In addition, we show that these specifications are reasonably tight with respect to the decidability of the models and that they can model modern day real-time and embedded systems. As a result, the analysis of several problems for these systems admit effective algorithms. We provide a representative example of a hybrid automaton in this class. Unlike previously examined subclasses of o-minimally defined hybrid automata with decidable verification properties and extended o-minimal hybrid automata, we do not impose re-initialization of the continuous variables in a memoryless fashion when a discrete transition is taken. Our class of hybrid systems has both rich continuous dynamics and strong discrete-continuous coupling, showing that it is not necessary to either simplify the continuous dynamics or restrict the discrete dynamics to achieve decidability. [ABSTRACT FROM AUTHOR]