PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Koopman-Hopf Formula for Reachability with Adversary

Sarang Sutavani, Umesh Vaidya

arXiv:2609.06878v1eess.SYcs.SYmath.OC

TL;DR

HJI reachability for nonlinear adversarial systems is difficult because grid-based methods scale exponentially with state dimension. This paper lifts the drift into Koopman eigenfunction coordinates and approximates a state-independent reachability optimization; numerical examples show tractable reachable-set approximations, including a six-dimensional case where a grid baseline hit memory limits.

  • Problem

    Grid-based numerical solutions of HJI equations scale exponentially with state dimension, restricting classical dynamic-programming methods to low-dimensional systems.

    Source: §I · p. 1

  • Method

    The framework lifts nonlinear drift into Koopman eigenfunction coordinates, approximates transformed input directions, and uses path-integral eigenfunction computation to avoid spatial-grid PDE solves.

    Source: §I · p. 1, §VII · p. 6

  • Results

    Numerical examples yield tractable reachable-set approximations; in the six-dimensional arm example, LSM failed from memory at 21 nodes per dimension while SKH avoided the 85,766,121-node grid.

    Source: §VII · p. 6, B. N-Link Robotic Arm · p. 6

  • Takeaways & Limitations

    With only the n principal eigenfunctions, the framework preserves the original system dimension while enabling pointwise value-function evaluation without constructing a high-dimensional HJI grid.

    Source: §I · p. 1, §VII · p. 6, B. N-Link Robotic Arm · p. 6

    The dimensionality burden shifts to spectral approximation involving trajectory simulations rather than disappearing.

    Source: §I · p. 1

Abstract

from arXiv · show

This paper develops a spectral Koopman-Hopf framework for adversarial reachability analysis of nonlinear systems. By lifting the nonlinear drift dynamics into Koopman eigenfunction coordinates, the proposed approach transforms the original state-dependent Hamilton-Jacobi-Isaacs (HJI) equation into an approximate state-independent optimization problem in spectral coordinates. The transformed control and disturbance directions are approximated using least-squares spectral projections, and upper and lower bounds on the transformed Hamiltonian are used to derive corresponding bounds on the value function and backward reachable sets. Koopman eigenfunctions are computed using a path-integral-based Galerkin framework that avoids spatial discretization of the associated eigenfunction PDEs. Numerical examples demonstrate tractable approximation of backward reachable sets for nonlinear adversarial systems.

I. INTRODUCTION

The paper addresses the dimensionality limits of HJI reachability by using Koopman eigenfunction coordinates to formulate adversarial reachability as a spectral Hopf-type problem. The preliminaries establish that these eigenfunctions evolve linearly along nonlinear trajectories and can serve as local coordinates.

I. INTRODUCTION

  • Grid-based HJI methods scale exponentially with state dimension, while classical Hopf approaches face state-dependent Hamiltonians and adversarial min-max structure.Some generalized Hopf approaches also require auxiliary optimization along characteristics or added dual-formulation complexity.Source: §I · p. 1
  • Under spectral input rigidity, lifting the drift into Koopman eigenfunction coordinates maps control and disturbance directions to constant matrices and yields a state-independent Isaacs Hamiltonian.The resulting representation supports a finite-dimensional Hopf-type approximation of the value function.Source: §I · p. 1
  • A path-integral construction computes Koopman eigenfunctions through trajectory evaluations instead of solving their PDEs on a spatial grid.The approach shifts the dimensionality burden from state-space discretization to spectral approximation involving trajectory simulations.Source: §I · p. 1
  • Using only the n principal eigenfunctions preserves the original system dimension, while retaining N > n modes improves rigidity at higher optimization cost.Numerical examples demonstrate tractable reachable-set computation for nonlinear systems with nontrivial drift and adversarial inputs.Source: §I · p. 1

II. PRELIMINARIES: KOOPMAN SPECTRAL THEORY

  • Along trajectories, Koopman eigenfunctions evolve exponentially in time even when the underlying state dynamics are nonlinear.Near a hyperbolic equilibrium, the n principal eigenfunctions have eigenvalues matching those of the linearization and define local coordinates.Source: §II · p. 2

