This paper studies the well-known problem of gathering multiple mobile agents moving in a graph, but unlike previous results, we consider the problem in the presence of an adversarial mobile entity which we call the malicious agent. The malicious entity can occupy any empty node and prevent honest mobile agents from entering this node. This new adversarial model is interesting as it models transient mobile faults that can appear anywhere in a network. Moreover, our model lies between the less powerful delay-fault model, where the adversary can block an agent for only a finite time, and the more powerful but static fault model of black holes that can even destroy the agents. We study the problem for ring networks and we provide a complete characterization of the solvability of gathering, depending on the size n of the ring and the number of agents k. We consider both oriented or unoriented rings with either synchronous or asynchronous agents. We prove that in an unoriented ring network with asynchronous agents the problem is not solvable when k is even, while for synchronous agents the problem is unsolvable when both n is odd and k is even. We then present algorithms that solve gathering for all the remaining cases, thus completely solving the problem. Finally, we provide a proof-of-concept implementation of the synchronous algorithms using programmable Lego Mindstorms EV3 robots.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Gathering of robots in a ring with mobile faults



    Erscheinungsdatum :

    01.01.2019



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Robots and Information Gathering

    Shaker, S. | British Library Conference Proceedings | 1994


    Getting close without touching: near-gathering for autonomous mobile robots

    PAGLI, LINDA / PRENCIPE, GIUSEPPE / Viglietta, Giovanni | BASE | 2015

    Freier Zugriff

    MANAGING MOBILE DATA GATHERING AGENTS

    SELBIE JONATHAN / HELGESSON SVEN ÅKE / PIEROPAN ALESSANDRO | Europäisches Patentamt | 2025

    Freier Zugriff

    A Flat Antenna Type Mobile Satellite News Gathering System

    Tanaka, S. / Fujita, M. / Murata, T. et al. | British Library Conference Proceedings | 1998


    Bike Assisted Evacuation on a Line of Robots with Communication Faults

    Jawhar, Khaled / Kranakis, Evangelos | ArXiv | 2023

    Freier Zugriff