Technical Summary: Decentralized Contingency MPC based on Safe Sets for Nonlinear Multi-agent Collision Avoidance

Problem Statement

The paper addresses the challenge of decentralized collision avoidance for multi-agent systems with nonlinear dynamics. A critical constraint is the state-only information pattern, where agents observe the current states of their peers but cannot exchange planned trajectories, intentions, or control inputs. Existing approaches often rely on conservative coordination mechanisms, require communication rounds (which introduces latency), or fail to provide strong guarantees on recursive feasibility and convergence in safety-critical settings. The objective is to achieve collision-free motion while driving agents toward reference states or safe equilibria, ensuring that a feasible backup maneuver always exists without inter-agent communication.

Methodology

The proposed solution is a Decentralized Contingency Model Predictive Control (MPC) framework augmented by a novel Freeze-or-Shift (FoS) safe-set update mechanism.

1. Local Safe Sets

Each agent $i$ is associated with a time-varying local safe set $S^*_i(t)$, defined as a Euclidean ball $B(c_i(t), R_i(t))$. These sets are constructed to satisfy:

• Recoverability: From any state within the set, a feasible contingency maneuver exists that remains inside the set, satisfies all constraints, and reaches an admissible safe equilibrium in finite time.
• Disjointness: The active safe sets of all agents must remain pairwise disjoint to guarantee collision avoidance.
• Reconstructability: Agents can reconstruct the safe sets of neighbors using only current state observations and one-step memory of previous safe-set parameters, without communication.

2. Decentralized Contingency MPC Formulation

At each time step, every agent solves a local finite-horizon optimal control problem (FHOCP) that simultaneously computes:

• A nominal trajectory for performance and reference tracking.
• A contingency trajectory that serves as a safety certificate, ensuring a feasible backup maneuver exists within the local safe set.
• Coupling: The two trajectories are coupled by enforcing a shared first control input ($u_i(t) = u^{n,*}_{i,(0|t)} = u^{c,*}_{i,(0|t)}$). This ensures that the action taken for performance is also the first step of the safety plan.

Key Constraints:

• Tail-Containment: The entire contingency trajectory must remain within the current active safe set. Furthermore, the "tail" of the contingency plan (from any future step $k$) must remain within the safe set generated by the predicted state at step $k$. This ensures that if the agent shifts to the next state, the remaining plan is still valid.
• Lyapunov-type Convergence: A constraint enforces a monotone decrease in a contingency-related cost bound, derived from the shifted tail of the previous optimal solution. This drives the system toward a safe equilibrium.
• Collision Avoidance: No explicit inter-agent collision constraints are imposed on the nominal trajectory. Safety is guaranteed entirely by the feasibility of the contingency trajectory within the disjoint safe sets.

3. Freeze-or-Shift (FoS) Update Rule

To maintain the pairwise disjointness of safe sets in a decentralized manner, the paper introduces a deterministic update rule. At each step, an agent calculates a candidate safe set based on its new state.

• Freeze ($\chi=1$): If updating to the candidate set would cause an overlap with any neighbor's candidate set or current active set, the agent freezes its safe set (keeps the previous parameters).
• Shift ($\chi=0$): If no overlap is detected, the agent shifts to the new candidate set.
  This rule is fully decentralized; agents determine $\chi$ locally by reconstructing neighbors' potential sets from observed states.

4. Plug-and-Play (PnP) Operation

The framework supports agents joining or leaving the workspace online.

• Joining: A new agent reconstructs the "frozen" safe sets of existing agents using a conservative history-free over-approximation (a reconstruction ball based on position and known radius bounds) if the existing agents are frozen. It then selects an initial safe set that does not overlap with these representations.
• Leaving: An exiting agent is simply removed from the local constraint sets of remaining agents, preserving feasibility.

Key Contributions

The paper outlines five primary contributions:

1. C1: A fully decentralized FoS update rule for time-varying convex local safe regions that preserves the disjointness of active safe sets.
2. C2: A decentralized contingency MPC formulation for nonlinear multi-agent systems coupling a nominal performance plan with a backup safety certificate via a shared first input.
3. C3: A constructive proof of recursive feasibility and collision avoidance based on shifted contingency candidates and invariant disjoint safe sets.
4. C4: A Lyapunov-type convergence result obtained by enforcing a monotone decrease condition on a contingency-related cost bound.
5. C5: Simulation results demonstrating effectiveness in sparse, dense, cluttered bottleneck, and plug-and-play scenarios.

Results

Simulation studies were conducted using discrete-time double integrator agents in a 2D workspace.

• Scalability: The scheme successfully managed increasing agent densities (up to 20 agents) with collision-free trajectories.
• Bottleneck Scenarios: In narrow passages with static obstacles, agents successfully navigated through. The results showed that close encounters triggered temporary "freeze" events, preventing unsafe safe-set updates while maintaining closed-loop progress.
• Plug-and-Play: The system handled the online insertion and removal of agents without trajectory communication or structural changes to the local MPC problems of existing agents.
• Convergence: The normalized contingency cost decreased monotonically as enforced by the Lyapunov constraint, confirming the theoretical convergence properties.

Significance and Claims

The paper claims to bridge the gap between decentralized control and rigorous safety guarantees in nonlinear multi-agent systems without relying on communication.

• Safety without Communication: Unlike many distributed MPC approaches that require negotiation or trajectory exchange, this method guarantees safety using only state observations and a deterministic geometric update rule.
• Recursive Feasibility: The combination of the contingency MPC structure and the FoS update rule provides a tractable guarantee that the optimization problem remains feasible at every time step, preventing the system from entering a deadlock where no safe maneuver exists.
• Robustness to Topology Changes: The framework is explicitly designed to handle changing agent sets (PnP) and dynamic environments, maintaining safety guarantees even when the number of agents changes.
• Theoretical Rigor: The paper provides formal proofs for recursive feasibility, collision avoidance, and Lyapunov-type convergence to an admissible safe equilibrium, addressing limitations in existing literature regarding convergence guarantees in decentralized settings.

The authors note that the approach exhibits moderate conservatism even in dense environments and aligns with intuitive safety behaviors (maintaining a margin for emergency maneuvers). Future work is suggested to address disturbances, model mismatch, and sensing noise.