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

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.

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

In cooperative environments, such as in factories or assistive scenarios, it is important for a robot to communicate its intentions to observers, who could be either other humans or robots. A legible trajectory allows an observer to quickly and accurately predict an agent's intention. In adversarial environments, such as in military operations or games, it is important for a robot to not communicate its intentions to observers. An illegible trajectory leads an observer to incorrectly predict the agent's intention or delays when an observer is able to make a correct prediction about the agent's intention. However, in some environments there are multiple observers, each of whom may be able to see only part of the environment, and each of whom may have different motives. In this work, we introduce the Mixed-Motive Limited-Observability Legible Motion Planning (MMLO-LMP) problem, which requires a motion planner to generate a trajectory that is legible to observers with positive motives and illegible to observers with negative motives while also considering the visibility limitations of each observer. We highlight multiple strategies an agent can take while still achieving the problem objective. We also present DUBIOUS, a trajectory optimizer that solves MMLO-LMP. Our results show that DUBIOUS can generate trajectories that balance legibility with the motives and limited visibility regions of the observers. Future work includes many variations of MMLO-LMP, including moving observers and observer teaming.