A Hopf-Lax Formula in Hamilton–Jacobi Analysis of Reach-Avoid Problems

Abstract

Reach-avoid problems compute control laws under which a dynamic system can reach a desired set of states while avoiding another set. They are used in solving a variety of problems, such as goal-seeking and obstacle avoidance. Hamilton-Jacobi analysis provides a method for solving reach-avoid problems, through a corresponding Hamilton-Jacobi (HJ) equation. Although the HJ equation can be utilized for a general class of problems, computing the solution of the HJ equation by grid-based methods has exponential complexity in the dimension of the continuous state. To alleviate this complexity, this letter presents a generalized version of the Hopf-Lax formula and proves its correctness for solving the reach-avoid problem. The method does not rely on discretization of the state space. A numerical algorithm for the proposed Hopf-Lax formula is presented, and demonstrated using a 12D vehicle example.