Juegos dinámicos de persecución y evasión

Abstract

Pursuit-Evasion games settle the foundations for Dynamic Games, a very active area in these days due to its great applicative potential. The Hamstrung Squad Car and the Homicidal Chaffeur are two zero-sum, two-player Pursuit-Evasion games with complete information, that this work studies in order to formulate and implement a numeric solution based on Dynamic Programming for this kind of games. The resulting algorithms are implemented using Matlab and have complexity of polynomial order, depending directly on the dimension of the problem and the number of directions that players can use. These algorithms can be reused to solve similar problems.

Los juegos de Persecución y Evasión sentaron las bases de los Juegos Dinámicos, un área muy activa en estos tiempos debido a su gran potencial aplicativo. La Patrulla Restringida y el Chofer Homicida son dos juegos de Persecución y Evasión de suma cero de dos jugadores con información completa, que se estudian en el presente trabajo para poder plantear e implementar una solución numérica basada en Programación Dinámica para este tipo de juegos. Los algoritmos resultantes son implementados usando Matlab y son de complejidad de orden polinómico, dependiente directamente de la dimensión del problema y el número de direcciones que los jugadores pueden usar. Estos algoritmos pueden ser reusados para resolver problemas similares.