Elements of the Optimal Search Problem
Lawrence Stone defined the elements of the optimal search problem in his 1986 book, Theory of Optimal Search.
This was paraphrased extremely well by Cooper, Frost and Robe in their 2003 report – Compatibility of Land SAR Procedures with Search Theory as quoted below;
A probability density distribution on search object location and state (so the probability of containment, POC (a.k.a. POA for “probability of area”), for any subset of the possible locations and states can be estimated),
A detection function relating the probability of detecting (POD) the object if it is in a searched area to the density of the searching effort expended there,
A known finite amount of available searching effort, and
An optimization criterion of maximizing probability of finding the object in a desirable state (probability of success or POS) subject to the constraint on effort availability.
I will endeavour to simplify further. In order to need and/or use the mathematics of search theory you require four essential elements.
- The ability to predict the likelihood that an object is in any particular search area or region. This might be done using sophisticated computer software working with the latest missing person behaviour statistics, or could be as simple as a coming up with a consensus within the search planning team.
- The ability to calculate the likelihood a given search resource will have of finding the object if it in the area being searched – unfortunately we can’t ask how many clues would you have found! [See my definition of POD for a brief explanation of why]
- A limited but known amount of search resource – when do you ever get too much search resource?
- A method of calculating the best way to use the search resource to maximise the chances of finding the search object as quickly as possible.
I’ll look in detail at each of these in further posts.
January 19, 2010
· 
Robert Bradley · 
2 Comments
Tags: Compatibility of Land SAR Procedures with Search Theory, Consensus, D Cooper, J Frost, Lawrence Stone, Missing Person Behaviour Statistics, Optimisation, POA, POC, POD, POS, Probability Density, Probability Density Distribution, Probability of Area, Probability of Detection, Probability of Success, R Quincy Robe, Search Effort, Search Planning, Search Resource, Search Theory, Theory of Optimal Search · Posted in: Search Research, Search Thoughts, Search Training
2 Responses
Apologies for the late comment on this. I haven’t read ‘Theory of Optimal Search’, so I may simply be restating what’s already said in there, but I think your point 4. is a restatement of what’s known as the ‘knapsack problem’ (I’m not sure why this never occured to me before).
This makes calculating 4 interesting from a computational perspective.
James,
If resources come in predefined chunks, then I believe it is a variant on the knapsack problem, which makes it combinatorial.
But if we allow ourselves to divide our resources arbitrarily, we can find optimal solutions quickly. There are algorithms for single and multiple resource types.
We can also use those unconstrained optimal solutions to guide the search to nearby feasible solutions, so we can get very good approximations without going fully combinatorial.
Leave a Reply