Source-linked AI summary
Reach-Avoid Problems with Time-Varying Dynamics, Targets and Constraints
Jaime F. Fisac, Mo Chen, Claire J. Tomlin, S. Shankar Sastry
TL;DR
The paper addresses reach-avoid differential games with time-varying dynamics, targets, and constraints, where one player seeks a constrained target reach and another tries to prevent it. It formulates a double-obstacle Hamilton-Jacobi-Isaacs variational inequality and proves that its viscosity solution’s zero sublevel set gives the capture basin. The resulting numerical method has complexity equivalent to time-invariant techniques and avoids state augmentation, while the paper also notes a scope boundary concerning post-target constraint violations.
Problem
Reach-avoid games require guaranteed target reach while respecting constraints against an adversary, but prior methods either restrict time variation or augment the state with time, causing exponential dimensional complexity.
Method
The paper formulates a double-obstacle Hamilton-Jacobi-Isaacs variational inequality for time-varying dynamics, targets, and constraints, and uses its viscosity solution to characterize the capture basin.
Results
The zero sublevel set of the viscosity solution characterizes the reach-avoid set, while numerical implementations have computational complexity equivalent to existing time-invariant techniques.
Takeaways & Limitations
The formulation supports reachability analysis and safety guarantees for time-varying systems without the additional computational cost of incorporating time as a state variable.
Takeaways & Limitations
The value function permits constraint violations after the target has been reached, whereas requiring feasibility for the entire game is treated as an alternative problem outside the paper’s scope.
Abstract
from arXiv · showhide
We consider a reach-avoid differential game, in which one of the players aims to steer the system into a target set without violating a set of state constraints, while the other player tries to prevent the first from succeeding; the system dynamics, target set, and state constraints may all be time-varying. The analysis of this problem plays an important role in collision avoidance, motion planning and aircraft control, among other applications. Previous methods for computing the guaranteed winning initial conditions and strategies for each player have either required augmenting the state vector to include time, or have been limited to problems with either no state constraints or entirely static targets, constraints and dynamics. To incorporate time-varying dynamics, targets and constraints without the need for state augmentation, we propose a modified Hamilton-Jacobi-Isaacs equation in the form of a double-obstacle variational inequality, and prove that the zero sublevel set of its viscosity solution characterizes the capture basin for the target under the state constraints. Through this formulation, our method can compute the capture basin and winning strategies for time-varying games at no additional computational cost with respect to the time-invariant case. We provide an implementation of this method based on well-known numerical schemes and show its convergence through a simple example; we include a second example in which our method substantially outperforms the state augmentation approach.
1. INTRODUCTION
The paper studies reach-avoid games with time-varying dynamics, targets, and constraints, motivated by safety-critical applications. It introduces a double-obstacle Hamilton-Jacobi formulation that characterizes the capture basin without state augmentation and avoids the computational burden of adding time to the state.
- Applications include collision avoidance, surveillance, energy management, and safe reinforcement learning, with obstacles represented as forbidden configurations.
- Reach-avoid games seek states from which an attacker can reach a target while satisfying constraints against an opposing defender.The resulting winning set is called the capture basin, backwards reachable set, or reach-avoid set.
- Existing time-varying methods augment the state with time, making numerical complexity exponential in the problem dimensionality.This transforms time dependence into state dependence but creates a significant computational drawback.
- The paper extends Hamilton-Jacobi reach-avoid analysis to time-varying dynamics, targets, and constraints without significant additional cost relative to the time-invariant case.
- A double-obstacle Hamilton-Jacobi-Isaacs variational inequality is formulated, whose viscosity solution’s zero sublevel set characterizes the reach-avoid set.
- The paper identifies its double-obstacle Hamilton-Jacobi analysis as the first such analysis in reachability problems, while noting applicability to optimal control.
2. PROBLEM FORMULATION
The formulation models a two-player dynamical system with measurable controls, time-varying target and constraint sets, and value functions that encode reachability under competing information patterns. The capture basin is characterized by zero sublevel sets of the corresponding game values.
- 2.1 System Dynamics: The system has state x in R^n, player inputs a and b, and time-dependent dynamics f that are measurable in inputs and time and bounded and Lipschitz continuous in x.These assumptions yield a unique continuous trajectory for each initial condition and pair of input signals.
- 2.1 System Dynamics: Trajectories solve the dynamics in the extended sense, meaning the differential equation holds almost everywhere over the time interval.
- 2.2 Target and Constraint Sets: Time-varying target and constraint sets are modeled as upper hemicontinuous set-valued maps with closed slices, producing closed space-time sets.A lemma establishes closedness of the corresponding unions in R^n × [0,T].
- 2.2 Target and Constraint Sets: The target and constraint sets are represented as subzero regions of Lipschitz functions l and g, respectively.Signed distance functions provide one construction, and the representation permits changing topologies over time.
- 2.2 Target and Constraint Sets: The payoff l records the minimum target-related value along an admissible trajectory, while the discriminator g records the maximum constraint violation.A trajectory is admissible when it remains in the constraint set throughout the considered interval.
- 2.3 Value and Strategies: Player I minimizes the game outcome as attacker, while player II maximizes it as defender and may prevent success by driving the system outside the constraints.
- 2.3 Value and Strategies: Nonanticipative strategies give the responding player an information advantage, defining upper and lower game values according to which player adapts to the other.The upper value corresponds to defender strategies, while the lower value corresponds to attacker strategies.
- 2.3 Value and Strategies: The capture basin is the zero sublevel set of the upper or lower value function, depending on which player is allowed to use nonanticipative strategies.Under fixed controls, the same subzero characterization identifies trajectories that reach the target without prior constraint violation.
3. THE DOUBLE-OBSTACLE ISAACS EQUATION
The paper extends reach-avoid value-function analysis to a double-obstacle Hamilton-Jacobi-Isaacs variational inequality. A dynamic programming principle supports the viscosity-solution characterization and uniqueness under stated regularity assumptions.
- Bellman’s principle of optimality propagates the reach-avoid value backward over a short time interval while accounting for future game outcomes.The dynamic programming principle separates local payoff evolution from the value propagated from the remainder of the game.
- The upper and lower Hamiltonians encode the players’ opposing optimization over their respective input sets.The upper Hamiltonian minimizes over the defender’s input, while the lower Hamiltonian maximizes over the attacker’s input.
- The value function is characterized as the unique viscosity solution of a double-obstacle Hamilton-Jacobi-Isaacs variational inequality.The proof establishes both viscosity subsolution and supersolution properties, then invokes comparison and uniqueness results.
- The double-obstacle structure combines the payoff obstacle and the constraint discriminator in the variational inequality.The displayed terms include l(x,t) − V(x,t) and g(x,t) − V(x,t), with terminal value defined by a maximum.
- The viscosity proof derives contradictions from violations of the subsolution or supersolution inequalities, completing the characterization.The argument is presented for the upper value and Hamiltonian; the lower-value proof is stated to be analogous.
- Lipschitz continuity of the dynamics, payoff, and discriminator is sufficient for the theorem, while uniform continuity still supports a viscosity-sense equation.The paper notes that the theorem’s assumptions are stronger than necessary and can be relaxed.
4. NUMERICAL IMPLEMENTATION
The numerical implementation solves the time-varying variational inequality by backward propagation on a spatial-temporal grid. Its additional obstacle update and time dependence preserve computational similarity to the time-invariant method.
- The algorithm computes the numerical value function through a three-step update rule while propagating backward over discrete time steps.The grid uses decreasing times T = t_0 > t_1 > ... > t_n = 0, with discretized payoff and discriminator functions.
- The numerical Hamiltonian uses the Lax-Friedrichs approximation, with a stable choice of α over a hypercube containing the relevant derivative values.The implementation also uses right and left spatial derivative approximations.
- The example implementation uses fifth-order WENO spatial derivatives and third-order TVD Runge-Kutta time integration.Lower-order approximations can also provide stable, less accurate solutions at lower computational expense.
- The method computes time-varying backward reachable sets at essentially no additional cost compared with the time-invariant case.The overhead consists of the third update step and allowing the payoff, discriminator, and Hamiltonian to depend on time.
- Optimal feedback actions are obtained during the Hamiltonian minimax computation and yield guaranteed winning strategies inside each player’s winning region.The attacker’s winning region is the reach-avoid set, while the defender’s is its complement.
5. NUMERICAL EXAMPLES
Two examples evaluate the proposed method on time-varying reachability and reach-avoid games. The numerical solution converges against an analytic boundary, while the augmentation-free approach matches state augmentation with substantially lower computation time.
- 5.1 Example 1: Reachability Problem: The first example models a vehicle reaching a downward-moving square target while avoiding a downward-moving square obstacle.The vehicle speed is 0.5, the target speed is 1.5, and the obstacle speed is 1.
- 5.1 Example 1: Reachability Problem: The computed capture basin changes backward in time as additional travel time allows more target-reaching states, while the obstacle blocks or pinches the basin.At earlier times, nearby states may route around the obstacle, but a triangular region beneath it remains excluded.
- 5.1.1 Analytic Solution: The analytic boundary is derived geometrically from distinct segments corresponding to straight paths, rounded corners, obstacle avoidance, and states that cannot avoid interception.Optimal trajectories may reach the moving target at intermediate or final positions, barely miss the obstacle, or be blocked by it.
- 5.1.2 Convergence: The numerical scheme converges across grids: mean boundary error is approximately one-tenth of grid spacing and maximum error approximately one-half.Errors are measured using signed distances from approximately 20 000 analytic boundary points to the numerical boundary.
- 5.2 Example 2: Reach-Avoid Game: The second example compares four-dimensional state augmentation with the proposed three-dimensional augmentation-free method across defender positions.The two methods produce boundaries well within one grid cell, but computation takes approximately 1 hour and 50 minutes versus approximately 3 minutes.
- 5.2 Example 2: Reach-Avoid Game: The augmentation-free computation is two orders of magnitude faster while providing essentially the same reach-avoid set.Defender position changes whether the attacker can use gaps around the obstacle, producing asymmetric capture-basin extensions.
6. CONCLUSION
The paper extends Hamilton-Jacobi reach-avoid analysis to time-varying dynamics, targets, and constraints. The formulation supports practical differential-game and optimal-control applications while retaining computational complexity equivalent to time-invariant methods.
- 6. CONCLUSION: The paper presents a Hamilton-Jacobi extension for reach-avoid problems with time-varying dynamics, targets, and constraints.The work discusses applications including pursuit-evasion, differential games, and safety certificates for dynamical systems.
- 6. CONCLUSION: The method can provide guarantees for collision avoidance in dynamic environments with multiple moving obstacles.This consequence is stated within the paper's supported applications of the formulation.
- 6. CONCLUSION: Numerical implementations have computational complexity equivalent to existing techniques for time-invariant systems, avoiding time as an additional state variable.The paper contrasts this with approaches whose numerical complexity grows exponentially with problem dimensionality.
- 6. CONCLUSION: The authors intend to apply the formulation to large-scale cooperative and adversarial multi-agent systems.They aim to develop solutions that scale linearly rather than exponentially with multi-agent network complexity.