Guarding a convex target set in a particular case of the game of two cars

Abstract

This paper presents a geometric solution framework for a target defense problem, formulated as a variant of the classical Game of Two Cars. The setting considers a Dubins defender that is faster and more maneuverable and aims to intercept a Dubins attacker attempting to reach a convex target set. To address the computational complexity of solving the associated Hamilton-Jacobi-Isaacs (HJI) equations, a geometric approach based on the concept of the Attacker Dominance Region (ADR) is developed. The ADR is constructed piecewise from the boundaries of the players’ reachable sets. The complete solution consists of two components: a Game of Kind, which determines the outcome based on the spatial relationship between the ADR and the target set, and a Game of Degree, which derives optimal strategies that achieve equilibrium. Simulation results demonstrate the effectiveness of the proposed method under realistic motion constraints and indicate its potential applicability to practical target defense scenarios.

Keywords

Game of Two Cars / Attacker dominance region / Reachability analysis / Target defense game

References

[1] Li X., Meng M., Hong Y., Chen J.. A survey of decision making in adversarial games. Sci. China Inf. Sci., 2024, 67(4): 1-28

[2] Chi S., Li S., Wang C., Xie G.. A review of research on pursuit-evasion games. Acta Autom. Sin., 2025, 51(4): 705-726

[3] Peterson A.N., Soto A.P., McHenry M.J.. Pursuit and evasion strategies in the predator-prey interactions of fishes. Integr. Comp. Biol., 2021, 61(2): 668-680

[4] Garcia E., Casbeer D.W., Pachter M.. Design and analysis of state-feedback optimal strategies for the differential game of active defense. IEEE Trans. Autom. Control, 2018, 64(2): 553-568

[5] Garcia E., Casbeer D.W., Fuchs Z.E., Pachter M.. Cooperative missile guidance for active defense of air vehicles. IEEE Trans. Aerosp. Electron. Syst., 2017, 54(2): 706-721

[6] Isaacs R.. Differential Games, 1965, Mineola, Dover

[7] Pontryagin L.S.. On the theory of differential games. Russ. Math. Surv., 1966, 21(4): 193-246

[8] Krassovskii N., Subbotin A.I.. Positional Differential Games, 1974, Moskva, Nauka

[9] Friedman A.. Differential Games, 2013, Mineola, Courier Corporation

[10] Fu H., Liu H.H.-T.. Guarding a territory against an intelligent intruder: strategy design and experimental verification. IEEE/ASME Trans. Mechatron., 2020, 25(4): 1765-1772

[11] Liang L., Deng F., Lu M., Chen J.. Analysis of role switch for cooperative target defense differential game. IEEE Trans. Autom. Control, 2020, 66(2): 902-909

[12] Bakolas E., Tsiotras P.. Optimal pursuit of moving targets using dynamic Voronoi diagrams. Proc. IEEE Conf. Decis. Control, 201074317436

[13] Dorothy M., Maity D., Shishika D., Von Moll A.. One Apollonius circle is enough for many pursuit-evasion games. Automatica, 2024, 163 111587

[14] Garcia E., Fuchs Z.E., Milutinovic D., Casbeer D.W., Pachter M.. A geometric approach for the cooperative two-pursuer one-evader differential game. IFAC-PapersOnLine, 2017, 50(1): 15209-15214

[15] Garcia E., Casbeer D.W., Pachter M.. Optimal strategies for a class of multi-player reach-avoid differential games in 3D space. IEEE Robot. Autom. Lett., 2020, 5(3): 4257-4264

[16] Yan R., Deng R., Duan X., Shi Z., Zhong Y.. Multiplayer reach-avoid differential games with simple motions: a review. Front. Control Eng., 2023, 3 1093186

[17] Mulla A.K., Chakraborty D.. Min-max time consensus tracking with communication guarantee. IEEE Trans. Autom. Control, 2017, 63(1): 132-144

[18] Sarkar R., Patil D., Mulla A.K., Kar I.N.. Finite-time consensus tracking of multi-agent systems using time-fuel optimal pursuit evasion. IEEE Control Syst. Lett., 2021, 6: 962-967

[19] Li S., Wang C., Xie G.. Optimal strategies for pursuit-evasion differential games of players with damped double integrator dynamics. IEEE Trans. Autom. Control, 2023, 69(8): 5278-5293

[20] Dubins L.E.. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math., 1957, 79(3): 497-516

[21] Cockayne E., Hall G.. Plane motion of a particle subject to curvature constraints. SIAM J. Control, 1975, 13(1): 197-220

[22] Merz A.. The game of two identical cars. J. Optim. Theory Appl., 1972, 9: 324-343

