Braid-Indexed Plan Libraries for Multi-Robot Teams That Must Survive Contact with Reality

When several robots share a space, each robot's safe moves depend on what the others do: if one robot is two seconds late, the gap another robot was planning to slip through may be gone. Today's strongest multi-robot planners return one joint plan. When execution drifts from simulation, through wheel slip, latency, or a slightly wrong map, the only remedy is to replan from scratch. This proposal builds something different. Offline, it constructs a library of joint plans that differ in their topology: which robot passes which side of which, and in what order. Online, when the executed motion drifts and the current plan becomes infeasible, the team switches to a library entry from a different topological class. The bet is that the plan that saves you after a perturbation is usually not a small adjustment of the failed plan. It is one where the robots weave around each other differently, and a gradient-based replanner started from the failed plan rarely finds it.

Building the library combines three ingredients. MAP-Elites is a search method that keeps the best solution found in each cell of a grid of user-chosen behavior descriptors, instead of keeping only one overall best. Differentiable rasterization is a way of drawing shapes onto a pixel grid so that gradients flow from pixels back to shape coordinates. Pairwise winding numbers count how many times one robot circles another over a trajectory. In the proposed method, each robot's footprint over time is drawn softly onto a shared space-time grid, together with an occupancy map. This gives one differentiable collision field for both robot–robot and robot–obstacle contact, and the field uses the same kind of image the real robots build from their sensors. MAP-Elites, with a gradient repair step on this field, fills an archive keyed by the team's winding signature.

Core Claim

For multi-robot teams with interdependent feasible actions, a library of joint plans that covers many distinct braid (winding) classes gives higher execution success under sim-to-real perturbations than a single optimized plan with online replanning, at equal offline compute. Gradient-repaired MAP-Elites fills such a library with more distinct classes than restarting gradient descent from random initial plans. The claim has two parts and could fail at either one. The library may not help robustness, or MAP-Elites may not beat multi-start search at building it. The experiments are designed to separate the two.

Relation to Prior Work

Several papers motivate the gap. Prof. Robot shows that optimizing a robot only for pixel alignment drives it into collisions. It reports collision rates falling from 99% to 17% once a learned signed-distance classifier is added. That classifier is trained for static scenes and, by the authors' account, loses accuracy when objects move. We avoid learning the coupling at all: other robots' footprints are re-rasterized at each time step, so moving obstacles are handled by construction. Waymax documents a related failure in multi-agent simulation. Policies trained against always-yielding simulated drivers exploit that politeness and transfer badly. This is evidence that a single plan tuned to a particular partner behavior is fragile, which is the failure a topologically diverse library is meant to buffer.

Other papers supply the method. SC-GAN rasterizes trajectories into Gaussian heatmaps so that image-space map penalties flow back into coordinates. It does this for single actors against static maps, and we extend the rasterizer to many mutually coupled agents. Bézier Splatting shows that splatting curves as 2D Gaussians speeds up differentiable rendering by up to 150x. We reuse this footprint representation to keep space-time rasterization cheap. BeTop uses braid theory to describe how driving agents cross in space-time, but it uses braids as a supervised prediction target. We use them as archive keys for search.

Some papers constrain the design. Evaluating MAP-Elites on Constrained Optimization Problems finds that plain MAP-Elites with random mutation almost never lands on thin feasible sets. Collision-free joint plans in a narrow corridor form such a set, so our variation operator must include a gradient repair step rather than relying on mutation. Differentiable Collision Avoidance Using Collision Primitives optimizes multi-robot trajectories locally through implicit differentiation, and its authors report getting stuck in local minima in clutter. Our repair step will hit the same minima, and the archive is what is supposed to route around them. GAME is the closest quality-diversity work on interdependent agents. It coevolves strategies with derivative-free mutation and indexes them by CLIP embeddings of rendered video, and it is evaluated only in game engines. We differ in using gradients, in using topological descriptors instead of visual appearance, and in measuring physical transfer. Finally, Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models (SMD) is the strongest single-plan competitor. It is centralized, returns one plan per call, and does not maintain a repertoire of alternatives.

Research Program

Plans are parameterized as one spline per robot with fixed start and goal points. The fixed endpoints remove the start/goal equality constraints that defeat plain MAP-Elites. At time step $t$, robot $i$'s footprint is splatted into a soft occupancy image $O_i^t(p)$ over pixels $p$. The static map $M(p)$ is an occupancy image: in simulation it comes from benchmark geometry, and on hardware from the robots' own mapping. The coupled infeasibility is

$$C(\tau)=\sum_t\sum_p\Big(\sum_{i<j}O_i^t(p)\,O_j^t(p)+\sum_i O_i^t(p)\,M(p)\Big),$$

where $\tau$ is the joint plan. The first term encodes the interdependence: moving robot $j$ changes the gradient robot $i$ feels. The descriptor of a plan is its winding signature. For each pair of robots that come within an interaction radius, we compute

$$w_{ij}=\frac{1}{2\pi}\sum_t \Delta\arg\big(x_i^t-x_j^t\big),$$

the accumulated rotation of robot $j$ around robot $i$, rounded to the nearest half-integer. The rounded vector identifies which side each pair passes and how often they circle each other. Because only observed signatures are stored, in a dictionary rather than a full grid, the exponential cost of a 36-pair grid for nine robots is never paid.

One MAP-Elites iteration selects an elite and perturbs it. The perturbation is either a random mutation or a descriptor-directed step that uses the fact that the unrounded $w_{ij}$ is differentiable, pushing a chosen pair toward an unoccupied neighboring class. The child is then repaired with a few gradient steps on $C$ plus a smoothness term. Its signature is recomputed after repair, so a repair that changes class is still kept, just in a different cell. Fitness is negative makespan subject to $C$ falling below a tolerance.

At execution time, the team tracks its current plan. When the measured state makes the current plan's predicted $C$ exceed the tolerance, it re-times every archive entry from the current state and switches to the best feasible one. This is a lookup plus a short repair, not a fresh plan.

Baselines

The naive reference is a single plan from gradient repair alone, started from straight-line paths and executed open-loop with tracking control. It shows how often doing nothing clever fails under perturbation.

The strongest existing method is SMD, run on its own Multi-Robot Motion Planning (MRMP) benchmark. It reports a 96% success rate with nine robots in dense maps, against 27% for the earlier diffusion planner MMD, and 100% on narrow-corridor swaps where other diffusion planners scored 0%. We run SMD with its released training setup on the same layouts. Under perturbation, SMD is allowed to replan from the current state whenever infeasibility is detected, with its wall-clock replanning time charged to the robots, which wait while it computes. Beating it means higher execution success at matched perturbation levels, without longer makespans. For library-backed execution under perturbation, no reported result was found on Lacuna, so these numbers are new measurements.

The ablation that isolates the archive is multi-start gradient repair. Random initial plans are repaired, the results are binned by the same winding signature, and the run gets the same number of collision-field evaluations as MAP-Elites. If this baseline fills as many classes and gives the same robustness, the contribution is the braid-indexed library itself, not quality-diversity search. We would report it that way.

A second ablation replaces the rasterized field with analytic pairwise disc distances, which isolates the rasterization. A third baseline is a single robust plan with inflated clearance margins. It stands in for domain-randomization-style conservatism and lets us measure how much makespan the margins cost.

Why not just…?

Why not just restart gradient descent many times and cluster the results by topology? This is the most serious threat, because in low-dimensional search multi-start local optimization is often competitive with quality-diversity methods. The case for MAP-Elites rests on stepping stones. Qian et al. prove that keeping low-fitness intermediate solutions can beat objective-only search on deceptive problems. Rare braid classes, such as a three-way rotation in a corridor, may be reachable only from neighboring classes and not from random initial plans. Classes found per unit of compute, in dense nine-robot maps and in corridors, decides this directly. If the two curves overlap, we drop the claim about MAP-Elites.

Why not just sample SMD many times, or replan with it online? Diffusion sampling tends to concentrate in dominant modes, and SMD's projection step pulls samples toward nearby feasible plans, which may all share one topology. We will measure how many distinct winding classes 100 SMD samples cover. If SMD sampling covers as many classes as the archive, the archive's remaining advantage is only switching latency, and the latency experiment measures exactly that.

Why not just use analytic distances between disc-shaped robots? For disc robots on polygon maps, analytic distances are simpler and probably just as good, and the ablation should show parity there. Rasterization earns its place only when robots have irregular footprints, or when the map comes from sensors as an occupancy image, as it does on hardware. In that case the same pipeline consumes the simulated map and the real one without converting the real map to geometry. If parity holds even on sensor-built maps, rasterization is a convenience and not a contribution, and we will say so.

Why not just add safety margins or randomize dynamics? Wider margins buy robustness by making robots slower and by closing narrow passages altogether, which is the over-conservatism problem known from domain randomization. Plotting success against makespan for the inflated-margin baseline and for the library, across margin sizes, shows whether the library sits strictly above the trade-off curve.

Proposed Experiments

All planning runs on the MRMP layouts used by SMD, with fleets of three, six, and nine robots across random, corridor, shelf, and room maps.

Coverage is measured as distinct feasible winding classes per scene and as a quality-diversity score: summed fitness over the cells the archive fills. Both are reported against collision-field evaluations, for MAP-Elites, multi-start repair, and SMD sampling.

Robustness is measured in a perturbed simulator that injects per-robot start delays, velocity-tracking lag, and map errors, the last by eroding or dilating obstacles in the occupancy image. Each of these is swept over magnitudes. We report execution success, collisions, makespan, and decision latency for every method.

The decisive check is the delay sweep. If library switching keeps success high at delay levels where SMD-with-replanning and inflated margins fall off, the core claim holds. If not, it fails. A second check asks whether successful switches usually land in a different winding class from the failed plan. If most rescues stay within the same class, local repair would have sufficed, and topological diversity is not the mechanism.

A small hardware tier then repeats the corridor-swap and room scenarios. It uses three to six differential-drive robots tracked by an overhead motion-capture system, with maps built from onboard sensing. The question is whether the success ordering from the perturbed simulator carries over to the real robots.