A piecewise ellipsoidal reachable set estimation method for continuous bimodal piecewise affine systems

In this work, the issue of estimation of reachable sets in continuous bimodal piecewise affine systems is studied. A new method is proposed, in the framework of ellipsoidal bounding, using piecewise quadratic Lyapunov functions. Although bimodal piecewise affine systems can be seen as a special class of affine hybrid systems, reachability methods developed for affine hybrid systems might be inappropriately complex for bimodal dynamics. This work goes in the direction of exploiting the dynamical structure of the system to propose a simpler approach. More specifically, because of the piecewise nature of the Lyapunov function, we first derive conditions to ensure that a given quadratic function is positive on half spaces. Then, we exploit the property of bimodal piecewise quadratic functions being continuous on a given hyperplane. Finally, linear matrix characterizations of the estimate of the reachable set are derived.     

A geometric approach for reachability and observability of linear switched impulsive systems

This paper is concerned with the reachability and observability of linear switched impulsive systems with singular impulse matrices. First some new concepts with respect to the reachability and unobservability are introduced. Especially, span reachability is proposed because the reachable sets of switched impulsive systems do not always constitute subspaces. Then the geometric characterization of the span reachable and unobservable sets is presented. Moreover, the relations between the span reachable set, unobservable set and the invariant subspaces of such systems are discussed. Finally, corresponding criteria applied to linear impulsive systems and linear switched systems are also discussed.     

Triple integral approach to reachable set bounding for linear singular systems with time‐varying delay

This paper is concerned with the reachable set estimation problem of singular systems with time‐varying delay and bounded disturbance inputs. Based on a novel Lyapunov–Krasovskii functional that contains four triple integral terms, reciprocally convex approach and free‐weighting matrix method, two sufficient conditions are derived in terms of linear matrix inequalities to guarantee that the reachable set of singular systems with time‐varying delay is bounded by the intersection of ellipsoid. Finally, two numerical examples are given to demonstrate the effectiveness and superiority of the proposed method. Copyright © 2016 John Wiley & Sons, Ltd.     

Partial Differential Equation for Evolution of Star-Shaped Reachability Domains of Differential Inclusions

The problem of reachability for differential inclusions is an active topic in the recent control theory. Its solution provides an insight into the dynamics of an investigated system and also enables one to design synthesizing control strategies under a given optimality criterion. The primary results on reachability were mostly applicable to convex sets, whose dynamics is described through that of their support functions. Those results were further extended to the viability problem and some types of nonlinear systems. However, non-convex sets can arise even in simple bilinear systems. Hence, the issue of nonconvexity in reachability problems requires a more detailed investigation. The present article follows an alternative approach for this cause. It deals with star-shaped reachability sets, describing the evolution of these sets in terms of radial (Minkowski gauge) functions. The derived partial differential equation is then modified to cope with additional state constraints due to on-line measurement observations. Finally, the last section is on designing optimal closed-loop control strategies using radial functions.     

Computing reachable sets for uncertain nonlinear monotone systems

We address nonlinear reachability computation for uncertain monotone systems, those for which flows preserve a suitable partial orderings on initial conditions. In a previous work Ramdani (2008) [22], we introduced a nonlinear hybridization approach to nonlinear continuous reachability computation. By analysing the signs of off-diagonal elements of system’s Jacobian matrix, a hybrid automaton can be obtained, which yields component-wise bounds for the reachable sets. One shortcoming of the method is induced by the need to use whole sets for addressing mode switching. In this paper, we improve this method and show that for the broad class of monotone dynamical systems, component-wise bounds can be obtained for the reachable set in a separate manner. As a consequence, mode switching no longer needs to use whole solution sets. We give examples which show the potentials of the new approach.     

Analysis of multi-stage open shop processing systems

We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).     

Reachability realization and stabilizability of switched linear discrete-time systems

In this paper, the reachability realization of a switched linear discrete-time system, which is a collection of linear time-invariant discrete-time systems along with some maps for “switching” among them, is addressed. The main contribution of this paper is to prove that for a switched linear discrete-time system, there exists a basic switching sequence such that the reachable (controllable) state set of this basic switching sequence is equal to the reachable (controllable) state set of the system. Hence, the reachability (controllability) can be realized by using only one switching sequence. We also discuss the stabilizability of switched systems, and obtain a sufficient condition for stabilizability. Two numeric examples are given to illustrate the results.     

