Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

Ralf Klasing; Adrian Kosowski; Alfredo Navarra

doi:10.1016/j.tcs.2010.05.020

Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

Abstract

One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot.In such a restricted scenario, we study the influence of symmetries of the robot configuration on the feasibility of certain computational tasks. More precisely, we deal with the problem of gathering all robots at one node of the graph, and propose a solution based on a symmetry-preserving strategy. When the considered graph is an undirected ring and the number of robots is sufficiently large (more than 18), such an approach is proved to solve the problem for all starting situations, as long as gathering is feasible. In this way we also close the open problem of characterizing symmetric situations on the ring which admit a gathering [R. Klasing, E. Markou, A. Pelc: Gathering asynchronous oblivious mobile robots in a ring, Theoret. Comput. Sci. 390 (1) (2008) 27-39].The proposed symmetry-preserving approach, which is complementary to symmetry-breaking techniques found in related work, appears to be new and may have further applications in robot-based computing.

Citations

7 3

CrossRef
0

Web of Science
7 6

Scopus

Authors (3)

Cite as

Full text

download paper

downloaded 19 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.tcs.2010.05.020
License: Copyright (2010 Elsevier B.V)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: THEORETICAL COMPUTER SCIENCE no. 411, pages 3235 - 3246,
ISSN: 0304-3975
Language:: English
Publication year:: 2010
Bibliographic description:: Klasing R., Kosowski A., Navarra A.: Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring// THEORETICAL COMPUTER SCIENCE. -Vol. 411, nr. Iss. 34-36 (2010), s.3235-3246
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.tcs.2010.05.020
Verified by:: Gdańsk University of Technology