Probabilistic Occupancy Function and Sets Using Forward Stochastic Reachability for Rigid-Body Dynamic Obstacles
For roboticists and control engineers, this work offers a rigorous, computationally efficient framework for probabilistic collision avoidance with dynamic obstacles, though it is an incremental extension of existing reachability methods.
This paper introduces a forward stochastic reachability approach to compute probability-weighted keep-out sets for safe navigation among rigid-body obstacles with stochastic dynamics. The method uses Fourier transforms and computational geometry to characterize obstacle stochasticity without grids or recursion, and provides convexity guarantees and efficient approximation algorithms.
We present theory and algorithms for the computation of probability-weighted "keep-out" sets to assure probabilistically safe navigation in the presence of multiple rigid body obstacles with stochastic dynamics. Our forward stochastic reachability-based approach characterizes the stochasticity of the future obstacle states in a grid-free and recursion-free manner, using Fourier transforms and computational geometry. We consider discrete-time Markovian switched systems with affine parameter-varying stochastic subsystems (DMSP) as the obstacle dynamics, which includes Markov jump affine systems and discrete-time affine parameter-varying stochastic systems (DPV). We define a probabilistic occupancy function, to describe the probability that a given state is occupied by a rigid body obstacle with stochastic dynamics at a given time; keep-out sets are the super-level sets of this occupancy function. We provide sufficient conditions that ensure convexity and compactness of these keep-out sets for DPV obstacle dynamics. We also propose two computationally efficient algorithms to overapproximate the keep-out sets --- a tight polytopic approximation using projections, and an overapproximation using Minkowski sum. For DMSP obstacle dynamics, we compute a union of convex and compact sets that covers the potentially non-convex keep-out set. Numerical simulations show the efficacy of the proposed algorithms for a modified version of the classical unicycle dynamics, modeled as a DMSP.