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.


    Access

    Download


    Export, share and cite



    Title :

    Circle formation by asynchronous opaque robots on infinite grid


    Contributors:

    Publication date :

    2021-02-01


    Remarks:

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



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629




    Circle formation by asynchronous opaque robots on infinite grid

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

    Free access

    Distributed computing by mobile robots: uniform circle formation

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

    Free access

    SELECTABLY OPAQUE DISPLAYS

    BAO SHENG / LIU YANG | European Patent Office | 2018

    Free access

    Apollo 12 - Opaque oxides

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


    Opaque paper withstanding immersion

    REJSEK ALICE / GERMAIN MICHEL | European Patent Office | 2023

    Free access