On the closure of reachable sets for control systems

We prove the existence of a dense subsetD of continuous functions such that, forfD, the reachable set for the control system

Guaranteed-accuracy approximation of reachable sets for a linear dynamic system subject to impulse actions

A method is proposed for approximating the reachable set of a dynamic system with a state space dimension no higher than six-eight considered on a finite time interval. The system is governed by linear differential equations with piecewise constant coefficients and impulse actions specified at prescribed times. The method is based on guaranteed-accuracy polyhedral approximations of reachable sets at researcher-specified times. Every approximation is constructed using the preceding one. A procedure is described for choosing parameters of the method that ensure the required accuracy with close-to-minimal time costs.     

On the boundedness and unboundedness of external polyhedral estimates for reachable sets of linear differential systems

The boundedness and unboundedness properties of external polyhedral (paralle-lepiped-valued) estimates are investigated for reachable sets of linear differential systems with a stable matrix. Boundedness and unboundedness criteria on an infinite time interval are presented for two types of estimates (“touching” estimates, which were introduced earlier, and estimates with constant orientation matrix). Conditions for the system matrix and bounding sets are given under which there are bounded estimates among the estimates of the mentioned types, under which there are unbounded estimates, and under which all the estimates are bounded or all the estimates are unbounded. In terms of the exponents of the estimates, the possible rate of their growth is described. For two-dimensional systems, the classification and comparison of possible situations of the boundedness or unboundedness for estimates of both types are given and boundedness criteria for estimates with special (orthogonal and “quasi-orthogonal”) constant orientation matrices are found. Results of numerical modeling are presented.     

Estimating reachable sets for two-dimensional linear discrete systems

We are concerned with the problem of estimating the reachable set for a two-dimensional linear discrete-time system with bounded controls. Different approaches are adopted depending on whether the system matrix has real or complex eigenvalues. For the complex eigenvalue case, the quasiperiodic nature of minimum time trajectories is exploited in developing a simple, but often accurate, procedure. For the real eigenvalue case, over estimates of reachable sets can be trivially obtained using a decomposition method.The second author was supported by funds supplied by the John M. Bennett Faculty Fellowship, Trinity University, San Antonio, Texas.     

Reachable and controllable sets for two-dimensional,linear, discrete-time systems

We consider two-dimensional discrete-time linear systems with constrained controls. We propose a simple polynomial time procedure to give an exact external representation of theN-step reachable set and controllable set. The bounding hyperplanes are explicitly derived in terms of the data of the problem. By using a result in computational geometry, all the calculations are made in polynomial time in contrast to classical methods. The limit case asN is also investigated.     

Hyperplane method for reachable state estimation for linear time-invariant systems

A numerical algorithm is presented for generating inner and outer approximations for the set of reachable states for linear time-invariant systems. The algorithm is based on analytical results characterizing the solutions to a class of optimization problems which determine supporting hyperplanes for the reachable set. Explicit bounds on the truncation error for the finite-time case yield a set of so-called -supporting hyperplanes which can be generated to approximate the infinite-time reachable set within an arbitrary degree of accuracy. At the same time, an inner approximation is generated as the convex hull of points on the boundary of the finite-time reachable set. Numerical results are presented to illustrate the hyperplane method. The concluding section discusses directions for future work and applications of the method to problems in trajectory planning in servo systems.This research was supported in part by Digital Equipment Corporation through the American Electronics Association Fellowship Loan Program and by the National Science Foundation under Grant No. ECS-84-04607.     

Outer ellipsoidal approximations of the reachable set at infinity for linear systems

Outer ellipsoidal approximations to the reachable set at infinity for a linear control system with bounded scalar controls are obtained using a new method based on quadratic Lyapunov functions. These outer approximations are compared with those given by an algorithm due to Sabin and Summers, and also with certain tangential outer approximations, obtained using a fixed-point iteration scheme.This research was supported by the Natural Sciences and Engineering Research Council of Canada. The authors gratefully acknowledge the assistance of Mr. Ryan Davies, recipient of an NSERC Undergraduate Research Award.     

Asymptotic estimates for reachable sets of singularly perturbed linear systems

We study the limit behavior of the reachable set for singularly perturbed nonautonomous linear systems with geometric control constraints. We assume that the system is stable in the fast variables and its coefficients are Lipschitz functions of time. We obtain estimates for the convergence rate as the small parameter tends to zero.     

On the reachable sets in linear systems

We consider the finite-dimensional linear control system, with minimal assumptions concerning the control restraint set . Specifically, we consider the set of reachable states and conclude that as far as controllability is concerned, can be replaced by convhull().     

Note on prime representations of convex polyhedral sets

Consider a convex polyhedral set represented by a system of linear inequalities. A prime representation of the polyhedron is one that contains no redundant constraints. We present a sharp upper bound on the difference between the cardinalities of any two primes.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A8807, A4625, and A7742.     

On external estimates for reachable sets of nonlinear control systems

