CS Paper Radar

Scalable Tube-Tightened Multi-Agent Safety via Certified Constraint Reduction

Armel Koulong

eess.SY ·submitted 2026-08-26 03:10 UTC · v1

Abstract

This paper develops a certified constraint-reduction method for distributed model predictive control with tube-tightened exponential control barrier functions (eCBFs) in multi-agent systems. At each prediction stage, pairwise agent--agent and agent--obstacle eCBF conditions define halfspaces in the local control space. Rather than enforcing all such halfspaces, a geometry-adaptive subset is retained and a Farkas certificate verifies that the reduced admissible set is contained in the full tightened set. For planar inputs, cone coverage is characterized through the largest angular gap: two extreme directions suffice in the strict half-plane regime, while other geometries initialize with three retained constraints and escalate only when certification fails. Conic multipliers and nominal-aware offsets are obtained in closed form, without an auxiliary optimization, and the resulting construction preserves any nominal control already admissible for the full tightened set. Consequently, the reduced controller inherits the robust safety guarantee of the underlying tube-eCBF formulation. In a ten-follower, four-obstacle study, the method retained fewer safety constraints on average, reproduced the full filter's nominal accept/reject decisions with no true safety violations, and achieved increasing computational gains as the constraint count and prediction horizon grew.

Comment
Submitted for consideration at the 2027 American Control Conference (ACC)

Closest papers

Nearest neighbours by meaning across the whole index.

Configuration-Constrained Tube MPC for Difference-of-Convex Nonlinear Systems

eess.SY math.OC ·2026-09-07 ·Filippo Badalamenti, Jose A. Borja-Conde, Filiberto Fele, Teodoro Alamo, Daniel Limon
similarity 0.63
Abstract · 11 pages, 3 figures, submitted to Automatica

This paper develops a convex tube model predictive control formulation for constrained nonlinear systems. We consider dynamics described by a discrete-time state-space model with parametric and additive uncertainty that admits a difference-of-convex decomposition. Convex directional bounds of the nonlinear dynamics are combined with configuration-constrained polytopic tubes, whose predefined combinatorial structure yields an affine parameterization of their vertices. The resulting finite-dimensional sufficient conditions certify robust one-step tube propagation under parametric uncertainty and additive disturbances, while allowing the tube geometry and an associated vertex control law to be optimized jointly in a single convex program. An implicit terminal condition guarantees recursive feasibility and convergence of the predicted tube to a target robust control invariant set. Numerical results illustrate the closed-loop properties and the trade-off between geometric flexibility and computational complexity.

0.23

Collective Tube Model Predictive Control With Distribution-Free Joint Safety Certificates

eess.SY ·2026-09-22 ·Giuseppe C. Calafiore
theory similarity 0.63
Abstract

Data-calibrated stochastic MPC typically builds separate risk margins for many events along the horizon, such as times, facets, state/input components, or obstacles, and then combines them with a union bound. This approach is valid, but it does not match the key object used in the tube-MPC recursive-feasibility proof, which shifts a complete error tube. This paper develops collective tube MPC (CT-MPC), where the calibrated uncertainty object is the finite-horizon prediction-error trajectory. A reusable trajectory tube is calibrated offline, its cross-sections define deterministic Pontryagin tightenings online, and the certified violation event is that a fresh prediction-error trajectory leaves the tube. For linear systems with additive uncertainty and fixed ancillary feedback, we prove joint state-input safety over the prediction horizon, one-step recursive feasibility from an explicit shifted candidate, a finite-deployment risk bound, and a practical value-decrease inequality. The finite-sample certificate is distribution-free under split calibration and has beta-binomial form; its complexity is the certified number of residual trajectories that can define the tube, rather than the number of horizon-constraint blocks. We also give implementable shift-compatibility tests for polytopic tubes and a stable-compression fallback for irregular tube designers. Numerical experiments compare CT-MPC with Bonferroni tightening, a sample-envelope tube, and a joint-in-time conformal MPC baseline. The collective tube reduces deterministic tightening while preserving empirical safety and recursive feasibility.

