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: $\mathcal{O}\mathcal{B}\mathcal{L}\mathcal{O}\mathcal{T}$ (the weakest), $\mathcal{L}\mathcal{U}\mathcal{M}\mathcal{I}$ (the strongest), and two intermediate models $\mathcal{F}\mathcal{S}\mathcal{T}\mathcal{A}$ and $\mathcal{F}\mathcal{C}\mathcal{O}\mathcal{M}$. 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.