I. Simple scenario

The simple scenario has 2 components. First, the object is in one of a fixed number of locations. Second, even if we search the location containing the object, we may or may not find (detect) it. Let the four locations be A₁ ... A₄ and let D be the event of detection. For now, we assume we can search all locations simultaneously.

To "navalize" the situation, suppose a pilot has gone down in the jungle. His flight plan had 4 segments. P(A_i) is the probability he went down on leg i. Two legs may have been flown in bad weather and have a higher crash probability. The last leg might be more familiar terrain and have a lower crash probability. We will cruise over his route of flight and look for the wreckage. But some areas have dense foliage, so the wreckage will be hard to spot and so P(D| A_i) will be lower here. Note also that P(D| A_i) need not sum to one.

	A1	A2	A3	A4
P(Ai)	0.4	0.4	0.15	0.05
P(D|Ai)	0.3	0.5	0.6	0.8

In this scenario, A₁ and A₂ are equally likely. A₄ is not at all likely (5%). The terrain in A₁ is more rugged, so there is a lower detection probability than in A₂.

We can draw the following Venn diagram.

	A1	A2	A3	A4
D	0.12	0.20	0.09	0.04
Not D	0.28	0.20	0.06	0.01

Note that the columns sum to P(A_i) and that

0.45 =P(D) = sum of top row and

0.55 =P(not D) = sum of bottom row.

Suppose we search and do not find the pilot. (If we DO find him/her, we stop.) Given "not D", we refer to the bottom row of the box and divide by P(not D).

	A1	A2	A3	A4
P(Ai|Dc)	0.509091	0.363636	0.109091	0.018182

Note that if the first search fails, then A₁ and A₂ are no longer equally likely. Since A₂ was easier to search, the fact that we didn't find the pilot makes it less likely that he/she is in A₂. However, not finding him in A₁ is not so unexpected.

After searching all of Monday for the pilot (without finding him/her), we start again on Tuesday. We have now revised our probabilities of where the pilot might be. Our table now is

	A1	A2	A3	A4
	0.509091	0.363636	0.109091	0.018182
D	0.153	0.182	0.065	0.0145
Not D	0.357	0.182	0.0436	0.00364

From this we see that P(D^c) = 0.58624. If Tuesday is as fruitless as Monday was, we would revise the probability of A_i by

	A1	A2	A3	A4
P(Ai|Dc)	0.609	0.310	0.0744	0.00621

Note how the original probability of A₁ has grown from 0.4 to 0.609. In the exercise, you are to determine what factors govern this effect.

II. Single sector search

Suppose we cannot search all sectors, but can only search one sector. We wish to maximize the P(D). We must modify the layout in (I) by setting all but one of P(D| A_i) to zero because we can't find the object if we don't search the sector. Since P(D) is the sum of the top row of the box above, and all but one element of the box will be zero, it should be clear we should choose to search the cell with the largest entry in the top row of the box. In the given example, this is sector A₂.

	A1	A2	A3	A4
D	0.12	0.20	0.09	0.04
Not D	0.28	0.20	0.06	0.01

We now envision our problem as being the following.

	A1	A2	A3	A4
P(Ai)	0.40	0.40	0.15	0.05
P(D|Ai)	0	0.50	0	0

The Venn diagram becomes:

	A1	A2	A3	A4	Total
D	0.0	0.20	0.0	0.0	0.20
Not D	0.40	0.20	0.15	0.05	0.80

0.2 =P(D)

0.8 =P(not D)

To find P(A_i | D^c), divide the bottom row by P(D^c) = 0.8.

	A1	A2	A3	A4
P(Ai|Dc)	0.50	0.25	0.1875	0.0625

If we do not detect our object on the first try, we re-apply the detection probabilities.

We write D₁^c to mean we didn't detect the pilot on the first attempt.

	A1	A2	A3	A4
P(Ai|Dc)	0.50	0.25	0.1875	0.0625
P(D|Ai)	0.30	0.50	0.60	0.80

	A1	A2	A3	A4
D	0.15	0.125	0.1125	0.05
not D	0.35	0.125	0.075	0.0125

Now, sector A₁ is the most likely. So if we search A₁, we set P(D| A_i) to be

	A1	A2	A3	A4
P(D|Ai)	0.30	0	0	0

If this search fails, P(A_i| D₂^c) is given by:

	A1	A2	A3	A4
P(Ai D2c)	0.35	0.25	0.1875	0.0625

0.85 =P(not D₂)

Dividing by P(not D₂) gives P(A_i| D^c)=

	A1	A2	A3	A4
P(Ai|D2c)	0.411765	0.2964118	0.220588	0.073529

In an actual searching scenario, we would like to send our search party to the best sector and tell them how long to spend searching before moving on to the next sector. (Obviously, if they find the pilot, they can come home to a joyous welcome.) The values of P(D|A_i) in the examples are based on a certain time spent searching. It is reasonable that if we spend less time searching a sector, then P(D|A_i) will be less. For simplicity, assume that if we spend half as much time searching, we have 1/2 the probability of detection. Then we should be able to reproduce the above example using smaller values of P(D|A_i), corresponding to a smaller time spent searching before considering moving to a new sector. Suppose the probabilities given are for a 4 hour search. If we divide them to correspond to a 5 minute search, we should be able to find the time to move on, at least down to 5 minutes. You are asked to do this in the exercises.

Assignment:

1. Reproduce the simple search algorithm on the handout.

