This paper presents a distributed algorithm for circle formation problem under the infinite grid environment by asynchronous mobile opaque robots. Initially all the robots are acquiring distinct positions and they have to form a circle over the grid. Movements of the robots are restricted only along the grid lines. They do not share any global co-ordinate system. Robots are controlled by an asynchronous adversarial scheduler that operates in Look-Compute-Move cycles. The robots are indistinguishable by their nature, do not have any memory of their past configurations and previous actions. We consider the problem under luminous model, where robots communicate via lights, other than that they do not have any external communication system. Our protocol solves the circle formation problem using seven colors. A subroutine of our algorithm also solves the line formation problem using three colors.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Circle formation by asynchronous opaque robots on infinite grid


    Beteiligte:

    Erscheinungsdatum :

    2021-02-01


    Anmerkungen:

    doi:10.7494/csci.2021.22.1.3840
    Computer Science; Vol. 22 No. 1 ; 2300-7036 ; 1508-2806



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629




    Circle formation by asynchronous opaque robots on infinite grid

    Adhikary, Ranendu / Kundu, Manash Kumar / Sau, Buddhadeb | BASE | 2021

    Freier Zugriff

    Distributed computing by mobile robots: uniform circle formation

    Flocchini, Paola / PRENCIPE, GIUSEPPE / Santoro, Nicola et al. | BASE | 2017

    Freier Zugriff

    SELECTABLY OPAQUE DISPLAYS

    BAO SHENG / LIU YANG | Europäisches Patentamt | 2018

    Freier Zugriff

    Apollo 12 - Opaque oxides

    Haggerty, S. E. / Meyer, H. O. A. | NTRS | 1970


    Opaque paper withstanding immersion

    REJSEK ALICE / GERMAIN MICHEL | Europäisches Patentamt | 2023

    Freier Zugriff