Ellipsoidal Bounds on Reachable Sets of Dynamical Systems with Matrices Subjected to Uncertain Perturbations1

Linear dynamical systems described by finite-difference or ordinary differential equations are considered. The matrix of the system is uncertain or subject to disturbances, and only the bounds on admissible perturbations of the matrix are known. Outer ellipsoidal estimates of reachable sets of the system are obtained and equations describing the evolution of the approximating ellipsoids are derived. An example is presented.     

Differential equations for ellipsoidal estimates for reachable sets of a nonlinear dynamical control system

The problem of estimating trajectory tubes of a nonlinear control dynamical system with uncertainty in initial data is considered. It is assumed that the dynamical system has a special structure, in which nonlinear terms are quadratic in phase coordinates and the values of the uncertain initial states and admissible controls are subject to ellipsoidal constraints. Differential equations are found that describe the dynamics of the ellipsoidal estimates of reachable sets of the nonlinear dynamical system under consideration. To estimate reachable sets of the nonlinear differential inclusion corresponding to the control system, we use results from the theory of ellipsoidal estimation and the theory of evolution equations for set-valued states of dynamical systems under uncertainty.     

Reachable Set Bounding for Linear Discrete-Time Systems with Delays and Bounded Disturbances

This paper addresses the problem of reachable set bounding for linear discrete-time systems that are subject to state delay and bounded disturbances. Based on the Lyapunov method, a sufficient condition for the existence of ellipsoid-based bounds of reachable sets of a linear uncertain discrete system is derived in terms of matrix inequalities. Here, a new idea is to minimize the projection distances of the ellipsoids on each axis with different exponential convergence rates, instead of minimization of their radius with a single exponential rate. A smaller bound can thus be obtained from the intersection of these ellipsoids. A numerical example is given to illustrate the effectiveness of the proposed approach.     

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.     

Parallel algorithm for calculating the invariant sets of high-dimensional linear systems under uncertainty

The development of efficient computational methods for synthesizing controls of high-dimensional linear systems is an important problem in theoretical mathematics and its applications. This is especially true for systems with geometrical constraints imposed on the controls and uncertain disturbances. It is well known that the synthesis of target controls under the indicated conditions is based on the construction of weakly invariant sets (reverse reachable sets) generated by the solving equations of the process under study. Methods for constructing such equations and corresponding invariant sets are described, and the computational features for high-dimensional systems are discussed. The approaches proposed are based on the previously developed theory and methods of ellipsoidal approximations of multivalued functions.     

State estimation of linear dynamical systems under bounded control

The problem of estimation of all possible states that a linear system under bounded control may take (namely, the reachable or attainable set) is addressed. A number of previously developed Lyapunov techniques for estimating the reachable set of ann-dimensional linear system are extended and compared. The techniques produce over-estimates in the form ofn-dimensional ellipsoids. Illustrative examples are solved.This work was supported by the Natural Sciences and Engineering Research Council of Canada, Operating Grant Nos. A-0621 and A-4080, and by Research Personnel Support from the Dean of Science, Memorial University of Newfoundland, Canada.     

External Ellipsoidal Estimation of the Union of Two Concentric Ellipsoids and Its Applications

For an arbitrary set representable as the convex hull formed by the union of two concentric ellipsoids we propose a method to construct a family of external undominated ellipsoidal approximations and represent the estimated set as the intersection of all estimates from a given family. A sufficient condition of undominated guaranteed ellipsoidal approximation of a convex compactum is derived. A method is described that for certain classes of sets (such as the intersection of an ellipsoid or a cone with two halfspaces) constructs a family of internal undominated ellipsoidal approximations using the previous formulas for the external estimates of the union of concentric ellipsoids.     

Internal ellipsoidal estimates of attainability sets for linear systems under conditions of uncertainty

The problem of constructing internal ellipsoidal estimates of the geometric difference between two ellipsoids and applying the estimated results for the attainability sets of linear systems with a disturbance is considered. An addition to the existing method of constructing the difference between two ellipsoids is presented, and the previous constraints are removed. In the process of validating the addition, some relationships between certain properties of constructed ellipsoidal estimations and set convexity are given, being the data for the problem. A method for estimating the attainability sets for linear systems with a disturbance, equivalent to the existing approach to systems without disturbances, are given. The disturbances are considered using the obtained results.     

On dominance core and stable sets for cooperative ellipsoidal games

Abstract

The allocation problem of rewards or costs is a central question for individuals and organizations contemplating cooperation under uncertainty. The involvement of uncertainty in cooperative games is motivated by the real world where noise in observation and experimental design, incomplete information and further vagueness in preference structures and decision-making play an important role. The theory of cooperative ellipsoidal games provides a new game theoretical angle and suitable tools for answering this question. In this paper, some solution concepts using ellipsoids, namely the ellipsoidal imputation set, the ellipsoidal dominance core and the ellipsoidal stable sets for cooperative ellipsoidal games, are introduced and studied. The main results contained in the paper are the relations between the ellipsoidal core, the ellipsoidal dominance core and the ellipsoidal stable sets of such a game.     

Reachability analysis of linear systems using support functions

