CS Paper Radar

Computing Invariant Reachable Sets through Sum-of-Squares Programming

Mohamed Khalid M Jaffar

eess.SY cs.ROmath.OC ·submitted 2026-11-03 05:06 UTC · v1
code/data

Abstract

Funnels, time-varying invariant sets around nominal trajectories, certify that a closed-loop system tracks its plan, and can be composed into verified motion plans. Their computation by sum-of-squares (SOS) programming is well established in formulation but not in practice: the result depends on implementation choices such as the initial guess, Lyapunov function normalization, and termination rule, which the literature documents only briefly. This paper presents a self-contained treatment of SOS-based funnel computation, implemented in the open-source package computeSOSFunnels. We propose a minimum-volume formulation with inlet and outlet constraints under which funnels with coinciding nominal endpoints compose by construction. Numerical experiments on a unicycle, with timing studies on a cart-pole and a 12-state quadrotor, characterize the pipeline: infeasible initial guesses are partly decidable before solving, the certificate shows no violations among 39,000 boundary samples per funnel under the true dynamics, and constructing the semidefinite program, not solving it, dominates computation time.

Comment
8 pages, 3 figures, 3 tables. Submitted to IEEE Transactions on Control Systems Technology. Code: github.com/khalid2696/computeSOSFunnels

Closest papers

Nearest neighbours by meaning across the whole index.

COAST: Safe Flight Corridor Planner for Fast and Robust Snap Minimized Trajectories

cs.RO eess.SY ·2026-11-17 ·Alejandro Pelaez, Randal W. Beard
code/data similarity 0.59
Abstract · 14 pages, 4 figures, 2 tables. Submitted to the 2027 American Control Conference (ACC 2027)

Current B-Spline trajectory planners face a critical trade-off: they either sacrifice computational speed to maintain strict Safe Flight Corridor (SFC) guarantees, or they abandon hard safety bounds in favor of soft-constraint penalties to achieve real-time performance. We present COAST (Corridor-Optimized Aerially-Safe Trajectories), a B-Spline based, online trajectory planner capable of formulating snap minimized trajectories with SFC guarantees. COAST divides the problem into two stages: an A* based front-end that generates geometrically simple SFCs (represented as a chain of rectangular prisms), and a quadratic programming back-end for control point optimization. To handle the non-convexity of SFC intersections, we leverage the finite support property of B-Splines, to ensure the spline never exits SFC boundaries. The control point optimization incorporates MINVO transforms for kinodynamic bounding, allowing COAST to design non-conservative, dynamically feasible trajectories, while a snap minimization matrix calculation provides flight smoothness. This formulation provides a formal geometric containment guarantee, while ensuring mean trajectory computation times under 5 ms for real-time deployment. We validate our results through high-fidelity simulation experiments. The source code can be found at: https://github.com/byu-magicc/Minimum-Snap-Trajectories

0.46

Real-Time Synthesis of Robust Controlled Invariant Sets for Monotone Systems

eess.SY cs.AIcs.RO ·2026-09-12 ·Yasin Sonmez, Mahmoud Khaled, Majid Zamani, Murat Arcak
published similarity 0.58
Abstract

Safety-critical control of autonomous systems requires formal safety certificates, such as controlled invariant sets, that must be computed online as conditions change. Although standard synthesis algorithms scale poorly with state dimension, monotone dynamical systems with lower-closed safety specifications allow for accelerated computation of controlled invariant sets. In particular, lazy fixed-point algorithms exploit monotonicity and track only the antichain basis of the set. However, membership tests and redundancy checks against an evolving basis remain major bottlenecks. We introduce a threshold-function reformulation in which a lower-closed set on a d-dimensional grid is represented by its column heights along a designated axis. This reformulates the greatest-fixed-point iteration as independent one-dimensional binary searches, one per grid column, yielding an embarrassingly parallel iteration with asymptotically lower computational complexity than the lazy fixed-point algorithm. Experiments synthesize invariant sets on 3D grids with 10^9 cells in under 50 ms and 10^14 cells in under two minutes. We further demonstrate online re-synthesis in a safety-informed model predictive controller example.

0.28

OpenSCvx: An Open-Source Modular and Extensible Nonlinear Trajectory Planning Package