2. Change P(A_i) to .3, .3, .3, .1. What is P(D) now? What is P(A_i| D^c)?

3. Implement the single sector search algorithm. Put P(D| A_i) in A3..D3. In A2, place a 1 (to be changed later). In A4..D4, put +A3*$A$2. Use these for P(D| A_i). In A6..D6, put P(Ai), e.g., 0.4, 0.4, 0.15, 0.05. In E6..H6, put P(D A_i) = P(D | A_i) P(A_i). In I6, put @MAX(E6..H6). In J6..M6, put P(D^c A_i) when only the most likely sector is searched. Calculate these from the formula: @IF(E6=$I6,(1-A$4)*A6,A6). In N6, put the sum of these, namely, P(D^c). In A7..D7 (new row), put P(A_i| D^c), found by dividing the last four entries in row 6 by their sum. Copy the rest of row 6 down (columns E-N). Make numerous copies of (all of) row 7. This represents the long- term progress of the search, if not successful.

	A-D	E-H	I	J-M	N
2	t
3	P(D|Ai)
4	detect in t
5
6	P(Ai)	P(D Ai)	MAX	P(not D Ai)	P(not D)
7	P(Ai | not D1)
8

4. Set up column O to be time. Increment it by A$2. Using this as the horizontal axis, graph columns E-H. What does this graph represent (especially which curve is on top)?

5. Decrease A2 to represent finer time divisions. (This reduces the probability of detection in one unit.) What happens to the graph? What changes and what doesn't? Do this for several (2 or 3) smaller time steps.

6. Change P(A_i) to .3, .3, .2, .2 and P(D| A_i) to .5, .6, .6, .5 Examine several time increments (A2). Give an overall description of the two graphs.

7. Change P(D| A₂)=.2 How does this change things?

8. For P(D| A_i)= .5, .6, .6, .5, change P(A_i) to .4, .2, .2, .2. How does this change things? What do you conclude about what drives the final solution?

9. Write a one page report about SEARCHING (not about spreadsheets). Tell me what you have learned that is relevant to this course and/or the Navy.

Problems:

1. I can't find my keys. They may be in my overcoat, on the ground in the parking lot or still in my ignition.

	Coat	Lot	Car
P(Ai)	0.10	0.85	0.05
P(D|Ai)	0.75	0.05	1.00

a. If I look in all 3 places, what is the probability I will find my keys?

b. If I fail to find them the first time, what is the probability they are in the Lot?c. If I instead decide to look in only one place first, where should I look?

1. If I look and don't find it in that one place, what is the probability it is in each of the other places?

2. An object is in one of 3 locations. If it is in location 1, there is a 30% of detection. If it is in location 2, there is a 40% chance and in location 3, there is a 50% chance.

(a) If there is a 50% probability that the object is in location 1, 30% chance it is in location 2 and 20% chance it is in location 3, what is the chance we will find the object if we search all 3 locations?[Ans: 0.37]

(b) If we could search only 1 location, where should we search? What is the probability of detection?[Ans: Location 1. Prob=0.15]

(c) Repeat (a) and (b) if the probability of detection is reduced by half. (As if we only searched 1/2 a day, instead of a full day.)[Ans: 0.185, Still Location 1, 0.075] (d) If we searched all 3 locations and did not find the object, what are the new probabilities it is in each location? Use the probabilities in (a), not (c). Does it make any difference?[Ans: 0.5556 0.2857 0.1587 ]

(e) If we search all 3 locations a second time, what is the chance of detection (on the second try)?[Ans: 0.3603]

(f) In part (b), if we searched and did not find the object, what are the updated probabilities of the object being in each location?[Ans: 0.4118 0.3529 0.2353 ]

1. If P(D | A_i) is the same for all cells, which cell should we search first? Use some mathematics to show your answer.

4. Suppose in the single sector search we decide to search sector 1. Show mathematically that P(A_i | D^c) > P(A_i) for the sectors not searched. If all but one probability increases, the remaining probability (for sector 1) must decrease. Why?

5. A dresser has 4 drawers. We are looking for an object that may or may not be in the dresser. Suppose we open the top drawer and look. If we do not find the object there, show that the probability that it is in one of the other 3 drawers increases. Also show that the probability that the object is not in the dresser at all also increases. [ Hint: think of a fifth imaginary drawer.] Is the above result a contradiction? Why or why not?

1. A lost object is in one of 9 cells. The following gives the probability of being in each cell.

0.40	0.05	0.10
0.15	0.10	0.05
0.05	0.05	0.05

a. If P(D| A_i) = .3 for all cells and all cells are searched, find P(D).

1. If P(D| A_i) is as given below, find P(D).

0.6	0.6	0.2
0.6	0.4	0.4
0.5	0.5	0.5

[Ans: 0.515 ]

1. If all cells are searched and the object is not found, find P(A_i| not D)

[Ans:

0.330	0.041	0.165
0.124	0.124	0.062
0.052	0.052	0.052

d. If we can only search 2 cells, which two should we do? What is P(D) if we search these 2 cells?

[Ans 0.33 for top cells in left column]

e. If we search these 2 and do not find it, find P(A_i| not D). [Ans:

0.239	0.075	0.149
0.090	0.149	0.075
0.075	0.075	0.075

f. Failing on the first try, which 2 cells should we now search?

[Ans center and upper left]

What is P(D)? [Ans 0.202985 ]

If our second try fails, find P(A_i| not D). [Ans:

0.120	0.094	0.187
0.112	0.112	0.094
0.094	0.094	0.094