离散和连续空间中的最优搜索理论

Initial probability density function:

(1)     Uniform density

1/V_n

(2)     Gaussian density

mu, sigma

(3)     Truncated Gaussian density

Normalization constant c=1/int_A(p₀(s)ds)

目标运动模型:

采用Transition density function 表示: dX/dt=V(X,t) (V表示目标的速度向量)

在正态分布等假设下,X(t)满足:

                (*)           dX=beta(X,t)dt+a(X,t)^1/2dW

其中dW是一个维纳过程(Wiener process),有时也叫做布朗运动(Brownian motion),定义为: dW是具有正态分布且满足E(dW)=0和E[(dW)²]=dt,并且在不相交的时间区间上有相互独立的增量的随机过程.

方程(*)只是随机运动目标的近似模型,特别是当deta t很小时不成立.因为当deta t - ->0时,增量独立的假设不正确.为了弥补这个缺点,可以引入下面的加速度模型,或采用一个更一般的随机过程.但是对于大部分的应用来说,由(*)式所定义的运动模型只需经过少许修正就可使用.

两个特例:

1.       逃避运动目标 (evading target)

假定目标在向量场Z_p(t)X(t)的方向以最大的速度逃离

2.       随机漫游 (random tours)

第二类的运动目标模型是基于目标的运动加速模型.

探测函数模型:

1.       Visual detection model (视觉探测模型), 一个通用的视觉探测函数模型构造为:假定目标位置在平面上的X点,而搜索者的位置在空间Z点处,探测函数b与目标所在平面和搜索者与目标位置所在直线的立体角(solid angle)成比例

2.       Radar detection model (雷达探测模型), 应用探测统计学理论

3.       Cookie cutter model (圆盘探测模型), 对称之为对时间依赖的圆盘模型 (TDCC, time-dependent cookie cutter)----当搜索者和目标之间的距离小于R时,探测概率为1,而在其他情况下探测概率等于0

扫描宽度(sweep width):它表示的是一个距离的大小,在这个距离以外搜索者探测到目标的概率与在这个距离以内搜索者探测不到目标的概率恰好相等

最简单情况:假设搜索者站在原点不动,而目标以速度v沿着平行于y轴的直线移动.设探测函数为b(x₁,x₂,t,z),则在时间t₁和t₂之间,搜索者探测的目标的概率为…

公式略

这个积分值F[x₁]称为视能(sighting potential)

现在假设目标的运动路线是源于x点且平行于y轴的射线,到t时刻搜索者探测不到目标的概率u(x,t),表示搜索时间开始于t…

令p(x)=1-u(x,infinity), 这样p(x)就是最终在x点一侧的半直线上探测到目标的概率.因此得:

p(x)=1-e^-F[x]

通常称为侧向值域曲线(lateral range curve).现在给出扫描宽度W的定义如下:

W=int_-infity^+infinityp(x)dx

因为p(x)关于原点对称,很容易看出这样定义的扫描宽度W满足:

int₀^W/2[1-p(x)]dx=int_W/2^infinityp(x)dx

上面的等式说明前面对扫描宽度W的理解是正确的

对视觉探测的情况…

搜索者运动模型和搜索资源模型

简单情况下搜索者是静止的,dZ/dt=0. 更普遍情况下,搜索者的运动分基于速度的运动模型和基于加速度的运动模型.

定义:搜索资源分配函数

本书新颖之处:

1.       以前的论著中均假设搜索目标的位置的初始概率分布函数是已知的,本书研究了在离散空间中当目标的初始分布函数未知的情况下的最优搜索问题

2.       分析讨论了非正则探测函数的最优搜索问题

3.       研究了把随机运动的移动目标最优搜索问题转化为随机系统的最优控制问题进行研究的方法,并利用最优化原是推导出随机移动目标搜索问题的Hamilton-Jacobi-Bellman (HJB)方程,将随机系统的最优搜索问题转为拟线性确定性系统的求解.这种方法对于解决十分困难的移动目标最优搜索问题指出了一条新途径.

对于静止目标的最优搜索问题即搜索资源的最优分配问题开展研究的先驱是B.O. Koopman.在探测函数具有指数函数形式的假定下研究了如何最大化发现目标的概率,并提出了在连续目标空间中且搜索资源连续可分的情况下进行查找的资源分配方法.Koopman证明了资源E1+E2的最优分配是资源E1的最优分配与资源E2的条件最优分配之和(在E1的分配完成后没能找到目标的条件对资源E2的最优分配).因此他得出结论:如果资源E1的分配策略已定,则搜索者在分配资源E2时并不能从资源E1的使用没能找到目标这个附加信息中获得任何好处.

