Computational power of autonomous robots: Transparency vs. opaqueness

摘要

The research on distributed computing by robot swarms has formalized different models where robots act through a sequence of Look-Compute-Move cycles in the Euclidean plane. Models mostly under study differ for (i) the possibility of storing constant-size information, (ii) the possibility of communicating constant-size information, (iii) the synchronization mode, and (iv) the visibility of robots. By varying features (i) and (ii) , we obtain the noted four base models: OBLOT (silent and oblivious robots), FSTA (silent and finite-state robots), FCOM (oblivious and finite-communication robots), and LUMI (finite-state and finite-communication robots). Feature (iii) comprehends the three main synchronization modes: fully synchronous , semi-synchronous , and asynchronous . According to robot visibility (iv) , models can assume robots to be transparent (thus enjoying complete visibility ) or opaque (thus experiencing obstructed visibility in case of collinearities). By combining features (i-iv) , we obtain 24 models. Extensive research has studied the computational power of the 12 transparent models, proving the hierarchical relations among them; to this regard, it is worth noticing that robots have been assumed to be collision-tolerant. In this work, we assume our robots to be collision-intolerant and we lay down the computational hierarchy by considering all 24 models. Firstly, we study the relations between the transparent and the opaque framework, focusing on how obstructed visibility affects the computational power of a model. Then, we introduce five witness problems that prove most of the computational relations among the 24 models. • We consider 24 robot models differing in memory, communication, synchronization, and visibility (transparent vs. opaque). • Some problems are exhibited, which cannot be solved under any opaque model. • Five witness problems are designed, showing the dominance and orthogonality relations among the models. • We introduce the phenomenon of “false election” occurring in case of asynchronism and obstructed visibility. • We provide an almost complete relation table depicting the computational hierarchy of the 24 models under study.