Learning to Reconfigure the Safety Filter: Hybrid Actions for Breaking Multi-Robot Deadlock

Robots that share space usually run a safety filter, a small optimization solved at every control step that takes whatever command the robot's planner or learned policy proposes and changes it as little as possible so that no collision can occur. These filters are reliable, and they have a known flaw. When several robots meet in a doorway or corridor, each filter pushes its robot away from the others while the task pulls it forward. The pushes and pulls cancel, and everyone stops. This standstill is created by the filter itself. It is not a failure of the learned policy, and the usual fixes are hand-built rules that switch to a planner, a scripted swap maneuver, or a language model once a stall timer expires.

We propose to learn deadlock resolution by acting on the filter rather than on the motors. At rare moments chosen by the filter's own internal state, a learned policy picks a discrete coordination mode, such as yield to a specific neighbor, pass on the left, or back into a bypass, together with a few continuous parameters for that mode. The chosen mode is carried out by re-parameterizing the safety filter. Every mode is built so that it can only tighten the agent's own safety constraints or redirect its nominal goal. It can never loosen a constraint. As a result, no choice the policy makes during training or deployment can cause a collision. The learned policy makes very few decisions per episode, sees only a small action space, and never needs to experience a crash. For these reasons we expect it to learn from far fewer environment steps than flat safe multi-agent reinforcement learning.

Core Claim

The Lagrange multipliers of the multi-agent safety filter give a compact signal for detecting deadlock. They are the "forces" each active collision constraint exerts, and each one comes attached to the specific neighbor that constraint involves. The learned policy observes these multipliers and acts through a hybrid (discrete mode plus continuous parameter) space of filter configurations. Our claim is that this combination produces three things together: safety at every time step, not just on average, whatever the policy does; deadlock resolution that scales beyond the three-robot limit of analytic methods; and sample complexity measured in tens of thousands of high-level decisions rather than millions of low-level steps.

The motivating evidence comes from Grover et al.. They use the optimality conditions of the barrier-function quadratic program to prove that multi-robot deadlock is a force equilibrium on the boundary of the safe set, where task attraction and barrier repulsion cancel. Their resolution is a hand-designed swap maneuver, demonstrated only for up to three robots, and they state that four or more remains open. We reuse their characterization as a sensor, and we replace the hand-designed resolution with a learned hybrid choice.

Research Program

Filter and control-barrier background. A control barrier function is a scalar $h_{ij}(x)$ that is nonnegative exactly when agents $i$ and $j$ are safely separated. The survey by Ames et al. shows that keeping $\dot h \ge -\alpha(h)$ holds the pair inside the safe set. In the decentralized setting, agent $i$ solves

$$u_i^\star=\arg\min_{u}\ \|u-u^{\text{nom}}_i(d,\theta)\|^2 \quad \text{s.t.}\quad \nabla h_{ij}\cdot \dot x_i(u) \ \ge\ -\rho_{ij}(d,\theta)\,\alpha(h_{ij})\ \ \forall j\in\mathcal N_i,$$

Here $u^{\text{nom}}_i$ is the nominal command, $d$ is the discrete mode, and $\theta$ its continuous parameters. $\mathcal N_i$ is the set of neighbors, and $\rho_{ij}\in(0,\tfrac12]$ is the fraction of the pairwise safety margin that agent $i$ takes responsibility for. The default is $\rho_{ij}=\tfrac12$, the symmetric split. Lowering $\rho_{ij}$ makes agent $i$ more conservative toward $j$.

The central design rule is that modes may only lower $\rho_{ij}$ or change $u^{\text{nom}}_i$. For example, the yield-to-$j$ mode lowers $\rho_{ij}$ by an amount set by $\theta$. Pass-left adds a tangential component to the nominal command with a magnitude set by $\theta$. Retreat replaces the goal with a nearby bypass waypoint whose location is set by $\theta$. Each agent therefore still meets at least its half of every pairwise constraint, so pairwise forward invariance holds regardless of what neighbors choose. The only exception is when the filter is infeasible. In that case we fall back to a braking controller and report the frequency of these events.

