230 lines
11 KiB
TeX
230 lines
11 KiB
TeX
\section{问题四：混合源的前向半盘覆盖与联合信念}\aigcC
|
||
\subsection{定向观测模型与无信号歧义}
|
||
在问题三中，"无信号"只有一种解释：源太远。
|
||
一旦引入定向源，这唯一的解释就被打破——源可能只是背对着检测点。
|
||
因此本问的关键在于为无信号保留第二种解释。
|
||
设定向源位于 $g$，朝向为 $\psi$。在检测点 $q$ 可见的充要条件为
|
||
\begin{equation}
|
||
\norm{q-g}\le r_{\mathrm{eff}},\qquad
|
||
(q-g)\cdot u(\psi)\ge0.
|
||
\label{eq:visibility}
|
||
\end{equation}
|
||
边界属于可见半平面。可见且距离不超过 $5$ m 时返回 $\near$，
|
||
否则返回 $\direction$；任何一个条件失败均为 $\sgnless$。
|
||
问题二的可行区域满足距离约束，定向接收还需满足前向半平面约束。
|
||
对于已发现频道，位于该区域内的负观测反映朝向遮挡，
|
||
因此不应被当作距离证据；区域外的负观测则同时包含距离与朝向两种解释。
|
||
这一区分直接决定了后续信念表示的形式。
|
||
|
||
朝向约束也改变了覆盖的要求。问题三的七点计划只保证"至少一站距离足够近"；
|
||
对定向源还要求该站位于源的前向半平面内，因此需要重新设计站点集。
|
||
向外发射的边界源需要在圆域外布置接收站点。
|
||
适用于混合源的站点集合 $S$ 应满足
|
||
\begin{equation}
|
||
\forall g\in\Omega,\ \forall\psi\in[0,2\pi),\
|
||
\exists s\in S:\quad
|
||
\norm{s-g}\le1000,\quad (s-g)\cdot u(\psi)\ge0.
|
||
\label{eq:halfcover}
|
||
\end{equation}
|
||
这是一项针对"位置、朝向"二元状态的全覆盖要求，而不是对位置的单变量覆盖。
|
||
|
||
问题三的七点计划不满足式~\eqref{eq:halfcover}；当前测试程序改用 $31$ 点最小命中集与（位置×朝向）联合幸存集，
|
||
定位停滞时以有限格后备清除兜底。
|
||
|
||
\subsection{方格点集的连续覆盖性}
|
||
在设计具体站点之前，先考虑一个容易证明的结构：方格点集。
|
||
取 $S_{49}=\{(700i,700j):i,j=-3,\ldots,3\}$。
|
||
其网格方域包含 $\Omega$，每个源落在某个边长为 $700$ m 的闭方格内。
|
||
方格四角恰好同时满足距离与朝向两项要求。
|
||
|
||
\begin{proposition}[方格四角的定向覆盖]
|
||
$S_{49}$ 满足式~\eqref{eq:halfcover}，对全向与任意朝向的定向源均保证发现。
|
||
\end{proposition}
|
||
\begin{proof}
|
||
设包含 $g$ 的方格四角为 $v_1,\ldots,v_4$。
|
||
四角距 $g$ 均不超过对角线长 $700\sqrt2<1000$。
|
||
由于 $g$ 是四角的凸组合，存在 $\lambda_i\ge0$、
|
||
$\sum_i\lambda_i=1$ 使 $\sum_i\lambda_i(v_i-g)=0$。
|
||
对任意朝向 $u$ 取内积，得
|
||
$\sum_i\lambda_i(v_i-g)\cdot u=0$，
|
||
故不可能四个角均满足 $(v_i-g)\cdot u<0$；
|
||
至少一角处于前向闭半平面，且同时满足距离条件。
|
||
\end{proof}
|
||
|
||
证明的关键是凸组合性质：四个方向的投影不可能同时为负。
|
||
该方案具有显式站点坐标和覆盖距离上界。不过在同样覆盖 $\Omega$ 的前提下，
|
||
网格方案的站点数并不经济，因此实际选点仍需借助集合覆盖模型。
|
||
|
||
\subsection{前向半盘最小命中集的31点方案}
|
||
把"每个位置与朝向组合至少被一个站点覆盖"写成整数规划，
|
||
就可以用远比网格稀疏的站点集完成同样的任务。
|
||
当前 \texttt{directional} 实现采用 \texttt{q4\_mincover\_v2} 计划。
|
||
在候选站点 $s_j$ 和离散目标状态 $(g_i,\psi_i)$ 上定义关联矩阵
|
||
\begin{equation}
|
||
A_{ij}=\mathbf1\{
|
||
\norm{s_j-g_i}\le r_{\mathrm{design}},
|
||
\ (s_j-g_i)\cdot u(\psi_i)\ge
|
||
\norm{s_j-g_i}\sin\gamma_{\mathrm{design}}\}.
|
||
\end{equation}
|
||
其中角度余量 $\gamma_{\mathrm{design}}$ 把"恰好落在可见边界"的情形排除在外，
|
||
使站点对朝向扰动保持稳健。站点筛选可写为集合覆盖模型
|
||
\begin{equation}
|
||
\min\sum_j z_j,\qquad
|
||
\sum_jA_{ij}z_j\ge1\ \ (\forall i),\qquad z_j\in\{0,1\}.
|
||
\label{eq:setcover}
|
||
\end{equation}
|
||
采用集合覆盖的贪心算法与冗余站点删除求近似解\cite{chvatal}，得到 $31$ 个站点。
|
||
设计阶段使用 $965$ m 距离与 $5^\circ$ 前向角余量，
|
||
最终按 $15$ m 位置间距、$72$ 个朝向采样复核。
|
||
验证结果覆盖全部 $3\,256\,200$ 个离散状态，
|
||
最坏覆盖距离约为 $990.051$ m。
|
||
|
||
\begin{figure}[htbp]
|
||
\centering
|
||
\includegraphics[width=0.72\linewidth]{geo-q4-minimum-cover-31-points.png}
|
||
\caption{31 点最小命中集的几何分布与定向源的读图约定。
|
||
实心圆点为圆域内检测站（$15$ 个），空心圆点为圆域外的检测站（$16$ 个），
|
||
后者用于接收向外发射的边界源；
|
||
浅色扇形区域为源位置圆域 $\Omega$。
|
||
图中左侧以一个圆外检测站为例说明定向源的观测读法：
|
||
绿箭头是该源的发射朝向、浅绿细线扇形是它的 $\pm90^\circ$ 可见范围、
|
||
红色虚线是检测站在该点测得的示向度，三者共同说明
|
||
"有朝向遮挡时同一位置也可能测不到信号"。
|
||
离散校验不等同于连续覆盖证明。}
|
||
\label{fig:q4plan}
|
||
\end{figure}
|
||
|
||
从离散覆盖推广到连续覆盖时，需同时计入位置与朝向的离散化误差。
|
||
设任意实际位置距某采样位置不超过 $\varepsilon$，
|
||
实际朝向距其采样朝向不超过 $\alpha$，覆盖站点距采样位置为 $d$。
|
||
由三角不等式及单位向量差的上界，一组充分条件为
|
||
\begin{equation}
|
||
d+\varepsilon\le1000,\qquad
|
||
(s-g_i)\cdot u(\psi_i)\ge
|
||
\varepsilon+2d\sin(\alpha/2).
|
||
\label{eq:continuous}
|
||
\end{equation}
|
||
采样网格应覆盖 $\Omega$ 及其边界。本文对 $31$ 点方案采用离散集合覆盖模型，
|
||
对 $49$ 点方案采用上述连续覆盖定理；连续近似误差的控制将在未来工作中讨论。
|
||
|
||
\subsection{位置与朝向联合候选的保守更新}
|
||
站点解决"能否发现"，而要完成清除还必须知道源在哪里、朝向如何。
|
||
这正是问题三的候选集表示不足以处理的部分：位置可行并不代表朝向可行。
|
||
对定向假设，在每个候选位置网格的中心 $z$ 附加 $H=24$ 个朝向档，
|
||
档宽为 $15^\circ$。令 $M_z$ 为仍可能的朝向掩码。
|
||
方向与近距离观测先更新位置约束，再保留可能覆盖检测点的朝向；
|
||
无信号时只有在整格处于 $1000$ m 保证接收盘内，才可删除必然可见的朝向。
|
||
|
||
记 $\beta=\operatorname{bearing}(z\to s)$、
|
||
$\Delta_\psi=7.5^\circ$，格内方位余量为 $\alpha_z$，
|
||
查表舍入余量为 $\eta_\psi=1.5^\circ$。
|
||
以 $d_\circ$ 表示圆周最小角差，保守保留条件为
|
||
\begin{equation}
|
||
\begin{aligned}
|
||
\text{正观测：}\quad&
|
||
d_\circ(\psi_k,\beta)\le90^\circ+\Delta_\psi+\eta_\psi+\alpha_z,\\
|
||
\text{盘内负观测：}\quad&
|
||
d_\circ(\psi_k,\beta)>90^\circ-\Delta_\psi-\eta_\psi-\alpha_z.
|
||
\end{aligned}
|
||
\label{eq:heading}
|
||
\end{equation}
|
||
第二行保留含有不可见方向的朝向区间，排除整个区间均可见的候选。
|
||
若格心距测点过近，格内方位可覆盖整个圆周，此时保留全部朝向。
|
||
在定向假设下，上述更新保持真源所在位置与朝向网格的可行性。
|
||
|
||
\subsection{可见性筛选与探点选择}
|
||
联合候选的第一个用途是给候选测点排序。
|
||
在混合场景中，一个测点是否值得去，取决于那里的候选源有多大可能正对着它。
|
||
对候选 $q$，以均匀接收半径假设给出距离权重
|
||
\begin{equation}
|
||
w_r(d)=
|
||
\begin{cases}
|
||
1,&d\le1000,\\
|
||
(1500-d)/500,&1000<d<1500,\\
|
||
0,&d\ge1500.
|
||
\end{cases}
|
||
\end{equation}
|
||
记 $\widetilde{\mathcal G}_c$ 为位置样本集，$b_z(q)$ 为与检测点 $q$ 相容的候选朝向档数，
|
||
采用如下\textbf{可见性权重}：
|
||
\begin{equation}
|
||
V(q)=\frac1{|\widetilde{\mathcal G}_c|}\sum_{z\in\widetilde{\mathcal G}_c}
|
||
w_r(\norm{z-q})\,\frac{b_z(q)}{24}.
|
||
\label{eq:visibility-score}
|
||
\end{equation}
|
||
分母 $24$ 为初始朝向档数，$b_z(q)$ 由保留朝向集合与预计算可见角区间的交集确定。
|
||
该权重用于衡量各候选点的相对检测价值，可直接避免"跑过去却因遮挡而无信号"的空跑。
|
||
|
||
候选族包括算法2给出的基础点、关于候选圆心的对跖点，以及
|
||
$0.5\rho,\rho,1.5\rho$ 半径上的八方向环点。
|
||
排除已被遮挡的重复点后，保留评分达到当前最大值 $70\%$ 的点，
|
||
并从中选择
|
||
\begin{equation}
|
||
\frac{\norm{p-q}}5+\frac{\norm{q-m}}5+6
|
||
\label{eq:q4score}
|
||
\end{equation}
|
||
最小者。常数 $6$ 是检测加换频的选点评分费用，
|
||
真实结算仍按当时频道计算。该规则优先避免完全遮挡的点，
|
||
再减少移动及后续接近距离。
|
||
联合集不可用时，返回算法2、对跖探点和环探的确定性顺序。
|
||
持续遮挡时转入基于距离约束的网格遍历清除。
|
||
|
||
\subsection{网格遍历清除与计算预算}
|
||
遮挡可能使定位长期无法收缩，此时需要一条不依赖朝向信息的兜底路径。
|
||
注意到清除是否成功只与距离有关，与源朝向无关，
|
||
因此可以放弃"先定位再清除"的顺序，改为逐格试探。
|
||
当一轮有效定位测量达到 $8$ 次，或连续遮挡探点达到 $4$ 次且候选区域仍较大，
|
||
对保守凸候选多边形建立边长 $20$ m 的方格覆盖。
|
||
保留所有与多边形相交的格子，并以格心作为清除点。
|
||
格内任一点到格心距离满足
|
||
\begin{equation}
|
||
\norm{g-z}\le10\sqrt2<20.
|
||
\label{eq:fallback}
|
||
\end{equation}
|
||
因清除与源朝向无关，只要真源保留在多边形中，
|
||
逐格清除必有一次到达其 $20$ m 内。
|
||
按最近邻顺序访问，首次成功即停止该频道的网格遍历。
|
||
|
||
兜底方案必须受预算约束，否则会挤占其他频道的处理时间。
|
||
若外包框宽、高为 $w,h$，保守格数上界为
|
||
\begin{equation}
|
||
B_{\mathrm{cell}}=
|
||
\left(\left\lceil\frac w{20}\right\rceil+2\right)
|
||
\left(\left\lceil\frac h{20}\right\rceil+2\right).
|
||
\end{equation}
|
||
当前格数硬上限为 $400$，现实预算需覆盖
|
||
$N_{\mathrm{cell}}\,t_{\mathrm{RTT},95}+t_{\mathrm{reserve}}$。
|
||
超过格数或预算上限即跳过并报告未解决；
|
||
全部清除点失败则保留候选集并记录异常。
|
||
在\textbf{候选区域包含真源、格数满足上限且预算足够}的条件下，
|
||
逐格访问可保证完成该源的清除。
|
||
|
||
\subsection{算法四与终止条件}
|
||
\begin{algorithm}[htbp]
|
||
\caption{前向半盘最小命中集、联合信念与后备清除}
|
||
\label{alg:q4}
|
||
\begin{algorithmic}[1]
|
||
\Require 混合源接口、定向覆盖计划与预算
|
||
\Ensure 已清除频道、未解决频道与停止依据
|
||
\State 加载覆盖计划；默认 $31$ 点按 $15$ m/$72$ 档校核，$49$ 点备选有连续证明
|
||
\While{存在未解决频道且预算充足}
|
||
\State 选择最近待测站，当前频道优先，批量检测未知频道
|
||
\State 更新凸位置候选与位置乘朝向联合幸存集；首次正观测后建立朝向候选
|
||
\While{频道尚未清除}
|
||
\State 按可见性概率筛选探点，取移动最省者执行测量
|
||
\If{满足半径判据}
|
||
\State 执行清除并跳出
|
||
\ElsIf{遮挡或定位停滞}
|
||
\State 检查格数与预算，允许则执行 $20$ m 方格后备清除
|
||
\EndIf
|
||
\EndWhile
|
||
\EndWhile
|
||
\State 主动退出时报告清除数与停止依据
|
||
\end{algorithmic}
|
||
\end{algorithm}
|
||
|
||
综上，问题四得到三点结论：1. 定向源使无信号具有距离与朝向两种解释，
|
||
候选集必须由位置扩展为位置与朝向的联合表示；2. 发现条件须由位置圆盘覆盖
|
||
提升为前向半盘覆盖，$31$ 点最小命中集以远少于网格的站点数完成该任务；
|
||
3. 清除与朝向无关这一物理性质可用于构造有界预算的兜底清除，
|
||
使遮挡不再导致任务无法完成。
|