PaperlayerView exact revision on arXiv

Source-linked AI summary

SparseMax-dSTL: Sound Robustness with Horizon-Independent Gradient Allocation for Temporal Logic Trajectory Optimization

Sai Sandeep Damera, Ryan Matheu, John S. Baras, Calin Belta

arXiv:2610.23837v1eess.SYcs.LOcs.ROcs.SY

TL;DR

Smoothed STL robustness determines both which trajectories a gradient-based solver accepts and how it distributes gradient across samples, but existing approximations do not jointly ensure soundness and horizon-independent weight on violating samples. The paper builds lower approximations of both extrema with sparsemax gradients and proves guarantees for the resulting robustness. Simulations and a constrained unicycle optimization illustrate the guarantees and contrast them with LSE behavior.

  • Problem

    Existing smooth robustness approximations do not jointly ensure soundness and gradient weight on violating samples that stays bounded away from zero as the horizon grows.

    Source: §I · p. 1

  • Method

    The paper replaces each extremum with a lower approximation derived from a quadratically regularized maximum whose gradient is the sparsemax projection.

    Source: §I · p. 2, A. The operators · p. 3

  • Results

    The sparsemax robustness is a lower bound with horizon-independent error and gradient allocation; on the manipulator, LSE weight falls from 0.216 to 0.036 as the horizon grows from 10 to 80 s.

    Source: §VI · p. 7, B. Manipulator beside a person · p. 7

  • Takeaways & Limitations

    In constrained unicycle optimization, the sparsemax lower-bound constraint returns a trajectory meeting the 0.2 m margin, unlike plain LSE, which returns a violating trajectory at zero margin.

    Source: A. Planar unicycle · p. 7

Abstract

from arXiv · show

A gradient-based solver that enforces a Signal Temporal Logic (STL) specification uses a smooth approximation of its quantitative semantics, the robustness. In safety-critical trajectory optimization, this approximation must have two properties. First, it must be sound, that is, nonnegative only on trajectories that satisfy the specification. Second, at each temporal operator, the weight of its gradient on the violating samples must stay bounded away from zero, however long the horizon. The approximations in use, including the log-sum-exp, its sound variant, and the generalized-mean robustness, do not have both. We introduce lower approximations of the minimum and the maximum whose gradients are sparsemax projections, and we prove that the robustness built from them has both. It lies below the exact robustness and is therefore sound, and its error has a bound that is independent of the number of samples and known before optimization. The gradient of each approximation is exactly zero on every sample beyond a data-dependent threshold, so the weight on violating samples a gap beyond the others has a positive lower bound at every horizon. On a planar unicycle and on a seven-joint manipulator beside a person in simulation, the log-sum-exp approximation is positive on a violating trajectory. As the horizon of the manipulator's task grows from 10 to 80 s, the gradient weight of the sound variant on the violating samples falls from 0.22 to 0.04, while that of sparsemax stays at 1. In a constrained trajectory optimization of the unicycle, the constraint on the log-sum-exp robustness returns a violating trajectory, whereas the constraint on the sparsemax robustness returns a trajectory that satisfies the specification with the required margin.

I. INTRODUCTION

STL solvers use smoothed robustness both to decide feasibility and to allocate gradients across time samples. This section motivates a sound smoothing whose gradient retains weight on violating samples as the horizon grows.

I. INTRODUCTION

  • A sound smoothing must be negative on every violating trajectory, while its gradient weight on violating samples must not vanish as the horizon grows.These properties matter to gradient-based solvers, policy gradients, and safety filters that differentiate robustness.Source: §I · p. 1
  • Plain LSE can be positive on a shallow until violation when tied witnesses arise, while sound LSE can lose violating-sample weight as the horizon adds near-valued samples.At equal worst-case error, GMR's weight on k violating samples scales as (k/d)^(1/q).Source: §I · pp. 1–2
  • Sparsemax lower approximations of both extrema compose into a robustness lower bound with error known before optimization and at most γ/2 per node, independent of sample count.Their gradients are exactly zero beyond a data-dependent threshold, and the weight on violating samples separated by a gap has a horizon-independent lower bound.Source: §I · p. 2

