cs.DCSep 12, 2025

Asynchronous Indulgent Gathering of Opaque Robots

Authors: Subhajit Pramanick, Saswata Jana, Partha Sarathi Mandal, Gokarna Sharma

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We consider the benchmarking problem of gathering in an (N,f)(N,f)-fault system consisting of NN robots, of which at most ff may fail at any execution. The {\em traditional} version asks N−fN-f non-faulty robots to gather at a point not known a priori. The recently studied {\em indulgent} version asks N−fN-f non-faulty robots to gather at the location of a faulty one. Indulgent gathering is impossible in a (2,1)(2,1)-crash system in the LUMILUMI model under semi-synchrony, even when infinitely many colors and coordinate axis agreement are available. In this paper, we establish four results for indulgent gathering under asynchrony in LUMILUMI, considering a {\em mobility fault} model in which a robot crash only impacts its mobility but not the operation of the light. We first show that indulgent gathering is impossible in a (2,1)(2,1)-mobility system using 2-colored lights, and then give an optimal solution w.r.t. the number of colors using 3-colored lights. We then give two deterministic algorithms for an (N,f)(N,f)-mobility system, f<Nf<N, N,fN,f unknown, that exhibit a nice time-color trade-off: One with time O(N)O(N) using 7-colored lights and another with time O(max⁡{ℓ,f})O(\max\{\ell,f\}) using 26-colored lights, where ℓ<N\ell< N is the number of distinct convex layers of robot positions in the initial configuration. Our algorithms for an (N,f)(N,f)-mobility system are the first to be analysed time complexity, can withstand obstructed visibility (opaque robot model) and asynchronous scheduling. Interestingly, our algorithms also solve traditional gathering.

Figures & tables

PaperSynchronySystemGatheringOpacityModelTime
[ 26 ]SSYNC\mathcal{SSYNC}(2,0)(2,0) -faultImpossible–OBLOT\mathcal{OBLOT}–
[ 1 ]ASYNC\mathcal{ASYNC}(3,1)(3,1) -ByzantineImpossibleNoOBLOT\mathcal{OBLOT}–
[ 17 ]ASYNC\mathcal{ASYNC}(2,0)(2,0) -faultPossible–2- LUMI\mathcal{LUMI}–
[ 1 ]SSYNC\mathcal{SSYNC}(N,1)(N,1) -crashPossibleNoOBLOT\mathcal{OBLOT}–
[ 1 ] ∗FSYNC\mathcal{FSYNC}(N,f)(N,f) -ByzantinePossibleNoOBLOT\mathcal{OBLOT}–
Table 1: Results on traditional gathering. ∗N≥3f+1{}^{*}N\geq 3f+1 . OBLOT≡\mathcal{OBLOT}\equiv 1- LUMI\mathcal{LUMI} . ‘–’ in time means finite time.
NotationMeaning
Move action (first component of an action)
StStstay : the robot does not move
MMmeet : the robot moves onto the other robot’s current position
ShShshift : the robot moves to some other point, i.e. neither robot’s current position
Sh=mSh=ma shift onto the midpoint mm
Sh≠mSh\neq ma shift onto a point other than the midpoint mm
Table 3: List of notation used in the 2- LUMI\mathcal{LUMI} impossibility
Figure 1: Case 1 of the 22 - LUMI\mathcal{LUMI} impossibility.
Figure 2: Case 2 of the 22 - LUMI\mathcal{LUMI} impossibility.
Figure 3: An asynchronous execution in which the adversary delays the completion of an LCM cycle while the other robot executes multiple cycles.
Figure 4: Case 3 of the 22 - LUMI\mathcal{LUMI} impossibility.
Figure 5: Case 4 of the 22 - LUMI\mathcal{LUMI} impossibility.
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
More in this topic

Multi-Robot Coordination

Multi-robot coordination studies how teams of robots plan, communicate, allocate tasks, and act together safely and efficiently.

See all 317 papers

Explore similar work

CardsList
Oct 3, 2026

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

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.

Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty +1

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

Multi-Robot SystemsMulti-Robot CoordinationResilient Multi-Robot Coordination
AskPDF
Oct 3, 2026

Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model

We investigate the mutual visibility problem for a swarm of n≥3n\ge3 autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the SSYNC\mathsf{SSYNC} model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.

Prakhar Shukla, Animesh Maiti, Shivam Kumar +1

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

Resilient Multi-Robot CoordinationMulti-Robot Coordination
AskPDF
Sep 20, 2026

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the gathering problem, where robots gather at a point not known to them a priori, and the circle formation problem, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common chirality. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.

Animesh Maiti, Prakhar Shukla, Subhash Bhagat

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

Multi-Robot Formation ControlMobile RoboticsRobotics
AskPDF