Visualization of pursuit differential game on a plane

Abstract

This paper is dedicated to differential pursuit games. In the theory of dynamic games, a number of methods have been developed that provide a guaranteed result. The scheme of the Method of Resolving Functions is applied in the work. Sufficient conditions to end of the game have been found. For the task of simple pursuit, the visualization of the trajectory of the movements of the group of pursuers and the fugitive on the plane is realized. To do this, a software product was created in the Python programming language. This software product is a prototype of a "pursuer-evader" simulation system that can be used to select controls in pursuit tasks. Two cases of fugitive control selection were considered in the development. In the first one, the control of the fugitive is based on the following algorithm: the fugitive determines the nearest pursuer in terms of the Euclidean norm; the fugitive builds his control on the beam, which comes from the position of the nearest pursuer and crosses the position of the fugitive, in the direction opposite to the pursuer with maximum speed. In the second case, the control of the fugitive is set by the user. The visualization of the trajectory of one pursuer and one evader on the plane was realized for the Pontryagin's checking example of a game problem with simple motions. The results have a graphical presentation. The result showed the coincidence of the estimated time and the actual end time of the game.

Keywords

• dynamic games
• conflict-controlled processes
• differential games
• pursuit games
• group pursuit games

-

In the theory of dynamic games (conflict-controlled processes and differential games), along with Isaacs ideology [ 1 ], a number of methods have been developed that provide a guaranteed result. Such methods include, in particular, the first direct method of L.S. Pontryagin [ 2, 3 ], the method of extreme aiming of M.M. Krasovskii [ 4 ] and the method of resolving functions of A.O. Chikrii [ 5–15 ]. In this paper, the last method will be used, which gives a theoretical justification for the classical rule of parallel pursuit and the method of convergence by the beam. The method scheme for differential-difference games is developed in works [ 16–19 ]. In [ 20–22 ], the problem of rapprochement for a group of pursuers and a single evader is considered. The scheme of the method of resolving functions for differential-difference systems of neutral type was developed in works [ 25-27 ]. differential equations: where ables.

Let 0

drical form. i.e. [ 23 ]. A modification of the method is proposed for objects with different inertia in [ 24 ]. Game problems of convergence in case of failure of control devices are considered in Consider the motion of a controlled object, which is described by a system of , , ∈ , 1, , ∈ , ∈ are square constant matrices of order , ⋯ , and nonempty compacts sets, , : → , are jointly continuous in their vari° be the initial condition of the process (1). The terminal set has cylin⋃

,..., and ∗ ° =⋃ ,..., ∗ plement

of ∙ in where ° are linear spaces in sider the multivalued mappings filled. The pursuers use quasi-strategies, and the evader uses software control..

Game (1), (2) is considered complete if for some 1, the condition ∈ ∙ fulLet be the orthogonal projection mapping from onto the subspace . Conare compact sets from the orthogonal com(1) are (2) , ∈

, , , ,

0, ∈ . ∅ Pontryagin condition. The mappings for all 1, , 0.

There exists at least one Borelian selector ∈ [ 28-32 ]. Let’s fix it and set , , ∙ .

Let’s assign a resolving function to each pursuer:

, , , , ∙ sup 0: , ⋂ , , ∙ ∅ (3) If , , ∙ ∈ , then put , , , , ∙ ∞ , 0 , ∈ . In other cases the function , , , , ∙ assumes finite values for each ∈ 0, , ∈ .

Let’s take ∙ ∙ , … ,

∙ and let Г ∙ : ∈ ,

Theorem 1 [ 5, 33 ]. Assume that the Pontryagin condition holds for the conflict-control process (1), (2), ° ∈ Г we have

, °, °∙ ∞ from the initial state ° to the set ∗ at the moment °, ° ∙ .