II. RELATED WORK

  • Prior average-based measures preserve the sign but not necessarily a margin, while this construction provides both a lower bound and a horizon-independent allocation guarantee.The paper positions its operators between extrema, which focus on critical samples, and means, which let every sample contribute.Source: §II · p. 2
  • At equal worst-case error ε, sparsemax assigns k violating samples at least min{1, k∆/γ} weight, independent of N; sound LSE weight tends to zero as N grows when ∆<ε.Source: §I · p. 2

III. PROBLEM FORMULATION

The formulation represents a sampled robot trajectory and STL specification as a finite evaluation graph of predicate values and extrema. A smoothed robustness is then used in a constrained, least-effort control problem.

A. Specifications and exact robustness

  • The robot follows a discrete-time model with bounded controls, which generate a sampled trajectory over horizon H = Th.The initial state is fixed.Source: A. Specifications and exact robustness · pp. 2–3
  • The specification grammar includes predicates, negated predicates, conjunction, disjunction, globally, eventually, and until operators over sample windows.A predicate's differentiable value is nonnegative when that predicate holds.Source: A. Specifications and exact robustness · p. 3
  • Exact robustness is defined recursively from predicate values, and a sampled trajectory satisfies the specification when its robustness at the initial sample is nonnegative.The until semantics use a closed prefix: each witness requires ψ at its offset and ϕ at every sample from the start through that offset.Source: A. Specifications and exact robustness · p. 3
  • Unrolling the specification over samples produces a finite acyclic graph whose leaves are predicate values and whose internal nodes are minima and maxima.A node is evaluated only where all samples in its window exist, so the specification horizon is at most H.Source: A. Specifications and exact robustness · p. 3

B. Constrained trajectory optimization

  • The control objective is to find controls of least effort that satisfy the specification, with the top-level conjunction imposed as separate constraints.The exact robustness constraints are nonsmooth in the controls.Source: B. Constrained trajectory optimization · p. 3
  • The solver replaces every extremum node with a smooth function and enforces smoothed robustness constraints at margin c ≥ 0.The smoothing determines both the feasible set and the solver's search direction.Source: B. Constrained trajectory optimization · p. 3

C. Two requirements on the smoothing

The smoothing must preserve a sound feasible set while maintaining gradient weight on violating samples as the horizon grows. These requirements are posed at a fixed worst-case error per node.

C. Two requirements on the smoothing

  • A smoothed robustness is sound when nonnegativity implies nonnegative exact robustness, and a lower bound with budget B stays between exact robustness minus B and exact robustness.A margin on a lower bound is also a margin on exact robustness, so its feasible set excludes violating trajectories.Source: C. Two requirements on the smoothing · p. 3
  • The gradient with respect to controls is a weighted sum over predicate leaves, with each leaf's weight accumulated along root-to-leaf paths through the smooth extrema.At a temporal minimum, violating children may remain few while the number of other children grows with the horizon.Source: C. Two requirements on the smoothing · p. 3
  • The problem asks for smooth extrema that give a graph-dependent lower-bound budget and keep weight on k extreme children separated from N others by gap ∆ bounded away from zero as N grows.The comparison fixes worst-case error ε per node because smoother accuracy changes how abruptly the gradient varies with the trajectory.Source: C. Two requirements on the smoothing · p. 3

IV. SPARSEMAX LOWER EXTREMA

Sparsemax lower extrema are derived from a quadratically regularized maximum over the probability simplex. Their gradients are sparsemax projections, yielding sample-count-independent error bounds and zero weight beyond a threshold.

A. The operators

  • The quadratically regularized maximum over the simplex has sparsemax projection pγ(z) as its optimizer and gradient.The projection follows by completing the square; the envelope theorem gives the gradient.Source: A. The operators · p. 3
  • Entries at or below a data-dependent threshold receive exactly zero derivative, and the lower-extremum gradients lie in the simplex.The operators are continuously differentiable and nondecreasing in each entry.Source: A. The operators · p. 4
  • The sparsemax minimum and maximum approximations stay within a band of width at most γ/2 for every number of entries.Figure 3 compares sparsemax and sound LSE minima at equal worst-case error and shows sparsemax's weight on a non-minimal entry becomes zero once ∆ ≥ γ/k.Source: A. The operators · p. 4, Figure 3 · p. 4

B. A lower bound on the evaluation graph

The evaluation graph replaces each exact extremum with a lower approximation and tracks the resulting error through a pathwise budget. This makes the smoothed robustness a lower bound, with an until node adding two bands regardless of window length.

