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.


    Access

    Download


    Export, share and cite



    Title :

    Gathering of robots in a ring with mobile faults



    Publication date :

    2019-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    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

    Free access

    MANAGING MOBILE DATA GATHERING AGENTS

    SELBIE JONATHAN / HELGESSON SVEN ÅKE / PIEROPAN ALESSANDRO | European Patent Office | 2025

    Free access

    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

    Free access