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.
In @cite_22 , an approximate dynamic programming technique is presented that, although still grid-based, enables a more efficient computation of the viability kernel. The viability kernel (similarly to @cite_4 ) is expressed as the zero sublevel set of the value function of the corresponding optimal control problem. It is assumed that the value function, which is a viscosity solution of a HJB PDE, is differentiable everywhere on the constraint set. The PDE is then discretized and the resulting value function is numerically computed on a grid using a function approximator such as the @math -nearest neighbor algorithm. The error-bounded approximation is not conservative (it is an over-approximation) but converges to the true viability kernel in the limit as the number of grid points goes to infinity.
@cite_4 @cite_22
2090501324 2130715863
Questions of reachability for continuous and hybrid systems can be formulated as optimal control or game theory problems, whose solution can be characterized using variants of the Hamilton-Jacobi-Bellman or Isaacs partial differential equations. The formal link between the solution to the partial differential equation and the reachability problem is usually established in the framework of viscosity solutions. This paper establishes such a link between reachability, viability and invariance problems and viscosity solutions of a special form of the Hamilton-Jacobi equation. This equation is developed to address optimal control problems where the cost function is the minimum of a function of the state over a specified horizon. The main advantage of the proposed approach is that the properties of the value function (uniform continuity) and the form of the partial differential equation (standard Hamilton-Jacobi form, continuity of the Hamiltonian and simple boundary conditions) make the numerical solution of the problem much simpler than other approaches proposed in the literature. This fact is demonstrated by applying our approach to a reachability problem that arises in flight control and using numerical tools to compute the solution. Viability theory considers the problem of maintaining a system under a set of viability constraints. The main tool for solving viability problems lies in the construction of the viability kernel, defined as the set of initial states from which there exists a trajectory that remains in the set of constraints indefinitely. The theory is very elegant and appears naturally in many applications. Unfortunately, the current numerical approaches suffer from low computational efficiency, which limits the potential range of applications of this domain. In this paper we show that the viability kernel is the zero-level set of a related dynamic programming problem, which opens promising research directions for numerical approximation of the viability kernel using tools from approximate dynamic programming. We illustrate the approach using k-nearest neighbors on a toy problem in two dimensions and on a complex dynamical model for anaerobic digestion process in four dimensions