On-line Search in Two-Dimensional Environment

摘要

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. 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. 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 O({the square root of}n) searchers, where n is the number of nodes in the grid. We prove also a lower bound of Ω({the square root of}n/log n) in terms of achievable competitive ratio of any on-line algorithm.