PaperlayerView exact revision on arXiv

Source-linked AI summary

Safety-Filtered Distributed Koopman-MPC

Shengjun Zhang, Wenhao Li, Zhenxin Lin, Zhenglong Sun

arXiv:2609.27463v1cs.ROcs.SYeess.SY

TL;DR

DMPC can use neighbor trajectories for both horizon planning and collision constraints, so packet loss can affect both. This paper uses received trajectories for Koopman-MPC and local sensing for a hard projection of the applied input. In matched eight-robot trials, the full controller is collision-free in 20/20 trials, compared with 1/20 for predictive Koopman-MPC without the projection.

  • Problem

    DMPC often derives both predictions and collision constraints from neighbor trajectories, allowing a lost packet to affect both planning and safety constraints.

    Source: §I · p. 1

  • Method

    The architecture uses received trajectories for nominal Koopman-MPC planning and a local-sensing-based hard QP to project the applied input.

    Source: §I · p. 1, B. Local Predictive Planning · p. 3

  • Results

    20/20 full-controller trials are collision-free, versus 1/20 for predictive Koopman-MPC without the final projection; the full controller reaches 160/160 robot goals.

    Source: C. Main Warehouse Result · p. 7

  • Takeaways & Limitations

    The safety claim is conditional on stated residual and sensing bounds and local feasibility; the theory addresses collision avoidance, not deadlock avoidance or goal convergence.

    Source: §V · p. 6

    The collision-avoidance claim requires the stated residual and sensing bounds and µ_i(k) ≥ 0 for every active hard-row set; infeasibility leaves the ensuing hold without a collision-avoidance claim.

    Source: §V · p. 6

Abstract

from arXiv · show

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.

I. INTRODUCTION

DMPC can lose both its neighbor-based plans and collision constraints when packets are dropped; this paper separates nominal planning from locally sensed constraints on the applied input. It frames that design against predictive, reactive, and barrier-based safety approaches and states the plant, sensing, and communication conditions for its problem.

I. INTRODUCTION

  • The baseline Koopman-MPC planner reaches goals accurately but collides in nearly every packet-loss run, motivating separation of task progress from applied-input safety constraints.The paper distinguishes collision avoidance from route-level completion.Source: §I · p. 1
  • The proposed architecture uses exchanged trajectories for nominal planning but builds final pair constraints from local sensing, so packet loss does not remove constraints for sensed pairs.The paper's stated theory addresses collision avoidance, not learned-model stability or global liveness.Source: §I · p. 1

II. RELATED WORK

  • Koopman predictors support nominal planning, while recent distributed CBF methods optimize coupled horizons; this design instead uses a local nominal planner and a current-step safety QP,,, [14].The paper says this choice sacrifices coupled horizon optimality but removes edge copies, dual variables, stopping tests, and safety messages.Source: §II · p. 1
  • The paper distinguishes its acceleration projection after horizon control from ORCA's velocity projection and from predictive safety filters using a backup horizon,,.Unlike a softened barrier row, its hard finite-hold row is not relaxed,.Source: §II · p. 2

III. PROBLEM FORMULATION

  • Robots apply constant commands over each sampling interval, with plant drift and bounded local snapshot errors included in the problem formulation.Received trajectories depend on communication radius and packet delivery, whereas sensed neighbors are selected by sensing radius and share synchronized symmetric snapshots.Source: §III · p. 2
  • Safety claims concern the stated plant and directional bounds; packet loss affects trajectory exchange but not the local snapshot used to build applied-input constraints.Koopman prediction accuracy and goal arrival are evaluated separately from safety.Source: §III · p. 2

IV. METHOD

The method separates a frozen Koopman predictor for nominal horizon planning from a locally rebuilt safety projection. The planner uses received trajectories, while local sensing and shelf geometry supply constraints on the applied input.

A. Koopman Identification

  • An offline EDMDc predictor is fit from transitions and kept fixed during evaluation, using observables that include state, quadratic terms, and trigonometric position features.Training covers the operating envelope, and no training rollout is reused in evaluation.Source: A. Koopman Identification · pp. 2–3

B. Local Predictive Planning

  • Each robot's local predictive QP uses available neighbor trajectories and a goal or waypoint reference to choose its nominal input.The optimization includes predictive slacks, planner input and speed bounds, and pair and shelf separation rows over the horizon.Source: B. Local Predictive Planning · p. 3
  • The first MPC input becomes the nominal command, but missing packets remove the corresponding predictive pair rows and leave sensed constraints to the separate safety projection.The planner defines nominal motion rather than imposing sensed constraints on the applied input.Source: B. Local Predictive Planning · p. 3

