Compensation Load as a Leading Indicator of Multi-Agent Deadlock

Teams of robots and warehouse vehicles get stuck. Two robots meet head-on in a corridor, or a cluster of vehicles blocks one another at an intersection, and no one can move forward even though nothing is broken. Today's systems notice this late. They raise an alarm only when robots have already stopped, when an agent has made no progress for many steps, or when a planner runs out of time. Medicine has a well-studied version of the same problem. Serum creatinine stays normal for 48 to 72 hours after kidney injury begins (post-cardiac surgery AKI). The standard FEV1/FVC ratio misses lung disease that the shape of the flow-volume curve already shows (Deep learning for detecting and early predicting chronic obstructive pulmonary disease from spirogram time series). In both cases the output measure looks normal because the body is compensating. The signal that leads is the cost of that compensation, not the output it protects.

We propose to carry this lesson into multi-agent navigation. Velocity and progress are output measures. The safety and coordination layer that sits between each agent's goal-seeking intent and its actual motion is the compensating mechanism. Concretely, that layer is a collision-avoidance filter in continuous control, or priority passing and collision shielding in grid planning. Our claim is that this layer's compensation load rises well before motion stops. Compensation load means how strongly, how persistently, and how directly the layer must oppose what each agent wants to do. Because it rises early, it can serve as an early-warning score, and triggering existing resolution methods on that score should recover throughput that late detection loses.

Core Claim

For robots controlled by Control Barrier Function quadratic programs (CBF-QPs), a deadlock has an exact characterization. A CBF-QP is a safety filter that minimally edits a desired control so the robot never leaves a safe set. The Before, During, and After of Multi-Robot Deadlock and Deadlock Analysis and Resolution for Multi-robot Systems prove that a deadlock is a force balance. The filter's correction exactly cancels the nominal goal-seeking command, and this happens on the boundary of the safe set. Both papers then detect deadlock only after the speed has fallen below a threshold, $\|v\|\le\epsilon$. Their characterization implies a natural continuous quantity that they never monitor. Let $\hat u_i$ be agent $i$'s nominal command and $u_i^\star$ the filtered command. We define the opposition index

$$\rho_i(t) = -\frac{\langle \hat u_i,\; u_i^\star - \hat u_i\rangle}{\|\hat u_i\|^2},$$

which is $0$ when the filter does nothing, and approaches $1$ exactly when the correction cancels the nominal command, which is the KKT equilibrium those papers describe. Speed can stay high while $\rho_i$ climbs, because the filter first bends the trajectory sideways and only cancels the command at the end. The indicator we propose is therefore not $\rho_i$ at a single instant. It is a persistence-weighted group score: $\rho$ integrated over a sliding window and aggregated over each connected cluster of mutually constrained agents. The window and the aggregation address the false-alarm problem that upstream clinical biomarkers face. Benign, self-resolving yielding produces brief spikes, while a developing trap produces sustained, cluster-wide opposition.

On discrete grids the same idea becomes a deflection measure. The deflection rate counts how often an agent's executed move differs from its preferred greedy move. We pair it with two signals the planner already produces: the depth of priority-inheritance chains and the backtrack counts in Priority Inheritance with Backtracking (PIBT), or the number of collision-shield interventions in POGEMA. We pair this load with net progress toward goals over the same window. A livelock, where agents oscillate between adjacent cells at full speed, shows high load with near-zero net progress. That is exactly the failure that velocity thresholds cannot see.

What is new is not "predict deadlock with a classifier." It is the specific hypothesis that signals internal to the controller lead kinematic signals by a measurable margin. The program also measures that margin under clinical-style constraints on false alarms, and shows that acting on it changes outcomes.

Research Program

The work has three parts.

The first is analytical, in the setting of Grover, Liu, and Sycara. For two and three robots, where their deadlock sets are fully characterized, we will show that along trajectories converging to deadlock, $\rho$ crosses any fixed level $\rho_0<1$ a bounded time before $\|v\|$ crosses $\epsilon$. We will also characterize how that lead time depends on controller gain and on how symmetric the approach is. This links the indicator to the open "basin of attraction" problem: the sublevel sets of the integrated score give an inexpensive, empirical inner approximation of the basin, which can be checked against brute-force rollouts for small $N$.

The second part is empirical generalization. Grover et al. note that analytical resolution becomes intractable at $N\ge4$ because the number of deadlock configurations grows as $0.5(N+1)(N-1)!$. Above that size we will rely on measurement rather than enumeration. We will also port the indicator to the discrete planners PIBT (Priority inheritance with backtracking for iterative multi-agent path finding), RHCR, LaCAM, and learned policies in POGEMA, using the deflection and inheritance signals described above.

The third part closes the loop. We will trigger existing resolution actions at the indicator's alarm rather than at stall, and measure whether the earlier trigger helps. The actions are Grover's symmetry-breaking rotation in continuous control, and on grids a temporary local priority reshuffle or a transient one-way constraint on the affected corridor. The transient constraint is a dynamic, local counterpart to the static one-way streets of Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding (MGGO). MGGO computes edge directions offline and imposes them everywhere, at all times.

