We study the Uniform Circle Formation (UCF) problem, which asks a swarm of mobile agents, arbitrarily positioned onto the plane, to arrange on the vertices of a regular polygon. Each agent, customarily called robot, runs a distributed algorithm by executing a sequence of look-compute-move cycles. The robot swarm may adhere to three synchronization modes: fully synchronous, semi-synchronous, and asynchronous. Our robots are assumed to be punctiform, anonymous, and indistinguishable by their appearance; they do not store past actions or system snapshots, and they have neither a coordinate system nor chirality in common. Moreover, we consider opaque robots, i.e. they may have obstructed visibility due to collinearities. To cope with these strong limitations, we consider luminous robots, that is, they are equipped with a persistent light assuming different colors. This latter peculiarity represents the only way robots have to communicate. For all three synchronization modes, we solve the UCF problem with a constant number of colors. Concerning the running time, our solutions use a constant number of cycles (epochs) for fully synchronous (semi-synchronous) robots, and linearly many epochs in the worst-case for asynchronous robots.

Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights / C. Feletti, C. Mereghetti, B. Palano, P. Raucci (CEUR WORKSHOP PROCEEDINGS). - In: ICTCS 2022 : 23rd Italian Conference on Theoretical Computer Science 2022 / [a cura di] U. Dal Lago, D. Gorla. - [s.l] : CEUR-WS, 2022. - pp. 207-221 (( Intervento presentato al 23. convegno Italian Conference on Theoretical Computer Science tenutosi a Roma nel 2022.

Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights

C. Feletti;C. Mereghetti;B. Palano;P. Raucci
2022

Abstract

We study the Uniform Circle Formation (UCF) problem, which asks a swarm of mobile agents, arbitrarily positioned onto the plane, to arrange on the vertices of a regular polygon. Each agent, customarily called robot, runs a distributed algorithm by executing a sequence of look-compute-move cycles. The robot swarm may adhere to three synchronization modes: fully synchronous, semi-synchronous, and asynchronous. Our robots are assumed to be punctiform, anonymous, and indistinguishable by their appearance; they do not store past actions or system snapshots, and they have neither a coordinate system nor chirality in common. Moreover, we consider opaque robots, i.e. they may have obstructed visibility due to collinearities. To cope with these strong limitations, we consider luminous robots, that is, they are equipped with a persistent light assuming different colors. This latter peculiarity represents the only way robots have to communicate. For all three synchronization modes, we solve the UCF problem with a constant number of colors. Concerning the running time, our solutions use a constant number of cycles (epochs) for fully synchronous (semi-synchronous) robots, and linearly many epochs in the worst-case for asynchronous robots.
Autonomous mobile robots; Luminous robots; Opaque robots; Pattern formation
Settore INF/01 - Informatica
Italian Chapter of the European Association of Theoretical Computer Science
https://ceur-ws.org/Vol-3284/8511.pdf
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
8511.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 1.13 MB
Formato Adobe PDF
1.13 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/949971
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact