The distributed setting of computational mobile entities, called robots, that have to perform tasks without global coordination has been extensively studied in the literature. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) cycles. During each cycle, a robot acquires a snapshot of the surrounding environment (Look phase), then executes an appropriate algorithm by using the obtained snapshot as input (Compute phase), and finally moves toward a desired destination, if any (Move phase). Look-Compute-Move cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for the activation and synchronization of mobile robots are the well-known fully-synchronous, semi-synchronous, and asynchronous models. A first comprehensive evaluation of the computational power of robots operating in the LCM model and moving within the Euclidean plane, under different levels of synchronization, has been proposed in [1]. In detail, the authors provide a series of results that prove relations between classic models and variations of them, which consider the possibility that robots are endowed with a visible light, i.e. they are luminous, or with the capability to store some past snapshots, or combinations of them. In this paper, we are interested in similar settings but for robots moving on graphs. In particular, we propose a characterization of the computational power of mobile robots on graphs as follows. First, we show the relations among the three classic activation and synchronization models. Second, we compare the models where robots are endowed with lights against the models without lights. Third, we highlight the relations among the different models concerning luminous robots. Finally, we provide a detailed comparison of the proposed results with the case of robots moving in the Euclidean plane.
Characterizing the Computational Power of Anonymous Mobile Robots
NAVARRA, Alfredo
2016
Abstract
The distributed setting of computational mobile entities, called robots, that have to perform tasks without global coordination has been extensively studied in the literature. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) cycles. During each cycle, a robot acquires a snapshot of the surrounding environment (Look phase), then executes an appropriate algorithm by using the obtained snapshot as input (Compute phase), and finally moves toward a desired destination, if any (Move phase). Look-Compute-Move cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for the activation and synchronization of mobile robots are the well-known fully-synchronous, semi-synchronous, and asynchronous models. A first comprehensive evaluation of the computational power of robots operating in the LCM model and moving within the Euclidean plane, under different levels of synchronization, has been proposed in [1]. In detail, the authors provide a series of results that prove relations between classic models and variations of them, which consider the possibility that robots are endowed with a visible light, i.e. they are luminous, or with the capability to store some past snapshots, or combinations of them. In this paper, we are interested in similar settings but for robots moving on graphs. In particular, we propose a characterization of the computational power of mobile robots on graphs as follows. First, we show the relations among the three classic activation and synchronization models. Second, we compare the models where robots are endowed with lights against the models without lights. Third, we highlight the relations among the different models concerning luminous robots. Finally, we provide a detailed comparison of the proposed results with the case of robots moving in the Euclidean plane.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.