Constructing a map of an anonymous graph: applications of universal sequences - Publikacja - MOST Wiedzy

Wyszukiwarka

Constructing a map of an anonymous graph: applications of universal sequences

Abstrakt

We study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria is to minimize the amount of information that the robot has to carry when moving from node to node in the graph. We present efficient algorithms for solving map construction using a robot that is not allowed to mark any vertex of the graph, assuming the knowledge of only an upper bound on the size of the graph. We also give universal algorithms (independent of the size of the graph) for map construction when only the starting location of the robot is marked. Our solutions apply the technique of universal exploration sequences to solve the map construction problem under various constraints. We also show how the solution can be adapted to solve other problems such as the gathering of two identical robots dispersed in an unknown graph.

Cytowania

  • 2 7

    CrossRef

  • 0

    Web of Science

  • 5 2

    Scopus

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Opublikowano w:
LECTURE NOTES IN COMPUTER SCIENCE nr 6490, strony 119 - 134,
ISSN: 0302-9743
Język:
angielski
Rok wydania:
2010
Opis bibliograficzny:
Chalopin J., Das S., Kosowski A.: Constructing a map of an anonymous graph: applications of universal sequences// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6490., (2010), s.119-134
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-642-17653-1_10
Weryfikacja:
Politechnika Gdańska

wyświetlono 149 razy

Publikacje, które mogą cię zainteresować

Meta Tagi