On the Suicidal Pedestrian Differential Game
Tóm tắt
We consider the following differential game of pursuit and evasion involving two participating players: an evader, which has limited maneuverability, and an agile pursuer. The agents move on the Euclidean plane with different but constant speeds. Whereas the pursuer can change the orientation of its velocity vector arbitrarily fast, that is, he is a “pedestrian” á la Isaacs, the evader cannot make turns having a radius smaller than a specified minimum turning radius. This problem can be seen as a reversed Homicidal Chauffeur game, hence the name “Suicidal Pedestrian Differential Game.” The aim of this paper is to derive the optimal strategies of the two players and characterize the initial conditions that lead to capture if the pursuer acts optimally, and areas that guarantee evasion regardless of the pursuer’s strategy. Both proximity-capture and point-capture are considered. After applying the optimal strategy for the evader, it is shown that the case of point-capture reduces to a special version of Zermelo’s Navigation Problem (ZNP) for the pursuer. Therefore, the well-known ZNP solution can be used to validate the results obtained through the differential game framework, as well as to characterize the time-optimal trajectories. The results are directly applicable to collision avoidance in maritime and Air Traffic Control applications.
Tài liệu tham khảo
Bakolas E, Tsiotras P (2010) Time-optimal synthesis for the Zermelo–Markov–Dubins problem: the constant wind case. In Poceedings of the American control conference, Baltimore, MD, pp 6163–6168
Bakolas E, Tsiotras P (2012) Feedback navigation in an uncertain flowfield and connections with pursuit strategies. J Guid Control Dyn 35(4):1268–1279
Basar T, Olsder GJ (1995) Dynamic noncooperative game theory. Academic Press, Waltham
Bopardikar S, Bullo F, Hespanha J (2007) A cooperative homicidal chauffeur game. In Proceedings of the 46th IEEE conference on decision and control pp 4857–4862
Bryson A, Ho Y (1975) Applied optimal control: optimization, estimation and control. Taylor and Francis, New York
Cockayne E (1967) Plane pursuit with curvature constrains. SIAM J Appl Math 15:1511–1516
Exarchos I, Tsiotras P (2014) An asymmetric version of the two car pursuit-evasion game. In Proceedings of the 53rd IEEE conference on decision and control, Los Angeles, CA
Ho Y, Bryson A, Baron S (1965) Differential games and optimal pursuit-evasion strategies. IEEE Trans Autom Control 10:385–389
Isaacs R (1965) Differential games. Willey, New York
Lewin J (1994) Differential games—theory and methods for solving game problems with singular surfaces. Springer, London
Li B, Xu C, Kok LT, Chu J (2013) Time optimal Zermelo’s navigation problem with moving and fixed obstacles. J Appl Math Comput 224:866–875
Meier LI (1969) A new technique for solving pursuit-evasion differential games. IEEE Trans Autom Control 14(4):352–359
Merz A (1971) Homicidal chauffeur-a differential game. Ph.D. Thesis, Stanford University
Merz A (1972) The game of two identical cars. J Opt Theory Appl 9:324–343
Merz A (1973) Optimal evasive maneuvers in maritime collision avoidance. J Inst Navig 20(2):144–152
Miloh T, Sharma SD (1975) Bericht nr. 319: determination of critical maneuvers for collision avoidance. Tech Rep, Institut fur Schiffbau, Technische Universitat Hamburg
Miloh T, Sharma SD (1976) Bericht nr. 329: maritime collision avoidance as a differential game. Tech Rep, Institut fur Schiffbau, Technische Universitat Hamburg
Mitchell I (2001) Games of two identical vehicles. Technical Report, Department of Aeronautics and Astronautics (SUDAAR), Stanford University, Stanford, CA
Mitchell I, Bayen A, Tomlin C (2005) A time-dependent Hamilton–Jacobi formulation of reachable sets for continuous dynamic games. IEEE Trans Autom Control 50:947–957
Nahin PJ (2007) Chases and escapes: the mathematics of pursuit and evasion. Princeton University Press, Princeton
Olsder GJ, Walter JL (1977) Collision avoidance of ships. Tech Rep, Dept of Applied Mathematics, Twente University of Technology
Olsder GJ, Walter JL (1977) A differential game approach to collision avoidance of ships. Optimization techniques. Lecture notes in control and information sciences, vol 6. Springer, Berlin pp 264–271
Pachter M (2002) Simple-motion pursuit-evasion differential games. In Proceedings of the 10th Mediterranean conference on control and automation
Pachter M, Miloh T (1987) The geometric approach to the construction of the barrier surface in differential games. Comput Math Appl 13(1–3):47–67
Pachter M, Yavin Y (1981) A stochastic homicidal chauffeur pursuit-evasion differential game. J Opt Theory Appl 34(3):405–424
Patsko V, Turova V (2001) Level sets of the value function in differential games with the homicidal chauffeur dynamics. Int Game Theory Rev 3(1):67–112
Pshenichnyi B (1976) Simple pursuit by several objects. Kibernetika 3:145–146
Rublein G (1972) On pursuit with curvature constrains. SIAM J Control 10:37–39
Salmon D (1969) Policies and controller design for a pursuing vehicle. IEEE Trans Autom Control 14(5):482–488
Sgall J (2001) Solution of David Gale’s lion and man problem. Theoret Comput Sci 259(1–2):663–670
Vincent TL, Peng WY (1973) Ship collision avoidance. In Proceedings of the workshop on differential games, Naval Academy, Annapolis
Yavin Y (1986) Stochastic pursuit-evasion differential games in the plane. J Opt Theory Appl 50:495–523
Yavin Y, Villiers RD (1989) Proportional navigation and the game of two cars. J Opt Theory Appl 62:351–369
Zermelo E (1931) Uber das Navigationsproblem bei ruhender oder veranderlicher Windverteilung. Zeitschrift fuer Angewandte Mathematik und Mechanik 11:114–124