Posts Tagged ‘Optimisation’

Elements of the Optimal Search Problem

January 19th, 2010

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.

  1. 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.
  2. 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]
  3. A limited but known amount of search resource – when do you ever get too much search resource?
  4. 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.

  • Share/Bookmark

2 comments »

Posted in Search Research, Search Thoughts, Search Training

Tags:

What is Search Theory?

January 6th, 2010

I’ve alluded to Search Theory lots of times during the last couple of months, and have often been told that I am happy to “bore” anyone to death with such maths. So I thought it was about time to write a series on the maths of search theory and how it can [should?] be used by search teams looking for missing persons.

And I thought the best way to start would be to try to explain what search theory really is?

Search Theory sits in a branch of mathematics referred to as Operations Research.

It is about optimisation! Simply put, it is about getting the best possible outcome with the resources available.

I have often compared it to a silly game of dice. If I were to offer you odds on what number a dice would come up like these, what would be your best (optimum) strategy? 1 : 4-6 , 2 : Evens , 3 : 2-1 , 4 : 3-1 , 5 : 4-1 and 6 : 6-1

The answer to this is, of course, you would always bet on number 6. Now, you would not win every time. In fact, you would lose 5 times more than you would win in general. But you would win the most money of all the strategies. (If you are unsure of why, just try it out! Whilst the dice numbers should come up roughly as often as each other, the money you win on each differs with no. 6 giving the highest total.)

Search theory is a slightly more complicated version of this. You take a situation, in this case a missing person.

The misper could be anywhere, but some areas are more likely than others.
You are limited by having only a certain amount of search resource.
Time is also critical – in many cases the misper is dying as time goes by.

The mathematics of search theory takes these “variables” and works out an optimum use of the search resources. Like the dice game, you don’t win all the time – in fact like the dice game you tend to lose a lot more often than you win. BUT by using the maths of search theory you know that you are getting the best possible results – in this case saving the most lives and finding the most missing persons (instead of money as in the dice game)

In the later sections of the series I will discuss the history of search theory, before looking in detail at the various parts of calculating and using the maths.

  • Share/Bookmark

No comments »

Posted in Search Thoughts

Tags: