On the unsolvability of problems of guaranteed search in a sufficiently large domain
Let two point players (a searcher and an evader) move in the plane. Denote their states at time \(t\) as \(S(t)\) and \(H(t)\), respectively. The evader is considered to be detected if the inequality \(|S(t)- H(t)|\leq r\) (\(r\) is the radius of detection) is true. The article shows the existence of insoluble problems of monitoring and detection. Both problems are designated as \((Q, \omega, r\)) where \(Q\) is a bounded set on the plane. It is supposed that the trajectories of the two players satisfy the following constraints \[ |S(t_1) - S(t_2)|\leq |t_1 - t_2 |, \quad |H(t_1)- H(t_2)|\leq \omega |t_1 - t_2 |, \quad 0<\omega<1. \tag{1} \] It is proved that the problem of detection is insoluble if the maximum of a so called perimeter function of the set \(Q\) satisfies an inequality.
- On some problems of guaranteed search
- On the unimprovability of full-memory strategies in problems of guaranteed result optimization
- On some problems of guaranteed search on graphs
- scientific article; zbMATH DE number 18757
- On a class of optimization problems with no ``efficiently computable solution
- More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case
- Combinatorial dominance guarantees for problems with infeasible solutions
- More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case
- scientific article; zbMATH DE number 2085252
This page was built for publication: On the unsolvability of problems of guaranteed search in a sufficiently large domain
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5954768)