A CSP Versus a Zonotope-Based Method for Solving Guard Set Intersection in Nonlinear Hybrid Reachability

Computing the reachable set of hybrid dynamical systems in a reliable and verified way is an important step when addressing verification or synthesis tasks. This issue is still challenging for uncertain nonlinear hybrid dynamical systems. We show in this paper how to combine a method for computing continuous transitions via interval Taylor methods and a method for computing the geometrical intersection of a flowpipe with guard sets, to build an interval method for reachability computation that can be used with truly nonlinear hybrid systems. Our method for flowpipe guard set intersection has two variants. The first one relies on interval constraint propagation for solving a constraint satisfaction problem and applies in the general case. The second one computes the intersection of a zonotope and a hyperplane and applies only when the guard sets are linear. The performance of our method is illustrated on examples involving typical hybrid systems.     

Reachability and Observability Concepts for Stochastic Systems

We define observability and reachability and introduce the corresponding Gramians for a Levy driven linear system like Benner, Damm in [3] which focused on the case of Wiener noise. We additionally show that the sets of observable and reachable states are characterized by these Gramians. This is analogous to deterministic systems, where observability and reachability concepts are described in Sections 4.2.1 and 4.2.2 in Antoulas [1]. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Geometric control of hybrid systems

In this paper, we present a geometric approach for computing controlled invariant sets for hybrid control systems. While the problem is well studied in the ellipsoidal case, this family is quite conservative for constrained or switched linear systems. We reformulate the invariance of a set as an inequality for its support function that is valid for any convex set. This produces novel algebraic conditions for the invariance of sets with polynomial or piecewise quadratic support functions.     

Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

Multicriteria optimization of convex dynamical systems

We suggest an approach to the solution of multicriteria optimization problems for dynamical systems described by differential inclusions. The investigation is restricted to dynamical systems with concave differential inclusion, for which the trajectory tube is convex. Such systems are typical of economic models. We assume that the criteria for the choice of the solution depend on the system state at a given terminal time and are related to it by sufficiently arbitrary functions. The approach is based on the interactive visualization of the Pareto frontier, which is carried out by approximating the reachable set of the dynamical system and the Edgeworth-Pareto set of feasible criteria vectors.     

Output controllability and optimal output control of positive fractional order linear discrete system with multiple delays in state, input and output

The article concerns output controllability and optimal output control of positive fractional order discrete linear systems with multiple delays in state, input and output. Necessary and sufficient conditions for output reachability (output controllability from zero initial conditions) and null output controllability (output controllability to zero final output) are given and proven. We also prove that the positive system is output controllable if it is output reachable and null output controllable with the output reachability index is equal or less than the null output controllability index. Sufficient conditions for the solvability of the optimal output control problem are given. Numerical examples are presented to illustrate the theoretical results.     

Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes

The computation of reachable sets for hybrid systems with linear continuous dynamics is addressed. Zonotopes are used for the representation of reachable sets, resulting in an algorithm with low computational complexity with respect to the dimension of the considered system. However, zonotopes have drawbacks when being intersected with transition guards which determine the discrete behavior of the hybrid system. For this reason, in the proposed approach, reachable sets are represented by polytopes within guard sets as an intermediate step in order to enclose them by zonotopes afterwards. Different methods for the conservative conversion from zonotopes to polytopes and vice versa are proposed and numerically evaluated.     

Determination of Inner and Outer Bounds of Reachable Sets Through Subpavings

The computation of the reachable set of states of a given dynamic system is an important step to verify its safety during operation. There are different methods of computing reachable sets, namely interval integration, capture basin, methods involving the minimum time to reach function, and level set methods. This work deals with interval integration to compute subpavings to over or under approximate reachable sets of low dimensional systems. The main advantage of this method is that, compared to guaranteed integration, it allows to control the amount of over-estimation at the cost of increased computational effort. An algorithm to over and under estimate sets through subpavings, which potentially reduces the computational load when the test function or the contractor is computationally heavy, is implemented and tested. This algorithm is used to compute inner and outer approximations of reachable sets. The test function and the contractors used in this work to obtain the subpavings involve guaranteed integration, provided either by the Euler method or by another guaranteed integration method. The methods developed were applied to compute inner and outer approximations of reachable sets for the double integrator example. From the results it was observed that using contractors instead of test functions yields much tighter results. It was also confirmed that for a given minimum box size there is an optimum time step such that with a greater or smaller time step worse results are obtained.     

A Survey of Reachability and Controllability for Positive Linear Systems

This paper is a survey of reachability and controllability results for discrete-time positive linear systems. It presents a variety of criteria in both algebraic and digraph forms for recognising these fundamental system properties with direct implications not only in dynamic optimization problems (such as those arising in inventory and production control, manpower planning, scheduling and other areas of operations research) but also in studying properties of reachable sets, in feedback control problems, and others. The paper highlights the intrinsic combinatorial structure of reachable/controllable positive linear systems and reveals the monomial components of such systems. The system matrix decomposition into monomial components is demonstrated by solving some illustrative examples.     

Reachability sets of hybrid systems in the presence of successive switchings

The concept of reachability domains of hybrid systems is described together with the use of ellipsoidal methods for calculation of such domains in the case when there are successive switchings on several given hyperplanes or bands. An algorithm for calculation of the reachability sets for a hybrid system that uses ellipsoidal approximations is given for the cases in which the switching sets are planes or bands. The parametrization of nonconvex reachability domains is obtained as a union of intersections of the corresponding ellipsoidal estimates.     

Optimization Techniques for State-Constrained Control and Obstacle Problems

The design of control laws for systems subject to complex state constraints still presents a significant challenge. This paper explores a dynamic programming approach to a specific class of such problems, that of reachability under state constraints. The problems are formulated in terms of nonstandard minmax and maxmin cost functionals, and the corresponding value functions are given in terms of Hamilton-Jacobi-Bellman (HJB) equations or variational inequalities. The solution of these relations is complicated in general; however, for linear systems, the value functions may be described also in terms of duality relations of convex analysis and minmax theory. Consequently, solution techniques specific to systems with a linear structure may be designed independently of HJB theory. These techniques are illustrated through two examples.The first author was supported by the Russian Foundation for Basic Research, Grant 03-01-00663, by the program Universities of Russia, Grant 03.03.007, and by the program of the Russian Federation President for the support of scientific research in leading scientific schools, Grant NSh-1889.2003.1.The second author was supported by the National Science and Engineering Research Council of Canada and by ONR MURI Contract 79846-23800-44-NDSAS.The third and first authors were supported by NSF Grants ECS-0099824 and ECS-0424445.Communicated by G. Leitmann     

Analytical Linear Inequality Systems and Optimization

In many interesting semi-infinite programming problems, all the constraints are linear inequalities whose coefficients are analytical functions of a one-dimensional parameter. This paper shows that significant geometrical information on the feasible set of these problems can be obtained directly from the given coefficient functions. One of these geometrical properties gives rise to a general purification scheme for linear semi-infinite programs equipped with so-called analytical constraint systems. It is also shown that the solution sets of such kind of consistent systems form a transition class between polyhedral convex sets and closed convex sets in the Euclidean space of the unknowns.     

Weakly invariant sets of hybrid systems

We consider a mathematical model of a hybrid system in which the continuous dynamics generated at any point in time by one of a given finite family of continuous systems alternates with discrete operations commanding either an instantaneous switching from one system to another, or an instantaneous passage from current coordinates to some other coordinates, or both operations simultaneously. As a special case, we consider a model of a linear switching system. For a hybrid system, we introduce the notion of a weakly invariant set and analyze its structure. We obtain a representation of a weakly invariant set as a union of sets of simpler structure. For the latter sets, we introduce special value functions, for which we obtain expressions by methods of convex analysis. For the same functions, we derive equations of the Hamilton-Jacobi-Bellman type, which permit one to pass from the problem of constructing weakly invariant sets to the control synthesis problem for a hybrid system.