Reach-Avoid Differential game with Reachability Analysis for UAVs: A decomposition approach
Authors: Minh Bui, Simon Monckton, Mo Chen
Organizations: Simon Fraser University, Burnaby, BC V5A 1S6, Canada · Defense Research & Development Canada (DRDC), Medicine Hat, Alberta T1A 8K6, Canada
Reach-avoid (RA) games have significant applications in security and defense, particularly for unmanned aerial vehicles (UAVs). These problems are inherently challenging due to the need to consider obstacles, consider the adversarial nature of opponents, ensure optimality, and account for nonlinear dynamics. Hamilton-Jacobi (HJ) reachability analysis has emerged as a powerful tool for tackling these challenges; however, while it has been applied to games involving two spatial dimensions, directly extending this approach to three spatial dimensions is impossible due to high dimensionality. On the other hand, alternative approaches for solving RA games lack the generality to consider games with three spatial dimensions involving agents with non-trivial system dynamics. In this work, we propose a novel framework for dimensionality reduction by decomposing the problem into a horizontal RA sub-game and a vertical RA sub-game. We then solve each sub-game using HJ reachability analysis and consider second-order dynamics that account for the defender's acceleration. To reconstruct the solution to the original RA game from the sub-games, we introduce a HJ-based tracking control algorithm in each sub-game that not only guarantees capture of the attacker but also tracking of the attacker thereafter. We prove the conditions under which the capture guarantees are maintained. The effectiveness of our approach is demonstrated via numerical simulations, showing that the decomposition maintains optimality and guarantees in the original problem. Our methods are also validated in a Gazebo physics simulator, achieving successful capture of quadrotors in three spatial dimensions space for the first time to the best of our knowledge.
Figures & tables
pA,pD =
X, Y, Z coordinates of attacker and defender respectively (meters)
pAh,pDh =
X, Y coordinates of attacker and defender respectively (meters)
x =
joint state vector of both attacker and defender
xDh,xAh =
state vector in horizontal direction for defender and attacker
xDz,xAz =
state vector in vertical direction for defender and attacker
V =
Maximum distance value function between attacker and defender
Φ =
Signed-distance value function of reach-avoid game
Table 1
Figure 1: In three spatial dimensions, the defender needs to capture the attacker before it reaches T while avoiding Ωobs .
Figure 2: Our approach breaks down the problem into horizontal and vertical game
Figure 3: Our Reach-Track control procedure in vertical axis
Figure 4: Plot of zrel against vDz , showing contour of relative distance function (light purple) and Vz,∞ (bright yellow-orange)
Figure 5: Winning region WD,z for the defender (blue + green) at different durations T
Figure 6: The joint state of attacker and defender remain inside the invariant capture set if the defender applies optimal tracking control
Figure 7: Using reach-track control algorithm, the joint system can be driven into invariant set Bz .
Figure 8: Contour plot of horizontal distance function Vh,T computed at T=2.5 seconds at different vDy,vDx
Figure 9: Top-view of our experiment configuration in Gazebo simulation
Figure 10: Contour of the value function Vh
Figure 11: Simulation of the defender applying optimal tracking control to track attacker and avoid obstacles
Figure 12: Winning region of the defender (red) and of the attacker (white) given fixed defender (blue) and attacker (green)’s states.
Figure 13: Software configuration of our experiment in Gazebo simulation.
Figure 14: Numerical simulation of the joint trajectories in the horizontal game at different time steps.
Figure 15: Positions (left column) and past trajectories (right column) of defender (blue) and attacker (red) over time in Gazebo.
We study assignment quality in 3D heterogeneous multi-agent reach-avoid games and identify a recurring failure mode of cardinality-only matching in geometrically structured scenarios, which we term Geometric Sprawl. In these cases, multiple maximum-cardinality assignments are available, but some induce spatially incoherent pairings and inefficient pursuit trajectories. Building on the evasion-space framework of Yan et al.~\cite{yan2022}, we introduce a cardinality-first weighted sequential matching method in which the Hamilton--Jacobi--Isaacs interception value zI(s,j) is used as a secondary assignment weight. Each sequential stage is solved with a min-cost max-flow backend, while the unweighted baseline uses the same solver with the weight term removed. We evaluate both methods on a deterministic 35-scenario benchmark (7 families & 5 initialization variants) under two regimes: a diagnostic stationary-unmatched setting and a hybrid saddle-point setting with goal-directed unmatched evaders. On this benchmark, the weighted method resolves 13 of 15 geometric stress-test instances that cause repeated timeouts for the unweighted baseline in the diagnostic regime, and under the hybrid regime improves mean captures from 3.20 to 3.91 (22% increase) and mean interception height from 3.87 to 5.36 (40% increase). We also report lower path tortuosity and lower angular-effort proxy values, suggesting smoother pursuit trajectories in this first-order simulation model. We release the simulator and benchmark suite at github.com/Prajwal-Vijay/geometric-coherence-weighted-matching to support reproducible evaluation of assignment strategies for 3D reach-avoid games.
Prajwal Vijay
Dept. of Electrical Engineering, IIT Madras, Chennai, India
This article presents a Hamilton--Jacobi (HJ) reachability framework for a two--satellite collision avoidance problem operating in the same circular orbit, where relative motion is modeled in the radial--tangential--normal (RTN) frame using planar Hill--Clohessy--Wiltshire (HCW) dynamics. We define the target state space as unsafe relative configurations in the orbit plane corresponding to minimum separation requirements consistent with Federal Communications Commission (FCC) orbital standards. The interaction between spacecraft is formulated as a zero--sum differential game, where Player 1 is the controlled satellite and Player 2 is modeled as a bounded adversarial disturbance with unknown intent. We present the HJ formulation and compute backward reachable sets that characterize relative states from which collision cannot be avoided under worst-case disturbances, while states outside this set admit provably collision-free trajectories. These reachable sets are integrated with supervisory hybrid control logic to determine when evasive maneuvers must be initiated, enabling mathematically grounded safety guarantees for scalability.
Larry Hui, Jordan Kam, William Su +1
Department of Mechanical Engineering, University of California, Berkeley, Berkeley, CA 94720, USA. · Aerospace Engineering Program, University of California, Berkeley, Berkeley, CA 94720, USA. · Department of Mechanical Engineering, National University of Singapore, Singapore 117575.
Aviation authorities worldwide expect Advanced Air Mobility (AAM) traffic management to be decentralized among service providers, requiring AAM flights to autonomously plan trajectories by predicting other flights' control inputs rather than relying on centralized coordination. Game-theoretic approaches that formulate multi-agent collision avoidance as an exact dynamic potential game can efficiently find open-loop equilibria, but they assume that agents exactly follow their equilibrium trajectories---an unrealistic assumption given uncertainties in actuation, perception, and computation. We propose a strategically robust formulation where each agent protects against a fictitious adversary that, for each timestep, perturbs other agents' control inputs within a bounded budget to minimize distance at that timestep. We show that, under reasonable assumptions on agents' distance cost and robustness levels, the strategically robust game remains an exact dynamic potential game and admits a quasi-closed-form solution to the inner adversarial problem for linear dynamics, which limits computational overhead. Experiments with up to eight agents using logarithmic distance costs show that strategic robustness selects more robust trajectories in high-collision-risk configurations while leaving low-risk trajectories nearly unchanged, with only a modest increase in runtime.
Victor L. Qin, Nicolas Lanzetti, Saverio Bolognani +1
Department of Aeronautics and Astronautics, MIT. · Department of Computing and Mathematical Sciences, Caltech. · Automatic Control Laboratory, ETH Zurich.