Translator Disclaimer
18 September 2019 What probability distribution describes search?
Author Affiliations +
Abstract

Typically, search research papers assume that target acquisition is described by an exponential distribution. We investigate when this assumption is valid. It is obvious that two people are more effective than one person at finding a target, but how can that be quantified? The network imaging sensor (NIS) and time-dependent search parameter (TDSP) models quantify how much more effective multiple observers are at finding a target than a single individual for a wide variety of scenarios. We reference and summarize evidence supporting the NIS and TDSP models and demonstrate how NIS model results can be expressed in terms of a reduced hyperexponential distribution for scenarios where observer and target are stationary. Target acquisition probabilities are determined by analysis and confirmed by computer simulations and perception experiments. Search by multiple stationary observers looking for a stationary target is described by the hyperexponential distribution. Stationary scenarios with multiple observers are more accurately modeled by hyperexponential rather than exponential distributions. Hyperexponential distributions are an example of phase-type distributions used in queuing and in the performance evaluation of computer networks and systems. The observation that search, queuing, and computer networks share phase-type distributions facilitates cross fertilization between these fields.

1.

Introduction

1.1.

Meaning of Model, Simulation, and Experiment

The words “model,” “simulation,” and “experiment” are used in the abstract and for clarity are discussed here. A model is a set of equations intended to approximately describe a physical situation. This paper models search performance, i.e., target acquisition probability as a function of time P(t) for several different situations. Target acquisition performance is simulated by taking random draws from the appropriate distribution and those random draws determine individual or group search performance. In an experiment, observers search for targets, either in the field or in the lab using imagery collected in the field or simulated imagery. The simulated imagery may be field collected imagery that has been image processed to approximate imagery produced by a sensor at a greater range, a sensor with less image resolution, and in some cases the imagery is computer generated. Experimental target acquisition probabilities as a function of time are then compared with modeled and simulated results. Measured and modeled results never exactly agree, in part because the modeled results typically describe results for a large number of identical observers and measured results are for a limited number of observers with different search capabilities. Simulation with a large number of draws can show that the mathematics used to develop the model and the simulation itself are in agreement; repeated simulations with the number of draws equal to the number of individuals taking a perception test can indicate if model results are within the expected range of the experiment.

1.1.1.

Literature review

Several books have been written on the subject of search.16 Braga has given an elementary description of search theory.7 Mardell8 investigated different methods of displaying video to determine the best display method for finding a lost hiker in forested terrain using aerial search. Mardell found serial visual presentation was the best display method, but would serial video display be as effective as video in reconnaissance missions for stationary targets? In a series of experiments, Skirlo presented evidence which supports the view that serial visual presentation is at least as effective as video for detecting stationary targets in reconnaissance missions.9,10

Rotman1114 coauthored a series of articles on different aspects of search. Data for testing search and detection models are available15 and used to test visual search and detection models.16 Variations of the classical search model developed by Johnson and Lawson and later described by Howe are currently in use at Night Vision Electronic Sensors Directorate (NVESD).1719 In the classical search model, target size and the temperature difference between the target and background are the signals that enable search. It has been shown that targets can be detected using texture differences between target and background even when the temperature difference between the target and background is zero.20 The neoclassical search model describes search in terms of random transitions between: (1) the wandering state, (2) N points of interest that are not the target, and (3) a point P0 that is near the target.2123 The model described in this paper starts from a different set of assumptions and is conceptually different from the neoclassical model but is similar to this model in that it describes search in terms of a distribution function with multiple exponentials.

NVESD develops sensors for the Army intended to acquire enemy targets. The efficacy of a sensor is predicted by a NVESD developed model, night vision integrated performance model (NV-IPM),24,25 which is useful for writing sensor specifications and for evaluating purchasing decisions for competing, not yet built, sensors. One way to test NV-IPM target acquisition predictions is to collect and store field imagery photos and then do perception tests using that imagery to determine sensor target acquisition characteristics.26

Krendel and Wodinsky27 (K&W) showed that field-of-view (FOV) search by observers with nearly identical target acquisition skill searching for a small bright spot against a uniform background is described by an exponential distribution, a result that can be derived by applying probability theory to reasonable assumptions about how the eye works.19 Empirical evidence shows that search in rural scenes for a military target by trained Army personnel is approximately described by an exponential distribution.26,28 In this paper, K&W results are generalized to the case where it can no longer be assumed observers have nearly identical target acquisition capability. The exponential distribution found in the K&W experiment applies to FOV experiments where the sensor and target are stationary. To generalize the K&W result to scenarios where the target and/or sensor is moving, the time-dependent search parameter (TDSP) model was developed.19,20,29 Search where multiple observers look for a target and the target is said to be detected the moment the first observer detects the target is termed “cooperative search.” To generalize the result of the K&W experiment to scenarios where multiple observers are engaged in cooperative search, the network imaging sensor (NIS) model was developed.30,31

1.1.2.

Background

This paper builds on the K&W experimental result: search in a single stationary FOV with zero clutter by a single observer searching for a single target is described by an exponential distribution. The TDSP model generalized the K&W result. It applies to cluttered or uncluttered imagery, applies to FOV or field of regard (FOR) and no longer requires a stationary target or observer, i.e., the sensor-target range can change and/or the background can change while search is taking place. The TDSP model gets its input from two sources: (1) the NV-IPM and (2) from empirical fit equations for the time constant τ as a function of P. A restriction of the TDSP model is that it applies to a single observer and a single target. The NIS model takes as input target detection probabilities as functions of time produced by the TDSP model for each sensor against each target and outputs target acquisition probabilities for each target. The NIS model assumes statistical independence of observers taking part in the search prior to target detection. The assumptions of the TDSP model are described in Table 1 of Ref. 19.

1.1.3.

Objectives

This paper has six objectives: (1) provide an overview of selected search theory results obtained over the past several years, (2) point out to the reader that P/τ when averaged over scenes and observers is a good metric for characterizing sensor target acquisition capability, (3) to communicate that analytical models exist for calculating how target acquisition probability grows as a function of time in battlefield scenarios where multiple moving targets are engaged by multiple moving observer/sensor combinations, (4) to show analytically that target acquisition by multiple stationary observers searching for a stationary target in noncooperative search is better described by the hyperexponential distribution rather than the exponential distribution as is usually assumed, (5) to show analytically cooperative target acquisition is also described by the hyperexponential distribution, and (6) to show that cooperative or noncooperative search for a single stationary target can be modeled using phase-type distributions. Objectives 4, 5, and 6 have not been previously reported and it is believed few readers are aware of objectives 2 and 3. In the Army, the third objective is normally done using simulation methods, i.e., COMBATXXI simulation methods32 are used. This paper shows that there is an alternative to simulation for describing target acquisition in combat situations. Phase-type distributions are used by computer scientists modeling computer systems and networks, queueing theorists and operations research analysts. This paper makes a connection between search theory and queueing theory and will hopefully stimulate a beneficial dialogue among researchers working in these specialties.

1.1.4.

Paper outline

In Sec. 2, search background is discussed to minimize the reader’s need to consult references quoted in this paper. In Sec. 3, evidence is referenced that indicates P/τ, averaged over scenes and observers, and measured in perception experiments, is a good metric for characterizing sensor target acquisition capability. Evidence is also referenced that indicates P/τ averaged over scenes and sensors is a good metric for characterizing observer target acquisition capability. In Sec. 4, it is also shown that noncooperative FOV and FOR search is described by the reduced hyperexponential distribution. Section 5 shows NIS model target acquisition probabilities for scenarios where the target and sensor are stationary are also described in terms of the reduced hyperexponential distribution. Section 6 describes phase-type distributions and shows that the exponential and hyperexponential distributions are special cases of phase-type distributions. In this paper, it is shown that FOV or FOR search for a stationary target by a stationary sensor, whether done by an individual or a group of individuals engaged in cooperative or noncooperative search, is described by phase-type distributions. Results and conclusions are summarized in Sec. 7.

2.

Search Background

This section describes search notation and ideas needed to understand new results obtained in the following sections.

2.1.

Search by a Single Observer

Krendel and Wodinsky’s experiment27 provides evidence that search in an unstructured field by a single-well-trained individual is described by an exponential distribution:

Eq. (1)

P(t)=1etτ,0t<,
where P(t) is the target acquisition probability which approaches one since in this experiment the observer always found the target. The parameter τ describes how quickly target acquisition probability approaches one. Target acquisition by a single, stationary soldier searching for a single target in FOV or FOR is described by19,28

Eq. (2)

