Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots - Publikacja - MOST Wiedzy


Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots


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.


  • 2


  • 0

    Web of Science

  • 0


Informacje szczegółowe

publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
Algorithms for Sensor Systems strony 1 - 12
Rok wydania:
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
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-319-72751-6_1

wyświetlono 5 razy

Publikacje, które mogą cię zainteresować

Meta Tagi