Theorem 2 [ 5 ]. Assume that the control process (1), (2) is linear (i.e., , the Pontryagin condition holds, the multivalued mappings the sets tions,

are continuous nonnegative numerical func0, and is the unit ball centered at zero in the space .

Then the resolving functions , , , , ∙ for , , ∙ ∉ are large roots of the quadratic equations , , and 1, … , , for the initial state ° and a certain selector , , ∙ , with respect to , 0 0.

, 1, , ∈ , ∈

Example of problem for a process with simple matrices Consider the problem of group pursuit with pursuers and one evader [ 5, 34 ]: , 0, ∈ , || || 1, || || 1 , 1, (4)

The terminal set

The game is considered over if for some .

∗ ⋃ 1, . The selectors of the multivalued mappings 0. The functions , , ∙ , 1, . The where , Hence we obtain the time to the end the group pursuit: min ∙ ∈ max 1 . min || || max , . Finally, we deduce the upper bound ∗ ln 1

∗ , max [ 1 ]. where ∗ (6) is true.

Theorem 3 [ 5 ]. Let ° be the initial state of the process (4). Then if 0 ∈ then the problem of group pursuit is solvable at finite time ° for which the estimate If ∗ ∗ ∙ , ∗

° , is the instant of switching, at which the test function 1 max the interval 0, ∗ have the form vanishes, then the controls of the pursuers, ensuring of the game at the time ° , on ° , ° , 1, , (5) (6) ° and on the interval ∗, ° for the indices , satisfying the equality the form

If 0 ∉

° , max ,…, ° , , allowing the controls of the remaining pursuers to be arbitrary.

° then the problem is solvable by means of any constant evader’s control which furnished minimum to function max °, .

Visualization of a simple pursuit on the plane There are ϑ pursuers and one evader. The positions of the participants are geometric points, that is we do not take into account their size. Motion of pursuers have the form , ∈ , 1, || || , 1, . If it is true, the motion is calculated by for

1, , then we find the pursuer with the greatest max , and determine his motion , / , 1, and the motion of others is set to zero.

To represent the trajectories of the pursuers and the evader in the game for the plane case, a software product was written in the Python programming language. For the program, the input data is the following information: the number of pursuers, initial coordinates of all participants; maximum speed values for all participants. For the algorithm to work, you need to choose the evader motion. Two cases of evader movement were used in the development. In the first, the motion of the evader is based on the following algorithm: 1) the evader determines the nearest pursuer in terms of the Euclidean norm; 2) the evader builds his control on the beam, which comes from the position of the nearest pursuer and crosses the position of the evader, in the direction opposite to the pursuer with maximum velocity. In the second case, the motion of the evader is set by the user. with a pentagon.

In the figures, the initial positions of the pursuers are marked with stars, the initial position of the evader is marked with a rhombus, and the point of capture is marked

