Metraipolis › archive › dc_aa7d280a3310
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-02T05:05:43.884Z
- SHA-256 of the archived text
664d54ec43fde9aafbb0f889048fdbc1bc124491be19561b5a99489b5e9c966e- Stable URL of this page
https://metraipolis.com/documento/dc_aa7d280a3310
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_aa7d280a3310 (Metraipolis archive dc_aa7d280a3310, sha256 664d54ec43fde9aafbb0f889048fdbc1bc124491be19561b5a99489b5e9c966e)
BibTeX
@misc{dcaa7d280a3310,
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_aa7d280a3310; sha256 664d54ec43fde9aafbb0f889048fdbc1bc124491be19561b5a99489b5e9c966e},
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-02T04:49:28.212Z dalla pagina https://arxiv.org/list/cs.RO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).