Locally Optimizing Strategies for Approaching the Furthest Evader

Igor Shevchenko

Contributions to game theory and management, Tome 5 (2012), pp. 293-303.

Résumé

We describe a method for constructing feedback strategies based on minimizing/maximizing state evaluation functions with use of steepest descent/ascent conditions. For a specific kinematics, not all control variables may be presented implicitly in the corresponding optimality conditions and some additional local conditions are to be invoked to design strategies for these controls. We apply the general technics to evaluate a chance for the pursuer $P$ to approach the real target that uses decoys by a kill radius $r$. Assumed that $P$ cannot classify the real and false targets. Therefore, $P$ tries to come close to the furthest evader, and thereby to guarantee the capture of all targets including the real one. We setup two-person zero-sum differential games of degree with perfect information of the pursuing, $P$, and several identical evading, $E_1,\ldots,E_N$, agents. The $P$'s goal is to approach the furthest of $E_1,\ldots,E_N$ as closely as possible. Euclidean distances to the furthest evader at the current state or their smooth approximations are used as evaluation functions. For an agent with simple motion, the method allows to specify the strategy for heading angle completely. For an agent that drives a Dubins or Reeds-Shepp car, first we define his targeted trajectory as one that corresponds to the game where all agents has simple motions and apply the locally optimal strategies for heading angles. Then, to design strategies for angular and ordinary velocities, local conditions under which the resulting trajectories approximate the targeted ones are invoked. Two numerical examples of the pursuit simulation when one or two decoys launched at the initial instant are given.

Détail

Keywords: Conservative pursuit strategy, Lyapunov-type function, steepest descent/ascent condition, smooth approximation for min/max, Dubins car, Reeds-Shepp car, decoy.

Bibliographie

[1] Abramyants T. G., Maslov E. P., Rubinovich E. Y., “An Elementary Differential Game of Alternate Pursuit”, Autom. Remote Control, 40:8 (1980), 1043–1052 | MR

[2] Armo K. R., The Relationship Between a Submarine's Maximum Speed and Its Evasive Capability, Master's Thesis of Naval Postgraduate School, Monterey, CA, USA, 2000

[3] Breakwell J. V., Hagedorn P., “Point Capture of Two Evaders in Succession”, J. Optim. Theory Appl., 27:1 (1979), 90–97 | DOI | MR

[4] Cho D.-Y. et al., “Analysis of a submarine's evasive capability against an antisubmarine warfare torpedo using DEVS modeling and simulation”, Proceedings of the 2007 spring simulation multiconference SpringSim'07 (Norfolk, Virginia), Society for Computer Simulation International, San Diego, CA, 2007, 307–315

[5] Dem'yanov V. F., Vasilev L. V., Non-differentiable Optimization, Springer-Verlag, Berlin, 1985 | MR | Zbl

[6] Friedman A., Differential Games, John Wiley, New York, 1971, 350 pp. | MR | Zbl

[7] LaValle S. M., Planning Algorithms, Cambridge University Press, 2006 | MR | Zbl

[8] Lewin J., Decoy in Pursuit Evasion Games, Ph. D. Dissertation, Department of Aeronautics and Astronautics, Stanford University, 1973

[9] Pang J.-E., Pursuit-evasion with Acceleration, Sensing Limitation, and Electronic Counter Measures, MS Dissertation, Graduate School, Clemson University, 2007

[10] Patsko V. S., Turova V. L., Homicidal Chauffeur Game: History and Recent Findings, Institute of Mathematics and Mechanics, Ekaterinburg, 2009 (in Russian) | MR

[11] Shevchenko I. I., “An Elementary Model of Successive Pursuit”, Automat. Remote Control, 43:4 (1982), 456–460 | MR | Zbl

[12] Shevchenko I. I., “Guaranteed Approach with the Farthest of the Runaways”, Automat. Remote Control, 69:5 (2008), 828–844 | DOI | MR | Zbl

[13] Shevchenko I., “Successive Pursuit with a Bounded Detection Domain”, J. Optim. Theory Appl., 95:1 (1997), 25–48 | DOI | MR | Zbl

[14] Shevchenko I., “Approaching Coalitions of Evaders on the Average”, Proceedings of the Eleventh International Symposium on Dynamic Games and Applications (Lowes Ventana Canyon Resort, Tucson, Arizona), ed. T. L. Vincent, 2004, 828–840

[15] Shevchenko I., “Minimizing the Distance to One Evader While Chasing Another”, Computers and Mathematics with Applications, 47:12 (2004), 1827–1855 | DOI | MR | Zbl

[16] Shevchenko I., “Guaranteed Strategies for Successive Pursuit with Finite Sensor Range”, Collected abstracts of papers presented on the Third International Conference on Game Theory and Management, eds. L. A. Petrosyan, N. A. Zenkevich, School of Management, SPb., 2009, 239–240

[17] Stipanović D., Melikyan A., Hovakimyan N., “Some Sufficient Conditions for Multi-Player Pursuit-Evasion Games with Continuous and Discrete Observations”, Annals of the International Society of Dynamic Games, 10 (2009), 133–145 | MR | Zbl

[18] Sticht D. J., Vincent T. L., Schultz D. G., “Sufficiency Theorems for Target Capture”, J. Optim. Theory Appl., 17:5/6 (1975), 523–543 | DOI | MR | Zbl

[19] Subbotin A. I., Chentsov A. G., Optimization of guarantee in control problems, Nauka, Moscow, 1981 (in Russian) | MR