In the Fig. 1-8, we can see several examples of pursuit game. In the Fig. 1-4, the evader uses first algorithm. The evader does not choose his movement optimally because he pays attention only to the nearest pursuer. Such actions can be seen in real life, when of all the threats, the object notices only the nearest and does not pay attention to others. In the Fig. 5-8, the evader`s motion is set by user.

Letting

Therefore 1, 2 , ∈ ,

| | 2 The motions of the one pursuer and the one evader are described by the equations [ 5 ]: Substitute the values of the parameters in (7): 2 0 0 1, 1. 0, , 0, 0 . The operator of orthogonal projecrion

The fundamental matrix of a homogeneous system is 1 .

1. 1 1 0 1 2 0 2 , 1 We set ≡ 0, 0 1 . Then ξ , , 0 4 root of the quadratic equation

By Theorem 2, we obtain the resolving function , , , , 0 as a large positive 1 ξ , 0 , 0

2. 1 Next, by virtue of the capture time set M consists of one point, we conclude that

Let’s find the control of the pursuer. Since the motion occurs on the plane and the and therefore , , °, , , °, , 5, 1 , , °, , , °, , min 1. 5

Visualisation of Pontryagin’s checking example To represent the trajectories of the pursuers and fugitives in the game described in the previous paragraph and for the case of the plane, was created a software in the Python programming language. This is a prototype of a modeling system "fugitive-pursuers", which can be used to select control in control tasks.

The inputing data for the program is the following information: 1.

The values of the parameters α, β, σ, ρ; 2. Initial coordinates of all participants.

Consider the algorithm by which the software works: 1. 2.

Check the conditions

, Check the condition ∅ Сalculate the fundamental matrix , and find .

. 1 Letting 4. 5.

Сalculate ξ , , 0

Сalculate fugitive delay time as min Construct the pursuer control as 0: , , °, , 0 , °, 0 | , , | , , , 1

Using the Runge-Kutta method, we construct the solutions of differential equations at time t.

Let's use this control example to check the program.

, ξ , , 0 |ξ , , 0 | 1

||ξ , , 0 || 1, 2, 2, 0

We get the capture time T that coincides with the time obtained in our calculations (see We obtain the capture time T (see Fig. 10).

References

1. Isaacs , Rufus: Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization . John Wiley & Sons Inc, New York ( 1965 ).

2. Pontryagin , L.S.: Selected scientific works , Nauka, Moscow. 2 ( 1988 ).

3. Nikol 'skii, M.S.: Pontryagin's First Direct Method in Differential Games . Mosk. Gos. Univ., Moscow, 1984 (in Russian).

4. Krasovskii , N.N. , Subbotin , A.I. : Game-theoretical control problems . Springer-Verlag, New York ( 1988 ).

5. Chikrii , A. : Conflict-Controlled Processes . Springer Science &Business Media ( 2013 ).

6. Chikrii , A.A. , Rappoport , I.S. , Chikrii K.A. : Multivalued Mappings and their Selectors in the Theory of Conflict-Controlled Processes . Cybernetics and Systems Analysis 43 ( 5 ), 719 - 730 ( 2007 ).

7. Albus , J. , Meystel , A. , Chikrij , A.A. , Belousov , A.A. , Kozlov , A.I. : Analytical Method for Solution of the Game Problem of Solf Landing for Moving Objects . Cybernetics and Systems Analysis 37 ( 1 ), 75 - 91 ( 2001 ).

8. Chikrii , A.A. , Kalashnikova , S.F. : Pursuit of a Group of Evaders by a Single Controlled Object . Cybernetics 23 ( 4 ), 437 - 445 ( 1987 ).

9. Chikrij , A.A. , Dzyubenko , K.G. : Bilinear Markovian Processes of Search for Moving Objects . Problemy Upravleniya I Informatiki (Avtomatika) 1 , 92 - 106 ( 1997 ).

10. Chikrii , A.A. , Eidelman , S.D.: Control Game Problems for Quasilinear systems with Riemann-Liouvtlle fractional Derivatives . Cybernetics and Systems Analysis 37 ( 6 ), 836 - 864 ( 2001 ).

11. Chikrii , A.A. , Rappoport , I.S. : Systems Analysis Method of Resolving Functions in the Theory of Conflict-Controlled Processes . Cybernetics and Systems Analysis 48 ( 4 ), 512 - 531 ( 2012 ).

12. Chikrii , A.A. , Chikriy , V.K. : Image Structure of Multivalued Mappings in Game Problems of Motion Control . Journal of Automation and Information Science 48 ( 3 ), 20 - 35 ( 2016 ).

13. Chikrii , A. , Matychyn , I. : Riemann-Liouville, Caputo, and Sequential Fractional Derivatives in Differential Games . Annals of the International Society of Dynamic Games 11 , 61 - 81 ( 2011 ).

14. Chikrii , A.A. , Matichin , I.I. : Game Problems for Fractional-order Linear Systems . Proceedings of the Steklov Institute of Mathematics 261 56 - 65 ( 2015 ).

15. Chikrii , A.A. , Chikrii , G.T.: Matrix Resolving Functions in Game Problems of Dynamics . Proceedings of the Steklov Institute of Mathematics 268(SUPPL. 1) ( 2010 ).

16. Baranovska , L.V. : Quasi-Linear Differential-Difference Game of Approach. Understanding Complex Systems , 505 - 524 ( 2019 ).

17. Baranovska , L.V. : On Quasilinear Differential-Difference Games of Approach . Journal of Automation and Information Sciences 49 ( 8 ), 53 - 67 ( 2017 ).

18. Baranovska , Lesia V.: Pursuit differential-difference games with pure time-lag . Discrete and Continuous Dynamical Systems - Series B 24 ( 3 ), 1024 - 1031 ( 2019 ).

19. Baranovska , L.V. : Group Pursuit Differential Games with Pure Time-Lag . In: Sadovnichiy, V. , Zgurovsky , M. (eds.) Contemporary Approaches and Methods in Fundamental Mathematics and Mechanics. Understanding Complex Systems , pp. 475 - 488 . Springer, Cham ( 2021 ).

20. Baranovskaya , G.G. , Baranovskaya , L.V. : Group Pursuit in Quasilinear Differential-Difference Games . Journal of Automation and Information Sciences 29 ( 1 ), 55 - 62 ( 1997 ).

21. Baranovskaya , L.V. , Chikrij , A.A. , Chikrij , Al.A.: Inverse Minkowski functionals in a nonstationary problem of group . Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya (1) , 109 - 114 ( 1997 ).

22. Baranovskaya , L.V. , Chikrij , A.A. , Chikrij , Al.A.: Inverse Minkowski functionals in a nonstationary problem of group . Journal of Computer and Systems Sciences International 36 ( 1 ), 101 - 106 ( 1997 ).

23. Baranovskaya , L.V. : A method of resolving functions for one class of pursuit problems . Eastern-European Journal of Enterprise Technologies , vol. 2 , 4 ( 74 ), 4 - 8 ( 2015 ).

24. Baranovska , L.V. : Method of resolving functions for the differential-difference pursuit game for different-inertia objects . Studies in Systems, Decision and Control 69 , 159 - 176 ( 2016 ).

25. Chikrij , A.A. , Baranovskaya , L.V. , Chikrij , Al.A.: The game problem of approach under the condition of failure of controlling devices . Problemy Upravleniya i Informatiki (Avtomatika) (4) , 5 - 13 ( 1997 ).

26. Baranovskaya , L.V. , Chikrii , Al.A.: Game Problems for a Class of Hereditary Systems . Journal of Automation and Information Sciences 29 ( 2 ), 87 - 97 ( 1997 ).

27. Chikriy , A.A. , Baranovskaya , L.V. , Chikriy , Al. A. : An Approach Game Problem under the Failure of Controlling Devices . Journal of Automation and Information Sciences 35 ( 5 ), 1 - 8 ( 2000 ).

28. Ioffe , A.D. , Tikhomirov , V.M.: Teoriya extremal'nykh zadach (in Rassian) , Nauka, Moscow ( 1974 ).

29. Aubin , J.-P. , Ekeland , I.: Applied Nonlinear Analysis, Wiley, New York ( 1984 ).

30. Aubin , J.-P. , Francowska , He.: Set-Valued Analysis . Birkhause , Boston ( 1990 )

31. Chikrii , A.A. : Multivalued mappings and their selections in game control problems . Journal of Automation and Information Science 27 ( 1 ), 27 - 38 ( 1995 ).

32. Rockafellar , R.T.: Convex Analysis , Princeton University Press, Princeton ( 1970 ).

33. Pittsyk , M. , Chikrii , A.A. : On group pursuit problem . Journal of Applied Mathematics and Mechanics , 46 ( 5 ). 584 - 589 ( 1982 ).

34. Phenichnyi , B.N. : Simple Pursuit by Several Objects . Kibernetika, 3 , 145 - 146 ( 1976 ).

35. Chikrii , A.A. , Prokopovich , P.V. : Simple pursuit of one evader by a froup . Cybernetics and Systems Analysis , 28 ( 3 ), 438 - 444 ( 1992 ).

36. Chikrii , A.A. , Sobolenko , L.A. , Kalashnikova , S.F. : A numerical method for the solution of the pursuit-and-evasion problem . Cybernetics 24 ( 1 ), 53 - 59 ( 1988 ).