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

Abstrakt

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.

Cytowania

7 3

CrossRef
0

Web of Science
7 6

Scopus

Autorzy (3)

Cytuj jako

Pełna treść

pobierz publikację

pobrano 23 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2010.05.020
Licencja: Copyright (2010 Elsevier B.V)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: THEORETICAL COMPUTER SCIENCE nr 411, strony 3235 - 3246,
ISSN: 0304-3975
Język:: angielski
Rok wydania:: 2010
Opis bibliograficzny:: 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:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2010.05.020
Weryfikacja:: Politechnika Gdańska