Computing the k-resilience of a synchronized multi-robot system
From MaRDI portal
(Redirected from Publication:721922)
Computing the \(k\)-resilience of a synchronized multi-robot system
Computing the \(k\)-resilience of a synchronized multi-robot system
Abstract: We study an optimization problem that arises in the design of covering strategies for multi-robot systems. Consider a team of cooperating robots traveling along predetermined closed and disjoint trajectories. Each robot needs to periodically communicate information to nearby robots. At places where two trajectories are within range of each other, a communication link is established, allowing two robots to exchange information, provided they are "synchronized", i.e., they visit the link at the same time. In this setting a communication graph is defined and a system of robots is called emph{synchronized} if every pair of neighbors is synchronized. If one or more robots leave the system, then some trajectories are left unattended. To handle such cases in a synchronized system, when a live robot arrives to a communication link and detects the absence of the neighbor, it shifts to the neighboring trajectory to assume the unattended task. If enough robots leave, it may occur that a live robot enters a state of emph{starvation}, failing to permanently meet other robots during flight. To measure the tolerance of the system under this phenomenon we define the emph{-resilience} as the minimum number of robots whose removal may cause surviving robots to enter a state of starvation. We show that the problem of computing the -resilience is NP-hard if is part of the input, even if the communication graph is a tree. We propose algorithms to compute the -resilience for constant values of in general communication graphs and show more efficient algorithms for systems whose communication graph is a tree.
Recommendations
- On the robustness of a synchronized multi-robot system
- On optimal coverage of a tree with multiple robots
- Adaptive synchronization of multi-agent systems with resilience to communication link faults
- Computing without communicating: ring exploration by asynchronous oblivious robots
- Optimal Byzantine-resilient convergence in uni-dimensional robot networks
Cites work
- scientific article; zbMATH DE number 1748532 (Why is no real title available?)
- scientific article; zbMATH DE number 1748533 (Why is no real title available?)
- Algorithmic Number Theory
- Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
- Hardness results and spectral techniques for combinatorial problems on circulant graphs
- New results in the packing of equal circles in a square
- On fence patrolling by mobile agents
- Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling
- View-obstruction problems
Cited in
(5)- Connectivity and stochastic robustness of synchronized multi-drone systems
- Failure and communication in a synchronized multi-drone system
- On the robustness of a synchronized multi-robot system
- Stochastic strategies for patrolling a terrain with a synchronized multi-robot system
- On optimal coverage of a tree with multiple robots
This page was built for publication: Computing the \(k\)-resilience of a synchronized multi-robot system
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q721922)