P(t)=P(1etτ),0t<.

The asymptotic value of P(t) is P, a number less than or equal to one, which reflects the observation that even in time-unlimited search the probability a soldier will find the target is frequently <1. The time constant τ is typically determined experimentally: it goes up with increasing clutter and target range, whereas the parameter P goes down with increasing clutter and target range. The NV-IPM model24,25 estimates P for the average observer as a function of sensor, target, and atmospheric parameters. Equation (2) has been derived19 using probability theory and properties of the human eye. Empirical formulae19 for τ in urban and rural areas using infrared sensors have been tabulated.

The value for τ in Eq. (2) depends on whether one is engaged in FOR or FOV search. For random search in a FOR, the relationship between τFOV and τFOR is19

Eq. (3)

τFOR=NτFOV,
where N describes the number of FOVs needed to fill the FOR. If the sensor is systematically stepped over the FOR, spending a time t0 in each FOV, then the relationship between τFOV and τFOR is19

Eq. (4)

τFOR=(2Ps)2Ps(N1)t0+τFOV;Ps1et0τFOV.

The derivation19 of Eq. (4) assumes N is an integer but Eqs. (3) and (4) yield reasonable results for noninteger N values. Equations (3) and (4) express τFOR in terms of τFOV. An analytical model describing τFOV has not been developed. The parameter τFOV is usually obtained experimentally by curve fitting or by empirical equations for daytime or nighttime long-wave infrared or medium-wave infrared sensors in rural or urban terrain.19

Equation (2) describes how target acquisition probability grows for an observer who acquires a target but does not need to take action to point at the target. If the observer needs to perform some task, say click on the target, before one agrees the target has been acquired, then Eq. (2) needs to be modified as follows:

Eq. (5)

P(t)=P(1ettdτ),tdt<.
Here td is the delay time required to point. For a person moving, a mouse to click on the target, the delay time is typically between 0.5 and 1 s. When td is zero, Eq. (5) reduces to Eq. (2).

Equations (2) and (5) correspond to “time-unlimited” search by a single observer where sensor-target range is constant. For “time-limited” search where the observer has time tL to look for a target19

Eq. (6)

