John C. Turner
SM230 - Spring 1996
Introduction and Assumptions
In this section, we develop results for various searching scenarios, each with its own set of assumptions An actual situation may not exactly match any of the assumptions made here, but will fall between the cases. Thus, the results derived here may be considered as bounds on the probability of detection in more realistic situations.
Throughout this section, it will be assumed that there is a fixed area, A, within which the target is known to lie. The target is assumed to be stationary and we are moving in a search effort along a track of length l. We have no other prior information on the target's position, and so we assume that the target's position is randomly (uniformly) distributed over A. Technically, this means that the probability that the target is in some sub-region, a, is proportional to the area of the sub-region, i.e., a/A. The probability does not depend on the location of a.
Sometimes it is convenient to break our search down into segments. This is largely an artificial device. It does not affect the way the search is actually conducted.
Throughout, we assume that our sensor has perfect detection within range +/-r/2 and no detection beyond range +/-r/2. There is a related analysis that assumes only a probability of detection within this range. As will be shown later, this amounts to reducing that situation to a form of the situation presented here. We now distinguish two important cases. The first is the methodical search and the second is the random search.
Methodical Search and Random Search
In the methodical search, we are careful never to search the same area twice. We ensure that our track (±r/2) never crosses itself. It may be helpful to think of mowing the grass using a zig-zag pattern. Since our track is of length l, it will cover a region of total area rl, where l is the length of the track. (This is clearly the case for a straight line track.) The assumption that the target is uniformly distributed in A says that the probability of detection for this search is given by rl/A, the fraction of the total area that has been searched. If we are careful, we can cover all the area of A and are then certain of detecting the target.
What this means is that the distance we have to travel in order to detect the target has a uniform distribution. Obviously, the minimum distance is 0. The maximum distance is given by a/r, because when we have traveled this far, we have covered the entire area. Therefore,
Prob(detect in distance y) = ry/a, 0<y<a/r
In the random search, we imagine that our search path is divided into segments and assume that detection on one segment of our search is independent of detection (or non-detection) on any previous segment. This could arise, for instance, if we take absolutely no care whatsoever with our track and pay no attention to whether or not we have searched a region previously. We will see later that it can also arise under other, less artificial assumptions.
Note how the random search differs from the methodical search. In the methodical search, failure to detect on one segment increases the chance of detection on all subsequent segments. In the extreme, if we have searched all segments but one and have failed to detect the target so far, we are certain of detecting it in the last segment. However, in the random search, our probability of detection is the same, regardless of how far we have searched.
Probabilty of Detection
For the random search, the probability of detection on one segment is not affected by our failure to detect on earlier segments. Thus, the probability of detection on all segments is the same. Under the assumption that the target is uniformly distributed in A, the probability of detection on a segment is proportional to the area of the segment. Consider breaking our search into small segments, each of area a. The probability of detection on each segment is a / A. Let X be the number of segments we must search to find our target. Then X is a geometric random variable and the mean value of X is given by A/a. From the properties of the geometric random variable, we have
Prob(X=k) = (1-a/A)^(k-1) (a/A)
Prob(X < k) = 1- (1-a/A)^k
Prob(X > k) = (1-a/A)^k
Now consider a track of length y and, consequently, total area of ry. If we divide the track into N segments, each with area ry/N, the probability of detection on each segment is given by the ratio of ry/N to A, i.e., ry/(NA). Also, the probability of failing to detect on each segment is given by 1-ry/(NA). All the segments are independent, so the probability of failing to detect on any segment is merely the product of all these segment probabilities, namely,
Prob(fail to detect) = Prob(X > N)
= (1-(ry/N)/A)^N
= (1-(ry/A)/N)^N
If we take the limit as N goes to infinity, the right hand side becomes e^(-ry/A) , from calculus. This leads to
Prob(detection in distance y) = 1- e^(-ry/A)
Now let the random variable Y be the distance traveled in order to detect the target. Then Y has an exponential distribution with mean A/r. Since Y is the distance we need to travel, consider what area would be covered. Since the width is r, the area covered is rY. Hence, the expected area to be covered is r times the expected value of Y. This just turns out to be A, the total area we have to search. So, on average, we cover the entire area before detecting the target. In the methodical search, we expect to cover only half the area before detecting the target. Also, observe that if A is fixed in the random search, we can decrease the mean distance by increasing r. This makes practical sense because if we use a wider search distance, we should not need to travel as far to cover the same area.
Variations
The usual scenario is that of a ship searching for a stationary target. In this case, the assumption of independence of all segments of the search is not realistic. Given that a ship's course is made of straight segments, we can be fairly sure that the region being searched one minute is not the same as the region searched in the previous minute. Thus, the probability of detection in the second minute depends on whether or not we detected the target in the previous minute. The only way that all adjacent segments could be independent would be if the ship followed Brownian motion, so that it always had some chance of re-tracing its path.
However, the discrete case of the random search with regions of area a fits another useful scenario. This is the case of "snapshots". In the analysis above, the small regions searched do not have to be adjacent. If the regions are chosen randomly across the entire area, then the assumption of independence of the smaller regions becomes reasonable. The sensors could be dipped sonars. Or they could be several reconaissance photos. Or they could be separate reports from patrols.
In the continuous track case, the assumption of independence is consistent with a slightly different, and interesting, scenario. This is the case where both the searcher and the target are moving, and their movements are independent. That is, the searcher has no information about the target in order to pursue it and the target does not have information to help it evade the searcher. In the case of discrete track segments, one could argue that having searched one segment and not found the target does not change the probabilities of other segments (including the one just searched). When the searcher moves on to the next segment, the target could move into the segment just searched. Thus, the notion of a stationary target is quite important.
Sweep width
In all of the above, we have assumed that if the target is within ± r/2 of us, we will detect it with probability 1. This is not very realistic. We have all walked right past something we are looking for without seeing it. What happens to the above discussion if the probability of detecting something that is within range is less than 1?
Suppose we have searched (methodically) a box of length l and width r. If our probability of detection is 1, we have seen that the probability of detecting the target is just the probability that the target is within this box, which is given by rl/a. Now suppose that we have a probability p of detecting the target even if it lies within the box we have searched. Now the probability of detecting is given by
p * rl/A = Prob(find target)
= Prob(find target | target is in box) * Prob(target in box).
But observe that this formula, prl/A is the same as the probability of detection in the "perfect world" case, but with a smaller box. That is, it is the answer for the case where we have probability of detection 1 and our "sweep width" is now p * r. Thus, all the above results can be applied, but we now consider that we can search a width of pr, instead of r.
Some sensors (sonar, etc.) have a higher probability of detection when the target is nearby than when the target is farther away. How can we handle this case? To begin with, let us suppose that we have just two ranges to consider. Suppose that over a width of r1, we have detection probabilility p1 and over an additional width of r2, we have probability p2. (We would have r1+r2=r.) By reasoning similar to that above, the overall probability of detection would be the same as we had detection probability 1 and the the width of our search was p1 r1 + p2 r2. This latter expression is the sweep width for our sensor. Note that it is characterized completely in terms of the sensor, not the area to be searched. Also, the detection probabilities for the random search using the less than perfect sensor are exactly the same as the detection probability using a perfect sensor whose width is given by the sweep width calculation.
Obviously, we can extend the above analysis to any number of sectors of operation for the sensor. If the probability of detecting a target over a width of ri is given by pi, then the sweep width is given by Sum pi ri. What happens if we have a formula for the probability of detection as a function of the distance the target is from the sensor? In that case, we write p(x) for the probability of detection if the target is a distance x from the sensor. We can then think of p(x) dx as playing the same role as pi ri, so the above sum becomes an integral,
This gives us the sweep width in the case where the detection probability varies continuously with distance.
In summary, the notion of perfect detection over a width of r would not appear at first glance to be a very reasonable one. However, the idea of sweep width shows that, as far as detection probability goes, all imperfect sensors can be converted to an equivalent "perfect" sensor.
Exercises
1. I dropped my keys somewhere in the front yard. It has an area of 2000 ft^2. I can search 2 feet to my right and left.
2. I'm searching for an underground water line. My metal detector can detect the pipe if I'm within 3 feet of it. I know it's in an area of 150 ft^2.
3. A submarine is suspected in an area of 400 mi^2. A sonobuoy can search a circle of radius 0.5 mile. I deploy these at random.
4. The random search assumes that neither the searcher nor the target have any information about each other. How do things change if the target can try to elude the searcher?
5. There is the assumption of a uniform (initial) distribution. Suppose that certain areas are more likely than others. How can we modify our search strategy to use this information?
6. Suppose we are leaving port and know that our mission will be to conduct two separate searches. We wish to carry enough sonobuoys so that we will be 80% sure of detecting both targets. Since our target will be moving around, we use the random search model.
7. Return to the first problem on random searching. What if I have an 80% chance of seeing keys if they are within 1 foot of me, but only a 50% of seeing keys if they are between 1 and 2 feet away from me?
8. What is the sweep width for a sensor whose detection probability is 90% when it is right over a target (distance=0) and the detection probability decreases linearly to 0% at a distance of ± 10 feet?