Background and History
Search
theory was one of
the earliest OR problems studied in the United States. As described in
Stone (1980), the problem of optimal search begins with a search object
that the searcher wishes to find. The search space may be continuous or
discrete. Time may be continuous or discrete. A probability
distribution on the location of the search object is assumed. There is
also a detection function that yields a probability of detecting the
object as a function of the effort (resources) spent in an area or in a
cell containing the object. The search object may be stationary or
moving, cooperative or noncooperative. Search effort may be discrete
or continuous. There can be a single searcher or multiple searchers.
Usually, the objective of an optimal search is to maximize some measure
of effectiveness with some constraint imposed on the amount of search
effort available.
The search problem may be divided into two categories: Optimal search
density problems (search effort allocation) and optimal searcher path
problems. The first category corresponds to a situation where search
effort can be divided infinitely. When the location of search effort at
one time constrains the location of effort at a later time, we have an
optimal searcher path problem. The effort
allocation problem for stationary targets and a single searcher under
idealized assumptions and a single criterion can be considered solved
(Koopman, 1980). Stone (1980) extended the results to most of the
standard cases. However, it is important to stress that the optimal
theoretical plan is not necessarily a feasible plan. Many researchers
have worked on the on the optimal effort allocation problem or the
optimal searcher path problem with moving targets and a single
searcher.
Further research is needed to extend the algorithms to a multiple
searcher and multicriteria context in order to generate operationally
feasible plans that are near optimal.
Current Activities
In
the seed
project phase of this research, we will concentrate on prototyping and
proof of concept. We will test the possibility of using multiple
criteria on a smaller scale and validate our results on real data by
evaluating the added benefits of our approach. A large portion of our
efforts at this stage will be devoted to modelling issues. The
endproducts of this phase must satisfy (i) enduser requirements, and
(ii) small scale algorithmic feasibility, as well as provide comparison
benchmarks for the next phase. In a fullscale project, we intend to
further develop our models in two main directions: Algorithmic
refinements extending our models’ scope to reallife problem
instances and a largescale implementation of our prototype with
appropriate user interfaces. We will likely need to improve the
efficiency of our algorithms.
Status
This seed
project is currently ongoing.