This design separates us from HMARL-CBF. That work picks a discrete skill and then runs an unchanged filter underneath it, so the skill layer cannot see whether the filter will freeze. In our design the mode is itself a filter configuration.

Triggering from the filter's own state. Following Grover et al.'s equilibrium characterization, agent $i$ is flagged as approaching deadlock when two conditions hold: the filtered command is small relative to the nominal one ($\|u_i^\star\|/\|u_i^{\text{nom}}\|<\tau$), and at least one constraint is active with a large multiplier. Only then is the high-level policy queried. Its observation is the local graph of active constraints, with multipliers as edge features, plus positions, goals, and nearby free space. This replaces the stall timers and bounding-box thresholds that Wang et al. tune by hand. It also fires while robots are still decelerating into equilibrium, before they stop. We treat the threshold $\tau$ as a hyperparameter and sweep it.

Hybrid policy and feasibility masking. The policy uses a graph neural network backbone, in the style of the neighbor encoding in GCBF+, which lets us train on 8 agents and test on more. It has a categorical head over modes and a conditioned continuous head over $\theta$. This is the conditioned structure that Fu et al. found much cheaper than computing parameters for every mode at once. Before sampling, each candidate mode's filter is solved once at the current state, and modes whose filter is infeasible are masked out. This directly addresses the open problem, noted in the file's analysis of HMARL-CBF, that high-level choices are blind to low-level feasibility. Training is centralized-critic PPO over high-level decisions. The reward is progress toward the goal plus a flow-rate term. There is no collision penalty, because collisions cannot occur outside the fallback case.

Why sample efficiency should improve. Three effects reduce the samples needed. The effective horizon shrinks to the handful of triggered decisions per episode. The action space is a few modes times a low-dimensional $\theta$, instead of joint continuous control. And no samples are spent discovering constraint boundaries through failures, which is where CHPO spends its budget: it keeps safety only in expectation ($J_C\le d$) and only in single-agent tasks. We do not assume these effects combine cleanly, so we measure each with an ablation.

Baselines

The naive reference is the plain decentralized filter with symmetric responsibility and a straight-to-goal nominal command. This is the configuration Grover et al. prove will deadlock, and it tells us how often deadlock actually occurs in each scene.

The strongest hand-designed competitor is the liveness-set method of Chandra et al.. It adds a discrete-time barrier layer inside model predictive control, applies a minimal speed perturbation when a liveness measure drops, and runs an auction to break exact symmetry. It reports a 100% success rate with zero deadlocks in its social mini-game simulations, a physical doorway flow rate of 2.0 (m·s)$^{-1}$, and path deviations under 0.09 m. We will re-implement it on our scenes with the same dynamics model and barrier function. We extend its liveness sets to T-junctions and multi-agent corridors only as far as the published derivation allows, and we report where that extension breaks. On the canonical two-agent doorway, beating it means matching 100% success while achieving flow above 2.0 (m·s)$^{-1}$ at equal or smaller deviation. On scenes with four or more agents, beating it means higher success at matched safety.

The strongest learned-plus-planner competitor is the hybrid RL/path-finding system of Wang et al. It runs PPO with velocity obstacles by default and hands off to Push-and-Rotate grid planning in a subregion when a stall monitor fires. It reports 100% success in 6–8 agent corridors and 4-agent doorways, where its pure-RL baseline scored 0% and 15.63% respectively. To isolate the resolution strategy, we will run it with our barrier filter in place of velocity obstacles and give it the same threshold-tuning budget we give $\tau$. Because its success saturates on those scenes, beating it means equal success with shorter clearing time, fewer control discontinuities, and no hand-tuned bounding box, plus higher success on continuous maps where the grid abstraction fits poorly.