The paper is devoted to the problem of constructing external estimates for reachable sets of a nonlinear control system. The estimates are constructed in the form of level sets of smooth functions in the space of states satisfying differential inequalities. In the system under consideration, the linear part is found, for which the corresponding functions are assumed to be known. The method proposed for estimating trajectories of a nonlinear system is based on modifying estimates for the linear part and on applying the comparison principle.     

Locally Farkas-Minkowski linear inequality systems

This paper introduces thelocally Farkas-Minkowski (LFM) linear inequality systems in a finite dimensional Euclidean space. These systems are those ones that satisfy that any consequence of the system that is active at some solution point is also a consequence of some finite subsystem. This class includes the Farkas-Minkowski systems and verifies most of the properties that these systems possess. Moreover, it contains the locally polyhedral systems, which are the natural external representation of quasi-polyhedral sets. TheLFM systems appear to be the natural external representation of closed convex sets. A characterization based on their properties under the union of systems is provided. In linear semi-infinite programming, theLFM property is the more general constraint qualification such that the Karush-Kuhn-Tucker condition characterizes the optimal points. Furthermore, the pair of Haar dual problems has no duality gap.     

On the intersection of controllable and reachable sets

In this paper, we prove that the intersection of the controllable set to and the reachable set from a point target is connected, and that points within the intersection have the same controllable and reachable sets. We further demonstrate that the intersection is positive invariant whenever the intersection is not a single point. We then introduce the concept of a maneuverable set which allows us to generalize the results by replacing the point target with a maneuverable set. Use of the theory is illustrated.This paper is based on research supported by NSF Grant INT-82-10803 and the University of Western Australia (Visiting Fellowship, Department of Mathematics, 1983).     

Reachability properties of constrained linear systems

This paper presents reachability results for a linear control system and arbitrary terminal pointsp inR ⁿ with controls constrained within a compact setU containing the origin. The well-known results forp=0 are then a special case of our results.Geometric properties of the reachable set are presented and include: general containment properties which describe conditions that guarantee the inclusion of a reachable set in another reachable set; classification of the set of all pointsp that ensure the equivalence of two (different) reachable sets and the properties of this set.The topological properties of the reachable set to a pointp depends on the control setU, the final pointp, and the location of the spectrum of the system in the complex plane. We characterize the geometric properties of the reachable set when the spectrum lies in the closed right-half plane, the open left-half plane, or a combination of both.This work was supported in part by NSF Grant ECS-86-09586.     

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.     

Minimal representation of convex polyhedral sets

A system of linear inequality and equality constraints determines a convex polyhedral set of feasible solutionsS. We consider the relation of all individual constraints toS, paying special attention to redundancy and implicit equalities. The main theorem derived here states that the total number of constraints together determiningS is minimal if and only if the system contains no redundant constraints and/or implicit equalities. It is shown that the existing theory on the representation of convex polyhedral sets is a special case of the theory developed here.The author is indebted to Dr. A. C. F. Vorst (Erasmus University, Rotterdam, Holland) for stimulating discussions and comments, which led to considerable improvements in many proofs. Most of the material in this paper originally appeared in the author's dissertation (Ref. 1). The present form was prepared with partial support from a NATO Science Fellowship for the Netherlands Organization for the Advancement of Pure Research (ZWO) and a CORE Research Fellowship.     

Separating the solution sets of analytical and polynomial systems

A linear inequality system with infinitely many constraints is polynomial (analytical) if its index set is a compact interval of the real line and all its coefficients are polynomial (analytical, respectively) functions of the index on this interval. This paper provides an example of analytical system whose solution set cannot be the solution set of any polynomial system. Research supported by DGES of Spain and FEDER of UE, Grant BFM2002-04114-C02-01. Research supported by CONACyT of Mexico, Grant 130036. Research partially supported by CONACyT of Mexico, Grant 44003.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

Controllability properties of constrained linear systems

In this paper, we present results on constrained controllability for linear control systems. The controls are constrained to take values in a compact set containing the origin. We use the results on reachability properties discussed in Ref. 1.We prove that controllability of an arbitrary pointp inR ⁿ is equivalent to an inclusion property of the reachable sets at certain positive times. We also develop geometric properties ofG, the set of all nonnegative times at whichp is controllable, and ofC, the set of all controllable points. We characterize the setC for the given system and provide additional spectrum-dependent structure.We show that, for the given linear system, several notions of constrained controllability of the pointp are the same, and thus the setC is open. We also provide a necessary condition for small-time (differential or local) constrained controllability ofp.This work was supported in part by NSF Grant ECS-86-09586.     

Inner and outer bounds for the solution set of parametric linear systems

Consider linear systems involving affine-linear dependencies on interval parameters. Presented is a free C-XSC software implementing a generalized parametric fixed-point iteration method for verified enclosure of the parametric solution set. Some specific features of the corresponding algorithm concerning sharp enclosure of the contracting matrix and inner approximation of the solution enclosure are discussed.