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.
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 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.
Several books have been written on the subject of search.1–6 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
Rotman11–14 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).17–19 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) points of interest that are not the target, and (3) a point that is near the target.21–23 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
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 . 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.
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 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.
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 , 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 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.
This section describes search notation and ideas needed to understand new results obtained in the following sections.
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:19,28
The asymptotic value of is , 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 . The time constant is typically determined experimentally: it goes up with increasing clutter and target range, whereas the parameter goes down with increasing clutter and target range. The NV-IPM model24,25 estimates 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 and is1919
The derivation19 of Eq. (4) assumes is an integer but Eqs. (3) and (4) yield reasonable results for noninteger values. Equations (3) and (4) express in terms of . An analytical model describing has not been developed. The parameter 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:
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 to look for a target19
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 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
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 value in the first- and second-gen imagery had values that were 76% and 36% higher than the value for an average performer. For first- and second-gen images, the best observers had 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 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
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 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):
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 definitions are given for equations in this paper where this symbol appears. Note that in Eq. (7), plays the role of and plays the role of in Eq. (5). In Eqs. (8) and (9), and are, respectively, the time constant and value of a single observer doing either FOV or FOR search depending on the scenario. The 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. 2–3. Observe that when , in Fig. 1 then .
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 were obtained by taking a random draw for a uniform distribution between 0 and 1 and assigning detection to draws and a similar process was used for other values of . 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 draws from an exponential distribution with resulting in 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 . Thus the number of accepted exponential draws goes down as decreases. 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 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, are random variables representing the target acquisition times of the observers. The assumption of identical observers means that are drawn from the same exponential distribution. The independence assumption means that
Less formally, target acquisition times and are statistically independent if the conditional distribution of given is the same as the (unconditional) distribution of .
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 , 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 for 10 observers searching for a target in FOR computer-generated scenes. is defined by , where is the detection time of the ’th observer. The definition for 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 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 values. Dots in Fig. 3 correspond to values averaged over scenes binned about the plotted value. Error bars correspond to the standard deviation of . 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.
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 ’th observer 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., and are known. Denote the system target acquisition probability for two observers engaged in cooperative search by . Then30Fig. 4.
The generalization of Eq. (10) for 3 and observers are, respectively,30
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
Target Acquisition Metric for Sensors and Observers
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.
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 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 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 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 and are natural parameters for describing search but are not appropriate metrics for ranking sensor target acquisition capability.
Equation (2) implies that the slope at the origin is , 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 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.
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 averaged over observers and scenes. Similarly, a measure of observer target acquisition capability is averaged over scenes for a particular sensor.
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 and . 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 in the former case and in the latter. Less formally, all observers taking part in the perception experiment are considered when calculating , whereas only observers who found the target are considered when calculating .
Two Sets of Observers
Consider the case where a group of identical stationary observers each characterized by search parameters and , and a second group of identical stationary observers each characterized by search parameters and 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 and are large. For this case, the expected number of detections among all observers is given by
For , the exponentials are essentially zero which shows that Eq. (13) asymptotically approaches 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 . The estimated number of detections is unchanged from the estimate made to compute Eq. (13). In this case, target acquisition probability is given by
The probability density function associated with Eq. (13) is obtained by differentiating with respect to time
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 .
Two Individual Observers
When , Eqs. (13)–(15) become
Three Individual Observers
The method already used for two individual observers can be extended to three individual observers
N Individual Observers
The extension of Eqs. (19)–(21) to observers is straightforward:
Results of this section are applicable to search experiments intended to determine and .
Equations (22) and (23) are, respectively, a hyperexponential distribution with 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.
Cooperative Search by Observers with Different Search Capabilities
Cooperative search by two, three and 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, , 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.
Derivation for Two Observers
Substitute , into Eq. (10) to get
Let denote system asymptotic target acquisition probability. Then for the case of two observers:
Using this result, Eq. (25) becomes
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.
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 is replaced by a matrix 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.
Theory of Phase-Type Distributions
The probability density function for a phase-type distribution is given43 by
It is important to know that an exponential raised to a matrix power is calculated using a Taylor series expansion:
This allows us to show that in Eq. (28a) is a scalar. Since any power of a matrix is a matrix, Eq. (29) implies is a matrix. The definition of implies that it is a vector. The product is thus a column vector. This is premultiplied by , a vector, to produce a scalar.
The CDF for a phase-type distribution is given by43
Realize that is a scalar. This implies in Eq. (30) is a scalar.
When , Eq. (30) reduces to the exponential distribution described by Eq. (1) because then and have just one component and are scalars. The condition that the sum over of is one implies . When , Eqs. (28a), (28b), and (29) generalize the exponential distribution.
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.
Several examples are provided which demonstrate how to use these functions.
Exponential random variable
The first line of Fig. 9 defines the row and the 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 .
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.
The first two lines of Fig. 10 define the appropriate and 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 and , i.e., adjust the number of values on the main diagonal of S and adjust the number of values so that matches order of the matrix. The , , for noncooperative search are given by Eq. (22). The reduced CDF is obtained by multiplying the CDF by the asymptotic system target acquisition probability .
The hyperexponential PDF and CDF for the case of three observers in noncooperative search isFigure 10 is in agreement with Eqs. (23)–(26).
Hyperexponential random variables (cooperative search)
The technique for calculating the cooperative hyperexponential distribution for two independent observers is shown in Fig. 11.
The first two lines of Fig. 11 define the appropriate and 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 , , and 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.
The first two lines of Fig. 12 define the appropriate and 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 parameters and the last line displays the CDF for this hyperexponential distribution. The reduced CDF is obtained by multiplying the CDF by .
We need to generalize Eq. (27b) to the case of three observers, that is, we need to identify how individual ’s relate to individual . The generalization of Eq. (27b) for is with similar expressions for and . The coefficient for is with similar expressions for and . The coefficient for is . In general, subscripts match the numerals in the matrix and the alpha coefficients describe which exponentials survive given a combination of values for different observers that are either zero or one. Thus only the exponent survives with , . Similarly, only the exponent survives when . The value for is found from Eq. (11) by replacing in that equation by .
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.
Summary of Results and Conclusions
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 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.
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 . 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 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 and that second-gen sensors had a higher value than first-gen sensors.
Observers too can be ranked for target acquisition efficacy using 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.
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.
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.
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.
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 . 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 , (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.
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 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 times. The detection time is a random variable. Out of the trials, let denote the number of times the target is detected in a time less than or equal to . Then in Eq. (1), the definition of is
Equation (2). A thought experiment for which Eq. (2) applies is described. Suppose 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 denote the number of times the target is detected in a time less than or equal to . Then in Eq. (2), 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 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 to click on the target. Any clicks on the image after time are ignored.
Equation (7). Here 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 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 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 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 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 denote the mean detection time for that process, denotes the number of trials which have a target, and denotes the number of detections in those trials that take place in a time less than . Then in Eq. (7), 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 and 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 times in searches that contain a target. The detection time for the search process described above is a random variable. In the searches, let denote the number of detections in a time less than or equal to . Then in Eq. (10), 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.
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.
Express Eq. (2) in terms of and a random variable , the time a single Soldier detects the target. Then
Consider two observers with detection times given by independent random variables and . The event that each observer eventually finds the target is now denoted by and , respectively. When two observers search, a target is found as soon as either observer finds the target. Let denote the system time for target detection. Then
Let 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 denote the probability that either Soldier detects the target. Then . We seek the CDF associated with the random variable . To get the CDF, it is convenient to first calculate as follows:
The last equality follows from the observation:
Referring to Eq. (38), we need to evaluate . It must be that
Using Eqs. (39a)–(39e) and (40a)–(40d), Eq. (38) becomes
The last equation simplifies to
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.