When Patrolmen Become Corrupted: Monitoring a Graph using Faulty Mobile Robots

Abstract : A team of k mobile robots is deployed on a weighted graph whose edge weights represent distances. The robots perpetually move along the domain, represented by all points belonging to the graph edges, not exceeding their maximal speed. The robots need to patrol the graph by regularly visiting all points of the domain. In this paper, we consider a team of robots (patrolmen), at most f of which may be unreliable, i.e. they fail to comply with their patrolling duties. What algorithm should be followed so as to minimize the maximum time between successive visits of every edge point by a reliable patrolmen? The corresponding measure of efficiency of patrolling called idleness has been widely accepted in the robotics literature. We extend it to the case of untrusted patrolmen; we denote by Ifk (G) the maximum time that a point of the domain may remain unvisited by reliable patrolmen. The objective is to find patrolling strategies minimizing Ifk (G). We investigate this problem for various classes of graphs. We design optimal algorithms for line segments, which turn out to be surprisingly different from strategies for related patrolling problems proposed in the literature. We then use these results to study the case of general graphs. For Eulerian graphs G, we give an optimal patrolling strategy with idleness Ifk (G) = (f + 1)|E|/k, where |E| is the sum of the lengths of the edges of G. Further, we show the hardness of the problem of computing the idle time for three robots, at most one of which is faulty, by reduction from 3-edge-coloring of cubic graphs — a known NP-hard problem. A byproduct of our proof is the investigation of classes of graphs minimizing idle time (with respect to the total length of edges); an example of such a class is known in the literature under the name of Kotzig graphs.
Type de document :
Communication dans un congrès
26th International Symposium on Algorithms and Computation (ISAAC 2015), Proceedings, Dec 2015, Nagoya, Japan. 9472, pp.343-354, Lecture Notes in Computer Science. 〈10.1007/978-3-662-48971-0_30〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194847
Contributeur : Adrian Kosowski <>
Soumis le : lundi 7 septembre 2015 - 16:15:47
Dernière modification le : jeudi 15 novembre 2018 - 20:27:23
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:14:53

Fichier

fp.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Collections

Relations

Citation

Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc, et al.. When Patrolmen Become Corrupted: Monitoring a Graph using Faulty Mobile Robots. 26th International Symposium on Algorithms and Computation (ISAAC 2015), Proceedings, Dec 2015, Nagoya, Japan. 9472, pp.343-354, Lecture Notes in Computer Science. 〈10.1007/978-3-662-48971-0_30〉. 〈hal-01194847〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

229