Stochastic reachability of a target tube: Theory and computation
For control theorists and engineers, this work provides a theoretically grounded, scalable method for probabilistic safety guarantees in stochastic systems, though it is incremental as it extends existing reachability concepts.
The paper addresses the stochastic reachability problem for constrained dynamical systems with stochastic uncertainty, aiming to maximize the probability of staying within time-varying state constraints. It provides theoretical conditions for the stochastic reach set and proposes a scalable, grid-free algorithm that computes polytopic underapproximations and synthesizes open-loop controllers, outperforming existing verification tools on numerical examples.
Probabilistic guarantees of safety and performance are important in constrained dynamical systems with stochastic uncertainty. We consider the stochastic reachability problem, which maximizes the probability that the state remains within time-varying state constraints (i.e., a ``target tube''), despite bounded control authority. This problem subsumes the stochastic viability and terminal hitting-time stochastic reach-avoid problems. Of special interest is the stochastic reach set, the set of all initial states from which it is possible to stay in the target tube with a probability above a desired threshold. We provide sufficient conditions under which the stochastic reach set is closed, compact, and convex, and provide an underapproximative interpolation technique for stochastic reach sets. Utilizing convex optimization, we propose a scalable and grid-free algorithm that computes a polytopic underapproximation of the stochastic reach set and synthesizes an open-loop controller. This algorithm is anytime, i.e., it produces a valid output even on early termination. We demonstrate the efficacy and scalability of our approach on several numerical examples, and show that our algorithm outperforms existing software tools for verification of linear systems.