# Modeling Sequential Searches with Ancillary Target Dependencies

Authors: Thomas A. Wettergren; John G. Baylog
Journal: Advances in Decision Sciences
 (2010)

---

## Abstract

We develop a mathematical modeling approach to evaluate the effectiveness of a Bayesian search for objects in cases where the target exhibits ancillary dependencies. These dependencies occur in situations where there are multiple search passes of the same region, and they represent a change in search probability from that predicted using an assumption of independent scans. This variation from independent scans is typically found in situations of advanced detection processing due to fusion and/or collaboration between searchers. The framework developed is based upon the evaluation of a recursion process over spatial search cells, and the dependencies appear as additive utility components within the recursion. We derive expressions for evaluating this utility and illustrate in detail some specific instantiations of the dependency. Computational examples are provided to demonstrate the capabilities of the method.


---

## Body

## 1. Introduction

The planning of searches for objects of uncertain disposition is a classical problem in military operations research. Historically, such searches are conducted by a single platform examining different regions of the space over time. This has led to a classical search theory methodology that provides an analytical basis for evaluating potential searchesa priori. When such searches are represented parametrically, the evaluation can be computationally very efficient. The problem of optimal search involves the mathematical determination of these search parameters in order to maximize this search effectiveness. These modeling approaches have been limited by the requirement to obtain analytical solutions for computational exigency, yet have served well as appropriate-fidelity models of historical search practice. Modern search platforms, however, can store past search information and, thus, fuse the overlapping “looks” of the same region to improve performance. Unfortunately, these multipass search dependencies are not consistent with the independence assumptions that are explicit in the conventional analytical formulations of search theory.The independence dominant perspective of conventional approaches to modeling search effectiveness considers the target as an object whose presence can be ascertained only on the proximity of a searcher to that object. However, modern search systems exhibit many more dependencies in addition to simple proximity that affect the search performance. The type of search dependencies we are concerned with occurs when the target contains some sort of ancillary dependency on the particulars of the search platform's engagement. These dependencies violate the independence assumptions of the classical analytical approach to search theory.With modern computing capabilities, there is an opportunity to consider a numerical approach to search evaluation that incorporates a Bayesian update of the likelihood of finding an object under a grid representation of the search region. Previous computational limitations prohibited the computational examination of these grid approaches that necessarily require extensive computer storage. In this paper, we develop a mathematical model of search that allows for the incorporation of multiple pass dependencies. The model is based on recursively updating a geometric likelihood structure that represents the search success. We illustrate an efficient computational process for determining search effectiveness utilizing this modeling framework. Examples that illustrate the model are provided for some notional dependencies and the results are demonstrated with computer simulations.


## 2. Classical Approaches to Search Modeling

The classical theory of search, as initially developed by Koopman [1], was developed to examine the search for randomly located objects within a large search space. That work was furthered by many others over many years, as summarized in Benkoski et al. [2] and the references therein. From a modeling perspective, these extensions allowed the examination of more complicated scenarios, such as accounting for the effects of motion and for the effects of multiple targets. While the extension to two-sided games for evading targets is well studied, we are only focused on fixed nonreactive search objects, and thus do not consider those extensions. However, the classical one-sided search problem still has a variety of probability questions, as noted by Nakai [3]. These problems include the detection search problem, the information search problem, and the whereabouts search problem. While different from a design and optimization standpoint, from an evaluation standpoint all of the proceeding problems focus on the sequential evaluation of object detection likelihood over the search space.From a system design perspective, search theory allows the development of improved courses of action for limited search resources. Given models that determine the effectiveness of arbitrary search distributions, one can formulate the problems of optimal search, which lead to “best” allocations of search effort for maximizing the search goal. As clearly pointed out by Washburn [4], the problem of optimizing the search for a stationary object becomes a distribution of effort problem, for which a number of solutions exist (see [5, 6] for an overview). However, many of these search optimization problems are computationally difficult [7], and approximation methods are often employed. Computationally efficient cell-based methods to the problem of search allocation are often employed [8].When the searchers are moving yet the target remains fixed, the kinematics of the search platform limit the achievable states and thus provide a constraint on the optimal solution. Many practical problems involve long durations with relatively narrow search swaths. This leads to problems of path formulation, as in Reber search theory (as described in [9]) which examines the achievable performance over long times given a relatively narrow search swath. Even when paths are fixed, benefits can be achieved if one adjusts the sensor gains dynamically [10]. However, all of these approaches to improved search performance hinge on the underlying mathematical model of probabilistic search performance that is employed.When modeling the expected performance of a given search, the use of density representations of search objects is often utilized. This has been done either due to physical complications of multiple objects [11], uncertainty of the number of discrete objects [12], or a desire to search for an object whose natural representation is density-based [13]. In all these cases, the density approaches provide a natural likelihood structure for the underlying process of search. In the search context, the density approach extends to more complicated search problems, such as, the introduction of false target objects [14] or the added uncertainty of unknown searcher performance [15]. Furthermore, the likelihood formulations extended readily into the problem of (non-reactive) moving targets [16], although that complication leads to problems of optimal control which are beyond the scope of this paper. We examine the problem of one or more searchers seeking a set of objects with uncertain disposition. As opposed to other decision-theoretic methods [17], we focus on creating a sequential likelihood update process for given search paths and anticipated searcher performance. These sequential likelihood updates are similar to other approaches to sequential likelihood updating as found in receding horizon estimation [18]. When applied to geographic maps of performance, the sequential likelihood update process creates a geographic form of Bayesian estimation, which has been successfully applied to areas such as robot localization [19] and search-and-rescue [20, 21]. By formulating our numerical approach as a sequential likelihood update over a common geographical partition, we have developed a model that is scalable with respect to complex application-specific variabilities. This capability augments the limited parametric considerations found in other approaches. This new approach to recursive search performance prediction accounts for complex multiple pass search operations, and thus provides a foundation for future work on optimal planning of coordinated search efforts.


## 3. Search Modeling for Multiple Search Passes

Performance evaluation models that are applicable to multiple pass search operations must possess enough flexibility to account for dependencies inherent within the dynamics of collaborative search yet be simple enough to promote the computational efficiency necessary for extended usage in planning. We model the search as an interrogation over a set of geometric grid cells. We choose a grid partition of the search space as a means to account for variability encountered during the search that is not readily articulated in closed form. This variability may present itself as spatial variations in object placement likelihood or in the sensor's capacity to detect objects. The variability may also be exhibited in the spatial coverage projected by various search plans. It can be manifested by irregularity in hypothesized search path trajectories or as a distribution in the number of search passes conducted over the space. The extent of the variability dictates the specification of the grid such that the quantities are approximately static within each grid cell. This enables us to avoid any need for segmentation within the evaluation process and to keep the numeric calculation of performance to its simplest realization. We do not impose any kinematic constraints on the cell structure as search paths can be considered an input to the model. Rather, the kinematics of searcher motion are naturally translated into a sequence of cell visitations.While we employ the grid construct in a two-dimentional search paradigm in this paper, the approach readily extends to higher dimensions in any of the searcher parameters subject to optimization. In particular, three-dimensional spatial constructs are a natural extension of the approach provided that likelihood variability restrictions on grid specification are maintained. By using a Bayesian update framework, we develop expressions for the sequential update of search probabilities over the cell visitation sequence in a manner that retains the ability to include nontrivial multipass search dependencies. We furthermore restrict our attention to cases of fixed search objects, the extension to moving search objects is a subject of future study.This modeling approach to search evaluation is intended to address the search for multiple objects. In the following subsections, we provide a quantification of search effort in multiple pass searches. For this development, we revert to a single object placement density as a fundamental cell characteristic applicable to either a set of distinct object density functions or to a common density representative of objects that are independent and identically distributed.


### 3.1. Cell-Based Representations of Performance

