2015 | OriginalPaper | Chapter
Wait-Free Gathering Without Chirality
Authors : Quentin Bramas, Sébastien Tixeuil
Published in: Structural Information and Communication Complexity
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of gathering
n
autonomous robots that evolve in a 2-dimensional Euclidian space at a single location, not known beforehand. We suppose the robots operate in the semi-synchronous Look-Compute-Move model and are anonymous, oblivious, and disoriented.
When robots are capable of strong multiplicity detection (that is, sensing the number of robots at a given location) and the initial configuration is not bivalent, the problem is known to be deterministically solvable for
n
> 2 robots. When an arbitrary number
f
<
n
of robots may crash, recent results achieve deterministic gathering of correct robots in the classical model, assuming robots agree on a global common chirality (that is all robots have the same notion of left and right), leaving open the necessity of this assumption.
In this paper, we answer negatively to this question. Our approach is constructive: we present a deterministic gathering algorithm that admits an arbitrary number of crashes and gathers all correct robots even if they do not have a common chirality.