eess.SYDec 28, 2025

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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\textbf{p}_{A},\textbf{p}_{D} =X, Y, Z coordinates of attacker and defender respectively (meters)
pAh,pDh\textbf{p}^{h}_{A},\textbf{p}^{h}_{D} =X, Y coordinates of attacker and defender respectively (meters)
x\mathbf{x} =joint state vector of both attacker and defender
xDh,xAh\mathbf{x}^{h}_{D},\mathbf{x}^{h}_{A} =state vector in horizontal direction for defender and attacker
xDz,xAz\mathbf{x}^{z}_{D},\mathbf{x}^{z}_{A} =state vector in vertical direction for defender and attacker
VV =Maximum distance value function between attacker and defender
Φ\Phi =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\mathcal{T} while avoiding Ωobs\Omega_{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 zrelz_{\text{rel}} against vDzv^{z}_{D} , showing contour of relative distance function (light purple) and Vz,∞V_{z,\infty} (bright yellow-orange)
Figure 5: Winning region WD,z\mathcal{W}_{D,z} for the defender (blue + green) at different durations TT
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\mathcal{B}_{z} .
Figure 8: Contour plot of horizontal distance function Vh,TV_{h,T} computed at T=2.5T=2.5 seconds at different vDy,vDxv^{y}_{D},v^{x}_{D}
Figure 9: Top-view of our experiment configuration in Gazebo simulation
Figure 10: Contour of the value function VhV_{h}
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.
More in this topic

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 236 papers

Explore similar work

CardsList

  1. Geometric Coherence via Weighted Matching for 3D Heterogeneous Multi-Agent Reach-Avoid Games

    Sep 19, 2026Prajwal VijayMulti-Agent SystemsGame Theory

    Dept. of Electrical Engineering, IIT Madras, Chennai, India

  2. Hamilton--Jacobi Reachability for Spacecraft Collision Avoidance

    May 19, 2026Larry Hui, Jordan Kam, William Su +1Collision AvoidanceReachability Analysis

    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.

  3. Strategically Robust Game-Theoretic Multi-Agent Trajectory Optimization

    Sep 28, 2026Victor L. Qin, Nicolas Lanzetti, Saverio Bolognani +1Collision AvoidanceTrajectory Optimization

    Department of Aeronautics and Astronautics, MIT. · Department of Computing and Mathematical Sciences, Caltech. · Automatic Control Laboratory, ETH Zurich.