Measuring Search Effectiveness
Many-Target and Single-Target Searches

We now consider the question of how much "better" is the completely coordinated search (first case) than the completely random search (second case).

Different search applications require different measures of systems effectiveness. The task may involve a single target (a sunken submarine, for example), or may involve many targets. And, in the case of many targets, the desire to maximize target detections per amount of search effort (as in prospecting for manganese nodules) is not the same thing as the desire to minimize the number of targets missed in a swept area (as in minesweeping). Finally, a search problem may be embedded in a larger optimization context, as in "what is the best strategy for two adults to use in searching for a stationary lost child so as to minimize the expected time until all three are reunited?" [THOM92]

Effectiveness of Many Target Search (e.g., Minesweeping)

For the minesweeping application our goal is to minimize the cost of detecting a specified fraction D of the targets, which allows us to make the notion of "better" a precise one by recasting the question as: for a given sensor effectiveness p, how much larger a sweep fraction S_r is required so that the detect fraction D of a completely random search (second case) is equal to that of a completely coordinated search (first case) with sweep fraction S_c? By equating D_c in equation (2) with D_r in equation (3), we calculate the "search gain" G, or factor reduction in required search effort afforded by a coordinated search as compared to a random search:

G_c, many target = S_r / S_c = -ln (1 - p) / p (4)

This result says that, for any sensor detection probability p < 1, we can achieve any desired detect fraction D equally well by (a) performing a completely coordinated search with sweep fraction S_c we calculate from equation (1), or by (b) performing a random search with sweep fraction S_r calculated from equation (2), which is larger than S_c by a factor (equation (4)) which depends only on p, and is independent of the desired detect fraction D and the S required to achieve it. Figure 2a shows how this ratio varies with p; it is fairly small for poor sensors, and, as is obvious from inspection of equation (4), the numerator of the expression dominates the behavior as p approaches 1.

Figure 3. Search strategy gain (G) of a completely coordinated search strategy over a completely random strategy, as a function of the sensor target detection probability (p), for (a) finding a specified fraction of multiple targets, equation (4), and (b) finding a single target, equation (9).

The fact that S_r/S_c is independent of the desired D suggests that we might be able to make use of the corresponding ratio to quantitatively describe the relative effectiveness of other search strategies. Accordingly, we define the "search gain" G of any given search strategy s as:

G_s = S_r / S_s

In other words, the search gain G_s of a search strategy s is the factor by which that strategy reduces the search fraction required to achieve any desired detect fraction, compared to a random search. So we can then write the detect fraction D_s for any search strategy s as: D_s = 1 - e^{-p Gs Ss} = 1 - e^{-p Gs N 2r d / A} (5)

G will be most meaningful if it depends only on p, as in the case of the fully coordinated search of case 1, but it will still be useful if it varies slowly and predictably with S. Note that while the G calculated for the completely coordinated search -- equation (4) -- serves as the maximum value achievable by any search strategy, it is entirely possible for a strategy's G to be less than 1.0 if element paths are positively correlated, as in the case of ants following each others' pheromone trails.

The System Design Space

The reason for choosing to write equation (5) in this format is that the variables in the expression essentially provide a coordinate system for the system design space, and they break naturally into three groups:

p and r are characteristics of the primary mission sensor: its single-pass probability of target detection and its range. Note that in some cases the choice of a sensor will have immediate implications for other system characteristics; for example, p and/or r may depend critically on element speed, as with sonar self noise.
N and d, which together with r determine the sweep factor S, are parameters pertaining to the element platforms: the number of elements to be employed, and the effective search range of each. Mission time and stealth requirements, maximum platform speed, and energy storage limitations may be important in determining d.
G is the gain in search effectiveness due to the coordination (negative correlation) of element search paths to provide balanced coverage; this is where vehicle search strategy behaviors are accounted for.

Figure 3 presents a (fictitious, or "toy") simple application example in which the design space consists of 12 possible systems, allowing any of three possible sensors, a completely random or a completely coordinated search strategy, and an optional battery upgrade to double vehicle range, with each choice having an associated specified cost. As the quality of the sensor (its raw target detection probability p) improves, the most cost effective design shifts from employing a large number of the least expensive and least capable elements to a much smaller number of more expensive and more capable elements. In the real world, with a much more complex design space and unavailable, unreliable, and expensive cost estimates, the design process would probably begin with the determination of p for the mission sensor package, since determining p determines the maximum G that can be achieved. The lower the value of p, the more likely it is that it will be more cost effective to utilize a random search strategy (G = 1) and increase S, rather than implement a coordinated search strategy, with its added cost and complexity. Once the search strategy is selected, determining G, then the tradeoff between sensor range, number of elements, and search range per element can be made to realize the required S in the most cost effective fashion.

sensor cost sensor range sensor detect p G*S reqd coord gain G(p) coord search? double range? elem cost num elems system cost

1 1 0.5 9.21 1.39 no no 11 460.52 5066 <---

