A Stochastic Approximation Method for Reachability Computations

Abstract

We develop a grid-based method for estimating the probability that the trajectories of a given stochastic system will eventually enter a certain target set during a – possibly infinite – look-ahead time horizon. The distinguishing feature of the proposed methodology is that it rests on the approximation of the solution to stochastic differential equations by using Markov chains. From an algorithmic point of view, the probability of entering the target set is computed by appropriately propagating the transition probabilities of the Markov chain backwards in time starting from the target set during the time horizon of interest. We consider air traffic management as an application example. Specifically, we address the problem of estimating the probability that two aircraft flying in the same region of the airspace get closer than a certain safety distance and that an aircraft enters a forbidden airspace area. In this context, the target set is the set of unsafe configurations for the system, and we are estimating the probability that an unsafe situation occurs.