Autonomous Mobile Robots: Refining the Computational Landscape

Within distributed computing, the study of distributed systems of identical mobile computational entities, called robots, operating in a Euclidean space is rather extensive. When a robot is activated, it executes a Look-Compute-Move cycle: it takes a snapshot of the environment (Look); with this input, it computes its destination (Compute); and then it moves towards that destination (Move). The choice of the times a robot is activated and how long its cycle lasts is made by a fair (but adversarial) scheduler; three schedulers are usually considered: fully synchronous (Fsync), semi-synchronous (Ssync), and asynchronous (Async).Extensive investigations have been carried out, under all those schedulers, within four models, corresponding to different levels of computational and communication powers of the robots: OBLOT (the weakest), LUMI (the strongest), and two intermediate models FSTA and FCOM. The many results for specific problems have provided insights on the relationships between the models and with respect to the activation schedulers. Recently, a comprehensive characterization of these relationships has been provided with respect to the Fsync and Ssync schedulers; however, in several cases, the results were obtained under some restrictive assumptions (chirality and/or rigidity). In this paper, we improve the characterization by removing those assumptions, providing a refined map of the computational landscape for those robots. We also establish some preliminary results with respect to the Async scheduler.