Mathematics of Information Technology and Complex Systems

Project Highlights
Team Members
Partner Organizations
Seminar Series

Project Highlights

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 non-cooperative. 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 end-products of this phase must satisfy (i) end-user requirements, and (ii) small scale algorithmic feasibility, as well as provide comparison benchmarks for the next phase. In a full-scale project, we intend to further develop our models in two main directions: Algorithmic refinements extending our models’ scope to real-life problem instances and a large-scale implementation of our prototype with appropriate user interfaces. We will likely need to improve the efficiency of our algorithms.


This seed project is currently ongoing.


©2009 Université Laval