Complementarity-based reformulation and numerical method for solving pursuit-evasion differential games

Pursuit-evasion differential games are challenging to solve both analytically and numerically, particularly as the problem dimensionality increases. These games involve bounded control inputs for each player, reflecting the limitations commonly present in real-world systems. In this study, we propose the D-gap penalty method as a new numerical reformulation for solving pursuit-evasion differential games. The original problem is first reformulated as a differential complementarity system (DCS). The D-gap penalty method then penalizes the complementarity constraints, transforming the DCS into a nonlinear programming (NLP) problem, which is then solved using an off-the-shelf NLP solver. To evaluate the accuracy, computational efficiency, and complementarity violations, we compare the proposed method with the conventional Fischer-Burmeister penalty method across various pursuit-evasion scenarios. In almost all tested scenarios, the D-gap penalty method achieved shorter computation times and better trajectory performance, even as the problem complexity increased.