PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Decomposition of Value Functions for Two-Player Games in Hamilton-Jacobi Reachability

Dylan Hirsch, William Sharpless, Sylvia Herbert

arXiv:2608.27654v1eess.SY

TL;DR

HJR decomposition methods for composite tasks do not generally carry over from one-player to two-player settings. This note establishes a two-player continuous-time, finite-horizon analogue under a critical monotonicity assumption, demonstrates failure without it, and applies the result across several tasks.

  • Problem

    One-player value-function decompositions for composite HJR tasks do not directly translate to settings with adversarial disturbances.

  • Method

    The paper develops and proves a two-player, continuous-time, finite-horizon analogue of a prior decomposition result, centered on a downstream monotonicity assumption.

  • Results

    The decomposition holds under the monotonicity condition, supports formulas such as V[J] = VRA[˜r, q1; T], and recovers or extends several prior task-specific results.

  • Takeaways & Limitations

    The single decomposition formula can be used to analyze multiple two-player tasks involving ordered or sequential reaching while respecting constraints.

  • Takeaways & Limitations

    The two-player decomposition may fail when the downstream monotonicity condition is not satisfied.

Abstract

from arXiv · show

Hamilton-Jacobi reachability (HJR) is an important framework in safe control theory. HJR provides theoretical tools and numerical methods to obtain value-functions for tasks involving target-reaching and obstacle-avoidance. A recent work proposed an algebraic framework to scale to complex, composite tasks via decomposing the value functions of the composite tasks into value functions for the fundamental tasks traditionally studied in HJR, all in the one-player setting. Many of these decomposition results, however, do not directly translate to the two-player setting. In this technical note, we nevertheless show that one of the previous work's key results for analyzing various tasks involving reaching multiple targets while obeying constraints still holds in the two-player setting, so long as a critical monotonicity assumption is satisfied. In particular, we detail the analogous result and its proof (which structurally differs from the one-player case), we show via a counter-example what can go wrong if this monotonicity assumption is not satisfied, and we show how the analysis of a variety of tasks can be performed using this result. We note that, whereas the prior work considered discrete-time, infinite-horizon tasks, which are more standard in reinforcement learning, we here consider continuous-time, finite-horizon tasks, which are more standard in HJR.

I. INTRODUCTION

HJR decomposes complex tasks into fundamental-task value functions, but the one-player rule does not generally extend to two-player games. The paper provides a two-player analogue requiring monotonicity and demonstrates its scope and failure mode.

  • HJR computes value functions for goal-reaching and obstacle-avoidance tasks using differential-game theory and numerical tools.
  • A prior algebraic framework decomposes composite-task value functions into fundamental-task value functions in the one-player setting.
  • The upstream–downstream decomposition uses three steps: solve downstream, construct a time-varying target, then solve an upstream reach-avoid problem.
  • The paper derives the proper two-player analogue for continuous-time, finite-horizon tasks, unlike the prior discrete-time, infinite-horizon setting.
  • Two-player decomposition requires a downstream monotonicity assumption, and a counter-example shows failure without it.
  • A single formula recovers and extends decomposition results for multiple tasks, including reach-always-avoid, reach-reach, and sequential reach-avoid problems.

II. SETUP AND BACKGROUND

The setup and background section reproduces the general HJR setup for completeness.

  • The article states that its setup and background are almost identical to a previously described general HJR setup.The material is reproduced for completeness.

A. Dynamics

The dynamics use a state, control, and disturbance with compact input sets and regularity assumptions that guarantee globally existing, unique trajectories.

  • The system dynamics are represented by f, with state x, control input u, and disturbance input d.The dynamics map the state and inputs over time to the state space.
  • The control and disturbance sets U and D are compact.
  • The dynamics are continuous in state and inputs and measurable in time.
  • A linear-growth bound limits the dynamics by K(1 + ∥x∥).
  • The dynamics are locally Lipschitz in the state uniformly over inputs and time.

B. Signals and trajectories

Control and disturbance signals are measurable functions, and each signal pair defines a unique Carathéodory state trajectory from an initial state and time.

  • U and D denote the sets of all measurable control and disturbance signals, respectively.
  • A control signal and disturbance signal determine a state trajectory from initial state x0 at time t0.
  • The trajectory is the Carathéodory solution satisfying the initial condition x(t0) = x0.
  • The resulting trajectory is a unique locally absolutely continuous map from R to R^n.

C. Performance functionals