cs.RO math.OC ·2026-08-21 ·Christopher R. Hayner, Griffin J. Norris, Fabio Spada, Samet Uzun, Avi Mittal +2 more
code/data similarity 0.57
Abstract

Trajectory optimization computes dynamically feasible motions that enable autonomous systems to accomplish complex tasks while satisfying operational and environmental constraints. This tutorial presents OpenSCvx, an open-source Python framework that bridges the gap between high-level problem specification and efficient numerical optimization. Rather than requiring users to derive solver-specific mathematical formulations, OpenSCvx provides a symbolic modeling interface that automatically constructs and solves trajectory optimization problems from modular descriptions of objectives, dynamics, and constraints. Beyond simplifying problem formulation, OpenSCvx supports (i) continuous-time constraint modeling, (ii) temporal and logical specifications, (iii) automatic vectorization for scalable and batched optimization, and (iv) a modular architecture that enables new algorithms, models, and solver backends to be incorporated with minimal effort. These capabilities allow researchers and practitioners to rapidly prototype, solve, and extend state-of-the-art trajectory optimization methods.

0.30

Dynamics-Aware Adaptive Corridors with Feasibility-Perturbed Trust-Region SQP for Certified Nonholonomic Motion Planning

cs.RO eess.SY ·2026-10-05 ·Yang Shi
benchmark similarity 0.55
Abstract

Optimisation-based parking planners usually impose collision constraints only at the time samples, so a vehicle corner can cut an obstacle between samples, and no executable trajectory exists until the solver converges. We present a planner for car-like vehicles with reverse gear in which every iterate of the optimisation phase satisfies the discretised dynamics exactly and keeps the whole vehicle rectangle clear of obstacles between the samples. Each time interval receives one convex corridor that holds all vehicle corners at both ends and is shrunk by a sweep margin bounding how far the corner paths leave their chords. Separating half-planes give the corridors a direction out of obstacles when the initial guess is in collision; later, heading-aligned boxes are grown from the speed, curvature and step of the current iterate and rebuilt after accepted steps. A feasibility-perturbed trust-region sequential quadratic programming method projects each step onto the dynamics by feedback and verifies it exactly; the cost decreases monotonically, and once the corridors stop changing, limit points are Karush-Kuhn-Tucker points of the corridor-constrained problem or violate a constraint qualification. On 820 benchmark cases the planner succeeds in 818 without penetration (797 from the first initial guess), none of the 7103 evaluated optimisation-phase iterates is unusable, and it succeeds in 96.5% of the cases when 99% of the initial guesses intersect an obstacle. Its maneuvers take 0.7% longer in the median than those of a similarly certified exact-collision baseline. The guarantees hold for the planning model, not for a physical vehicle.

0.32

ConicFlow: constrained Inference-time optimal control for flow matching models

cs.AI cs.CVcs.LGeess.SY ·2026-10-09 ·Shervin Khalafi, Kasra Fallah, Sung Cho, Dongsheng Ding, James Anderson +1 more
similarity 0.54
Abstract

We propose ConicFlow, which frames constrained sampling from a flow matching model at inference time as an optimal control problem that balances deviation from the pretrained trajectory against reward, subject to hard terminal constraints. We discretize this problem and adapt receding-horizon control, optimizing only a short window of the trajectory at each step for computational tractability. We address the resulting sequence of receding-horizon subproblems with a receding-horizon primal-dual algorithm. Its dual multipliers capture the difficulty of satisfying each constraint and are refined throughout sampling, steering generation toward feasible final samples. We further propose a terminal-estimate variant that avoids accumulating local truncation errors by evaluating the reward and constraints at the predicted terminal point rather than at the end of the current horizon. Under standard regularity assumptions, we establish finite-horizon guarantees on suboptimality. Under convex-affine structure, we derive a sharper bound that scales linearly with omitted horizon length, and we show that the terminal-estimate variant is provably tighter when the flow dynamics change slowly. Experiments in both low- and high-dimensional settings with a recent large-scale flow matching model show that ConicFlow achieves high reward and strong constraint satisfaction while deviating less from the pretrained flow than recent baselines.

0.23

Strengthening Compact Vehicle Routing Formulations through Arc-Flow Aggregation and Refinement

cs.DM math.OC ·2026-11-15 ·Julian Yarkony, Willem-Jan van Hoeve, Anthony Karahalios, Martin Karyamsetty, Soheyl Khalilpourazari +2 more
similarity 0.54
Abstract · 47 pages. Submitted to Transportation Science

