Abstract In this work we study the strengths and limitations of collaborative teams of simple robotic agents, operating in stochastic environments. In particular, we discuss the efficient use of a swarm of “ant robots” (e.h. simple drones with a limited technical specifications) for covering a connected region on the $$\mathbf{Z}^{2}$$ grid, whose area and shape is unknown in advance and which expands stochastically. Specifically, we discuss the problem where an initial connected region of $$S_0$$ “squares” expands outward with probability p at every time step. On this grid region a group of k limited and simple drone-agents operate, with the goal of “cleaning” this unmapped and dynamically expanding region. A preliminary version of this problem was discussed in [3, 7], involving a deterministic expansion of a region in the grid. We present probabilistic lower bounds for the minimal number of agents and minimal time required to enable a collaborative coverage of the expanding region, regardless of the algorithm used and the drones’ hardware and software specifications. Furthermore, we provide a method of producing ad-hoc lower bounds, for any given desired correctness probability. We further present impossibility results that for any given values of k (the number of drones used) and spreading probability provides an upper bound for the minimal value of the initial area of the expanding region which is guaranteed to be impossible to clear. Finally, we support the analytic bounds with empirical computer simulation results.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Collaborative Patrolling Swarms in Stochastically Expanding Environments


    Beteiligte:


    Erscheinungsdatum :

    04.08.2017


    Format / Umfang :

    31 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    PATROLLING VOLLEY

    GONCHAROV IGOR NIKOLAEVICH / PURTOV PETR YAKOVLEVICH / KOREPANOV GEORGIJ NIKOLAEVICH et al. | Europäisches Patentamt | 2018

    Freier Zugriff

    The Search Complexity of Collaborative Swarms in Expanding $$\mathbf{Z}^{2}$$ Grid Regions

    Altshuler, Yaniv / Pentland, Alex / Bruckstein, Alfred M. | Springer Verlag | 2017


    Night Patrolling Robot

    Prarit Vishnoi / Aayushi Ojha / Mohd. Yasir Siddique et al. | BASE | 2021

    Freier Zugriff

    Virtual-Pheromone-Aware Path Planning for Collaborative Patrolling on Road Networks

    Zhang, Yan / Huang, Panfeng / Zhang, Fan | Springer Verlag | 2025


    A HIDDEN PATROLLING SYSTEM

    EKIN AKIF | Europäisches Patentamt | 2020

    Freier Zugriff