Gluss推广了Koopman的模型,使之包含了惩罚性开销在内.

连续空间中的Koopman模型

假定搜索目标是隐藏在一个一维空间中的点:

g(x)>=0;

g(x)dx=Prob[x<=X<=x+dx]

int_-infinity^infinityg(x)dx=1 - ->此条件隐含着目标必定隐藏在这个给定的一维空间内的假定.当然我们也可以假定目标隐藏在此空间中的概率为alpha(alpha<=1).这样一来就包含了我们不知道是否搜索目标真的在我们所查找的空间内的情况,这种情况在实际实用(如石油勘探)中是可能出现的.

在区间x和x+dx中所投入的搜索资源可以用phi(x)dx表示.这里的phi(x)是一个尚待确定的非负并且连续的函数,称之为资源分配函数.如果我们所掌握的可供配置的总资源是有限的,设其等于K,于是我们得到:

int_-infinity^infinityphi(x)dx=K

在搜索目标确实位于点x的条件下,使用了搜索资源phi(x)以后成功地发现目标的概率记为b[phi(x)],这个概率叫做探测概率或探测函数,其特点如下:

b(0)=0, b’(phi)>=0, lim_{phi->infinity}b(phi)=1

De Guenin进一步假设这个探测函数b(phi)是个正则函数,即: b’(.)是个单调递减函数,并且有b’(0)>0以及b’(infinity)=0.所以搜索者在x和x+dx之间成功发现目标的概率等于:

g(x)b[phi(x)]dx,

于是在整个空间中的搜索过程的成功发现目标的总概率为:

P(phi)= int_-infinity^infinity g(x)b[phi(x)]dx.

所以在这种情况下,最优搜索问题等价于确定函数phi(x)使得P(phi)达到最大化,并且满足下面的约束条件:

phi(x)>=0;             int_-infinity^infinityphi(x)dx=K.

De Guenin的主要结果阐述在下面的定理中:

定理2.1                phi(x)使用P(phi)达到最大值的必要条件是在任一满足条件phi(x)>0的点x,有

g(x)b’_phi[phi(x)]=C

这里C是任一常数.

Algorithm De Guenin略…

最小期望成本模型

不同的优化准则:

1.       成功发现目标的概率最大化,而且总的搜索成本开销不超过事先的预算值K

2.       用于查找和发现目标的时间期望值达到最小化- ->Staroverov

N个笼子:

<1> 目标不在笼j中,则找到目标的概率为0

<2> 目标在笼j中,则找到目标的概率为p

假定搜查不同笼子时得到的搜索结果是相互独立的.

我们可以将搜索所有笼子的过程表示为如下的一个序列:

a=(a₁,a₂,…,a_j,…)

对应于每一个搜索过程a我们引入一个随机变量tao_a,它的含义是在本次搜索中发现目标的时刻, Staroverov通过研究相关的正单调递减序列得到的一些代数结果,给出了:

E[tao_a*]=inf_a E[tao_a];

其中E表示数学期望算子.因此a*是满足第二种优化优化准则的过程.

满足第二种优化准则的最优化搜索资源分配策略是由Gilbert首先提出并研究的:两个盒子,时间损失- ->Gluss,N个盒子搜索问题,特例:这些盒子是排成一列的 - ->时间损失为常数的N个盒子- ->具有转换损失的离散搜索模型,并得到了使用检测时间期望值最小化的最优搜索所满足的条件.

行踪搜索:

Detection search探测搜索:在资源预算的限制下选择一种搜索策略使得找到目标的可能性大致最大,在这种情况下整个搜索成本是由事先确定的数值K所限定的.

Whereabouts search行踪搜索:在使搜索成本不超过K个单位(预算的上限)的条件下判断出目标最有可能藏在哪个盒子里.

行踪搜索的结果可能有两种:一是搜索中成功地找到了目标；二是在搜索到最后也没有找到目标的情况下给出哪个盒子最可能藏有目标的判断.所以行踪搜索的策略不但包括了前面的最优搜索策略,还包括在搜索不成功时的最优猜想策略.

第三章:分布函数未知情况下的搜索问题:

设计搜索策略时首先考虑的是选择目标分布函数q(k),

探测函数具有指数函数形式(例如b(t)=1-e^-t).

定理3.1(最优搜索策略的探测概率的上下界) 一个物体藏在N个盒子中的一个盒子里面,并且具有任意的概率分布函数:p(i) (i=1,2,…,N).b(t)=1-e^-t,则最优搜索策略f*发现目标的概率P[f*]满足不等式:

