Time and Memory-Efficient Computation of Hamilton-Jacobi Reachable Sets Based on a Level Set Method Employing Adaptive Grids

Formal verification of dynamic control systems often involves reachability analysis to ensure safety and performance characteristics. Hereby, Hamilton-Jacobi-based methods are beneficial as they can be applied to non-linear, continuous systems under the influence of bounded disturbances. Furthermore, they can consider input- and state constraints. These benefits come with the computational effort of solving a Hamilton-Jacobi partial differential equation. State-of-the-art methods numerically determine a viscosity solution at the vertices of a static grid that is used to discretize the state space. This becomes particularly costly if the reachable set propagates fast and needs to be determined precisely as this requires a grid of many vertices. This contribution proposes a method that computes the solution successively on small adaptive grids instead of on one static grid to reduce the computational effort of Hamilton-Jacobi reachability analysis. Using the proposed method, changes between grids can be performed in an outer or inner approximative manner. The performance of the proposed method is demonstrated in a numerical example computing a forward reachable set of a Dubins car model. ... mehrWhile increasing the accuracy of the resulting set, the method proposed saves 73% of computation time, 76% of average memory usage, and 43% of maximum memory usage in the presented scenario.