Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Collaborative Exploration by Energy-Constrained Mobile Robots
verfasst von : Shantanu Das, Dariusz Dereniowski, Christina Karousatou
Erschienen in: Structural Information and Communication Complexity
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
We study the problem of exploration of a tree by mobile agents (robots) that have limited energy. The energy constraint bounds the number of edges that can be traversed by a single agent. Thus we need a team of agents to completely explore the tree and the objective is to minimize the size of this team. The agents start at a single node, the designated root of the tree and the height of the tree is bounded by the energy bound
B
. We provide an exploration algorithm without any knowledge about the tree and we compare our algorithm with the optimal offline algorithm that has complete knowledge of the tree. Our algorithm has a competitive ratio of
O
(log
B
), independent of the number of nodes in the tree. We also show that this is the best possible competitive ratio for exploration of unknown trees.