Performance functionals assign scores to trajectories based on task-start time, with positive values indicating task satisfaction in HJR. The framework includes reach, avoid, and reach-avoid functionals and commonly requires past independence.

  • Performance functionals: A performance functional J assigns a score to trajectory x based on the time t when the task begins.The allowed start times form a set T representing when task initiation is reasonable.
  • Performance functionals: In HJR, J(x, t) > 0 exactly when trajectory x satisfies the task starting at time t.Robustness metrics for temporal-logic specifications can use the sign of the performance functional to encode qualitative satisfaction.
  • Performance functionals: The principal examples are reach, avoid, and reach-avoid performance functionals defined from continuous target and constraint functions.These functionals are defined over continuous trajectories and times no later than a horizon T.
  • Technical condition: A performance functional is past-independent when trajectories agreeing from task-start time t onward receive the same score at t.The reach, avoid, and reach-avoid functionals are continuous and past-independent.

D. Differential games and value functions

The differential-game value function captures optimal controller performance against a disturbance player under a non-anticipative information structure. Its sign determines task satisfiability, and continuity of the performance functional carries over to the value function.

  • Differential games: The controller maximizes a performance functional while the disturbance player minimizes it in the differential game.This defines the opposing objectives underlying the two-player value function.
  • Information pattern: A disturbance strategy is non-anticipative when its decisions up to time t depend only on control inputs up to t.The admissible strategy set Δ consists of all non-anticipative disturbance strategies.
  • Value functions: V[J](x, t) represents the performance score obtained when both players act optimally from state x at time t.The value function is defined under the non-anticipative information structure.
  • Value functions: If J is continuous, V[J] is continuous; finite upper or lower bounds on J also transfer to V[J].This is stated in Lemma 1 and is used for the value functions considered in the note.
  • Task satisfaction: A positive value guarantees that for every disturbance strategy some control achieves a positive task score, while a negative value guarantees a disturbance strategy forcing a negative score.Thus, the sign of V[J](x, t) determines whether the task can be satisfied from state x at time t.

III. DECOMPOSITION THEOREM

The decomposition theorem extends a key one-player result to two-player, continuous-time, finite-horizon HJR tasks, provided a downstream monotonicity condition holds. It computes the composite value through a downstream value function and a modified reach-avoid target, while applications recover several prior decompositions.

  • III. DECOMPOSITION THEOREM: The theorem is the two-player, continuous-time, finite-horizon analogue of a prior decomposition result, with monotonicity as the critical additional assumption.The assumption is uniquely needed in the two-player setting.
  • Monotonicity assumption: The monotonicity requirement says that obeying constraints until a later intermediate time and then performing the downstream task must not become easier.For downstream goal-reaching before T, later intermediate times leave less time to reach all goals, making the task more challenging or no less challenging.
  • Theorem 1: Theorem 1 establishes that the composite performance functional is continuous and past-independent, and its value decomposes through a reach-avoid value function.The modified target is ˜r = min{r, V[J0]}.
  • Task setup: The composite task first completes an upstream reach-avoid task at an intermediate time and then completes a downstream task.The downstream performance functional is continuous, real-valued, past-independent, and defined on X × R≤T.
  • Three-step computation: Computing V[J0], forming ˜r := min{r, V[J0]}, and computing VRA[˜r, q; T] yields exactly the composite value V[J].The final reach-avoid value can be computed by solving a Hamilton-Jacobi-Isaacs partial differential equation.
  • Counter-example: Without the monotonicity condition, the decomposition may fail in the two-player setting, as demonstrated by a counter-example.The counter-example uses an ordered double reach-avoid game whose downstream obstacle is not a subset of the upstream obstacle.
  • Applications: The theorem recovers and extends multiple literature decompositions, including reach-always-avoid, reach-reach, and sequential reach-avoid problems.The note applies the general formula to several previously studied task decompositions.

IV. APPLICATION OF THE DECOMPOSITION TO ORDERED AND UNORDERED MULTI-REACH-AVOID GAMES

The decomposition formula is applied to ordered and unordered multi-reach-avoid games, as well as reach-always-avoid tasks. These applications express composite value functions through reach-avoid value functions with constructed target functions.

  • Applications: The section derives decomposition formulas for ordered multiple reach-avoid, unordered multiple reach-avoid, and reach-always-avoid tasks.The ordered task allows constraints to change after a target is reached, while the unordered task keeps constraints unchanged; reach-always-avoid requires remaining within constraints after reaching the target.
  • Scope: The presentation is limited to two targets and two obstacles in the ordered case and two targets in the unordered case.Generalizations to N targets are indicated as following a similar proof structure to be detailed in future work.
  • Ordered Double Reach-Avoid: For ordered double reach-avoid, the construction assumes continuous target and constraint functions with q1 ≤ q2.The ordered performance functional uses separate target-reaching intervals and corresponding constraint minima.
  • Ordered Double Reach-Avoid: The ordered value function is obtained as V[J] = VRA[˜r, q1; T], after defining the downstream reach-avoid performance functional J0.The proof expands the composite objective over target-reaching times and applies the decomposition theorem.
  • Unordered Double Reach-Avoid: For unordered double reach-avoid, the new target function is ˜r = max{min{r1, VRA[r2, q; T]}, min{r2, VRA[r1, q; T]}}.This takes the better of the two possible target orders while using the shared constraint q.
  • Unordered and Reach-Always-Avoid: The unordered value function and the reach-always-avoid value function both reduce to reach-avoid value functions with constructed targets.For unordered double reach-avoid, V[J] = VRA[˜r, q; T]; the reach-always-avoid result likewise gives V[J] = VRA[˜r, q; T].

