cs.DCOct 3, 2026

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

Authors: Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat

Organizations: Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India · Department of Mathematics, Birla Institute of Technology Mesra, Ranchi, Jharkhand, India

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study the optimal gathering problem over a finite set of designated meeting nodes for asynchronous, anonymous, and 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 Weber Meeting Node, minimizing the total Manhattan distance from their initial positions. Up to n−2n-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 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 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.

Figures & tables

Figure 1: Overview of the two phases of the CrashTolerantWeberGathering() algorithm.
Figure 2: Restricted shortest paths toward m2†m_{2}^{\dagger} . The green dots represent the robots activated to move. (a) If m2†∈Q†m_{2}^{\dagger}\in\mathcal{Q}^{\dagger} , robots enter Q†\mathcal{Q}^{\dagger} directly, except those in Qopp\mathcal{Q}^{\mathrm{opp}} , which pass through cc . (b) If m2†∈L1++m_{2}^{\dagger}\in\mathcal{L}_{1}^{++} , robots first reach L1++\mathcal{L}_{1}^{++} through their prescribed regions and then proceed along it toward m2†m_{2}^{\dagger} .
Figure 3: An asymmetric configuration with SERM=PQRS\mathcal{SER}_{\mathcal{M}}=PQRS and SERI=P′Q′R′S′\mathcal{SER}_{\mathcal{I}}=P^{\prime}Q^{\prime}R^{\prime}S^{\prime} . Here, W(t0)={m2,m3}\mathcal{W}(t_{0})=\{m_{2},m_{3}\} . Under the shorter-side traversal rule for the non-square rectangle SERM\mathcal{SER}_{\mathcal{M}} , ΓSR\Gamma_{SR} is the unique lexicographically smallest relevant Γ\Gamma -string; hence, SS is the pivot corner and Wc(t0)={m2}\mathcal{W}_{c}(t_{0})=\{m_{2}\} . Moreover, αP′S′\alpha_{P^{\prime}S^{\prime}} is the unique lexicographically smallest canonical traversal string of the entire configuration, so P′P^{\prime} is the anchor corner.
Figure 4:
Figure 5: Target-dependent restricted shortest paths. Robot rr may follow one of the purple paths through SS or r′r^{\prime} toward m1m_{1} . The red path through r′′r^{\prime\prime} leads toward the reflected candidate m2m_{2} .
More in this topic

Multi-Robot Systems

Multi-robot systems coordinate teams of robots to plan, perceive, communicate, and act together in shared tasks and environments.

See all 200 papers

Explore similar work

CardsList

  1. Asynchronous Indulgent Gathering of Opaque Robots

    Sep 12, 2025Subhajit Pramanick, Saswata Jana, Partha Sarathi Mandal +1Multi-Robot Coordination

    University of Wroclaw, Poland · Indian Institute of Technology Guwahati, India · Kent State University, USA

  2. Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

    Sep 20, 2026Animesh Maiti, Prakhar Shukla, Subhash BhagatMulti-Robot Formation ControlMobile Robotics

    Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India

  3. Huddle: Parallel Shape Assembly using Decentralized, Minimalistic Robots

    Mar 18, 2026Khai Yi Chin, Tingwei Meng, Zhe Chen +2Robotic AssemblyMulti-Robot Formation Control

    Amazon Robotics