The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.


    Access

    Download


    Export, share and cite



    Title :

    Meeting in a Polygon by Anonymous Oblivious Robots



    Publication date :

    2017-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Meeting in a polygon by anonymous oblivious robots

    Di Luna G. A. / and Flocchini P. / and Santoro N. et al. | BASE | 2020

    Free access

    Meeting in a Polygon by Anonymous Oblivious Robots

    Di Luna G. A. / Flocchini P. / Santoro N. et al. | BASE | 2017

    Free access

    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

    The mutual visibility problem for oblivious robots

    Di Luna G / Flocchini P / Poloni F et al. | BASE | 2014

    Free access

    TuringMobile: a turing machine of oblivious mobile robots with limited visibility and its applications

    Di Luna G. A. / Flocchini P. / Santoro N. et al. | BASE | 2022

    Free access