On-line Search in Two-Dimensional Environment - Publikacja - MOST Wiedzy

Wyszukiwarka

On-line Search in Two-Dimensional Environment

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

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

Publikacje, które mogą cię zainteresować

Meta Tagi