PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Armel Koulong

arXiv:2608.25323v1eess.SY

TL;DR

Dense distributed MPC problems impose many tube-tightened eCBF halfspaces across agents, obstacles, and prediction stages. The paper retains a geometry-adaptive subset and certifies containment with Farkas-based cone coverage, preserving robust safety; experiments report fewer constraints, matching nominal decisions, no true safety violations, and increasing computational gains with scale.

  • Problem

    Distributed MPC safety enforcement can impose many pairwise agent and obstacle eCBF constraints across interaction neighborhoods and prediction horizons.

  • Method

    The method retains geometry-adaptive tube-tightened eCBF halfspaces and uses Farkas containment certificates, cone coverage, closed-form multipliers, and nominal-aware offsets.

  • Results

    2.80 safety constraints on average versus 13 for the full formulation, a 4.6× reduction, while full and reduced formulations report the same final formation error and minimum clearances.

  • Takeaways & Limitations

    The reduced controller preserves the robust safety guarantee of the unreduced tube-eCBF formulation while reducing explicitly enforced constraints and gaining more computational benefit as constraint count or horizon grows.

Abstract

from arXiv · show

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.

I. INTRODUCTION

DMPC distributes constrained multi-agent control across local finite-horizon problems, but safety constraints multiply with interaction density and horizon length. The paper introduces certified, geometry-adaptive reduction of tube-tightened eCBF constraints while preserving containment and robust safety.

  • DMPC lets each agent solve a local finite-horizon problem while coupling through exchanged predicted trajectories.
  • Collision and obstacle avoidance add pairwise safety constraints at each interaction and prediction stage, increasing computational burden in dense environments and long horizons.
  • The method retains a subset of tube-tightened eCBF halfspaces and uses a Farkas certificate to guarantee the reduced admissible set is contained in the full set.
  • For planar inputs, cone coverage retains two extreme directions in the strict half-plane regime, otherwise starting with three constraints and escalating only when certification fails.
  • Closed-form conic multipliers and nominal-aware offsets support reduction without an auxiliary optimization while preserving admissible nominal controls.
  • The formulation addresses follower synchronization and safety under bounded disturbances using tube-based robust predictive control and barrier constraints.

A. Tightened eCBF Functions [3]

Safety is represented by pairwise and obstacle barrier functions, with exponential high-relative-degree conditions enforcing forward-invariance requirements under the system dynamics. Tube support functions tighten these conditions against tracking-error uncertainty.

  • Pairwise and obstacle barrier functions encode minimum inter-agent separation and obstacle avoidance using geometric distance conditions.
  • The barriers are assumed convex, sufficiently differentiable, and of uniform relative degree, with Hurwitz polynomial gains for the exponential CBF construction.
  • For the specified dynamics, the barrier relative degree equals the system order because the input enters only at the nth derivative.
  • Support-function tightening is applied to both inter-agent and obstacle constraints to account for robust positively invariant tracking tubes.

B. Halfspace form

After predicted states and neighboring trajectories are fixed, each tightened eCBF condition becomes a halfspace in the local control input. Neighbor- and disturbance-dependent quantities enter through scalar offsets rather than the normal vector.

  • The tightened eCBF inequality is affine in the local decision input once the predicted state and neighboring trajectory are fixed.
  • Neighbor trajectories are generated from plans broadcast at the previous instant in the distributed MPC implementation.
  • Neighbor- and disturbance-dependent quantities affect the scalar offset bij, while the vector aij remains independent of them.

Problem Statement:

Each agent faces one tightened safety halfspace per relevant neighbor or obstacle at every prediction step, creating a constraint burden that grows with threat count and horizon. The proposed reduction retains a geometry-adaptive subset and certifies containment of the full admissible set, including tube-tightening margins.

  • Each relevant neighbor and obstacle contributes a tightened safety constraint, and every constraint is imposed across the prediction horizon.The resulting burden grows with neighborhood size and horizon length.
  • The reduction targets the dominant computational burden by enforcing a small geometry-adaptive subset whose admissible set is certified contained in the full set.
  • The index set Ji combines neighboring-agent and obstacle-induced safety constraints participating in the reduction.
  • A Farkas containment certificate uses nonnegative conic multipliers and offset inequalities to show that retained halfspaces imply each omitted full constraint.
  • Tube-tightening margins preserve the containment certificate because the same conic multipliers remain valid after robustness margins are added.

A. Selecting the directions

The method selects a small subset of safety directions whose conic hull covers all original normals, using planar geometry and escalation when coverage is not certified.

  • A. Selecting the directions: In the strict half-plane regime, retaining the two directions adjacent to the largest angular gap generates every original normal.The complementary arc has width less than π, so its two extreme rays suffice.
  • A. Selecting the directions: When the largest angular gap satisfies G < π, the full cone is R2 and accepted retained directions must positively span R2.Positive spanning is stronger than covering only the particular original directions.
  • A. Selecting the directions: When G = π, two antiparallel rays suffice only for collinear normals; a non-collinear closed half-plane requires at least three retained directions.The retained subset must generate the same conic hull as the full set.
  • A. Selecting the directions: The G ≤π branch initializes with K = 3 when at least three constraints exist and increases K until exact cone coverage is achieved.Escalation terminates at K = |Ji|, where retaining the full set makes coverage trivial.
  • A. Selecting the directions: Once coverage holds, every dropped planar normal has a nonnegative representation using at most two retained directions, obtained by a closed-form 2 × 2 solve.This converts geometric selection into the conic multipliers needed for containment certification.

B. Choosing the offsets

