Hamilton-Jacobi formulation for reach-avoid differential games

Kostas Margellos; John Lygeros

Source-linked AI summary

Hamilton-Jacobi formulation for reach-avoid differential games

Kostas Margellos, John Lygeros

arXiv:0911.4625v1Nov 24, 2009math.OC

TL;DR

Reach-avoid problems with nonlinear dynamics, competing inputs, and state constraints are difficult for earlier formulations because of linear-system restrictions or discontinuous Hamiltonians. This paper introduces a continuous-Hamiltonian differential-game framework and demonstrates it on two-aircraft collision avoidance with Target Window constraints and wind disturbance. The formulation provides numerically computed reach-avoid sets, while the aircraft application uses simplifying abstractions and remains slated for validation with more realistic simulations.

Problem
Earlier reach-avoid computations are restricted to linear systems or face numerical difficulties because the Hamiltonian can be discontinuous.
Method
The paper formulates nonlinear reach-avoid problems with competing inputs as differential games and characterizes their value functions using continuous Hamiltonians and viscosity-solution variational inequalities.
Results
The approach was numerically applied to a two-aircraft collision-avoidance scenario with Target Window constraints and wind disturbance.
Takeaways & Limitations
The framework computes reach-avoid sets for nonlinear systems with state constraints and competing inputs using existing numerical tools.
Takeaways & Limitations
The aircraft reachability computation uses a simplified model, and future work proposes validation with realistic aircraft, flight-management, flight-plan, and wind-uncertainty models.

Abstract

from arXiv · show

A new framework for formulating reachability problems with competing inputs, nonlinear dynamics and state constraints as optimal control problems is developed. Such reach-avoid problems arise in, among others, the study of safety problems in hybrid systems. Earlier approaches to reach-avoid computations are either restricted to linear systems, or face numerical difficulties due to possible discontinuities in the Hamiltonian of the optimal control problem. The main advantage of the approach proposed in this paper is that it can be applied to a general class of target hitting continuous dynamic games with nonlinear dynamics, and has very good properties in terms of its numerical solution, since the value function and the Hamiltonian of the system are both continuous. The performance of the proposed method is demonstrated by applying it to a two aircraft collision avoidance scenario under target window constraints and in the presence of wind disturbance. Target Windows are a novel concept in air traffic management, and represent spatial and temporal constraints, that the aircraft have to respect to meet their schedule.

1. Introduction

The paper develops a reach-avoid framework for nonlinear systems with competing inputs and state constraints, addressing limitations of earlier numerical formulations. It applies the approach to aircraft collision avoidance under spatial and temporal Target Window constraints and wind disturbance.

1. Introduction: Earlier reach-avoid methods are restricted to linear systems or face numerical difficulties from potentially discontinuous Hamiltonians.These limitations arise in formulations for systems with state constraints.
1. Introduction: The paper formulates reach-avoid sets for nonlinear control systems with competing inputs as optimal control problems.The disturbance seeks to steer trajectories away from the target while the control input seeks to reach it without violating constraints.
1. Introduction: The proposed framework covers target hitting at the terminal time and at some time within a specified horizon.Both formulations are treated as pursuit-evasion games with a worst-case value function.
1. Introduction: The framework is demonstrated in a two-aircraft collision-avoidance problem with spatial and temporal Target Window constraints and wind disturbance.Target Windows encode constraints that aircraft must respect to meet their schedules.
1. Introduction: The paper characterizes the resulting value functions through variational inequalities and presents a realistic-data application after posing the differential games.The paper’s sections cover problem formulation, value-function characterization, simulation, and conclusions.

2. Differential games and Reach-Avoid problems

The paper defines reach-avoid differential games using constrained trajectories and non-anticipative strategies, then links their initial-state sets to value-function level sets. It extends the formulation from terminal-time reachability to reaching the target at any time within the horizon.

