Metraipolis › archive › dc_26343d100b89

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes — arXiv:2610.06939

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.06939
License (as archived)
CC0-1.0
Archived
2026-10-07T11:17:14.853Z
SHA-256 of the archived text
0d9b356fcb46b61ccc6ae27e0b689de7b3e1e55e661a38a1ec418ae51c456be0
Stable URL of this page
https://metraipolis.com/documento/dc_26343d100b89

How to cite

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes — arXiv:2610.06939 — arXiv (en), https://arxiv.org/abs/2610.06939 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_26343d100b89 (Metraipolis archive dc_26343d100b89, sha256 0d9b356fcb46b61ccc6ae27e0b689de7b3e1e55e661a38a1ec418ae51c456be0)
BibTeX
@misc{dc26343d100b89,
  title = {When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes — arXiv:2610.06939},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.06939},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_26343d100b89; sha256 0d9b356fcb46b61ccc6ae27e0b689de7b3e1e55e661a38a1ec418ae51c456be0},
  year = {2026}
}

Archived text

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

We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a \textsc{Weber Meeting Node}, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a \textsc{Weber Meeting Node}. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm \textsc{CrashTolerantWeberGathering()} selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.MA, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Computational Geometry (cs.CG); Multiagent Systems (cs.MA).
Pagina del lavoro: https://arxiv.org/abs/2610.06939 — 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-07T11:15:09.466Z dalla pagina https://arxiv.org/list/cs.MA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).