P(t)={0,t<tdPtL(1ettdτFOV1etLtdτFOV),tdttLPtL,tL<t.
Here PtL is the asymptotic target acquisition probability when the observer has time tL to search for the target. When tL is infinite, Eq. (6) reduces to Eq. (5).

2.2.

Moving Sensor and/or Moving Target

It should be realized that Eqs. (2), (5), and (6) apply to scenarios where the target-sensor range is fixed and the background against which the target is seen is unchanging. If the sensor-target range changes or the background against which the target is seen changes then P and τ change and Eqs. (2), (5), and (6) are no longer valid. In that case, target acquisition probabilities are given by the TDSP model.19,20,29 The equations of the TDSP model are too complicated to exhibit here. However, the NV-IPM model has an ability to calculate TDSP model results.24,25

2.3.

Observer Variability

Observers differ in target acquisition ability. In one experiment, carried out with simulated first- and second-generation (gen) imagery, 42 observers searched for targets in 69 simulated first-gen and second-gen images.26,33 Averaged over all the images in a perception experiment, the observers with the highest P value in the first- and second-gen imagery had P values that were 76% and 36% higher than the P value for an average performer. For first- and second-gen images, the best observers had 1/τ value that were 85% and 75% higher than for an average performer. These observations support the view that observers differ substantially in their ability to find targets and the speed with which they do so. This implies target acquisition performance can be substantially improved if target acquisition performance was tested and only the most talented target acquisition people are given the target acquisition task. NV-IPM, the standard model24,25 used by the army to evaluate sensors, predicts P values for the average observer.

Other researchers have modeled search by multiple observers and the first detection of a target in multitarget search.11,12 A distribution different from the exponential or hyperexponential has been proposed to describe target acquisition by a single observer searching for a single stationary target.34

2.4.

Cooperative Search: Stationary Sensor and Target

Cooperative search takes place when the first observer who is certain he/she detected a target lets the other observers know the target has been detected and P(t) is the target acquisition probability for this process. Cooperative target acquisition probability19 for a scenario where several “independent” and “identical” observers search a scene on individual monitors yields an equation which has the same form as Eq. (5):

Eq. (7)

P(t)=Pdet(n,P)[1e(ttd)τmin(n)],tdt<,
where

Eq. (8)

τMin(n)=τm=1nC(n,m)mPm(1P)nm1(1P)n
C(n,m)n!m!(nm)!

Eq. (9)

Pdet(n,P)=1(1P)n.

Note the independence assumption in search is not established and there is conflicting evidence regarding the validity of this assumption in this context. A discussion of this point is given in Sec. 7 of this paper. In Sec. 8, detailed P(t) definitions are given for equations in this paper where this symbol appears. Note that in Eq. (7), Pdet(n,P) plays the role of P and τmin(n) plays the role of τ in Eq. (5). In Eqs. (8) and (9), τ and P are, respectively, the time constant and P value of a single observer doing either FOV or FOR search depending on the scenario. The n in Eqs. (8) and (9) corresponds to the number of identical observers searching for a target in the target acquisition task. Evidence35 that Eqs. (7)–(9) are valid is provided in Figs. 1Fig. 23. Observe that when n=1, in Fig. 1 then Pdet=P.

Fig. 1

The dependence of Pdet in Eqs. (7) and (9) versus single observer detection probability P and the number n of identical observers searching for the target.35 Note the rapid increase in detection probability with n and that when n=1, Pdet=P.

OE_58_9_093103_f001.png

Fig. 2

The dependence of τmin in Eqs. (7) and (8) versus P for a single observer with number of identical observers n as a parameter.35 The parameter τ is target acquisition probability time constant for a single observer. Note the rapid increase in target acquisition speed with increasing number of identical observers.

OE_58_9_093103_f002.png

Fig. 3

Comparison between experiment and model [Eq. (8)]. P and τ are single observer search parameters. Note that when n=10 and P=0.4 that τmin(n)/τ=0.3.

OE_58_9_093103_f003.png

Modeled curves in Fig. 1 were obtained from Eq. (9). Simulated data were obtained by taking random draws from a uniform distribution between 0 and 1. Detection events at the level P=0.2 were obtained by taking a random draw for a uniform distribution between 0 and 1 and assigning detection to draws <0.2 and a similar process was used for other values of P. For 10 observers, a detection event is said to occur if any of the 10 observers detected the target. Simulation was done with 10,000 draws per point.

Modeled curves in Fig. 2 were obtained from Eq. (8). Each simulated point in this figure is an average taken over many outcomes of a random experiment. Take n draws from an exponential distribution with τ=1 resulting in n detection times. To determine if a detection time is accepted, take a draw from a uniform distribution and only accept a detection time draw if the draw is less than P. Thus the number of accepted exponential draws goes down as P decreases. τmin is defined as the smallest of the accepted exponential draws since a target is detected the moment the first observer declares the target is found.

Tremendous improvements in target acquisition probabilities were analytically predicted by Eqs. (7)–(9) and confirmed by simulations in Figs. 1 and 2. Figure 3 shows experimental data35 which supports Eqs. (7)–(9).

Results predicted by Eqs. (7) and (8) illustrated in Figs. 1 and 2 show search performance improves dramatically with increases in number of observers. Figure 2, for example, shows that for scenes with P=0.8 the mean time to find a target with six observers is a little more than 0.2 the mean time to find the target with one observer. A quick defense of these results is that they depend only on (1) the observation that search by an individual is described by an exponential distribution and (2) target acquisition times of different observers are statistically independent. The first condition is supported by the K&W experiment27 and the second condition is supported by Fig. 3.

The validity of Eqs. (7) and (8) depends on the assumption of independent, identical observers whose detection time is described by an exponential distribution so it is important to understand the meaning of identical and independent. In the formalism of probability theory, T1,,Tn are random variables representing the target acquisition times of the n observers. The assumption of identical observers means that T1,,Tn are drawn from the same exponential distribution. The independence assumption means that

P(T1t1,T2t2,,Tntn)=P(T1t1)P(T2t2)P(Tntn).

Less formally, target acquisition times T1 and T2 are statistically independent if the conditional distribution of T1 given T2 is the same as the (unconditional) distribution of T1.

The agreement between the modeled curve in Fig. 3 and the data merits discussion. The modeled curve in Fig. 3 was obtained from Eq. (8). For each P, the value of τ and its standard deviation was measured from experimental data.36 Thus the modeled curve has no fit parameters and detection times were experimentally measured.

A more detailed defense of Eqs. (7) and (8) illustrated in Figs. 1 and 2 follows. The validity of Eqs. (7) and (8) results was first investigated using data36 reported in 2005 which were reanalyzed35 in 2010. These results are shown in Fig. 3 which shows a comparison of mean detection time τmin/τ for 10 observers searching for a target in FOR computer-generated scenes. τmin is defined by min(T1,,T10), where Ti is the detection time of the i’th observer. The definition for τmin is reasonable because when multiple observers search for a target, detection takes place the moment the first observer finds the target. Here τ is calculated in the usual way and represents the mean acquisition time for a single observer representative of the ensemble of observers. The model curve was calculated using Eqs. (7) and (8) with Pdet set equal to one because only events where at least one of the ten observers detected the target were considered in the analysis. Measured probabilities in Fig. 3 were obtained by examining data in Ref. 36 which consist of detection times for a particular scene binned for different P values. Dots in Fig. 3 correspond to τmin/τ values averaged over scenes binned about the plotted P value. Error bars correspond to the standard deviation of τmin/τ. The agreement of measured results in Fig. 3 supports Eqs. (7) and (8) illustrated by Figs. 1 and 2. Other evidence [Eqs. (7) and (8)] are valid is provided in Fig. 5, since these are expressed by Eq. (12) and Eq. (12) reduces to Eqs. (7) and (8) for the special case of identical observers.

2.5.

Cooperative Search: Moving Target and Sensor

Equations (7)–(9) model target acquisition probability when independent and identical observers cooperatively search an FOR or FOV for a stationary target with a stationary sensor. In this section, the requirement for identical observers is no longer assumed. If the target-sensor range is changing or if the target-background contrast is changing, then the target acquisition probability for the i’th observer Pi(t) is obtained from the TDSP model.19,20,29 Suppose target acquisition probabilities for observers 1 and 2 are known having been computed from the TDSP model, i.e., P1(t) and P2(t) are known. Denote the system target acquisition probability for two observers engaged in cooperative search by Ps(2). Then30

Eq. (10)

Ps(2)=P1(t)+P2(t)P1(t)P2(t)=P1+P2P1P2,
where in the second equality the time dependence of P1 and P2 were suppressed for notational convenience. The improvement in target acquisition with cooperative search over individual search is illustrated in Fig. 4.

Fig. 4

Comparison of target acquisition probabilities with observers working alone and cooperatively. P1 and P2 represent target acquisition probabilities from observers 1 and 2 working alone. Observers 1 and 2 are characterized, respectively, by search parameters {P,τ} values of {0.5,4},{0.6,3}. Ps(2) is the system target acquisition probability with observers 1 and 2 searching cooperatively.

OE_58_9_093103_f004.png

The generalization of Eq. (10) for 3 and n observers are, respectively,30

Eq. (11)

Ps(3)=P1+P2+P3P1P2P1P3P2P3+P1P2P3,

Eq. (12)

Ps(n)=i=1nPii<jPiPj+i<j<kPiPjPk(1)n1P1P2Pn.

Equations (10)–(12) are exemplars of the NIS model for 2, 3, and n observers. Detailed definitions of Ps(2), Ps(3), and Ps(n) are given in Sec. 8. Equations (10) and (11) are supported by perception tests.37

Evidence31 that Eqs. (10)–(12) and the generalizations of these equations to a larger number of observers are valid is provided in Fig. 5.

Fig. 5

Modeled and simulated target acquisition probabilities for 2, 4, 6, and 8 stationary observers engaged in search for a stationary target.31 The dashed blue line describes detection experiment measured time-limited (12 s) target acquisition probability using simulated imagery from a second-gen sensor for a single observer search a FOV that has a single target. The solid blue and purple lines are modeled results from Eqs. (10) and (12) for two and four observers engaged in cooperative search. The blue and purple dots correspond, respectively, to two or four draws taken from data used to construct the dashed blue line.

OE_58_9_093103_f005.png

The dashed blue curve in Fig. 5 is an interpolation curve taken from perception data.26,31,38 The blue, purple, tan, and green dots in this figure were obtained by taking 2, 4, 6, or 8 random draws from data used to construct the dashed blue curve. The solid lines in Fig. 5 are modeled results [Eq. (12)]. The good agreement between the dots and the solid curves support the view that Eqs. (10) and (12) are valid. Figure 5 illustrates how cooperative search improves target acquisition probability. At the end of 12 s, the target acquisition probability for the single observer is about 0.3. With two observers at the end of 12 s, the target acquisition probability is about 0.5 and with four observers it is about 0.75.

Knowing details of how Fig. 5 was constructed facilitates a deeper understanding of what this figure means. The dashed curve labeled 1 in Fig. 5 is an interpolation curve taken from perception experiments.26,31,38 The curves labeled 2, 4, and 6 correspond to 2, 4, and 6 observers engaged in cooperative search, which means the observers search independently and the target is found the moment one of the observers involved in the search finds the target, i.e., observers search independently but make other observers aware target is found as soon as one of them finds the target. Figure 5 assumes that identical observers are taking part in the search and each observer is characterized by target acquisition capabilities illustrated by the interpolation curve labeled 1. The solid curves labeled 1, 2, 4, 6, and 8 were calculated using Eq. (12). We describe how the dots in Fig. 5 were constructed by considering the case of 4 observers (similar methods were used to construct the data curves for 2, 6, and 8 observers). For four observers, a random experiment is conducted by taking four random draws from perception experiment data used to construct the curve labeled one. Each experimental result is an outcome belonging to one of two mutually exclusive events: (1) detection or (2) no detection. An outcome is said to result in a detection event if one of the four draws resulted in a detection and the time of the detection is the smallest of the draws that resulted in a detection. An outcome is said to result in no detection if none of the four observers detected the target. After conducting a large number of random experiments, say 1000 we have a list of 1000 data points (each data point is either a detection time, or an indication that no detection took place for that event). Using standard methods, these 1000 data points are converted to dots associated with four observers shown in Fig. 5. More details of how Fig. 5 was constructed are available.31

3.

Target Acquisition Metric for Sensors and Observers

3.1.

Sensor or Observer Target Acquisition Metric

In this section, a simple metric is proposed that can be used to rank target acquisition capabilities of observers and sensors. The ability of an observer to quickly find a target has great military value: a tank commander who finds an enemy tank before the enemy tank has found him can carefully aim and destroy the enemy tank before the enemy tank even knows he is there.

3.2.

Background

Perception search experiments26,28 intended to compare target acquisition performance of first- and second-gen sensors had an interesting result. In these experiments, scenes, targets, target locations, and FOV were identical for first- and second-gen sensors. The differences between the two sets of imagery is that first-gen imagery was blurred more than the second-gen imagery reflecting the empirical fact that first-gen sensors are typically more blurred than second-gen sensors. Perception experiment results revealed P and τ were higher for second-gen sensors than they were for first-gen sensors. The results made sense. Since second-gen sensors have more detail, more difficult targets could be found which explains why P went up. Also because second-gen imagery had more detail than first-gen imagery, observers took longer to finish searching a second-gen image. Difficult targets were found after a long time in second-gen imagery that were not found in first-gen imagery, which caused second-gen imagery to have a larger mean time then first-gen imagery. If one took P and τ averaged over observers and scenes as a measure of sensor target acquisition capability, because second-gen sensors had a higher τ value than first-gen sensors they might not seem to be the obvious choice for the preferred target acquisition sensor. Empirically, it is known that second-gen sensors are superior to first-gen sensors in target acquisition. The problem is P and τ are natural parameters for describing search but are not appropriate metrics for ranking sensor target acquisition capability.

3.3.

Solution

Equation (2) implies that the slope at the origin is P/τ, the initial rate for acquiring a target. Figure 6 illustrates this result. What happens is that τ is a little larger for second-gen sensors than for first-gen sensors, but P is a lot larger for second-gen sensors than for first-gen sensors. The net result is that the initial slope of target acquisition probability is greater for second-gen sensors than it is for first-gen sensors.

Fig. 6

Illustration of single observer target acquisition probability P(t), P, τ and the slope at t=0. The slope at the origin is P/τ.

OE_58_9_093103_f006.png

3.4.

Conclusion

P and τ are natural parameters for describing target acquisition probability but when averaged over observers and scenes are not good measures of sensor performance for target acquisition. A good overall33 measure of sensor target acquisition performance is P/τ averaged over observers and scenes. Similarly, a measure of observer target acquisition capability is P/τ averaged over scenes for a particular sensor.

4.

Noncooperative Search by Observers with Different Search Capabilities

This section describes why the hyperexponential distribution is a more accurate description of search performance than the exponential when it is carried out by more than one observer. This result depends on the observation that individuals vary in search capability.33,39

It is important to understand the distinction between noncooperative and cooperative search. In noncooperative search, each observer searches until they find the target or the time allocated to search is used up, whereas in cooperative search each observer stops searching as soon as the first observer is confident he/she has found the target. Noncooperative search is often used in search experiments and might be used in the field if observers could not communicate with one another. Our theory requires the assumption of independent observers for cooperative search but not for noncooperative search.

It is important to understand the distinction between the symbols P(t) and Pc(t). Target acquisition time is sampled uniformly from among the set of observers who have found the target or from the set of all observers. Target acquisition probability is denoted by Pc(t) in the former case and P(t) in the latter. Less formally, all observers taking part in the perception experiment are considered when calculating P(t), whereas only observers who found the target are considered when calculating Pc(t).

4.1.

Two Sets of Observers

Consider the case where a group of n1 identical stationary observers each characterized by search parameters P1 and τ1, and a second group of n2 identical stationary observers each characterized by search parameters P2 and τ2 search for a stationary target in an image produced by a stationary sensor. Although it is difficult to get and train observers so they have nearly identical search performance, it has already been done for several observers27,40 and conceptually it could be done for any number of observers. Thus we are free to consider the case where n1 and n2 are large. For this case, the expected number of detections among all observers is given by

Dtot=n1P1+n2P2.
Of the expected number of detections, n1P1 are from the first group of observers and n2P2 are from the second group of observers. The first and second groups of observers detect targets with time constants τ1 and τ2, respectively. Thus the cumulative distribution function (CDF) for this scenario is

Eq. (13)

Pc(t)=α1(1eλ1t)+α2(1eλ2t),0t<,
where
αi=niPin1P1+n2P2,λi=1τi,i=1,2.

For tmax(τ1,τ2), the exponentials are essentially zero which shows that Eq. (13) asymptotically approaches α1+α2 which is one. Thus Eq. (13) is a hyperexponential CDF. Equation (13) describes how target acquisition probability grows with time for those observers who eventually find the target.

It is of value to calculate target acquisition probability for all observers taking part in the experiment. Some observers detect the target, others do not. By hypothesis, the total number of observers taking part in the experiment is n1+n2. The estimated number of detections is unchanged from the estimate made to compute Eq. (13). In this case, target acquisition probability is given by

Eq. (14)

P(t)=1n1+n2[n1P1(1eλ1t)+n2P2(1eλ2t)],0t<.
For large t, P(t) asymptotes to (n1P1+n2P2)/(n1+n2) which is less than or equal to one since Pi are probabilities less than or equal to one. Because Eq. (14) does not asymptote to one, we call it the reduced CDF.

The probability density function associated with Eq. (13) is obtained by differentiating with respect to time

Eq. (15)

pc(t)=α1λ1eλ1t+α2λ2eλ2t,0t<.

Equations (13)–(15) apply to a scenario where there are two large sets of observers and each set has observers with nearly identical search performance. In practice, it is hard to get a large number of observers looking for a target and harder yet to get a large number of observers with nearly identical search performance. For that reason, these equations are conceptually useful but of limited practical utility. One use of these equations is to specialize them to the frequently occurring case where n1=n2=1.

4.2.

Two Individual Observers

When n1=n2=1, Eqs. (13)–(15) become

Eq. (16)

Pc(t)=P1P1+P2(1eλ1t)+P2P1+P2(1eλ2t),

Eq. (17)

P(t)=12[P1(1eλ1t)+P2(1eλ2t)],

Eq. (18)

pc(t)=P1P1+P2λ1eλ1t+P2P1+P2λ2eλ2t.
For typographical convenience, in Eqs. (16)–(18), restrictions on t are not explicitly stated.

4.3.

Three Individual Observers

The method already used for two individual observers can be extended to three individual observers

Eq. (19)

Pc(t)=P1iPi(1eλ1t)+P2iPi(1eλ2t)+P3iPi(1eλ3t),

Eq. (20)

P(t)=13[P1(1eλ1t)+P2(1eλ2t)+P3(1eλ3t)],

Eq. (21)

pc(t)=P1iPiλ1eλ1t+P2iPiλ2eλ2t+P3iPiλ3eλ3t,
where in Eqs. (19) and (20), the symbol iPi is short for P1+P2+P3.

4.4.

N Individual Observers

The extension of Eqs. (19)–(21) to N observers is straightforward:

Eq. (22)

Pc(t)=1i=1NPii=1Nαi(1eλit),αi=Pii=1NPi,

Eq. (23)

P(t)=1Ni=1NPi(1eλit),

Eq. (24)

pc(t)=1i=1NPii=1NPiλieλit.

4.5.

Applications

Results of this section are applicable to search experiments intended to determine P and τ.

4.6.

Conclusion

Equations (22) and (23) are, respectively, a hyperexponential distribution with αi=Pi/i=1NPi and a reduced hyperexponential distribution. FOV or FOR search where the target and sensor are stationary is described by a reduced hyperexponential distribution. When the observers have identical search capabilities, the reduced hyperexponential simplifies to a reduced exponential distribution.

5.

Cooperative Search by Observers with Different Search Capabilities

Cooperative search by two, three and n observers where the sensors and targets are either stationary or moving is described by Eqs. (10)–(12).30 Development of the equations in this section requires independent observers. In general, Pi, i=1,2,,n are functions of time and are obtained from the TDSP model.19 Here we consider the case where the sensors and target are stationary to show that for this case target acquisition probability is a reduced hyperexponential distribution. To simplify notation, the derivation given here is for two observers but the result is true for any number of observers.

5.1.

Derivation for Two Observers

Substitute Pi=Pi(1etλi), i=1,2 into Eq. (10) to get

Eq. (25)

Ps(2)=P1+P2P1P2[P1(1P2)etλ1+P2(1P1)etλ2+P1P2et(λ1+λ2)].

Let Ps denote system asymptotic target acquisition probability. Then for the case of two observers:

Eq. (26)

Ps=P1+P2P1P2.

Using this result, Eq. (25) becomes

Eq. (27a)

Ps(2)=Ps{1[α1etλ1+α2etλ2+α3et(λ1+λ2)]},
where

Eq. (27b)

α1=P1(1P2)Ps,α2=P2(1P1)Ps,α3=P1P2Ps.
Equation (27b) implies

Eq. (27c)

i=13αi=1.
An equation of the form
Pc(t)=1α1etλ1α2etλ2α3etλ3,
which satisfies Eq. (27c) is said to be a hyperexponential distribution. In Eq. (27a), the quantity multiplied by Ps is the hyperexponential distribution. Equation (27a) asymptotes to Ps, a value <1, and for that reason is called a reduced hyperexponential distribution.

5.2.

Conclusion

We have shown that cooperative search by two independent observers is characterized by a reduced hyperexponential distribution. Similarly, Eqs. (11) and (12) and the generalization of those equations to an arbitrary number of observers is described by a reduced hyperexponential distribution. The derivation given here starts from the assumption that Eq. (10) is valid. A derivation from first principles that the hyperexponential distribution applies to cooperative search is given in Sec. 9.

6.

Phase-Type Distributions

To the best of our knowledge, this paper is the first to apply the methodology of phase-type distributions to search. No new models are presented in this section. Instead, we show that some of the results already given in Secs. 2, 4, and 5 can be more elegantly expressed using phase-type distributions. Just like Newton’s law of motion can be expressed in terms of the Lagrange’s or Hamilton’s equations, the K&W exponential distribution27 result which applies to a single observer can be generalized to cooperative or noncooperative search using phase-type distributions. Simplifying a little, the K&W exponential distribution is described by Eq. (1); phase-type distributions are also described by Eq. (1) only 1/τ is replaced by a matrix S and the exponential is multiplied by a row vector. It is remarkable that search by multiple observers is described by a generalization of the exponential distribution. Phase-type distributions are used extensively by computer scientists and engineers who study the performance of computer systems and networks41 and by operations research analysts who study queuing theory.42 The value of this section is that it provides a link between search theory on one hand and computer networks and queuing theory on the other. Cross fertilization of ideas between these fields may be beneficial.

In Secs. 4 and 5, it was shown that both cooperative and noncooperative target acquisition by multiple observers is described by a reduced hyperexponential distribution. For a single observer, the reduced hyperexponential distribution simplifies to a reduced exponential distribution. In this section, we point out that the exponential and hyperexponential distributions are special cases of phase-type distributions. This section applies phase-type distribution methodology to search scenarios described by exponential and hyperexponential distributions.

6.1.

Theory of Phase-Type Distributions

The probability density function p(x) for a phase-type distribution is given43 by

Eq. (28a)

p(x)=aexp(xS)S0,x>0,
where α is a row vector of weights:

Eq. (28b)

α(α1,α2,α3,,αm),
where αi0 and i=1mαi=1. As will be seen later, S is a m×m matrix, which determines the form of the particular phase-type distribution and S0 is defined by the relationship S0=S1, where 1 represents a m×1 column vector of ones.

It is important to know that an exponential raised to a matrix power is calculated using a Taylor series expansion:

Eq. (29)

exp(M)=k=0Mkk!=M0+M11!+M22!+.

This allows us to show that p(x) in Eq. (28a) is a scalar. Since any power of a m×m matrix is a m×m matrix, Eq. (29) implies exp(xS) is a m×m matrix. The definition of S0 implies that it is a m×1 vector. The product exp(xS)S0 is thus a m×1 column vector. This is premultiplied by α, a 1×m vector, to produce a scalar.

The CDF P(x) for a phase-type distribution is given by43

Eq. (30)

P(x)=1αexp(xS)1.

Realize that αexp(xS)1 is a scalar. This implies P(x) in Eq. (30) is a scalar.

When m=1, Eq. (30) reduces to the exponential distribution described by Eq. (1) because then α and S0 have just one component and are scalars. The condition that the sum over i of αi is one implies α=1. When m>1, Eqs. (28a), (28b), and (29) generalize the exponential distribution.

6.2.

Computer Implementation of Phase-Type Distributions

In this section, we show that the exponential and hyperexponential distribution are special cases of phase-type distributions. Work with phase-type distributions is facilitated by computer implementation because of the difficulty in evaluating Eq. (29) by hand. Mathematica code for computer-generated PDFs and CDFs for phase-type distributions is shown in Figs. 7 and 8.

Fig. 7

Mathematica code for implementing Eq. (28a). Here f is the PDF determined by input row vector α and matrix S.

OE_58_9_093103_f007.png

Fig. 8

Code for implementing Eq. (30). Here F is the CDF determined by input vector α and matrix S.

OE_58_9_093103_f008.png

Several examples are provided which demonstrate how to use these functions.

6.2.1.

Exponential random variable

Figure 9 demonstrates how to use the code shown in Figs. 7 and 8 to calculate the exponential distribution.

Fig. 9

Technique for calculating the PDF and CDF of an exponential random variable.

OE_58_9_093103_f009.png

The first line of Fig. 9 defines the α row and the S matrix appropriate to the exponential distribution. The set of braces enclosing 1 and the double set of braces enclosing λ tell Mathematica that 1 is a row vector and λ is a matrix. The second line computes the PDF and CDF which are input as row vectors. The third line is the output of the second line and displays the calculated PDF and CDF as row vectors. The reduced CDF is obtained by multiplying the CDF by P.

6.2.2.

Hyperexponential random variables (noncooperative search)

Recall from Sec. 4 that noncooperative search by observers with individual search characteristics is described by the hyperexponential distribution. Figure 10 shows how to use phase-type distribution methodology to calculate those distributions.

Fig. 10

Technique for calculating the PDF and CDF of a hyperexponential random variable for three observers engaged in noncooperative search.

OE_58_9_093103_f010.png

The first two lines of Fig. 10 define the appropriate a and S parameters. The hyperexponential PDF and CDF are calculated in the third line and the results are shown in the fourth and fifth line. Hyperexponential PDFs and CDFs of different order can be calculated by suitably adjusting the number of entries in S and α, i.e., adjust the number of λ values on the main diagonal of S and adjust the number of a values so that i matches order of the S matrix. The αi, i=1,2,3,, for noncooperative search are given by Eq. (22). The reduced CDF is obtained by multiplying the CDF by the asymptotic system target acquisition probability Ps.

The hyperexponential PDF and CDF for the case of three observers in noncooperative search is

Eq. (31)

p(t)=α1λ1etλ1+α2λ2etλ2+α3λ3etλ3,α1+α2+α3=1,

Eq. (32)

Pc(t)=1α1etλ1α2etλ2α3etλ3,α1+α2+α3=1,

Eq. (33)

Ps(3)=PsPc(t),
where Ps is given by Eq. (11) with Pi replaced by Pi. Figure 10 is in agreement with Eqs. (23)–(26).

6.2.3.

Hyperexponential random variables (cooperative search)

The technique for calculating the cooperative hyperexponential distribution for two independent observers is shown in Fig. 11.

Fig. 11

Technique for calculating the PDF and CDF of a hyperexponential random variable for two observers engaged in cooperative search.

OE_58_9_093103_f011.png

The first two lines of Fig. 11 define the appropriate α and S parameters. The hyperexponential PDF and CDF are calculated in the third line and the results are shown in the fourth and fifth lines. The appropriate values for α1, α2, and α3 are given by Eq. (27b).

As illustrated in Fig. 12, the technique for calculating the appropriate PDF and CDF for three observers engaged in cooperative search is more intricate than that for two observers.

Fig. 12

Technique for calculating the PDF and CDF of a hyperexponential distribution for three observers engaged in cooperative search.

OE_58_9_093103_f012.png

The first two lines of Fig. 12 define the appropriate α and S parameters. The hyperexponential PDF and CDF are calculated in the third line. The fourth and fifth lines display the PDF associated with the input α and S parameters and the last line displays the CDF for this hyperexponential distribution. The reduced CDF is obtained by multiplying the CDF by Ps.

We need to generalize Eq. (27b) to the case of three observers, that is, we need to identify how individual α’s relate to individual Pi. The generalization of Eq. (27b) for α1 is α1=P1(1P2)(1P3)/Ps with similar expressions for α2 and α3. The coefficient for α1,2 is α1,2=P1P2(1P3)/Ps with similar expressions for α1,3 and α2,3. The coefficient for α1,2,3 is α1,2,3=P1P2P3. In general, α subscripts match the λ numerals in the S matrix and the alpha coefficients describe which exponentials survive given a combination of P values for different observers that are either zero or one. Thus only the λ1 exponent survives with P1=1, P2=P3=0. Similarly, only the (λ1+λ2+λ3) exponent survives when P1=P2=P3=1. The value for Ps is found from Eq. (11) by replacing Pi in that equation by Pi.

6.3.

Conclusions

In Secs. 4 and 5, we have shown there is reason to believe that when multiple nonidentical observers search for a stationary target with a stationary sensor, the reduced hyperexponential distribution is a better model than the reduced exponential distribution for describing target acquisition of a stationary target by stationary sensors. Here we have shown that the hyperexponential distribution can be expressed using the phase-type distribution methodology frequently employed in queuing theory.42 It is anticipated that this section will foster a connection between queuing and search theory that will be mutually beneficial to both subjects. The neoclassical search model21,23 is couched in the language of random transitions between different observer states and it may be that this model can be described more simply using phase-type distributions.

7.

Summary of Results and Conclusions

7.1.

Summary of Known Results

Research pertinent to the work done here and evidence for believing that the research is valid was discussed in Sec. 2. Time-unlimited target acquisition probabilities for scenarios where the sensor and target are both stationary when search is done by a single observer or by many observers was described. These results were generalized to time-limited search and finally the results were generalized further to the case where the observer, the target, or both are moving. Experimental evidence (Fig. 3) showing how the mean time to detect a target decreased with increasing P was compared with a model with excellent agreement. Simulations of cooperative search which assumed search by individual independent observers are described by an exponential distribution are in excellent agreement with modeled results (Figs. 1 and 2). It is obvious that for target acquisition, two heads are better than one. How much better is quantified by Eqs. (10)–(12) and illustrated in Fig. 4. The model was tested in a simulation that used experimental data in Fig. 5 with excellent agreement between model and experiment.

7.2.

Summary of New Results

In Sec. 4, it was shown that target acquisition by multiple observers, who differ in target acquisition skills, is described by a hyperexponential rather than an exponential distribution. In Sec. 5, it was shown that cooperative target acquisition is also described by a hyperexponential distribution. The α parameters and the order of the hyperexponential are different for noncooperative and cooperative search and methods for calculating α parameters was presented. Mathematica code was developed to calculate PDFs and CDFs for phase-type distributions and this code was applied to calculating hyperexponential distributions appropriate to cooperative and noncooperative search.

Target acquisition probabilities for a scenario with a stationary sensor and target are naturally described using parameters τ and P. Sensors can also be described using these parameters by doing target acquisition perception experiments (stationary target and stationary sensor) with an ensemble of observers over a large number of images. When this was done with simulated first- and second-gen sensors, it was found that second-gen sensors had higher P and τ values than first-gen sensors. The fact that second-gen sensors had a larger τ value than first-gen sensors could be disturbing. Analysis showed that the efficacy of sensors for target acquisition is better ranked using P/τ and that second-gen sensors had a higher P/τ value than first-gen sensors.

Observers too can be ranked for target acquisition efficacy using P/τ values by doing perception experiment over a large number of images with different imaging sensors. Experiment showed that observers differ substantially in target acquisition capabilities.

We emphasize: (1) the hyperexponential distribution in Sec. 4 does not rely on the independence assumption but does rely on the observation that observers differ in search capability and (2) the hyperexponential distribution in Sec. 5 does rely on the independence assumption but not on the different capabilities of the observer.

7.3.

Conclusions

We have shown that sometimes target acquisition distributions are given by the exponential distribution, sometimes they are given by the hyperexponential distribution, and for the case where the sensor or target or both are moving, target acquisition distribution results are predicted by the TDSP and NIS models and in general are not a named distribution.

Evidence for the above conclusion follows. Experimental27,44,45 and theoretical19 evidence supports the belief that the exponential distribution describes search by an individual observer. Evidence also supports the validity of the TDSP20,29 and NIS30,31 models. The validity of the hyperexponential distribution of Sec. 4 on noncooperative search depends on two observations: (1) search by an individual is described by an exponential distribution and (2) observers substantially differ in their search capabilities. The validity of the exponential distribution is generally accepted.27,44,45 Evidence33,39 is expected and established that observers differ substantially in their search capabilities. Although there is no direct experimental evidence for the validity of the hyperexponential distributions described in Sec. 4, it is a direct logical consequence of the observations 1 and 2 that search described by an individual is described by an exponential distribution and observers differ substantially in their search capabilities and both of these observations are supported by experiment.

The validity of the hyperexponential distribution of Sec. 5 on cooperative search depends on observation 1 as well as an assumption 2′ that observers search independently. The validity of the hyperexponential distributions of Sec. 5 is a logical consequence of observation 1 and assumption 2′. We note the validity of the independence assumption used in much of our work is subject to debate.

7.3.1.

Evidence for independent observers

(1) Figure 3 presents evidence that predictions based on the independence assumption are valid. (2) It has been shown that search is more effective if multiple observers participate in search.46 The results of the theory developed here, illustrated in Fig. 5 also support the view that search is more effective with multiple observers.

7.3.2.

Evidence against independent observers

For two observers, Fig. 4 in Ref. 47 graphs the probability of joint missed detections against the product of the probability for individual missed detections for targets of 50% and 2% prevalence. If the missed detections are independent, these two probabilities would be the same and fall on a straight line with unity slope. The experimental data clearly fall above the straight line showing that missed detections are not independent. This was also done for false alarms, which were also shown to be not independent. This suggests that detection events by two observers are not independent.

7.3.3.

Conclusion on the independence assumption

More experiments are needed to determine the conditions under which search by multiple observers are well modeled using the independence assumption.

Methods for finding the appropriate distribution for a specified target acquisition scenario are described in this paper.

A parameter which characterizes target acquisition capability in a sensor or observer is P/τ. For a sensor perception test, data are averaged over observers, whereas for observer perception tests, data are averaged over images. This belief is supported using data used in Refs. 26 and 28 which was analyzed in Ref. 33.

This is the first paper to show that target acquisition probabilities by multiple observers can be described using phase-type distributions and the method for doing this was illustrated. Although no new models were found using this technique, we are hopeful it will lead to new search insights which may come from the computer systems performance and queuing communities where phase-type distributions are widely used.

Because observers differ substantially in target acquisition capability, it is suggested observers be tested for target acquisition capability and assigned target acquisition responsibilities based on their capability. A technique for testing observers has been described.33

False alarms have been ignored in this paper because our proposed method of search yields a negligible number of false alarms. Search is done in the wide field of view (WFOV) and confirmed in the narrow field of view (NFOV). Targets initially found in the WFOV can easily be false alarms but we assume that in switching to the NFOV almost all false alarms are rejected. Results for cooperative search illustrated in Fig. 5 indicate substantial improvements in detection probability and initial rate of detection with increases in observers. For that reason, achieving objective 2 below is especially important.

Arguably, the three most important unsolved target acquisition problems are: (1) develop a model which describes the mean FOV target detection time τFOV, (2) determine if search by observers who do not communicate with one another until the object is found search independently, and (3) determine how to model target acquisition of low-prevalence targets.

8.

Appendix A: The Meaning of Noncooperative and Cooperative Target Acquisition Probability

Although the target acquisition probabilities in Eqs. (1), (2), (5)–(7), and (10)–(12) are all denoted by the symbol P(t) and are all properly termed target acquisition probabilities, the distinction among these probabilities may escape some readers. This appendix is written to make the distinction among these probabilities clear to the reader.

Equation (1). An ideal experiment for which Eq. (1) applies is described. The subject is asked to detect a circular spot (the target) that is brighter than the uniform circular background against which the target is seen. The angular size of the target, the angular size of the circular field to be searched, and the contrast between the target and background are adjusted so that finding the target is challenging, but once the target is found the contrast and target size is such that the observer is confident this is not a false alarm and is indeed the target. The observer is given unlimited time to detect the target and since the observer knows a target is present, with persistence the observer always finds the target. The observation that Eq. (1) asymptotes to one reflects this reality. Because of the structureless background, the difficulty in finding the target did not depend on where the target is located in the visual field. For a fixed angular size target with fixed contrast and fixed visual field size, the experiment can be done N times. The detection time is a random variable. Out of the N trials, let n(t) denote the number of times the target is detected in a time less than or equal to t. Then in Eq. (1), the definition of P(t) is

Eq. (34)

P(t)=n(t)N.

Equation (2). A thought experiment for which Eq. (2) applies is described. Suppose N identical observers have individual monitors showing identical images from an imaging sensor. The scene is typical of what might be seen in a military context: there are trees, rocks, bushes, and perhaps dirt roads in the scene. The scene may or may not have a military target but never has more than one target. The observer’s task is to find the military target using the sensor’s WFOV. In the WFOV military targets cannot be clearly distinguished from the background so sometimes an observer clicks on a spot where no target is present, i.e., sometimes there are false alarms. When a detection is made, the observer clicks the place where the target is the moment, the target is detected, and this time, a random variable, is recorded. In this experiment, each observer is only allowed one click on an image if the observer believes a target is present or no click if the observer believes no target is present. If a target is present its location is known to personnel running the experiment which enables grading of observer responses. Let n(t) denote the number of times the target is detected in a time less than or equal to t. Then in Eq. (2), P(t) is defined by Eq. (34).

Equation (5). The same thought experiment which applies to Eq. (2) also applies to Eq. (5). For Eq. (5), it is assumed the observer takes a time td to go from target detection to clicking on the target.

Equation (6). The same thought experiment which applies to Eq. (5) also applies to Eq. (6). In Eq. (6), it is assumed the observer has time tL to click on the target. Any clicks on the image after time tL are ignored.

Equation (7). Here n identical observers engaged in time-unlimited search are looking at individual monitors each showing an image produced by a stationary camera looking at a rural scene that may or may not contain a single stationary military target, e.g., a tank. The target-background-contrast-sensor-range is such that the probability any single observer detects the target is P and this is known from NV-IPM model. Target detection time for any single observer is a random variable with mean τ. A target is said to be detected the moment any one of the n observers is certain the military target is detected. Each observer is allowed one click, searches with the sensor in the WFOV mode but switches to NFOV mode to make certain it is a target that was seen in WFOV mode. The td in Eq. (7) corresponds to the time to switch from WFOV to NFOV plus the time to take some action to indicate the location of the target, i.e., click on the target or put crosshairs on the target. Suppose now that the n identical observers are memoryless, i.e., they do not remember where the target is from one trial to another, so the experiment can be repeated as many times as desired. The detection time for this process is a random variable. Let Tmin(n) denote the mean detection time for that process, N denotes the number of trials which have a target, and n(t) denotes the number of detections in those N trials that take place in a time less than t. Then in Eq. (7), P(t) is defined by Eq. (34).

Equation (10). Here two observers with different search capabilities are engaged in search for a single target. The observers may be stationary or moving and the target may be stationary or moving. Target acquisition probabilities P1(t) and P2(t) refer, respectively, to observers 1 and 2 searching separately and are calculated using the methods of the TDSP model which have been programmed into NV-IPM. Equation (10) applies to FOV and FOR search, an input to the TDSP model. As in Eq. (7), a target is said to be detected the moment the first of the two observers engaged in search detect the target. Imagine the two observers are memoryless and the search process described above is repeated N times in searches that contain a target. The detection time for the search process described above is a random variable. In the N searches, let n(t) denote the number of detections in a time less than or equal to t. Then in Eq. (10), P(t) is defined by Eq. (34).

Equations (11) and (12). Comments already given for Eq. (10) apply to these equations with appropriate modifications that reflect these equations apply to three and four observers instead of two observers.

9.

Appendix B: Cooperative Search and Hyperexponential Distribution

In this section, it is directly shown that target acquisition probability Eq. (33), appropriate to two observers, can be derived from first principles without assuming the validity of Eq. (10). The result obtained here for two observers can be extended to any number of observers. However, doing so requires a more complicated notation and a more difficult to understand derivation.

9.1.

Derivation

Express Eq. (2) in terms of λ and a random variable T, the time a single Soldier detects the target. Then

Eq. (35)

P(t)P(T<t)=P(1eλt),0t<,
where λ1/τ and P is needed because even with time-unlimited search there is some probability the observer will not find the target. Let D and D¯, respectively, denote the event that a target was or was not detected. Thus the probability that a Soldier eventually detects the target P(D)=P. Since D and D¯ exhaust the space P(D¯)=1P. The conditional probability given that the target is found is

Eq. (36)

P(T<t|D)=1eλt,0t<.

Consider two observers with detection times given by independent random variables T1 and T2. The event that each observer eventually finds the target is now denoted by D1 and D2, respectively. When two observers search, a target is found as soon as either observer finds the target. Let Ts denote the system time for target detection. Then

Eq. (37)

Ts=min(T1,T2).

Let Ds denote the system detection event which means Soldier 1 or Soldier 2 or both detect the target. It is possible that given as much time as desired neither Soldier finds the target. Let Ps denote the probability that either Soldier detects the target. Then P(Ds)=Ps. We seek the CDF associated with the random variable Ts. To get the CDF, it is convenient to first calculate P(Ts>t) as follows:

Eq. (38)

P(Ts>t)=P(Ts>t|D¯1D¯2)P(D¯1,D¯2)+P(Ts>t|D1,D¯2)P(D1,D¯2)+P(Ts>t|D¯1,D2)P(D¯1,D2)+P(Ts>t|D1,D2)P(D1,D2),
where P(D¯1,D¯2) means the joint probability of D¯1 and D¯2. The equality in Eq. (38) follows from the law of total probability since the conditional events are mutually exclusive and exhaust the space. The first term corresponds to neither observer detecting the target, the second term corresponds to only the first observer detecting the target, the third term corresponds to only the second observer detecting the target, and the last term corresponds to both observers detecting the target. The assumption that the random variables T1 and T2 are independent allows us to write

Eq. (39a)

P(D¯1,D¯2)=P(D¯1)P(D¯2)=(1P1)(1P2)=1(P1+P2P1P2)=1Ps.

The last equality follows from the observation:

Eq. (39b)

Ps=P(Ds)=P(D1D2)=P(D1)+P(D2)P(D1D2)=P1+P2P1P2.
Similarly,

Eq. (39c)

P(D1,D¯2)=P1(1P2),

Eq. (39d)

P(D¯1,D2)=(1P1)P2,

Eq. (39e)

P(D1,D2)=P1P2.

Referring to Eq. (38), we need to evaluate P(Ts>t|D¯1D¯2). It must be that

Eq. (40a)

P(Ts>t|D¯1D¯2)=1.
Since given that neither observer detects the target, Ts is certainly greater than any finite time. Note that

Eq. (40b)

P(Ts>t|D1,D¯2)=P(Ts>t)|D1)=eλ1t,

