CS Paper Radar

Solving quantified constraint satisfaction problems with applications to control

Éric Goubault, Nuwan Herath Mudiyanselage, Sylvie Putot

cs.LO ·submitted 2026-10-29 10:26 UTC · v1
published

Abstract

Many problems in control can be expressed as quantified constraints, such as robust forward and backward reachability, synthesis of controllers, solutions to motion planning problems. In this paper, we develop a method for computing inner and outer approximations of global solutions to very general quantified constraints, generalizing widely the state of the art on similar problems, usually restricted to at most one alternation of quantifiers or to local solutions. By global solutions, we mean characterizing accurately the entire set of solutions, within some prescribed bounds. For this, our approach uses a set inversion technique relying on oracles for set inclusion using local solutions to related quantified reachability problems. We exemplify the approach throughout the paper on different examples related to control problems.

Journal ref
29th ACM International Conference on Hybrid Systems: Computation and Control, May 2026, Saint-Malo (35400), France

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Constraint Extraction for Corrective Control under STL Specifications via Logical Dependency Tracking

cs.LO cs.ROeess.SY ·2026-09-08 ·Antoine Besset, Joris Tillet, Chuchu Fan, Julien Alexandre dit Sandretto
publishedcode/data similarity 0.60
Abstract · Accepted for publication at 65th IEEE Conference on Decision and Control (CDC 26)

Ensuring the satisfaction of Signal Temporal Logic (STL) specifications under uncertainty is challenging, as reachability-based monitoring provides guarantees but does not indicate how to restore satisfaction when it becomes indeterminate. A key difficulty is identifying which uncertain components actually affect global satisfaction, especially for nested formulas. This paper introduces a logical dependency tracking framework that propagates uncertainty through the STL structure and captures the causal contribution of reachable sets to satisfaction. By associating markers to uncertain predicates and propagating them via three-valued semantics, we extract in milliseconds a compact Disjunctive Normal Form (DNF) of sufficient constraints, avoiding combinatorial enumeration. As an application, we formulate control correction as a minimum-effort optimization problem. Using zonotopic reachability, the derived constraints are enforced via linear programming, yielding corrections that guarantee STL satisfaction under bounded uncertainty and provide certified probabilistic bounds in the stochastic case. We demonstrate the approach on a nonlinear system with nested STL specifications, showing that dependency tracking enables efficient and formally guaranteed correction. The tracking implementation is available at https://github.com/Antoine-Bst/STL-Three-Valued-Clause-Filtering/.

0.50

What Makes a Good Symbol for Hybrid Discrete-Continuous Planning?

cs.RO ·2026-10-16 ·Yiyuan Pan, Changliu Liu, Jiayuan Mao
similarity 0.59
Abstract

The physical world has continuous state and action spaces, yet robot planning often benefits from hybrid discrete-continuous formulations that explicitly expose combinatorial structure, such as contact modes or discrete primitive actions. Existing methods typically rely on human-defined symbol sets or symbols derived from language supervision, without asking what makes a symbol computationally useful. In this paper, we take an inference-algorithm--centric view to define usefulness: a good symbol should expose the discrete commitments that simplify solving the original planning problem. We first introduce the concept of solver-sufficient symbolization by studying finite-horizon piecewise-affine systems, for which solver sufficiency can be precisely characterized, and develop a counterexample-guided algorithm for symbol invention. We then extend this principle to invent symbols for optimization objectives parameterized by general neural networks as energy functions, showing that solver-sufficient symbols can nevertheless be induced from their continuous optimization landscapes. Experiments on simulated and real-robot tasks show that the resulting symbols reduce solving cost while preserving solution quality, while also improving interpretability and steerability. Furthermore, our theoretical and algorithmic insights help explain why certain human-defined symbols are computationally useful.

0.37

ElastiQP: An Always-Feasible QP Solver for Constrained Robot Control

cs.RO math.OC ·2026-09-16 ·Daniel Morton, Jon Arrizabalaga, Zachary Manchester, Marco Pavone
code/datahot direction similarity 0.58
Abstract

