Optimal Patrolling of Fragmented Boundaries - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2012

Optimal Patrolling of Fragmented Boundaries

Résumé

A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their maximum speed. The quality of patrolling is measured by the idle time, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idle time. Our main contribution is a proof that the optimal solution to the patrolling problem is attained either by the cyclic strategy, in which all the robots move in one direction around the curve, or by the partition strategy, in which the curve is partitioned into sections which are patrolled separately by individual robots. These two fundamental types of strategies were studied in the past in the robotics community in different theoretical and experimental settings. However, to our knowledge, this is the first theoretical analysis proving optimality in such a general scenario. Throughout the paper we assume that all robots have the same maximum speed. In fact, the claim is known to be invalid when this assumption does not hold, cf. [Czyzowicz et al., Proc. ESA 2011].
Fichier principal
Vignette du fichier
vn.pdf (293.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00686270 , version 1 (09-04-2012)
hal-00686270 , version 2 (22-04-2012)
hal-00686270 , version 3 (09-10-2013)

Identifiants

  • HAL Id : hal-00686270 , version 1

Citer

Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, et al.. Optimal Patrolling of Fragmented Boundaries. 2012. ⟨hal-00686270v1⟩
351 Consultations
489 Téléchargements

Partager

Gmail Facebook X LinkedIn More