Computing the viability kernel is key in providing guarantees of safety and proving existence of safety-preserving controllers for constrained dynamical systems. Current numerical techniques that approximate this construct suffer from a complexity that is exponential in the dimension of the state. We study conditions under which a linear time-invariant (LTI) system can be suitably decomposed into lower dimensional subsystems so as to admit a conservative computation of the viability kernel in a decentralized fashion in subspaces. We then present an isomorphism that imposes these desired conditions, most suitably on two-time-scale systems. Decentralized computations are performed in the transformed coordinates, yielding a conservative approximation of the viability kernel in the original state space. Significant reduction of complexity can be achieved, allowing the previously inapplicable tools to be employed for treatment of higher dimensional systems. We show the results on two examples including a 6-D system.
 Using only the existence and uniqueness of trajectories for a generic dynamic system with inputs, we define and examine eight types of forward and backward reachability constructs. If the input is treated in a worst-case fashion, any forward or backward reach set or tube can be used for safety analysis, but if the input is treated in a best-case fashion only the backward reach tube always provides the correct results. Fortunately, forward and backward algorithms can be exchanged if well-posed reverse time trajectories can be defined. Unfortunately, backward reachability constructs are more likely to suffer from numerical stability issues, especially in systems with significant contraction--the very systems where forward simulation and reachability are most effective. This report describes the calculation of the reach sets and tubes for linear control systems with time-varying coefficients and hard bounds on the controls through tight external and internal ellipsoidal approximations. These approximating tubes touch the reach tubes from outside and inside respectively at every point of their boundary so that the surface of the reach tube is totally covered by curves that belong to the approximating tubes. The proposed approximation scheme induces a very small computational burden compared with other methods of reach set calculation. In particular such approximations may be expressed through ordinary differential equations with coefficients given in explicit analytical form. This yields exact parametric representation of reach tubes through families of external and internal ellipsoidal tubes. The proposed techniques, combined with calculation of external and internal approximations for intersections of ellipsoids, provide an approach to reachability problems for hybrid systems. 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. Abstract While a number of Lagrangian algorithms to approximate reachability in dozens or even hundreds of dimensions for systems with linear dynamics have recently appeared in the literature, no similarly scalable algorithms for approximating viable sets have been developed. In this paper we describe a connection between reachability and viability that enables us to compute the viability kernel using reach sets. This connection applies to any type of system, such as those with nonlinear dynamics and or non-convex state constraints; however, here we take advantage of it to construct three viability kernel approximation algorithms for linear systems with convex input and state constraint sets. We compare the performance of the three algorithms and demonstrate that the two based on highly scalable Lagrangian reachability–those using ellipsoidal and support vector set representations–are able to compute the viability kernel for linear systems of larger state dimension than was previously feasible using traditional Eulerian methods. Our results are illustrated on a 6-dimensional pharmacokinetic model and a 20-dimensional model of heat conduction on a lattice. We present a scalable reachability algorithm for hybrid systems with piecewise affine, non-deterministic dynamics. It combines polyhedra and support function representations of continuous sets to compute an over-approximation of the reachable states. The algorithm improves over previous work by using variable time steps to guarantee a given local error bound. In addition, we propose an improved approximation model, which drastically improves the accuracy of the algorithm. The algorithm is implemented as part of SpaceEx, a new verification platform for hybrid systems, available at spaceex.imag.fr. Experimental results of full fixed-point computations with hybrid systems with more than 100 variables illustrate the scalability of the approach.   We present a connection between the viability kernel and maximal reachable sets. Current numerical schemes that compute the viability kernel suffer from a complexity that is exponential in the dimension of the state space. In contrast, extremely efficient and scalable techniques are available that compute maximal reachable sets. We show that under certain conditions these techniques can be used to conservatively approximate the viability kernel for possibly high-dimensional systems. We demonstrate the results on two practical examples, one of which is a seven-dimensional problem of safety in anesthesia. 