Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions

We present a class of numerical schemes for the Isaacs equation of pursuit-evasion games. We consider continuous value functions, where the solution is interpreted in the viscosity sense, as well as discontinuous value functions, where the notion of viscosity envelope-solution is needed. The convergence of the approximation scheme to the value function of the game is proved in both cases. A priori estimates of the convergence in L∞ are established when the value function is Hölder continuous. We also treat problems with state constraints and discuss several issues concerning the implementation of the approximation scheme, the synthesis of approximate feedback controls, and the approximation of optimal trajectories. The efficiency of the algorithm is illustrated by a number of numerical tests, either in the case of one player (i.e., minimum time problem) or for some 2-players games.