Organizations: School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · College of Engineering and Computing, George Mason University, Fairfax, VA, USA. · Department of Electrical and Computer Engineering, University of North Carolina at Charlotte, Charlotte, NC, USA. · DEVCOM Army Research Laboratory, Adelphi, MD, USA.
This work identifies the dominance regions for discrete, simultaneous-move pursuit-evasion games on graphs. Existing geometric approaches provide efficient characterizations of winning regions, but typically provide only sufficient conditions and rely on open-loop strategies. To address these challenges, we develop a set-based dynamic programming approach to characterize the pursuer's winning and losing regions, providing necessary and sufficient winning conditions under worst-case behavior. The reachability analysis admits a set-chasing interpretation, allowing translation of dominance sets to feedback strategies that adapt to the players' positions in real time. For states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation and establish upper and lower bounds on the pursuer's winning probability. Simulation results validate the correctness of the dominance-region characterization and the proposed bounds.
Figures & tables
Fig. 1: Dilemma faced by the (blue) Pursuer, exploited by the (red) Evader. Black cells denote obstacles, and green squares mark evasion states.
Fig. 2: An illustrative example of the sequence of Q-sets and Z-sets in a 10×10 grid environment. The red dot indicates the current Evader position yt for which the Q-sets and Z-sets are visualized. The Pursuer has 8-way mobility and a 3×3 capture region, whereas the Evader has 4-way mobility.
Fig. 3: An illustration of the dilemma the Pursuer faces in the gray zone.
Fig. 4: Game trajectories and the corresponding dominance sets at each Evader state. The blue Pursuer remains within the Q-set and captures the Evader.
Fig. 5: (a) Visualization of Q/Z-sets for the dilemma example. (b) Pursuer states used for performance evaluations. (c) Game trajectory with the Pursuer starting from Z-set.
Q States
Z States
State
Pursuer Win Rate
State
Pursuer Win Rate
Q1
1.0
Z1
0.0
Q2
1.0
Z2
0.0
Q3
1.0
Z3
0.0
Q4
1.0
Z4
0.0
TABLE I: Simulated Pursuer Win Rate in Dominance Regions
Fig. 6: Illustrative example of LP construction in the gray zone.