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

Prakhar Shukla; Animesh Maiti; Shivam Kumar; Subhash Bhagat

cs.DCOct 3, 2026

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

Authors: Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat

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

Abstract

We investigate the mutual visibility problem for a swarm of $n\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 $\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.

Figures & tables

Reference	Faults	Scheduler	Axis/assumption	Colors	Time	Approach
Poudel et al. [ 12 ]	$f$	$\mathsf{ASYNC}$	One-axis agreement	$3$	$O(n)$	Non-convex hull
Pramanick et al. [ 15 ]	$f$	$\mathsf{ASYNC}$	No axis agreement	$35$	$O(n)$	Convex hull
This work	$\boldsymbol{f}$	$\boldsymbol{\mathsf{SSYNC}}$	Beacon and uniform movement budget	$\mathbf{12}$	$\boldsymbol{O(n)}$	Non-convex hull

Table 1: Existing work on mutual visibility algorithms under mobility fault.

Figure 1: Illustration of adjacent and friend robots. The adjacent robot pairs are $(r_{i},r_{j})$ , $(r_{j},r_{k})$ , and $(r_{k},r_{l})$ . Since $r_{j}$ and $r_{k}$ are non-terminal robots, $r_{i}$ and $r_{k}$ are the friend robots of $r_{j}$ , whereas $r_{j}$ and $r_{l}$ are the friend robots of $r_{k}$ .

Panel of Figure 2 — Figure 2: Illustration of cyclic dependencies: (a) a cyclic configuration involving four non-terminal robots, where the black robots are faulty, and (b) a cyclic dependency involving multiple critical non-terminal robot positions.

Figure 3: An illustration of resolving an equal-distance cyclic dependency. (a) The critical non-terminal robots lie on a common circle centered at $P^{*}$ . (b) If the robots move equal distances toward $P^{*}$ , the existing collinearities are broken. (c) If they move unequal distances due to non-rigid movement, the collinearities are also broken, and the robots attain distinct distances from $P^{*}$ , inducing an order for Phase III.

Resilient Multi-Robot Coordination

See all 11 papers

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
When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes
Oct 3, 2026Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty +1Multi-Robot Systems Multi-Robot Coordination
Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, Rajasthan, India · Department of Mathematics, Birla Institute of Technology Mesra, Ranchi, Jharkhand, India
From Legible to Inscrutable Trajectories: (Il)legible Motion Planning Accounting for Multiple Observers
Feb 9, 2026Ananya Yammanuru, Maria Lusardi, Nancy M. Amato +1Trajectory Optimization Trajectory Generation
University of Illinois at Urbana-Champaign, Urbana IL 61801, USA

Sep 12, 2025J/K move · Enter open · S save

Asynchronous Indulgent Gathering of Opaque Robots

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

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

Multi-Robot Coordination

Open paper AskPDF arXiv

We consider the benchmarking problem of gathering in an

(N,f)

-fault system consisting of

N

robots, of which at most

f

may fail at any execution. The {\em traditional} version asks

N-f

non-faulty robots to gather at a point not known a priori. The recently studied {\em indulgent} version asks

N-f

non-faulty robots to gather at the location of a faulty one. Indulgent gathering is impossible in a

(2,1)

-crash system in the

LUMI

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

LUMI

, 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)

-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)

-mobility system,

f<N

N,f

unknown, that exhibit a nice time-color trade-off: One with time

O(N)

using 7-colored lights and another with time

O(\max\{\ell,f\})

using 26-colored lights, where

\ell< N

is the number of distinct convex layers of robot positions in the initial configuration. Our algorithms for an

(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.

Abstract

Resilient Multi-Robot Coordination

Explore similar work

Asynchronous Indulgent Gathering of Opaque Robots

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

From Legible to Inscrutable Trajectories: (Il)legible Motion Planning Accounting for Multiple Observers