Numerical method for solving time-optimal differential games with lifeline

Natal'ya V. Munts ; Sergei S. Kumkov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 10 (2018) no. 3, pp. 48-75.

Résumé

This paper discusses classic time-optimal differential games with lifeline. In such games, together with a target set, whereto the first player tries to guide the system, another set is chosen (namely, it is called lifeline), with reaching which the second player wins. Numerical method solving time-optimal games with lifeline is suggested. This method constructs the value function as a viscosity solution of the corresponding boundary value problem for the Hamilton–Jacobi equation. A convergence of the method is proved.

Détail

Keywords: numerical methods, time-optimal differential games with lifeline, value function, Hamilton–Jacobi equations, viscosity solutions.

Bibliographie

[1] Aizeks R., Differentsialnye igry, Mir, M., 1967, 480 pp.

[2] Dutkevich Yu. G., Petrosyan L. A., “Igra s «liniei zhizni». Sluchai $l$-zakhvata”, Vestn. Leningr. un-ta, 1969, no. 13, 31–38

[3] Krasovskii N. N., Subbotin A. I., Pozitsionnye differentsialnye igry, Nauka, M., 1974

[4] Munts N. V., Kumkov S. S., “O sovpadenii minimaksnogo resheniya i funktsii tseny igry bystrodeistviya s liniei zhizni”, Trudy Instituta matematiki i mekhaniki UrO RAN, 24, no. 2, UrO RAN, Ekaterinburg, 2018, 200–214

[5] Petrosyan L. A., “Dispersionnye poverkhnosti v odnom semeistve igr presledovaniya”, Doklady Akademii nauk Armyanskoi SSR, 43:4 (1966), 193–197 | Zbl

[6] Petrosyan L. A., Differentsialnye igry presledovaniya, Izdatelstvo LGU, L., 1977

[7] Subbotin A. I., Obobschennye resheniya uravnenii v chastnykh proizvodnykh pervogo poryadka. Perspektivy dinamicheskoi optimizatsii, Institut kompyuternykh issledovanii, M.–Izhevsk, 2003

[8] Bardi M., Capuzzo-Dolcetta I., Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, Boston, 1997 | MR | Zbl

[9] Bardi M., Falcone M., Soravia P., “Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions”, Stochastic and Differential Games, Annals of the International Society of Dynamic Games, 6, eds. M. Bardi, T. Parthasarathy, T. E. S. Raghavan, Birkhäuser, Boston, 1999, 105–175 | MR

[10] Barles G., Perthame B., “Discontinuous solutions of deterministic optimal stopping time problems”, RAIRO Model. Math. Anal., 21 (1987), 557–579 | DOI | MR | Zbl

[11] Barles G., Solutions de viscosite des equations de Hamilton–Jacobi, Mathematiques et Applications, 17, Springer, Paris, 1994 | MR | Zbl

[12] Cardaliaguet P., Quincampoix M., Saint-Pierre P., “Some algorithms for differential games with two players and one target”, RAIRO — Modélisation mathématique et analyse numérique, 28:4 (1994), 441–461 | DOI | MR | Zbl

[13] Cardaliaguet P., Quincampoix M., Saint-Pierre P., “Set-Valued Numerical Analysis for Optimal Control and Differential Games”, Annals of the International Society of Dynamic Games, 4 (1999), 177–247 | MR | Zbl

[14] Cardaliaguet P., Quincampoix M., Saint-Pierre P., “Pursuit differential games with state constraints”, SIAM J. Control and Optimization, 39:5 (2001), 1615–1632 | DOI | MR | Zbl

[15] Cardaliaguet P., Quincampoix M., Saint-Pierre P., “Differential Games Through Viability Theory: Old and Recent Results”, Annals of the International Society of Dynamic Games, 9 (2007), 3–35 | DOI | MR | Zbl

[16] Crandall M. G., Evans L. C., Lions P.-L., “Some properties of viscosity solutions of Hamilton-Jacobi equations”, Transactions of the American Mathematical Society, 282:2 (1984), 487–502 | DOI | MR | Zbl

[17] Crandall M. G., Ishii H., Lions P. L., “User's guide to viscosity solutions of second order partial differential equations”, Bull. Amer. Math. Soc., 27 (1992), 1–67 | DOI | MR | Zbl

[18] Isaacs R., Differential Games, John Wiley and Sons, New York, 1965 | MR | Zbl

[19] Krasovskii N. N., Subbotin A. I., Game-Theoretical Control Problems, Springer-Verlag, New York, 1988 | MR | Zbl

[20] Munts N. V., Kumkov S. S., “Existence of value function in time-optimal game with life line (Suschestvovanie funktsii tseny v igre bystrodeistviya s liniei zhizni)”, Proceedings of the 47th International Youth School-conference «Modern Problems in Mathematics and its Applications», Yekaterinburg, Russia, January 31 – February 6, 2016, 94–99

[21] Patsko V. S., Turova V. L., “Level Sets of the Value Function in Differential Games with the Homicidal Chauffeur Dynamics”, International Game Theory Review, 3:1 (2001), 67–112 | DOI | MR | Zbl

[22] Patsko V. S., Turova V. L., Numerical Study of Differential Games with the Homicidal Chauffeur Dynamics, Institute of mathematics and mechanics, UrB of RAS, Ekaterinburg, 2000 sector3.imm.uran.ru/preprint2000_01/preprint2000.pdf

[23] Petrosjan L. A., “A family of differential survival games in the space $\mathbb R^{n}$”, Soviet Math. Dokl., 1965, no. 6, 377–380 | MR