2. Differential games and Reach-Avoid problems: The continuous-time system uses dynamics f(x,u,v), target function l, and state-constraint function h under boundedness and Lipschitz-continuity assumptions.The control and disturbance inputs range over compact sets, and the assumptions ensure a unique system solution.
2. Differential games and Reach-Avoid problems: A non-anticipative strategy maps disturbance signals to control signals while preserving agreement up to every time at which disturbances agree.This information pattern defines the admissible strategy class Γ[t,T].
2. Differential games and Reach-Avoid problems: The terminal-time reach-avoid problem seeks a strategy that reaches the closed target R at T while avoiding the open obstacle A throughout [t,T].The sets are encoded by R={x | l(x)≤0} and A={x | h(x)>0}.
2. Differential games and Reach-Avoid problems: The differential-game value function minimizes over non-anticipative strategies and maximizes over disturbances the larger of terminal target cost and accumulated constraint cost.Its terminal condition is V(x,T)=max{l(x),h(x)}.
2. Differential games and Reach-Avoid problems: The terminal-time reach-avoid set equals the nonpositive level set of the value function: RA(t,R,A)={x∈R^n | V(x,t)≤0}.This equivalence follows by separating the terminal target condition from the requirement to avoid A along the trajectory.
2. Differential games and Reach-Avoid problems: The within-horizon problem allows trajectories to reach R at some time τ1∈[t,T] while avoiding A until that hitting time.An augmented input and pseudo-time construction are used to formulate this variant.
2. Differential games and Reach-Avoid problems: For the within-horizon formulation, Proposition 2 identifies the reach-avoid set with the nonpositive level set of the augmented value function.The proposition states gRA(τ,R,A)={x∈R^n | eV(x,τ)≤0}.

3. Characterization of the value function

The paper characterizes reach-avoid value functions for competing-input systems through variational inequalities, establishing boundedness, Lipschitz continuity, and unique viscosity-solution results.

Basic properties: The value function is bounded and Lipschitz continuous in both state and time.There is a constant C such that |V(x,t)| ≤ C and |V(x,t) − V(ˆx,ˆt)| ≤ C(|x − ˆx| + |t − ˆt|).
Variational inequality for V: Dynamic programming yields a variational-inequality characterization of V using the Hamiltonian defined by competing disturbance and control inputs.The Hamiltonian is introduced through a supremum over v and infimum over u of p^T f(x,u).
Variational inequality for V: The characterization includes the terminal condition V(x,T) = max{l(x), h(x)}.The value function also satisfies V(x,t) ≥ h(x) throughout the time horizon.
Variational inequality for eV: The transformed value function eV is the unique viscosity solution of a second variational inequality with the same terminal condition.The paper states this as Theorem 2 and establishes equivalence between the two variational inequalities.
Variational inequality for eV: The two variational inequalities are equivalent because the transformed Hamiltonian satisfies eH(x,p) = min{0, H(x,p)}.This equivalence transfers the viscosity-solution characterization from V to eV.

4. Case study: Collision Avoidance in Air Traffic Management

The case study models aircraft following predetermined flight plans while satisfying spatial-temporal Target Windows and avoiding conflicts under wind disturbance. A two-stage reach-avoid computation identifies states that can reach the windows safely, using simplified aircraft dynamics and parallel per-aircraft calculations.

Air traffic management setting: Target Windows impose spatial and temporal constraints that aircraft must satisfy during the flight plan.They support punctuality and predictability by defining commitments to deliver aircraft within specified windows.
Aircraft model: Each aircraft follows a predetermined flight plan represented by waypoints and flight-plan segments.The model tracks the current segment using a discrete state and represents horizontal progress, altitude, and time as continuous states.
Aircraft model: The aircraft model uses heading-dependent horizontal motion, flight-path-angle modes, altitude-dependent airspeed, bounded control variation, and bounded wind disturbance.The simulations allow airspeed to vary within 10% of nominal values and use wind bounded by 12 m/s.
Reach-avoid formulation: The reach-avoid objective is to find initial states from which a non-anticipative strategy reaches an aircraft’s Target Window despite wind while avoiding conflict with another aircraft.Conflict is defined through violation of the protected separation zone surrounding an aircraft.
Reach-avoid formulation: The computation proceeds in two stages: first reach each aircraft’s spatial window during its time window, then reach that set while avoiding dynamically detected conflicts.The first stage computes Rj; the second computes initial states that can reach Rj while avoiding the other aircraft.
Simulation results: For two intersecting flight plans with a 30sec entry difference, backward reachable tubes contain states that can reach the Target Windows, while conflict detection removes unsafe regions.The resulting safe sets are computed as two parallel 2D problems rather than one 4D computation.

