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.
Computing Nash equilibrium policies in multi-agent Pursuit-Evasion games (PEG) is challenging due to the exponential growth of the joint state and action spaces with the number of agents. Existing approaches either rely on offline equilibrium approximations, which may lack adaptability during execution, or online planning methods, which suffer from large branching factors. In this work, we propose Primitive-Guided Tree Search (PGTS), a hybrid framework that integrates offline exact Nash equilibrium computation with online tree search: PGTS first solves a collection of smaller, tractable sub-games offline; at deployment, PGTS performs online tree search at each time step, using the optimal sub-game policies and value functions to guide tree expansion and estimate leaf-node values. Extensive experiments on varied graph topologies, including real-world networks, demonstrate that PGTS significantly outperforms state-of-the-art learning and heuristic baselines, while maintaining robust performance against adversaries.
Mukesh Kumar, Yue Guan, Panagiotis Tsiotras
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA
Reachability games are two-player games played on a graph, where the objective of REACH player is to reach the target set whereas the objective of SAFE player is to stay away from the target set. Reachability games have important applications in artificial intelligence and reactive synthesis, and many of these applications give rise to infinite-state reachability games. In this paper, we study turn-based reachability games on infinite-state graphs defined over valuations of a finite set of real variables. We consider the problem of determining the existence of and computing a winning strategy for REACH player. Our contributions are twofold. First, we propose ranking certificates for reachability games, a sound and complete proof rule for proving that REACH player has a winning strategy from the specified initial state. Second, we consider polynomial reachability games, where transitions and objectives are described by polynomial constraints over real variables, and propose a fully automated algorithm for computing a winning strategy for REACH player together with a formal correctness witness in the form of a ranking certificate. The algorithm is sound, semi-complete, and runs in sub-exponential time. Our experiments demonstrate the ability of our method to solve challenging examples from the literature that were out of the reach of existing methods. Specifically, for the classical Cinderella-Stepmother game, we are able to compute an optimal winning strategy for an arbitrary precision parameter for the first time.
A common assumption when designing an agent in a multi-agent system is that the other agents behave adversarially. This allows a designer to obtain the strongest guarantees when they have no control over nor knowledge about the other agents' behavior. However, when all agents are designed under this adversarial assumption, their actual interaction is not adversarial (e.g., when all players play defensively, no player actually attacks). In such settings, we would like to know what behavior arises in the multi-agent system. However, analyzing the interaction among agents is notoriously challenging, both mathematically and algorithmically. In this paper, we provide such an analysis, focusing on bidding games, played by two agents on a graph as follows. A token is placed on a vertex, and in each turn an auction (bidding) determines which agent moves the token, thus generating an infinite path that determines the agents' utilities. We consider mean-payoff objectives; each vertex is associated with a reward for each player, and the utility in an infinite play is the limit average of the rewards. We analyze the play that is generated when each agent follows a strategy that optimizes against an adversary, and consider the two known explicit constructions of optimal strategies. The technical challenge stems from the infinitely-many configurations of a bidding game and their complicated dynamics. We show that, under some restrictions, the generated play is ultimately periodic, and develop algorithms to compute the players' utilities in it.
Shaull Almagor, Guy Avni, Julian Ewaied
Department of Computer Science, Technion. · Department of Computer Science, University of Haifa.