Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Why Robots Need Maps
verfasst von : Miroslaw Dynia, Jakub Łopuszański, Christian Schindelhauer
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
Ω
(log
k
/loglog
k
) 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.