B. A lower bound on the evaluation graph

  • At each node, the propagated error is bounded by the largest child budget plus that node’s approximation band.This follows from monotonicity, nonexpansiveness of the exact extremum, and the per-node bound.Source: B. A lower bound on the evaluation graph · p. 4
  • The smoothed robustness is a lower bound of the exact robustness, and its error budget is fixed by the graph and parameters before evaluating any trajectory.At the root, the budget is the largest sum of node bands and leaf error along a root-to-leaf path.Source: B. A lower bound on the evaluation graph · p. 4
  • An until node adds two bands to a path for any window length because it is one maximum over witnesses whose children are minima.The witness minimum ranges over j + 2 values.Source: B. A lower bound on the evaluation graph · p. 4
  • The guarantees concern sampled semantics in exact arithmetic and do not cover behavior between samples.Source: B. A lower bound on the evaluation graph · p. 4

C. The log-sum-exp at an until node

At an until node, plain LSE can turn a shallow violation into positive smoothed robustness when tied witnesses inflate its maximum. The paper gives a condition for this sign flip and notes that its lower-bound operators instead keep the node negative.

C. The log-sum-exp at an until node

D. Gradient allocation at equal error

At equal worst-case error, sparsemax allocates gradient only to samples within a data-dependent threshold, while sound LSE assigns every sample positive weight. The sparsemax weight on a group separated by a gap has a horizon-independent lower bound, with a trade-off between that allocation range and smoothness.

D. Gradient allocation at equal error

  • With equal worst-case error ε, sound LSE has positive weight on every entry, while the sparsemax-derived lower maximum has zero weight beyond its threshold.The sound-LSE gradient is softmax; sparsemax’s full weight on the k children occurs when ∆ ≥ γ/k.Source: D. Gradient allocation at equal error · p. 5
  • For unequal children, sound-LSE uses effective count keff = Σ_i e^−βδ_i, while sparsemax gives full weight exactly when Σ_i(∆ − δ_i) ≥ γ.These expressions reduce to the equal-child result when the k children are equal.Source: D. Gradient allocation at equal error · p. 5
  • For k children separated from N others by gap ∆, sparsemax weight is at least min{1, k∆/(4ε)} independently of N and the other children’s values.It assigns the whole weight when ∆ ≥ γ/k; the sound-LSE weight has no such bound for ∆ < ε and decays as N grows.Source: D. Gradient allocation at equal error · p. 5
  • When ∆ > ε, sound-LSE weight on the k children tends to 1 as N grows, but choosing ε below the gap requires knowing the trajectory’s gap.Sparsemax keeps the whole weight for every ε ≤ k∆(1 − 1/m)/2; this range exceeds ε < ∆ by a factor k(1 − 1/m)/2, above one for k ≥ 3.Source: D. Gradient allocation at equal error · p. 5
  • Reducing γ widens sparsemax’s full-weight gap range but raises the gradient’s Lipschitz constant to 1/γ, making the constraint less smooth.As γ approaches zero, the operator tends to the exact extremum.Source: D. Gradient allocation at equal error · p. 6
  • For until, violating samples followed by N samples a gap ∆ above them match the allocation setup; under sparsemax those later samples contribute nothing once ∆ ≥ γ/k.Under sound LSE, those samples can contribute almost all the weight when its violating-group weight is small; whether this moves controls out of violation depends on the dynamics.Source: D. Gradient allocation at equal error · p. 6

A. Planar unicycle

The unicycle experiment compares robustness measures on fixed trajectories and in constrained optimization, testing whether their constraints reject violations and preserve a required margin.

