Title: A Decomposition Method for a Class of Pursuit-Evasion Games

Authors: Tuomas Raivio, Harri Ehtamo and Raimo P. Hämäläinen

Date: March 1998

Status: Symposium on Differential Games and Applications, Kanagawa, Japan, December 16-18, 1996, Vol. 2, pp. 784-795.


The paper presents a new computational approach for a class of pursuit-evasion games of degree. The saddle point problem is decomposed into two subproblems that are solved by turns iteratively. The subproblems are optimal control problems that can be solved efficiently using discretization and nonlinear programming techniques. Hence it is not necessary to supply an initial guess of the adjoint variables or a hypothesis on the switching structureof the solution. Furthermore, in the presented approach the numerical differentiation of the payoff is avoided. We test the algorithm with different numerical examples and compare the results with solutions obtained by an indirect method. In the test examples the method converges rapidly from a rough initial guess, and the results coincide well with the reference solutions.