C. Finite-Hold Local Safety Projection

The local projection derives hard finite-hold constraints from sensed pair states and obstacle geometry. It separates safety rows from anticipatory targets that may be relaxed.

C. Finite-Hold Local Safety Projection

  • For a sensed pair, relative direction, velocity, and tightened clearance determine a radial demand that prevents the lower-bound clearance from becoming negative during the hold.The text gives a closed form for this demand, including separate cases for positive clearance and zero clearance.Source: C. Finite-Hold Local Safety Projection · p. 3
  • The hard row reacts to motion that could violate separation within the current hold, while the higher-order expression remains an anticipatory target.The QP's relaxation variables affect anticipatory targets only and do not enter the hard rows.Source: C. Finite-Hold Local Safety Projection · p. 3
  • Complementary pair weights allocate the coupled radial demand between the two robots, with equal robots recovering a half split.The input sets are known to both members of a sensed pair.Source: C. Finite-Hold Local Safety Projection · p. 3
  • For obstacles, the method uses a supporting plane at the estimated position to define the local shelf constraint.The excerpt identifies the supporting-plane point and normal but does not give further obstacle-row details.Source: C. Finite-Hold Local Safety Projection · p. 3

D. Online Decomposition and Feasibility Check

The method checks whether each robot's local hard-row set is simultaneously feasible before solving the projection QP. Its online margin exposes infeasibility without adding safety slack.

D. Online Decomposition and Feasibility Check

  • The max-min feasibility LP reports a fault when the local margin µ_i is negative, and the hard rows use no safety slack.For polygonal input sets, the LP is linear in the two input components and µ_i.Source: D. Online Decomposition and… · p. 4
  • With m_i local rows, the projection has at most 2 + m_i variables and 16 + 3m_i scalar inequalities, independent of MPC horizon and fleet size outside sensed degree.A negative margin is reported as infeasibility rather than softened in the hard rows.Source: D. Online Decomposition and… · p. 4
  • At each sample, robots receive available plans, build local snapshots and obstacle planes, solve the feasibility test, then solve the projection and hold its input.The algorithm requires µ_i(k) ≥ 0 before the projection QP.Source: D. Online Decomposition and… · p. 4

V. THEORETICAL RESULTS

The theoretical results characterize finite-hold acceleration demands, local feasibility, and conditions under which hard pair and obstacle constraints preserve separation continuously, including as the sensing graph switches. These guarantees are conditional on the stated plant and sensing bounds and on feasibility of each active hard-row set.

V. THEORETICAL RESULTS

  • The finite-hold demand is the least constant acceleration that keeps the supporting-plane clearance nonnegative at every time in the hold.It is obtained as the supremum of the required acceleration over positive times up to the hold endpoint, with four cases given for the demand.Source: §V · p. 4
  • Complementary local rows for a symmetrically sensed pair recover the coupled demand, and for an isolated pair their feasibility is determined by available combined input authority.The input sets are independent and the pair uses opposite normals; under the stated condition, the split makes both local rows feasible.Source: §V · pp. 4–5
  • The local hard rows are jointly feasible exactly when μ_i(k) ≥ 0, and when feasible the projection has a unique optimizer independent of trajectory packets.Packets change the nominal input in the objective, while constraints use local sensing, geometry, input sets, and plant bounds.Source: §V · p. 5
  • For compact polytope input sets, the dual weights identify a convex combination of limiting rows, and a negative dual value indicates conflict among pair, obstacle, and input constraints.This distinguishes a local constraint conflict from numerical QP failure.Source: §V · p. 5
  • Under bounded snapshot and directional plant errors, satisfying the pair and obstacle hard rows preserves the corresponding separation throughout the zero-order-hold interval.The result applies when tightened clearances are nonnegative and the finite-hold demand is finite.Source: §V · pp. 4–5
  • A switching sensing graph preserves continuous-time separation when active row sets are feasible and obstacles activate within the stated sensing-radius condition.Newly active rows enter the next induction step with positive tightened clearance; packet delivery does not affect the induction.Source: §V · pp. 5–6

A. Protocol

The protocol evaluates controllers in a fixed eight-robot warehouse benchmark with shared packet-loss streams for communication-dependent methods. It defines collision and goal-success measures and reports timing against a 120 ms control period.

