We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Oblivious Permutations on the Plane


    Beteiligte:

    Erscheinungsdatum :

    2020-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    Oblivious permutations on the plane

    Das S. / Di Luna G. A. / Flocchini P. et al. | BASE | 2020

    Freier Zugriff

    Towards Oblivious Guidance Systems for Autonomous Vehicles

    Solnør, Petter / Petrovic, Slobodan / Fossen, Thor I. | BASE | 2023

    Freier Zugriff

    The mutual visibility problem for oblivious robots

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

    Freier Zugriff

    Software Adaptation: A Conscious Design for Oblivious Programmers

    Akkawi, Faisal / Bader, Atef / Fletcher, Daryl et al. | IEEE | 2007