We study the Uniform Circle Formation (UCF) problem for a swarm of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the Euclidean plane. We assume our robots are luminous, i.e. equipped with a persistent light that can assume a color chosen from a fixed palette, and opaque, i.e. not able to see beyond a collinear robot. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. To solve UCF, a swarm of n robots must autonomously arrange themselves so that each robot occupies a vertex of the same regular n-gon not fixed in advance. In terms of efficiency, the goal is to design an algorithm that optimizes (or provides a tradeoff between) two fundamental performance metrics: (i) the execution time and (ii) the size of the color palette. In this paper, we develop a deterministic algorithm solving UCF avoiding collisions in O(1)-time with O(1) colors under the asynchronous scheduler, which is asymptotically optimal with respect to both time and number of colors used, the first such result. Furthermore, the algorithm proposed here minimizes for the first time what we call the computational SEC, i.e. the smallest circular area where robots operate throughout the whole algorithm.

Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots / C. Feletti, D. Pattanayak, G. Sharma (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS). - In: 38th International Symposium on Distributed Computing (DISC 2024)[s.l] : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. - ISBN 9783959773522. - pp. 46:1-46:7 (( Intervento presentato al 38. convegno International Symposium on Distributed Computing tenutosi a Madrid nel 2024 [10.4230/LIPIcs.DISC.2024.46].

Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots

C. Feletti;
2024

Abstract

We study the Uniform Circle Formation (UCF) problem for a swarm of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the Euclidean plane. We assume our robots are luminous, i.e. equipped with a persistent light that can assume a color chosen from a fixed palette, and opaque, i.e. not able to see beyond a collinear robot. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. To solve UCF, a swarm of n robots must autonomously arrange themselves so that each robot occupies a vertex of the same regular n-gon not fixed in advance. In terms of efficiency, the goal is to design an algorithm that optimizes (or provides a tradeoff between) two fundamental performance metrics: (i) the execution time and (ii) the size of the color palette. In this paper, we develop a deterministic algorithm solving UCF avoiding collisions in O(1)-time with O(1) colors under the asynchronous scheduler, which is asymptotically optimal with respect to both time and number of colors used, the first such result. Furthermore, the algorithm proposed here minimizes for the first time what we call the computational SEC, i.e. the smallest circular area where robots operate throughout the whole algorithm.
Autonomous Robots; Computational SEC; Rank Encoding; Robots with Lights; Time and Color Complexities; Uniform Circle Formation
Settore INFO-01/A - Informatica
2024
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
DISC24_BA_Optimal_UCF.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 810.7 kB
Formato Adobe PDF
810.7 kB 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/1122415
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact