Metraipolis › archive › dc_4149c90bd27f
Contact-based optimization for collision-free motion planning for a million robots — arXiv:2610.41548
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41548
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T05:47:25.061Z
- SHA-256 of the archived text
a9d38be26bbfbe7ed202224132deb1f452ed073d57900248953726bba9daf1f4- Stable URL of this page
https://metraipolis.com/documento/dc_4149c90bd27f
How to cite
Contact-based optimization for collision-free motion planning for a million robots — arXiv:2610.41548 — arXiv (en), https://arxiv.org/abs/2610.41548 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4149c90bd27f (Metraipolis archive dc_4149c90bd27f, sha256 a9d38be26bbfbe7ed202224132deb1f452ed073d57900248953726bba9daf1f4)
BibTeX
@misc{dc4149c90bd27f,
title = {Contact-based optimization for collision-free motion planning for a million robots — arXiv:2610.41548},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41548},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4149c90bd27f; sha256 a9d38be26bbfbe7ed202224132deb1f452ed073d57900248953726bba9daf1f4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41548. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Multi-agent robotic systems have attracted growing interest in recent years, with applications ranging from coordinated drone shows to autonomous operations on land, in the air, and on water. At the planning level, robot motion is often modeled using double-integrator dynamics (with low-level controllers handling the physical dynamics during execution) with a minimum-energy objective subject to collision-avoidance constraints and limits on position, velocity, and acceleration. The complexity of the problem resides in the constraints, which couple the trajectories and make the optimization problem nonconvex. Existing numerical approaches typically discretize and optimize entire trajectories, which becomes expensive for large fleets. We exploit the structure of optimal trajectories by organizing optimization around contacts, at which robots reach the minimum allowed separation. We formulate a coupled algebraic system in contact variables and reconstruct trajectories analytically between contacts. Our algorithm, sequential contact insertion (SCI), starts from unconstrained trajectories, inserts contacts at separation violations, and jointly adjusts their times and states. Numerical experiments demonstrate planning for one million robots in minutes and thousands of robots in fractions of a second. On problems feasible for a fixed-grid sequential convex programming baseline, SCI achieves median speedups of several orders of magnitude at matching solution accuracy. Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.RO, nuovi lavori del giorno). Categorie arXiv: Robotics (cs.RO) ; Systems and Control (eess.SY). Pagina del lavoro: https://arxiv.org/abs/2610.41548 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T05:33:48.019Z dalla pagina https://arxiv.org/list/cs.RO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).