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.
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.