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.