III. ADVERSARIAL REACHABILITY FORMULATION

The section formulates reachability as a finite-horizon differential game with constrained control and adversarial disturbance. Its value function characterizes whether the controller can force the state into the target by the terminal time.

III. ADVERSARIAL REACHABILITY FORMULATION

  • Indicator running costs enforce the hard control and disturbance constraints almost everywhere over the finite horizon.The running cost is finite only when the inputs remain in their admissible sets almost everywhere.Source: §III · p. 2
  • The value function is equivalent to a constrained terminal-cost game in which the controller seeks to reach the target by time T despite the worst-case disturbance.The admissible control and disturbance sets are compact, convex, and contain the origin.Source: §III · p. 2
  • The backward reachable set is the zero sublevel set of the value function, so V(x,t) ≤ 0 characterizes states from which the controller can guarantee reaching the target.The terminal cost is negative inside the target and zero on its boundary.Source: §III · p. 2

A. Hamiltonian and HJI PDE

Under the Isaacs condition, dynamic programming yields an HJI equation whose Hamiltonian takes the control minimum and disturbance maximum. The value function satisfies this PDE in the viscosity sense and determines the backward reachable set.

A. Hamiltonian and HJI PDE

  • The Isaacs condition equates the min-max and max-min Hamiltonians, allowing the dynamic programming principle to yield the HJI equation for the value function.The value function satisfies the resulting PDE in the viscosity sense.Source: A. Hamiltonian and HJI PDE · p. 2
  • The Hamiltonian optimizes the state-gradient pairing with the dynamics over admissible control and disturbance inputs, with control minimized and disturbance maximized.The drift term is independent of those inputs and does not affect their optimization.Source: A. Hamiltonian and HJI PDE · p. 2
  • When the optimizers exist, the feedback policies follow from the Hamiltonian, and the backward reachable set is the zero sublevel set of the value function.For common compact convex input sets, the optimizers admit closed-form projection or saturation expressions.Source: A. Hamiltonian and HJI PDE · p. 2

IV. SPECTRAL KOOPMAN HOPF FORMULA

The spectral Koopman-Hopf formulation uses Koopman coordinates to remove state dependence from the Hamiltonian. It introduces time-varying spectral coordinates and truncated eigenfunction dictionaries, then represents transformed inputs for approximation or bounding.

IV. SPECTRAL KOOPMAN HOPF FORMULA

  • Koopman spectral coordinates are used to eliminate state dependence in the Hamiltonian and obtain a tractable HJI representation.The time-varying coordinate X = e^(-Λt)Φ(x) makes the drift stationary in spectral space.Source: §IV · p. 3
  • The time-varying spectral coordinate is formed by evolving the principal eigenfunction map with e^(-Λt), making the drift stationary.The principal map satisfies the Koopman eigenfunction relation with the drift.Source: §IV · p. 3

A. Transformed Input Directions in Spectral Coordinates

  • The truncated eigenfunction dictionary combines principal eigenfunctions with higher-order eigenfunctions generated by the Koopman algebra property.Modes are ordered by the magnitude of the real part of their associated eigenvalues, with principal modes dominant near the equilibrium.Source: A. Transformed Input Directions in… · p. 3
  • The framework defines transformed control and disturbance directions in the truncated spectral coordinates.The transformed Hamiltonian is obtained by substituting these directions into the Hamiltonian.Source: A. Transformed Input Directions in… · p. 3
  • After transformation, the Hamiltonian remains state dependent through the transformed control and disturbance matrices.This residual dependence motivates approximating or bounding those matrices with state-independent representations.Source: A. Transformed Input Directions in… · p. 3
  • The proposed framework targets state-independent representations of the transformed inputs to support the spectral Koopman-Hopf formulation.The transformed Hamiltonian's residual state dependence runs through the control and disturbance matrices.Source: A. Transformed Input Directions in… · p. 3, §IV · p. 3

B. Approximate Spectral Rigidity

The method approximates transformed control and disturbance directions with constant spectral projections, yielding a state-independent Hamiltonian and a pointwise Hopf approximation. Its accuracy depends on projection residuals, while more modes can improve rigidity at higher optimization cost.

