Wyszukiwarka
Abstrakt
We study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one unit and the robot can only perform such move initially having at least one unit of energy. There are two distinguished nodes s and t in the graph and the goal for the robots is to deliver the package initially present on s to the node t. The package can be passed from one robot to another when they are colocated. In the first problem we study, the robots are initially placed at some given nodes of the graph and the question is whether the delivery is feasible. We prove that this problem is NP-complete. In the second problem, the initial positions of the robots are not fixed but a subset of nodes H of the graph is given as input together with an integer k, and the question is as follows: is there a placement of k robots at nodes in H such that the delivery is possible? We prove that this problem can be solved in polynomial time.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
7
Scopus
Autorzy (4)
-
Evangelos Bampas
- Aix-Marseille University and CNRS
-
Shantanu Das
- Aix-Marseille University and CNRS
-
Christina Karousatou
- Aix-Marseille University and CNRS
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja monograficzna
- Typ:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Tytuł wydania:
- Algorithms for Sensor Systems strony 1 - 12
- Język:
- angielski
- Rok wydania:
- 2017
- Opis bibliograficzny:
- Bampas E., Das S., Dereniowski D., Karousatou C.: Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots// Algorithms for Sensor Systems/ ed. Fernández Anta A., Jurdzinski T., Mosteiro M., Zhang Y. : Springer, 2017, s.1-12
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-319-72751-6_1
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 112 razy
Publikacje, które mogą cię zainteresować
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
- R. Klasing,
- A. Kosowski,
- A. Navarra
Collaborative Exploration of Trees by Energy-Constrained Mobile Robots
- S. Das,
- D. Dereniowski,
- C. Karousatou