Show simple item record

Optimal Patrolling of Fragmented Boundaries

hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorCOLLINS, Andrew
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorGASIENIEC, Leszek
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierSchool of Computer Science (Carleton, Ottawa)
dc.contributor.authorKRANAKIS, Evangelos
hal.structure.identifierDepartment of Mathematics and Computer Science
dc.contributor.authorKRIZANC, Danny
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorMARTIN, Russell
hal.structure.identifierSchool of Computer Science (Carleton, Ottawa)
dc.contributor.authorMORALES PONCE, Oscar
dc.date.accessioned2024-04-15T09:42:44Z
dc.date.available2024-04-15T09:42:44Z
dc.date.issued2013
dc.date.conference2013
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197705
dc.description.abstractEnA 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 idleness, 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 idleness. 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].
dc.language.isoen
dc.publisherACM
dc.subject.enmobile agents
dc.subject.enidleness
dc.subject.enboundary patrolling
dc.subject.encycle
dc.title.enOptimal Patrolling of Fragmented Boundaries
dc.typeCommunication dans un congrès
dc.identifier.doi10.1145/2486159.2486176
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page241-250
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSPAA - 25th Symposium on Parallelism in Algorithms and Architectures
bordeaux.countryCA
bordeaux.conference.cityMontreal
bordeaux.peerReviewedoui
hal.identifierhal-00686270
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00686270v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2013&rft.spage=241-250&rft.epage=241-250&rft.au=COLLINS,%20Andrew&CZYZOWICZ,%20Jurek&GASIENIEC,%20Leszek&KOSOWSKI,%20Adrian&KRANAKIS,%20Evangelos&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record