pith. sign in

arxiv: 1907.03225 · v1 · pith:E4Q4QSGAnew · submitted 2019-07-07 · 📡 eess.SY · cs.SY

Backward Reachability for Polynomial Systems on A Finite Horizon

He Yin , Murat Arcak , Andrew Packard , Peter Seiler This is my paper

Pith reviewed 2026-05-25 01:49 UTC · model grok-4.3

classification 📡 eess.SY cs.SY
keywords backward reachable setpolynomial systemssum-of-squaresS-procedureinner approximationcontroller synthesisfinite horizonuncertain systems
0
0 comments X

The pith

The paper presents an optimization method to compute inner approximations of backward reachable sets for polynomial systems over a finite horizon, along with a controller that keeps trajectories inside a target tube.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a method to find guaranteed inner approximations to the backward reachable set of a target tube for polynomial dynamical systems. This matters to a sympathetic reader because such approximations let engineers certify safe starting regions from which a controller can steer the system into a desired set without violating tube constraints. The approach formulates the problem as nonlinear optimizations that are broken into smaller subproblems and solved iteratively with sum-of-squares programming and the polynomial S-procedure. The same framework produces an admissible controller and extends to systems with L2 disturbances and L-infinity uncertainties.

Core claim

A method is presented to obtain an inner-approximation of the backward reachable set (BRS) of a given target tube, along with an admissible controller that maintains trajectories inside this tube. The proposed optimization algorithms are formulated as nonlinear optimization problems, which are decoupled into tractable subproblems and solved by an iterative algorithm using the polynomial S-procedure and sum-of-squares techniques. This framework is also extended to uncertain nonlinear systems with L_2 disturbances and L_∞ parametric uncertainties.

What carries the argument

The iterative algorithm that decouples the reachability optimization into tractable subproblems solved via the polynomial S-procedure and sum-of-squares techniques.

If this is right

  • The method produces both an inner-approximated safe set and a controller that keeps trajectories inside the target tube.
  • The same decoupled optimization extends directly to uncertain systems that include L2 disturbances and L-infinity parametric uncertainties.
  • The approach applies to finite-horizon problems and has been tested on robotics and aircraft models that include control saturation.
  • Inner approximations guarantee that every initial state inside the computed set can reach the target tube under the synthesized controller.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The iterative decoupling may allow the method to scale to moderate state dimensions if the sum-of-squares solvers remain tractable.
  • Combining these inner sets with outer approximations from other reachability tools could produce tighter certified regions.
  • Polynomial relaxations mentioned for non-polynomial dynamics suggest a route to broader classes of nonlinear systems.
  • The controller output could be used to construct real-time safety filters that override nominal commands when the state approaches the boundary of the approximated set.

Load-bearing premise

The dynamical systems are polynomial or can be handled via polynomial relaxations so that sum-of-squares and S-procedure techniques apply directly to the subproblems.

What would settle it

For a low-dimensional polynomial system whose exact backward reachable set is known by other means, run the algorithm and verify that every state in the computed inner approximation can be driven into the target tube by the returned controller while staying inside the tube at every step.

Figures

Figures reproduced from arXiv: 1907.03225 by Andrew Packard, He Yin, Murat Arcak, Peter Seiler.