After selecting directions, the method constructs reduced offsets that satisfy containment while minimizing their worst-case margin relative to a prescribed nominal control.

  • B. Choosing the offsets: The reduced offsets must satisfy conic combinations of retained offsets that dominate every original tube-tightened offset.Direction selection fixes reduced normals but does not determine their offsets.
  • B. Choosing the offsets: The auxiliary scalar ε measures the worst-case reduced-offset margin relative to vnom, and minimizing it favors the nominal control.The containment inequalities remain hard constraints, so offset selection changes conservatism but not certificate validity.
  • B. Choosing the offsets: Proposition 3.4 provides finite reduced offsets once cone coverage is established, so offset construction requires no separate certification escalation.At this stage, cone coverage is the only certificate-construction failure mode.
  • B. Choosing the offsets: At full-set fallback, the original normals and offsets are restored, the reduced and unreduced constraint sets coincide exactly, and the identity multipliers certify containment.The selector affects the amount of reduction, while correctness depends on certification of the retained set.

IV. MAIN RESULT

Under the stated tube-validity and eCBF assumptions, certified reduction preserves robust safety and keeps any nominal control that was already admissible for the full tightened set.

  • IV. MAIN RESULT: The construction acts on tube-tightened eCBF halfspaces, transferring the nominal-level directional certificate through tube tightening with the same conic multipliers.Propositions 3.1–3.4 provide selection, multipliers, and offsets before the main guarantee is applied.
  • IV. MAIN RESULT: Theorem 1 establishes eUi ⊆ Ui, so every reduced-feasible control satisfies all full tube-tightened safety eCBF constraints.The containment result applies when retained directions have nonnegative conic multipliers and offsets follow Proposition 3.4.
  • IV. MAIN RESULT: If the tightened constraints hold along the closed-loop trajectory, tube validity holds, and required initial conditions are satisfied, the original safety sets are forward invariant for the disturbed system.This is the robust-safety consequence inherited from the underlying eCBF invariance result.
  • IV. MAIN RESULT: If vnom ∈ Ui, then ε⋆ ≤ 0 and vnom ∈ eUi, so an already admissible nominal control is preserved by the reduction.The nominal-aware offsets prevent containment from unnecessarily excluding that safe nominal action.

V. IMPLEMENTATION

The implementation recomputes stage-dependent certificates along the horizon, reuses retained indices when possible, and enlarges them when coverage or OCP feasibility requires it.

  • V. IMPLEMENTATION: Stage-dependent normals, conic multipliers, and reduced offsets are recomputed at every prediction stage because predicted geometry varies along the horizon.The initial retained set is selected at l = 0.
  • V. IMPLEMENTATION: For later stages, the previous retained index set is reused and re-certified with current-stage normals whenever possible.If cone coverage fails, the set is reselected or enlarged for that stage.
  • V. IMPLEMENTATION: If the certified reduced OCP is infeasible, retained sets are enlarged and may escalate to the full-set fallback Ki(l) = Ji.At fallback, the reduced OCP coincides exactly with the unreduced OCP.

VI. NUMERICAL SIMULATION

The numerical study extends the reference implementation to ten followers and four obstacles while retaining the follower model, safety parameters, and disturbance setting.

  • The scenario includes ten followers, four obstacles, and a follower jerk-servo model.Agents 6–10 reuse five follower fields cyclically, and the study adds two obstacles to the reference implementation.
  • The study uses eCBF gains (κ0, κ1, κ2) = (30, 38, 3) and a safety distance of dsafe = 0.1 m.
  • The implementation sets umax = 300, sampling period Ts = 0.05 s, and disturbance bound ∥wi∥∞≤0.4.

A. Closed-loop results

In the ten-follower, four-obstacle closed-loop study, the reduced controller retained far fewer constraints while matching the full formulation's reported formation and clearance outcomes without tightened-halfspace violations.

  • A. Closed-loop results: 0.0% constraint violations were reported for both full and reduced filtered runs.Constraint violations mean that the applied input violated at least one original tube-tightened eCBF halfspace.
  • A. Closed-loop results: 2.80 safety constraints were retained on average versus 13 for the full formulation, a 4.6× reduction.
  • A. Closed-loop results: The reduced formulation matched the full formulation's reported final formation error and minimum clearances.
  • A. Closed-loop results: The workflow selects or reuses retained sets, certifies cone coverage, and escalates locally when directional certification fails.OCP infeasibility can enlarge affected stage sets up to the exact full-set fallback.
  • A. Closed-loop results: Minimum obstacle clearance increased from 0.1483 m without filtering to 0.2721 m with either safety formulation.Inter-agent separation remained well above dsafe = 0.1 m.

B. Where the reduction pays

Scaling sweeps show that reduction is nearly cost neutral for small single-step cases but becomes increasingly beneficial as safety-constraint count or prediction horizon grows.

  • B. Where the reduction pays: 147× and 458× growth factors occurred for full solve times across the two scaling sweeps, versus 4.7× and 7.0× for reduced solves.Times are milliseconds per solve and include all reduction overhead.
  • B. Where the reduction pays: At |Ji| = 13 and Np = 1, the isolated benchmark achieved only a 1.24–1.26× speedup, while the complete implementation achieved 0.94× end-to-end.
  • B. Where the reduction pays: Reduction is essentially cost neutral for the small single-step case but increasingly beneficial as |Ji| or Np grows.
  • B. Where the reduction pays: The reduced formulation preserves the reported closed-loop performance of the full formulation while reducing explicitly enforced constraints.
Loading 2608.25323v1…