Designing
Planning Algorithms
for the Era of Parallelism
One algebra for batched tensor search: global graphs, local connectors, optimal transport, rollouts, and learned priors as a single Generate·Score·Reduce operator.
TU Darmstadt (visiting) · VinRobotics
The hardware stopped waiting for the algorithm. The algorithm has to meet the hardware.
Parallel hardware is a design constraint, like dynamics, collision, or uncertainty.
What changed
- GPUs, SIMD CPUs, FPGAs, and edge accelerators are now commodity for robotics.
- ML stacks (JAX · XLA · MuJoCo XLA · Triton) made dense, batched compute the default kernel.
- Classical planners, built for serial pointer chasing, leave most of this hardware idle.
That is the RoboARCH question: match each algorithm to the hardware it runs best on, from CPU SIMD and GPU to FPGA, MCU, edge, and cloud.
Do not ask “how do I parallelize my planner?”
Ask: “what planner would I write if parallelism were the primitive?”
1 · Generate
Make many similar subproblems visible at once, as one batched object.
2 · Score
Evaluate every candidate independently; keep geometry and logic, do not flatten into brute force.
3 · Reduce
End with one structured reduction: min, Sinkhorn, expectation, score, DP.
Three verbs, held for the whole talk: Generate · Score · Reduce.
Three schools, one lesson: design for what batches.
VAMP · FCIT*
ICRA 2024 · 2025
Vectorize the kernels of sampling-based planning. 35 µs median, ~25 kHz on one CPU core (7-DoF Panda); FCIT* = first fully-connected a.s.-optimal.
cuRobo · pRRTC · cpRRTC
2023–2025
Batched trajopt; GPU-parallel RRT-Connect. cuRobo: ~60× vs CPU, ~30 ms full pipeline. pRRTC (MotionBenchMaker Panda, mean planning time): 128× cuRobo, 3× slower than VAMP-RRTC, 1.4× slower than GTMP; cpRRTC up to 165× constrained.
GTMP · MPOT · CLOT · MTP · MPD
RA-L · NeurIPS · ICRA · ICLR · T-RO · 2023–2026
Make the graph itself a batched object. GTMP: 1000 paths in 4.6 ms.
One design pressure across the field: expose more regular, batched, schedulable work. Benchmark of record: MotionBenchMaker.
A planner is a compute substrate, not only a path generator.
$M$ layers, $N$ samples per layer, each a point in configuration space $\mathbb{R}^d$. Now turn this into a search.
A planner is a compute substrate, not only a path generator.
What this buys you
- Many candidate futures in one object, diversity by construction.
- Local work distributed across SIMT lanes.
- Global decisions recovered by reductions (DP, Sinkhorn, prune).
- Theorems and kernels describe the same object.
The batched object is the Generate stage. Design a graph whose natural operations are batched kernels.
teal · tensor / batch axes sage · value / cost orchid · operator / reducer rose · this‑talk highlight
Every planner here is Generate → Score → Reduce.
Three verbs. Each is a typed map; their composition is the planner.
Every planner here is Generate → Score → Reduce.
$$\textbf{Planner}=\textcolor{#8a3f9c}{\textstyle\bigoplus}\,\circ\,\textcolor{#557a3a}{s}\,\circ\,\textcolor{#2f7d8a}{\mathcal{G}_\theta}.\qquad\text{\small Different planners are different semiring choices for one skeleton.}$$
Five planners, one kernel: they differ only in the reduction.
Generate and Score are shared; a planner only chooses the reducer $\oplus$ over the semiring $(\mathbb{S},\oplus,\otimes)$. One compiled kernel, five planners, with a single temperature knob sliding between them.
One kernel schedule for all five planners, and the honest caveat.
Reduction-invariance
Every $\oplus_\lambda$ is associative, so all five share one iteration space, one memory layout, and one $O(\log B)$ reduction tree. One compiled template instantiated by swapping the combine op.
What actually differs
- min is one comparator; soft-min spends $\exp/\log$ on the SFU (with a max-shift for stability).
- Register pressure and occupancy differ, so “one template” $\ne$ identical wall-clock.
- $\min$ returns an index (argmin path); soft-min returns a distribution.
The proof object and the compute object are the same: the semiring is both the algebra in the theorem and the reduction in the kernel. Invariant skeleton, method-specific arithmetic. Next: the per-method work and depth.
Associativity buys an $O(\log B)$ reduction tree. That is the architecture payload.
Embarrassingly-parallel Score gives $W=|B|\,\text{cost}(s)$ at fixed depth; an associative $\oplus$ folds it in $O(\log B)$. Available parallelism $W/D$ sets the ceiling; realized speed is then capped by bandwidth and occupancy.
| Method | Semiring $(\oplus,\otimes)$ | Work $W$ | Depth $D$ |
|---|---|---|---|
| GTMP | $(\min,+)$ | $\Theta(MN^2)$ | $\Theta(M\log N)$ |
| MPOT | soft-min, $+$ | $\Theta(T\,nm)$ | $\Theta(T\log n)$ |
| CLOT | OT $\otimes$ STL min/max | $\Theta(R\,(Tnm{+}|\Phi|T))$ | $\Theta(R\log nm)$ |
| MTP | expectation | $\Theta(BH)$ | $\Theta(H{+}\log B)$ |
| MPD | score | $\Theta(KB\,c_\theta)$ | $\Theta(K\,d_\theta)$ |
Every method shares the depth signature $D=(\text{sequential scan})+O(\log B)$. The scan length is the number an architect should optimize.
Global search becomes a layered random multipartite graph.
The aha: the graph IS a tensor
- Sample N dream points in each of M layers.
- Evaluate adjacent-layer edges in batch.
- Run finite-horizon value iteration on the layered DAG.
One graph contains several qualitatively different route families, so diversity is a property of the data structure, not a post-processing step.
The Bellman backward pass is a tropical matrix–vector product.
Edge count
Single start/goal, complete adjacent-layer connectivity. Every adjacent-layer pair is an independent local subproblem.
Backward DP · the Reduce step
A batched min-reduction over the next-layer axis: $J_m = C_m\boxtimes J_{m+1}$, tropical GEMV: the segment_min the accelerator runs.
The edge is the interface between global combinatorics and local geometry.
Reach $\Lambda$: at budget $s$, with confidence $1-\tau$, the connector succeeds on local hops up to length $\ell$.
GTMP consumes, doesn't compete: each connector is the per-edge local Generate and Score, a pluggable oracle, while the tropical Reduce stays fixed.
VAMP‑RRTC · pRRTC · AORRTC · FCIT* · cuRobo · CHOMP · MPD
Anytime should not conflate diversity and optimality.
Mode RR · diversity
- Fix $(M,\,N,\,s)$; draw independent graph realizations.
- Top-$B$ class-indexed elite archive.
- Diversity = coverage of distinct route families: $\delta$-robust homotopy classes, paths inequivalent under deformation in the $\delta$-inflated free space.
geometric rate, so almost-sure coverage as $K\to\infty$ (2nd Borel–Cantelli)
Mode AO · cost
- Grow $M_\nu,\,N_\nu \to \infty$; keep $s$ fixed.
- Informed samples inside a shrinking prolate hyperspheroid.
- Reuse + prune edges; AO$^\star$-style convergence to $c^\star$.
optimality by contracting support
Two schedules of the same reducer: diversity repeats generation, optimality enriches it.
Top of the feasibility hierarchy, with a batch throughput nothing else matches.
anytime-GTMP charts: results from a manuscript under preparation.
500 parallel Panda instances in ~0.3 ms via JAX vmap on RTX 3090. On MotionBenchMaker feasibility time, GTMP sits with VAMP-RRTC at the top, ~1.4× faster than pRRTC.
Warm the temperature: swap GTMP's hard min for a soft-min.
GTMP selects one vertex. Relax the selection and the same DP becomes differentiable transport.
Sinkhorn Step: the soft-min relaxation of the tropical DP.
$\lambda\to 0$ recovers GTMP: the transport plan concentrates on the min-cost vertices, soft selection becomes hard selection.
Sinkhorn is matrix-scaling: the densest GPU-friendly inner loop.
Gradient-free because the search set is a polytope.
The generator $\mathcal{G}_\theta$
- Each waypoint emits a batch of candidate moves along polytope vertices.
- No gradients: the score is a black box evaluated per direction.
- Rotations randomize the probe so coverage stays isotropic.
Choosing $D_P$ is choosing the Generate stage; Sinkhorn does the Reduce.
From a 2-D probe to whole-body mobile manipulation.
Same reducer as GTMP, one temperature warmer. The batch axis is the trajectory; the polytope is the per-waypoint candidate set.
Finite temperature turns the same substrate into an online control loop.
The aha: a graph becomes a loop
- The candidate object is a control rollout, not an edge.
- Tensorized MuJoCo-XLA rollouts on the
vmapsubstrate. - The reducer is a finite-$\lambda$ Gibbs expectation, not a hard min.
Same Generate·Score·Reduce as GTMP, now replanning every step instead of building one graph.
Two Boltzmann reducers at two temperatures, convexly mixed.
Roll out
$B$ control sequences of horizon $H$, scored by a black-box simulator in parallel.
Then mix
Each component is a Gibbs measure $\pi_\bullet\propto e^{-J/\eta_\bullet}$ (its weights $p_{\eta_\bullet}=\nabla_v R_{\eta_\bullet}$), so the convex mix is again a valid distribution: an explicit exploit (cold $\eta_{\text{loc}}$) to explore (warm $\eta_{\text{glb}}$) knob $\beta$.
Both reducers are $\nabla R_\lambda$ from the temperature family: expectation is just soft-min, differentiated.
The expectation reducer explores where MPPI and OpenAI-ES stall.
Same batch budget, same hardware. The reducer's temperature decides how much of the space the rollouts actually see. Demonstrated across in-hand cube, G1 whole-body, and crane.
From single-robot transport to multi-robot, temporal-logic-coupled transport.
Multi-robot STL tasks
- Collision avoidance + dynamic feasibility.
- Relative formation + connectivity maintenance.
- Bounded-time temporal goals: globally $G^I$, eventually $F^I$, until $U^I$.
GPU-parallel, gradient-free Sinkhorn steps over batches of system-wide trajectories.
Start from the MPOT cost …
One robot, one transport cost. Now couple many robots under temporal logic.
STL robustness, collective cost, connectivity: all batchable.
STL robustness
Parse-tree decomposition: a batched min/max reduction over time slices, tropical again.
Collective cost
Task robustness + obstacle penalty + inter-robot penalty, all dense per timestep, summed over robots.
Connectivity
Algebraic connectivity $\lambda_2$ of the inter-robot Laplacian $L(t)$: a smooth, batchable surrogate for the Boolean connected predicate. $\lambda_2\ge\varepsilon\Rightarrow\varepsilon$-robustly connected.
The Sinkhorn step is untouched. The cost surface gets richer; the update stays a dense regular kernel.
Three reducers, one stack: sequence · optimal transport · STL min/max.
CLOT is GSR nested three deep. Each level is its own Generate·Score·Reduce; the semirings compose without changing the kernel schedule.
CLOT treats the robot planning order as part of the search.
Hybrid search node
$\nu$ indexes both the discrete planning sequence and the continuous candidate-trajectory set, so the search is over both at once.
Value function
Coverage minus accumulated cost plus back-propagated feedback $\psi(\nu)$; the weight $\eta\in(0,1)$ scales cost onto the coverage scale.
Scalability and reliability on STL-coupled multi-robot tasks.
| Method | Success N=12 | Time N=12 |
|---|---|---|
| CLOT (ours) | 1.00 | 20.3 s |
| MPOT | 0.10 | 26.5 s |
| FSOT | 0.70 | 19.8 s |
| CONS | 0.00 | n/a |
| MICP / NLP / CBS | 0.00 | n/a |
3-UAV hardware: planned in 2.91 s, formation tracked to ±0.1 m.
STL goal: $\varphi = \textcolor{#8a3f9c}{G}_{\textcolor{#2f7d8a}{[8,15]}}\,\textcolor{#557a3a}{\mu_{B}}$. Always between $t=8$ and $t=15\,\text{s}$, maintain the linear formation.
Guidance is a score-function reducer, the warm end of the family.
Denoise, then guide
- $D_\theta$: learned prior, the Generate stage.
- $\nabla_z J$: guidance, the score-function Reduce.
- $B_\psi$: maps control latents to a smooth B-spline trajectory (learnable knots), so guidance acts on $C^2$, dynamically feasible curves.
The per-step $-\nabla_z J$ is the score $\nabla_z\log p(z)$ of the Boltzmann target $p\propto e^{-J}$ (the normalizer drops out), the score end of the temperature continuum.
Five planners, one batched kernel.
One Generate·Score·Reduce skeleton; each planner exposes the parallel work its hardware runs best.
Five rules I keep returning to.
Generate many · Score in batch · Reduce with structure
- Expose independent work early.
- Replace pointer-heavy control flow with dense algebra.
- Separate global exploration from local connection.
- Treat diversity and optimality as different compute allocations.
- Make the proof object match the compute object.
What this is not
- Not “GPU everywhere.”
- Not abandoning geometry or proofs.
- Not claiming one planner wins everywhere.
It is a way to design algorithms whose bottlenecks are visible, measurable, and schedulable.
A planner can be compiled into a heterogeneous robotics stack.
The same plan flows across three schedulers: the right allocation of algorithm to computing hardware.
Where I hope this community pushes next.
Lazy tensor graphs with guarantees
Skip most edges while proving homotopy-critical edges survive.
Class-aware extraction
If the graph contains many route families, enumerate them deliberately.
Connector-aware scheduling
Adapt $(M,N,s)$ online from measured $\bigl(q_s,\Lambda_s\bigr)$ profiles.
Compiler / runtime co-design
Should planners ship as XLA / JAX programs? Benchmark homotopy coverage and compute efficiency, not only first-solution time.
These are algorithm, architecture, and systems questions, not only motion-planning questions.
Parallelism is a design constraint, not an implementation detail.
The next planning algorithms will be judged by the workloads they expose, not only the paths they return.
the math is too beautiful to ignore.
Thank you
