Fully-Discrete Schemes for the Value Function of Pursuit-Evasion Games with State Constraints

We deal with the approximation of a generalized Pursuit-Evasion game with state constraints. Our approach is based on the Dynamic Programming principle and on the characterization of the lower value v of the game via the Isaacs equation. Our main result is the convergence of the fully-discrete scheme for Pursuit-Evasion games under continuity assumptions on v and some geometric assumptions on the dynamics and on the set of constraints (Omega) over bar. We also analyze the Tag-Chase game in a bounded convex domain when the two players have the same velocity and we prove that in the constrained case the time of capture is finite. Some hints to improve the efficiency of the algorithm on serial and parallel machines will be also given. An extensive numerical section will show the accuracy of our method for the approximation of the value function v and of the corresponding optimal trajectories in a number of different configurations.