From the clinical work we take evaluation methods rather than mechanisms. Deep Learning-Based Approach to Emergency Department Chest Pain Risk Stratification by ECG judged its waveform score by two tests: what it added on top of the established marker (clinical model AUC 0.75 rising to 0.80 with the ECG score), and whether a "rule-out" threshold existed below which no adverse events occurred (ECG-Risk below −1.25, with zero 30-day deaths). We adopt both tests. The indicator must add predictive value beyond velocity and progress, not merely correlate with them. It must also have a threshold below which deadlocks essentially never follow within the horizon, so that operators can safely ignore low scores.

Baselines

The naive reference point is the detector the deadlock literature already uses. For continuous control this is the speed threshold $\|v\|\le\epsilon$ from The Before, During, and After of Multi-Robot Deadlock. For grids it is a no-progress timeout. Both are run with resolution triggered at detection. We will sweep $\epsilon$ and the timeout length, and report the whole curve rather than a single setting. No reported result was found on Lacuna for the lead time or false-alarm rate of velocity-threshold deadlock detection, so we will measure this baseline ourselves.

The strongest simple competitor is a tuned kinematic early-warning detector. It combines windowed net progress toward goal, speed variance, and pairwise minimum distance, so it can catch slowing, oscillation, and crowding. It gets the same window lengths, the same threshold-tuning budget on held-out seeds, and the same alarm-rate constraint as our score. Beating it means a longer median lead time at a matched false-alarm rate of alarms per agent-hour. It also means a statistically significant AUROC gain when controller-internal features are added to a logistic model already containing the kinematic ones. This is the analogue of the ECG score adding to the clinical model.

The strongest learned competitor is a temporal classifier, either a small transformer or a GRU, trained on trajectory windows to predict deadlock within $H$ steps. It is trained on the same rollouts with the same compute.

The ablation that isolates our key ingredient is to train that same classifier twice. One copy sees only kinematic inputs. The other also sees controller-internal signals: $\rho$, deflection, inheritance depth, and shield interventions. If the internal signals carry no extra lead time, the core claim fails, whether or not our hand-built score is useful.

On the planning side, the strongest prevention method is HMAGAT from Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding. That paper reports a success rate above 75% in Dense Warehouse, where other baselines including the 85M-parameter MAPF-GPT fall below 11%, and a residual 2.7% failure rate in Dense Rooms, mostly livelocks. If HMAGAT checkpoints are unavailable we will substitute the top POGEMA learned baseline, MAMBA. For lifelong traffic the comparison points are static MGGO and RHCR. In closed-loop tests we compare a planner alone, the planner plus resolution at stall, and the planner plus resolution at our alarm. Beating these means higher success or throughput at equal or lower total makespan.

Why not just…?

Why not just raise the speed threshold or use a no-progress window? Grover et al. show that robots on a symmetric approach move at full speed until the force balance forms, so speed carries little early information. A looser threshold fires on every routine slowdown for a turn or a yield. Livelocks in Jain et al.'s Dense Rooms failures happen at nonzero speed. A windowed progress measure is a genuine threat, though, especially for livelocks. That is why it is our strongest simple baseline rather than a straw man. If it matches our score on lead time at a fixed alarm rate, we will report that, and the contribution shrinks to the continuous-control setting, where $\rho$ has its theoretical grounding.

Why not just train a black-box predictor on trajectories? This could work, and we test it directly. The input ablation asks whether such a predictor needs the controller's internal signals. If a kinematics-only model already reaches the same lead time, the hypothesis that compensation load leads motion is false. In that case the proposal reduces to a recommendation to use learned detectors, and we would say so.

Why not just prevent deadlocks with better planners or one-way streets? MGGO's static directions require Edge Reversal Search just to keep the map strongly connected. They impose detours even when traffic is light, and they cannot be applied in single-passage corridors. The best learned planner still leaves residual livelocks. Our detector sits on top of these planners rather than replacing them. The closed-loop experiment measures whether it adds anything to HMAGAT, MGGO, or PIBT. If those planners show near-zero residual failures on our test distributions, there is little left to rescue, and that is a legitimate negative result.

Proposed Experiments and Decisive Checks

In continuous control we will simulate CBF-QP teams of 2 to 16 robots in corridors, doorways, and crossings, matching the Khepera-IV setup of Grover et al. Initial conditions will be sampled with controlled symmetry and noise. A deadlock is labeled when Grover's force-balance condition is met. For $N\le3$ we will compare the indicator's alarm times against the analytical result. For larger teams we will measure lead time, AUROC within a horizon of $H$ steps, and the rule-out threshold.

On grids we will use POGEMA's generated maze, room, and warehouse grids and MovingAI warehouse maps, with PIBT, LaCAM, RHCR, and learned policies. Episodes are labeled by timeout and by detected oscillation cycles. Lifelong warehouse runs on MovingAI maps with hundreds of agents will report throughput, and will compare dynamic, alarm-triggered local one-way constraints against static MGGO-style directions.

Three results would decide the question. First, the controller-internal ablation must show a positive lead-time gain at matched false-alarm rates on both continuous and discrete tasks, or the claim is refuted. Second, the integrated score must add predictive value over the tuned kinematic detector, measured as incremental AUROC with confidence intervals across seeds. Third, alarm-triggered resolution must improve success or throughput over resolution at stall without inflating makespan. A useful falsifier is to break robot symmetry with noise: Grover et al.'s analysis predicts fewer deadlocks, and the indicator's alarm rate should fall accordingly rather than staying constant.