Wyszukiwarka
Abstrakt
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. We use a team of agents to collectively 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 assumed to be less than the energy bound B of the agents. The agents have local vision and communication capabilities; two agents can exchange information only when they are collocated at the same node. We provide an exploration algorithm for visiting all nodes of the unknown 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.
Cytowania
-
1 5
CrossRef
-
0
Web of Science
-
1 6
Scopus
Autorzy (3)
-
Shantanu Das
- Aix-Marseille University, CNRS LIF
-
Christina Karousatou
- Aix-Marseille University, CNRS LIF
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ł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
THEORY OF COMPUTING SYSTEMS
nr 62,
wydanie 5,
strony 1223 - 1240,
ISSN: 1432-4350 - Język:
- angielski
- Rok wydania:
- 2018
- Opis bibliograficzny:
- Das S., Dereniowski D., Karousatou C.: Collaborative Exploration of Trees by Energy-Constrained Mobile Robots// THEORY OF COMPUTING SYSTEMS. -Vol. 62, iss. 5 (2018), s.1223-1240
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00224-017-9816-3
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 117 razy