HJ-Gauss: A Monte-Carlo HJ Reachability Scheme

Abstract

Backward reachable sets or tubes (BRS/Ts), evaluated with grid-based level-set methods over viscous Hamilton-Jacobi (HJ) equations, furnish principled reachability certificates for learning-enabled control. However, these methods incur an $O(M^n)$ memory cost, where $M$ is the number of grid points for every $n$-state dimension, which has precluded their applications in high-dimensional physical phenomena. Towards scalable reachability analysis, we propose a frozen-coefficient Picard iterative Gaussian sampling scheme: with a Cole-Hopf-type transformation, the HJ PDE effectively reduces to a sequence of linear heat equations, whose values are then iteratively recovered via Gaussian heat-kernel expectations. In this sentiment, Monte Carlo roll-outs over Gaussian densities ultimately recover the (approximate) HJ value and its spatial gradient. Ours is a storage- and discretization-free algorithm whose memory footprint scales (for \textit{i.i.d} samples, $N$) as $N\cdot n$; we show that sampling is a polynomial power law in $N$ and provide a conditional linear convergence analysis to the \textit{consistent} viscosity solution. Furthermore, we provide a quasilinearization defect per iteration between frozen coefficient samples to make our HJ sampling scheme tight. Our theoretical machinery is rigorously benchmarked on rocket launch and Dubins pursuit-evasion (P-E) games over Holm-Bonferroni-informed experiments: for a $45D$-multi-rocket launch P-E game, we find an \textit{almost zero} Picard residual floor. Certifying the safety of \textbf{$100,000$} European starlings (\textit{sturnus vulgaris}) in murmurations over their collective value functions reveals vacuole nucleation, cordon formation, and flock splitting on the resulting BRT zero-levelset phase topology as predator attacks evolve , demonstrating the scalability of our approach to large-scale multi-agent systems.