How many oblivious robots can explore a line

Paola Flocchini; David Ilcinkas; Andrzej Pelc; Nicola Santoro

hal-00643668, version 1

How many oblivious robots can explore a line

Paola Flocchini () ¹, David Ilcinkas (, ) ^2, 3, Andrzej Pelc () ⁴, Nicola Santoro () ⁵

Information Processing Letters 111, 20 (2011) 1027-1031

Résumé : We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a n-node line. For k= 5, or k=4 and n is odd. For all values of k for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.

1 : School of Information Technology and Engineering [Ottawa] (SITE)
University of Ottawa
2 : Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
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)
4 : Département d'Informatique et d'Ingénierie (DII)
Université du Québec en Outaouais
5 : School of Computer Science
Carleton University

hal-00643668, version 1
http://hal.archives-ouvertes.fr/hal-00643668
oai:hal.archives-ouvertes.fr:hal-00643668
Contributeur : David Ilcinkas <>
Soumis le : Mardi 22 Novembre 2011, 15:22:50
Dernière modification le : Mardi 22 Novembre 2011, 15:41:19

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1016/j.ipl.2011.07.018

Exporter

Bibtex EndNote TEI RefWorks

<?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>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00643668"><analytic>
<author><persName><forename>Paola</forename><surname>Flocchini</surname></persName>
<affiliation>
<orgName type="laboratory">SITE</orgName>
<orgName type="team">School of Information Technology and Engineering [Ottawa]</orgName>
<country>CA</country>
<orgName type="institution">University of Ottawa</orgName>
</affiliation>
</author>
<author><persName><forename>David</forename><surname>Ilcinkas</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<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>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
<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>Andrzej</forename><surname>Pelc</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>Nicola</forename><surname>Santoro</surname></persName>
<affiliation>
<orgName type="team">School of Computer Science</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<title type="main" level="a">How many oblivious robots can explore a line</title></analytic><monogr><title level="j" type="main">Information Processing Letters</title><imprint><biblScope type="publicationDate">2011-10-31</biblScope><biblScope type="vol">111</biblScope><biblScope type="issue">20</biblScope><biblScope type="pp">1027-1031</biblScope></imprint></monogr><idno type="doi">10.1016/j.ipl.2011.07.018</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00643668</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00643668/PDF/final_IPL.pdf</idno></biblStruct>
</listBibl>
</listBibl>