We consider the well known distributed setting of computational mobile entities, called robots, operating in the Euclidean plane in Look-Compute-Move (LCM) cycles. We investigate the computational impact of expanding the capabilities of the robots by endowing them with an externally visible memory register, called light, whose values, called colors, are persistent, that is they are not automatically reset at the end of each cycle. We refer to so endowed entities as luminous robots. We study the computational power of luminous robots with respect to the three main settings of activation and synchronization: fully-synchronous, semi-synchronous, and asynchronous. We establish several results. A main contribution is the constructive proof that asynchronous robots, illuminated with a constant number of colors, are strictly more powerful than traditional semi-synchronous robots. We also constructively prove that, for luminous robots, the difference between asynchrony and semi-synchrony disappears. This result must be contrasted with the strict dominance between the models without lights (even if the robots are enhanced with an unbounded amount of persistent internal memory). Additionally we show that there are problems that robots cannot solve without lights, even if they are fully-synchronous, but can be solved by asynchronous luminous robots with O(1) colors. It is still open whether or not asynchronous luminous robots with O(1) colors are more powerful than fully-synchronous robots without lights. We prove that this is indeed the case if the robots have the additional capability of remembering a single snapshot. This in turn shows that, for asynchronous robots, to have O(1) colors and a single snapshot renders them more powerful than to have an unlimited amount of persistent memory (including snapshots) but no lights.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Autonomous mobile robots with lights



    Erscheinungsdatum :

    01.01.2016



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Autonomous Mobile Robots

    H. P. Moravec | NTIS | 1986


    AUTONOMOUS VEHICLE SERVICE LIGHTS

    SALTER STUART C / DELLOCK PAUL KENNETH / BUTTOLO PIETRO et al. | Europäisches Patentamt | 2018

    Freier Zugriff

    Navigating semi-autonomous mobile robots

    STORFER LIOR / GAIDAR TAMARA / LAPIDOT IDO | Europäisches Patentamt | 2020

    Freier Zugriff

    Autonomous vehicle service lights

    SALTER STUART C / DELLOCK PAUL KENNETH / BUTTOLO PIETRO et al. | Europäisches Patentamt | 2019

    Freier Zugriff

    Autonomous recharging of mobile robots

    Birk,A. / Vrije Univ.Brussel,BE | Kraftfahrwesen | 1997