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.
Complexity reduction for viability and minimal reachability has been addressed by many researchers. A projection scheme in @cite_5 based on Hamilton-Jacobi (HJ) partial differential equations (PDEs) over-approximates the projection of the true minimal reachable tube in lower dimensional subspaces, with the unmodeled dimensions treated as a disturbance. Similarly, @cite_38 decomposes a full-order nonlinear system into either disjoint or overlapping subsystems and solves multiple HJ PDEs in lower dimensions. More recently, a mixed implicit-explicit HJ is presented in @cite_25 for nonlinear systems whose state vector contains states that are integrators of other states. The complexity of this new formulation is linear in the number of integrator states, while still exponential in the dimension of the rest of the states. These techniques assume that the system itself presents a certain structure that can be exploited.
@cite_5 @cite_25 @cite_38
315739085 2067202372 1542232783
In earlier work, we showed that the set of states which can reach a target set of a continuous dynamic game is the zero sublevel set of the viscosity solution of a time dependent Hamilton-Jacobi-Isaacs (HJI) partial differential equation (PDE). We have developed a numerical tool—based on the level set methods of Osher and Sethian—for computing these sets, and we can accurately calculate them for a range of continuous and hybrid systems in which control inputs are pitted against disturbance inputs. The cost of our algorithm, like that of all convergent numerical schemes, increases exponentially with the dimension of the state space. In this paper, we devise and implement a method that projects the true reachable set of a high dimensional system into a collection of lower dimensional subspaces where computation is less expensive. We formulate a method to evolve the lower dimensional reachable sets such that they are each an overapproximation of the full reachable set, and thus their intersection will also be an overapproximation of the reachable set. The method uses a lower dimensional HJI PDE for each projection with a set of disturbance inputs augmented with the unmodeled dimensions of that projection's subspace. We illustrate our method on two examples in three dimensions using two dimensional projections, and we discuss issues related to the selection of appropriate projection subspaces. The solution of a particular Hamilton-Jacobi (HJ) partial differential equation (PDE) provides an implicit representation of reach sets and tubes for continuous systems with nonlinear dynamics and can treat inputs in either worst-case or best-case fashion; however, it can rarely be determined analytically and its numerical approximation typically requires computational resources that grow exponentially with the state space dimension. In this paper we describe a new formulation - also based on HJ PDEs - for reach sets and tubes of systems where some states are terminal integrators: states whose evolution can be written as an integration over time of the other states. The key contribution of this new mixed implicit explicit (MIE) scheme is that its computational cost is linear in the number of terminal integrators, although still exponential in the dimension of the rest of the state space. Application of the new scheme to four examples of varying dimension provides empirical evidence of its considerable improvement in computational speed. In this paper, we present a method to decompose the problem of computing the backward reachable set for a dynamic system in a space of a given dimension, into a set of computational problems involving level set functions, each defined in a lower dimensional (subsystem) space. This allows the potential for great reduction in computation time. The overall system is considered as an interconnection of either disjoint or overlapping subsystems. The projection of the backward reachable set into the subsystem spaces is over-approximated by a level set of the corresponding subsystem level set function. It is shown how this method can be applied to two-player differential games. Finally, results of the computation of polytopic over-approximations of the unsafe set for the two aircraft conflict resolution problem are presented.