Taking Turns Without a Referee: Decentralized Alternating Updates for Multi-Robot Deadlocks

When many robots plan their paths at the same time and only talk to nearby robots, they tend to fail in a specific way. Two robots meet in a doorway. Each one reasons about the other symmetrically, so both yield or both push forward, round after round, and neither gets through. A central controller avoids this by planning everyone jointly, but that controller stops working at scale: joint planning for 1,024 simulated cars took centralized sequential quadratic programming over two hours, against about two minutes for a distributed method, in Distributed Differential Dynamic Programming Architectures for Large-Scale Multiagent Control. Decentralized methods remove the controller but bring back the doorway problem. The learned safety method in GCBF+ scales to more than 1,000 agents, yet its authors report that agents act "selfishly" and deadlock in narrow passages.

This proposal argues that the doorway deadlock comes largely from simultaneous updates. Consensus ADMM (the alternating direction method of multipliers, which splits a coupled problem into local pieces and reconciles them with price-like dual variables) and its relatives have every agent re-plan at once against the previous plans of its neighbors. Alternating optimization, also called block coordinate descent, does something different: it freezes some variables while others move. We propose to make agents take turns. In each round, only a set of mutually non-conflicting agents re-plans, treating its frozen neighbors as moving obstacles. The set is chosen by a local priority rule that uses only neighbor messages, and the rule rotates so that no agent is starved. Taking turns gives a quantity that provably never increases, makes it possible to start from colliding plans, and needs no central referee.

Core Claim

Write $\tau_i$ for agent $i$'s planned trajectory over a short horizon, $J_i(\tau_i)$ for its own cost (goal progress, control effort, dynamics limits), and $\phi_{ij}(\tau_i,\tau_j)\ge 0$ for a smooth pairwise penetration penalty. $\phi_{ij}$ is zero when the two plans keep a safe distance and grows with overlap; it is built from the dual signed-distance formulation in Optimization-Based Collision Avoidance. Every pair of agents within communication range carries a local weight $\mu_{ij}>0$. The team's shared potential is

$$\Phi(\tau_1,\dots,\tau_N)=\sum_i J_i(\tau_i)+\sum_{(i,j)}\mu_{ij}\,\phi_{ij}(\tau_i,\tau_j).$$

In round $t$, the agents select an independent set $S_t$ of the current conflict graph, meaning that no two members are within interaction range of each other. Each $i\in S_t$ solves

$$\tau_i \leftarrow \arg\min_{\tau_i}\; J_i(\tau_i)+\sum_{j}\mu_{ij}\,\phi_{ij}(\tau_i,\tau_j^{\text{frozen}}),$$

and everyone else holds still. Members of $S_t$ do not interact, so their parallel updates are exactly equivalent to some sequential block coordinate descent order. That makes $\Phi$ non-increasing at fixed weights. This is the standard monotonicity of exact block coordinate descent, and the inexact case is covered by Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization. Simultaneous updates have no such guarantee, and in symmetric conflicts they can cycle.

A doorway deadlock is then a well-defined object: a point where $\Phi$ stops decreasing but some $\phi_{ij}>0$, or where agents make no goal progress. Two purely local mechanisms are designed to escape it. First, a pair that keeps violating its constraint raises its own $\mu_{ij}$, an ADMM-style dual increase owned by the two endpoints, which reshapes the landscape. Second, the priority that decides who enters $S_t$ grows with an agent's accumulated waiting and with the size of its unresolved multipliers. The agent that has been blocked longest therefore eventually moves while its neighbors are frozen.

Because the penalty is soft and the frozen neighbors are fixed, each subproblem is a single-agent trajectory problem that accepts infeasible starting plans. This removes the strictly feasible initialization that Robust Multi-Robot Trajectory Optimization Using ADMM requires.

Relation to Prior Work

Four lines of work motivate or supply this proposal. Distributed Differential Dynamic Programming (ND-/MD-DDP) combines local trajectory optimization with consensus ADMM, agent-specific penalty adaptation and Nesterov acceleration, but all neighborhoods update synchronously and no convergence proof is given. We keep its local solver and its idea of per-agent penalty adaptation. We change the update schedule from simultaneous to turn-taking and gain a monotone potential. Sampling-Based Optimization for Multi-Agent MPC and Trajectory Splitting also rely on simultaneous consensus updates, and Trajectory Splitting keeps a central unit for its dual updates. Our weights and priorities live only on edges and nodes. Sheaf-ADMM unrolls ADMM over static graphs to learn coordination. It shows that structured alternating consensus beats free-form message passing (92.6% versus 10.7% solve rate on multi-agent Sudoku), but it assumes a fixed topology. Our conflict graph is recomputed every round from current plans.

The closest idea in spirit is Electing First-Move Agent (EFA-DWM), which breaks symmetry with a learned leader under leader-follower dynamics in cooperative games. Here the ordering is not learned. It comes from a transparent local rule tied to the optimization's own multipliers, and it carries a descent guarantee. Localized Predictive Control constrains our ambitions. Its exponential-decay competitive bounds hold only for convex costs on static graphs, so we claim monotone descent and empirical deadlock resolution, not competitive ratios. Classical prioritized planning, which plans agents one after another in a fixed global order, is the obvious ancestor. It is not in our sources. Our version differs in three ways: the order is local, it is re-chosen every round, it is driven by the multipliers, and intermediate plans may be infeasible. The fixed-order version appears below as an ablation.

Research Program

We will build the method on two local solvers so that the result does not hinge on one of them. The first is the differential dynamic programming solver used in D-DDP, for unicycle cars and quadrotors. The second is IPOPT on the signed-distance formulation of OBCA, for 2D polygonal robots.

