  We propose a new probabilistic pattern formation algorithm for oblivious
mobile robots that operates inthe ASYNC model. Unlike previous work, our
algorithm makes no assumptions about the local coordinatesystems of robots (the
robots do not share a common "North" nor a common "Right"), yet it preserves
theability from any initial configuration that contains at least 5 robots to
form any general pattern (and not justpatterns that satisfy symmetricity
predicates). Our proposal also gets rid of the previous assumption (in thesame
model) that robots do not pause while moving (so, our robots really are fully
asynchronous), and theamount 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
deterministicpattern formation one. As the deterministic phase does not use
chirality, it may be of independentinterest in the deterministic context. A
noteworthy feature of our algorithm is the ability to form patternswith
multiplicity points (except the gathering case due to impossibility results), a
new feature in the contextof pattern formation that we believe is an important
asset of our approach.
