pith. sign in

arxiv: 2606.09620 · v1 · pith:2RKFEZSXnew · submitted 2026-06-08 · 💻 cs.RO · cs.SY· eess.SY

Motion planning for hundreds of floating robots

Jan Kamm , Antonio Terpin , Raffaello D'Andrea , Aswin Ramachandran This is my paper

Pith reviewed 2026-06-27 16:43 UTC · model grok-4.3

classification 💻 cs.RO cs.SYeess.SY
keywords multi-robot motion planningcollision graphinteraction clustersscalable decompositionomnidirectional floating robotstrajectory synthesisparallel optimization
0
0 comments X

The pith

A pipeline that decomposes a collision graph into interaction clusters enables collision-free motion planning for hundreds of floating robots.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that strong coupling among many robots can be broken apart without losing feasibility. It starts from an initial solution to build a graph of potential collisions, splits that graph into smaller groups where robots actually interact, and solves each group on its own. This matters for an interactive design tool that must output minute-long trajectories in seconds even when the fleet reaches hundreds of agents. The authors show the pipeline works in simulation up to 500 robots and produces usable paths in two physical deployments on water.

Core claim

The authors claim that the coupled multi-robot planning problem can be solved scalably by constructing a collision graph from an initialization, decomposing the graph into interaction clusters, and optimizing the clusters independently and in parallel, while adding robustness checks that repair common failures such as infeasible subproblems or timing violations across the sparse keyframes.

What carries the argument

Interaction-cluster decomposition of the collision graph, which isolates locally coupled subgroups so they can be solved separately without a single global optimization.

If this is right

  • Planning time stays low enough for interactive use even when transitions span minutes.
  • Fleets of 500 robots become feasible in simulation without solving the full coupled problem.
  • Physical deployment on water succeeds for at least 24 robots using the same decomposed trajectories.
  • Parallel cluster solves reduce computation while the robustness mechanisms handle most decomposition errors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method implicitly assumes that most interactions remain local after the initial graph is built, so distant robots rarely need joint re-planning.
  • If the initial graph misses some collisions, the downstream cluster solves may still succeed provided the robustness layer can recover.
  • The same decomposition pattern could be tested on other sparse-interaction systems such as ground vehicle fleets where global coupling is also weak.

Load-bearing premise

An initial collision graph plus cluster decomposition will produce feasible collision-free trajectories for the whole fleet without global re-optimization or violation of keyframe timing constraints even across thousands of time steps.

What would settle it

A 200-robot simulation in which the independently solved clusters produce collisions between robots from different clusters or miss the required keyframe times.

Figures

Figures reproduced from arXiv: 2606.09620 by Antonio Terpin, Aswin Ramachandran, Jan Kamm, Raffaello D'Andrea.