A. Protocol

  • The benchmark places eight robots on opposing warehouse lanes where shortest routes cross between shelves, creating simultaneous pair and shelf conflicts.The Koopman model is trained from 220 rollouts and then frozen.Source: A. Protocol · p. 6
  • Communication-dependent controllers receive the same Bernoulli packet-loss stream within each setting, while trial seeds vary the stream but not warehouse geometry.ORCA and reactive QP are deterministic because they do not use messages.Source: A. Protocol · p. 6
  • A robot collision step means any pair falls below 0.45 m, while a successful robot run ends within 0.75 m of its goal.The available control period is 120 ms; sequential cycle time includes all eight planning calls, safety QPs, and Python orchestration.Source: A. Protocol · p. 6
  • The fleet-scaling figure uses five packet streams per fleet size and separates safety/feasibility counts, margins, and workload measures.Its workload panel compares a reconstructed per-agent critical path with the 120 ms period.Source: Figure 4 · p. 7

B. Prediction Ablation

The prediction ablation compares 25-step errors across four Koopman lifts. The full lift has the lowest reported error and improves on the linear lift by 44%.

B. Prediction Ablation

  • 0.265 ± 0.010 m is the 25-step error for the full lift, versus 0.471 ± 0.003 m for the linear lift.Across three model seeds and 100 test rollouts each, the trigonometric and quadratic lifts report 0.280 ± 0.010 and 0.381 ± 0.012 m, respectively.Source: B. Prediction Ablation · p. 7
  • The full lift’s 25-step error is lower than the linear, trigonometric, and quadratic lift errors reported across the three model seeds and 100 test rollouts each.Source: B. Prediction Ablation · p. 7
  • The full lift is 44% better than the linear lift and uses no shelf coordinates, so layout changes require no dynamics retraining within the sampled envelope.Source: B. Prediction Ablation · p. 7

C. Main Warehouse Result

In the fixed warehouse benchmark, the full controller combines collision-free trials with complete goal attainment, unlike predictive Koopman-MPC without the final projection. The stress-test table notes that negative μ_i removes the theorem’s premise.

C. Main Warehouse Result

  • 20/20 full-controller trials are safe and reach 160/160 robot goals, while predictive Koopman-MPC reaches 160/160 goals but is safe in only 1/20 trials.The full controller retains the predictive controller’s 0.0065 m error.Source: C. Main Warehouse Result · p. 7
  • 0.676 m and 0.321 m are the full controller’s worst pair and shelf distances, respectively.Source: C. Main Warehouse Result · p. 7
  • Table IV covers frozen-model stress tests, and negative μ_i removes the theorem’s premise.Source: Table IV · p. 8

D. Hard-Row Audit

The hard-row audit records proof-bound minima and reports successful local solves, positive feasibility and clearance bounds, and anticipatory relaxation outside safety rows.

E. Boundary and Scaling Studies

The conclusion reports a higher collision-free trial count with the full projection, while boundary tests expose sensing and fleet-authority limits and solver diagnostics report per-agent timing below the control period.

E. Boundary and Scaling Studies

  • At 3 cm snapshot error, 5/5 runs remain collision-free despite min µ_i = -0.979 m/s^2 and four hard-row faults.The rows reuse model seed 7, and (23) holds at every listed sensing-error level.Source: E. Boundary and Scaling Studies · p. 8
  • At N = 20, negative margin precedes nine collision samples, marking a fixed-footprint authority boundary rather than a fleet-size guarantee.The near-zero N = 16 audit is attributed to solver tolerance.Source: E. Boundary and Scaling Studies · p. 8
  • Authority allocation raises worst pair distance from 0.696 to 0.802 m and cuts maximum anticipation relaxation from 0.683 to 0.039 m/s^2.The differential-drive stress preserves longitudinal acceleration and clips lateral acceleration at ∥v_i∥ω_max; it uses v_max = 1.5 m/s and ω_max = 2.4 rad/s.Source: E. Boundary and Scaling Studies · p. 8

F. Solver Diagnostics

  • Per-agent reconstructed critical-path mean/p95/max is 18.1/25.5/46.9 ms, with a 73.0 ms scaling maximum below the 120 ms sampling period.The reconstruction includes full row-build time but excludes scheduling, communication I/O, and hardware worst-case timing; all 38,400 MPC and 38,400 safety-QP solves return.Source: F. Solver Diagnostics · p. 8

VII. CONCLUSION

  • At the same 0.0065 m goal error, full projection raises collision-free trials from 1/20 for predictive Koopman-MPC to 20/20.The conclusion conditions this result on explicit plant, sensing, and feasibility conditions.Source: §VII · p. 8

Related papers

Loading 2609.27463v1…