1-e^-k/N<=P[f*]<=1-C_Ne^-k/N=1-lambda

其中:C_N=N[p(1)…p(N)]^1/N,且K>0是总成本开销约束条件.

推广到探测函数b(i,z)是正则函数时的情况

b(i,0)+lambda*K<=P[f*]<=b(i,0)+b’(i,0)K.

目标概率分布的估计和误差分析

简化：两个盒子，探测函数具有指数形式的情况；

目标真实概率分布(a,1-a),搜索者假设其为(b,1-b)；

定理:P[f_b*]<=P[f_a*]

推论: (选取目标位置概率分布的第一个准则) 使得下面的式子取最大值:

P[f_b*]=1-(a+b-2ab)/sqrt(b-b²) e^-K/2

这里a定义在一个优先集(priority set)上,即所有的a有较大可能取值的那些点的集合. 即:P[a=a₀ in A]>=p₀. 其中p₀是一个固定的常数,通常在0.5到1之间.

(探测概率误差) 搜索空间为两个盒子:探测概率误差由下式给出:

E(a,b)= (a+b-2sqrt(ab)[sqrt(ab)+sqrt((1-a)(1-b))]) / () e^-K/2.

选择目标概率分布的第二个准则:满足在a的一个优先集上使E(a,b)取值为最小.

下面我们将证明:如果优先集是一个长度为delta>0的区间,那么当区间长度趋于0时,误差E(a,b)也趋于0.

E(a,a₀)<c₀ (delta)².其中c₀为某个常数.

假设我们知道探测概率的均值是E[P(f*)],那么由此可以计算出相应的目标分布函数的平均值吗?换句话说,如果目标分布函数是E(a),那么对应的最优搜索方案的探测概率等于E[P(f*)]吗?答案通常中否定的.

推广到N个盒子的情况:

定理:探测函数为指数函数形式,则P[f_b*]<=P[f_a*]

P[f_b*]=1-e^-K/N sum_i=1^N [(prod_j=1^N bj)^1/N a_i/b_i]

第一准则:使上面的表达式P[f_b*]在一个优先集上达到最大值.

第二准则:使下面的表达式E(a,b)在一个优先集上达到最小值

误差E(a,b)= e^-K/N sum_i=1^N {[(prod_j=1^N b_j)^1/N a_i - (prod_j=1^N a_j)^1/N b_i] / b_i }

非正则探测函数的最优搜索问题:

正则:如果b(i,.)对每个i是连续可导的,并且导函数b’(i,.)是单调递减函数,且满足b’(i,0)>0和b’(i,infinity)=0,那么称b(i,z)是正则的.很明显,正则函数存在可逆的导函数,这个限制很强很不必要.

因为正则函数必须单调递增的,这个性质隐含着对于每一个单元格(盒子)C_i,搜索者在其中搜索一个物体所花的时间越长,在这个单元格中找到这个物体的可能性就越大.然而在很多情况下,这个假设并不正确.

探测函数:

b(i,z)=exp(–alpha_i (z-z_i)²), z>0, alpha_i>0, i=1~N,

b(i,z)=0, z=0.

例子: (2/3,1/3) 总时间4分钟- ->在引入了非正则探测函数之后,我们看到花在第一个抽屉里的搜索时间由2.35降到了2.28,这是因为在搜索第一个抽屉所花的时间超过了某一个临界点后,再继续搜索下去将会是徒劳的.

当b!=a=2/3时,探测概率P[f_b]变化曲线: 先增后减

Chapter 4:

静止目标搜索模型中,目标的位置是由一个概率分布函数来描述.对于运动目标来说,目标的位置是关于时间的函数,因此可以用一个随机过程来刻画.假设搜索时间被限制在一个区间[0,T]上,我们的目的是使得在时刻T发现目标的概率达到最大.

搜索空间为Y，搜索策略ψ (y,t)>=0表示一种搜索策略，即t时刻分配到y点上的搜索资源密度.搜索资源的投放速度是具有限制的，即存在一个与t有关的搜索资源上限m(t),使得：

∫_Yψ (y,t)dy<=m(t), t in [0,T]

满足上式的搜索策略ψ集合记为Ψ(m)。

最优解的充分必要条件：

空间Y通常表示搜索空间，而T表示搜索的时间区间;

令P是定义在集合Ψ中的一个实值泛函集合。

定理：如果P的G微分存在且有核函数k，则ψ*是Ψ中最优解的必要条件为…

如果P是一个concave functional，并且ψ in Ψ₀,那么上面的条件也是充分条件。

F导数：

G导数：