许多计算运动目标最优搜索计划的算法依赖于能够计算静止目标的最优搜索计划。

  本章概述了最佳搜索静止目标的标准模型和结果。讨论了搜索传感器和检测建模的一些基本概念，包括横向距离曲线、扫描宽度和检测函数。定义了离散空间和连续空间中的搜索空间和目标位置的先验分布。提出了寻找在固定时间内发现目标概率最大化的搜索方案的方法，并探讨了最小化平均寻找目标时间等相关的最优搜索问题。提出了在大多数情况下可用于计算最优计划的算法。

# 一、先验分布

  我们假设目标的位置有一个先验分布。这种分布捕捉到了我们对目标位置的了解和不确定性。通常这种分布既包括主观信息，也包括客观信息，其不确定性用概率分布表示。

  我们通常认为目标的位置在二维或三维空间的某个区域，或者在一组单元格中。首先，让我们考虑目标位于一组单元格中的情况。单元格通常指的是物理位置，但这不是必需的。

# 1.1 离散先验分布

  离散先验是 J 个单元格集合上的概率分布。为简单起见，我们假设单元格的数量是有限的，并且单元格的编号为 j=1,...,J : 单元格可以表示离散的位置或网格中的单元格；它们可以表示目标在有限位置集合中的任何一种情况。我们一般用单元格这个词来表示这些可能性。离散先验指定了下目标在单元格 j 中的概率 p(j),1,...,j ; 我们假设

$$\sum_{j=1}^Jp(j)=1$$

  即使目标搜索空间是连续的，通常也可以方便地在空间上施加一个单元格网格，并使用单元格来近似潜在的目标位置分布。图 2.1 为

# 1.2 连续先验分布

  连续空间 (如二维或三维空间) 上的先验分布用概率密度函数表示。当搜索空间 S 为平面时，两个标准先验是均匀分布和高斯分布。

# 1.2.1 均匀先验

  面积为 a 的平面上区域 R 上的均匀先验分布可以表示为：

