Search
Abstract
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.
Citations
-
3
CrossRef
-
0
Web of Science
-
7
Scopus
Authors (4)
-
Evangelos Bampas
- Aix-Marseille University and CNRS
-
Shantanu Das
- Aix-Marseille University and CNRS
-
Christina Karousatou
- Aix-Marseille University and CNRS
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Monographic publication
- Type:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Title of issue:
- Algorithms for Sensor Systems strony 1 - 12
- Language:
- English
- Publication year:
- 2017
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1007/978-3-319-72751-6_1
- Verified by:
- Gdańsk University of Technology
seen 112 times
Recommended for you
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
- R. Klasing,
- A. Kosowski,
- A. Navarra
Deterministic Rendezvous in Restricted Graphs
- A. Farrugia,
- L. Gąsieniec,
- Ł. Kuszner
- + 1 authors