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.


    Access

    Download


    Export, share and cite



    Title :

    Autonomous mobile robots with lights



    Publication date :

    2016-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    Autonomous Mobile Robots

    H. P. Moravec | NTIS | 1986


    AUTONOMOUS VEHICLE SERVICE LIGHTS

    SALTER STUART C / DELLOCK PAUL KENNETH / BUTTOLO PIETRO et al. | European Patent Office | 2018

    Free access

    Navigating semi-autonomous mobile robots

    STORFER LIOR / GAIDAR TAMARA / LAPIDOT IDO | European Patent Office | 2020

    Free access

    Autonomous vehicle service lights

    SALTER STUART C / DELLOCK PAUL KENNETH / BUTTOLO PIETRO et al. | European Patent Office | 2019

    Free access

    Autonomous recharging of mobile robots

    Birk,A. / Vrije Univ.Brussel,BE | Automotive engineering | 1997