In this paper, we propose a new method for ensuring formally that a controlled trajectory stay inside a given safety set S for a given duration T. Using a finite gridding X of S, we first synthesize, for a subset of initial nodes x of X , an admissible control for which the Euler-based approximate trajectories lie in S at t @math [0,T]. We then give sufficient conditions which ensure that the exact trajectories, under the same control, also lie in S for t @math [0,T], when starting at initial points 'close' to nodes x. The statement of such conditions relies on results giving estimates of the deviation of Euler-based approximate trajectories, using one-sided Lipschitz constants. We illustrate the interest of the method on several examples, including a stochastic one.
Problem P2: In the work of @cite_11 @cite_25 , the authors pursue an objective similar to ours: providing a (finite time-horizon) optimal control procedure with a formal guarantee of constraint satisfaction (safety). However they do not use SL-schemes, but perform a reachability analysis based on over-approximative state set representations ( zonotopes , cf. @cite_8 @cite_17 ).
@cite_8 @cite_17 @cite_25 @cite_11
2042835403 2154136656 2080813827 2048738839
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. We describe a framework for analyzing probabilistic reachability and safety problems for discrete time stochastic hybrid systems within a dynamic games setting. In particular, we consider finite horizon zero-sum stochastic games in which a control has the objective of reaching a target set while avoiding an unsafe set in the hybrid state space, and a rational adversary has the opposing objective. We derive an algorithm for computing the maximal probability of achieving the control objective, subject to the worst-case adversary behavior. From this algorithm, sufficient conditions of optimality are also derived for the synthesis of optimal control policies and worst-case disturbance strategies. These results are then specialized to the safety problem, in which the control objective is to remain within a safe set. We illustrate our modeling framework and computational approach using both a tutorial example with jump Markov dynamics and a practical application in the domain of air traffic management. In this work, probabilistic reachability over a finite horizon is investigated for a class of discrete time stochastic hybrid systems with control inputs. A suitable embedding of the reachability problem in a stochastic control framework reveals that it is amenable to two complementary interpretations, leading to dual algorithms for reachability computations. In particular, the set of initial conditions providing a certain probabilistic guarantee that the system will keep evolving within a desired 'safe' region of the state space is characterized in terms of a value function, and 'maximally safe' Markov policies are determined via dynamic programming. These results are of interest not only for safety analysis and design, but also for solving those regulation and stabilization problems that can be reinterpreted as safety problems. The temperature regulation problem presented in the paper as a case study is one such case. Consider a system governed by the time-dependent Schrodinger equation initialized in its ground state. When subjected to weak (size e) parametric forcing by an “ionizing field” (time-varying), the state decays with advancing time due to coupling of the bound state to radiation modes. The decay rate of this metastable state is governed by Fermi’s golden rule, Γ[V], which depends on the potential V and the details of the forcing. We pose the following potential design problem: find Vopt which minimizes Γ[V] (maximizes the lifetime of the state) over an admissible class of potentials with fixed spatial support. We formulate this problem as a constrained optimization problem and prove that an admissible optimal solution exists. Then, using quasi-Newton methods, we compute locally optimal potentials. These have the structure of a truncated periodic potential with a localized defect. In contrast to optimal structures for other spectral optimization problems, our optimizing potentials appear to be interior point...