Eq. (40c)

P(Ts>t|D¯1,D2)=P(Ts>t|D2)=eλ2t,

Eq. (40d)

P(Ts>t|D1,D2)=P(T1>t,T2>t|D1D2)=P(T1>t|D1)P(T2>t|D2)=eλ1teλ2t=e(λ1+λ2)t.

Equation (40d) provides a derivation of the well-known property that the minimum of two independent exponential variables with parameters λ1 and λ2 has an exponential distribution19,48 with parameter λ1+λ2.

Using Eqs. (39a)–(39e) and (40a)–(40d), Eq. (38) becomes

Eq. (41a)

P(Ts>t)=(1Ps)+P1(1P2)eλ1t+(1P1)P2eλ2t+P1P2e(λ1+λ2)t.

The last equation simplifies to

Eq. (41b)

P(Ts>t)=1Ps[1α1eλ1tα2eλ2tα1,2e(λ1+λ2)t],
where
α1P1(1P2)Ps,α2(1P1)P2Ps,α1,2P1P2Ps.
It is easy to verify that α1+α2+α1,2=1. Thus the quantity within the parenthesis in Eq. (41b) is a hyperexponential distribution. We are really interested in Ps(t)=P(Tst)=1P(Ts>t). Using Eq. (41b)

Eq. (42)