V. IMPORTANCE OF THE MONOTONICITY CONDITION

The two-player decomposition can fail without the monotonicity condition, as shown by an ordered double reach-avoid counter-example where the decomposed and composite values disagree.

  • Counter-example setup: The counter-example uses an ordered double reach-avoid task with sequential goals G1 and G2, obstacles O1 and O2, and horizon T = 5.The system must reach G1 while avoiding O1, then reach G2 while avoiding O2.
  • Counter-example setup: The example uses the scalar system ẋ = d with disturbance bound D = [−1, 1] and explicitly defined goal and obstacle regions.There is no explicit control action; equivalently, U = {0}.
  • Failure of decomposition: Because the disturbance can force O2 from any point in G1,a, VRA[r2, q2; T] is negative throughout G1,a.This makes the downstream value unsuitable as a monotone continuation value for the decomposition.
  • Failure of decomposition: Along the disturbance trajectory d1(·) := 1, the constructed target ˜r := min{r1, VRA[r2, q2; T]} remains negative, yielding VRA[˜r, q1; T](0, 0) < 0.The decomposed reach-avoid value therefore predicts failure from the origin.
  • Failure of decomposition: Nevertheless, the ordered double reach-avoid task succeeds from (0, 0) regardless of the disturbance, with V[JODRA](0, 0) ≥ 0.The contradiction demonstrates that the decomposition conclusion need not hold when monotonicity is absent.
  • Role of the assumption: The counter-example also explains why Corollary 1 requires q1 ≤ q2: here O2 is not a subset of O1, so q1 ≰ q2.The downstream obstacle is not contained in the upstream obstacle.

A. Proof of Theorem 1

The proof establishes the two-player decomposition by constructing composite adversary and control strategies, proving their non-anticipativity, and bounding the resulting value in both directions.

  • Regularity: Continuity of the composite value follows from continuity of r, q, and J0 together with uniform bounds in time.The result is locally uniform in time for the spatial variable.
  • Strategy construction: The proof defines a composite adversary strategy by switching from a primary strategy to a secondary strategy at a trajectory-dependent time.The construction uses α before the switch and β[y, s] afterward.
  • Strategy construction: The composite strategy is shown to be non-anticipative by comparing switch times and post-switch states for control signals that agree up to time s.Equal switch times and states allow the secondary strategies to produce matching disturbances.
  • Two-sided value bound: The upper-bound direction builds a near-optimal composite adversary strategy and obtains V[J](x, t) ≤ VRA[˜r, q; T](x, t) + 3ε.The bound uses the monotonicity assumption and past-independence of J0.
  • Two-sided value bound: The lower-bound direction constructs a near-optimal control by concatenating primary and secondary signals, yielding V[J](x, t) ≥ VRA[˜r, q; T](x, t) − 2ε.The secondary control begins at the selected intermediate time and state.

B. Proof of Corollary 2

The proof of Corollary 2 verifies monotonicity, identifies the transformed target function, and applies Theorem 1 to obtain the stated value decomposition.

  • Proof setup: The proof sets J1 = JRA[r1, q; T], J2 = JRA[r2, q; T], J0 = min{J1, J2}, and r = max{r1, r2}.These definitions reduce the corollary to the general composite-task theorem.
  • Monotonicity: Step 1 proves that the required monotonicity condition holds by considering the relative values of r1 and r2.The proof treats the case r1 ≥ r2 and invokes an analogous argument when r2 ≥ r1.
  • Composite representation: Step 2 establishes the composite performance representation by comparing ordered intermediate times and the associated constraint and target values.The proof treats both s1 ≤ s2 and s1 ≥ s2 cases.
  • Final decomposition: Applying Theorem 1 gives the exact decomposition V[J] = VRA[min{r, V[J0]}, q; T].Thus the corollary expresses the composite value through a reach-avoid value function with the transformed target.
  • Transformed target: The transformed target is ˜r(x, t) = min{r(x, t), V[J0](x, t)}.The proof shows equivalent expressions using J1 and J2 before identifying this target.
Loading 2608.27654v1…