A. Planar unicycle

  • The experiment uses a unicycle in a 10 m square workspace with disk regions; its task combines an until condition, reaching and dwelling in target regions, obstacle avoidance, and workspace containment.The model uses h = 0.1 s, |v| ≤ 1 m/s, and |ω| ≤ π/2 rad/s.Source: A. Planar unicycle · p. 6
  • The fixed S1 trajectory cuts into Red before waiting outside it, whereas S2 passes Red with 0.3 m clearance and exact robustness 0.3.The wait is lengthened from 3 to 130 s, giving 31 to 1301 samples while maintaining a 0.038 m gap above the violation.Source: A. Planar unicycle · p. 6, Figure 4 · p. 6
  • On S1, plain LSE is positive despite a 0.015 m Red intrusion, while both GMR orders have the correct sign and sparsemax’s error is 0.95ε.All 21 witnesses tie; sparsemax’s error arises at the inner minimum over tied samples.Source: A. Planar unicycle · p. 6
  • Sparsemax’s weight on samples inside Red stays 1 as the wait grows from 3 to 130 s, while both LSE variants’ weights fall for ∆ < ε.The fixed trajectories use k = 21 violating samples, with ∆ = 0.038 m and ε = 0.1 m.Source: A. Planar unicycle · p. 6
  • With c = 0.2 m, only the sound LSE and sparsemax return a trajectory with exact robustness at least c; from S2, the plain LSE returns a violating trajectory.From S1, the plain LSE constraint returns a trajectory cutting 0.058 m into Red, while the sound LSE and sparsemax keep it 0.045 m and 0.087 m outside, respectively.Source: A. Planar unicycle · pp. 6–7

B. Manipulator beside a person

The manipulator experiment tests robustness measures on simulated pick-and-handover tasks beside a person, including how gradient allocation and constrained optimization behave as the horizon grows.

B. Manipulator beside a person

  • The simulated seven-joint manipulator picks a part outside a person-reserved zone and hands it over inside the zone, with separation, speed, and pose-tolerance predicates.The separation threshold is 0.10 m; slow and speed thresholds are 0.30 m and 0.25 m/s, and pick and handover tolerances are 0.05 m.Source: B. Manipulator beside a person · p. 7
  • The plain LSE is positive on the violated until conjunct because all 51 pick-window witnesses tie, whereas sound LSE and sparsemax stay below exact robustness within the 0.41 error budget.The initial trajectories have exact robustness −0.05, with 18 or 19 samples inside the zone and horizons from 10 to 80 s.Source: B. Manipulator beside a person · p. 7
  • Sparsemax’s weight on samples inside the zone is 1.000 at every horizon, while the sound LSE weight falls from 0.216 to 0.036 as the horizon grows from 10 to 80 s.The torque-gradient component passing through those samples stays the same under sparsemax, but falls by a factor of 5.4 under the LSE and 10 under GMR of order (0, 1).Source: B. Manipulator beside a person · p. 7
  • Across 16 locations, the first exactly satisfying trajectory appears after 1 or 2 updates under sparsemax and GMR (−10, 10), versus 4.5 to 19.5 updates under sound LSE.At 40 s, 3 of 32 sparsemax trajectories never meet the solver’s own constraint; after 100 updates, the plain LSE and GMR medians remain near zero exact robustness.Source: B. Manipulator beside a person · p. 7

VI. CONCLUSION

Sparsemax lower extrema bound robustness error independently of sample count and preserve weight on gap-separated samples across horizons. Their thresholded gradients and larger realized error create tradeoffs, including the possibility of rejecting plans when feasibility is tight.

VI. CONCLUSION

  • At every horizon, sparsemax assigns weight of at least min{1, k∆/γ} to k samples separated by gap ∆, with per-node error at most γ/2.At equal worst-case error ε, the bound is min{1, k∆/(4ε)}; the sound LSE weight tends to zero as other samples grow when ∆ < ε.Source: §VI · p. 7
  • Sparsemax’s realized error is 0.17 versus 0.13 for the sound LSE, and can leave no feasible plan when feasibility is tight.The minimum’s error band is attained at a tie, where sparsemax gives the smaller value at equal worst-case error.Source: §VI · p. 7
  • Fig. 5 shows a violating manipulator trajectory with exact robustness −0.05 and plots inside-zone sample weights at ε = 0.2.The trajectory enters the zone for 0.3 s, then waits at the pick pose; the plotted weights are medians over four trajectories.Source: Figure 5 · p. 8
  • Table III reports optimization on torques from violating initial trajectories at 16 locations, including time to nonnegative exact robustness and final robustness and effort at 40 s.It uses c = 0 and 100 updates; quartiles are reported at 40 s, and locations that never satisfy are excluded from the median.Source: Table III · p. 8
  • Samples beyond the threshold receive no derivative, which can hide soon-critical samples and mask them from higher nodes in nested specifications.The operators are once continuously differentiable, and the measured update advantage is first-order.Source: §VI · p. 8
Loading 2610.23837v1…