Probabilistic Asynchronous Arbitrary Pattern Formation
Résumé
We propose a new probabilistic pattern formation algorithm for oblivious mobile robots that operates in
the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate
systems of robots (the robots do not share a common “North” nor a common “Right”), yet it preserves the
ability from any initial configuration that contains at least 5 robots to form any general pattern (and not just
patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the
same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the
amount of randomness is kept low – a single random bit per robot per Look-Compute-Move cycle is used.
Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic
pattern formation one. As the deterministic phase does not use chirality, it may be of independent
interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form patterns
with multiplicity points (except the gathering case due to impossibility results), a new feature in the context
of pattern formation that we believe is an important asset of our approach.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...