Source-linked AI summary
Provably Safe Decentralized Contingency MPC under State-Only Information and Limited Sensing for Nonlinear Multi-agent Systems
Max Studt, Georg Schildbach
TL;DR
Communication-free decentralized collision avoidance is difficult when agents have only local current-state measurements and finite sensing. The paper introduces state-dependent safe-set updates within contingency MPC, preserving recursive feasibility, collision avoidance, and Lyapunov-type convergence. A nonlinear four-way intersection study demonstrates operation with unknown maneuvers, finite sensing, and plug-and-play traffic.
Problem
Communication-free decentralized collision avoidance must operate from local current-state measurements without future neighbor trajectories, inputs, or intentions.
Method
The paper uses a memory-free, state-dependent safe-set interaction mechanism within decentralized contingency MPC, with nominal and contingency plans sharing the first input.
Results
The scheme preserves recursive feasibility, collision avoidance, and Lyapunov-type convergence, while 50 vehicles complete a plug-and-play intersection experiment without collisions.
Takeaways & Limitations
The framework supports decentralized nonlinear multi-agent operation with finite sensing, unknown maneuver intentions, and continuous plug-and-play traffic.
Abstract
from arXiv · showhide
This paper considers decentralized contingency MPC for multi-agent control under a state-only information pattern, with particular focus on limited sensing and plug-and-play operation. The objective is to retain recursive feasibility, safety, and Lyapunov-type convergence while reducing conservatism in local interaction handling. The framework relies on agent-wise fallback regions (safe sets) in which a feasible contingency maneuver to a safe equilibrium is always available. A novel safe-set update mechanism is introduced that supports less conservative decentralized interaction while preserving the underlying guarantees. This, in turn, enables memory-free local interaction and finite sensing ranges without requiring agents to reconstruct the exact neighbor geometry. The resulting scheme remains fully decentralized and preserves the shared-first-input contingency MPC structure. Theoretical guarantees and simulation results illustrate the effectiveness of the approach in dense multi-agent scenarios.
I. INTRODUCTION
The paper addresses communication-free decentralized collision avoidance with finite sensing and introduces a memory-free contingency-MPC interaction mechanism that preserves safety and convergence guarantees.
- Motivation: State-only decentralized collision avoidance requires agents to plan from local neighbor states without future trajectories, inputs, or intentions.The information pattern is relevant when communication is unreliable, unavailable, or undesirable, especially with finite-range sensing.
- Motivation: Reactive methods handle limited information but generally lack predictive multi-step constraints, recursive-feasibility guarantees, and closed-loop convergence guarantees.Decentralized predictive schemes often instead require communication, trajectory exchange, or coordination.
- Contributions: The paper removes history-dependent neighbor reconstruction through a memory-free, state-dependent interaction mechanism for decentralized contingency MPC.The active safe set remains contained in a region computable from the agent’s current state.
- Contributions: The safe-set construction provides a memory-free outer representation recoverable from current state information.This supports finite sensing and plug-and-play operation without requiring neighbor trajectories or update histories.
- Guarantees and Evaluation: The framework retains recursive feasibility, collision avoidance, and Lyapunov-type convergence guarantees during nonlinear multi-agent operation.The contributions include a four-way intersection study with nonlinear vehicle dynamics and continuous plug-and-play operations.
B. Standing Assumptions
The framework assumes exact translation-invariant agent dynamics and finite sensing, then uses state-generated and interaction-restricted safe sets to certify feasible collision-free fallback behavior.
- Agent model: Each agent’s closed-loop evolution is assumed to follow its discrete-time model exactly, without model mismatch or external disturbances.
- Agent model: Translation invariance is imposed through an embedding that shifts position while preserving the relevant dynamics.The embedding satisfies the position-shift relation specified by the assumption.
- Information pattern: Under finite sensing, an agent measures its own state and current states of sensed neighbors, but not their references, future inputs, or predicted trajectories.
- Safe sets: A safe set is a position-space region containing a feasible contingency maneuver to an admissible safe equilibrium while remaining inside the region.
- Safe sets: The generated safe set Gi(t) is computed from the agent’s current state using a deterministic generator and must support a feasible safe fallback.
- Safe-set interaction: The active safe set Si(t) may be further restricted to maintain safe interaction with neighbors, while remaining contained in a state-computable outer set.Neighbors can therefore use Gi(t) without knowing the exact active safe set or its update history.
- Safe-set interaction: Commonly known safe-set generators allow an agent to reconstruct a sensed neighbor’s generated safe set from that neighbor’s current state.
- Collision avoidance: Disjoint active safe sets suffice to certify collision avoidance when both agents keep their bodies inside their respective sets.The local update mechanism is designed to preserve pairwise disjointness.
III. DECENTRALIZED CONTINGENCY MPC FORMULATION
The decentralized MPC optimizes nominal and contingency plans together, constrains the contingency plan within an active safe set, and applies their shared first input.
- A. Nominal and Contingency Plans: The formulation uses separate nominal and contingency prediction horizons, with the contingency horizon long enough to represent a feasible fallback maneuver.The nominal horizon is selected according to desired performance behavior.
- A. Nominal and Contingency Plans: At each time, the agent optimizes a nominal state-input sequence for performance.
- A. Nominal and Contingency Plans: The agent simultaneously optimizes a contingency state-input sequence and its predicted positions.
- A. Nominal and Contingency Plans: Both prediction plans start from the measured state at the current time.
- A. Nominal and Contingency Plans: The nominal trajectory serves the control objective, while the contingency trajectory remains inside the active safe set and terminates at an admissible safe equilibrium.
- A. Nominal and Contingency Plans: The nominal and contingency plans share their first input, which is applied to the real system after optimization.This coupling makes the applied action nominally optimal while remaining contingency-feasible.
B. Objective Function
The objective combines nominal reference-seeking performance with a preference for safe terminal equilibria, while tail-containment constraints support recursive feasibility.
- B. Objective Function: The local objective combines a nominal performance term with a contingency-offset term favoring safe terminal equilibria near the reference.
- B. Objective Function: A sufficiently large γ makes the selected contingency terminal state optimal with respect to the global reference.
- C. Safety and Tail-Containment Constraints: The contingency trajectory must remain inside the active safe set, including the agent’s physical radius, to certify current-time safety.
- C. Safety and Tail-Containment Constraints: Recursive feasibility additionally requires each remaining contingency tail to fit inside a safe set generated from its predicted contingency state.
- C. Safety and Tail-Containment Constraints: The tail-containment condition ensures that the shifted contingency tail remains inside the successor-state-generated safe set after the first input is applied.It is the key compatibility condition in the recursive-feasibility argument.
D. Lyapunov-Type Constraint
The framework enforces a decreasing contingency-cost bound and updates active safe sets using current-state information, stored separators, and bootstrap restrictions. These constructions preserve tail compatibility and yield monotone contingency-cost decrease.
- D. Lyapunov-Type Constraint: A recursively maintained contingency-cost bound imposes Lyapunov-type progress on the fallback plan.The contingency stage cost is nonnegative, and the bound is updated after the shared first input using the shifted contingency tail.
- D. Lyapunov-Type Constraint: Once recursive feasibility is established, the shifted-tail argument gives monotone decrease of the optimal contingency cost.The cost-bound update is independent of the particular safe-set construction.
- D. Lyapunov-Type Constraint: Agent i constructs its generated safe set and reconstructs sensed neighbors’ generated safe sets from their current measured states.Pairwise separators are locally constructed whenever generated safe sets are disjoint.
- D. Lyapunov-Type Constraint: Stored separators are updated when generated safe sets are disjoint and retained otherwise, while bootstrap restrictions handle newly sensed overlaps.Bootstrap restrictions remain active until the generated safe sets become disjoint and regular separators can be initialized.
- D. Lyapunov-Type Constraint: The active safe set remains contained in the generated safe set, which is computable from current sensed neighbor states and local stored restrictions.No neighbor trajectories or neighbor safe-set update histories are required.
A. Assumptions
Under initial feasibility, initial separation, and sensing-completeness assumptions, the shifted contingency candidate supports safe-set containment, recursive feasibility, collision avoidance, and plug-and-play operation.
- A. Assumptions: Initial feasibility and pairwise separation are assumed at t = 0, together with detection of every pair whose generated safe sets overlap.These are the stated initial-feasibility, separation, and sensing-completeness conditions.
- A. Assumptions: Recursive feasibility follows by induction because a feasible contingency candidate admits a nominal completion with the same first input.The theorem states feasibility at time t implies feasibility at t+ for all t ∈Z+.
- A. Assumptions: Active safe sets remain contained in generated safe sets and pairwise disjoint under regular separators or bootstrap restrictions.The containment and separation result is stated in Lemma 1.
- A. Assumptions: The shifted contingency tail preserves dynamics, constraints, terminal conditions, safe-set containment, and the Lyapunov-bound constraint at the successor state.The terminal equilibrium is unchanged, and the appended equilibrium stage contributes zero stage cost.
- A. Assumptions: The resulting closed-loop execution is collision-free, and feasible joining agents preserve recursive feasibility and collision avoidance when sensing assumptions remain satisfied.The plug-and-play corollary requires an initially disjoint active safe set for the joining agent.
C. Lyapunov-Type Convergence
The Lyapunov-type convergence argument uses the standard shifted-tail Lyapunov reasoning and is not reproved in this paper.
- C. Lyapunov-Type Convergence: The paper applies the standard shifted-tail Lyapunov argument unchanged, with the corresponding proof given in prior work.The convergence proof is cited rather than repeated here.
VI. SIMULATION STUDY
The framework is evaluated in a nonlinear autonomous-driving intersection with changing agents, unknown maneuvers, finite sensing, and contingency-safe-set constraints. Simulations illustrate that contingency predictions stay admissible while nominal predictions retain route-following flexibility.
- VI. SIMULATION STUDY: The study models multiple vehicles traversing a four-way intersection with nonholonomic dynamics, lane constraints, varied maneuvers, and changing active agents.Vehicles enter from four directions and may proceed straight, turn left, or turn right.
- VI. SIMULATION STUDY: Vehicles use a kinematic bicycle model with fourth-order Runge–Kutta discretization at Ts = 0.2 s.The state includes Cartesian position, heading, longitudinal velocity, acceleration, and steering angle.
- VI. SIMULATION STUDY: The contingency prediction has hard lane-keeping constraints, while the nominal trajectory uses softened lane constraints for performance flexibility.Each vehicle is represented by a Euclidean disc with radius ragent = 0.4 m.
- VI. SIMULATION STUDY: Figure 1 shows nominal and contingency predictions alongside locally active safe sets for vehicles with mutually unknown driving maneuvers.Contingency predictions remain within admissible regions while nominal predictions retain flexibility to follow assigned routes.
- VI. SIMULATION STUDY: The simulation spawns vehicles every 2 s when entrance clearance permits and continues until 50 vehicles traverse the intersection.Maneuver probabilities are 0.5 for straight, 0.25 for left, and 0.25 for right.
- VI. SIMULATION STUDY: The generated safe set contains a complete stopping maneuver after the shared first input, with a maximum generated radius of Rmax = 3.25 m and finite sensing.The active safe sets use the update rule from Section IV.
B. Results
The intersection simulation handles nonlinear vehicle interactions, changing traffic, and unknown maneuvers while maintaining collision-free, lane-following operation and Lyapunov-type behavior. All 50 vehicles reach their assigned exits under state-based local coordination.
- All 50 vehicles successfully traverse the intersection and reach their assigned exits while remaining collision-free.The simulation includes repeated arrivals and departures alongside simultaneous straight, left-turn, and right-turn maneuvers.
- Vehicles locally coordinate motion through the state-based safe-set construction while remaining close to their prescribed lanes.
- The experiment remains collision-free despite plug-and-play vehicle operation and the absence of communicated maneuver intentions.
- The contingency costs exhibit the Lyapunov-type behavior enforced by the contingency MPC formulation.
- The scheme handles nonlinear vehicle dynamics, mutually unknown driving maneuvers, and dynamically changing intersection traffic under a purely state-based information pattern.
VII. CONCLUSION AND DISCUSSION
The paper presents provable decentralized MPC for finite sensing and state-only information, preserving safety and convergence while avoiding history-dependent neighbor reconstruction. Its guarantees assume exact agent models and complete detection of potentially interacting agents, while robustness, experimental validation, and larger-scale implementations remain future work.
- The framework uses a state-dependent outer representation of active safe sets to avoid history-dependent neighbor reconstruction while preserving recursive feasibility, collision avoidance, and Lyapunov-type convergence.
- The intersection study demonstrates applicability to nonlinear vehicle dynamics, unknown maneuver intentions, and plug-and-play multi-agent operation.
- The present guarantees rely on exact agent models and complete detection of potentially interacting agents.
- Future work targets robustness to model uncertainty and disturbances, experimental validation, and larger-scale real-time implementations.