Wyszukiwarka
Abstrakt
We consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph that is guaranteed to be free of the fugitive is connected and whenever some node gains a property that it cannot be occupied by the fugitive, the strategy must operate in such a way to keep this property till its end. As a way of modeling two-dimensional shapes, we restrict our attention to networks that are embedded into partial grids: nodes are placed on the plane at integer coordinates and only nodes at distance one can be adjacent. Agents do not have any knowledge about the graph a priori, but they recognize the direction of the incident edge (up, down, left or right). We give an on-line algorithm for the searchers that allows them to compute a connected and monotone strategy that guarantees searching any unknown partial grid with the use of (√) searchers, where n is the number of nodes in the grid. As for a lower bound, there exist partial grids that require (√) searchers. Moreover, we prove that for each on-line searching algorithm there is a partial grid that forces the algorithm to use (√) searchers but (log) searchers are sufficient in the off-line scenario. This gives a lower bound on (√/log) in terms of achievable competitive ratio of any on-line algorithm.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (2)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00224-019-09948-6
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
THEORY OF COMPUTING SYSTEMS
nr 63,
strony 1819 - 1848,
ISSN: 1432-4350 - Język:
- angielski
- Rok wydania:
- 2019
- Opis bibliograficzny:
- Dereniowski D., Osula D.: On-line Search in Two-Dimensional Environment// THEORY OF COMPUTING SYSTEMS -Vol. 63,iss. 8 (2019), s.1819-1848
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00224-019-09948-6
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 135 razy
Publikacje, które mogą cię zainteresować
How to meet when you forget: log-space rendezvous in arbitrary graphs
- J. Czyzowicz,
- A. Kosowski,
- A. Pelc
Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs
- S. Das,
- D. Dereniowski,
- A. Kosowski
- + 1 autorów