0.21

Exact Feasibility Certification and Optimal Responsibility Allocation for Multi-Robot CBF Safety Filters

cs.RO cs.MA ·2026-09-14 ·Chandan Kumar Sah, Jishnu Keshavan
hot direction similarity 0.62
Abstract

Multi-robot Control Barrier Function (CBF) safety filters can become infeasible, but a failed quadratic program (QP) does not indicate why the conflict occurred or how to resolve it. To address this, we develop an exact feasibility certificate for multi-agent CBF filters with heterogeneous control-affine dynamics and convex input sets. The certificate quantifies a feasibility reserve by separating the demand imposed by safety constraints from the available actuator supply. This decomposition shows when CBF gain tuning or increased actuation can and cannot resolve infeasibility, and identifies the agents and interactions responsible for the conflict. We further propose an algorithm to optimally allocate shared safety constraints by maximizing the worst local feasibility margin, yielding a linear program for polyhedral input sets. In $320$ paired closed-loop simulations, the proposed allocation reduces infeasible control steps from roughly $50\%$ to $6.2\%$, and reduces safety-violating runs from $118/160$ to $24/160$. In addition, across $52$ infeasibility events, the certificate identifies an interaction whose relaxation restores feasibility in $94\%$ of cases.

0.31

Safety-Aware Dimension Selection for Reduced-Order Model Predictive Control

eess.SY ·2026-10-12 ·Amirhossein Asadi, Nitin Sharma
similarity 0.60
Abstract

Model reduction can substantially reduce the computational burden of model predictive control (MPC) for high-dimensional systems, but a reduced dimension chosen for performance may be insufficient for safety-critical operation. This paper introduces a safety-aware dimension-selection framework in which the prediction model adapts to the order of the model required to maintain a certified finite-horizon safety condition. Dynamic active subspaces provide a performance-oriented ordering of reduced coordinates, while finite-horizon error bounds robustly enforce discrete-time control barrier function constraints. The controller selects the smallest prediction order for which the resulting safety-critical MPC problem remains feasible. We establish full-order horizon safety, recursive feasibility, and closed-loop invariance of the safe set under the proposed reduced-order formulation. The proposed approach therefore adapts the prediction complexity to safety requirements, avoiding unnecessary high-dimensional prediction during benign operation.

0.08

Safety-Filtered Distributed Koopman-MPC

cs.RO eess.SY ·2026-09-23 ·Shengjun Zhang, Wenhao Li, Zhenxin Lin, Zhenglong Sun
theory similarity 0.60
Abstract

Distributed model predictive control (DMPC) often constructs both predictions and collision constraints from neighbor trajectories, so packet loss can remove both. We separate these roles: received trajectories drive Koopman-MPC, while local sensing and shelf geometry define a hard-constrained quadratic program (QP) that projects the applied input. Its radial demand is the least constant acceleration that keeps a supporting-plane clearance nonnegative throughout one zero-order-hold interval. Complementary pair rows recover the coupled demand without exchanging safety decisions. We give an intersample separation theorem under bounded snapshot and directional plant errors, an exact max-min test for simultaneous local feasibility, and a sensing-radius condition for switching interaction graphs. Anticipatory high-order rows may be relaxed for performance, but the finite-hold rows contain no safety slack. Matched eight-robot warehouse simulations use a frozen Koopman model, nonlinear drift, bounded inputs and speed, shelf constraints, a 120 ms control period, and packet dropout. The full controller is collision-free in 20/20 matched trials and reaches 160/160 robot goals; predictive Koopman-MPC without the final projection is collision-free in 1/20 trials. All 38,400 full-method hard-row sets pass the online feasibility test, and every local QP solves. Five-stream fleet sweeps are collision-free and hard-row feasible through 16 robots; the 20-robot boundary fails only after the online margin turns negative, while the reconstructed per-agent critical path remains below the sampling period. Bounded-sensing and differential-drive tests provide additional deployment stress.

