The Game of Two Identical Cars: An Analytical Description of the Barrier | Journal of Optimization Theory and Applications Skip to main content
Springer Nature Link
Log in

The Game of Two Identical Cars: An Analytical Description of the Barrier

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

In this study, a pursuit-evasion game of two players, known as a game of two identical cars, is examined. It is assumed that the game proceeds in a two-dimensional plane. Both players have a constant speed and a limited turn radius. The goal of the first player (pursuer) is to ensure that the second player (evader) enters the capture circle as quickly as possible. The goal of the evader is to avoid or delay capturing for as long as possible. The kinematics of both players are described using the same equations. Thus, the game has only one free parameter: capture radius. This study aims to provide an exhaustive analytical description of the barrier surface for all values of capture radius. Previously, Merz analytically investigated the barrier in a game of two identical cars. In this work, it was found that there is a certain critical value of the capture radius, above which the barrier is qualitatively different from Merz’s example. In addition, we obtained an explicit analytical description of the optimal feedback controls for the barrier.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availability

All data generated or analyzed during this study are included in this published article.

Notes

  1. Throughout the paper, \({\mathbb {B}}\) denotes the binary set \(\{-1, +1\}\). Additionally, we use the letter \(\upsilon \) (upsilon) to denote a binary variable. This letter looks like an evader’s control v, which will actually play this role.

