Bayesian search theory

Bayesian search theory is the application of Bayesian statistics to the search for lost objects. It has been
used several times to find lost sea vessels, for example USS Scorpion, and has played a key role in the
recovery of the flight recorders in the Air France Flight 447 disaster of 2009. It has also been used in the
attempts to locate the remains of Malaysia Airlines Flight 370.[1][2][3]

Procedure
The usual procedure is as follows:

1. Formulate as many reasonable hypotheses as possible about what may have happened to the object.
2. For each hypothesis, construct a probability density function for the location of the object.
3. Construct a function giving the probability of actually finding an object in location X when searching there
if it really is in location X. In an ocean search, this is usually a function of water depth — in shallow water
chances of finding an object are good if the search is in the right place. In deep water chances are
reduced.
4. Combine the above information coherently to produce an overall probability density map. (Usually this
simply means multiplying the two functions together.) This gives the probability of finding the object by
looking in location X, for all possible locations X. (This can be visualized as a contour map of probability.)
5. Construct a search path which starts at the point of highest probability and 'scans' over high probability
areas, then intermediate probabilities, and finally low probability areas.
6. Revise all the probabilities continuously during the search. For example, if the hypotheses for location X
imply the likely disintegration of the object and the search at location X has yielded no fragments, then
the probability that the object is somewhere around there is greatly reduced (though not usually to zero)
while the probabilities of its being at other locations is correspondingly increased. The revision process is
done by applying Bayes' theorem.

In other words, first search where it most probably will be found, then search where finding it is less
probable, then search where the probability is even less (but still possible due to limitations on fuel, range,
water currents, etc.), until insufficient hope of locating the object at acceptable cost remains.