[23] Bera R., Makkapati V.R., Kothari M.. A comprehensive differential game theoretic solution to a game of two cars. J. Optim. Theory Appl., 2017, 174: 818-836

[24] Chaudhari A., Chakraborty D.. A time-optimal feedback control for a particular case of the game of two cars. IEEE Trans. Autom. Control, 2021, 67(4): 1806-1821

[25] Exarchos I., Tsiotras P.. An asymmetric version of the two car pursuit-evasion game. Proc. IEEE Conf. Decis. Control, 201442724277

[26] Pachter M., Coates S.. The classical homicidal chauffeur game. Dyn. Games Appl., 2019, 9: 800-850

[27] Liu Z., Lei J., Yi P., Hong Y.. An interaction-fair semi-decentralized trajectory planner for connected and autonomous vehicles. Auton. Intell. Syst., 2025, 5(1): 1

[28] Chen Y., Wu Y., Yang H., Cao J., Wang Q., Liu Y.. A distributed pipeline for collaborative pursuit in the target guarding problem. IEEE Robot. Autom. Lett., 2024, 932064-2071

[29] Shishika D., Maity D., Dorothy M.. Partial information target defense game. Proc. IEEE Int. Conf. Robot. Autom., 202181118117

[30] Chen M., Zhou Z., Tomlin C.J.. Multiplayer reach-avoid games via pairwise outcomes. IEEE Trans. Autom. Control, 2016, 62(3): 1451-1457

[31] Yan R., Shi Z., Zhong Y.. Reach-avoid games with two defenders and one attacker: an analytical approach. IEEE Trans. Cybern., 2018, 49(3): 1035-1046

[32] Velhal S., Sundaram S., Sundararajan N.. Dynamic resource allocation with decentralized multi-task assignment approach for perimeter defense problem. IEEE Trans. Aerosp. Electron. Syst., 2022, 58(4): 3313-3325

[33] Deng R., Zhang W., Yan R., Shi Z., Zhong Y.. Multiple-pursuer single-evader reach-avoid games in constant flow fields. IEEE Trans. Autom. Control, 2023, 69(3): 1789-1795

[34] Liang L., Deng F., Peng Z., Li X., Zha W.. A differential game for cooperative target defense. Automatica, 2019, 102: 58-71

[35] Yan R., Deng R., Lai H., Zhang W., Shi Z., Zhong Y.. Homicidal chauffeur reach-avoid games via guaranteed winning strategies. IEEE Trans. Autom. Control, 2023, 69(4): 2367-2382

[36] Yan R., Duan X., Zou R., He X., Shi Z., Bullo F.. Multiplayer homicidal chauffeur reach-avoid games: a pursuit enclosure function approach. Automatica, 2024, 167 111770

[37] Cai B., Li H., Zhang N., Cao M., Yu H.. A cooperative jamming decision-making method based on multi-agent reinforcement learning. Auton. Intell. Syst., 2025, 5(1): 3

[38] Zhou P., Xu Y., Wahlberg B., Hu X.. Distributed strategies for pursuit-evasion of high-order integrators. Auton. Intell. Syst., 2024, 4128

[39] Buzikov M., Galyaev A.. The game of two identical cars: an analytical description of the barrier. J. Optim. Theory Appl., 2023, 1983988-1018

[40] Garcia E., Casbeer D.W., Pachter M.. Optimal strategies of the differential game in a circular region. IEEE Control Syst. Lett., 2019, 4(2): 492-497

[41] Huang W., Liang L., Xu N., Deng F.. Dominance regions of pursuit-evasion games in non-anticipative information patterns. Automatica, 2025, 176 112258

[42] Yan R., Shi Z., Zhong Y.. Construction of the barrier for reach-avoid differential games in three-dimensional space with four equal-speed players. Proc. IEEE Conf. Decis. Control, 201940674072

[43] Oyler D.W., Girard A.R.. Dominance regions in the homicidal chauffeur problem. Proc. Amer. Control Conf., 201624942499

[44] Li D., Cruz J.B., Chen G., Kwan C., Chang M.-H.. A hierarchical approach to multi-player pursuit-evasion differential games. Proc. IEEE Conf. Decis. Control, 200556745679

[45] Lee Y., Bakolas E.. Optimal strategies for guarding a compact and convex target set: a differential game approach. Proc. IEEE Conf. Decis. Control, 202143204325

[46] Ip C.M.B., Lam Y.L., Zhang C., Huang H.. Game-theoretical mpc for quadrotor pursuit: strategic anticipation and efficient capture. Proc. IEEE Int. Conf. On Control Autom., 2025552557

RIGHTS & PERMISSIONS

The Author(s)