Ps(t)=Ps[1α1eλ1tα2eλ2tα1,2e(λ1+λ2)t].
Equation (42) is identical to Eq. (33).

9.2.

Conclusion

In this section, the application of the hyperexponential distribution to cooperative search was derived from first principles.

Acknowledgments

We thank anonymous reviewers whose perceptive comments improved this paper.

References

1. 

B. O. Koopman, Search and Screening: General Principles with Historical Applications, Pergamon Press, New York (1980). Google Scholar

2. 

L. D. Stone, Theory of Optimal Search, Academic Press, New York (1975). Google Scholar

3. 

A. R. Washburn, Search and Detection, 4th ed.Institute for Operations Research, Linthicum, Maryland (2002). Google Scholar

4. 

L. D. Stone, J. O. Royset and A. R. Washburn, Optimal Search for Moving Targets, Springer International Publishing, New York (2016). Google Scholar

5. 

N. P. Travnikova, Efficiency of Visual Search, Mashinostroyeniye, Moscow (1984). Google Scholar

6. 

N. P. Travnikova, Ergonomics of Human Visual Activity, Mashinostroenie, Leningrad (1989). Google Scholar

7. 

M. J. F. Braga, “An introduction to search theory,” Naval Postgraduate School, (1974). Google Scholar

8. 