Letd∈{0,1} represent the event that a search has successfully located the object of search (i.e., d=1 when search is successful and d=0 otherwise). Define the global detection probability map as the spatial representation of the search detection likelihood function Pd(x):𝒜→[0,1]. This function (defined on the subset 𝒜 of ℝ2 that corresponds to our search region) represents the probability that an object located at x would be found when the searcher conducts a search at location x (as in Pr(d∣x)=Pd(x)). For an object of search that is located in the search region according to the density function f(x), the probability of the search being successful is then given by(3.1)Pr(d)=∫𝒜Pr(d∣x)·f(x)dx=∫𝒜Pd(x)·f(x)dx.
Equation (3.1) represents the search effectiveness as a simple marginalization of the global detection probability map Pd(x) over the search object location density f(x). The development of prior representations of these search object location density functions for problems of practical interest has been previously reported by the authors [22]. Thus, by maintaining careful geometric representations of the evolution of these spatial densities throughout the search evaluation, we develop a search model with flexibility to handle a variety of modeling complexities.Fundamentally, the evaluation of search dependency is a problem in spatial processing of multiple looks over regions. As such, we consider a cell-based decomposition of the finite search region𝒜⊂ℝ2 into a finite set of cells Gi⊂𝒜, such that the complete set of cells Gi form a partition on the search region 𝒜. Thus, this implies the relationships ⋃iGi=𝒜 and Gi∩Gj=0,foralli≠j. In simple convex geometries such as typically found in spatial search problems, these regions generally form a simple grid of the space 𝒜. However, any finite partitioning of the search region is allowed, and a particular choice of partitioning is application-dependent. Consider a two-dimensional search evaluation over the cells {Gi}. We assume that the object is located somewhere in the search region, and specifically concern ourselves with examining the probability that a search of the cell that contains the object is successful. By focusing on the cell that contains the object, the object location density may be mapped to the cell-specific object location density fi(x) as(3.2)fi(x)={f(x)∫Gif(y)dy,x∈Gi0,otherwise.
We note that, by this definition, the cell-specific object location density is necessarily equal to zero in cells that have no likelihood of containing the object, as expected.The search evaluation function of (3.1) now reduces to(3.3)Pr(d)=∑i∫GiPr(d∣x)·f(x)dx=∑i[∫Gif(x)dx]PDi,
where(3.4)PDi=∫GiPd(x)·fi(x)dx
represents the search effectiveness of the use of the search effort Pd(x) against target object f(x) over the specific cell Gi. We note that this resulting value denotes a weighted spatial average of the detection likelihood function over the grid cells, where the weights represent the likelihood of the object being located in each cell. For a cell Gi0 that is known to specifically contain the object, the integral ∫Gif(x)dx is equal to one for i=i0 and zero for all other i's, such that Pr(d)=PDi0, as expected. Thus, the decomposition of (3.3) separates the problem of overall search evaluation into one of independent examination of search performance in each cell.We shall assume that grid resolution is sufficient such that the variation in both the detection likelihood and the placement probability over the grid cell is small such that a nominal constant value can be presumed for the cell. Observe that forPDi<1, there is a probability of (1-PDi)>0 that an object will not be detected on the first search opportunity. It may, however, be detected on subsequent passes if the search path covers this cell in a future segment of the search path.


### 3.2. Likelihood Functions for Multiple Passes

Letn denote position within a sequence of search scans on the cell position Gi obtained by a traveling observer. Let δi denote the event that first detection of an object occurs somewhere within the sequence of NS scans of cell Gi. Furthermore, define the first detection probabilityPδi(n) as the probability that the first detection occurs within scan n. The succession of these first occurrence probabilities develops sequentially as multiple scans of the cell materialize from the search plan, leading to(3.5)Pr(δi)=∑n=1NSPδi(n),
By modeling each scan's detection observation as an independent Bernoulli trial, the waiting time (i.e., the number of scans before detection occurs) for each cell follows a geometric distribution [23]. Then, the first detection probability Pδi(n) becomes(3.6)Pδi(n)=(1-PDi)n-1PDi
for cell detection probabilities PDi that are independent from pass to pass. This probability expression naturally incorporates both the temporal and spatial aspects of the search process (the spatial through PDi and the temporal through n).When there exists a dependency between the multiple passes of a cellGi, the independence assumption of the Bernoulli trial is no longer valid. Let us assume that the cell detection probability PDi varies from scan to scan for a given grid cell Gi, such that PDi=PDi(n). This may be due to an ancillary dependency such as with sensor type or proximity to sensor or otherwise. We define the complementary event of no detections through a sequence of scans NS as η. Then the probability of no detections through the first n scans of cell Gi is given by Pηi(n). At a given scan number n, the probability of achieving a first detection event δi in cell Gi is given as the probability product of detecting during scan n and not having detected up through scan (n-1). This leads to the relation(3.7)Pδi(n)=PDi(n)·Pηi(n-1),n=1,…,NS.
Similarly, the probability of continuing to not detect at scan n is given by the probability product of not detecting during scan n and not having detected up through scan (n-1), as in(3.8)Pηi(n)=(1-PDi(n))·Pηi(n-1),n=1,…,NS.
Equation (3.8) is the fundamental recursion relation that guides the search evaluation. The initial value for this recursion relation (with n=0 scans designating the unsearched condition) is given by(3.9)Pηi(0)=1.
Since the recursion is defined only on the nondetection probability Pηi(n) (and not on the detection probability Pδi(n)), the initial probability for Pδi(n) is not explicitly required. However, we note that (3.7) and (3.9) imply Pδi(1)=PDi(1), as expected.By computing the evolution of the grid cell detection functionPDi(n) over successive passes as the search progress, (3.8) is used to recursively update the probability of the search object nondetection on a per cell basis. To obtain the first detection probability of any given cell at a given scan, the nondetection probability Pηi(n) is applied to (3.7). The spatial aggregation of these per cell first detection probabilities (3.7) is then a summation (as in (3.3)) to obtain the aggregate performance at any time step within the search process. Thus, the probability likelihood maps given by Pηi(n) and Pδi(n) provide the fundamental mechanism for capturing the search performance information for multiple scans of a search region, whereby all other aggregate search performance measures can be simply derived.We note that, in the case of independent scans,PDi(n)=PDiforalln, such that the recursion of (3.8) is a linear homogeneous recursion equation with general solution form Pηi(n)=αrn for some constants α and r. In this form, (3.8) is solved with r=(1-PDi), and the initial condition (3.9) is met with α=1, leading to(3.10)Pηi(n)=(1-PDi)n
and, correspondingly, the complementary first detection probability is given by(3.11)Pδi(n)=PDi(1-PDi)n-1
which is the same expression as (3.6) that was found by the Bernoulli trials for independent scans, as expected.


### 3.3. Utility Functions for Likelihood Updates

We next extend the detection likelihood modeling to include dependency on ancillary parameters that describe the interrelation between searcher and object properties. Such modeling may articulate random dependencies such as orientation angle of the search object or particular dependencies categorizing the capability of specific searchers to detect objects of a given type. Letθ∈Θ denote a random variable that corresponds to the ancillary parameter that is an object property that is independent of both the scan and the placement of the search object (such as an orientation angle of an object). Furthermore, let ϕn denote the deterministic ancillary parameters of the searcher that are specific to the nth scan (such as a specific searcher type). Let Pr(d∣x,θ;ϕn) represent the probability that an object located at x with random parameter θ would be found when the nth scan of a search is conducted at x given the scan parameter ϕn. Given a probability distribution h(θ):Θ→[0,1] of the random parameter θ, the marginal search detection likelihood function is given by(3.12)Pr(d∣x)=∫ΘPr(d∣x,θ;ϕn)h(θ)dθ=P̅d(x;ϕn).
We note that the overbar in P̅d is used to differentiate it from Pd which retains the dependency. Observe that, when h(θ)=constant, we have Pr(d∣x,θ;ϕn)∝Pr(d∣x;ϕn), and the detection likelihood depends only on placement x. In such cases, if there are no additional scan-specific dependencies, then ϕn=ϕ0foralln, and the expression for search detection is as previously defined, such that Pd(x)=P̅d(x;ϕ0).We presume (as indicated in (3.12)) that the ancillary parameter θ and the location x at which the object is placed are independent random variables. The consequence of this assumption is that the probability likelihood may be represented as a mean component with a zero-mean perturbation; that is,(3.13)Pr(d∣x,θ;ϕn)=P̅d(x;ϕn)+ΔP(θ;ϕn).
Here the search detection likelihood function is decomposed into a nominal value that varies over the search space (and may vary according to ϕn as well) and a perturbation that depends only on the ancillary parameters θ and ϕn. Again, for the simple case with no ancillary parameters, the search detection likelihood reverts to P̅d(x;ϕ0)=Pd(x).We next consider the evaluation of this search detection likelihood over a region𝒜 that has been partitioned into subregions {Gi} as described in Section 3.1. We focus our attention on a specific grid cell Gi, such that the object location density f(x) has been rescaled to fi(x) as in (3.2). Within this grid cell, the cell first detection probability Pδi(1) associated with the first (n=1) pass of cell Gi is now given as(3.14)Pδi(1)=∫Θ∫GiPr(d∣x,θ;ϕ1)fi(x)h(θ)dxdθ=∫GiP̅d(x;ϕ1)fi(x)dx+∫ΘΔP(θ;ϕ1)h(θ)dθ=PDi(1;ϕ1)+∫ΘΔP(θ;ϕ1)h(θ)dθ,
where PDi(1;ϕ1) explicitly shows the dependence on ϕ1. Since we generally expect any dependence on ϕn to be implied in the nth pass detection probability, we simplify notation to PDi(n;ϕn)↦PDi(n) with an implied dependence on ϕn. To further facilitate the exposition, we define an ancillary cell detection function ψ1(ϕn) that serves as a decision-theoretic utility function in ϕn for the nth search pass of a location. Specifically, we let(3.15)ψ1(ϕn)=∫ΘΔP(θ;ϕn)h(θ)dθ,n=1,2,….
However, ΔP(θ;ϕn) has been defined in (3.13) to be zero-mean perturbation term, so its integral over θ goes to zero, leading to ψ1(ϕn)=0. With that simplification, (3.14) becomes(3.16)Pδi(1)=PDi(1).
In similar fashion, the first pass nondetection probability for cell Gi is now given as(3.17)Pηi(1)=∫Θ∫Gi(1-Pr(d∣x,θ;ϕ1))fi(x)h(θ)dxdθ=1-∫GiP̅d(x;ϕ1)fi(x)dx-∫ΘΔP(θ;ϕ1)h(θ)dθ=1-PDi(1).
We note that the separation in (3.14) and (3.17) is  enabled by the separation of terms in (3.13), and that these expressions are equivalent to the first terms of (3.7) and (3.8). While the additional definition of the ancillary cell detection function ψ1 seems to be unnecessary, it will become useful in the following recursion terms.For subsequent passes over the grid cell, the perturbed likelihood equations are slightly more complicated. We assume the grid cell size is chosen to be small enough such thatP̅d(x;ϕn) is approximately constant over a cell, so that
(3.18)∫GiP̅d(x;ϕn)P̅d(x;ϕm)fi(x)dx≈PDi(n)PDi(m)foranyn,m.
Then, for the second pass, the equation for first detection takes the form(3.19)Pδi(2)=∫Θ∫GiPr(d∣x,θ;ϕ2)(1-Pr(d∣x,θ;ϕ1))fi(x)h(θ)dxdθ=∫GiP̅d(x;ϕ2)(1-P̅d(x;ϕ1))fi(x)dx+∫ΘΔP(θ;ϕ2)h(θ)dθ∫Gi(1-P̅d(x;ϕ1))fi(x)dx-∫ΘΔP(θ;ϕ1)h(θ)dθ∫Gi(P̅d(x;ϕ2))fi(x)dx-∫ΘΔP(θ;ϕ1)ΔP(θ;ϕ2)h(θ)dθ≈PDi(2)(1-PDi(1))+ψ1(ϕ2)(1-PDi(1))-ψ1(ϕ1)PDi(2)-ψ2(ϕ1,ϕ2),
where(3.20)ψ2(ϕ1,ϕ2)=∫ΘΔP(θ;ϕ1)ΔP(θ;ϕ2)h(θ)dθ
represents the second-order ancillary cell detection function. Recalling that ψ1(ϕn)=0 for any n, we have that(3.21)Pδi(2)≈PDi(2)Pηi(1)-ψ2(ϕ1,ϕ2).
Note that (3.21) is similar to (3.7) with n=2; however, there is now an additional term (given by ψ2) to account for the effects of the ancillary parameters defining the search. Similarly, the second pass recursion equation for nondetection becomes(3.22)Pηi(2)=∫Θ∫Gi(1-Pr(d∣x,θ;ϕ2))(1-Pr(d∣x,θ;ϕ1))fi(x)h(θ)dxdθ≈(1-PDi(2))Pηi(1)+ψ2(ϕ1,ϕ2).
In summary, for the second scan pass of the cell Gi, we have(3.23)Pδi(2)≈PDi(2)Pηi(1)+U(2),Pηi(2)≈(1-PDi(2))Pηi(1)-U(2),
where the utility function U(2)=-ψ2(ϕ1,ϕ2) represents the added utility of the search scan over that obtained with traditional independent passes. It is a result of marginalization over the control parameter θ for the given search scan perturbation function ΔP. This second pass utility function has two arguments, one for each ancillary parameter corresponding to each scan of the grid cell. More generally, we construct a set of functions that are readily calculated to assess search utility for any number of passes given the search path. It is desirable that these utility functions do not present unduly computational storage requirements associated with the detection and nondetection maps developed by the search evaluation.The general form for thenth scan cell nondetection probability becomes
(3.24)Pηi(n)=∫Θ∫Gi(1-Pr(d∣x,θ;ϕn))[∏j=1n-1(1-Pr(d∣x,θ;ϕj))]fi(x)h(θ)dxdθ=∫Gi(1-P̅d(x;ϕn))∫Θ[∏j=1n-1(1-Pr(d∣x,θ;ϕj))]h(θ)dθfi(x)dx-∫Θ(ΔP(θ;ϕn))∫Gi[∏j=1n-1(1-P̅d(x;ϕj)-ΔP(θ;ϕj))]fi(x)dxh(θ)dθ≈(1-PDi(n))Pηi(n-1)-U(n),
where we note that(3.25)Pηi(n-1)=∫Θ∫Gi∏j=1n-1(1-Pr(d∣x,θ;ϕj))fi(x)h(θ)dxdθ,
and U(n) is defined as the nth pass utility function. Note that the approximation in (3.24) comes from the approximation of (3.18) for spatial integrations over a grid cell. Similarly, for the nth scan cell first detection probability, we have(3.26)Pδi(n)=∫Θ∫GiPr(d∣x,θ;ϕn)[∏j=1n-1(1-Pr(d∣x,θ;ϕj))]fi(x)h(θ)dxdθ≈PDi(n)Pηi(n-1)+U(n)
with the same utility function U(n). Thus, the fundamental nondetection recursion of (3.8) is now generalized to the form of (3.24), and the complementary equation for first detection of (3.7) is generalized by (3.26).The form of the utility functionU(n) found in (3.26) and (3.24) is explicitly given by(3.27)U(n)=∫ΘΔP(θ;ϕn)[∏j=1n-1(1-PDi(j)-ΔP(θ;ϕj))]h(θ)dθ.
By multiplying out the product term, taking the integral over θ, and then rearranging terms, this function is written in the form
(3.28)U(n)=∑j=2n(-1)j-1∑γj∈μj-1n-1[ψj(ϕn,{ϕm};γj)∏k=1k≠γjn-1(1-PDi(k))]
with(3.29)ψj(ϕn,{ϕm};γj)=∫ΘΔP(θ;ϕn)∏m∈γjΔP(θ;ϕm)h(θ)dθ,
representing the jth ancillary function. Here U(n) represents an nth pass general utility function with μjm representing the set of all j-tuples of indices from 1 to m (i.e., μ34={(1,2,3),(1,3,4),(1,2,4),(2,3,4)}), and γj representing a specific j-tuple. For convenience, we rewrite the utility in the form U(n)=∑j=2nUj(n), where the component utility function Uj(n) denotes the contribution of the jth ancillary function ψj to the total utility.An important simplification of the utility function can be found when the nominal value of the search detection likelihoodP̅d is independent of the scan parameter ϕn. In particular, for those cases when P̅d(x;ϕn)=P̅d(x), (3.4) implies that PDi(n)=PDi for all n, such that the component utility functions reduce to(3.30)Uj(n)=(-1)j-1(1-PDi)n-j∑γj∈μj-1n-1ψj(ϕn,{ϕm};γj);
a form that is found to be convenient in many practical computational examples. Because the ancillary functions ψj may be computed and stored prior to any specific search evaluation, the forms in (3.28) and (3.30) are extremely computationally efficient.


### 3.4. Properties of Multipass Utility Functions

We next note some useful properties of the utility function that illustrate some features of ancillary dependency in search and also aid in the numerical evaluation. We first consider the case of noninteracting scans, that is, events whereby the detection performance of each scan is independent of the other scans. In such cases, we have the following lemma.Lemma 3.1.
For searches in which there is no scan-specific dependencyϕn, the utility function U(n) is a linear combination of the moments of the random perturbation component of detection likelihood ΔP(θ).Proof.
Assume a search with no scan-specific dependenciesϕn. Then P̅d(x;ϕn)=P̅d(x) which leads to PDi(n)=PDi for all n via (3.4). Furthermore, when there is no ϕn, we have ΔP(θ;ϕn)=ΔP(θ) which leads to ψj=∫ΔP(θ)jh(θ)dθ from (3.29). Thus, each component ψj is the jth moment of ΔP(θ). The form of the utility function U(n) in (3.30) now holds, and ∑ψj(ϕn,{ϕm};γj)=αψj, where α=(n-1j) is the number of terms in the sum. Thus, the component utilities are given by Uj(n)=(-1)j-1(n-1j)(1-PDi)n-jψj=c(n,j)ψj, where c(n,j) is a constant that depends on n and j. Now, U(n)=∑j=2nUj(n)=∑j=2nc(n,j)ψj, which is a linear combination of the moments ψj of ΔP(θ).This lemma naturally leads to the following theorem about the construction of zero-utility functions.Theorem 3.2.
If a search has no scan-specific dependenciesϕn, then the utility is zero through the nth scan if the first n moments of the random perturbation ΔP(θ) are zero.Proof.
The proof of this theorem follows from Lemma3.1. Assume a search has no scan-specific dependencies ϕn. Furthermore, assume the first n moments of ΔP(θ) are zero. Let v∈ℝn be a vector of the first n moments of ΔP(θ). From Lemma 3.1, it is known that there exists a vector u∈ℝn such that U(n)=uTv. However, vj=∫ΔP(θ)jh(θ)dθ=0forallj, so that U(n)=uT0=0.An obvious case of the conditions in Theorem3.2 is the case of no ancillary dependency at all. In such cases, there are no scan-specific dependencies ϕn and the random perturbation term ΔP(θ)=0 for all θ. Thus, the conditions of the theorem are met and we have zero utility, as expected. However, there are conditions under which we may have no scan-specific dependencies ϕn, but still have a non-trivial ΔP(θ), for which we have the following important corollary to Theorem 3.2.Corollary 3.3.
In searches with no scan-specific dependenciesϕn, there may still exist a non-zero utility if there are non-zero moments of the random perturbation ΔP(θ).The importance of this corollary is that a model may be constructed to incorporate effects that vary randomly over the scans, but have no scan-specific dependency associated with them. These effects are naturally modeled with theθ dependency in ΔP(θ;ϕn) and can lead to non-zero utility, thus showing a change in search performance relative to the situation with no ancillary dependencies.For the special case of repeated events, which are more restrictive than independent events, the utility can be used to show that the search effectiveness actually decreases. This is illustrated by the following theorem.Theorem 3.4.
For a search component comprised of repeated events, there is non-positive utility, that is,U(n)≤0.Proof.
Assume a search component comprised of repeated events, such thatϕn=ϕm for all n,m. From (3.29), we have ψj(ϕn)=∫ΔP(θ;ϕn)jh(θ)dθ. Since ΔP(θ;ϕn) is, by definition, a zero-mean real-valued function, we have that all of the odd moments of ΔP(θ;ϕn) are also zero, specifically ∫ΔP(θ;ϕn)jh(θ)dθ=0 for j odd. Since P̅d(x;ϕn)=P̅d(x) for repeated events, we have the form of (3.30) for component utility. From (3.30), we then have Uj=0 for j odd. Thus, U(n)=∑j=1n/2U2j(n) for n even, and U(n)=∑j=1(n-1)/2U2j(n) for n odd. Since 0≤PDi≤1, we have (1-PDi)n-2j≥0. Furthermore, ψ2j≥0 for all arguments. Thus, U2j(n)=(-1)(1-PDi)n-2j∑ψ2j≤0 for all positive integer values of j, and therefore U(n)≤0.This theorem is important since utility is an additive component of the standard independent event recursions. If a search is performed without independent examination, but instead a repeatable examination, then the benefits of multiple independent scans are lost, yet the utility formulation can be utilized to quantify this decrease in performance.The computation of utility becomes combinatorially complex as the number of passesn of a cell increases. This is due to the summation over the components of μjn-1, which has size (n-1j). To reduce this computational burden, we utilize the following theorem that gives bounds on the magnitude of the component utility functions Uj(n).Theorem 3.5.
For a search with cell detection probabilities that are independent of scan number, and with random perturbation bounded by1/2, the component utility functions are bounded by
(3.31)|Uj(n)|≤12j(n-1j-1)(1-PDi)n-j.Proof.
Consider a search with scan independent detection probabilities, such thatPDi(n)=PDiforalln. Then the component utility form of (3.30) holds. The function ΔP(θ;ϕn) is a zero-mean function over a probability space that is bounded by 1/2, so the integral expression ∫|ΔP(θ;ϕn)|h(θ)dθ≤1/2. Furthermore, the integral composed of the product of j of these terms under the integrand is also bounded by (1/2)j. Thus, we have |ψj|≤1/2j. The summation in (3.30) contains (n-1j-1) terms, such that the summation is bounded by 2-j(n-1j-1). Substituting this into (3.30) yields |Uj(n)|≤2-j(n-1j-1)(1-PDi)n-j, thus demonstrating the bound in the theorem.


## 3.1. Cell-Based Representations of Performance

Letd∈{0,1} represent the event that a search has successfully located the object of search (i.e., d=1 when search is successful and d=0 otherwise). Define the global detection probability map as the spatial representation of the search detection likelihood function Pd(x):𝒜→[0,1]. This function (defined on the subset 𝒜 of ℝ2 that corresponds to our search region) represents the probability that an object located at x would be found when the searcher conducts a search at location x (as in Pr(d∣x)=Pd(x)). For an object of search that is located in the search region according to the density function f(x), the probability of the search being successful is then given by(3.1)Pr(d)=∫𝒜Pr(d∣x)·f(x)dx=∫𝒜Pd(x)·f(x)dx.
Equation (3.1) represents the search effectiveness as a simple marginalization of the global detection probability map Pd(x) over the search object location density f(x). The development of prior representations of these search object location density functions for problems of practical interest has been previously reported by the authors [22]. Thus, by maintaining careful geometric representations of the evolution of these spatial densities throughout the search evaluation, we develop a search model with flexibility to handle a variety of modeling complexities.Fundamentally, the evaluation of search dependency is a problem in spatial processing of multiple looks over regions. As such, we consider a cell-based decomposition of the finite search region𝒜⊂ℝ2 into a finite set of cells Gi⊂𝒜, such that the complete set of cells Gi form a partition on the search region 𝒜. Thus, this implies the relationships ⋃iGi=𝒜 and Gi∩Gj=0,foralli≠j. In simple convex geometries such as typically found in spatial search problems, these regions generally form a simple grid of the space 𝒜. However, any finite partitioning of the search region is allowed, and a particular choice of partitioning is application-dependent. Consider a two-dimensional search evaluation over the cells {Gi}. We assume that the object is located somewhere in the search region, and specifically concern ourselves with examining the probability that a search of the cell that contains the object is successful. By focusing on the cell that contains the object, the object location density may be mapped to the cell-specific object location density fi(x) as(3.2)fi(x)={f(x)∫Gif(y)dy,x∈Gi0,otherwise.
We note that, by this definition, the cell-specific object location density is necessarily equal to zero in cells that have no likelihood of containing the object, as expected.The search evaluation function of (3.1) now reduces to(3.3)Pr(d)=∑i∫GiPr(d∣x)·f(x)dx=∑i[∫Gif(x)dx]PDi,
where(3.4)PDi=∫GiPd(x)·fi(x)dx
represents the search effectiveness of the use of the search effort Pd(x) against target object f(x) over the specific cell Gi. We note that this resulting value denotes a weighted spatial average of the detection likelihood function over the grid cells, where the weights represent the likelihood of the object being located in each cell. For a cell Gi0 that is known to specifically contain the object, the integral ∫Gif(x)dx is equal to one for i=i0 and zero for all other i's, such that Pr(d)=PDi0, as expected. Thus, the decomposition of (3.3) separates the problem of overall search evaluation into one of independent examination of search performance in each cell.We shall assume that grid resolution is sufficient such that the variation in both the detection likelihood and the placement probability over the grid cell is small such that a nominal constant value can be presumed for the cell. Observe that forPDi<1, there is a probability of (1-PDi)>0 that an object will not be detected on the first search opportunity. It may, however, be detected on subsequent passes if the search path covers this cell in a future segment of the search path.


## 3.2. Likelihood Functions for Multiple Passes

Letn denote position within a sequence of search scans on the cell position Gi obtained by a traveling observer. Let δi denote the event that first detection of an object occurs somewhere within the sequence of NS scans of cell Gi. Furthermore, define the first detection probabilityPδi(n) as the probability that the first detection occurs within scan n. The succession of these first occurrence probabilities develops sequentially as multiple scans of the cell materialize from the search plan, leading to(3.5)Pr(δi)=∑n=1NSPδi(n),
By modeling each scan's detection observation as an independent Bernoulli trial, the waiting time (i.e., the number of scans before detection occurs) for each cell follows a geometric distribution [23]. Then, the first detection probability Pδi(n) becomes(3.6)Pδi(n)=(1-PDi)n-1PDi
for cell detection probabilities PDi that are independent from pass to pass. This probability expression naturally incorporates both the temporal and spatial aspects of the search process (the spatial through PDi and the temporal through n).When there exists a dependency between the multiple passes of a cellGi, the independence assumption of the Bernoulli trial is no longer valid. Let us assume that the cell detection probability PDi varies from scan to scan for a given grid cell Gi, such that PDi=PDi(n). This may be due to an ancillary dependency such as with sensor type or proximity to sensor or otherwise. We define the complementary event of no detections through a sequence of scans NS as η. Then the probability of no detections through the first n scans of cell Gi is given by Pηi(n). At a given scan number n, the probability of achieving a first detection event δi in cell Gi is given as the probability product of detecting during scan n and not having detected up through scan (n-1). This leads to the relation(3.7)Pδi(n)=PDi(n)·Pηi(n-1),n=1,…,NS.
Similarly, the probability of continuing to not detect at scan n is given by the probability product of not detecting during scan n and not having detected up through scan (n-1), as in(3.8)Pηi(n)=(1-PDi(n))·Pηi(n-1),n=1,…,NS.
Equation (3.8) is the fundamental recursion relation that guides the search evaluation. The initial value for this recursion relation (with n=0 scans designating the unsearched condition) is given by(3.9)Pηi(0)=1.
Since the recursion is defined only on the nondetection probability Pηi(n) (and not on the detection probability Pδi(n)), the initial probability for Pδi(n) is not explicitly required. However, we note that (3.7) and (3.9) imply Pδi(1)=PDi(1), as expected.By computing the evolution of the grid cell detection functionPDi(n) over successive passes as the search progress, (3.8) is used to recursively update the probability of the search object nondetection on a per cell basis. To obtain the first detection probability of any given cell at a given scan, the nondetection probability Pηi(n) is applied to (3.7). The spatial aggregation of these per cell first detection probabilities (3.7) is then a summation (as in (3.3)) to obtain the aggregate performance at any time step within the search process. Thus, the probability likelihood maps given by Pηi(n) and Pδi(n) provide the fundamental mechanism for capturing the search performance information for multiple scans of a search region, whereby all other aggregate search performance measures can be simply derived.We note that, in the case of independent scans,PDi(n)=PDiforalln, such that the recursion of (3.8) is a linear homogeneous recursion equation with general solution form Pηi(n)=αrn for some constants α and r. In this form, (3.8) is solved with r=(1-PDi), and the initial condition (3.9) is met with α=1, leading to(3.10)Pηi(n)=(1-PDi)n
and, correspondingly, the complementary first detection probability is given by(3.11)Pδi(n)=PDi(1-PDi)n-1
which is the same expression as (3.6) that was found by the Bernoulli trials for independent scans, as expected.


## 3.3. Utility Functions for Likelihood Updates

We next extend the detection likelihood modeling to include dependency on ancillary parameters that describe the interrelation between searcher and object properties. Such modeling may articulate random dependencies such as orientation angle of the search object or particular dependencies categorizing the capability of specific searchers to detect objects of a given type. Letθ∈Θ denote a random variable that corresponds to the ancillary parameter that is an object property that is independent of both the scan and the placement of the search object (such as an orientation angle of an object). Furthermore, let ϕn denote the deterministic ancillary parameters of the searcher that are specific to the nth scan (such as a specific searcher type). Let Pr(d∣x,θ;ϕn) represent the probability that an object located at x with random parameter θ would be found when the nth scan of a search is conducted at x given the scan parameter ϕn. Given a probability distribution h(θ):Θ→[0,1] of the random parameter θ, the marginal search detection likelihood function is given by(3.12)Pr(d∣x)=∫ΘPr(d∣x,θ;ϕn)h(θ)dθ=P̅d(x;ϕn).
We note that the overbar in P̅d is used to differentiate it from Pd which retains the dependency. Observe that, when h(θ)=constant, we have Pr(d∣x,θ;ϕn)∝Pr(d∣x;ϕn), and the detection likelihood depends only on placement x. In such cases, if there are no additional scan-specific dependencies, then ϕn=ϕ0foralln, and the expression for search detection is as previously defined, such that Pd(x)=P̅d(x;ϕ0).We presume (as indicated in (3.12)) that the ancillary parameter θ and the location x at which the object is placed are independent random variables. The consequence of this assumption is that the probability likelihood may be represented as a mean component with a zero-mean perturbation; that is,(3.13)Pr(d∣x,θ;ϕn)=P̅d(x;ϕn)+ΔP(θ;ϕn).
Here the search detection likelihood function is decomposed into a nominal value that varies over the search space (and may vary according to ϕn as well) and a perturbation that depends only on the ancillary parameters θ and ϕn. Again, for the simple case with no ancillary parameters, the search detection likelihood reverts to P̅d(x;ϕ0)=Pd(x).We next consider the evaluation of this search detection likelihood over a region𝒜 that has been partitioned into subregions {Gi} as described in Section 3.1. We focus our attention on a specific grid cell Gi, such that the object location density f(x) has been rescaled to fi(x) as in (3.2). Within this grid cell, the cell first detection probability Pδi(1) associated with the first (n=1) pass of cell Gi is now given as(3.14)Pδi(1)=∫Θ∫GiPr(d∣x,θ;ϕ1)fi(x)h(θ)dxdθ=∫GiP̅d(x;ϕ1)fi(x)dx+∫ΘΔP(θ;ϕ1)h(θ)dθ=PDi(1;ϕ1)+∫ΘΔP(θ;ϕ1)h(θ)dθ,
where PDi(1;ϕ1) explicitly shows the dependence on ϕ1. Since we generally expect any dependence on ϕn to be implied in the nth pass detection probability, we simplify notation to PDi(n;ϕn)↦PDi(n) with an implied dependence on ϕn. To further facilitate the exposition, we define an ancillary cell detection function ψ1(ϕn) that serves as a decision-theoretic utility function in ϕn for the nth search pass of a location. Specifically, we let(3.15)ψ1(ϕn)=∫ΘΔP(θ;ϕn)h(θ)dθ,n=1,2,….
However, ΔP(θ;ϕn) has been defined in (3.13) to be zero-mean perturbation term, so its integral over θ goes to zero, leading to ψ1(ϕn)=0. With that simplification, (3.14) becomes(3.16)Pδi(1)=PDi(1).
In similar fashion, the first pass nondetection probability for cell Gi is now given as(3.17)Pηi(1)=∫Θ∫Gi(1-Pr(d∣x,θ;ϕ1))fi(x)h(θ)dxdθ=1-∫GiP̅d(x;ϕ1)fi(x)dx-∫ΘΔP(θ;ϕ1)h(θ)dθ=1-PDi(1).
We note that the separation in (3.14) and (3.17) is  enabled by the separation of terms in (3.13), and that these expressions are equivalent to the first terms of (3.7) and (3.8). While the additional definition of the ancillary cell detection function ψ1 seems to be unnecessary, it will become useful in the following recursion terms.For subsequent passes over the grid cell, the perturbed likelihood equations are slightly more complicated. We assume the grid cell size is chosen to be small enough such thatP̅d(x;ϕn) is approximately constant over a cell, so that
(3.18)∫GiP̅d(x;ϕn)P̅d(x;ϕm)fi(x)dx≈PDi(n)PDi(m)foranyn,m.
Then, for the second pass, the equation for first detection takes the form(3.19)Pδi(2)=∫Θ∫GiPr(d∣x,θ;ϕ2)(1-Pr(d∣x,θ;ϕ1))fi(x)h(θ)dxdθ=∫GiP̅d(x;ϕ2)(1-P̅d(x;ϕ1))fi(x)dx+∫ΘΔP(θ;ϕ2)h(θ)dθ∫Gi(1-P̅d(x;ϕ1))fi(x)dx-∫ΘΔP(θ;ϕ1)h(θ)dθ∫Gi(P̅d(x;ϕ2))fi(x)dx-∫ΘΔP(θ;ϕ1)ΔP(θ;ϕ2)h(θ)dθ≈PDi(2)(1-PDi(1))+ψ1(ϕ2)(1-PDi(1))-ψ1(ϕ1)PDi(2)-ψ2(ϕ1,ϕ2),
where(3.20)ψ2(ϕ1,ϕ2)=∫ΘΔP(θ;ϕ1)ΔP(θ;ϕ2)h(θ)dθ
represents the second-order ancillary cell detection function. Recalling that ψ1(ϕn)=0 for any n, we have that(3.21)Pδi(2)≈PDi(2)Pηi(1)-ψ2(ϕ1,ϕ2).
Note that (3.21) is similar to (3.7) with n=2; however, there is now an additional term (given by ψ2) to account for the effects of the ancillary parameters defining the search. Similarly, the second pass recursion equation for nondetection becomes(3.22)Pηi(2)=∫Θ∫Gi(1-Pr(d∣x,θ;ϕ2))(1-Pr(d∣x,θ;ϕ1))fi(x)h(θ)dxdθ≈(1-PDi(2))Pηi(1)+ψ2(ϕ1,ϕ2).
In summary, for the second scan pass of the cell Gi, we have(3.23)Pδi(2)≈PDi(2)Pηi(1)+U(2),Pηi(2)≈(1-PDi(2))Pηi(1)-U(2),
where the utility function U(2)=-ψ2(ϕ1,ϕ2) represents the added utility of the search scan over that obtained with traditional independent passes. It is a result of marginalization over the control parameter θ for the given search scan perturbation function ΔP. This second pass utility function has two arguments, one for each ancillary parameter corresponding to each scan of the grid cell. More generally, we construct a set of functions that are readily calculated to assess search utility for any number of passes given the search path. It is desirable that these utility functions do not present unduly computational storage requirements associated with the detection and nondetection maps developed by the search evaluation.The general form for thenth scan cell nondetection probability becomes
(3.24)Pηi(n)=∫Θ∫Gi(1-Pr(d∣x,θ;ϕn))[∏j=1n-1(1-Pr(d∣x,θ;ϕj))]fi(x)h(θ)dxdθ=∫Gi(1-P̅d(x;ϕn))∫Θ[∏j=1n-1(1-Pr(d∣x,θ;ϕj))]h(θ)dθfi(x)dx-∫Θ(ΔP(θ;ϕn))∫Gi[∏j=1n-1(1-P̅d(x;ϕj)-ΔP(θ;ϕj))]fi(x)dxh(θ)dθ≈(1-PDi(n))Pηi(n-1)-U(n),
where we note that(3.25)Pηi(n-1)=∫Θ∫Gi∏j=1n-1(1-Pr(d∣x,θ;ϕj))fi(x)h(θ)dxdθ,
and U(n) is defined as the nth pass utility function. Note that the approximation in (3.24) comes from the approximation of (3.18) for spatial integrations over a grid cell. Similarly, for the nth scan cell first detection probability, we have(3.26)Pδi(n)=∫Θ∫GiPr(d∣x,θ;ϕn)[∏j=1n-1(1-Pr(d∣x,θ;ϕj))]fi(x)h(θ)dxdθ≈PDi(n)Pηi(n-1)+U(n)
with the same utility function U(n). Thus, the fundamental nondetection recursion of (3.8) is now generalized to the form of (3.24), and the complementary equation for first detection of (3.7) is generalized by (3.26).The form of the utility functionU(n) found in (3.26) and (3.24) is explicitly given by(3.27)U(n)=∫ΘΔP(θ;ϕn)[∏j=1n-1(1-PDi(j)-ΔP(θ;ϕj))]h(θ)dθ.
By multiplying out the product term, taking the integral over θ, and then rearranging terms, this function is written in the form
(3.28)U(n)=∑j=2n(-1)j-1∑γj∈μj-1n-1[ψj(ϕn,{ϕm};γj)∏k=1k≠γjn-1(1-PDi(k))]
with(3.29)ψj(ϕn,{ϕm};γj)=∫ΘΔP(θ;ϕn)∏m∈γjΔP(θ;ϕm)h(θ)dθ,
representing the jth ancillary function. Here U(n) represents an nth pass general utility function with μjm representing the set of all j-tuples of indices from 1 to m (i.e., μ34={(1,2,3),(1,3,4),(1,2,4),(2,3,4)}), and γj representing a specific j-tuple. For convenience, we rewrite the utility in the form U(n)=∑j=2nUj(n), where the component utility function Uj(n) denotes the contribution of the jth ancillary function ψj to the total utility.An important simplification of the utility function can be found when the nominal value of the search detection likelihoodP̅d is independent of the scan parameter ϕn. In particular, for those cases when P̅d(x;ϕn)=P̅d(x), (3.4) implies that PDi(n)=PDi for all n, such that the component utility functions reduce to(3.30)Uj(n)=(-1)j-1(1-PDi)n-j∑γj∈μj-1n-1ψj(ϕn,{ϕm};γj);
a form that is found to be convenient in many practical computational examples. Because the ancillary functions ψj may be computed and stored prior to any specific search evaluation, the forms in (3.28) and (3.30) are extremely computationally efficient.


## 3.4. Properties of Multipass Utility Functions

We next note some useful properties of the utility function that illustrate some features of ancillary dependency in search and also aid in the numerical evaluation. We first consider the case of noninteracting scans, that is, events whereby the detection performance of each scan is independent of the other scans. In such cases, we have the following lemma.Lemma 3.1.
For searches in which there is no scan-specific dependencyϕn, the utility function U(n) is a linear combination of the moments of the random perturbation component of detection likelihood ΔP(θ).Proof.
Assume a search with no scan-specific dependenciesϕn. Then P̅d(x;ϕn)=P̅d(x) which leads to PDi(n)=PDi for all n via (3.4). Furthermore, when there is no ϕn, we have ΔP(θ;ϕn)=ΔP(θ) which leads to ψj=∫ΔP(θ)jh(θ)dθ from (3.29). Thus, each component ψj is the jth moment of ΔP(θ). The form of the utility function U(n) in (3.30) now holds, and ∑ψj(ϕn,{ϕm};γj)=αψj, where α=(n-1j) is the number of terms in the sum. Thus, the component utilities are given by Uj(n)=(-1)j-1(n-1j)(1-PDi)n-jψj=c(n,j)ψj, where c(n,j) is a constant that depends on n and j. Now, U(n)=∑j=2nUj(n)=∑j=2nc(n,j)ψj, which is a linear combination of the moments ψj of ΔP(θ).This lemma naturally leads to the following theorem about the construction of zero-utility functions.Theorem 3.2.
If a search has no scan-specific dependenciesϕn, then the utility is zero through the nth scan if the first n moments of the random perturbation ΔP(θ) are zero.Proof.
The proof of this theorem follows from Lemma3.1. Assume a search has no scan-specific dependencies ϕn. Furthermore, assume the first n moments of ΔP(θ) are zero. Let v∈ℝn be a vector of the first n moments of ΔP(θ). From Lemma 3.1, it is known that there exists a vector u∈ℝn such that U(n)=uTv. However, vj=∫ΔP(θ)jh(θ)dθ=0forallj, so that U(n)=uT0=0.An obvious case of the conditions in Theorem3.2 is the case of no ancillary dependency at all. In such cases, there are no scan-specific dependencies ϕn and the random perturbation term ΔP(θ)=0 for all θ. Thus, the conditions of the theorem are met and we have zero utility, as expected. However, there are conditions under which we may have no scan-specific dependencies ϕn, but still have a non-trivial ΔP(θ), for which we have the following important corollary to Theorem 3.2.Corollary 3.3.
In searches with no scan-specific dependenciesϕn, there may still exist a non-zero utility if there are non-zero moments of the random perturbation ΔP(θ).The importance of this corollary is that a model may be constructed to incorporate effects that vary randomly over the scans, but have no scan-specific dependency associated with them. These effects are naturally modeled with theθ dependency in ΔP(θ;ϕn) and can lead to non-zero utility, thus showing a change in search performance relative to the situation with no ancillary dependencies.For the special case of repeated events, which are more restrictive than independent events, the utility can be used to show that the search effectiveness actually decreases. This is illustrated by the following theorem.Theorem 3.4.
For a search component comprised of repeated events, there is non-positive utility, that is,U(n)≤0.Proof.
Assume a search component comprised of repeated events, such thatϕn=ϕm for all n,m. From (3.29), we have ψj(ϕn)=∫ΔP(θ;ϕn)jh(θ)dθ. Since ΔP(θ;ϕn) is, by definition, a zero-mean real-valued function, we have that all of the odd moments of ΔP(θ;ϕn) are also zero, specifically ∫ΔP(θ;ϕn)jh(θ)dθ=0 for j odd. Since P̅d(x;ϕn)=P̅d(x) for repeated events, we have the form of (3.30) for component utility. From (3.30), we then have Uj=0 for j odd. Thus, U(n)=∑j=1n/2U2j(n) for n even, and U(n)=∑j=1(n-1)/2U2j(n) for n odd. Since 0≤PDi≤1, we have (1-PDi)n-2j≥0. Furthermore, ψ2j≥0 for all arguments. Thus, U2j(n)=(-1)(1-PDi)n-2j∑ψ2j≤0 for all positive integer values of j, and therefore U(n)≤0.This theorem is important since utility is an additive component of the standard independent event recursions. If a search is performed without independent examination, but instead a repeatable examination, then the benefits of multiple independent scans are lost, yet the utility formulation can be utilized to quantify this decrease in performance.The computation of utility becomes combinatorially complex as the number of passesn of a cell increases. This is due to the summation over the components of μjn-1, which has size (n-1j). To reduce this computational burden, we utilize the following theorem that gives bounds on the magnitude of the component utility functions Uj(n).Theorem 3.5.
For a search with cell detection probabilities that are independent of scan number, and with random perturbation bounded by1/2, the component utility functions are bounded by
(3.31)|Uj(n)|≤12j(n-1j-1)(1-PDi)n-j.Proof.
Consider a search with scan independent detection probabilities, such thatPDi(n)=PDiforalln. Then the component utility form of (3.30) holds. The function ΔP(θ;ϕn) is a zero-mean function over a probability space that is bounded by 1/2, so the integral expression ∫|ΔP(θ;ϕn)|h(θ)dθ≤1/2. Furthermore, the integral composed of the product of j of these terms under the integrand is also bounded by (1/2)j. Thus, we have |ψj|≤1/2j. The summation in (3.30) contains (n-1j-1) terms, such that the summation is bounded by 2-j(n-1j-1). Substituting this into (3.30) yields |Uj(n)|≤2-j(n-1j-1)(1-PDi)n-j, thus demonstrating the bound in the theorem.


## 4. Applications

In this section, we articulate the application of the utility-based likelihood structure for the evaluation of search performance. To do this, we first establish a constructive baseline whereby no ancillary dependency is exhibited. This is done to demonstrate the efficacy of the grid-based numerical calculation and to validate the asserted modeling assumptions. We follow this with exemplary cases exhibiting a respective discrete or continuous ancillary dependency. The discussion within the examples highlights the corresponding distinct considerations that these respective modeling paradigms present.


### 4.1. Example: Generic Search with Overlapping Scans

We first consider an example in which there are known analytical solutions. Consider the search for objects within a rectangular region using a ladder-type (or mowing-the-lawn) search pattern. In this case, the searcher is a simple searcher with no ancillary dependencies. The absence of an ancillary dependency allows the recursion in detection likelihood to be based solely upon the single search pass expected probability of detection.Let the search over the partitioned placement space be defined to occur as a sequence of partial searchesIP={Iℓ}ℓ=0Imax, where Iℓ denotes a set of grid cell indices (for grid cells {Gi}) covered during the time interval over which the partial search is conducted. The time interval for partial search is chosen small enough so that no grid cell Gi is visited more than once in that time interval. Sequence IP then corresponds to a temporal partitioning of the total search trajectory into nonoverlapping segments. For each interval Iℓ, define a region Cℓ centered about the partial search trajectory segment where detection is possible. Unfortunately, these detection regions generally overlap across adjacent search intervals. To preserve the notion of independent persistent detection observations within the search paradigm whereby the observation is interrogated only once during the partial search, we define the index sets as(4.1)Iℓ={i∣Gi∈Cℓ∖Cℓ-1}.
Thus, we restrict the set of indices Iℓ to be that set of grid cell indices that are newly covered by the time interval. This “slither” of cells provides the subregion of the search space that has been additionally searched in the new partial search time interval. Multiple independent detection events are allowed to occur at a given cell only with the search path doubling back over itself (separated by at least one partial search time interval) or by distinct sensor platforms performing a coordinated search of the cell, which is not a concern in this example.When multiple pass searches occur, cell indices that are represented singularly within the distinct partial search time intervals are repeated over the course of multiple intervals. We consider cell-based search detection probabilitiesPDi(n) that are independent of n, so that PDi(n)=PDi. Furthermore, by Theorem 3.2, the utility for this problem U(n)=0. Therefore, for this search, the cell-referenced recursions of (3.26) and (3.24) are given by(4.2)Pδi(n)=PDiPηi(n-1),Pηi(n)=(1-PDi)Pηi(n-1),
where we have replaced the approximation (≈) with equality for ease of exposition. As previously solved in Section 3.2, this special case of constant coefficient linear homogeneous recursion equations can be solved analytically to arrive at(4.3)Pδi(n)=(1-PDi)n-1PDi.
The cumulative probability of detecting the target within cell Gi up through the Nith scan of that cell is then given by(4.4)Pr(d,{Gi,Ni})=Pr(Gi)∑n=1NiPδi(n)=Pr(Gi)[1-(1-PDi)Ni],
where Ni is the number of searches of cell Gi, and Pr(Gi)=∫Gif(x)dx is the probability of the target being located in cell Gi. The aggregate search probability for the search plan is now given by summing these individual cell probabilities(4.5)PSP=∑ℓ=1Imax∑GiPr(d,{Gi,Ni(Iℓ)}),
where the summation is performed both over the partial search time intervals ℓ as well as the spatially distributed grid cells Gi. Furthermore, Ni(Iℓ) explicitly notes the dependency of how many times cell Gi has been searched up to (and including) the search interval Iℓ. Thus, the search evaluation properly accounts for both the temporal and spatial aspects of the complex search problem.We next consider the numerical evaluation of the search probability compared to known theoretical benchmarks. The search path employed is the vertical ladder path depicted in Figure1. Nominally, such search path construction would extend beyond the search region so that all the space is covered. We employ the internal ladder-type search paths shown in Figure 1 to allow a comparison of the grid-based numeric calculation with theoretical results. We consider a region with N0 objects placed according to a distribution function f(x). The theoretical baseline comprises the probability of detecting n>k objects within the search path, given by (see [24])Figure 1
Experimental geometry for two searchers performing a vertical search plan. The blue squares, green diamonds, and red circles represent nominal locations of three different types of search objects, respectively, that are sampled withE{N0}=5. Only the initial history of the search path is shown for clarity.(4.6)PSS(n>k)=1-exp(E{N0}PdA0∫GSPf(x)dx),
where A0=∫𝒜1dx is the area of the search region.In Figure2, we show the performance of the theoretical and aggregated numerical search for this problem as black and red curves, respectively. The individual curves illustrate different values of k for probability of k>n detections for a scenario with E{N0}=5. The baseline theoretical curve is derived under an assumption of single pass coverage. Initially, the theoretical and numerical are nearly identical, as the paths do not overlap. However, after 4 hours of search time, path overlap commences and the curves deviate. Henceforth from this point in time, search probability aggregation occurs at the reduced rate given by the pass recursion probability.Figure 2
Search performance with overlapping search paths for cumulative probability of achievingk>n detections (n={0,2,4}). Red curves show the numerical calculation and black curves show a theoretical result illustrating single pass coverage.


### 4.2. Example: Search for Multiple Object Types

This example illustrates utility functionals that apply over extended discrete likelihood structures. These extensions arise from a variation in sensor detection performance due to a specialization in detection characteristics according to search object type. That is, certain sensors perform better against certain target types, and collaboration  between sensor platforms may be utilized to maximize the overall detection performance of the search group.In this case, the ancillary random variableθ is the search object type; that is, θ∈{mi}i=1M for M discrete object types. The ancillary deterministic parameter ϕn represents the searcher type that has been deployed to conduct search. The dependency manifests itself as a conditional probability of detection for each of the search object types. The discrete ancillary random variable (equivalent to (3.12)) for this sensor-specific detection likelihood takes the form of a mixture over possible search object types, as(4.7)Pr(d∣x;ϕn)=∑mj∈MPr(d∣x,mj;ϕn)Pr(mj∣x)=P̅d(x;ϕn),
where ϕn denotes the searcher type that is deployed for the nth search pass. The resulting detection likelihood function represents a marginalization over search object type aggregating the searcher/object-specific combinations. In this case, the placement likelihood over the space 𝒜 may vary for each of the respective search object types. The conditioning on x acknowledges a possible variation in search object composition over the search space.Analogous to (3.13), the detection likelihood function is formulated as a mean value with an additive variational quantity symptomatic of the ancillary dependency being modeled. That is, the likelihood function becomes(4.8)Pr(d∣x,θ;ϕn)=Pr(d∣x,mj;ϕn)=P̅d(x;ϕn)+ΔP(mj∣x;ϕn).
Assume as before that the grid resolution Gi is selected such that likelihood variations within the grid cell are insignificant, yet the scale is large enough to ensure the independence of detection events over the grid. Assume as well that the mixture weights do not vary within the grid cell; that is, ΔP(mj∣x;ϕn)=ΔP(mj;ϕn). Then, the first pass grid cell detection probability attained when deploying searcher ϕ1 becomes(4.9)Pδi(1)=∑mj∈M∫GiPr(d∣x,mj;ϕ1)fi(x)Pr(mj∣x)dx=∫GiP̅d(x;ϕ1)fi(x)dx+∑mj∈MΔP(mj;ϕ1)Pr(mj∣x∈Gi)≈PDi(ϕ1)+ψ1(ϕ1),
with the ancillary dependency condition(4.10)ψ1(ϕn)=∑mj∈MΔP(mj;ϕn)Pr(mj∣x∈Gi)=0
holding due to the definition of ΔP as a zero-mean perturbation term. The corresponding first pass grid cell probability of nondetection becomes(4.11)Pηi(1)=∑mj∈M∫Gi(1-Pr(d∣x,mj;ϕ1))fi(x)Pr(mj∣x)dx≈1-PDi(ϕ1)-ψ1(ϕ1)
yielding similar results to the previous sections.To develop the probability functions for further passes, we proceed with the utility function development by constructing a set of ancillary functions{ψj}j=2∞. The ψ2 ancillary function is explicitly given by(4.12)ψ2(ϕ1,ϕ2)=∑mj∈MΔP(mj;ϕ1)ΔP(mj;ϕ2)Pr(mj∣x∈Gi),
and the general form for the ψj term is given by(4.13)ψj(ϕn,{ϕm};γj)=∑mj∈MΔP(mj;ϕn)∏m∈γjΔP(mj;ϕm)Pr(mj∣x∈Gi),
where γj is a j-tuple used in the utility form of (3.28). These terms are calculated directly and applied to either (3.24) or (3.26) to realize the likelihood recurrence over the search field.As a numerical example of the searcher specialization, consider the case where a single grid cellGi is searched multiple times by the same searcher ϕn with mean detection probability PDi(ϕn)=0.5. Let ΔP=α·min{PDi(ϕn),1-PDi(ϕn)} represent a maximum deviation from this mean value as search object type is varied where α serves as a scale factor indicative of the variability. Let the search paradigm consist of finding three possible object types with the variation in detection probability given by ΔP(mj;ϕn)∈{ΔP,0,-ΔP}. Figure 3 illustrates the negative impact that searching the grid cell with the same searcher type can have on the resulting multipass search effectiveness. In this example, each object type is equally likely (i.e., Pr(mj∣x∈Gi)=1/3 for j=1,2,3). The search probability (as given by the sequence Pη(n)) and corresponding utility are depicted  for each of the set of α values in {1.0,0.9,0.5,and0.0}. The intent is to show the impact of the size of the variation from the mean detection likelihood value on the multipass detection probability. As this example presumes only one searcher type (i.e., ϕn is constant), all associated utilities are negative.Search probability and cell utility as a function of pass number for a specialized searcher with varying values of deviationα from mean detection probability. (blue: α=1.0, cyan: α=0.9, yellow: α=0.5, red: α=0.0).


### 4.3. Example: Search with Target Orientation Dependency

We next introduce a detection likelihood dependency example that is in the form of a continuous random variable. Here, we impart a dependency on detection due to the angular separation between searcher and search object orientation. For instance, in optical sensing, objects that present a significant shadow are considered more detectable, and that shadow depends on object orientation relative to the searcher look direction. As an example, consider a sinusoidal representation of detection likelihood in the form of (3.13) given by(4.14)Pr(d∣x,θ;ϕn,Gi)=PDi+Pθicos(2(θ-ϕn)),
where Pθi is a cell-specific constant indicative of the size of the variation, θ denotes search object orientation, and ϕn denotes searcher orientation during search pass n of cell Gi. This functional representation allows for maximum detection probability when the object orientation is aligned with the searcher motion axis (i.e., when the scans are perpendicular to the object orientation).Let search object orientation angle be denoted asθ∈[0,2π) with h(θ)=1/2π over that interval. Observe for these conditions that(4.15)ψ1(ϕ1)=∫02π12πPθcos(2(θ-ϕ1))dθ=0.
That is, as expected, there is no utility in specifying the searcher axis to address this random object orientation for the first pass over the grid cell.Using the trigonometric identity(4.16)cos(θ-θA)cos(θ-θB)=12cos(θB-θA)+12cos(2θ-θA-θB),
the ancillary functions ψ2(ϕ1,ϕ2) takes the form(4.17)ψ2(ϕ1,ϕ2)=∫02π12πPθ2cos(2θ-2ϕ1)cos(2θ-2ϕ2)dθ=Pθ22cos(2(ϕ2-ϕ1))
with corresponding utility U(2)=-ψ2(ϕ1,ϕ2). We note that, in general, the second pass detection probability is maximized when utility U(2) is maximized. This occurs for this sinusoidal model of orientation dependency when 2(ϕ2-ϕ1)=±π or simply when ϕ2=ϕ1±π/2 and the first two passes of the searcher are at right angles to each other.We note that the third ancillary functionψ3(ϕ1,ϕ2,ϕ3) for the likelihood function of (4.14) is given by(4.18)ψ3(ϕ1,ϕ2,ϕ3)=∫02π12πPθ3cos(2θ-2ϕ1)cos(2θ-2ϕ2)cos(2θ-2ϕ3)dθ=0,
and thus U3(3)=0. However, the utility function for the third pass U(3) still has non-zero components, and from (3.30) we have(4.19)U(3)=U2(3)+U3(3)=-(1-PDi)∑j=12ψ2(ϕ3,ϕj)+0=-Pθ22(1-PDi)[cos(2(ϕ3-ϕ1))+cos(2(ϕ3-ϕ2))],
where we recall that U2(3) represents the contribution of the ψ2 ancillary function to the third pass utility function U(3). In general, the ψ2 contribution for the nth pass utility function using this sinusoidal model takes the form (see (3.30))(4.20)U2(n)=-(1-PDi)n-2∑j=1n-1Pθ22cos(2(ϕn-ϕj))=-Pθ22(1-PDi)n-2(cos2ϕn∑j=1n-1cos2ϕj+sin2ϕn∑j=1n-1sin2ϕj).
Similarly, for this sinusoidal model, the fourth ancillary function ψ4 is generally non-zero, becoming(4.21)ψ4(ϕ1,ϕ2,ϕ3,ϕ4)=∫02π12πPθ4∏j=14cos(2(θ-ϕj))dθ=Pθ48[cos(2(ϕ4-ϕ3))cos(2(ϕ2-ϕ1))+cos(2(ϕ4-ϕ1))cos(2(ϕ3-ϕ2))+cos(2(ϕ4-ϕ2))cos(2(ϕ1-ϕ3))].
The corresponding U4(n) utility component aggregating the contribution of the ψ4 ancillary function on the nth pass utility where n≥4 takes the form(4.22)U4(n)=(1-PDi)n-4(Pθ48)∑j1=1n-1[cos(2(ϕn-ϕj1))∑j3=2j3≠j1n-1∑j2=1j2≠j1j3-1cos(2(ϕj3-ϕj2))].
As before, the odd ancillary function ψ5 integrates to zero. The analytic calculation of utility function components can continue until a specified degree of accuracy has been reached, as given in Theorem 3.5. For the purpose of this specific example, we terminate our discussion at ψ5.Naturally, an issue that is paramount in any extended likelihood structure is the amount of processing and storage necessary to calculate utility function components. Ideally, we wish to minimize both storage and computational loading. Table1 provides useful recursions for calculating the U2(n) and U4(n) components. Indicated in the table is the pass number in which the terms become non-zero or non-empty in the case of vector quantities. For the U2(n) component, observe from (4.17) that temporary variables defined in Table 1 reduce storage requirements to a two-parameter grid cell attribute. This same information must be stored in vector format, however, to apply it properly for the U4(n) component. The U4(n) recursion increases storage requirements in that three vectors of size n and one scalar attribute must now be saved for each grid cell location along with the stored quantities for the U2(n) calculation. Observe how the recursions in Table 1 separate the contribution of the nth pass control parameter from the preceding parameter values. This methodology generalizes for higher order recursions.Table 1
Recursion equations for computing component utilities for a sinusoidal orientation dependency.
Recursion for calculatingU2Initializationu2c(0)=u2s(0)=0Utility Calcw2=cos2ϕnu2c(n-1)+sin2ϕnu2s(n-1)n>1U2(n)=-(1-PDi)n-2(Pθ2/2)w2n>1Updateu2c(n)=u2c(n-1)+cos2ϕnn>0u2s(n)=u2s(n-1)+sin2ϕnn>0Recursion for calculatingU4InitializationVs(0)=Vc(0)=V4(0)=[]u4(0)=u4(1)=0Utility CalcVϕn=Vc(n-1)cos2ϕn+Vs(n-1)sin2ϕnn>1w4=[u4(n-1)-V4(n-1)]·VϕnT(n)n>3U4(n)=-(1-PDi)n-4(Pθ4/8)w4n>3UpdateVs(n)=[Vs(n-1)sin2ϕn]n>0Vc(n)=[Vc(n-1)cos2ϕn]n>0V4(n)=[(V4(n-1)+Vϕn)w2]n>1u4(n)=u4(n-1)+w2n>1We illustrate the impact of orientation and its utility calculation on search performance via the construction of search plans representing limiting cases on utility. Figure1 in its continuing pattern depicts a vertical search plan in which the detection likelihood remains relatively fixed over the plan. Here, the first searcher starts at the lower left corner of the space and commences a vertical ladder search. The second searcher starts at the upper right corner and similarly performs a vertical ladder search. Figure 4 depicts the second limiting case search plan. The first part of the search remains unchanged from the vertical ladder search. However, when the two searchers reach proximity to each other, they jointly turn at right angles to alter their orientation, that is, ϕ2=ϕ1±π/2 as above, while maintaining coverage of the space. Hence, this plan seeks to achieve a positive utility through orientation diversity. This plan also demonstrates the capacity of the search evaluation modeling technique to account for arbitrary searcher motion in collaborative, multipass search plans.Figure 4
Experimental geometry for two searchers performing an orientation switch search plan. Only the initial history of the search path is shown for clarity.The utilities achieved in the two search plans are illustrated in Figures5 and 6, respectively. Note that what is depicted is the average utility over the cells in the sequential update. For the vertical search plan, noninteraction between searchers results in a zero utility prior to search path overlap. When multipass coverage does occur, the resulting utility is negative, following Theorem 3.4, as the searchers have the same orientation (Incidental “spikes” into positive utility occur as the searchers maneuver between search legs). Orientation switching in the second plan yields the desired generally positive utility for both searchers as multipass coverage is achieved over the cells.Figure 5
Average utility for each of two searchers performing a vertical search plan with orientation dependency (the two curves are nearly identical).Figure 6
Average utility for each of two searchers performing a switched orientation search plan with orientation dependency (searcher 1 utility is in blue and searcher 2 utility is in red).These geometries represent two-pass search strategies developed over a benign search environment under which uniformity in placement preference and detection likelihood is assumed. More generally, spatial variability in these quantities may induce a variability in the number of search passes conducted over the space. To illustrate the capacity of the algorithm to accommodate higher order search pass sequences, we include a deviated coverage plan in which a local assessment of the direction of highest coverage induces the searchers to deviate from the standard ladder search. While the searchers attempt to fulfill a coverage strategy, the resulting search paths take on a random appearance. Further, in the process of deviating towards cells of highPηi, a natural variability in the number of cell search passes occurs over the cell grid construct. A partial realization of the search geometry is depicted  in Figure 7 with a histogram of the achieved search pass number provided in Figure 8. The average utility that results for the entire search path set is shown in Figure 9.Figure 7
Experimental geometry for two searchers performing a deviated coverage search plan. Only the initial history of the search path is shown for clarity.Figure 8
Search pass histogram for the deviated coverage search plan.Figure 9
Average utility for each of two searchers performing a deviated coverage search plan with orientation dependency (searcher 1 utility is in blue and searcher 2 utility is in red).The impact of these paths on the selected search criteria is shown in Figure10. For these evaluations, only one object type is considered. The uniform placement prior has an expected number of objects of E{N0}=5 over the space. The probability that k>n objects will be detected along the search paths is calculated as a function of search time for n={0,2,4} for each of the search plans. The limiting utility realizations yield corresponding search performance curves with the orientation switching plan clearly outperforming both the vertical ladder search and the deviated coverage plan. It is predictable that the deviated coverage search strategy yields a lower performance than the ladder searches during the initial (single pass) phase of the plan [5]. However, during the latter (multipass) phase of the plan, the deviated coverage strategy surpasses the vertical search strategy (but not the orientation switching plan) due to the negative utility incurred by the vertical ladder search (as in Figure 5).Figure 10
Search performance with orientation dependency for cumulative probability of achievingk>n detections (n={0,2,4}). Red curves represent the vertical search plan, blue curves represent a orientation switch search plan and grey curves indicate the deviated coverage search plan.We finish by presenting the results of a Monte Carlo experiment for the deviated coverage search plan. An ensemble of 1000 runs of a simulated placement scenario is executed and the frequency of occurrence results are calculated. For the experiment, objects are placed uniformly with a random object orientation assigned independently for each object. The detection event is simulated in a sequential realization of the search trajectories by a random draw governed according to (4.14). The results are illustrated in Figure 11. In the figure, the mean frequency of occurrence is plotted against the predicted successful search probability for the k>n detection events. Standard deviation bounds at the 3σ level are also depicted in the figure to indicate the estimation uncertainty in the experiment. The usefulness of Table 1 is validated under these operating conditions as the prediction is contained within the uncertainty interval.Figure 11
Monte Carlo performance results with orientation dependency for cumulative probability of achievingk>n detections (n={0,2,4}).


## 4.1. Example: Generic Search with Overlapping Scans

We first consider an example in which there are known analytical solutions. Consider the search for objects within a rectangular region using a ladder-type (or mowing-the-lawn) search pattern. In this case, the searcher is a simple searcher with no ancillary dependencies. The absence of an ancillary dependency allows the recursion in detection likelihood to be based solely upon the single search pass expected probability of detection.Let the search over the partitioned placement space be defined to occur as a sequence of partial searchesIP={Iℓ}ℓ=0Imax, where Iℓ denotes a set of grid cell indices (for grid cells {Gi}) covered during the time interval over which the partial search is conducted. The time interval for partial search is chosen small enough so that no grid cell Gi is visited more than once in that time interval. Sequence IP then corresponds to a temporal partitioning of the total search trajectory into nonoverlapping segments. For each interval Iℓ, define a region Cℓ centered about the partial search trajectory segment where detection is possible. Unfortunately, these detection regions generally overlap across adjacent search intervals. To preserve the notion of independent persistent detection observations within the search paradigm whereby the observation is interrogated only once during the partial search, we define the index sets as(4.1)Iℓ={i∣Gi∈Cℓ∖Cℓ-1}.
Thus, we restrict the set of indices Iℓ to be that set of grid cell indices that are newly covered by the time interval. This “slither” of cells provides the subregion of the search space that has been additionally searched in the new partial search time interval. Multiple independent detection events are allowed to occur at a given cell only with the search path doubling back over itself (separated by at least one partial search time interval) or by distinct sensor platforms performing a coordinated search of the cell, which is not a concern in this example.When multiple pass searches occur, cell indices that are represented singularly within the distinct partial search time intervals are repeated over the course of multiple intervals. We consider cell-based search detection probabilitiesPDi(n) that are independent of n, so that PDi(n)=PDi. Furthermore, by Theorem 3.2, the utility for this problem U(n)=0. Therefore, for this search, the cell-referenced recursions of (3.26) and (3.24) are given by(4.2)Pδi(n)=PDiPηi(n-1),Pηi(n)=(1-PDi)Pηi(n-1),
where we have replaced the approximation (≈) with equality for ease of exposition. As previously solved in Section 3.2, this special case of constant coefficient linear homogeneous recursion equations can be solved analytically to arrive at(4.3)Pδi(n)=(1-PDi)n-1PDi.
The cumulative probability of detecting the target within cell Gi up through the Nith scan of that cell is then given by(4.4)Pr(d,{Gi,Ni})=Pr(Gi)∑n=1NiPδi(n)=Pr(Gi)[1-(1-PDi)Ni],
where Ni is the number of searches of cell Gi, and Pr(Gi)=∫Gif(x)dx is the probability of the target being located in cell Gi. The aggregate search probability for the search plan is now given by summing these individual cell probabilities(4.5)PSP=∑ℓ=1Imax∑GiPr(d,{Gi,Ni(Iℓ)}),
where the summation is performed both over the partial search time intervals ℓ as well as the spatially distributed grid cells Gi. Furthermore, Ni(Iℓ) explicitly notes the dependency of how many times cell Gi has been searched up to (and including) the search interval Iℓ. Thus, the search evaluation properly accounts for both the temporal and spatial aspects of the complex search problem.We next consider the numerical evaluation of the search probability compared to known theoretical benchmarks. The search path employed is the vertical ladder path depicted in Figure1. Nominally, such search path construction would extend beyond the search region so that all the space is covered. We employ the internal ladder-type search paths shown in Figure 1 to allow a comparison of the grid-based numeric calculation with theoretical results. We consider a region with N0 objects placed according to a distribution function f(x). The theoretical baseline comprises the probability of detecting n>k objects within the search path, given by (see [24])Figure 1
Experimental geometry for two searchers performing a vertical search plan. The blue squares, green diamonds, and red circles represent nominal locations of three different types of search objects, respectively, that are sampled withE{N0}=5. Only the initial history of the search path is shown for clarity.(4.6)PSS(n>k)=1-exp(E{N0}PdA0∫GSPf(x)dx),
where A0=∫𝒜1dx is the area of the search region.In Figure2, we show the performance of the theoretical and aggregated numerical search for this problem as black and red curves, respectively. The individual curves illustrate different values of k for probability of k>n detections for a scenario with E{N0}=5. The baseline theoretical curve is derived under an assumption of single pass coverage. Initially, the theoretical and numerical are nearly identical, as the paths do not overlap. However, after 4 hours of search time, path overlap commences and the curves deviate. Henceforth from this point in time, search probability aggregation occurs at the reduced rate given by the pass recursion probability.Figure 2
Search performance with overlapping search paths for cumulative probability of achievingk>n detections (n={0,2,4}). Red curves show the numerical calculation and black curves show a theoretical result illustrating single pass coverage.


## 4.2. Example: Search for Multiple Object Types

This example illustrates utility functionals that apply over extended discrete likelihood structures. These extensions arise from a variation in sensor detection performance due to a specialization in detection characteristics according to search object type. That is, certain sensors perform better against certain target types, and collaboration  between sensor platforms may be utilized to maximize the overall detection performance of the search group.In this case, the ancillary random variableθ is the search object type; that is, θ∈{mi}i=1M for M discrete object types. The ancillary deterministic parameter ϕn represents the searcher type that has been deployed to conduct search. The dependency manifests itself as a conditional probability of detection for each of the search object types. The discrete ancillary random variable (equivalent to (3.12)) for this sensor-specific detection likelihood takes the form of a mixture over possible search object types, as(4.7)Pr(d∣x;ϕn)=∑mj∈MPr(d∣x,mj;ϕn)Pr(mj∣x)=P̅d(x;ϕn),
where ϕn denotes the searcher type that is deployed for the nth search pass. The resulting detection likelihood function represents a marginalization over search object type aggregating the searcher/object-specific combinations. In this case, the placement likelihood over the space 𝒜 may vary for each of the respective search object types. The conditioning on x acknowledges a possible variation in search object composition over the search space.Analogous to (3.13), the detection likelihood function is formulated as a mean value with an additive variational quantity symptomatic of the ancillary dependency being modeled. That is, the likelihood function becomes(4.8)Pr(d∣x,θ;ϕn)=Pr(d∣x,mj;ϕn)=P̅d(x;ϕn)+ΔP(mj∣x;ϕn).
Assume as before that the grid resolution Gi is selected such that likelihood variations within the grid cell are insignificant, yet the scale is large enough to ensure the independence of detection events over the grid. Assume as well that the mixture weights do not vary within the grid cell; that is, ΔP(mj∣x;ϕn)=ΔP(mj;ϕn). Then, the first pass grid cell detection probability attained when deploying searcher ϕ1 becomes(4.9)Pδi(1)=∑mj∈M∫GiPr(d∣x,mj;ϕ1)fi(x)Pr(mj∣x)dx=∫GiP̅d(x;ϕ1)fi(x)dx+∑mj∈MΔP(mj;ϕ1)Pr(mj∣x∈Gi)≈PDi(ϕ1)+ψ1(ϕ1),
with the ancillary dependency condition(4.10)ψ1(ϕn)=∑mj∈MΔP(mj;ϕn)Pr(mj∣x∈Gi)=0
holding due to the definition of ΔP as a zero-mean perturbation term. The corresponding first pass grid cell probability of nondetection becomes(4.11)Pηi(1)=∑mj∈M∫Gi(1-Pr(d∣x,mj;ϕ1))fi(x)Pr(mj∣x)dx≈1-PDi(ϕ1)-ψ1(ϕ1)
yielding similar results to the previous sections.To develop the probability functions for further passes, we proceed with the utility function development by constructing a set of ancillary functions{ψj}j=2∞. The ψ2 ancillary function is explicitly given by(4.12)ψ2(ϕ1,ϕ2)=∑mj∈MΔP(mj;ϕ1)ΔP(mj;ϕ2)Pr(mj∣x∈Gi),
and the general form for the ψj term is given by(4.13)ψj(ϕn,{ϕm};γj)=∑mj∈MΔP(mj;ϕn)∏m∈γjΔP(mj;ϕm)Pr(mj∣x∈Gi),
where γj is a j-tuple used in the utility form of (3.28). These terms are calculated directly and applied to either (3.24) or (3.26) to realize the likelihood recurrence over the search field.As a numerical example of the searcher specialization, consider the case where a single grid cellGi is searched multiple times by the same searcher ϕn with mean detection probability PDi(ϕn)=0.5. Let ΔP=α·min{PDi(ϕn),1-PDi(ϕn)} represent a maximum deviation from this mean value as search object type is varied where α serves as a scale factor indicative of the variability. Let the search paradigm consist of finding three possible object types with the variation in detection probability given by ΔP(mj;ϕn)∈{ΔP,0,-ΔP}. Figure 3 illustrates the negative impact that searching the grid cell with the same searcher type can have on the resulting multipass search effectiveness. In this example, each object type is equally likely (i.e., Pr(mj∣x∈Gi)=1/3 for j=1,2,3). The search probability (as given by the sequence Pη(n)) and corresponding utility are depicted  for each of the set of α values in {1.0,0.9,0.5,and0.0}. The intent is to show the impact of the size of the variation from the mean detection likelihood value on the multipass detection probability. As this example presumes only one searcher type (i.e., ϕn is constant), all associated utilities are negative.Search probability and cell utility as a function of pass number for a specialized searcher with varying values of deviationα from mean detection probability. (blue: α=1.0, cyan: α=0.9, yellow: α=0.5, red: α=0.0).


## 4.3. Example: Search with Target Orientation Dependency

We next introduce a detection likelihood dependency example that is in the form of a continuous random variable. Here, we impart a dependency on detection due to the angular separation between searcher and search object orientation. For instance, in optical sensing, objects that present a significant shadow are considered more detectable, and that shadow depends on object orientation relative to the searcher look direction. As an example, consider a sinusoidal representation of detection likelihood in the form of (3.13) given by(4.14)Pr(d∣x,θ;ϕn,Gi)=PDi+Pθicos(2(θ-ϕn)),
where Pθi is a cell-specific constant indicative of the size of the variation, θ denotes search object orientation, and ϕn denotes searcher orientation during search pass n of cell Gi. This functional representation allows for maximum detection probability when the object orientation is aligned with the searcher motion axis (i.e., when the scans are perpendicular to the object orientation).Let search object orientation angle be denoted asθ∈[0,2π) with h(θ)=1/2π over that interval. Observe for these conditions that(4.15)ψ1(ϕ1)=∫02π12πPθcos(2(θ-ϕ1))dθ=0.
That is, as expected, there is no utility in specifying the searcher axis to address this random object orientation for the first pass over the grid cell.Using the trigonometric identity(4.16)cos(θ-θA)cos(θ-θB)=12cos(θB-θA)+12cos(2θ-θA-θB),
the ancillary functions ψ2(ϕ1,ϕ2) takes the form(4.17)ψ2(ϕ1,ϕ2)=∫02π12πPθ2cos(2θ-2ϕ1)cos(2θ-2ϕ2)dθ=Pθ22cos(2(ϕ2-ϕ1))
with corresponding utility U(2)=-ψ2(ϕ1,ϕ2). We note that, in general, the second pass detection probability is maximized when utility U(2) is maximized. This occurs for this sinusoidal model of orientation dependency when 2(ϕ2-ϕ1)=±π or simply when ϕ2=ϕ1±π/2 and the first two passes of the searcher are at right angles to each other.We note that the third ancillary functionψ3(ϕ1,ϕ2,ϕ3) for the likelihood function of (4.14) is given by(4.18)ψ3(ϕ1,ϕ2,ϕ3)=∫02π12πPθ3cos(2θ-2ϕ1)cos(2θ-2ϕ2)cos(2θ-2ϕ3)dθ=0,
and thus U3(3)=0. However, the utility function for the third pass U(3) still has non-zero components, and from (3.30) we have(4.19)U(3)=U2(3)+U3(3)=-(1-PDi)∑j=12ψ2(ϕ3,ϕj)+0=-Pθ22(1-PDi)[cos(2(ϕ3-ϕ1))+cos(2(ϕ3-ϕ2))],
where we recall that U2(3) represents the contribution of the ψ2 ancillary function to the third pass utility function U(3). In general, the ψ2 contribution for the nth pass utility function using this sinusoidal model takes the form (see (3.30))(4.20)U2(n)=-(1-PDi)n-2∑j=1n-1Pθ22cos(2(ϕn-ϕj))=-Pθ22(1-PDi)n-2(cos2ϕn∑j=1n-1cos2ϕj+sin2ϕn∑j=1n-1sin2ϕj).
Similarly, for this sinusoidal model, the fourth ancillary function ψ4 is generally non-zero, becoming(4.21)ψ4(ϕ1,ϕ2,ϕ3,ϕ4)=∫02π12πPθ4∏j=14cos(2(θ-ϕj))dθ=Pθ48[cos(2(ϕ4-ϕ3))cos(2(ϕ2-ϕ1))+cos(2(ϕ4-ϕ1))cos(2(ϕ3-ϕ2))+cos(2(ϕ4-ϕ2))cos(2(ϕ1-ϕ3))].
The corresponding U4(n) utility component aggregating the contribution of the ψ4 ancillary function on the nth pass utility where n≥4 takes the form(4.22)U4(n)=(1-PDi)n-4(Pθ48)∑j1=1n-1[cos(2(ϕn-ϕj1))∑j3=2j3≠j1n-1∑j2=1j2≠j1j3-1cos(2(ϕj3-ϕj2))].
As before, the odd ancillary function ψ5 integrates to zero. The analytic calculation of utility function components can continue until a specified degree of accuracy has been reached, as given in Theorem 3.5. For the purpose of this specific example, we terminate our discussion at ψ5.Naturally, an issue that is paramount in any extended likelihood structure is the amount of processing and storage necessary to calculate utility function components. Ideally, we wish to minimize both storage and computational loading. Table1 provides useful recursions for calculating the U2(n) and U4(n) components. Indicated in the table is the pass number in which the terms become non-zero or non-empty in the case of vector quantities. For the U2(n) component, observe from (4.17) that temporary variables defined in Table 1 reduce storage requirements to a two-parameter grid cell attribute. This same information must be stored in vector format, however, to apply it properly for the U4(n) component. The U4(n) recursion increases storage requirements in that three vectors of size n and one scalar attribute must now be saved for each grid cell location along with the stored quantities for the U2(n) calculation. Observe how the recursions in Table 1 separate the contribution of the nth pass control parameter from the preceding parameter values. This methodology generalizes for higher order recursions.Table 1
Recursion equations for computing component utilities for a sinusoidal orientation dependency.
Recursion for calculatingU2Initializationu2c(0)=u2s(0)=0Utility Calcw2=cos2ϕnu2c(n-1)+sin2ϕnu2s(n-1)n>1U2(n)=-(1-PDi)n-2(Pθ2/2)w2n>1Updateu2c(n)=u2c(n-1)+cos2ϕnn>0u2s(n)=u2s(n-1)+sin2ϕnn>0Recursion for calculatingU4InitializationVs(0)=Vc(0)=V4(0)=[]u4(0)=u4(1)=0Utility CalcVϕn=Vc(n-1)cos2ϕn+Vs(n-1)sin2ϕnn>1w4=[u4(n-1)-V4(n-1)]·VϕnT(n)n>3U4(n)=-(1-PDi)n-4(Pθ4/8)w4n>3UpdateVs(n)=[Vs(n-1)sin2ϕn]n>0Vc(n)=[Vc(n-1)cos2ϕn]n>0V4(n)=[(V4(n-1)+Vϕn)w2]n>1u4(n)=u4(n-1)+w2n>1We illustrate the impact of orientation and its utility calculation on search performance via the construction of search plans representing limiting cases on utility. Figure1 in its continuing pattern depicts a vertical search plan in which the detection likelihood remains relatively fixed over the plan. Here, the first searcher starts at the lower left corner of the space and commences a vertical ladder search. The second searcher starts at the upper right corner and similarly performs a vertical ladder search. Figure 4 depicts the second limiting case search plan. The first part of the search remains unchanged from the vertical ladder search. However, when the two searchers reach proximity to each other, they jointly turn at right angles to alter their orientation, that is, ϕ2=ϕ1±π/2 as above, while maintaining coverage of the space. Hence, this plan seeks to achieve a positive utility through orientation diversity. This plan also demonstrates the capacity of the search evaluation modeling technique to account for arbitrary searcher motion in collaborative, multipass search plans.Figure 4
Experimental geometry for two searchers performing an orientation switch search plan. Only the initial history of the search path is shown for clarity.The utilities achieved in the two search plans are illustrated in Figures5 and 6, respectively. Note that what is depicted is the average utility over the cells in the sequential update. For the vertical search plan, noninteraction between searchers results in a zero utility prior to search path overlap. When multipass coverage does occur, the resulting utility is negative, following Theorem 3.4, as the searchers have the same orientation (Incidental “spikes” into positive utility occur as the searchers maneuver between search legs). Orientation switching in the second plan yields the desired generally positive utility for both searchers as multipass coverage is achieved over the cells.Figure 5
Average utility for each of two searchers performing a vertical search plan with orientation dependency (the two curves are nearly identical).Figure 6
Average utility for each of two searchers performing a switched orientation search plan with orientation dependency (searcher 1 utility is in blue and searcher 2 utility is in red).These geometries represent two-pass search strategies developed over a benign search environment under which uniformity in placement preference and detection likelihood is assumed. More generally, spatial variability in these quantities may induce a variability in the number of search passes conducted over the space. To illustrate the capacity of the algorithm to accommodate higher order search pass sequences, we include a deviated coverage plan in which a local assessment of the direction of highest coverage induces the searchers to deviate from the standard ladder search. While the searchers attempt to fulfill a coverage strategy, the resulting search paths take on a random appearance. Further, in the process of deviating towards cells of highPηi, a natural variability in the number of cell search passes occurs over the cell grid construct. A partial realization of the search geometry is depicted  in Figure 7 with a histogram of the achieved search pass number provided in Figure 8. The average utility that results for the entire search path set is shown in Figure 9.Figure 7
Experimental geometry for two searchers performing a deviated coverage search plan. Only the initial history of the search path is shown for clarity.Figure 8
Search pass histogram for the deviated coverage search plan.Figure 9
Average utility for each of two searchers performing a deviated coverage search plan with orientation dependency (searcher 1 utility is in blue and searcher 2 utility is in red).The impact of these paths on the selected search criteria is shown in Figure10. For these evaluations, only one object type is considered. The uniform placement prior has an expected number of objects of E{N0}=5 over the space. The probability that k>n objects will be detected along the search paths is calculated as a function of search time for n={0,2,4} for each of the search plans. The limiting utility realizations yield corresponding search performance curves with the orientation switching plan clearly outperforming both the vertical ladder search and the deviated coverage plan. It is predictable that the deviated coverage search strategy yields a lower performance than the ladder searches during the initial (single pass) phase of the plan [5]. However, during the latter (multipass) phase of the plan, the deviated coverage strategy surpasses the vertical search strategy (but not the orientation switching plan) due to the negative utility incurred by the vertical ladder search (as in Figure 5).Figure 10
Search performance with orientation dependency for cumulative probability of achievingk>n detections (n={0,2,4}). Red curves represent the vertical search plan, blue curves represent a orientation switch search plan and grey curves indicate the deviated coverage search plan.We finish by presenting the results of a Monte Carlo experiment for the deviated coverage search plan. An ensemble of 1000 runs of a simulated placement scenario is executed and the frequency of occurrence results are calculated. For the experiment, objects are placed uniformly with a random object orientation assigned independently for each object. The detection event is simulated in a sequential realization of the search trajectories by a random draw governed according to (4.14). The results are illustrated in Figure 11. In the figure, the mean frequency of occurrence is plotted against the predicted successful search probability for the k>n detection events. Standard deviation bounds at the 3σ level are also depicted in the figure to indicate the estimation uncertainty in the experiment. The usefulness of Table 1 is validated under these operating conditions as the prediction is contained within the uncertainty interval.Figure 11
Monte Carlo performance results with orientation dependency for cumulative probability of achievingk>n detections (n={0,2,4}).


## 5. Conclusion

A mathematical model of search that allows for the incorporation of multiple pass dependencies has been developed. The model is based on recursively updating a geometric likelihood structure that directly impacts search performance. This model provides a general framework for modeling arbitrary ancillary search dependencies. The example problems studied include the standard overlapping scans, a multiple searcher with multiple objects problem where each searcher is tuned to a specific object type, and two search geometries with searcher performance that varies over relative aspect to the object. The latter examples show that the method provides an approach to examine the impacts of complex dependencies at a planning stage, without resorting to extensive simulation studies. Future efforts will examine the utilization of this evaluation model in the development of optimal multisearcher coordination strategies.



---

*Source: 472809-2010-02-28.xml*