Computing the k-resilience of a synchronized multi-robot system

DOI10.1007/S10878-018-0297-3zbMATH Open1421.90152arXiv1707.07083OpenAlexW2963505198WikidataQ129895233 ScholiaQ129895233MaRDI QIDQ721922FDOQ721922

Authors: L. E. Caraballo, Mario A. Lopez, Sergey Bereg, J. M. Díaz-Báñez 

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: We study an optimization problem that arises in the design of covering strategies for multi-robot systems. Consider a team of $n$ 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{$k$-resilience} as the minimum number of robots whose removal may cause $k$ surviving robots to enter a state of starvation. We show that the problem of computing the $k$-resilience is NP-hard if $k$ is part of the input, even if the communication graph is a tree. We propose algorithms to compute the $k$-resilience for constant values of $k$ in general communication graphs and show more efficient algorithms for systems whose communication graph is a tree.

Full work available at URL: https://arxiv.org/abs/1707.07083

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

zbMATH Keywords

synchronizationresiliencemulti-robot system

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Title not available (Why is that?)
• Algorithmic Number Theory
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• View-obstruction problems
• On fence patrolling by mobile agents
• New results in the packing of equal circles in a square
• Title not available (Why is that?)
• Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
• Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling

Cited In (5)

• 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
• Connectivity and stochastic robustness of synchronized multi-drone systems

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)