Construction of pursuit strategies with using Lyapunov functions

S.V. Pashko

Abstract


This paper is concerned with differential pursuit-evasion games, in which several agents chase one. The time of capture of a target is used as the criterion. The motion of agents is simple one, the velocities are piecewise-continuous. The function that specifies the maximal time of capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach in the following sense. Maximal time of pursuit for the new strategy is not more than maximal time of pursuit for the strategy of parallel approach; at the same time there are many games, for which maximal time of pursuit for the new strategy is less than for the strategy of parallel approach. In  case of pursuit-evasion game on a plane we find explicit form of Lyapunov function and calculate velocities of pursuers using the gradient of this function. Numerical examples show that such velocities of pursuers reduce the maximal time of pursuit. In case of pursuit-evasion game in a multidimensional Euclidean space, Lyapunov function is equal to an optimal value of an objective function of appropriate linear programming problem. The velocities of pursuers are calculated with using the gradient of this function.

Problems in programming 2017; 3: 194-211


Keywords


pursuit-evasion game; agent; strategy of parallel approach; Lyapunov function; maximal time of pursuit

Full Text:

PDF (Ukrainian)

References


Isaacs R. (1999). Differential Games. New York: Dover Publications.

Rikhsiev B.B. (1989). Simple Motion Differential Games. Tashkent: FAN. (In Russian).

Pashko S.V. (2016). Effective Strategies of Pursuit, Based on Lyapunov Function. Dopov. NAN Ukraine. N 1. P. 26 – 33. (In Russian).

Pshenichnyi B.N., Ostapenko V.V. (1992). Differential Games. Kyiv: Nauk. Dumka. (In Russian).

Chikrii A.A. (1992). Conflict-Controlled Processes. Kyiv: Nauk. Dumka. (In Russian).

Pshenichnyi B.N., Chikrii A.A., Rappoport I.S. (1981). Dokl. AN SSSR. 256. 3. P. 530–535. (In Russian).

Ibragimov G.I., Rikhsiev B.B. (2006). On some Sufficient Conditions for Optimality of the Pursuit Time in the Differential Game with Multiple Pursuers. Automation and Remote Control. Volume 67, Issue 4. P. 529–537. (In Russian).

Ivanov R.P., Lediaev Yu.S. (1981). Time Optimality for the Pursuit of Several Objects with Simple Motion in a Differential Game. Trudy Mat. Inst. Steklov.158. P. 87–97. (In Russian).

Kuntsevich V.M., Lychak M.M. (1977). Synthesis of Systems of Automatic Control with the Use of Lyapunov Functions. Moscow: Nauka. (In Russian).

Kolmogorov A.N., Fomin S.V. (1972). Introductory Real Analysis. Moscow: Nauka. (In Russian).

Pashko S.V., Yalovets A.L. (2014). Maximal Time of Pursuit for the Strategy of Parallel Approach. Problems in Programming. N 4.

P. 78–93. (In Russian).

Pashko S.V. (2014). Maximal time of pursuit for the strategy of parallel approach in case of equal speeds. Computer Mathematics. Kyiv: Institute of Cybernetics of the NAS of Ukraine. N 1. P. 140–149. (in Russian).

Pontryagin L.S. (1965). Ordinary Differential Equations. Moscow: Nauka. (In Russian).

Lyashenko I.N., Karagodova E.A., Cher-nikova N.V., Shor N.Z. (1975). Linear and Nonlinear Programming. Kyiv: Vishcha Shkola. (In Russian).

Pervozvansky A.A. (1975). Mathematical Models in Production Management. Moscow: Nauka. (In Russian).

Fikhtengolts G.M. (1969). Course of Differential and Integral Calculus. Volume 1. Moscow: Nauka. (In Russian).


Refbacks

  • There are currently no refbacks.