Metraipolis › archive › dc_f730abb427eb

Collision-free Movement on Grids and Beyond — arXiv:2609.31099

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.31099
License (as archived): CC0-1.0
Archived: 2026-10-08T01:37:44.636Z
SHA-256 of the archived text: 602cd876b1c582892e68b5da82da6512e494e03a9e87e9eaaf0e6dfe886d6c0d
Stable URL of this page: https://metraipolis.com/documento/dc_f730abb427eb

How to cite

Collision-free Movement on Grids and Beyond — arXiv:2609.31099 — arXiv (en), https://arxiv.org/abs/2609.31099 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f730abb427eb (Metraipolis archive dc_f730abb427eb, sha256 602cd876b1c582892e68b5da82da6512e494e03a9e87e9eaaf0e6dfe886d6c0d)

BibTeX

@misc{dcf730abb427eb,
  title = {Collision-free Movement on Grids and Beyond — arXiv:2609.31099},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31099},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f730abb427eb; sha256 602cd876b1c582892e68b5da82da6512e494e03a9e87e9eaaf0e6dfe886d6c0d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31099. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-28 in cs.MA).
Categorie arXiv: Multiagent Systems (cs.MA) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.31099 — 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-10-08T01:11:54.445Z dalla pagina https://arxiv.org/catchup/cs.MA/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).