As robot capabilities increase, quadratic programming (QP)-based controllers must account for a similarly increasing number of constraints to ensure safe, reliable operation. Yet, with each added constraint, this introduces more chances of momentary conflict: in which case, a QP solver that returns an "infeasible" status leaves the controller with nothing to execute. To address this, we introduce ElastiQP, a modified dual active-set QP solver that relaxes every inequality constraint with an exact, per-constraint l1 penalty while keeping equality constraints (dynamics) hard. Notably, ElastiQP does so by folding the slack variables into the solver analytically, maintaining a constant size of the condensed linear system. On a suite of robot control benchmarks, ElastiQP achieves microsecond-level performance, matching or outperforming leading modern solvers on feasible problems. On infeasible problems, ElastiQP handles these gracefully, confining violations to strictly the conflicting inequality terms, returning a usable solution up to 40x faster than the best alternative solvers. ElastiQP is available as an open-source C++ header-only library, with Python and JAX interfaces, at https://github.com/StanfordASL/elastiqp.

0.64

Motion Planning with Temporal Logic Precedence Specifications in Dynamic Environments via Spacetime Augmented Graphs of Convex Sets

eess.SY ·2026-10-19 ·Shilin You, Lars Lindemann, Tyler H. Summers
similarity 0.57
Abstract

We extend the augmented graph of convex sets GCS framework for motion planning with temporal logic precedence specifications to dynamic environments in which obstacles, keys, and doors undergo piecewise-linear translation and/or dilation over time. The main insight is that piecewise-linear motion of polytopic sets in R^d lifts exactly to a static polytopic partition of spacetime R^d X R_>=0. We show that the main result from the static case carries over to spacetime essentially without modification: a shortest path in the spacetime augmented GCS provides an exact optimal solution to the motion planning problem with precedence specifications. Moreover, the layered subgraph lattice that encodes signal temporal logic (STL) precedence specifications retains precise correspondence with the Bellman--Held--Karp (BHK) algorithm, and the full library of restricted but expressive STL specifications generalizes to the dynamic setting. Further, the framework allows time-gated keys and doors, collectible or passable only within a temporal window. The geometric side of the framework requires two modifications: a causality constraint (the time coordinate of a trajectory must be non-decreasing) and a spacetime speed constraint (bounded physical velocity), both of which are convex in the Bézier control points.

0.23

Planning along Differentiable Charts of Constraint Manifolds with General-Purpose IK Solvers

cs.RO ·2026-09-09 ·Thomas Cohn, Seiji Shaw, Harel Biggie, Travis Manderson, Nicholas Roy +1 more
theory similarity 0.57
Abstract · 8 pages, 4 figures, 3 tables. Under review. Project website: https://cohnt.github.io/inverse-function-theorem-parameterization/

Planning trajectories for robot manipulators under kinematic equality constraints restricts feasible motions to a measure-zero submanifold of the configuration space, requiring special algorithmic treatment. A promising strategy is parametrizing the set of feasible configurations using analytic inverse kinematics (IK). Bespoke analytic IK functions can be written to be differentiable, a necessary property for gradient-based trajectory optimization. But the vast majority of IK functions are computed by automated meta-solvers like IKFast, and are difficult to modify for differentiability. We present a new approach for computing gradients of analytic IK parameterizations: we leverage the inverse function theorem to recover the desired gradients from the ordinary forward kinematic Jacobian. Furthermore, we present a least-squares domain extension and an optimization-amenable description of the reachability constraint, which preserves gradient signal outside the reachable workspace. We demonstrate the efficacy of our approach through numerical experiments and downstream tasks, including a hardware demonstration of an RB-Y1 picking up a box and placing it on a table. Project website: https://cohnt.github.io/inverse-function-theorem-parameterization/

0.54

TAMPAgent: Agentic Belief-Space Planning for Mobile Manipulation

