We study the Rendezvous problem for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors. If robots can observe not only their own lights but also other robots' lights, their lights are called full-light. If robots can only observe the state of other robots' lights, the lights are called external-light. This paper focuses on robots with external-lights in asynchronous settings and a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and three colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors. In this paper, extending the impossibility result, we show that there exist no L-algorithms in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC and other robots can execute at most one Look operation between the Look operation of a robot and its subsequent Compute operation. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:

    Publication date :

    2018-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Autonomous mobile robots with lights

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

    Free access

    Gathering on Rings for Myopic Asynchronous Robots With Lights

    Kamei, Sayaka / Lamani, Anissa / Ooshita, Fukuhito et al. | BASE | 2020

    Free access

    Optimal Spacecraft Rendezvous Using Genetic Algorithms

    Young Ha Kim / David B. Spencer | AIAA | 2002



    Optimal Multiple-Impulse Time-Fixed Rendezvous Using Evolutionary Algorithms

    Gong, Mian / Zhou, Di / Shao, Chuntao et al. | AIAA | 2021