$$p_u(x)=\left\{\begin{array}{ll}1/A \quad\mathrm{for} \space x\in\mathcal{R}\\0\quad\quad\mathrm{otherwise}.\end{array}\right.$$

# 1.2.2 高斯分布

  很多时候，搜索开始于对目标最后已知位置的不确定估计，这是基于传感器报告，如雷达测量或视觉目击。经验和测试表明，许多传感器的测量误差具有高斯分布或正态分布。因此，最后已知位置的不确定性通常由二元正态概率分布来建模。

  为方便起见，我们使用 (x1, x2) 坐标系，其均值为 (0,0) ，并且有方向，这样目标的 x1 坐标的分布与 x2 坐标无关。设$\sigma_1$ 和$\sigma_2$ 为这两个坐标上分布的标准差。目标位置的先验密度函数为：

$$p_{G}\left(x_{1},x_{2}\right)=\frac{1}{2\pi\sigma_{1}\sigma_{2}}\exp\left[-\frac{1}{2}\left(\frac{x_{1}^{2}}{\sigma_{1}^{2}}+\frac{x_{2}^{2}}{\sigma_{2}^{2}}\right)\right] \text{for} (x_{1},x_{2})\in S.$$

  图 2.2 显示了特殊情况下的概率密度函数图，其中 d1。这被称为圆形正态密度函数。

# 二、探测模型

为了优化搜索努力的分配，我们必须有一个关于探测概率与努力程度关系的模型。通常情况下，需要考虑误报的可能性，但在此讨论中，我们假设传感器不会产生误报，也就是说，只报告真实的探测结果。

我们首先考虑在面积为$A$ 的矩形区域内进行搜索，假设我们正在用一个探测距离为$R$ 的传感器进行搜索，并且该传感器在该范围内具有完美的探测能力。如果传感器在目标的距离$R$ 内通过，则检测到目标的概率为$1$。这就是所谓的确定探测范围定律。在这种情况下，$W=2R$ 是传感器的扫描宽度。它是传感器在搜索区域移动时 “干净” 地扫过的宽度。如果传感器在矩形中长度为$l$ 的路径上进行搜索，则搜索努力 (扫描面积) 为$lW$，搜索努力密度 (或覆盖率) 为$lW/ a$。

# 2.1 检测函数

假设传感器执行如图 2.3 所示的平行轨迹搜索，路径间距正好为 W。然后，当目标位于矩形区域时，检测到目标的概率作为搜索努力密度的函数用图中的直线表示。2.4. 一旦努力密度达到 1，探测概率就不可能再增加了。

图 2.3: 扩散模型的结构图，引用自《扩散过程与模拟》。

假设传感器执行如图 2.3 所示的平行轨迹搜索，路径间距正好为 W。则当目标位于矩形区域时，检测到目标的概率作为搜索努力密度的函数用图 2.4 中的直线表示。一旦努力密度达到 1，探测概率就不可能再增加了。

图 2.4：检测函数

通常不可能将搜索轨道精确地间隔一个扫描宽度，因此会出现意外的间隙和重叠。这将降低检测概率。在极限情况下，由于我们将努力放置在所需位置的能力降低，我们会遇到这样一种情况，即搜索努力的每个增量都按照矩形上的均匀分布放置，并且与之前的增量放置的位置无关。然而，我们仍然假设所有的努力都落在矩形内。这种极限情况产生指数检测函数，如图 2.4 所示，推导如下。这个函数也被称为随机搜索函数或公式。通常，并行航迹搜索的有效性介于确定范围和指数检测函数之间。这将是第 2.2.2 节中导出的逆立方检测函数的情况

指数检测函数的推导首先由 Koopman (1946, 1956b) 给出。产生指数检测函数的数学假设如下。

• 每个小增量的搜索努力的位置在矩形上遵循均匀分布，而不相交的增量是独立分布的。

• 没有任何努力落在矩形之外。

设$b(l)$ 为航迹长度为$l$ 的搜索结果的检测概率，设$h$ 为搜索努力 (航迹长度) 的一个小增量。然后

$$(1-b(l))\frac{hW}{A}$$

是努力$l$ 未能探测到目标，但在下一个增量$h$ 成功的概率。因此

$$b\left(l+h\right)=b(l)+\left(1-b(l)\right)\frac{hW}{A}\mathrm{~}\\b'(l)=\lim_{h\to0}\frac{b(l+h)-b(l)}h=\left(1-b(l)\right)\frac WA$$

由于$b(0)=0$，上述微分方程有众所周知的解

$$b(l)=1-\exp{(-lW/A)}\quad\mathrm{for~}l\geq0.$$

对于搜索密度$z=lW/A$，上式变为

$$b(z)=1-e^{-z}\mathrm{~for~}z\geq0$$

即图 2.4 中的指数检测函数。

虽然证明指数检测函数的假设有些人为，但它提供了一个有用的搜索有效性的下界，在这个下界中，我们在一个矩形上均匀地应用搜索努力。如图 2.5 所示，其中我们绘制了矩形的分数，该矩形由具有确定的探测范围律和扫描宽度$W=2R$ 的传感器进行平行路径搜索所覆盖。有 100 条路径，路径的预期间距等于$W$，但我们假设每条路径的位置有一个独立的高斯误差，平均值为 0，标准差为$\sigma$。我们执行蒙特卡罗试验来计算被一条或多条路径覆盖的矩形的分数。黑线表示所覆盖矩形的期望分数，而浅色线表示结果与平均值的标准差。可以看到，当$\sigma /W$ 达到 5 时，所覆盖的矩形的预期分数接近上式所预测的$1-e^{-1}=0.63$。

图 2.5 平行路径搜索效率与相对导航误差$\sigma /W$ 的关系

# 2.2 横向范围函数

为了定义横向范围函数，我们想象一个传感器在经过一个目标时沿着一条长长的直线路径，如图 2.6 所示。轨迹最接近目标点的距离$r$ 是横向距离。横向范围是有符号的，如果目标在传感器的右边，横向范围是正的。设$L_d(r)$ 为传感器在横向距离$r$ 处通过时检测到目标的概率。利用横向距离曲线，我们将式 (2.3) 中给出的扫描宽度定义扩展为

$$W=\int_{-\infty}^{\infty}l_d(r)dr.$$

具有确定量程规律的传感器具有以下横向量程函数：

$$l_d(r)=\begin{cases} 1\text{ for}-R\leq r\leq R\\ 0\text{ otherwise}\end{cases}$$

和扫描宽度$W=2R$。

可以证明指数检测函数的证明适用于具有更一般的扫描宽度定义的传感器。

# 逆立方横向距离函数

逆立方横向距离函数是由 Koopman (1946) 及其同事开发的，用于模拟船舶尾迹的视觉检测。它被美国海岸警卫队 IAMSAR (2008) 用作视觉搜索的标准检测模型之一。Koopman (1946, 1956b) 在以下假设下推导出这个横向范围函数：参见 Washburn (2014)。

• 观测者的高度$h$ 高于海面上的目标。
• 观察者通过观察目标的尾迹来探测目标。
• 探测到的瞬时概率$\gamma$ 与来自观测者的尾迹所指向的立体角$\alpha\beta$ 成正比，如图 2.7 所示。

图 2.7 由宽度为$a$，长度为$b$ 的尾流所支撑的立体角

该尾流由长为 $a$ 和 $b$ 的矩形表示，其所张成的立体角是角度 $\alpha$ 和 $\beta$ 的乘积，角度以弧度测量。观察图 2.7 的左侧，可以看出 $\alpha = c/s$，根据相似三角形关系，有 $c/a = h/s$，因此 $\alpha = ah/s^2$。由于 $\beta = b/s$，因此立体角为

$$\alpha\beta=\frac{abh}{s^3}=\frac{Ah}{s^3}=\frac{Ah}{\left(h^2+r^2\right)^{3/2}}$$

其中$A=ab$ 是矩形的面积。因为$\gamma$ 与立体角成正比，我们有一个常数$k$

$$\gamma=\frac{kAh}{\left(h^2+r^2\right)^{3/2}}$$

当$r$ 比$h$ 大很多的时候

$$\gamma\approx\frac{kAh}{r^3}$$

常数$k$ 由海况、能见度和目标类型等因素决定。

设$\gamma(t)$ 为时刻$t$ 的瞬时检测率，则$\gamma(t)dt$ 为时刻$dt$ 小增量内的检测概率。我们进一步假设检测在不相交的时间间隔上是独立的。设$p(t_1, t_2)$ 为时间$[t_1, t_2]$ 的检测概率，$q(t_1,t_2)=1-p(t_1, t_2)$。然后

$$q\left(t_1,t+dt\right)=q\left(t_1,t\right)(1-\gamma(t)dt)$$

所以

$$\frac{dq\left(t_1,t\right)}{dt}=-\gamma(t)q\left(t_1,t\right)$$

解这个微分方程，我们得到

$$q\left(t_1,t\right)=\exp\left(-\int\limits_{t_1}^t\gamma(t)dt\right)$$

$$p\left(t_1,t\right)=1-\exp\left(-\int\limits_{t_1}^t\gamma(t)dt\right)$$

假设观察者以横向距离 $r_0$ 距离通过目标。为了简化，我们选择一个 $(x, y)$ 坐标系，使得观察者的路径沿着 $y$ 轴以速度 $v$ 从 $y = -\infty$ 到 $y = \infty$ 移动，目标位于 $(r_0, 0)$。令观察者在时间 $t$ 时的位置为 $(0, vt)$。从而有

$$\int_{\begin{array}{c}-\infty\\\end{array}}^\infty\gamma(t)dt=\int_{\begin{array}{c}-\infty\\\end{array}}^\infty\frac{kAh}{\left(r_0^2+(vt)^2\right)^{3/2}}dt=\frac{2kAh}{vr_0^2}$$

所以在横向距离为$r_0$ 的轨道上至少探测到一次目标的概率是

$$l_d\left(r_0\right)=1-\exp\left(\frac{-2kAh}{vr_0^2}\right)$$

这是 “逆立方” 横向范围函数。逆立方的名称是指检测率，它与目标到传感器距离的逆立方成正比。

# 逆立方体扫描宽度

根据以上内容，我们可以计算出逆立方横向范围函数的扫描宽度$W$

$$W=\int_{-\infty}^{\infty}l_d\left(r_0\right)dr_0=\int_{-\infty}^{\infty}\left(1-\exp\left(\frac{-2kAh}{vr_0^2}\right)\right)dr_0=2\sqrt{2\pi kAh/v}$$

# 逆立方检测函数

让我们回到图 2.3 中所示的矩形搜索区域，并考虑一大批长且平行的搜索轨迹，它们之间相距距离为$D$。我们再次选择坐标系，使得这些轨迹与$y$ 轴平行。检测目标在单条轨迹上的概率仅取决于目标位置的$x$ 坐标和该轨迹的$x$ 坐标。设第$i$ 条轨迹的$x$ 坐标为$iD$，则目标在$x$ 处时，轨迹的横向范围为$r_0 = |x - iD|$。假设在一条轨迹上的检测与其他轨迹上的检测是相互独立的。我们得出目标在$x$ 处时，在第$i$ 条轨迹上未被检测到的概率为

$$\exp\left(\frac{-2kAh}{vr_0^2}\right)=\exp\left(\frac{-W^2}{4\pi\left(x-iD\right)^2}\right)$$

所有轨道都探测不到的概率是

$$\exp\left(-\sum_{i=-\infty}^\infty\frac{W^2}{4\pi\left(x-iD\right)^2}\right)=\exp\left(-\frac\pi4\left(\frac WD\right)^2\csc\left(\frac{\pi x}D\right)\right)$$

其中无限和的值由 Koopman (1956b) 中描述的方法求出。如果目标位置在矩形上的分布是均匀的，则检测到目标的概率为

$$b\left(W/D\right)=1-\frac{1}{D}{\int}_{0}^{D}\exp\left(-\frac{\pi}{4}{\left(\frac{W}{D}\right)}^{2}\csc\left(\frac{\pi x}{D}\right)\right)dD=2\Phi\left(\sqrt{\frac{\pi}{2}}\frac{W}{D}\right)-1$$

其中，$\Phi$ 是均值为 0、方差为 1 的高斯分布的累积分布函数；参见 Koopman (1956b)。以 $ z = W/D $ 作为搜索密度，我们得到图 2.4 中的逆立方检测函数，该函数位于确定范围检测函数和指数检测函数之间。

当海岸警卫队使用这种探测功能时，搜索计划者参考一组表格 (参见海岸警卫队 (2010，附录 H))，这些表格给出了可视搜索的扫描宽度，作为搜索对象类型、能见度、海况、高度和搜索飞机速度的函数。扫描宽度的选择隐式地决定了逆立方体扫描宽度中 k 的值。

# 三、静止目标的最优搜索

最优搜索静止目标的基本问题有以下几个要素。

• 离散或连续搜索空间上的先验分布
• 一种将搜索努力 (密度) 与发现概率联系起来的检测函数
• 指定搜索工作分配 (搜索计划) 的函数。
• 目标是在成本约束下找到最大概率发现目标的分配。

# 3.1 离散搜索空间：持续努力

在本节中，我们导出了离散状态空间和连续努力下最优平稳目标搜索问题的解。我们首先用数学的方式定义这个问题的要素。

（1）先验分布

先验分布由$p(j)$ 给出，表示目标在单元格$j$ 的概率，$j=1,\dots J$，满足

$$\sum_{j=1}^Jp(j)=1$$

为方便起见，我们假设$p(j)\ge 0, j=1,\dots J$。

（2）检测函数

对于每个单元格$j$，有一个检测函数

$$b\left(j,z\right)=\Pr\left\{\text{detecting target with effort }z|\text{target in cell }j\right\}\mathrm{~for~}z\geq0$$

设$b'(j, z)$ 是$b(j, z)$ 对$z$ 的导数，我们假设$b'(j, z)$ 是$z$ 的一个正的、连续的、严格递减的函数，$b'(j, z)<\infty$，我们称其为递减率检测函数。

（3）成本函数

在单元格$j$ 中应用$z$ 努力的代价是$c(j)z$，其中$c(j)>0,j=1,\dots J$，通常，$c(j)=1$，在这种情况下，成本限制是在努力上。

（4）收益率函数

对于$j=1,\dots J$，定义收益率函数为

$$\rho\left(j,z\right)=b^{\prime}\left(j,z\right)p(j)/c(j)\text{ for }z\geq0$$

由于$b'(j, z)$ 是$z$ 的一个正的、连续的、严格递减的函数，收益率函数也具有这些性质。递减的收益率函数意味着应用于单元$j$ 的每一个新的搜索努力增量产生的检测概率增加与成本增加的比例较小。在经济学中，这被称为递减收益率。收益率递减性质是大多数检测函数所共有的，例如指数检测函数。

（5）分配函数

搜索计划是一个分配函数$f(j),j=1,\dots J$，其中$f(j)$ 是分配给单元格$j$ 的搜索量。我们要求所有的$j$ 满足$f(j)>0$。设$F$ 是分配函数的集合。

对于一个分配方案$f$，我们计算检测到的概率

$$P(f)=\sum_{j=1}^Jb\left(j,f(j)\right)p(j)$$

成本是

$$C(f)=\sum_{j=1}^Jc(j)f(j)$$

（6）最优分配

设$K>0$ 为成本约束。那么如果下式满足，那么$f^*\in F$ 对于代价$K$ 来说是最优的

$$C\left(f^*\right)\leq K\mathrm{~and~}P\left(f^*\right)\geq P(f)\text{ for all }f\in F\text{ for which C}(f)\leq K$$

# 3.1.1 离散空间拉格朗日优化

收益率的概念对于寻找最优搜索计划是至关重要的。在本节中，我们将展示如何通过分配工作量来找到降低率检测函数的最佳计划，以便下一个工作量小增量的收益率等于所有接受搜索工作的单元的公共值，并且等于或低于没有接受搜索工作的单元的公共值。我们用$\lambda$ 来表示这个收益率。

固定收益率$\lambda>0$。如果可能的话，对于每个单元格$j$，找到$f_{\lambda}(j)\ge0$ 使得$\rho(j,f_{\lambda}(j))=\lambda$。如果不可能，则$\rho(j,0)<\lambda$，设$f_{\lambda}(j)=0$。综上所述，$f_{\lambda}$ 满足以下条件:

$$\begin{aligned} \rho\left(j,f_{\lambda}(j)\right)& =b'\left(j,f_\lambda(j)\right)p(j)/c(j)=\lambda\text{ if }f_\lambda(j)>0 \\ &\leq\lambda\mathrm{~if~}f_\lambda(j)=0. \end{aligned}$$

由于$b$ 的递减率特性，我们可以证明$f_{\lambda}$ 是成本$C(f_{\lambda})$ 的最优搜索分配方案。我们将在下面进行证明。通过选择不同的$\lambda$ 值，我们可以为不同的成本生成最优方案。如果我们想找到成本为$K$ 的最优方案，则需要找到使得$C(f_{\lambda}) = K$ 的$\lambda$ 参数。如果$b$ 是一个递减率检测函数，那么$C(f_{\lambda})$ 将是一个关于$\lambda$ 递减函数，这意味着可以通过数值一维搜索轻松找到所需的参数值$\lambda$。

在接下来的讨论中，我们开发了一种算法，用于寻找任何期望成本的最优搜索计划，并提供了一个可以显式求解最优分配函数的示例。我们首先证明$f_{\lambda}$ 对于成本$C(f_{\lambda})$ 是最优的。最优性的证明依赖于拉格朗日乘数论证，其中回报率被用作拉格朗日乘数。

将离散空间逐点拉格朗日量 $l$ 定义为

$$l\left(j,z,\lambda\right)=b\left(j,z\right)p(j)-\lambda c(j)z\text{ for }j=1,\ldots,J,z\geq0,\text{ and }\lambda>0$$

然后

$$l^{\prime}\left(j,z,\lambda\right)=b^{\prime}\left(j,z\right)p(j)-\lambda c(j)$$

是$l(j, z,\lambda)$ 关于$z$ 的导数。