Independent-set selection uses randomized local priority comparison. An agent enters $S_t$ if its priority, plus a small random tie-breaker, beats every neighbor's. This takes one message exchange per round and no global clock beyond a neighborhood round counter. The priority is a weighted sum of waiting time and the summed multipliers on the agent's violated edges. The weight updates are $\mu_{ij}\leftarrow \gamma\mu_{ij}$ whenever $\phi_{ij}$ stays above a tolerance for $m$ consecutive rounds in which either endpoint updated.

We will run the method in closed loop as receding-horizon control, with a fixed per-control-step budget of alternation rounds. The analysis has two parts. One is a proof of monotone $\Phi$ descent between weight increases, together with a bound on how many rounds an agent can wait under the waiting-time priority. The other is an empirical characterization of when the weight increases are actually needed.

Baselines

The naive reference point is uncoordinated planning with a safety filter. Each agent optimizes $J_i$ alone toward its goal, and a hand-crafted control barrier function filter blocks collisions at execution time. This shows how much of the corridor problem coordination solves at all. GCBF+ reports that learned barriers beat hand-crafted ones by up to 20% at up to 256 agents. No deadlock-specific number is reported, so we will measure one.

The strongest learned decentralized competitor is GCBF+. It reports over 98% success with 256 agents and 128 obstacles and scales to 1,024 agents. It is the competitor that most directly owns the deadlock failure we target. We will run the released training procedure on the same dynamics, sensing radius and obstacle densities, with its training compute matched to our tuning compute. Beating it means higher success at equal or lower collision rate on the corridor and doorway families, without losing more than two points of success on its own open-space scenarios.

The strongest optimization-based competitor is MD-DDP from Distributed Differential Dynamic Programming. It scales to 4,096 cars and solves 1,024 cars in about 2 minutes against over 2 hours for centralized sequential quadratic programming. We will reimplement it with the same local DDP solver, the same horizon and communication radius, and its recommended 10 penalty-adaptation steps with Nesterov acceleration. Beating it means fewer deadlocks and fewer total communication rounds at equal wall-clock time per control step.

Centralized sequential quadratic programming, or centralized IPOPT, serves as the optimality reference on small instances of 32 agents or fewer. We expect it to be good on cost and impractical at scale.

The ablation that isolates the key ingredient is our own method with the turn-taking removed. All agents update every round, using the same penalty, the same weight growth and the same solver. This is a "Jacobi" version of the same algorithm. If deadlock rates match, our central claim is false. Further ablations replace the multiplier-and-waiting priority with a fixed global priority (prioritized planning) and with pure random selection, and they turn the weight increases off.

All methods get the same scenario seeds, dynamics, sensing radius, per-step compute budget, and a tuning budget of 50 configurations each.

Why not just…?

Why not just add random noise to simultaneous updates to break symmetry? This is the most serious threat. Random perturbation breaks exact symmetry. However, in dense corridors with many agents, nothing guarantees it produces a consistent yielding order, and simultaneous updates still lack a decreasing potential. Our ablations include Jacobi-with-noise, tuned over the same 50-configuration budget. If it matches our method on deadlock rate across densities, we will report that the benefit is symmetry breaking alone and drop the turn-taking claim.

Why not just use fixed-priority planning, one agent after another? A fixed order is incomplete. A high-priority agent can permanently block the only route of a low-priority one, and a global order needs a global agreement step, which brings back a coordinator. The fixed-priority ablation is run on scenarios built to contain such blocking configurations, such as crossing corridors with goals behind other agents. Waiting-time rotation should resolve these where the fixed order fails.

Why not just train decentralized reinforcement learning or a learned leader election such as EFA-DWM? The evidence in our sources is against pure reinforcement learning for safe navigation. GCBF+ reports success rates 45% above InforMARL, and POGEMA finds pure multi-agent RL behind hybrid and search planners, with poor out-of-distribution behavior. EFA-DWM is a fair idea but is demonstrated on game rewards, not collision-constrained dynamics, and gives no descent or safety guarantee. We compare against GCBF+ as the stronger learned representative instead of reimplementing EFA-DWM.

Why not just make the central solver faster? The figures from D-DDP (over 2 hours versus about 2 minutes at 1,024 cars) and from the sampling-MPC paper (centralized sampling crashed above 48 vehicles while the distributed version ran to 196) say centralization does not survive at our target scales. We keep it only as a small-instance optimality reference.

Proposed Experiments

The first experiment is a diagnostic: two-agent doorway swaps and $N$-versus-$N$ corridor crossings with $N$ from 2 to 64. Corridor widths are 1.2 to 2 agent diameters, and plans start in collision. We measure deadlock rate, defined as no agent progress for 50 control steps, along with collision rate, makespan and rounds to resolution. We also plot $\Phi$ trajectories for our method against Jacobi. The prediction is a monotone $\Phi$ under turn-taking and oscillation under simultaneous updates.

The second experiment scales to the GCBF+ obstacle scenarios and to doorway-dense warehouse maps with 64 to 1,024 agents, using car and quadrotor dynamics. It reports success rate, collision rate, flowtime, messages per agent per control step, and per-agent compute.

The third experiment tests cold start. Following the robust-ADMM benchmark, where ADMM reached 100% against 53% for a penalty method only when started from feasible plans, we initialize from straight-line plans that collide and report success. If time allows, a hardware check on Crazyflie quadrotors repeats the eight-drone position swap from GCBF+ through a constructed narrow gate.

The experiments would settle the question as follows. If turn-taking cuts corridor deadlocks substantially below both GCBF+ and MD-DDP at matched compute, while noisy Jacobi and fixed priority do not, the claim stands. If noisy Jacobi matches, the contribution narrows to the infeasible-start and descent properties. No reported result was found on Lacuna for deadlock rate in narrow-corridor scenarios for any baseline, so all corridor numbers will be measured here.