This work is concerned with the algorithmic reachability analysis of continuous-time linear systems with constrained initial states and inputs. We propose an approach for computing an over-approximation of the set of states reachable on a bounded time interval. The main contribution over previous works is that it allows us to consider systems whose sets of initial states and inputs are given by arbitrary compact convex sets represented by their support functions. We actually compute two over-approximations of the reachable set. The first one is given by the union of convex sets with computable support functions. As the representation of convex sets by their support function is not suitable for some tasks, we derive from this first over-approximation a second one given by the union of polyhedrons. The overall computational complexity of our approach is comparable to the complexity of the most competitive available specialized algorithms for reachability analysis of linear systems using zonotopes or ellipsoids. The effectiveness of our approach is demonstrated on several examples.     

Non-singular locally optimal ellipsoidal approximation of the estimate of the states of linear systems

A problem which arises when estimating the attainability domains of linear dynamical systems by ellipsoids is investigated in a short time interval in the case when the initial position of the system in phase space is known precisely for some at least coordinates. A method is proposed which allows one to avoid problems associated with the degeneracy of the right-hand sides of the differential equations of the locally optimal ellipsoidal approximation. The mathematical meaning of these equations is made more precise in the case of the minimization of the phase volume. An example is given.     

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.     

On robust mean-variance portfolios

We derive closed-form portfolio rules for robust mean–variance portfolio optimization where the return vector is uncertain or the mean return vector is subject to estimation errors, both uncertainties being confined to an ellipsoidal uncertainty set. We consider different mean–variance formulations allowing short sales, and derive closed-form optimal portfolio rules in static and dynamic settings.     

Open-Loop Viable Control Under Uncertain Initial State Information

We consider the problem of open-loop viable control of a nonlinear system in Rⁿ in the case of a nonexactly known initial state. We characterize the family of those initial sets for which the problem is solvable. The characterization employs the notion of a contingent field to a given collection of sets introduced in the paper. It also involves an appropriate set-dynamic equation that describes the evolution of the state estimation within a prescribed collection of sets. An extension of the classical concept of viability kernel with respect to this set-dynamic equation is the key tool. We present an approximation scheme for the viability kernel which is numerically realizable in the case of low dimension and simple collections of sets chosen for state estimation (balls, ellipsoids, polyhedrons, etc.). As an application, we consider a viability differential game, where the uncertainty may enter also in the dynamics of the system as an input which is not known in advance. The control is then sought as a nonanticipative strategy depending on the uncertain input.     

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.     

Optimal ellipsoidal approximations around the Analytic center

We present a simple and self-contained proof for two-sided ellipsoidal approximations of certain convex setsS. The ellipsoids are centered at the minimum of the logarithmic barrier function forS. The ratio of inner and outer ellipsoid is optimal with respect to a self-concordance parameter.     

Optimization of the Hausdorff distance between sets in Euclidean space

Set approximation problems play an important role in many areas of mathematics and mechanics. For example, approximation problems for solvability sets and reachable sets of control systems are intensively studied in differential game theory and optimal control theory. In N.N. Krasovskii and A.I. Subbotin’s investigations devoted to positional differential games, one of the key problems was the problem of identification of solvability sets, which are maximal stable bridges. Since this problem can be solved exactly in rare cases only, the question of the approximate calculation of solvability sets arises. In papers by A.B. Kurzhanskii and F.L. Chernous’ko and their colleagues, reachable sets were approximated by ellipsoids and parallelepipeds.In the present paper, we consider problems in which it is required to approximate a given set by arbitrary polytopes. Two sets, polytopes A and B, are given in Euclidean space. It is required to find a position of the polytopes that provides a minimum Hausdorff distance between them. Though the statement of the problem is geometric, methods of convex and nonsmooth analysis are used for its investigation.One of the approaches to dealing with planar sets in control theory is their approximation by families of disks of equal radii. A basic component of constructing such families is best n-nets and their generalizations, which were described, in particular, by A.L. Garkavi. The authors designed an algorithm for constructing best nets based on decomposing a given set into subsets and calculating their Chebyshev centers. Qualitative estimates for the deviation of sets from their best n-nets as n grows to infinity were given in the general case by A.N. Kolmogorov. We derive a numerical estimate for the Hausdorff deviation of one class of sets. Examples of constructing best n-nets are given.     

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.     

A New Class of Theorems of the Alternative

An estimation problem for a random set that is a reachable domain of the Ito differential equation with respect to its initial data is considered. The Markov property of the reachable set in the space of closed sets is proved. For the purposes of numerical solution, a random initial set of the differential equation is approximated by a finite set on an integer multidimensional grid, and the differential equation is replaced by a multistep Markov chain. Examples are considered.     

New proof and some generalizations of the minimum principle in optimal control

An optimal control problem is reduced to the finite-dimensional problem of minimizing the terminal payoff over the intersection of the target set with the reachable set. The pointwise Pontryagin minimum principle is derived from two simple preliminary results: the first states that the intersection of two inseparable derived cones at a common point of two given sets is contained in the quasitangent cone (hence, in the contingent cone) to their intersection; the second identifies a derived cone to the reachable set. The standard variants of the minimum principle are easily generalized to problems defined by non-differentiable terminal payoffs on arbitrary target sets.