Lion and Man game and fixed point free maps

Olga O. Yufereva

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 9 (2017) no. 2, pp. 105-120.

Résumé

This work is related with pursuit-evasion game where Lion is the pursuer and Man is the evader. We suppose that both players move in a metric space, have equal maximum speeds and complete information about the location of each other. We say that Man wins if he can escape a capture with non-zero radius; more precisely if there exists a positive number p and a non-anticipative strategy for some players' initial positions, that let him always be out of Lion's p-neighbourhood. We study sufficient conditions of the existence of Man's winning strategy. In this way we use the metric properties of space (mainly geodesics' behavior and fixed-point free maps). The technique requires neither convexity nor finite dimension of a space.

Détail

Keywords: pursuit-evasion game, lion and man game, fixed point, geodesic loop.

Bibliographie

[1] Blagodatskikh A. I., Petrov N. N., Konfliktnoe vzaimodeistvie grupp upravlyaemykh ob'ektov, Udmurtskii universitet, Izhevsk, 2009

[2] Zelikin M. I., “Ob odnoi differentsialnoi igre s nepolnoi informatsiei”, Dokl. AN SSSR, 202:5 (1972), 998–1000 | Zbl

[3] Ivanov R. P., Ledyaev Yu. S., “Optimalnost vremeni presledovaniya v differentsialnoi igre mnogikh ob'ektov s prostym dvizheniem”, Trudy Matematicheskogo instituta imeni V. A. Steklova, 158, 1981, 87–97 | Zbl

[4] Kovshov A. M., “Strategii parallelnogo sblizheniya v igre prostogo presledovaniya na sfere. Geodezicheskoe sblizhenie”, Matematicheskaya teoriya igr i ee prilozheniya, 1:4 (2009), 41–62

[5] Krasovskii N. N., Igrovye zadachi o vstreche dvizhenii, 1970

[6] Krasovskii N. N., Subbotin A. I., Pozitsionnye differentsialnye igry, 1974

[7] Krasovskii N. N., Upravlenie dinamicheskoi sistemoi, 1985

[8] Lokutsievskii L. V., “Optimalnyi veroyatnostnyi poisk”, Matematicheskii sbornik, 202:5 (2011), 77–100 | DOI | Zbl

[9] Neiman D., Morgenshtern O., Teoriya igr i ekonomicheskoe povedenie, Nauka, M., 1970

[10] Petrov N. N., “Kvazilineinye konfliktno-upravlyaemye protsessy s dopolnitelnymi ogranicheniyami”, Prikladnaya matematika i mekhanika, 57:6 (1993), 61–68 | Zbl

[11] Petrosyan L. A., “Differentsialnye igry na vyzhivanie so mnogimi uchastnikami”, Dokl. AN SSSR, 161:2 (1965), 285–287 | Zbl

[12] Petrosyan L. A., Tomskii G. V., “Dinamicheskie igry s polnoi informatsiei i ikh prilozheniya k igram s nepolnoi informatsiei”, Differentsialnye uravneniya, 18:4 (1982), 593–599 | Zbl

[13] Pontryagin L. S., Mischenko E. F., “Zadacha ob ubeganii odnogo upravlyaemogo ob'ekta ot drugogo”, Dokl. AN SSSR, 189:4 (1969), 721–723 | Zbl

[14] Pontryagin L. S., “Lineinye differentsialnye igry ubeganiya”, Trudy Matematicheskogo instituta imeni V. A. Steklova, 112, 1971, 30–63 | Zbl

[15] Pontryagin L. S., “Matematicheskaya teoriya optimalnykh protsessov i differentsialnye igry”, Trudy Matematicheskogo instituta imeni V. A. Steklova, 169, 1985, 119–158 | Zbl

[16] Pshenichnyi B. N., O zadache presledovaniya, Kibernetika, M., 1967

[17] Pshenichnyi B. N., “Struktura differentsialnykh igr”, Dokl. AN SSSR, 184:2 (1969), 285–287 | Zbl

[18] Pshenichnyi B. N., Chikrii A. A., “Zadacha ob uklonenii ot vstrechi v differentsialnykh igrakh”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 14:6 (1974), 1416–1426

[19] Pshenichnyi B. N., Prostoe presledovanie neskolkimi ob'ektami, Kibernetika, M., 1976

[20] Chernousko F. L., “O differentsialnykh igrakh s zapazdyvaniem informatsii”, Dokl. AN SSSR, 188:4 (1969), 766–769 | Zbl

[21] Chernousko F. L., Melikyan A. A., Igrovye zadachi upravleniya i poiska, Nauka, M., 1978

[22] Alexander S., Bishop R., Ghrist R., “Total curvature and simple pursuit on domains of curvature bounded above”, Geometriae Dedicata, 149:1 (2010), 275–290 | DOI | MR | Zbl

[23] Barmak J. A., Lion and man in non-metric spaces, 2017, arXiv: 1703.01480

[24] Bollobas B., Leader I., Walters M., Lion and man — can both win?, Israel Journal of Mathematics, 189:1 (2012), 267–286 | DOI | MR | Zbl

[25] Bramson M., Burdzy K., Kendall W. S., “Rubber bands, pursuit games and shy couplings”, Proceedings of the London Mathematical Society, 2014, 121–160 | DOI | MR | Zbl

[26] Chung T. H., Hollinger G. A., Isler V., “Search and pursuit-evasion in mobile robotics”, Autonomous robots, 31:4 (2011), 299–316 | DOI

[27] Isaacs R., Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization, Courier Corporation, 1999 | MR

[28] Kumkov S. S., Le Menec S., Patsko V. S., “Zero-Sum Pursuit-Evasion Differential Games with Many Objects: Survey of Publications”, Dynamic Games and Applications, 2016, 1–25 | MR

[29] Littlewood J. E., A mathematician's miscellany, Methuen, London, 1953 | MR | Zbl

[30] Melikyan A. A., “The Structure of the Value Function in Pursuit-Evasion Games on Surfaces of Revolution”, Cybernetics and Systems Analysis, 38:3 (2002), 444–452 | DOI | MR | Zbl

[31] Roxin E., “Axiomatic approach in differential games”, Journal of Optimization Theory and Applications, 3:3 (1969), 153–163 | DOI | MR | Zbl

[32] Ryll-Nardzewski C., “A theory of pursuit and evasion”, Advances in game theory, 1962, 113–126 | MR

[33] Tovar B., LaValle S. M., “Visibility-based pursuit-evasion with bounded speed”, The International Journal of Robotics Research, 27:11–12 (2008), 1350–1360 | DOI | MR

[34] Yufereva O., Lion and Man Game in Compact Spaces, 2016, arXiv: 1609.01897