We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: M_{init}, which denotes the number of nodes between two border nodes, and O_{init}, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if M_{init} or O_{init} is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.


    Access

    Download


    Export, share and cite



    Title :

    Gathering on Rings for Myopic Asynchronous Robots With Lights


    Contributors:

    Publication date :

    2020-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    000 / 004 / 629




    Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights

    Okumura, Takashi / Wada, Koichi | BASE | 2018

    Free access

    Autonomous mobile robots with lights

    Das, Shantanu / Flocchini, Paola / PRENCIPE, GIUSEPPE et al. | BASE | 2016

    Free access

    Gathering of robots in a ring with mobile faults

    Das, Shantanu / Focardi, Riccardo / Luccio, Flaminia L. et al. | BASE | 2019

    Free access

    Myopic biases in competitions

    Radzevick, Joseph R. | Online Contents | 2008


    Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots

    Giuseppe A. Di Luna / Ryuhei Uehara / Giovanni Viglietta et al. | BASE | 2020

    Free access