The advantages of the Bayesian method are that all information available is used coherently (i.e., in a "leak-
proof" manner) and the method automatically produces estimates of the cost for a given success probability.
That is, even before the start of searching, one can say, hypothetically, "there is a 65% chance of finding it in a
5-day search. That probability will rise to 90% after a 10-day search and 97% after 15 days" or a similar
statement. Thus the economic viability of the search can be estimated before committing resources to a
search.

Apart from the USS Scorpion, other vessels located by Bayesian search theory include the MV Derbyshire,
the largest British vessel ever lost at sea, and the SS Central America. It also proved successful in the search
for a lost hydrogen bomb following the 1966 Palomares B-52 crash in Spain,[4] and the recovery in the
Atlantic Ocean of the crashed Air France Flight 447.

Bayesian search theory is incorporated into the CASP (Computer Assisted Search Program) mission planning
software used by the United States Coast Guard for search and rescue. This program was later adapted for
inland search by adding terrain and ground cover factors for use by the United States Air Force and Civil Air
Patrol.

Mathematics
Suppose a grid square has a probability p of containing the wreck and that the probability of successfully
detecting the wreck if it is there is q. If the square is searched and no wreck is found, then, by Bayes' theorem,
the revised probability of the wreck being in the square is given by
For every other grid square, if its prior probability is r, its posterior probability is given by

USS Scorpion

In May 1968, the U.S. Navy's nuclear submarine USS Scorpion (SSN-589) failed to arrive as expected at her
home port of Norfolk, Virginia. The command officers of the U.S. Navy were nearly certain that the vessel had
been lost off the Eastern Seaboard, but an extensive search there failed to discover the remains of Scorpion.

Then, a Navy deep-water expert, John P. Craven, suggested that Scorpion had sunk elsewhere. Craven
organised a search southwest of the Azores based on a controversial approximate triangulation by
hydrophones. He was allocated only a single ship, Mizar, and he took advice from Metron Inc., a firm of
consultant mathematicians in order to maximise his resources. A Bayesian search methodology was adopted.
Experienced submarine commanders were interviewed to construct hypotheses about what could have
caused the loss of Scorpion.

The sea area was divided up into grid squares and a probability assigned to each square, under each of the
hypotheses, to give a number of probability grids, one for each hypothesis. These were then added together to
produce an overall probability grid. The probability attached to each square was then the probability that the
wreck was in that square. A second grid was constructed with probabilities that represented the probability of
successfully finding the wreck if that square were to be searched and the wreck were to be actually there. This
was a known function of water depth. The result of combining this grid with the previous grid is a grid which
gives the probability of finding the wreck in each grid square of the sea if it were to be searched.

At the end of October 1968, the Navy's oceanographic research ship, Mizar, located sections of the hull of
Scorpion on the seabed, about 740 km (400 nmi; 460 mi) southwest of the Azores,[5] under more than
3,000 m (9,800 ft) of water. This was after the Navy had released sound tapes from its underwater "SOSUS"
listening system, which contained the sounds of the destruction of Scorpion. The court of inquiry was
subsequently reconvened and other vessels, including the bathyscaphe Trieste II, were dispatched to the
scene, collecting many pictures and other data.

Although Craven received much credit for locating the wreckage of Scorpion, Gordon Hamilton, an acoustics
expert who pioneered the use of hydroacoustics to pinpoint Polaris missile splashdown locations, was
instrumental in defining a compact "search box" wherein the wreck was ultimately found. Hamilton had
established a listening station in the Canary Islands that obtained a clear signal of what some scientists
believe was the noise of the vessel's pressure hull imploding as she passed crush depth. A Naval Research
Laboratory scientist named Chester "Buck" Buchanan, using a towed camera sled of his own design aboard
Mizar, finally located Scorpion.[5] The towed camera sled, which was fabricated by J. L. "Jac" Hamm of Naval
Research Laboratory's Engineering Services Division, is housed in the National Museum of the United States
Navy. Buchanan had located the wrecked hull of Thresher in 1964 using this technique.

Optimal distribution of search effort

Searching in boxes
Assume that a stationary object is hidden in one of n boxes (locations). For each location there are three
known parameters: the cost of a single search, the probability of finding the object by a single search if
the object is there, and the probability that the object is there. A searcher looks for the object. They know
the a priori probabilities at the beginning and update them by Bayes’ law after each (unsuccessful) attempt.
The problem of finding the object in minimal expected cost is a classical problem solved by David
Blackwell.[6] Surprisingly, the optimal policy is easy to describe: at each stage look into the location which
maximizes . This is actually a special case of the Gittins index.

See also
Bayesian inference – Method of statistical inference
Search game – Two-person zero-sum game

References
1. Whitley, Angus. "How an Eighteenth-Century Statistician Is Helping to Find MH370" (https://www.bloombe
rg.com/news/articles/2015-12-03/find-mh370-next-job-for-theory-used-to-show-existence-of-god).
Bloomberg.com. Retrieved 2016-03-07.
2. "MH370 search narrowed to 'hot-spot' as analysis finds plane did not conduct controlled landing" (https://
www.telegraph.co.uk/news/worldnews/mh370/12030483/MH370-search-narrowed-to-hot-spot-as-analysis
-finds-plane-did-not-conduct-controlled-landing.html). Telegraph.co.uk. Retrieved 2016-03-07.
3. Whitley, Angus. "MH370 Hunters Narrow Down Most Likely Site of Wreckage" (https://www.bloomberg.co
m/news/articles/2015-12-02/mh370-hunters-say-new-analysis-reaffirms-most-likely-wreck-site).
Bloomberg.com. Retrieved 2016-03-07.
4. McGrayne, Sharon Bertsch (2011). The Theory That Would Not Die: How Bayes' Rule Cracked the
Enigma Code, Hunted Down Russian Submarines & Emerged Triumphant from Two Centuries of
Controversy. Yale University Press. pp. 92–. ISBN 978-0-300-18822-6.
5. "Strange Devices That Found the Sunken Sub Scorpion." (https://books.google.com/books?id=EyoDAAA
AMBAJ&pg=PA66) Popular Science, April 1969, pp. 66–71.
6. Assaf, David; Zamir, Shmuel (1985). "Optimal Sequential Search: A Bayesian Approach" (https://doi.org/1
0.1214%2Faos%2F1176349665). The Annals of Statistics. 13 (3): 1213–1221.
doi:10.1214/aos/1176349665 (https://doi.org/10.1214%2Faos%2F1176349665). ISSN 0090-5364 (https://
www.worldcat.org/issn/0090-5364). JSTOR 2241134 (https://www.jstor.org/stable/2241134).

Stone, Lawrence D., The Theory of Optimal Search, published by the Operations Research Society of
America, 1975
Stone, Lawrence D., In Search of Air France Flight 447. Institute of Operations Research and the
Management Sciences, 2011. https://www.informs.org/ORMS-Today/Public-Articles/August-Volume-38-
Number-4/In-Search-of-Air-France-Flight-447
Iida, Koji., Studies on the Optimal Search Plan, Vol. 70, Lecture Notes in Statistics, Springer-Verlag,
1992.
De Groot, Morris H., Optimal Statistical Decisions, Wiley Classics Library, 2004.
Richardson, Henry R; and Stone, Lawrence D. Operations Analysis during the underwater search for
Scorpion. Naval Research Logistics Quarterly, June 1971, Vol. 18, Number 2. Office of Naval Research.
Stone, Lawrence D. Search for the SS Central America: Mathematical Treasure Hunting. Technical
Report, Metron Inc. Reston, Virginia.
Koopman, B.O. Search and Screening, Operations Research Evaluation Group Report 56, Center for
Naval Analyses, Alexandria, Virginia. 1946.
Richardson, Henry R; and Discenza, J.H. The United States Coast Guard computer-assisted search
planning system (CASP). Naval Research Logistics Quarterly. Vol. 27 number 4. pp. 659–680. 1980.
Ross, Sheldon M., An Introduction to Stochastic Dynamic Programming, Academic Press. 1983.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Bayesian_search_theory&oldid=1154910859"