Wyszukiwarka
Abstrakt
We consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy based on locations of other agents in the graph, in order to minimize the total time needed for evacuation. We consider two scenarios: (i) the centralized (or offline) setting where the agents have full knowledge of initial positions of other agents, and (ii) the distributed (or online) setting where the agents do not have prior knowledge of the location of other agents but they can communicate locally with nearby agents and they must modify their strategy in an online fashion while they move and obtain more information. In the former case we present an offline polynomial time solution to compute the optimal strategy for evacuation of all agents. In the online case, we present a constant competitive algorithm when agents can communicate at distance two in the graph. We also show that when the agents are heterogeneous and each agent has access to only a subgraph of the original graph then computing the optimal strategy is NP-hard even with full global knowledge. This result holds even if there are only two types of agents.
Cytowania
-
7
CrossRef
-
0
Web of Science
-
1 3
Scopus
Autorzy (4)
-
Shantanu Das
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- materiały konferencyjne indeksowane w Web of Science
- Tytuł wydania:
- Structural Information and Communication Complexity strony 228 - 241
- Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Borowiecki P., Das S., Dereniowski D., Kuszner Ł..: Distributed Evacuation in Graphs with Multiple Exits, W: Structural Information and Communication Complexity, 2016, ,.
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-319-48314-6_15
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 177 razy
Publikacje, które mogą cię zainteresować
Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs
- S. Das,
- D. Dereniowski,
- A. Kosowski
- + 1 autorów