Optimization and search
Lyn C. Thomas · 2002
Search theory consists of models and optimization algorithms to find the best way to search for hidden targets. The difficulty of optimizing the search path is related to the motion, if any, of the target. If the target is stationary, the main optimal search problems have been essentially solved, as is outlined in Stone's classic text, while if the target's motion is much slower than the searcher's motion-search density problem-solution algorithms based on necessary conditions for optimality were developed in the early 80's. After reviewing briefly these results, the paper concentrates on two cases-where the target's motion is random and about the same speed as the searcher's motion and when the target is intelligent, where no satisfactory solution algorithms exist. Approaches based on partially observable Markov decision processes and on stochastic games to these problems are very attractive, but in order to obtain computationally feasible algorithms one has to introduce heuristic approximations or simplifying bounds.>