1 1 0.5 9.21 1.39 no yes 26 230.26 5987

1 1 0.5 9.21 1.39 yes no 41 332.19 13620

1 1 0.5 9.21 1.39 yes yes 56 166.10 9301

10 1 0.7 6.58 1.72 no no 20 328.94 6579

10 1 0.7 6.58 1.72 no yes 35 164.47 5756 <---

10 1 0.7 6.58 1.72 yes no 50 191.25 9562

10 1 0.7 6.58 1.72 yes yes 65 95.62 6216

15 1 0.9 5.12 2.56 no no 25 255.84 6396

15 1 0.9 5.12 2.56 no yes 40 127.92 5117

15 1 0.9 5.12 2.56 yes no 55 100.00 5500

15 1 0.9 5.12 2.56 yes yes 70 50.00 3500 <---

sensor cost	sensor range	sensor detect p	G*S reqd	coord gain G(p)	coord search?	double range?	elem cost	num elems	system cost

1	1	0.5	9.21	1.39	no	no	11	460.52	5066	<---
1	1	0.5	9.21	1.39	no	yes	26	230.26	5987
1	1	0.5	9.21	1.39	yes	no	41	332.19	13620
1	1	0.5	9.21	1.39	yes	yes	56	166.10	9301

10	1	0.7	6.58	1.72	no	no	20	328.94	6579
10	1	0.7	6.58	1.72	no	yes	35	164.47	5756	<---
10	1	0.7	6.58	1.72	yes	no	50	191.25	9562
10	1	0.7	6.58	1.72	yes	yes	65	95.62	6216

15	1	0.9	5.12	2.56	no	no	25	255.84	6396
15	1	0.9	5.12	2.56	no	yes	40	127.92	5117
15	1	0.9	5.12	2.56	yes	no	55	100.00	5500
15	1	0.9	5.12	2.56	yes	yes	70	50.00	3500	<---

Figure 3. Design spreadsheet for a fictitiously simple application design space consisting of only 12 possible systems. The mission is to search an area A = 10000 and achieve a detect fraction D = 0.99. A base vehicle costs 10, and has a range of 100. The additional cost of better batteries which double the range to 200 is 15. The cost of sensors and processing to implement a completely coordinated search strategy is 30. Three possible mission sensors are available. Equation (4) has been used to calculate the number of elements required, the cost per element, and the total system cost for each of the twelve possible combinations of mission sensor, random or coordinated behavior, and baseline or improved batteries. It is seen that (a) the most cost effective system using the least expensive sensor uses the simplest possible elements, (b) the intermediate sensor justifies the incorporation of the battery upgrade, but not the coordinated search behavior, and (c) using the most expensive sensor justifies both the battery upgrade and the coordinated search behavior.

Effectiveness of Single Target Search (e.g., SAR)

Here we present the analysis for the case of a search for a single target. Now the goal is to minimize the expected search effort required to find the target. Again letting S be the sweep fraction or search effort variable, and letting Prob(S) be the probability that the single target is discovered after the expenditure of effort S, we can write:

<S> = [integral from 0 to inf] S Prob(S) dS (5)

For a random search, we have

<Sr> = [integral from 0 to inf] S e^-pS dS = 1 / p (6)

which is a well known result. Also well known is the result for a coordinated search when p = 1

<S> = [integral from 0 to 1] S dS = 1/2 (7)

Since the value of <S> for a random search with p = 1 is just 1, we see that, for a cookie cutter sensor, a coordinated search for a single target is twice as good as a random search. Less well known, however, is the formula for a coordinated search when p is less than 1. With a suitable substitution of variables, the formula is

<Sc> = [sum n=0 to inf] [integral from 0 to 1] (n + x) p (1 - p)ⁿ dx = 1/p - 1/2 (8)

The "search gain" due to a fully coordinated search for a single target, compared to a random search, is thus

G_{single target} = <S_r>/<S_c> = (1/p) / (1/p - 1/2) = 2 / (2 - p) (9)

This value is also plotted in Figure 3. With an imperfect sensor, then, we see that the advantage of a coordinated search for a single target is is close to that for the multiple target search when p is low, but is limited to a maximum value of 2 when p = 1. Cost / benefit tradeoffs can be done analogous to those presented above for the multiple target search, and the results will be more favorable to the random search. The point is that, since the G value is different for the two applications, the optimal choice of sensor, search strategy, and other aspects of a system may well be different as well. It is entirely possible to devise two search systems A and B such that A will find any specified percentage of a field of mines with less cost than B, while B will, on average, find a single mine with less cost than A.

Up to Many Robot Systems

Robotics home page

Please address all questions and comments to: robo-web@spawar.navy.mil
Last update: 1 December 1998.

Measuring Search Effectiveness Many-Target and Single-Target Searches

Effectiveness of Many Target Search (e.g., Minesweeping)

The System Design Space

Effectiveness of Single Target Search (e.g., SAR)

Measuring Search Effectiveness
Many-Target and Single-Target Searches