cs.RO ·2026-11-02 ·Utkarsh A. Mishra, Alperen Degirmenci, Yongxin Chen, Danfei Xu, Tucker Hermans +1 more
similarity 0.57
Abstract · Website link: https://umishra.me/TAMPAgent/

Open-world robotic mobile manipulation requires acting in physical environments with only partial information. While recent Large Vision-Language Model (LVLM) agents show strong open-world reasoning capabilities, existing architectures that rely on direct tool calling struggle with geometric uncertainty and thus are limited to fully-observable tabletop environments. In contrast, Task and Motion Planning (TAMP) systems can solve long-horizon tasks under partial observability but incur high computational costs and require closed worlds. We propose \textbf{TAMPAgent}, an agentic planning framework that unifies the reasoning of LVLMs with the structured constraint satisfaction of TAMP systems. We endow an LVLM agent with a belief-space planning model operating over an extensible API of perception, planning, and control tools. The agent formulates a partial task plan composed of parameterized observation and execution actions, which is subsequently completed using classical search algorithms. After extracting the plan's geometric constraints, the agent leverages its tool API to bind valid parameter values, satisfying feasibility requirements and producing an executable motion plan. Upon execution, the agent continuously updates its belief history and repeats this closed-loop process by interleaving observation and manipulation actions. Evaluated across complex household mobile manipulation tasks on Rainbow Y1 and Unitree G1 platforms, TAMPAgent significantly outperforms direct tool-calling agentic baselines, demonstrating that integrating TAMP constraint satisfaction into agentic planning loops is essential for unstructured, partially observable environments.

0.17

Computing Fixed Points using Dependency Oracles

cs.LO ·2026-08-13 ·Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Daniele Toller
similarity 0.57
Abstract

We present global and local algorithms for solving systems of equations over Noetherian posets with a bottom element, a general setting underlying many verification problems. Our algorithms compute the solution of a selected variable by restricting exploration to those parts of the system required to determine its value. We achieve this by computing variable dependencies by means of dependency oracles. Oracles guide the exploration of the system and provide sound termination criteria for local fixed-point computation. A key advantage of our approach is its flexibility: oracles can be customized, composed, or over-approximated, offering a principled way to trade precision for performance without compromising correctness. We evaluate our solution against existing algorithms from the literature and show that our prototype implementation is competitive and often outperforms specialized solutions, while remaining simple and adaptable across diverse application domains.

0.04

Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation

cs.RO math.OC ·2026-08-26 ·Shashank A. Deshpande, Jonathan P. How
code/data similarity 0.55
Abstract · 28 pages. Code: https://github.com/croshank/DFTSearch

Steering-based planners require solutions to state-to-state boundary value problems, which can be inaccessible for nonlinear platforms. Forward propagation evades the steering requirement, but the finite-sample behavior of the associated planners remains uncharacterized and their implementations underperform in practice. This paper develops a propagation-based kinodynamic planner with deterministic finite-sample near-optimality guarantees. We work within the large class of differentially flat nonlinear systems and show that a forward tree of locally dispersive control commands contains a near-optimal trajectory at a certified tree size. We provide a general mechanism to construct dispersive command sets for control-affine systems, which are necessary to implement the search algorithm prescribed by the theory. We show that covering the certified trajectory class irrespective of cost provably demands a tree exponentially sized in the problem horizon, and present a cost-conditioned dominance pruning procedure that retains near-optimality at a tree size polynomial in the horizon. We implement the resulting search algorithm, Dispersive Forward Tree search (DFT*), as breadth-first expansion of the forward tree, which maps naturally onto parallel hardware. We design efficient dispersive samplers for the unicycle, the trailer car, and the quadrotor and evaluate challenging planning tasks for these platforms. DFT* delivers consistently competitive and often substantially better solution quality than state-of-the-art kinodynamic planners at comparable solution times on embedded-tier processors, accelerating further as parallel compute is scaled. We also implement DFT* in a receding-horizon loop to demonstrate real-time planning in dynamic environments at embedded-tier compute budgets.

0.49