Why Robots Need Maps
Identifieur interne : 004341 ( Istex/Curation ); précédent : 004340; suivant : 004342Why Robots Need Maps
Auteurs : Miroslaw Dynia [Allemagne] ; Jakub Łopusza Ski [Pologne] ; Christian Schindelhauer [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2007.
Abstract
Abstract: A large group of autonomous, mobile entities e.g. robots initially placed at some arbitrary node of the graph has to jointly visit all nodes (not necessarily all edges) and finally return to the initial position. The graph is not known in advance (an online setting) and robots have to traverse an edge in order to discover new parts (edges) of the graph. The team can locally exchange information, using wireless communication devices. We compare a cost of the online and optimal offline algorithm which knows the graph beforehand (competitive ratio). If the cost is the total time of an exploration, we prove the lower bound of Ω(logk /loglogk) for competitive ratio of any deterministic algorithm (using global communication). This significantly improves the best known constant lower bound. For the cost being the maximal number of edges traversed by a robot (the energy) we present an improved (4 − 2/k)-competitive online algorithm for trees.
Url:
DOI: 10.1007/978-3-540-72951-8_5
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :004341
Links to Exploration step
ISTEX:ACB897A2DD40174A6CB40B97A735579E326F2A97Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Why Robots Need Maps</title><author><name sortKey="Dynia, Miroslaw" sort="Dynia, Miroslaw" uniqKey="Dynia M" first="Miroslaw" last="Dynia">Miroslaw Dynia</name><affiliation wicri:level="1"><mods:affiliation>DFG Graduate College ”Automatic Configuration in Open Systems”, University of Paderborn, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>DFG Graduate College ”Automatic Configuration in Open Systems”, University of Paderborn</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: mdynia@uni-paderborn.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Lopusza Ski, Jakub" sort="Lopusza Ski, Jakub" uniqKey="Lopusza Ski J" first="Jakub" last="Łopusza Ski">Jakub Łopusza Ski</name><affiliation wicri:level="1"><mods:affiliation>Institute of Computer Science, University of Wroclaw, Poland</mods:affiliation><country xml:lang="fr">Pologne</country><wicri:regionArea>Institute of Computer Science, University of Wroclaw</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: jakub.lopuszanski@ii.uni.wroc.pl</mods:affiliation><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Schindelhauer, Christian" sort="Schindelhauer, Christian" uniqKey="Schindelhauer C" first="Christian" last="Schindelhauer">Christian Schindelhauer</name><affiliation wicri:level="1"><mods:affiliation>Computer Networks and Telematics, University of Freiburg, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>Computer Networks and Telematics, University of Freiburg</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: schindel@informatik.uni-freiburg.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:ACB897A2DD40174A6CB40B97A735579E326F2A97</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1007/978-3-540-72951-8_5</idno><idno type="url">https://api.istex.fr/document/ACB897A2DD40174A6CB40B97A735579E326F2A97/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">004341</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">004341</idno><idno type="wicri:Area/Istex/Curation">004341</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Why Robots Need Maps</title><author><name sortKey="Dynia, Miroslaw" sort="Dynia, Miroslaw" uniqKey="Dynia M" first="Miroslaw" last="Dynia">Miroslaw Dynia</name><affiliation wicri:level="1"><mods:affiliation>DFG Graduate College ”Automatic Configuration in Open Systems”, University of Paderborn, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>DFG Graduate College ”Automatic Configuration in Open Systems”, University of Paderborn</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: mdynia@uni-paderborn.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Lopusza Ski, Jakub" sort="Lopusza Ski, Jakub" uniqKey="Lopusza Ski J" first="Jakub" last="Łopusza Ski">Jakub Łopusza Ski</name><affiliation wicri:level="1"><mods:affiliation>Institute of Computer Science, University of Wroclaw, Poland</mods:affiliation><country xml:lang="fr">Pologne</country><wicri:regionArea>Institute of Computer Science, University of Wroclaw</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: jakub.lopuszanski@ii.uni.wroc.pl</mods:affiliation><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Schindelhauer, Christian" sort="Schindelhauer, Christian" uniqKey="Schindelhauer C" first="Christian" last="Schindelhauer">Christian Schindelhauer</name><affiliation wicri:level="1"><mods:affiliation>Computer Networks and Telematics, University of Freiburg, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>Computer Networks and Telematics, University of Freiburg</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: schindel@informatik.uni-freiburg.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2007</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">ACB897A2DD40174A6CB40B97A735579E326F2A97</idno><idno type="DOI">10.1007/978-3-540-72951-8_5</idno><idno type="ChapterID">5</idno><idno type="ChapterID">Chap5</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A large group of autonomous, mobile entities e.g. robots initially placed at some arbitrary node of the graph has to jointly visit all nodes (not necessarily all edges) and finally return to the initial position. The graph is not known in advance (an online setting) and robots have to traverse an edge in order to discover new parts (edges) of the graph. The team can locally exchange information, using wireless communication devices. We compare a cost of the online and optimal offline algorithm which knows the graph beforehand (competitive ratio). If the cost is the total time of an exploration, we prove the lower bound of Ω(logk /loglogk) for competitive ratio of any deterministic algorithm (using global communication). This significantly improves the best known constant lower bound. For the cost being the maximal number of edges traversed by a robot (the energy) we present an improved (4 − 2/k)-competitive online algorithm for trees.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004341 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 004341 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:ACB897A2DD40174A6CB40B97A735579E326F2A97
|texte= Why Robots Need Maps
}}
| This area was generated with Dilib version V0.6.31. |  |