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

Wyszukiwarka

Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots

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)

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 69 razy

Publikacje, które mogą cię zainteresować

Meta Tagi