J. P. Mardell, “Assisting search and rescue through visual attention,” Imperial College, London, (2015). Google Scholar

9. 

F. E. Skirlo, “Improving bandwidth efficiency and performance for unmanned aerial systems conducting target detection,” George Mason University, Fairfax, Virginia, (2018). Google Scholar

10. 

F. E. Skirlo et al., “Comparison of relative effectiveness of video with serial visual presentation for target reconnaissance from UASs,” Proc. SPIE, 9820 982008 (2016). https://doi.org/10.1117/12.2224796 PSISDG 0277-786X Google Scholar

11. 

S. R. Rotman, E. S. Gordon and M. L. Kowaslczyk, “Modeling human search and target acquisition performance: I. First detection probability in a realistic multitarget scenario,” Opt. Eng., 28 (11), 281216 (1989). https://doi.org/10.1117/12.7977122 Google Scholar

12. 

S. R. Rotman, “Modeling human search and target acquisition performance: II. Simulating multiple observers in dynamic scenarios,” Opt. Eng., 28 (11), 281223 (1989). https://doi.org/10.1117/12.7977123 Google Scholar

13. 

S. R. Rotman, E. S. Gordon and M. L. Kowaslczyk, “Modeling human search and target acquisition performance: III. Target detection in the presence of obscurants,” Opt. Eng., 30 (6), 824 –829 (1991). https://doi.org/10.1117/12.55852 Google Scholar

