Geodesic
Numerical construction of Nash solutions in a two-player linear positional differential game in which the phase space has more than two dimensions
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 1, pp. 170-181 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The problem of constructing Nash solutions in a two-player non-zero-sum positional differential game with terminal payoffs, linear dynamics, and constraints on the players' controls in the form of convex polyhedra is considered. The formalization of the players' strategies and of the motions generated by them is based on the formalization and results of the theory of zero-sum positional differential games developed by N. N. Krasovskii and his scientific school. The problem of finding game solutions is reduced to solving nonstandard control problems. We propose algorithms for the construction of the algebraic sum and geometric difference of convex polyhedra. The algorithms extend the applicability domain of an earlier developed algorithm, which constructed Nash solutions, to problems with dynamics in phase spaces with more than two dimensions.
Keywords: non-zero-sum differential game, computational geometry, Nash solutions. 
@article{TIMM_2013_19_1_a16,
     author = {D. R. Kuvshinov},
     title = {Numerical construction of {Nash} solutions in a~two-player linear positional differential game in which the phase space has more than two dimensions},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {170--181},
     year = {2013},
     volume = {19},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a16/}
}
TY  - JOUR
AU  - D. R. Kuvshinov
TI  - Numerical construction of Nash solutions in a two-player linear positional differential game in which the phase space has more than two dimensions
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2013
SP  - 170
EP  - 181
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a16/
LA  - ru
ID  - TIMM_2013_19_1_a16
ER  - 
%0 Journal Article
%A D. R. Kuvshinov
%T Numerical construction of Nash solutions in a two-player linear positional differential game in which the phase space has more than two dimensions
%J Trudy Instituta matematiki i mehaniki
%D 2013
%P 170-181
%V 19
%N 1
%U http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a16/
%G ru
%F TIMM_2013_19_1_a16
D. R. Kuvshinov. Numerical construction of Nash solutions in a two-player linear positional differential game in which the phase space has more than two dimensions. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 1, pp. 170-181. http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a16/

[1] Krasovskii N. N., Subbotin A. I., Pozitsionnye differentsialnye igry, Nauka, M., 1974, 456 pp. | MR | Zbl

[2] Krasovskii N. N., Upravlenie dinamicheskoi sistemoi, Nauka, M., 1985, 520 pp. | MR

[3] Kleimenov A. F., Neantagonisticheskie pozitsionnye differentsialnye igry, Nauka, Ekaterinburg, 1993, 184 pp. | MR

[4] Kuvshinov D. R., “Algoritm chislennogo postroeniya reshenii po Neshu v pozitsionnoi differentsialnoi igre dvukh lits”, Vest. Udmurt. un-ta. Matematika. Mekhanika. Kompyuternye nauki, 2009, no. 3, 81–90

[5] Kleimenov A. F., Kuvshinov D. R., Osipov S. I., “Chislennoe postroenie reshenii Nesha i Shtakelberga v lineinoi neantagonisticheskoi pozitsionnoi differentsialnoi igre dvukh lits”, Tr. In-ta matematiki i mekhaniki UrO RAN, 15, no. 4, 2009, 120–133

[6] Computational Geometry Algorithms Library, URL: http://www.cgal.org/

[7] Chazelle B., “An optimal convex hull algorithm in any fixed dimension”, Discrete Comput. Geom., 10 (1993), 377–409 | DOI | MR | Zbl

[8] Isakova E. A., Logunova G. V., Patsko V. S., “Postroenie stabilnykh mostov v lineinoi differentsialnoi igre s fiksirovannym momentom okonchaniya”, Algoritmy i programmy resheniya lineinykh differentsialnykh igr, materialy po matematicheskomu obespecheniyu EVM, IMM UNTs AN SSSR, Sverdlovsk, 1984, 127–158

[9] Botkin N. D., Ryazantseva E. A., “Algoritm postroeniya mnozhestva razreshimosti v lineinoi differentsialnoi igre vysokoi razmernosti”, Tr. In-ta matematiki i mekhaniki UrO RAN, 2, 1992, 128–134 | MR | Zbl

[10] E. S. Polovinkin [i dr.], “Ob odnom algoritme chislennogo resheniya lineinykh differentsialnykh igr”, Mat. sb., 192:10 (2001), 95–122 | DOI | MR | Zbl

[11] Shorikov A. F., Minimaksnoe otsenivanie i upravlenie v diskretnykh dinamicheskikh sistemakh, Izd-vo Ural. un-ta, Ekaterinburg, 1997, 241 pp. | MR | Zbl

[12] Shorikov A. F., “Algoritm adaptivnogo minimaksnogo upravleniya dlya protsessa presledovaniya-ukloneniya v diskretnykh dinamicheskikh sistemakh”, Tr. In-ta matematiki i mekhaniki UrO RAN, 6, no. 2, Ekaterinburg, 2000, 515–535 | MR | Zbl

[13] Kamzolkin D. V., Metody resheniya nekotorykh klassov zadach optimalnogo upravleniya i differentsialnykh igr, Dis. $\dots$ kand. fiz.-mat. nauk, Moskva, 2005, 116 pp.

[14] Zarkh M. A., Ivanov A. G., “Postroenie funktsii tseny v lineinoi differentsialnoi igre s fiksirovannym momentom okonchaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 2, 1992, 140–155 | MR | Zbl

[15] Pontryagin L. S., “Lineinye differentsialnye igry, 2”, Dokl. AN SSSR, 175:4 (1967), 764–766 | Zbl

[16] Kuvshinov D. R., “Chislennoe postroenie reshenii po Neshu v pozitsionnoi differentsialnoi igre dvukh lits s fazovym prostranstvom razmernosti bolshe dvukh”, Teoriya upravleniya i matematicheskoe modelirovanie, Tr. konf., Izd-vo IzhGTU, Izhevsk, 2012, 33–35

[17] Rokafellar R., Vypuklyi analiz, Mir, M., 1973, 470 pp.

[18] Chernikov S. N., Lineinye neravenstva, Nauka, M., 1968, 488 pp. | MR | Zbl

[19] Hart P. E., Nilsson N. J., Raphael B., “A formal basis for the heuristic determination of minimum cost paths”, IEEE Trans. Syst. Science and Cybernetics, 4:2 (1968), 100–107 | DOI