References

  1. Baron, S., Chu, K.C., Ho, Y.C., Kleinman, D.L.: A new approach to aerial combat games. Tech. Rep. NASA-CR-1626, Harvard University (1970)

  2. Bera, R., Makkapati, V.R., Kothari, M.: A comprehensive differential game theoretic solution to a game of two cars. J. Optim. Theory Appl. 174(3), 818–836 (2017). https://doi.org/10.1007/s10957-017-1134-z

    Article  MathSciNet  MATH  Google Scholar 

  3. Borówko, P., Rzymowski, W.: On the game of two cars. J. Optim. Theory Appl. 44(3), 381–396 (1984). https://doi.org/10.1007/bf00935458

    Article  MathSciNet  MATH  Google Scholar 

  4. Breakwell, J.V., Merz, A.W.: Minimum required capture radius in a coplanar model of the aerial combat problem. AIAA J. 15(8), 1089–1094 (1977). https://doi.org/10.2514/3.7399

    Article  Google Scholar 

  5. Ciletti, M.D., Merz, A.W.: Collision avoidance maneuvers for ships. Navigation 23(2), 128–135 (1976). https://doi.org/10.1002/j.2161-4296.1976.tb00731.x

    Article  Google Scholar 

  6. Cockayne, E.: Plane pursuit with curvature constraints. SIAM J. Appl. Math. 15(6), 1511–1516 (1967). https://doi.org/10.1137/0115133

    Article  MathSciNet  MATH  Google Scholar 

  7. Farber, N., Shinar, J.: Approximate solution of singularly perturbed nonlinear pursuit-evasion games. J. Optim. Theory Appl. 32(1), 39–73 (1980). https://doi.org/10.1007/BF00934842

    Article  MathSciNet  MATH  Google Scholar 

  8. Greenfeld, I.: A differential game of surveillance evasion of two identical cars. J. Optim. Theory Appl. 52(1), 53–79 (1987). https://doi.org/10.1007/BF00938464

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  10. Kostsov, A.V., Simakova, E.N.: Differential game an conventional ways to solve the pursuit problem. Autom. Remote Control 49(11), 1423–1432 (1988)

    MATH  Google Scholar 

  11. Kwik, K.H.: Calculation of ship collision avoidance manoeuvres: a simplified approach. Ocean Eng. 16(5), 475–491 (1989). https://doi.org/10.1016/0029-8018(89)90048-6

    Article  Google Scholar 

  12. Lewin, J.: Differential Games: Theory and Methods for Solving Game Problems with Singular Surfaces. Springer Science & Business Media, Berlin (2012). https://doi.org/10.1007/978-1-4471-2065-0

    Book  Google Scholar 

  13. Maurer, H., Tarnopolskaya, T., Fulton, N.: Singular controls in optimal collision avoidance for participants with unequal linear speeds. ANZIAM J. 53, 1–18 (2011). https://doi.org/10.21914/anziamj.v53i0.5098

  14. Maurer, H., Tarnopolskaya, T., Fulton, N.: Optimal bang-bang and singular controls in collision avoidance for participants with unequal linear speeds. In: 2012 IEEE 51st IEEE Conference on Decision and cCntrol (CDC) 2012. IEEE, pp. 7697–7702 2012). https://doi.org/10.1109/CDC.2012.6426792

  15. Maurer, H., Tarnopolskaya, T., Fulton, N.: Computation of bang-bang and singular controls in collision avoidance. J. Ind. Manag. Optim. 10(2), 443–460 (2014). https://doi.org/10.3934/jimo.2014.10.443

    Article  MathSciNet  MATH  Google Scholar 

  16. Meier, L.: A new technique for solving pursuit-evasion differential games. IEEE Trans. Autom. Control 14(4), 352–359 (1969). https://doi.org/10.1109/TAC.1969.1099226

    Article  MathSciNet  Google Scholar 

  17. Merz, A.W.: The game of two identical cars. J. Optim. Theory Appl. 9(5), 324–343 (1972). https://doi.org/10.1007/BF00932932

    Article  MathSciNet  MATH  Google Scholar 

  18. Merz, A.W.: Optimal evasive maneuvers in maritime collision avoidance. Navigation 20(2), 144–152 (1973). https://doi.org/10.1002/j.2161-4296.1973.tb01163.x

    Article  Google Scholar 

  19. Merz, A.W.: The homicidal chauffeur. AIAA J. 12(3), 259–260 (1974). https://doi.org/10.2514/3.49215

    Article  MathSciNet  Google Scholar 

  20. Merz, A.W., Karmarkar, J.S.: Collision avoidance systems and optimal turn manoeuvres. J. Navig. 29(2), 160–174 (1976). https://doi.org/10.1017/s0373463300030150

    Article  Google Scholar 

  21. Miloh, T.: Determination of critical maneuvers for collision avoidance using the theory of differential games. Tech. Rep. 319, Institut für Schiffbau der Uni Hamburg (1974)

  22. Miloh, T.: The game of two elliptical ships. Optim. Control Appl. Methods 4(1), 13–29 (1983). https://doi.org/10.1002/oca.4660040103

    Article  MathSciNet  MATH  Google Scholar 

  23. Miloh, T., Pachter, M.: Ship collision-avoidance and pursuit-evasion differential games with speed-loss in a turn. Comput. Math. Appl. 18(1), 77–100 (1989). https://doi.org/10.1016/0898-1221(89)90126-0

    Article  MathSciNet  MATH  Google Scholar 

  24. Miloh, T., Sharma, S.D.: Maritime collision avoidance as a differential game. Schiffstechnik 24(116), 69–88 (1977)

    Google Scholar 

  25. Mitchell, I.: Games of two identical vehicles. Tech. Rep. SUDAAR #740, Stanford University (2001)

  26. Olsder, G.J., Walter, J.L.: A differential game approach to collision avoidance of ships. In: Stoer, J. (ed.) Optimization Techniques Part 1, pp. 264–271. Springer, Berlin (1978)

    Chapter  Google Scholar 

  27. Pachter, M., Coates, S.: The classical homicidal chauffeur game. Dyn. Games Appl. 9(3), 800–850 (2019). https://doi.org/10.1007/s13235-018-0264-8

    Article  MathSciNet  MATH  Google Scholar 

  28. Pachter, M., Getz, W.M.: The geometry of the barrier in the game of two cars. Optim. Control Appl. Methods 1(2), 103–118 (1980). https://doi.org/10.1002/oca.4660010202

    Article  MathSciNet  MATH  Google Scholar 

  29. Pachter, M., Miloh, T.: The geometric approach to the construction of the barrier surface in differential games. Comput. Math. Appl. 13(1–3), 47–67 (1987). https://doi.org/10.1016/0898-1221(87)90093-9

    Article  MathSciNet  MATH  Google Scholar 

  30. Rublein, G.T.: On pursuit with curvature constraints. SIAM J. Control. Optim. 10(1), 37–39 (1972). https://doi.org/10.1137/0310003

    Article  MathSciNet  MATH  Google Scholar 

  31. Sharma, S.D.: On ship maneuverability and collision avoidance. Tech. Rep. 352, Institut für Schiffbau der Uni Hamburg (1977)

  32. Simakova, E.N.: Differential pursuit game. Autom. Remote Control 28(2), 173–181 (1967)

    MathSciNet  MATH  Google Scholar 

  33. Simakova, E.N.: Problem of pursuit and evasion. Autom. Remote Control 31(8), 1205–1211 (1970)

    MathSciNet  MATH  Google Scholar 

  34. Simakova, E.N.: On optimal strategies in games of pursuit with limited maneuverability. Autom. Remote Control 44(10), 1307–1315 (1983)

    MathSciNet  MATH  Google Scholar 

  35. Simakova, E.N.: On bellman functions in optimization of dynamic systems under uncertainty. Autom. Remote Control 47(2), 47–51 (1986)

    MathSciNet  MATH  Google Scholar 

  36. Tarnopolskaya, T., Fulton, N.: Optimal cooperative collision avoidance strategy for coplanar encounter: Merz’s solution revisited. J. Optim. Theory Appl. 140(2), 355–375 (2009). https://doi.org/10.1007/s10957-008-9452-9

    Article  MathSciNet  MATH  Google Scholar 

  37. Tarnopolskaya, T., Fulton, N.: Synthesis of optimal control for cooperative collision avoidance for aircraft (ships) with unequal turn capabilities. J. Optim. Theory Appl. 144(2), 367–390 (2010). https://doi.org/10.1007/s10957-009-9597-1

    Article  MathSciNet  MATH  Google Scholar 

  38. Tarnopolskaya, T., Fulton, N.L.: Non-unique optimal collision avoidance strategies for coplanar encounter of participants with unequal turn capabilities. IAENG Int. J. Appl. Math. 40(4), 289–296 (2010)

    MathSciNet  MATH  Google Scholar 

  39. Tarnopolskaya, T., Fulton, N.L.: Synthesis of optimal control for cooperative collision avoidance in a close proximity encounter: special cases. IFAC Proc. 44(1), 9775–9781 (2011). https://doi.org/10.3182/20110828-6-IT-1002.00325

    Article  Google Scholar 

  40. Vincent, T.L., Cliff, E.M., Grantham, W.J., Peng, W.Y.: A problem of collision avoidance. Tech. Rep. NASA-CR-129988, University of Arizona (1972)

  41. Vincent, T.L., Cliff, E.M., Grantham, W.J., Peng, W.Y.: Some aspects of collision avoidance. AIAA J. 12(1), 3–4 (1974). https://doi.org/10.2514/3.49141

    Article  Google Scholar 

  42. Vincent, T.L., Sticht, D.J., Peng, W.Y.: Aircraft missile avoidance. Oper. Res. 24(3), 420–437 (1976). https://doi.org/10.1287/opre.24.3.420

    Article  MATH  Google Scholar 

  43. Weintraub, I.E., Pachter, M., Garcia, E.: An introduction to pursuit-evasion differential games. In: 2020 American Control Conference (ACC), pp. 1049–1066 (2020). https://doi.org/10.23919/ACC45564.2020.9147205

Download references

Acknowledgements

The research was supported by RSF (project No. 23-19-00134).

Author information

Authors and Affiliations

  1. V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, Russia

    Maksim Buzikov & Andrey Galyaev

Authors
  1. Maksim Buzikov
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Andrey Galyaev
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Maksim Buzikov.

Ethics declarations

Conflict of interest

The authors have no conflicts of interest to declare.

Additional information

Communicated by Mauro Pontani.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Buzikov, M., Galyaev, A. The Game of Two Identical Cars: An Analytical Description of the Barrier. J Optim Theory Appl 198, 988–1018 (2023). https://doi.org/10.1007/s10957-023-02278-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-023-02278-1

Keywords

Mathematics Subject Classification