0.19

Anytime Primal--Dual Certification of the Maximum Disturbance Radius in Robust MPC

eess.SY ·2026-08-28 ·Wenqi Cai, Muhammad Bakr Abdelghany, Kyriakos G. Vamvoudakis, Anthony Tzes
similarity 0.59
Abstract

Adjustable-set robust model predictive control (MPC) characterizes a state-dependent maximum disturbance radius, which can be interpreted as a certified robustness reserve. Existing methods primarily focus on optimizing and propagating this reserve under in-set disturbances. This letter investigates how much reserve remains after a finite out-of-set disturbance without immediately re-solving the full optimization problem. To this end, we propose a two-sided reserve-depletion envelope formed by independent primal and dual correction hierarchies, which supply monotone lower and upper bounds, respectively. The envelope remains valid across active-set changes, has an online-computable width, and contracts monotonically under subspace expansion. Leveraging its finite-step exactness, we present a basis-first adaptive algorithm that operates in an anytime manner: every completed reduced solve returns a valid certificate, enabling early termination once a prescribed tolerance is reached. Across the tested cases, numerical studies report no certificate violations and median speedups of up to 4.97x over warm-started full re-optimization at a 2% certificate-width tolerance.

0.30

Certificate-Carrying Distributed Model Predictive Control on Product Manifolds with $\mathrm{SO}(3)$

eess.SY math.OC ·2026-09-25 ·Shengjun Zhang, Tingyi Liu, Lei Xu, Tao Yang
theory similarity 0.59
Abstract · 12 pages, 3 figures. Submitted to Automatica

This paper studies constraint certification in synchronous distributed model predictive control (DMPC) when neighboring predictions change between sampling instants. Before the parallel local solves, each agent communicates a shifted prediction and an announced update budget. A hard trajectory trust region makes that budget enforceable, while an edge-wise feasibility cap computed from the shifted packets keeps the fallback feasible without using any current optimizer output. Distance and relative-attitude constraints are tightened with explicit Lipschitz constants and two budget layers: one accounts for the simultaneous neighbor update and the other retains a checkable shift reserve. We prove hard pairwise constraint satisfaction and recursive feasibility under stated nominal-execution and terminal assumptions, give the additional residual caused by execution error, and derive a local practical value-decrease bound. A spacecraft formation example uses hard terminal and pairwise constraints, a geodesic relative- attitude constraint on $\SO$, and reproducible terminal-set checks. Comparisons with fixed, trajectory-only, and windowed online margins show that the proposed budget reduces conservatism while preserving a positive shifted-feasibility margin.

0.22

Safe Output-Regulation Flows for Constrained Optimization via Control Barrier Functions

eess.SY ·2026-11-05 ·Zihao Ren, Bingqi Liu, Lei Wang, Hongye Su, Guodong Shi
similarity 0.58
Abstract

Control-theoretic approaches to constrained optimization have been widely studied by interpreting optimization algorithms as dynamical systems. This paper formulates constrained optimization as an output-regulation problem with state constraints, where equality-constraint residuals are treated as regulated outputs and inequality constraints as state constraints. Proportional--integral feedback is employed to drive the equality-constraint residuals asymptotically to zero, while a control barrier function (CBF) safety filter is used to ensure inequality safety throughout the optimization process. We establish feasibility of the CBF filtering program throughout the inequality-feasible set and local exponential convergence of the resulting flow. Under stronger global conditions, we further prove convergence from an entire connected component of the inequality-feasible set. Since exact implementation of the flow requires solving a CBF quadratic program at each state, we further develop a flow that approximates the CBF solution through multiplier updates. Moreover, we provide a unified formulation encompassing the two proposed flows and projected primal--dual dynamics. Numerical examples demonstrate convergence, safety, and computational tradeoffs of the proposed flows.

0.13