Bayesian Search for Sunken Objects

Bayesian Search is a technique that has been used to search for sunken submarines (USS Scorpion), nuclear bombs (Palomares B-52 crash), and aircraft (Air France 447). The idea is best explained by a concrete example. A plane has crashed somewhere in the ocean. Suppose the search area is divided into four grids.

Using all available information, each grid is assigned a probability p, that the target is in the grid, and a probability q, that the target will be found if the target is in fact in the grid and the grid is searched. Therefore, f = pq = the probability that the target will be found.

Next, the grid with the highest f probability is searched. In the image, Grid 4 has the highest f value so it’s searched first. Suppose the target isn’t found. Note that the target could still be in Grid 4 because there’s a 1-q = 0.10 probability that the target was there but was missed during the Grid 4 search.

The p values for each of the four grids is updated. For the one searched grid, the new p’ value is (p)(1-q) / (1 – pq). For the unsearched grids, the new p’ value are (p) / (1 – pq).

After all the p values are updated to p’, they are normalized by dividing each by the sum of the p’ values. The q values don’t change, and new f values are computed as f = p’’ * q.

So, after searching Grid 4 without success, the original p values go from (0.4, 0.1, 0.2, 0.3) to (0.5734, 0.1246, 0.2548, 0.0471). The probability that the target is in Grid 4 has dropped to a very low value, while the p values of Grids 1 to 3 have increased a bit. The next search would be in Grid 1.

Advertisements
This entry was posted in Machine Learning. Bookmark the permalink.

One Response to Bayesian Search for Sunken Objects

  1. asdlfj says:

    Perfect timing on this post! We’re desperately searching for my daughter’s cell phone and I’m totally going to use this methodology to find it. After Round 1, there is a 17.6% chance it’s at her camp.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s