Figure 1
Figure 1. Figure 1: Dubin’s car Simulations 5.1.1 Dubin’s Car with Obstacle In addition to the terminal target set ΩrT 0 , suppose there is an unsafe region Ωobs 0 := {x ∈ R 3 |obs(x) := (x1−1.5)2+ x 2 2 + x 2 3 − 0.5 2 ≤ 0}. Thus the target tube is the intersection of the terminal target set ΩrT 0 and the complement of Ω obs 0 . Slices of the resulting ΩV t0,γ with the obstacle are shown as solid black curves in [PITH_FULL_… view at source ↗
Figure 2
Figure 2. Figure 2: Inner-approximated BRS for Dubin’s car example [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Inner-approximated BRS for the pendubot example [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Pendubot simulation results 5.3 NASA’s Generic Transport Model (GTM) around straight and level flight con￾dition with L2 Disturbance The GTM is a remote-controlled 5.5% scale commercial aircraft [24]. From [25], its longitudinal dynamical model is x˙ 1 = 1 m (−D − mg sin(x4 − x2) + Tx cos(x2) + Tz sin(x2)), x˙ 2 = 1 mx1 (−L + mg cos(x4 − x2) − Tx sin(x2) + Tz cos(x2) + x3), x˙ 3 = M + Tm Iyy , x˙4 =x3, (4)… view at source ↗
Figure 5
Figure 5. Figure 5: Inner-approximated BRS for GTM The simulation results of the polynomial model of GTM with the initial condition [47 m/s; 20 rad; 70 rad/s; 20 rad] and a disturbance signal w(t) = √ 2tR T η(t), using both k(t, x) and k(t, x, w) are shown in [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Simulations of GTM with disturbances w BRS, so that no matter how the evader chooses its control input at each time instance, all the trajectories for system (6) from the inner-approximated BRS will always be driven to the target set ΩrT 0 . This reachability problem is posed as a dynamic game in [3], whereas in this paper, the control input ue from the evader is regarded as the uncertain parameter with a … view at source ↗
Figure 7
Figure 7. Figure 7: Inner-approximated BRS for the pursuer-evader game [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
read the original abstract

A method is presented to obtain an inner-approximation of the backward reachable set (BRS) of a given target tube, along with an admissible controller that maintains trajectories inside this tube. The proposed optimization algorithms are formulated as nonlinear optimization problems, which are decoupled into tractable subproblems and solved by an iterative algorithm using the polynomial S-procedure and sum-of-squares techniques. This framework is also extended to uncertain nonlinear systems with L_2 disturbances and L_{\infty} parametric uncertainties. The effectiveness of the method is demonstrated on several nonlinear robotics and aircraft systems with control saturation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents a method to compute inner approximations of the backward reachable set (BRS) for polynomial systems over a finite horizon, together with an admissible controller that keeps trajectories inside a prescribed target tube. The approach formulates the problem as a nonlinear optimization, decouples it into subproblems, and solves them iteratively via the polynomial S-procedure and sum-of-squares (SOS) relaxations; the framework is extended to systems with L2 disturbances and L∞ parametric uncertainties and is illustrated on robotics and aircraft examples with input saturation.

Significance. If the iterative procedure is shown to produce valid inner approximations that respect the joint invariance constraints, the work would supply a practical SOS-based tool for finite-horizon safety verification and control synthesis on polynomial nonlinear systems, an area where exact BRS computation is intractable. The explicit handling of control saturation and the extension to uncertain dynamics are useful features, and the numerical demonstrations on concrete robotic and flight-control models provide evidence of applicability.

major comments (2)
  1. [§4] §4 (Iterative Algorithm): No theorem or proposition establishes that a fixed point of the decoupled subproblems satisfies the original coupled reachability and invariance conditions of the BRS. The manuscript states that each subproblem is solved via S-procedure relaxations, but does not derive that the recombination at convergence yields a valid inner approximation of the tube; accumulated slack from the individual relaxations could violate the joint constraints.
  2. [§5.2] §5.2 (Uncertain Systems): The extension to L2 disturbances and L∞ parametric uncertainties re-uses the same decoupled iteration without additional invariance arguments. It is therefore unclear whether the same fixed-point issue identified above is resolved or merely inherited for the robust case.
minor comments (2)
  1. Notation for the target tube and the polynomial vector fields is introduced without an explicit table of symbols; a compact notation summary would improve readability.
  2. Figure captions for the aircraft and quadrotor examples do not state the polynomial degrees used in the SOS relaxations or the iteration count at termination.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment point by point below, indicating planned revisions where appropriate.

read point-by-point responses

  1. Referee: [§4] §4 (Iterative Algorithm): No theorem or proposition establishes that a fixed point of the decoupled subproblems satisfies the original coupled reachability and invariance conditions of the BRS. The manuscript states that each subproblem is solved via S-procedure relaxations, but does not derive that the recombination at convergence yields a valid inner approximation of the tube; accumulated slack from the individual relaxations could violate the joint constraints.

    Authors: We acknowledge that the manuscript does not contain a formal proposition establishing that a fixed point of the iteration necessarily satisfies the original coupled conditions in the presence of relaxation slack. The iterative procedure is motivated by tractability and is supported by numerical validation on the examples, but a rigorous characterization of the fixed-point property is indeed absent. We will revise §4 to include a new proposition that derives sufficient conditions (based on the structure of the polynomial S-procedure subproblems) under which the converged solution remains a valid inner approximation of the tube, explicitly addressing the potential accumulation of slack. revision: yes

  2. Referee: [§5.2] §5.2 (Uncertain Systems): The extension to L2 disturbances and L∞ parametric uncertainties re-uses the same decoupled iteration without additional invariance arguments. It is therefore unclear whether the same fixed-point issue identified above is resolved or merely inherited for the robust case.

    Authors: We agree that the robust extension in §5.2 inherits the same theoretical gap. In the revised manuscript we will extend the new proposition introduced in §4 to the uncertain case, incorporating the additional invariance arguments required for L2 disturbances and L∞ parametric uncertainties. This will ensure that the fixed-point property and inner-approximation guarantee are stated uniformly for both the nominal and robust formulations. revision: yes

Circularity Check

0 steps flagged

No circularity; standard SOS framework

full rationale

The paper formulates an optimization problem for inner-approximating backward reachable sets using the polynomial S-procedure and sum-of-squares relaxations on decoupled subproblems, solved iteratively. These are established external techniques with no reduction of the central claim to self-definitional inputs, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained against standard benchmarks in polynomial optimization and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that the systems are polynomial, enabling direct application of SOS techniques; no free parameters or invented entities are described in the abstract.

axioms (1)
  • domain assumption Dynamical systems are polynomial
    Required for the polynomial S-procedure and sum-of-squares techniques to formulate and solve the optimization problems as described.

pith-pipeline@v0.9.0 · 5620 in / 1240 out tokens · 30968 ms · 2026-05-25T01:49:05.435696+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Control design along trajectories with sums of squares pro- gramming,

    A. Majumdar, A. A. Ahmadi, and R. Tedrake, “Control design along trajectories with sums of squares pro- gramming,” in Proceedings of International Conference on Robotics and Automation , 2013, pp. 4054–4061

    2013

  2. [2]

    Funnel libraries for real-time robust feedback motion planning,

    A. Majumdar and R. Tedrake, “Funnel libraries for real-time robust feedback motion planning,” The Interna- tional Journal of Robotics Research , vol. 36, no. 8, pp. 947–982, 2017

    2017

  3. [3]

    A time-dependent HamiltonJacobi formulation of reachable sets for continuous dynamic games,

    I. M. Mitchell, A. M. Bayen, and C. J. Tomlin, “A time-dependent HamiltonJacobi formulation of reachable sets for continuous dynamic games,” IEEE Transactions on Automatic Control , vol. 50, pp. 947 – 957, 2005

    2005

  4. [4]

    Convex computation of the region of attraction of polynomial control systems,

    D. Henrion and M. Korda, “Convex computation of the region of attraction of polynomial control systems,” IEEE Transactions on Automatic Control , vol. 59, pp. 297–312, 2014

    2014

  5. [5]

    Convex optimization of nonlinear feedback controllers via occupation measures,

    A. Majumdar, R. Vasudevan, M. M. Tobenkin, and R. Tedrake, “Convex optimization of nonlinear feedback controllers via occupation measures,” The International Journal of Robotics Research , vol. 33, pp. 1209–1230, 2014

    2014

  6. [6]

    Structured semidefinite programs and semialgebraic geometry methods in robustness and opti- mization,

    P. Parrilo, “Structured semidefinite programs and semialgebraic geometry methods in robustness and opti- mization,” PhD thesis, California Institute of Technology, 2000

    2000

  7. [7]

    Quantitative local analysis of nonlinear systems,

    U. Topcu, “Quantitative local analysis of nonlinear systems,” PhD thesis, University of California, Berkeley, 2008

    2008

  8. [8]

    Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming,

    W. Tan and A. Packard, “Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming,” IEEE Transactions on Automatic Control , vol. 53, p. 565, 2008

    2008

  9. [9]

    LMI-based computation of optimal quadratic Lyapunov functions for odd polynomial systems,

    G. Chesi, A. Garulli, A. Tesi, and A. Vicino, “LMI-based computation of optimal quadratic Lyapunov functions for odd polynomial systems,” International Journal of Robust and Nonlinear Control , vol. 15, no. 1, pp. 35–49, 2005

    2005

  10. [10]

    Computing the domain of attraction for polynomial systems via BMI optimiza- tion method,

    B. Tibken and Youping Fan, “Computing the domain of attraction for polynomial systems via BMI optimiza- tion method,” in 2006 American Control Conference, Minneapolis, MN, June 2006, pp. 117–122. 13

    2006

  11. [11]

    Region of attraction analysis with integral quadratic constraints,

    A. Iannelli, P. Seiler, and A. Marcos, “Region of attraction analysis with integral quadratic constraints,” submitted to Automatica

  12. [12]

    Controls applications of sum of squares programming,

    Z. Jarvis-Wloszek, R. Feeley, W. Tan, K. Sun, and A. Packard, “Controls applications of sum of squares programming,” in Positive Polynomials in Control . Springer, Berlin, Heidelberg, 2005, vol. 312

    2005

  13. [13]

    Finite horizon backward reachability analysis and control synthesis for uncertain nonlinear systems,

    H. Yin, A. Packard, M. Arcak, and P. Seiler, “Finite horizon backward reachability analysis and control synthesis for uncertain nonlinear systems,” to appear in 2019 American Control Conference

    2019

  14. [14]

    Reachability analysis using dissipation inequalities for nonlinear dynamical systems,

    ——, “Reachability analysis using dissipation inequalities for nonlinear dynamical systems,” arXiv preprint, aug 2018, arXiv:1808.02585

    work page arXiv 2018

  15. [15]

    Linearized analysis versus optimization-based nonlinear analysis for nonlinear systems,

    U. Topcu and A. Packard, “Linearized analysis versus optimization-based nonlinear analysis for nonlinear systems,” in Proceedings of 2009 American Control Conference, St. Louis, MO, USA, 2009

    2009

  16. [16]

    Quantitative local L 2- gain and reachability analysis for nonlinear systems,

    E. Summers, A. Chakraborty, W. Tan, U. Topcu, P. Seiler, G. Balas, and A. Packard, “Quantitative local L 2- gain and reachability analysis for nonlinear systems,” International Journal of Robust and Nonlinear Control , vol. 23, pp. 1115–1135, 2013

    2013

  17. [17]

    Quasiconvex sum-of-squares programming,

    P. Seiler and G. Balas, “Quasiconvex sum-of-squares programming,” in Proceedings of 49th IEEE Conference on Decision and Control , Atlanta, GA, USA, 2010, pp. 3337–3342

    2010

  18. [18]

    Method of centers for minimizing generalized eigenvalues,

    S. Boyd and L. E. Ghaoui, “Method of centers for minimizing generalized eigenvalues,” Linear Algebra and its Applications, vol. 188-189, pp. 63–111, 1993

    1993

  19. [19]

    Boyd and L

    S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004

    2004

  20. [20]

    SOSOPT: A Toolbox for Polynomial Optimization

    P. Seiler, “SOSOPT: A toolbox for polynomial optimization,” ArXiv e-prints, Aug 2013, arXiv:1308.1889

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  21. [21]

    The MOSEK optimization toolbox for MATLAB manual. Version 8.1

    MOSEK ApS, “The MOSEK optimization toolbox for MATLAB manual. Version 8.1.” 2017, http://docs. mosek.com/8.1/toolbox/index.html

    2017

  22. [22]

    On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,

    L. Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,” American Journal of Mathematics , vol. 79, no. 3, pp. 497–516, 1957

    1957

  23. [23]

    Kinematic and dynamic control of a wheeled mobile robot,

    D. DeVon and T. Bretl, “Kinematic and dynamic control of a wheeled mobile robot,” in IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems . IEEE, 2007, pp. 4065–4070

    2007

  24. [24]

    Recent NASA research on aerodynamic modeling of poststall and spin dynamics of large transport airplanes,

    A. M. Murch and J. V. Foster, “Recent NASA research on aerodynamic modeling of poststall and spin dynamics of large transport airplanes,” in In 45th AIAA Aerospace Sciences Meeting and Exhibit , Reno, Nevada, 2007

    2007

  25. [25]

    B. L. Stevens and F. L. Lewis, Aircraft Control and Simulation . Hoboken, NJ: John Wiley & Sons, 1992

    1992

  26. [26]

    Nonlinear region of attraction analysis for flight control verification and validation,

    A. Chakraborty, P. Seiler, and G. J. Balas, “Nonlinear region of attraction analysis for flight control verification and validation,” Control Engineering Practice, vol. 19, no. 4, pp. 335–345, 2011. 14

    2011