14. 

G. Tidhar et al., “Modeling human search and target acquisition performance: IV. Detection probability in the cluttered environment,” Opt. Eng., 33 (3), 801 –808 (1994). https://doi.org/10.1117/12.160980 Google Scholar

15. 

A. Toet, P. Biel and J. M. Valeton, “Image dataset for testing search and detection models,” Opt. Eng., 40 (9), 1756 –1759 (2001). https://doi.org/10.1117/1.1410760 Google Scholar

16. 

A. Toet, P. Bijl and J. M. Valeton, “A test of three visual search and detection models,” Proc. SPIE, 3699 323 –334 (1999). https://doi.org/10.1117/12.352960 PSISDG 0277-786X Google Scholar

17. 

J. Johnson and W. R. Lawson, “Performance modeling methods and problems,” in Proc. IRIS Spec. Group Imaging, (1974). Google Scholar

18. 

J. D. Howe, “Electro-optical imaging system performance prediction,” Infrared Electro-optical Systems Handbook, Electro-Optical Systems Design, Analysis and Testing, 4 55 –120 SPIE, Bellingham, WA (1993). Google Scholar

19. 

M. Friedman, “Fundamental search relationships and their application to field of regard search, search by multiple observers, search from a moving vehicle, and multitarget search,” Opt. Eng., 52 (4), 041107 (2013). https://doi.org/10.1117/1.OE.52.4.041107 Google Scholar

