Afficher la notice abrégée

Patrolling by Robots Equipped with Visibility

hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierSchool of Computer Science [Ottawa]
dc.contributor.authorKRANAKIS, Evangelos
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorPAJAK, Dominik
hal.structure.identifierSchool of Computer Science [Ottawa]
dc.contributor.authorTALEB, Najmeh
dc.contributor.editorMagnús M. Halldórsson
dc.date.accessioned2024-04-04T02:17:13Z
dc.date.available2024-04-04T02:17:13Z
dc.date.issued2014-07-23
dc.date.conference2014-07-23
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189208
dc.description.abstractEnWe study the problem of mobile robots with distinct visibility ranges patrolling a curve. Assume a set of $k$ mobile robots (patrolmen) $a_1, a_2,..., a_k$ walking along a unit-length curve in any of the two directions, not exceeding their maximal speeds. Every robot $a_i$ has a range of visibility $r_i$, representing the distance from its current position at which the robot can see in each direction along the curve. The goal of the patrolling problem is to find the perpetual movement of the robots minimizing the maximal time when a point of the curve remains unseen by any robot. We give the optimal patrolling algorithms for the case of close curve environment (known as the boundary patrolling problem in the robotics literature) and open curve (fence patrolling), when all robots have the same maximal speed. We briefly discuss the case of distinct speeds, showing that the boundary patrolling problem for robots with distinct visibility ranges is essentially different than the case of point visibility robots. We also give the optimal algorithm for fence patrolling by two robots with distinct speeds and visibility ranges. For the case when the environment in which the robots operate is a general graph, we show that the patrolling problem for robots with distinct visibility ranges is NP-hard, while it is known that the same problem for point-visibility robots has been known to have a polynomial-time solution.
dc.language.isoen
dc.publisherSpringer
dc.title.enPatrolling by Robots Equipped with Visibility
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-319-09620-9_18
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page224-234
bordeaux.volume8576
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSIROCCO - 21th International Colloquium on Structural Information and Communication Complexity
bordeaux.countryJP
bordeaux.conference.cityHida Takayama
bordeaux.peerReviewedoui
hal.identifierhal-00996773
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2014-07-25
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00996773v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2014-07-23&rft.volume=8576&rft.spage=224-234&rft.epage=224-234&rft.au=CZYZOWICZ,%20Jurek&KRANAKIS,%20Evangelos&PAJAK,%20Dominik&TALEB,%20Najmeh&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée