A robot moving through a crowd has to guard against the chance that people will not move the way its predictor expects. The standard robust approach draws a separate "worst-case bubble" around every pedestrian at every future timestep and plans so that the robot stays safe even if each person, independently, does the most dangerous thing inside their bubble. In a dense crowd this assumes that everyone misbehaves at once. The bubbles merge, no safe motion remains, and the robot stops. This is the well-known freezing robot problem. We propose to replace the many independent bubbles with a single shared budget of deviation that an imagined adversary must spread across the whole crowd and the whole planning horizon. The robot then guards against the worst plausible joint deviation of the crowd, not the union of every individual's worst case.
The motivation is that the two literatures have each found half of this problem. Robust reinforcement learning has shown that letting the adversary choose worst cases independently at each state and action, a property called rectangularity, produces compounding pessimism and paralyzed policies. Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization removes this with coupled, non-rectangular uncertainty, but tests it only on synthetic linear MDPs and option pricing. Crowd-navigation work has documented freezing whenever safety buffers grow (HiCrowd, Frozone, Interaction-aware Conformal Prediction), yet the distributionally robust planners that exist still build one uncertainty set per obstacle per step. Nobody has connected the diagnosis from one field to the failure in the other.
Core Claim
Freezing in distributionally robust crowd navigation is largely an artifact of rectangular, per-obstacle ambiguity sets. Distributionally robust optimization (DRO) means optimizing against the worst distribution within some neighborhood of the data, and that neighborhood is called an ambiguity set. We claim that one Wasserstein ambiguity set placed over the joint future trajectory of all nearby agents keeps the same guarantee on the probability of any collision while leaving much more free space. A Wasserstein ball is a set of distributions reachable from the empirical samples by moving probability mass a bounded total distance.
The existing baseline, Distributionally Robust CVaR-Based Safety Filtering, works per obstacle. It builds a Wasserstein ball around the predicted-position samples of each obstacle $i$ at each step $t$, and it requires the conditional value-at-risk (CVaR, the average loss over the worst $\alpha$-fraction of outcomes) of that obstacle's halfspace violation $\ell_{i,t}$ to be non-positive. To bound the probability of any collision over $N$ agents and $T$ steps at level $\alpha$, this per-constraint design must implicitly split the risk, with each of the $NT$ constraints held to roughly $\alpha/(NT)$. That split is where the buffers blow up.
We instead impose a single constraint on the joint crowd trajectory $\xi = (\xi_1,\dots,\xi_N)$:
$$\sup_{Q:\,W_d(Q,\hat P_\pi)\le \varepsilon}\ \mathrm{CVaR}^{Q}_{\alpha}\Big[\max_{i,t}\ \ell_{i,t}(x_t,\xi_i)\Big]\le 0 .$$
Here $\hat P_\pi$ is the empirical distribution of joint crowd rollouts conditioned on the robot's candidate plan $\pi$, and $x_t$ is the robot state. $W_d$ is the Wasserstein distance under the additive ground metric $d(\xi,\xi')=\sum_i \lVert \xi_i-\xi'_i\rVert$. Because this metric adds up displacements across people, the adversary's total budget $\varepsilon$ must be shared. For the piecewise-linear halfspace losses used in the safety filter, the worst-case shift of each sample goes to whichever agent is closest to binding, not to all of them. The robust margin therefore grows with the single most threatening interaction rather than with the number of people. The formulation stays a convex program of the same kind the per-obstacle filter already solves.
The joint set is less conservative only where the per-obstacle set was being pessimistic in physically implausible ways. It can be less safe when a crowd deviates together, for example in a surge. We handle this by letting members of the same group, found by DBSCAN clustering as in HiCrowd, share a displacement coordinate. A coordinated group deviation then costs the adversary as much as a single person's deviation.
Research Program
The system has three parts.
The nominal crowd distribution comes from joint multi-agent rollouts. We use the joint diffusion forecaster from Safe Diffusion MPC (SICNav-JMID), a generator that denoises random noise into joint trajectories for all humans. Its samples are conditioned on the robot's current plan through the Plan-Simulate-Calibrate loop of Interaction-aware Conformal Prediction. That loop makes the ambiguity set decision-dependent: its center moves with what the robot intends to do.
The joint DR-CVaR constraint is reformulated as linear constraints on the robot's controls. It replaces the per-obstacle halfspaces inside the same quadratic-program safety filter used by the per-obstacle baseline, so any compute difference comes from the ambiguity set and not from the solver.
The radius $\varepsilon$ is chosen by held-out calibration: we pick the smallest $\varepsilon$ whose empirical joint-collision frequency on held-out interactive rollouts falls below $\alpha$. This mirrors how the conformal baseline picks its buffer, which makes the two directly comparable.
On the analysis side, we will prove that the joint set's buffer is never larger than the per-obstacle set's buffer at the same joint risk level. We will also characterize when the gap is large: many agents, long horizons, and deviations that are only weakly correlated.
Baselines
The naive reference is a model predictive controller (MPC) that predicts pedestrians with a constant-velocity model, the low-level controller in HiCrowd. HiCrowd reports that pure MPC with this model freezes up to 10x more often than flow-aligned navigation. We run it with the same horizon and control limits as our method. Beating it on freezing is necessary but says little on its own.
The most direct competitor is the per-obstacle filter from Distributionally Robust CVaR-Based Safety Filtering. It sits downstream of a nominal planner and avoided all collisions under heavy-tailed Laplace errors in that paper. We found no reported result on Lacuna for it on ETH/UCY or the ORCA crowd benchmark, so we will run it ourselves with three controls held fixed. It gets the same diffusion samples, the same number of samples, and the same solver. Its per-obstacle radius is tuned over the same grid we use for our joint radius. Beating it means lower freezing frequency and shorter navigation time at an equal or lower measured rate of any collision.
The statistical competitor is Interaction-aware Conformal Prediction. In its interactive ORCA crowd simulator it reports safety coverage of about 0.93 (offline conformal prediction reaches about 0.85). It also reports roughly 11.12 s navigation time with 10 humans, against 17.48 s for standard ORCA. We use its simulator and densities (5 to 20 humans) and match its 0.93 coverage level. We count it beaten if we reach comparable coverage with shorter navigation time and fewer freezes, especially at 15 to 20 humans, where the conformal buffers are known to fill the available channels.
The flow-following heuristic is HiCrowd. It reports a success rate of 1.00 and 19.10 s navigation time on its ETH/UCY online tests, with freezing frequency near 0.00. It is the strongest non-robust method, and we compare against it under its own protocol.
Two ablations isolate the key ingredient. The first keeps the plan-conditioned samples but uses per-obstacle sets, which tests joint versus rectangular sets. The second keeps the joint set but uses plan-independent samples, which tests the contribution of decision-dependence. A third variant drops the group-shared coordinates, which tests safety under coordinated deviations.
Why not just…?
Why not just shrink the per-obstacle Wasserstein radius until the robot stops freezing? This is the most serious threat. A smaller radius does reduce freezing, but it discards the joint guarantee in exactly the dense scenes where many constraints are active. The decisive test is a frontier. We sweep the radius for both methods and plot the rate of any collision against freezing frequency. If a tuned per-obstacle filter matches our frontier, the central claim fails and we will report that. The theory predicts the gap widens with crowd size and horizon, and we will check that prediction by stratifying results by density.
Why not just lower the coverage level in conformal prediction? Conformal prediction gives a per-person, marginal radius, so lowering coverage shrinks every bubble equally, just as a smaller rectangular radius does. It also inherits its guarantee from the ORCA simulator. We test this by including interaction-aware conformal prediction at several coverage levels on the same collision-versus-freezing frontier. We also evaluate every method on ETH/UCY replays, where the real humans are not ORCA agents.
Why not just use flow-following, as in HiCrowd or Frozone? HiCrowd relies on a compatible group moving toward the robot's goal and gives no bound when flows scatter. Frozone switches to an uncertified learned policy above about 1 person/m² (Frozone). Flow-following is complementary, since the joint filter can sit beneath HiCrowd's follow point. We therefore also report HiCrowd with our filter replacing its constant-velocity MPC, in counter-flow and scattered-flow ORCA scenes.
Why not just use Gaussian chance constraints? Towards Integrated Perception and Motion Planning with Distributionally Robust Risk Constraints found that Gaussian constraints underestimate risk near narrow passages. We include a Gaussian chance-constrained filter only as a sanity baseline, under Laplace-perturbed prediction errors.
Proposed Experiments
The main experiment uses the interactive ORCA simulator at 5, 10, 15 and 20 humans, with a fixed fraction of non-yielding agents added to probe adversarial non-cooperation. We measure the rate of any collision per episode, empirical joint coverage, freezing frequency, success, navigation time and solve time per step. The decisive check is the collision-versus-freezing frontier described above.
A second experiment runs closed-loop tests on ETH/UCY with the HiCrowd protocol. This measures transfer when humans do not follow the simulator the ambiguity set was calibrated on.
A third, stress-test experiment injects coordinated group deviations. It checks whether the group-shared metric keeps collisions within $\alpha$, and whether the ungrouped joint set fails there as the analysis predicts.
We will also run a secondary test using the admissible-strategy setup from Rethinking Safe Control in the Presence of Self-Seeking Humans. That paper shows that a robot which always yields teaches self-seeking humans to stop cooperating entirely. We will adapt its two-agent bottleneck and ask whether a less passive joint-robust robot keeps human cooperation above zero.
The project succeeds if the joint set strictly dominates the tuned per-obstacle filter on the frontier at 15 or more humans. It fails if the frontiers coincide.
References
- Robust Offline Reinforcement Learning with Linearly Structured $f$-Divergence Regularization
- HiCrowd: Hierarchical Crowd Flow Alignment for Dense Human Environments
- Frozone: Freezing-Free, Pedestrian-Friendly Navigation in Human Crowds
- Interaction-aware Conformal Prediction for Crowd Navigation
- Distributionally Robust CVaR-Based Safety Filtering for Motion Planning in Uncertain Environments
- Safe Diffusion Model Predictive Control for Interactive Robotic Crowd Navigation
- Towards Integrated Perception and Motion Planning with Distributionally Robust Risk Constraints
- Rethinking Safe Control in the Presence of Self-Seeking Humans