Optimal Patrolling of Fragmented Boundaries

Andrew Collins; Jurek Czyzowicz; Leszek Gasieniec; Adrian Kosowski; Evangelos Kranakis; Danny Krizanc; Russell Martin; Oscar Morales Ponce

hal-00686270, version 2

Optimal Patrolling of Fragmented Boundaries

Andrew Collins ¹, Jurek Czyzowicz () ², Leszek Gasieniec ¹, Adrian Kosowski (, ) ³, Evangelos Kranakis ⁴, Danny Krizanc ⁵, Russell Martin ¹, Oscar Morales Ponce ⁴

1: Department of Computer Science [Liverpool]
http://www.csc.liv.ac.uk/
University of Liverpool Ashton Building, Ashton Street Liverpool, L69 3BX United Kingdom United Kingdom
2: Département d'Informatique et d'Ingénierie (DII)
http://w4.uqo.ca/dii/index.php
Université du Québec en Outaouais 101, Saint-Jean-Bosco, C.P. 1250, succursale Hull, Gatineau (Québec) Canada, J8X 3X7 Canada
3: CEPAGE (INRIA Bordeaux - Sud-Ouest)
INRIA – CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) France
4: Network Research Group, School of Computer Science
Carleton University Canada
5: Department of Mathematics and Computer Science
http://www.math.wesleyan.edu/
Wesleyan University Department of Mathematics and Computer Science Wesleyan University, Science Tower 655 265 Church St. Middletown, CT 06459-0128 USA United States

Available versions : v1 (2012-04-09) v2 (2012-04-23)

Bibliographic reference

Attached file list to this document:

TEX

biblio.bib

(12.7 KB)

vn.tex

(68.3 KB)

PDF

vn.pdf

(232.2 KB)

vn.ps

(541.4 KB)

hal-00686270, version 2
http://hal.inria.fr/hal-00686270
oai:hal.inria.fr:hal-00686270
From: Adrian Kosowski <>
Submitted on: Sunday, 22 April 2012 23:53:49
Updated on: Monday, 23 April 2012 12:21:46

See short view

Associated documents

PDF :

PS :

Export

Bibtex EndNote TEI RefWorks

%% hal-00686270, version 2
%% http://hal.inria.fr/hal-00686270
@unpublished{collins:hal-00686270,
    hal_id = {hal-00686270},
    url = {http://hal.inria.fr/hal-00686270},
    title = {{Optimal Patrolling of Fragmented Boundaries}},
    author = {Collins, Andrew and Czyzowicz, Jurek and Gasieniec, Leszek and Kosowski, Adrian and Kranakis, Evangelos and Krizanc, Danny and Martin, Russell and Morales Ponce, Oscar},
    abstract = {{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 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].}},
    keywords = {mobile agents; idleness; boundary patrolling; cycle},
    language = {English},
    affiliation = {Department of Computer Science [Liverpool] , D{\'e}partement d'Informatique et d'Ing{\'e}nierie - DII , CEPAGE - INRIA Bordeaux - Sud-Ouest , Network Research Group, School of Computer Science , Department of Mathematics and Computer Science},
    pdf = {http://hal.inria.fr/hal-00686270/PDF/vn.pdf},
}

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Documents without publication reference (Preprint)</head>
<biblStruct type="article" xml:id="hal-00686270"><analytic>
<author><persName><forename>Andrew</forename><surname>Collins</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science [Liverpool]</orgName>
<country>GB</country>
<orgName type="institution">University of Liverpool</orgName>
</affiliation>
</author>
<author><persName><forename>Jurek</forename><surname>Czyzowicz</surname></persName>
<affiliation>
<orgName type="laboratory">DII</orgName>
<orgName type="team">Département d'Informatique et d'Ingénierie</orgName>
<country>CA</country>
<orgName type="institution">Université du Québec en Outaouais</orgName>
</affiliation>
</author>
<author><persName><forename>Leszek</forename><surname>Gasieniec</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science [Liverpool]</orgName>
<country>GB</country>
<orgName type="institution">University of Liverpool</orgName>
</affiliation>
</author>
<author><persName><forename>Adrian</forename><surname>Kosowski</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">CEPAGE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
</affiliation>
</author>
<author><persName><forename>Evangelos</forename><surname>Kranakis</surname></persName>
<affiliation>
<orgName type="team">Network Research Group, School of Computer Science</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<author><persName><forename>Danny</forename><surname>Krizanc</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics and Computer Science</orgName>
<country>US</country>
<orgName type="institution">Wesleyan University</orgName>
</affiliation>
</author>
<author><persName><forename>Russell</forename><surname>Martin</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science [Liverpool]</orgName>
<country>GB</country>
<orgName type="institution">University of Liverpool</orgName>
</affiliation>
</author>
<author><persName><forename>Oscar</forename><surname>Morales Ponce</surname></persName>
<affiliation>
<orgName type="team">Network Research Group, School of Computer Science</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<title type="main" level="a">Optimal Patrolling of Fragmented Boundaries</title></analytic><monogr><imprint/></monogr><idno type="HALid">http://hal.inria.fr/hal-00686270</idno><idno type="HALFile">http://hal.inria.fr/hal-00686270/PDF/vn.pdf</idno></biblStruct>
</listBibl>
</listBibl>