5. Concluding Remarks

The paper presents a reachability/game-theoretic framework for nonlinear systems with state constraints and competing inputs, retaining Hamiltonian continuity for numerical solution. It formulates target-window conflict avoidance as a reach-avoid problem and computes it numerically.

The framework solves nonlinear reach-avoid problems with state constraints and competing inputs while maintaining continuity in the system Hamiltonian.This continuity is reported as advantageous for numerical solution.
The desired set, represented by a Target Window, is formulated as a reach-avoid problem while avoiding conflict with other aircraft.
The aircraft conflict-avoidance reach-avoid problem is computed numerically using existing tools.
Future work includes using reach-avoid bounds for conflict resolution through optimization of a cost criterion.

A.1. Proof of Proposition 2.

The proof establishes equality between the reach-avoid set and the nonpositive sublevel set of the augmented value function by proving both set inclusions through contradiction.

The first inclusion shows that every reach-avoid state has augmented value eV(x,τ) ≤ 0.Assuming a positive value yields a disturbance input violating either the target or obstacle condition, contradicting reachability and avoidance.
For a reach-avoid state, a control strategy reaches R at some τ1 while avoiding A throughout the preceding interval.
The proof constructs a combined control input that freezes the trajectory after target attainment while preserving non-anticipativity.
The two contradiction cases respectively address failure to reach the target and violation of the state constraint.
The second inclusion assumes eV(x,t) ≤ 0 and derives a contradiction from any disturbance strategy that prevents reaching R or causes entry into A.

B.1. Proof of Lemma 1.

The proof establishes the dynamic-programming relationship for the value function by decomposing controls and disturbances across an intermediate time and proving both inequalities up to vanishing error.

The proof aims to show V(x,t) ≤ W(x,t) + 2ϵ and V(x,t) ≥ W(x,t) − 3ϵ, then concludes V(x,t) = W(x,t).
The first inequality selects an initial strategy and then applies a continuation strategy after the intermediate time.
Controls and disturbances are split at t + α, and a composite non-anticipative strategy is formed from the strategies on the two subintervals.Uniqueness of trajectories makes the composite trajectory agree with the corresponding first- and second-stage trajectories.
The obstacle maximum and terminal target cost are evaluated over the corresponding time intervals when comparing the decomposed trajectories.
The reverse inequality fixes a full-horizon strategy and restricts it after t + α while splicing disturbance inputs across the two intervals.

B.2. Proof of Lemma 2.

The proof establishes continuity estimates for the value function in state and time by combining near-optimal strategies with Lipschitz bounds on the dynamics and cost functions.

The value function is bounded because the terminal cost l and obstacle function h are bounded.
The state-continuity proof compares trajectories from x and ˆx using a near-optimal strategy and the Lipschitz constant Cf of the dynamics.The Gronwall-Bellman lemma supplies a trajectory-distance bound.
The proof separates cases according to whether the terminal cost or the maximum obstacle value dominates the objective.
The time-continuity proof shifts trajectories between initial times t and ˆt and restricts the original strategy to the later interval.
A symmetric argument completes the continuity proof in the opposite time direction.

Appendix C.

Appendix C presents an algorithm summarizing the Reach-Avoid computation described in Section IV. The presentation assumes that the target windows do not overlap.

The appendix provides an algorithmic summary of the Reach-Avoid computation.The summarized computation is described in Section IV.
The summarized procedure corresponds to the Reach-Avoid computation described in Section IV.
The algorithm assumes that the target windows do not overlap.

Algorithm 1 Reach-Avoid computation

Algorithm 1 initializes the time interval, processes sectors and conflicts, solves the value-function equations over decreasing time, and updates the computation across target-window conditions.

Initialization: The procedure initializes the terminal and initial times from the target-window times and defines the initial reachable sets.
Backward iteration: It iterates backward from T to t0 while processing aircraft sectors and identifying pairs in conflict.
Value-function update: The procedure solves the value-function equations in the relevant target-window intervals and repeats the update steps with V instead of eV when required.
Conflict processing: For each conflicting pair, the algorithm defines a box Aji containing the conflict set Cji through the function hji.
Value-function update: The value function is updated using the maximum of hj and the auxiliary value function eV, with empty sets assigned when the condition does not apply.