Arc-flow formulations can provide strong relaxations for mixed-integer program formulations of vehicle routing problems, but the associated networks may be prohibitively large. We study the setting in which multiple arc flow relaxations may be applied, and introduce a dual-guided aggregation and refinement framework that constructs substantially smaller arc-flow formulations while recovering the LP bound of the original networks. Dual information is used both to identify states that can be aggregated without weakening the bound and to guide node disaggregation. We show that the resulting procedure converges finitely to the arc-flow bound of the full arc-flow formulation. The framework retains the original decision variables, allowing cutting planes to be added directly in the original variable space. Moreover, it produces an explicit MILP formulation without relying on column generation or pricing to determine the arc-flow relaxation bound. We apply our approach to the vehicle routing problem with time windows for which we define two arc flow relaxations, as well as two families of cutting planes over the original variable space. Computational experiments show that strong bounds can be obtained using substantially aggregated networks. The resulting root bounds are competitive with those obtained by the branch-and-price solver RouteOpt, while retaining a formulation that can be solved directly by a general-purpose MILP solver.

0.30

Learning Regions of Attraction for Transverse Feedback Linearization under Controller Singularities

cs.AI eess.SY ·2026-11-17 ·Abdullah Waqar Malik, Hamza Tariq, Adeel Akhtar
code/data similarity 0.53
Abstract · 27 pages (10 main + references + appendix), 1 figure, 8 tables

Transverse feedback linearization (TFL) achieves path following by exactly linearizing the error dynamics, but its controller is undefined on a singular set, such as zero speed for a unicycle or zero thrust for a quadrotor. The constrained region of attraction, the set of initial states from which the closed loop converges to the path without violating state or regularity constraints, determines where the controller can be safely activated. Exploiting the exact linear error dynamics, we show that this region is the largest forward invariant subset of the admissible set. We then decompose its state-constrained Zubov value function into an analytically known quadratic cost-to-go and a safety value function. We learn only the latter, by fitted value iteration without infinite-horizon trajectory labels. The resulting estimate combines an inner layer verified by interval branch and bound with a learned outer layer tested on samples. On a unicycle following a circle and a sinusoid and on a planar quadrotor, it covers on average 72.0%, 83.4% and 19.1% of the simulated region of attraction. In comparison, the quadratic cost-to-go and two physics-informed neural network (PINN) solvers of Zubov's equation cover at most 11.3%, 4.0% and 0.0% on average. Code and animations are available at https://gradslab.github.io/roa_tfl

0.47

Certified Zonotopic Reachability Analysis for Trajectory Tracking on Lie Groups

eess.SY cs.RO ·2026-11-09 ·Yanliang Huang, Peng Xie, Zhen Zhang, Zhuoqi Zeng, Amr Alanwar
similarity 0.53
Abstract

Autonomous vehicles track planned trajectories close to obstacles. Unknown disturbances make them deviate from these trajectories. With a bound on the tracking error that disturbances can cause, a planned trajectory can be certified as safe before execution. Existing set-based methods bound the tracking error by one invariant ellipsoid for the whole trajectory or by intervals, which are both conservative. For aerial and space vehicles, the tracking error evolves on a matrix Lie group with nonlinear dynamics. However, for group-affine systems, the error dynamics are linear in Lie algebra coordinates when the vehicle receives the inputs of the reference. The control input and the disturbance enter through the inverse right Jacobian, a matrix that depends on the error. We propagate the linear part of the error dynamics with zonotopes and enclose the effect of the inverse right Jacobian on the disturbance in closed form. The resulting tubes are tight and provably contain all reachable tracking errors in continuous time. When some error components have no input, the inverse right Jacobian leaves unmatched nonlinear terms in the closed loop. None of the tested methods certifies such a closed loop. Hybrid coordinates make these terms matched, so that our controller cancels every nonlinear term that does not contain the disturbance. Our tubes give tighter bounds than the ellipsoid method in simulations of a planar aircraft and a fully actuated multirotor and in real flights of a quadrotor, where the tube contains every measured attitude error. Under larger disturbances and the same feedback gain, the ellipsoid method yields no valid ellipsoid, whereas our tubes remain valid.

0.24