When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

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.

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.

We propose a novel algorithm for forming arbitrarily shaped assemblies using decentralized robots. By relying on local interactions, the algorithm ensures there are no unreachable states or gaps in the assembly, which are global properties. The in-assembly robots attract passing-by robots into expanding the assembly via a simple implementation of signaling and alignment. Our approach is minimalistic, requiring only communication between attached, immediate neighbors. It is motion-agnostic and requires no pose localization, enabling asynchronous and order-independent assembly. We prove the algorithm's correctness and demonstrate its effectiveness in forming a 107-robot assembly.