On-line Search in Two-Dimensional Environment

Dariusz Dereniowski; Dorota Osula

doi:10.1007/s00224-019-09948-6

On-line Search in Two-Dimensional Environment

Abstract

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.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (2)

Cite as

Full text

download paper

downloaded 19 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1007/s00224-019-09948-6
License: open in new tab

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach
Published in:: THEORY OF COMPUTING SYSTEMS no. 63, pages 1819 - 1848,
ISSN: 1432-4350
Language:: English
Publication year:: 2019
Bibliographic description:: Dereniowski D., Osula D.: On-line Search in Two-Dimensional Environment// THEORY OF COMPUTING SYSTEMS -Vol. 63,iss. 8 (2019), s.1819-1848
DOI:: Digital Object Identifier (open in new tab) 10.1007/s00224-019-09948-6
Verified by:: Gdańsk University of Technology