We study the Uniform Circle Formation (UCF) problem for a distributed system of n robots which are required to displace on the vertices of a regular n-gon. We consider a well-studied model of autonomous, anonymous, mobile robots that act on the plane through Look-Compute-Move cycles. Moreover, robots are unaware of the cardinality of the system, they are punctiform, completely disoriented, opaque, and luminous. Collisions among robots are not tolerated. In the literature, the UCF problem has been solved for such a model by a deterministic algorithm in the asynchronous mode, using a constant amount of light colors and O(n) epochs in the worst case. In this paper, we provide an improved algorithm for solving the UCF problem for asynchronous robots, which uses O(log n) epochs still maintaining a constant amount of colors.
O(log n)-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots / C. Feletti, C. Mereghetti, B. Palano (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS). - In: 27th International Conference on Principles of Distributed Systems (OPODIS 2023)[s.l] : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. - ISBN 9783959773089. - pp. 5:1-5:21 (( Intervento presentato al 27. convegno International Conference on Principles of Distributed Systems, OPODIS 2023 tenutosi a Tokyo nel 2023 [10.4230/LIPIcs.OPODIS.2023.5].
O(log n)-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots
C. FelettiPrimo
;C. MereghettiSecondo
;B. PalanoUltimo
2024
Abstract
We study the Uniform Circle Formation (UCF) problem for a distributed system of n robots which are required to displace on the vertices of a regular n-gon. We consider a well-studied model of autonomous, anonymous, mobile robots that act on the plane through Look-Compute-Move cycles. Moreover, robots are unaware of the cardinality of the system, they are punctiform, completely disoriented, opaque, and luminous. Collisions among robots are not tolerated. In the literature, the UCF problem has been solved for such a model by a deterministic algorithm in the asynchronous mode, using a constant amount of light colors and O(n) epochs in the worst case. In this paper, we provide an improved algorithm for solving the UCF problem for asynchronous robots, which uses O(log n) epochs still maintaining a constant amount of colors.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
942.13 kB
Formato
Adobe PDF
|
942.13 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.