Diffusion models (generators that learn to turn random noise into realistic samples by removing noise step by step) are now strong multi-robot motion planners. The best of them enforce hard safety rules by projecting the model's guess at the clean trajectory onto the set of allowed trajectories at every denoising step. These planners represent a trajectory as a list of waypoints, so "safe" only means "safe at the waypoints." Two robots can pass through each other between consecutive samples, and planners that stitch segments together produce velocity and acceleration spikes at the seams. We propose to run the same projection loop on the control points of a Bézier curve. A Bézier curve is a smooth polynomial curve that always stays inside the polygon formed by a few control points. Collision, speed, and smoothness rules then become conditions on those points, and any trajectory that satisfies them is guaranteed safe at every instant, not just at sampled times.
That guarantee comes at a price: control-point conditions are conservative, and conservative constraints are stiff. The projection then either fails or distorts the sample far from what the model learned. Our second idea is to read this stiffness off the projection solver itself. The Lagrange multipliers (the solver's running estimate of how hard each constraint is pushing back) show which curve segments are over-constrained. We split exactly those segments in half with the de Casteljau algorithm, which gives the same curve with more control points and a tighter safety condition. A residual-balancing penalty rule keeps the solver well-conditioned while the constraint set changes under it. In short, the proposal is a diffusion planner whose outputs come with continuous-time safety certificates, using a refinement scheme that only spends constraints where the certificate is binding.
Core Claim
Write each robot's trajectory on a time segment as $p(t)=\sum_{k=0}^{n} P_k B_{k,n}(t)$, where $B_{k,n}$ are the degree-$n$ Bernstein polynomials and $P_k$ are the control points. Many planning constraints become simple conditions on the $P_k$.
Velocity and acceleration limits become linear bounds on differences of control points, because the derivative of a Bézier curve is again a Bézier curve. Smoothness across segments becomes linear equalities between neighbouring control nets, which directly removes the seam spikes reported for Discrete-Guided Diffusion. Inter-robot separation becomes a Bernstein basis conversion. For robots with control points $P_k$ and $Q_k$, let $D_k=P_k-Q_k$. The squared distance is a degree-$2n$ polynomial with Bernstein coefficients
$$c_m=\sum_{i+j=m}\frac{\binom{n}{i}\binom{n}{j}}{\binom{2n}{m}}\,D_i\cdot D_j,\qquad m=0,\dots,2n.$$
Because Bernstein polynomials are nonnegative and sum to one, requiring $c_m\ge r^2$ for every $m$ guarantees the robots stay at least distance $r$ apart for all $t$ in the segment. Obstacles described by half-spaces or spheres convert the same way.
Within one projection, when a segment's constraint stays violated and its multiplier exceeds a threshold, we subdivide that segment at $t=1/2$. The penalty $\beta$ follows a residual-balancing rule in the spirit of LADMPSAP: it is raised when the feasibility residual dominates the change in the dual variables, and lowered otherwise. The claim to be tested has three parts. First, this planner matches the waypoint-level success rate of the strongest projected diffusion planners. Second, it achieves certified zero continuous-time violation, where waypoint planners show measurable violations between samples. Third, multiplier-guided subdivision reaches feasibility with fewer constraints and less distortion than either uniform subdivision or no subdivision.
Relation to Prior Work
The projection machinery comes from the projected diffusion planners: PDM, SMD and DGD. PDM introduced Augmented Lagrangian projection, a constrained solver that combines penalties with multipliers, for continuous multi-agent paths. SMD splits convex and non-convex constraints inside the denoising loop. DGD routes robots through convex regions so that each projection is cheap. All three parameterize paths as waypoints and use fixed or hand-tuned penalty schedules. They motivate this work because they leave between-waypoint safety unaddressed and, in DGD's case, produce discontinuities at region boundaries. The general predict-project-renoise pattern, and the observation that open-loop penalty schedules work, come from Constrained Posterior Sampling. Its schedule $\gamma(t)$ depends only on the noise level and is the same for every sample; ours reacts to each sample's residuals.
The Bernstein side is supplied by PCBA, which bounds polynomial costs and constraints using Bernstein coefficients and branches by subdivision. PCBA also constrains our design. It subdivides the decision space and stops being practical beyond about four dimensions. We subdivide only the one-dimensional time parameter of each segment, so cost grows with the number of binding segments rather than exponentially with dimension. PCBA is a deterministic optimizer, not a sampler, so it has no learned prior over multimodal behaviour. Bajaj and Xu provide precedent for subdividing until coefficient conditions hold. Their breakpoints are fixed by roots of derivatives; ours are chosen by dual information.
The adaptive-weighting ingredient adapts LADMPSAP's residual balancing. Its convergence proof assumes convexity, which our separation constraints violate, so we treat it as a heuristic and test it rather than claim a guarantee. We take a warning from Projected Coupled Diffusion, which found that projection dampens coupling forces and required ad hoc inflation of the coupling weights. Its finding that projection can collapse diversity is why we measure diversity explicitly.
Research Program
We will build two variants. The plug-in variant reuses an existing waypoint diffusion model. Least-squares fitting maps waypoints to Bézier control points through a fixed linear transformation. At each step we convert the predicted clean trajectory to control points, project there, and convert back for renoising. This requires no retraining and isolates the effect of the representation. The native variant trains the diffusion model directly on control nets, fit by least squares to the same demonstration data that MMD and SMD use.
The projection is an Augmented Lagrangian solver over control points. Linear constraints (speed, acceleration, endpoints, continuity) are handled by exact projection. The bilinear separation coefficients are handled through multipliers. Penalties follow residual balancing, and subdivision is triggered by the multipliers. Each projection is warm-started from the previous denoising step's multipliers and subdivision pattern, so most refinement happens once and is then inherited.
The analysis component will establish two results. First, every returned plan is certified for all $t$ through the coefficient conditions above. Second, the conservatism gap of these conditions shrinks quadratically with segment length under subdivision, which is a standard property of Bézier control polygons and is why a few splits usually suffice. We will report empirically how many subdivisions per segment are needed as robot density grows.
Baselines
The naive reference is the unprojected waypoint diffusion prior, together with the same prior with post-hoc smoothing. These show how often raw samples are infeasible in continuous time.
The strongest success-rate competitor is SMD, which reports a 96% success rate with 9 robots in dense maps, against 27% for MMD, and 100% on the narrow-corridor swap where other diffusion baselines reach 0% (SMD). The strongest scalable competitor is DGD, which reports 100% success in Room and Shelf maps with 18 robots and matches SMD on dense 6-robot maps at 4% of its computation time (DGD). Both will be run on the same benchmark instances with the same trained priors where code allows, the same number of denoising steps, and an equal tuning budget for penalty hyperparameters. We will also report a waypoint-density sweep for SMD so that it can buy continuous-time safety with more waypoints.
For continuous-time violation itself, no reported result was found on Lacuna for any of these planners. We will measure it ourselves by deep Bernstein certification and by sampling each output at 1000 times its waypoint resolution. Beating the baselines means matching SMD and DGD success within confidence intervals while achieving zero certified violations where they show nonzero between-waypoint violations, at wall-clock time no worse than SMD.
On the tabletop and two-car tasks, the training-time competitor is Constraint-Aware Diffusion, which raises the feasible ratio from 8.5% to 58.3% using a lookahead violation loss during training.
Three ablations isolate the key ingredients. The first removes subdivision and uses fixed degree only. The second replaces multiplier-guided splitting with uniform subdivision at a matched total control-point count. The third replaces residual balancing with SMD's fixed penalty schedule and with a CPS-style schedule that depends only on noise level.
Why not just…?
Why not just use denser waypoints? This is the most serious threat. At high enough density, sampled violations become rare. However, density never yields a certificate, and projection cost grows with the number of constraint points; PCD already reports a 4–7x slowdown from per-step projection (PCD). The density sweep against SMD settles the question. If dense waypoints reach zero measured violation at lower wall-clock time than our certified planner, the remaining contribution is the certificate alone, and we will say so.
Why not plan with waypoints and certify or repair afterwards? Fitting a Bézier curve to an SMD output and repairing it with a PCBA-style solver is plausible for one or two robots. Joint repair of many robots is exactly the high-dimensional regime where PCBA stops scaling. Post-hoc repair also moves samples away from the learned distribution without the model getting a chance to adapt in later denoising steps. We will run a "SMD + fit + projection at the final step only" baseline. If it matches us, then in-loop projection on control points is unnecessary.
Why not just keep a fixed penalty schedule? It may well suffice for linear constraints. Our argument for adaptivity is specific: subdivision adds constraints during the solve, so a schedule tuned for one constraint count is mis-scaled after splitting. The penalty-schedule ablations measure iterations to feasibility and the distance between the projected and unprojected predictions. If fixed schedules match, we drop residual balancing and keep the multiplier-guided subdivision.
Why not train constraint awareness into the model? Constraint-Aware Diffusion's 58.3% feasible ratio (Li et al.) shows that training-time losses leave many samples infeasible, and that approach costs 4–7x more training time. It is complementary at best, and we will test it as a prior under our projection.
Decisive Experiments
All experiments use the 4,000-instance multi-robot benchmark (Random, Corridor, Shelf, Room, plus the 104-obstacle large map) and the tabletop and two-car datasets of 350,000 SNOPT trajectories. Metrics are success rate, certified and densely sampled continuous-time violation, path length, peak acceleration and jerk at segment seams, wall-clock time per plan, and diversity, measured as pairwise trajectory distance across samples from the same start and goal.
Three results decide the proposal. First, waypoint planners must show nonzero between-waypoint violations at their reported success rates; otherwise the representation change addresses a non-problem. Second, the plug-in variant must achieve certified zero violation with success within a few points of SMD and DGD. Third, multiplier-guided subdivision must beat uniform subdivision at a matched constraint count on Corridor and dense Random maps, where the conservatism of control-point conditions bites hardest. A secondary check on DGD's Room and Shelf maps tests whether linear continuity constraints across regions remove its seam acceleration spikes without losing its speed advantage.
References
- Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning
- Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
- Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models
- Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models
- Constrained Posterior Sampling: Time Series Generation with Hard Constraints
- Safe, Optimal, Real-Time Trajectory Planning With a Parallel Constrained Bernstein Algorithm
- Converting a Rational Function to a Standard NURBS Representation
- Projected Coupled Diffusion for Test-Time Constrained Joint Generation
- Constraint-Aware Diffusion Models for Trajectory Optimization