B. Approximate Spectral Rigidity

  • Constant matrices approximate the transformed control and disturbance directions through least-squares projection over a neighborhood.The projection uses sampled data and defines approximation residuals.Source: B. Approximate Spectral Rigidity · p. 3
  • Substituting the constant input approximations yields a state-independent Hamiltonian and a pointwise Hopf approximation of the value function.The original value is recovered through the spectral coordinate transformation, without HJI state-space grid discretization.Source: B. Approximate Spectral Rigidity · p. 3
  • The approximate Hamiltonian has a difference-of-convex support-function form, so the resulting Hopf optimization need not be globally convex.The support function is defined for compact convex control and disturbance sets.Source: B. Approximate Spectral Rigidity · p. 3
  • Using N > n modes can reduce the input-map residuals, but increases the costate dimension to N and the optimization cost.Each query still requires an N-dimensional optimization, unlike the O(M n) grid-based HJI approach.Source: B. Approximate Spectral Rigidity · p. 3
  • The Hamiltonian approximation error is controlled by weighted input-map residuals; if they vanish uniformly on compact costate-time sets, the Hamiltonians converge locally uniformly.Under standard viscosity-solution stability and comparison assumptions and consistent terminal data, the corresponding value functions also converge.Source: B. Approximate Spectral Rigidity · pp. 3–4
  • A general guarantee that the residuals vanish requires approximation properties of the Koopman eigenfunction dictionary that are not established here.The paper treats the residuals as indicators of spectral approximation accuracy.Source: B. Approximate Spectral Rigidity · p. 4

C. State-Independent Bounds on the Hamiltonian

The section derives state-independent upper and lower Hamiltonian bounds under stated matrix and set assumptions. These yield corresponding value-function bounds and define reachable-set approximations through their zero sublevel sets.

C. State-Independent Bounds on the Hamiltonian

  • Under the stated ellipsoidal-set and constant-matrix conditions, the transformed Hamiltonian admits state-independent upper and lower bounds.The derivation uses the support functions of the ellipsoidal control and disturbance sets and monotonicity of quadratic forms.Source: C. State-Independent Bounds on the… · p. 4
  • When the state-independent Hamiltonians bound the transformed Hamiltonian, the corresponding viscosity solutions bound the value function under the comparison principle.The value-function bounds are mapped back to the original coordinates by the spectral change of variables.Source: C. State-Independent Bounds on the… · p. 4
  • The zero sublevel sets of the lower- and upper-bound value functions define the corresponding reachable-set approximations.The original backward reachable set is defined as the zero sublevel set of the value function.Source: C. State-Independent Bounds on the… · p. 4

V. KOOPMAN EIGENFUNCTION APPROXIMATION

The section constructs principal Koopman eigenfunctions near an equilibrium using a linear–nonlinear decomposition, then approximates their nonlinear corrections from drift trajectories and data. The resulting eigenfunction map supplies spectral coordinates for pointwise Hopf reachability.

V. KOOPMAN EIGENFUNCTION APPROXIMATION

  • Near an equilibrium, the drift is split into a linear part and nonlinear remainder, and each principal eigenfunction is formed from a linear eigenfunction plus a nonlinear correction.The correction satisfies a first-order linear PDE derived from the Koopman eigenfunction equation.Source: §V · p. 4
  • The correction equation becomes a forced transport equation along drift trajectories, whose finite-time path-integral representation has a terminal term.An explicit infinite-time formula requires the terminal term to vanish; the conditions for this can be restrictive, motivating path-integral-inspired basis functions.Source: §V · pp. 4–5
  • Short drift rollouts compute basis functions without spatial gridding, and snapshot pairs yield a finite-time Koopman identity for least-squares or projected Galerkin estimation of coefficients.The basis is tailored to the eigenfunction equation because its functions encode discounted nonlinear evolution along drift trajectories.Source: §V · p. 5
  • The learned principal eigenfunctions define Φ(x), which is transformed pointwise into spectral coordinate X = e^-ΛtΦ(x) for Hopf reachability.The eigenfunctions are collected into the principal eigenfunction map before evaluating the spectral coordinate.Source: §V · p. 5

A. Two-Dimensional Example: Rigidity and Bounds