20. 

M. Friedman et al., “Validating an analytical technique for calculating detection probability given time-dependent search parameters,” Proc. SPIE, 8355 835511 (2012). https://doi.org/10.1117/12.921020 PSISDG 0277-786X Google Scholar

21. 

J. F. Nicoll, “The neoclassical search model,” (1994). Google Scholar

22. 

J. F. Nicoll, “A mathematical framework for search: the neo-classical model,” in Proc. IRIS Passive Sens. Spec. Group, (1994). Google Scholar

23. 

J. F. Nicoll, “The neoclassical search model,” in Proc. Ground Target Model. and Validation Conf., (1994). Google Scholar

24. 

E. M. Burdette et al., “Comparative performance of large-format MWIR and LWIR systems in NV-IPM,” Proc. SPIE, 9452 94520O (2015). https://doi.org/10.1117/12.2190158 PSISDG 0277-786X Google Scholar

25. 

B. Teaney, D. Tomkinson and J. Hixson, “Legacy modeling and range prediction comparison: NV-IPM versus SSCamIP and NVTherm,” Proc. SPIE, 9452 94520P (2015). https://doi.org/10.1117/12.2179371 PSISDG 0277-786X Google Scholar

26. 

T. C. Edwards et al., “NVESD time-limited search model,” Proc. SPIE, 5076 53 –59 (2003). https://doi.org/10.1117/12.487143 PSISDG 0277-786X Google Scholar

27. 

E. S. Krendel and J. Wodinsky, “Search in an unstructured visual field,” J. Opt. Soc. Am., 50 (6), 562 –568 (1960). https://doi.org/10.1364/JOSA.50.000562 JOSAAH 0030-3941 Google Scholar

28. 

M. Friedman et al., “Search performance with PTN successfully predicts search performance with an advanced sensor,” in Proc. Ground Target Model. and Validation Conf., (2002). Google Scholar

29. 

M. Friedman et al., “Analytical calculation for probability of detection given time-dependent search parameters,” Proc. SPIE, 8014 80140C (2011). https://doi.org/10.1117/12.885161 PSISDG 0277-786X Google Scholar

30. 

M. Friedman, “A uniform method for analytically modeling multi-target acquisition with independent networked imaging sensors,” Proc. SPIE, 9071 90710O (2014). https://doi.org/10.1117/12.2054695 PSISDG 0277-786X Google Scholar

31. 

M. Friedman and S. Moyer, “Initial verification of an analytical model for target acquisition of multiple moving targets using multiple moving imaging sensors,” in Proc. Mil. Sens. Symp., (2014). Google Scholar

32. 

M. Hasting, “Combat simulation of individual soldier search in urban terrain,” Naval Postgraduate School, (2009). Google Scholar

33. 

M. Friedman, “Techniques for approaching ideal sensor target acquisition performance,” in Proc. Mil. Sens. Symp., (2015). Google Scholar

34. 

D. Wilson, N. Devitt and T. Maurer, “Search times and probability of detection in time-limited search,” Proc. SPIE, 5784 224 –231 (2004). https://doi.org/10.1117/12.604771 Google Scholar

35. 

M. H. Friedman, T. W. Du Bosq and E. A. Flug, “Analytical models quantify the military benefit of collaborative search,” Proc. SPIE, 7662 76620B (2010). https://doi.org/10.1117/12.851521 PSISDG 0277-786X Google Scholar

36. 

E. Flug, T. Maurer and O. Nguyen, “Time limited field of regard search,” Proc. SPIE, 5784 216 –223 (2005). https://doi.org/10.1117/12.604587 PSISDG 0277-786X Google Scholar

37. 

F. Skirlo, “Improving bandwidth efficiency and performance for manned aerial systems conducting target detection,” George Mason University, (2016). Google Scholar

38. 

T. Edwards et al., “Recent improvements in modeling time limited search,” Proc. SPIE, 4719 42 (2002). https://doi.org/10.1117/12.477474 PSISDG 0277-786X Google Scholar

39. 

J. Mazz, “Analysis of observer variability in the assessment of FLIR performance,” Proc. SPIE, 2743 2 –11 (1996). https://doi.org/10.1117/12.241975 PSISDG 0277-786X Google Scholar

40. 

H. R. Blackwell, “Contrast thresholds of the human eye,” J. Opt. Soc. Am., 36 (11), 624 –643 (1946). https://doi.org/10.1364/JOSA.36.000624 JOSAAH 0030-3941 Google Scholar

41. 

H. Kobayashi and B. L. Mark, Systems Modeling and Analysis—Foundations of System Performance Evaluation, Prentice Hall, Upper Saddle River, New Jersey (2009). Google Scholar

42. 

D. Gross et al., Fundamentals of Queueing Theory, John Wiley & Sons, Inc., Hoboken, New Jersey (2018). Google Scholar

44. 

N. Travnikova, “The probability of detecting a point light source,” Opt. Technol., 39 (8), 462 –464 (1972). Google Scholar

45. 

N. I. Pinegin and N. P. Travnikova, “The probability of visual detection of objects as a function of their angular size, contrast and search time,” Opt. Technol., 38 (5), 257 –260 (1971). Google Scholar

46. 

J. E. Corbett and J. Munneke, “It’s not a tumor: a framework for capitalizing on individual diversity to boost target detection,” Psychol. Sci., 29 (10), 1692 –1705 (2018). https://doi.org/10.1177/0956797618784887 1467-9280 Google Scholar

47. 

J. M. Wolfe et al., “Low target prevalence is a stubborn source of errors in visual search tasks,” J. Exp. Psychol. Gen., 136 (4), 623 –638 (2007). https://doi.org/10.1037/0096-3445.136.4.623 JPGEDD 1939-2222 Google Scholar

48. 

H. Kobayashi, B. L. Mark and W. Turin, Probability, Random Processes, and Statistical Analysis, 136 Cambridge University Press, Cambridge, United Kingdom (2012). Google Scholar

Biography

Melvin Friedman received his PhD in physics from Carnegie-Mellon for work in nuclear physics and subsequently received EE and CS MS degrees from Johns Hopkins. He retired from the federal government after 48 years of service. Currently, he volunteers at NVESD and is affiliated with George Mason University. He is the primary inventor of eight patents. He has done neutron activation analysis, electron microscopy, land mine detection, electro-optic sensor development, sensor performance, and search modeling.

Brian L. Mark received his PhD in electrical engineering from Princeton University and his BASc degree in computer engineering from the University of Waterloo. He has been at George Mason University since 2000, where he is currently a professor in the Department of Electrical and Computer Engineering. He was a research staff member at NEC Laboratories America from 1995 to 1999. His research interests lie in the areas of communication networks, stochastic models, and statistical signal processing.

Frank Skirlo received his PhD in electrical and computer engineering from George Mason University. He served more than 24 years in the U.S. Army Signal Corps, retiring as a colonel in December 2011. His last assignment was with the Joint Staff C4 Systems Directorate overseeing joint C4 programs and requirements. Since retiring from the Army, he works as a defense contractor for CACI Technologies as a modeling and simulation project lead for Program Executive Office Soldier.

© The Authors. Published by SPIE under a Creative Commons Attribution 4.0 Unported License. Distribution or reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.
Melvin H. Friedman, Brian L. Mark, and Frank E. Skirlo "What probability distribution describes search?," Optical Engineering 58(9), 093103 (18 September 2019). https://doi.org/10.1117/1.OE.58.9.093103
Received: 8 March 2019; Accepted: 20 August 2019; Published: 18 September 2019
JOURNAL ARTICLE
15 PAGES


SHARE
Advertisement
Advertisement
Back to Top