The strongest learned hierarchical competitor is HMARL-CBF. It reports at least 95% success on MetaDrive with up to 45 agents and converges in about 300k iterations versus up to 1M for Lagrangian baselines. We run it with its yield skill and an added deadlock-time penalty in its reward, under the same simulator step budget as ours. Beating it means higher success on bottleneck and tollgate maps and reaching its final success rate in fewer environment steps.

GCBF+ is included as the scalable continuous-only reference. It reports 95% success with 128 obstacles and over 98% success when an 8-agent-trained model is deployed on 1024 agents, but its authors note that it deadlocks in tight bottlenecks.

Four ablations isolate the proposal's ingredients. The first removes multiplier features and feeds raw observations. The second removes feasibility masking. The third queries the high-level policy at every step instead of on trigger. The fourth allows modes to raise $\rho$ above $\tfrac12$, which loosens constraints; we expect this variant to learn faster but record collisions, which shows why the tighten-only rule matters. For Garg et al., who use foundation-model deadlock resolution with a graph-barrier controller in Room and Maze environments, the file contains no reported numeric result. We will run it only as a latency and success reference on the Maze layout.

Why not just…?

Why not just add a fixed tie-breaking rule, such as always keep right or use a tangential bias, to the filter? This is the most serious threat. On symmetric two-agent doorways, a fixed rotational bias may well match us, and Chandra et al.'s small perturbation already achieves zero deadlocks there. Our prediction is that fixed rules fail once resolving the deadlock requires ordering among four or more agents or retreating into a bypass. Those are the regimes where Leroy et al. show that adjusting speed profiles cannot fix topologically incompatible paths. We include keep-right and fixed-ID-priority filters as baselines. If they match us on corridors with bypasses and on T-junctions at 8 or more agents, the learning component is not justified and we will say so.

Why not just train constrained multi-agent PPO with a deadlock penalty? HMARL-CBF reports that Lagrangian baselines (MAPPO-Lagrangian, MACPO, CoPo) reached only 10–70% success on MetaDrive and needed up to 1M iterations. These methods also bound collisions only in expectation, so they collide during training. We include MAPPO-Lagrangian under the same step budget and count training-time collisions. Our method's count should be zero outside filter-infeasible fallbacks.

Why not just detect stalls and call a path-finding planner, as Wang et al. do? This works on grid-like corridors, and we expect it to stay competitive there. The weaknesses are hand-tuned thresholds, discontinuous control handoffs, and the grid abstraction, none of which learns from experience. Our comparison on continuous, non-grid maps, together with the $\tau$-sensitivity sweep run against their threshold sweep, will show whether learned, filter-triggered modes actually remove that fragility or only move it.

Proposed Experiments

The scenes come from the file's synthetic doorway and corridor benchmarks, rebuilt in continuous space with double-integrator and unicycle dynamics. We extend them with corridors containing one bypass pocket, T-junctions, a roundabout, and random mazes, at team sizes of 2, 4, 8, 16, 32, and 64. Training uses 8 agents only. For road-scale transfer we use the bottleneck, tollgate, and roundabout maps of MetaDrive, which the platform reports simulating with 40+ agents at 60 FPS, with the bicycle-model filter used by HMARL-CBF. The metrics are success rate, deadlock rate (episodes that time out while the filter-equilibrium condition holds), time for the whole team to clear a bottleneck, flow rate in (m·s)$^{-1}$, deviation from nominal paths, collisions during both training and evaluation, fallback frequency, high-level decisions per episode, and environment steps needed to reach 90% of final success.

Three results would decide the question. The first is a scaling curve of success against team size in bypass corridors and T-junctions for our method, the fixed-rule filters, and Chandra et al. The proposal stands only if our advantage grows with $N$ beyond the three-agent limit of Grover et al. The second is a steps-to-competence curve against HMARL-CBF and MAPPO-Lagrangian together with the event-triggered and masking ablations. We expect at least a several-fold reduction in environment steps, and the ablations should show which ingredient contributes it. The third is the loosening-allowed ablation, which should show collisions that the tighten-only design avoids. That result would establish that the safety guarantee is a property of how the action space is built, not something the policy happens to learn.