Figure 1
Figure 1. Figure 1: Floating robots in formation on Lake Zürich. In this paper, we present a planning pipeline that generates dynamically feasible, collision-free [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Schematic of the deployment procedure. An offline planner generates references using a simplified model, while an online model-predictive [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Hierarchical solver pipeline overview. Labelled Unlabelled [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Effect of the labelled fraction |L|/N on the allocation-induced straight-line initialization. As more robots are manually pinned, the remain￾ing degrees of freedom shrink, and crossings become more frequent. encoded by an injective map σ : L → {1, . . . , N}. We compute a complete allocation by solving the minimum￾cost assignment problem (equivalently, an optimal transport problem between uniform discrete … view at source ↗
Figure 6
Figure 6. Figure 6: Empirical cumulative distribution functions (ECDFs) of the time to [PITH_FULL_IMAGE:figures/full_fig_p004_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Sparsity pattern of the single-integrator constraint matrix [PITH_FULL_IMAGE:figures/full_fig_p005_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of the time to solve a subproblem for varying number [PITH_FULL_IMAGE:figures/full_fig_p005_8.png] view at source ↗
Figure 10
Figure 10. Figure 10: Floating robots in formation in Venice. individual transitions discretizing into more than 400 time steps. A picture from the live demonstration is shown in [PITH_FULL_IMAGE:figures/full_fig_p006_10.png] view at source ↗
Figure 9
Figure 9. Figure 9: Computation times (top) and success rates (bottom) for the 500- [PITH_FULL_IMAGE:figures/full_fig_p006_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: Examples of synthesized trajectories. For each example, from left to right, each figure depicts a snapshot of the fleet at a different time-step, [PITH_FULL_IMAGE:figures/full_fig_p008_11.png] view at source ↗
read the original abstract

Planning collision-free motion for large robot fleets is difficult because collision avoidance induces strong inter-agent coupling that grows rapidly with team size. We consider omnidirectional floating robots on water, where choreographies are specified by sparse keyframes and an interactive tool must generate trajectories within seconds, even when transitions span minutes and thousands of time steps. We propose a scalable pipeline that builds a collision graph from an initialization, decomposes the coupled problem into interaction clusters, and solves clusters independently (and in parallel) with robustness mechanisms for common decomposition pathologies. We validate the approach in simulations up to 500 robots. The synthesized trajectories have also been deployed in two real-world demonstrations, on Lake Z\"urich with a fleet of 24 Way of Water crafts and at the Time Space Existence 2025 Venice Biennale.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a scalable pipeline for collision-free motion planning of large fleets of omnidirectional floating robots specified via sparse keyframes. The approach constructs a collision graph from an initialization, decomposes the coupled multi-agent problem into interaction clusters, solves the clusters independently and in parallel, and incorporates robustness mechanisms for common decomposition pathologies. Validation consists of simulations with up to 500 robots plus two real-world deployments (24 robots on Lake Zürich and at the 2025 Venice Biennale).

Significance. If the pipeline reliably yields globally feasible, collision-free trajectories without requiring global re-optimization, the work would represent a practical advance for interactive planning of large aquatic robot teams over long time horizons. The parallel cluster solving and real-world hardware validation are concrete strengths that could support applications in performance robotics and environmental monitoring.

major comments (2)
  1. [Pipeline description (decomposition and robustness mechanisms)] The central claim that independent cluster solves plus robustness mechanisms produce globally collision-free fleet trajectories rests on the assumption that an initial collision graph captures all relevant interactions. The manuscript should demonstrate (via analysis or counter-example experiments) that optimized trajectories over thousands of time steps do not induce new inter-cluster collisions or timing violations that the robustness mechanisms cannot resolve without re-optimization.
  2. [Experimental validation and real-world demonstrations] Validation sections report success up to 500 robots but do not provide quantitative metrics (e.g., fraction of runs with residual inter-cluster collisions, timing-constraint violations, or failure rate of the robustness mechanisms) that would confirm the end-to-end guarantee of feasibility for the full fleet.
minor comments (2)
  1. [Method overview] Notation for the collision graph and cluster boundaries should be defined more explicitly (e.g., with a small example) to clarify how the initial graph is constructed from the initialization.
  2. [Abstract and introduction] The abstract and introduction could include a brief statement of the maximum time horizon (in steps) used in the 500-robot simulations to contextualize the long-horizon claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below with clarifications from the paper's approach and commit to revisions that strengthen the presentation without overstating the guarantees.

read point-by-point responses

  1. Referee: [Pipeline description (decomposition and robustness mechanisms)] The central claim that independent cluster solves plus robustness mechanisms produce globally collision-free fleet trajectories rests on the assumption that an initial collision graph captures all relevant interactions. The manuscript should demonstrate (via analysis or counter-example experiments) that optimized trajectories over thousands of time steps do not induce new inter-cluster collisions or timing violations that the robustness mechanisms cannot resolve without re-optimization.

    Authors: The collision graph is constructed from an initialization that spans the full time horizon of the keyframes, with edges added for any pair of robots whose swept volumes intersect at any discrete time step. Clusters are formed from connected components of this graph, and the robustness mechanisms include conservative buffer distances plus a post-solve verification pass that re-checks all original inter-cluster pairs. We will add a dedicated subsection with counter-example experiments (e.g., deliberately sparse initial graphs and long-horizon runs) that quantify any newly induced collisions after independent solves; in our existing 500-robot simulations these checks returned zero residual violations, but the new experiments will make this explicit. revision: partial

  2. Referee: [Experimental validation and real-world demonstrations] Validation sections report success up to 500 robots but do not provide quantitative metrics (e.g., fraction of runs with residual inter-cluster collisions, timing-constraint violations, or failure rate of the robustness mechanisms) that would confirm the end-to-end guarantee of feasibility for the full fleet.

    Authors: We agree that aggregate success statistics would improve the validation. The revised manuscript will include tables reporting, over 50 independent random initializations per fleet size: (i) fraction of runs with zero residual inter-cluster collisions after the final verification pass, (ii) frequency and type of robustness-mechanism triggers, and (iii) any timing-constraint violations that required fallback re-optimization. These metrics will be computed from the same simulation data already presented. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper presents an algorithmic pipeline: collision graph from initialization, decomposition into interaction clusters, independent parallel solves with robustness mechanisms. No equations, fitted parameters, or predictions are described that reduce by construction to inputs (no self-definitional relations, no fitted-input-called-prediction, no ansatz smuggled via citation). Validation relies on external simulation (up to 500 robots) and real-world deployment, which are independent benchmarks. No load-bearing self-citations or uniqueness theorems from prior author work are invoked in the abstract or described text. The skeptic concern identifies a possible empirical limitation in the initial-graph assumption but does not constitute circularity under the enumerated patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The pipeline implicitly assumes that interaction clusters can be formed from an initialization without introducing unhandled global constraints.

pith-pipeline@v0.9.1-grok · 5670 in / 1140 out tokens · 20348 ms · 2026-06-27T16:43:07.026255+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 1 canonical work pages

  1. [1]

    Choreographing the Way of Water: A computational framework for aquatic robotic art,

    A. K. Ramachandran Venkatapathy, C. Golling, S. Burmester, N. Sendlhofer, R. Jiang, J. Kamm, and R. D’Andrea, “Choreographing the Way of Water: A computational framework for aquatic robotic art,” inProceedings of the International Conference on New Interfaces for Musical Expression (NIME ’26), 2026

    2026

  2. [2]

    Multi-robot navigation in formation via sequential convex programming,

    J. Alonso-Mora, S. Baker, and D. Rus, “Multi-robot navigation in formation via sequential convex programming,” in2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Hamburg, Germany: IEEE, 2015, pp. 4634–4641

    2015

  3. [3]

    Airways: Optimization-based planning of quadrotor trajectories according to high-level user goals,

    C. Gebhardt, B. Hepp, T. Nägeli, S. Stevši ´c, and O. Hilliges, “Airways: Optimization-based planning of quadrotor trajectories according to high-level user goals,” inProceedings of the 2016 CHI Conference on Human Factors in Computing Systems. New York, NY , USA: Association for Computing Machinery, 2016, p. 2508–2519

    2016

  4. [4]

    Technical Note—A General Inner Approximation Algorithm for Nonconvex Mathematical Programs,

    B. R. Marks and G. P. Wright, “Technical Note—A General Inner Approximation Algorithm for Nonconvex Mathematical Programs,” Operations Research, vol. 26, no. 4, pp. 681–683, 1978

    1978

  5. [5]

    An application of sequential convex programming to time optimal trajectory planning for a car motion,

    Q. Tran Dinh and M. Diehl, “An application of sequential convex programming to time optimal trajectory planning for a car motion,” inProceedings of the 48th IEEE Conference on Decision and Control (CDC) held jointly with the 2009 28th Chinese Control Conference. Shanghai, China: IEEE, 2009, pp. 4366–4371

    2009

  6. [6]

    Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach,

    F. Augugliaro, A. P. Schoellig, and R. D’Andrea, “Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach,” in2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. Vilamoura-Algarve, Portugal: IEEE, 2012, pp. 1917–1922

    2012

  7. [7]

    Finding Locally Optimal, Collision-Free Trajectories with Sequen- tial Convex Optimization,

    J. Schulman, J. Ho, A. Lee, I. Awwal, H. Bradlow, and P. Abbeel, “Finding Locally Optimal, Collision-Free Trajectories with Sequen- tial Convex Optimization,” inRobotics: Science and Systems IX. Robotics: Science and Systems Foundation, 2013

    2013

  8. [8]

    Motion planning with sequential convex optimization and convex collision checking,

    J. Schulman, Y . Duan, J. Ho, A. Lee, I. Awwal, H. Bradlow, J. Pan, S. Patil, K. Goldberg, and P. Abbeel, “Motion planning with sequential convex optimization and convex collision checking,”The International Journal of Robotics Research, vol. 33, no. 9, pp. 1251–1270, 2014

    2014

  9. [9]

    Reciprocal n- body collision avoidance,

    J. Van Den Berg, S. J. Guy, M. Lin, and D. Manocha, “Reciprocal n- body collision avoidance,” inRobotics Research, ser. Springer Tracts in Advanced Robotics, C. Pradalier, R. Siegwart, and G. Hirzinger, Eds. Springer, 2011, vol. 70, pp. 3–19

    2011

  10. [10]

    Conflict-based search for optimal multi-agent pathfinding,

    G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,”Artificial Intelligence, vol. 219, pp. 40–66, 2015

    2015

  11. [11]

    CHOMP: Gradient optimization techniques for efficient motion planning,

    N. Ratliff, M. Zucker, J. A. Bagnell, and S. Srinivasa, “CHOMP: Gradient optimization techniques for efficient motion planning,” in 2009 IEEE International Conference on Robotics and Automation. Kobe: IEEE, 2009, pp. 489–494

    2009

  12. [12]

    STOMP: Stochastic trajectory optimization for motion planning,

    M. Kalakrishnan, S. Chitta, E. Theodorou, P. Pastor, and S. Schaal, “STOMP: Stochastic trajectory optimization for motion planning,” in 2011 IEEE International Conference on Robotics and Automation. Shanghai, China: IEEE, 2011, pp. 4569–4574

    2011

  13. [13]

    Distributed feedback optimisation for robotic coordination,

    A. Terpin, S. Fricker, M. Perez, M. H. de Badyn, and F. Dörfler, “Distributed feedback optimisation for robotic coordination,” in2022 American Control Conference (ACC). IEEE, 2022, pp. 3710–3715

    2022

  14. [14]

    Decentralized non- communicating multiagent collision avoidance with deep reinforce- ment learning,

    Y . F. Chen, M. Liu, M. Everett, and J. P. How, “Decentralized non- communicating multiagent collision avoidance with deep reinforce- ment learning,” in2017 IEEE International Conference on Robotics and Automation (ICRA). Singapore: IEEE, 2017, pp. 285–292

    2017

  15. [15]

    Neural graph control barrier functions guided distributed collision-avoidance multi-agent control,

    S. Zhang, K. Garg, and C. Fan, “Neural graph control barrier functions guided distributed collision-avoidance multi-agent control,” inProceedings of The 7th Conference on Robot Learning, ser. Proceedings of Machine Learning Research, vol. 229, 2023, pp. 2373–2392. [Online]. Available: https://proceedings.mlr.press/v229/ zhang23h.html

    2023

  16. [16]

    doi:10.1007/s12532-020-00179-2 , urldate =

    B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, “OSQP: an operator splitting solver for quadratic programs,”Mathematical Programming Computation, vol. 12, no. 4, pp. 637–672, Dec. 2020. [Online]. Available: https://doi.org/10.1007/s12532-020-00179-2

    work page doi:10.1007/s12532-020-00179-2 2020

  17. [17]

    Results and problems in the theory of doubly-stochastic matrices,

    L. Mirsky, “Results and problems in the theory of doubly-stochastic matrices,”Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, vol. 1, no. 4, pp. 319–334, 1963

    1963

  18. [18]

    Dynamic Programming in Probability Spaces via Optimal Transport,

    A. Terpin, N. Lanzetti, and F. Dörfler, “Dynamic Programming in Probability Spaces via Optimal Transport,”SIAM Journal on Control and Optimization, vol. 62, no. 2, pp. 1183–1206, 2024

    2024

  19. [19]

    The hungarian method for the assignment problem,

    H. W. Kuhn, “The hungarian method for the assignment problem,” Naval research logistics quarterly, vol. 2, no. 1-2, pp. 83–97, 1955

    1955

  20. [20]

    Multidimensional binary search trees used for asso- ciative searching,

    J. L. Bentley, “Multidimensional binary search trees used for asso- ciative searching,”Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975

    1975

  21. [21]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to algorithms. MIT press, 2022

    2022

  22. [22]

    Convex optimization for trajectory generation: A tutorial on generating dynamically feasible trajectories reliably and efficiently,

    D. Malyuta, T. P. Reynolds, M. Szmuk, T. Lew, R. Bonalli, M. Pavone, and B. Açıkme¸ se, “Convex optimization for trajectory generation: A tutorial on generating dynamically feasible trajectories reliably and efficiently,”IEEE Control Systems Magazine, vol. 42, no. 5, pp. 40– 113, 2022

    2022

  23. [23]

    PiNet: Optimizing hard-constrained neural networks with orthogonal projection layers,

    P. D. Grontas, A. Terpin, E. C. Balta, R. D’Andrea, and J. Lygeros, “PiNet: Optimizing hard-constrained neural networks with orthogonal projection layers,”arXiv preprint arXiv:2508.10480, 2025

    arXiv 2025

  24. [24]

    Variational analysis in the wasserstein space,

    N. Lanzetti, A. Terpin, and F. Dörfler, “Variational analysis in the wasserstein space,”arXiv preprint arXiv:2406.10676, 2024

    arXiv 2024

  25. [25]

    Deep reinforcement learning from human preferences,

    P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei, “Deep reinforcement learning from human preferences,” Advances in neural information processing systems, vol. 30, 2017. Example 1:N= 500, K= 1000, from "W ATER" to "W AY" Example 2:N= 500, K= 1000, from "of" to star Example 3: The Lake Zürich demonstration Example 4: The demonstratio...

    2017