A Heuristic for Discrete Search Problems with Positive Switch Costs
Abstract
A searcher is looking for a stationary target which is not attempting to avoid detection. The target is in one location of a finite set, I, of locations (cells). An object is hidden in one of n cells according to a known probability distribution Pp...Pn. A search policy S is a sequence of cells to be visited and searched in an attempt to find the target. The probability of overlooking the target if we search cell i and if the target is in cell j is a(l). The cost of searching cell i is Cj. The cost of moving, or switching, from cell j to cell i is m(u). An optimal policy, s(*), is one for which the expected cost of finding the target is a minimum. When all m(u) = 0 the problem has a well known solution. The problem with positive m(u) is NP-hard and there is not an easy solution. We provide a heuristic to construct a search policy, s', which is good, but is not guaranteed to be optimal. The heuristic is an extension of the optimal solution for the problem with zero switching costs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1992
- Accession Number
- ADA251115
Entities
People
- Stephen R. Riese
Organizations
- Kansas State University