The two-dimensional example compares SKH reachability estimates with an LSM baseline under approximate rigidity and Hamiltonian bounds. The bounds produce inner and outer reachable-set approximations, while the approximate-rigidity contour agrees well with the baseline.

A. Two-Dimensional Example: Rigidity and Bounds

  • The example uses a two-dimensional system with target set defined in spectral coordinates and simulations over T = 1 with r = 0.25, |u| ≤ 2.0, and |d| ≤ 0.45.The system's drift and input fields are specified through the state-dependent terms in the example.Source: A. Two-Dimensional Example: Rigidity… · p. 5
  • Under approximate rigidity, the SKH zero-level contour agrees well with the LSM solution, with minor discrepancies away from the interface from averaging state-dependent input fields into constant matrices.The spectral input matrices are obtained by spatial averages over the computational domain.Source: A. Two-Dimensional Example: Rigidity… · p. 5
  • The bound construction uses 1 ≤ d0(x) ≤ 3 to bracket the true Hamiltonian with lower and upper expressions that weight control and disturbance strengths differently.The lower bound grants maximum control authority and minimum disturbance strength; the upper bound prioritizes disturbance.Source: A. Two-Dimensional Example: Rigidity… · p. 5
  • The lower and upper Hamiltonian bounds yield outer and inner reachable-set estimates, respectively, and their comparison with the LSM baseline confirms the SKH enclosures.The bounds case satisfies R^u ⊆ R ⊆ R^l.Source: A. Two-Dimensional Example: Rigidity… · p. 5, Figure 1 · p. 5

B. N-Link Robotic Arm

The robotic-arm examples apply SKH to learned eigenfunctions and averaged spectral input matrices in a neighborhood of a locally stable drift equilibrium. The method produces a qualitative 4D comparison and a 6D reachable-set estimate for which the LSM reference fails under memory limits.

B. N-Link Robotic Arm

  • The experiments use the N-link robotic-arm dynamics M(q)q̈ + C(q,q̇)q̇ + Ks(q) + Dq̇ = u + d, with the two-link case in four dimensions and three-link case in six.The reported 4D and 6D cases use different horizons, target radii, and control and disturbance bounds.Source: B. N-Link Robotic Arm · pp. 5–6
  • The robotic-arm drift has a locally stable equilibrium, and computations are restricted to its neighborhood; Koopman eigenfunctions are approximated and transformed input matrices use domain averages.Terminal data are defined using the learned eigenfunctions.Source: B. N-Link Robotic Arm · pp. 5–6
  • For the four-dimensional two-link arm, SKH contours are qualitatively consistent with the LSM baseline, but lower values near the interface produce larger zero sublevel sets.The reported discrepancy reflects learned eigenfunctions and averaged spectral input matrices, as well as LSM grid resolution, dissipation, and boundary effects.Source: B. N-Link Robotic Arm · p. 6, Figure 2 · p. 6
  • For the six-dimensional three-link arm, LSM failed from memory limits even at 21 nodes per dimension, while SKH produced a reachable-set estimate without constructing the reference grid.That reference grid would contain 85,766,121 nodes before auxiliary arrays; after construction, SKH evaluates the value function pointwise.Source: B. N-Link Robotic Arm · p. 6, Figure 2 · p. 6

VII. CONCLUSION

The conclusion presents SKH as an approximate state-independent, pointwise optimization approach to adversarial nonlinear reachability. It combines spectral input approximations, Hamiltonian and value-function bounds, and path-integral eigenfunctions, with numerical examples demonstrating tractable reachable-set approximation.

VII. CONCLUSION

  • The framework lifts drift dynamics into Koopman eigenfunction coordinates, replacing state-space discretization of the nonlinear HJI equation with approximate state-independent pointwise optimization.The method combines least-squares approximations of transformed input directions with Hamiltonian and value-function bounds for reachable-set enclosures.Source: §VII · p. 6
  • Path-integral eigenfunction computation avoids spatial discretization of the associated eigenfunction PDEs, and retaining n principal eigenfunctions preserves the original system dimension.The paper reports tractable approximation of backward reachable sets for nonlinear adversarial systems.Source: §VII · p. 6
Loading 2609.06878v1…