阅读这节需要先阅读前置章节：【机器人感知运控笔记一】从点云到避障：距离场的构建、查询与梯度
否则，你无法理解本文介绍的一些内容。
这节算是一个高阶内容吧，介绍第一章节工作中的加速思路，包括从循环存储与索引开始，逐步走到观测融合、增量距离更新、桶队列和多邻域传播。

机器人移动时，环境地图需要持续接收新观测、调整覆盖范围、处理障碍变化，并把新的距离信息交给规划器。整理好每一层的数据，可以减少搬运、重复处理和无效传播，让相同的计算资源服务于更大的地图或更高的更新频率。

1. 一帧新观测进入地图后，会产生哪些工作

可以把在线建图看成几个相互配合的环节：

环节	需要完成的工作	适合关注的设计
管理地图范围	让局部窗口跟随机器人移动	循环缓冲区、固定内存复用
定位体素数据	把世界坐标映射到存储位置	位掩码、连续数组、体素块索引
解释观测	判断哪些位置自由、占据或未知	可见性射线、传感器误差模型
融合多帧信息	累积对占据和表面位置的判断	贝叶斯更新、TSDF 加权融合
更新环境距离	障碍增加或消失后修正距离	增量 EDT、最近障碍关联
安排传播顺序	选择下一批需要处理的体素	优先队列、桶队列、传播邻域

例如，一帧点云只改变了货架附近的一小片占据区域。系统可以继续复用其他区域的存储，把观测证据融合到受影响体素中，再更新这些变化所影响的距离。下面逐层说明其中的原理。

2. Ewok 的循环地图：窗口移动，重叠区域继续复用

机器人通常只需要高频维护周围一定范围的环境。这个局部窗口随机器人移动，而窗口中相当大的一部分内容会与上一时刻重叠。

设一维窗口有八个格子，当前包含 A～H。窗口向前移动一格后，包含 B～I。B～H 对应的世界位置保持不变，只有 A 离开、I 进入。

循环缓冲区把这八个存储位置首尾相接。移动窗口时，让新格子 I 使用 A 原先的物理槽位，B～H 继续留在原来的位置；同时把逻辑读取起点向前移一格。

图 1：上面两行表示实际内存，下面一行表示规划器看到的逻辑顺序。数组中的 B～H 原地保留，逻辑读取从槽位 1 开始，经过槽位 7 后再读取槽位 0。

三维地图采用相同思想。假设地图在三个方向上分别有 N_x、N_y、N_z 个体素，沿 x 方向移动一个体素间距时，新进入区域是一层 N_y×N_z 个体素。重叠区域直接复用，系统只需重新初始化这层区域，并更新窗口的逻辑起点。

以 100×100×100 的窗口为例，全图有 1,000,000 个体素，沿 x 移动一格时，新进入的层有 10,000 个体素。这个差异说明了循环存储节省数据搬运的原因。新区域随后会接收观测，并参与距离场更新。

固定大小的体素数组还便于预先分配内存。窗口移动过程中，系统主要更新索引和已有数值；常用数据保持在稳定的存储区域，也有利于处理器缓存的复用。

Ewok 对应的文献 [1] 把这种三维循环占据地图与均匀 B 样条轨迹结合起来。循环地图高效维护机器人附近的环境，B 样条用一组控制点表达平滑轨迹，并支持局部调整。两部分共同服务于持续的局部重规划。

3. 位掩码索引：把环绕定位变成低成本运算

循环数组需要把世界格子下标映射回有限的物理槽位。设一个方向有 L 个存储位置，世界格子下标为 i，环绕后的槽位为 j。数学上可以写成：

$$j=i-L\lfloor \frac{i}{L}\rfloor$$

这个表达式把 j 放在 0 到 L−1 之间。例如，L=8 时，下标 8 回到槽位 0，下标 9 对应槽位 1，下标 −1 对应槽位 7。

当 L 是 2 的幂时，还可以利用二进制表示。若 L=128=2⁷，只保留下标最低的七个二进制位，就能完成环绕：

下标 130： 10000010
掩码 127： 01111111
按位相与： 00000010  →  槽位 2

一般写法是 j = i & (L - 1)。这里的 & 表示按位与，L−1 则是低位全部为 1 的掩码。

正取模与位掩码索引都属于常数时间操作。位掩码的优势在于单次运算简单；当地图读写反复访问大量体素时，这种差异就会累积。对于其他长度，可以使用正取模实现循环数组。

三个方向分别得到环绕下标 j_x、j_y、j_z 后，还可以把三维下标展平为一维数组位置 a：

$$a=(j_x{N}_y+j_y)N_z+j_z$$

其中 N_y、N_z 为相应方向的体素数。按这个布局遍历时，z 方向相邻体素在内存中也相邻。配合预分配和连续访问，可以减少定位数据与等待内存的开销。

4. 射线、贝叶斯概率和双目噪声：把观测变成稳定证据

文献 [2] 关注体积占据地图的稳健、高效构建，并以双目视觉作为应用。理解这类方法，可以从“光束经过了哪里”和“这次测量有多可信”两个问题入手。

可见性射线。 激光或深度传感器的一次测量可以看作一条射线：光束终点提供占据证据，沿途提供自由证据。进行射线遍历时，可以跟踪光束下一次穿过哪个栅格面：比较 x、y、z 方向的下一处交点，选择最先到达的那个，进入相邻体素。这样，处理量主要随光束实际穿过的格子数量增长。

遮挡关系也通过射线表达。观测终点之后的空间可以保留未知状态，等待后续视角提供信息。测量不确定性较大时，表面附近的一段区域会采用更柔和的证据分配。

贝叶斯累积。 一次观测可以理解为一次支持“占据”或“自由”的投票。用 p 表示体素被占据的概率，定义对数几率 L：

$$L=\log \frac{p}{1-p},p=\frac{1}{1+e^{-L}}$$

p=0.5 时，L=0；占据更可信时，L 为正；自由更可信时，L 为负。在常用的逐次观测模型下，每次测量贡献一个对数证据增量 ℓ_t，更新写成：

$$L_t=L_{t-1}+{\ell }_t$$

ℓ_t 可以由观测在“占据”和“自由”两种假设下的似然比确定。命中与穿过分别提供正、负增量。把概率更新放到对数域后，许多重复的乘法与归一化可以整理为加法。

例如，从先验 p=0.5 开始，每次命中增加 0.85，连续三次命中后 L=2.55，对应占据概率约 0.93。随后一次穿过若贡献 −0.40，L 降为 2.15，对应概率约 0.90。观测通过累积改变判断，单次波动的影响由证据强度调节。

图 2：左图给出一组示例观测增量对应的概率变化。右图展示固定视差误差下，双目深度标准差随距离增长的趋势。

双目噪声模型。 设两台相机的基线长度为 B，焦距为 f，左右图像匹配得到的视差为 δ。f 和 δ 使用像素单位，B 使用米，估计深度 z 为：

$$z=\frac{fB}{\delta }$$

如果视差标准差为 σδ，使用一阶误差传播，可以得到深度标准差的近似式：

$${\sigma }_z\approx \frac{z^2}{fB}{\sigma }_{\delta }$$

例如，f=500 像素、B=0.10 m、σδ=0.5 像素时，2 m 处的深度标准差约为 4 cm，4 m 处约为 16 cm。这个模型帮助建图系统为近、远测量选择合适的置信度和表面不确定区域。

这一层设计的价值是让距离变换收到更稳定的占据输入，并使每帧观测的处理量集中在实际可见的空间。

5. Voxblox：先融合表面测量，再向周围提供距离

占据地图为体素保存“是否存在物体”的证据。另一条常见建图路线，是在表面附近直接保存带符号的距离测量，并把多帧测量融合起来。文献 [3] 的 Voxblox 就把这类表面融合与增量 ESDF 构建连接起来。

5.1 沿测量射线描述表面

设一条射线的表面返回位置距离传感器为 ℓhit，射线上某个体素的采样位置为 ℓv。一次观测提供的带符号距离可以写为 ℓhit−ℓv：表面前方为正，表面后方为负。

再指定截断距离 μ，把保存的数值限制在 −μ 到 μ 之间：

$${\psi }_{\mathrm{obs}}=\mathrm{clip}({\ell }_{\mathrm{hit}}-{\ell }_v,-\mu ,\mu )$$

clip 表示把超出给定区间的值限制到区间边缘。这样的字段称为 TSDF，Truncated Signed Distance Field，截断带符号距离场。表面附近的数值保留了位置和符号信息，较远处的数值按截断规则保存。常见射线融合会更新可见自由空间，并在表面后方保留有限的更新带宽。

图 3：左图中，沿射线到达表面的路程为 0.671 m，垂直到达平面的最短距离为 0.600 m；两条线描述不同的几何参照。右图展示 μ=0.8 m 时的截断函数，s 表示沿射线相对表面的位置。

TSDF 的观测距离通常沿传感器射线获得，便于直接整合深度测量；ESDF 为规划器提供空间中的最近障碍距离。前者负责稳定地描述表面，后者把表面信息扩展为可用于避障的空间距离。

5.2 用权重累积多次测量

设某个体素已经保存距离 D，累计权重为 W；新观测提供距离 d，权重为 w。加权融合为：

$$D_{\mathrm{new}}=\frac{WD+wd}{W+w},W_{\mathrm{new}}=W+w$$

权重表达测量置信度，可以结合量程、噪声和观测质量设置。例如，已有距离为 0.06 m、累计权重为 4，新测量为 0.02 m、权重为 1，融合结果就是 0.052 m。高置信度的历史证据在这个例子中占更大比例。

5.3 把变化传递给 ESDF

Voxblox 利用表面附近的 TSDF 信息，为 ESDF 设置可靠的近表面距离，再向周围传播。新的观测改变表面后，受影响的 ESDF 区域随之更新。

它还采用稀疏体素块组织地图：先把空间分成固定大小的块，在有需要时分配块，再通过索引结构定位。循环地图适合持续维护固定大小的局部窗口；稀疏体素块适合逐步扩展已观测环境。两者分别从窗口复用和按需分配的角度控制存储开销。

6. 障碍变化后，沿着关联找到需要更新的区域

动态环境中，障碍会增加、移动或消失。文献 [4]、[5] 讨论的一个重要问题，就是如何利用上一时刻的结果，更新距离地图及相关空间表示。

关键做法是：每个格子除了保存距离，还保存这个距离来自哪个障碍种子。设格子 i 当前关联的种子坐标为 s(i)，距离就可以从两者的位置关系计算。

新增障碍时，让更小的距离向外传播。 新障碍格先设置为种子，并尝试改善邻居的距离。如果某个邻居改用这个种子后距离更小，就更新它的距离和种子关联，再把它放入待处理队列。这个过程通常称为 lower wavefront，即向更小距离更新的传播前沿。

删除障碍时，先找出依赖它的结果。 原先关联到该障碍的格子需要失效处理，然后从仍然有效的周边种子重新获得距离。失效区域向外扩展的过程常称为 raise wavefront；随后再由 lower wavefront 填入新的有效结果。

图 4：原来右半部分的距离来自 B。删除 B 后，关联到 B 的格子先被标为失效，再由剩余障碍 A 的信息重新覆盖。格子内上方是距离，下方是关联种子的标签。

当环境只在局部改变时，更新工作可以集中到受影响区域。障碍种子的关联范围决定了影响会传播多远；一个影响广泛的障碍消失，也会引起较大的更新区域。

地图窗口滚动时，移出窗口的障碍同样可能影响保留区域中的旧距离。保存种子关联，就能把这种变化纳入同一套更新逻辑。

7. Voronoi 表示：从最近障碍关联中提取通道

距离地图还隐含着空间的分区结构：有些位置最近的障碍是 A，有些位置最近的是 B。把这些位置按最近障碍分类，就形成了 Voronoi 区域。

两个区域交界处，到相关障碍的距离相同；多个区域相遇时，会形成分支。在二维中，这些分界可以组成曲线骨架；三维中则会出现等距面及其交线。

图 5：三个等半径障碍 A、B、C 形成三个最近障碍区域。绿色分界在不同障碍之间保留相等间隙，可以作为通道骨架的来源。

这类表示适合提供远离两侧障碍的通道参考。例如，走廊两侧墙面之间的等距线接近走廊中线。规划器可以沿这些骨架连接路线，再结合机器人外形、运动学约束和轨迹平滑要求生成实际运动。

文献 [5] 研究欧式距离地图与 Voronoi 图的动态更新；[4] 进一步系统讨论动态环境中的高效栅格空间表示。距离值服务于碰撞检查和局部优化，骨架结构则帮助组织可通行空间。

8. 桶队列：把优先级相同的待处理格子放在一起

桶队列在距离场构建中承担的作用，是安排“接下来先让哪个格子向邻居传播信息”。要理解它与 ESDF 的关系，可以先看待处理格子是怎样产生的。

8.1 待处理格子从哪里来

沿用第 6 节的障碍种子表示：每个格子保存当前找到的最近障碍坐标，以及自己到这个障碍的距离。这里先考虑障碍格子中心作为距离为零的种子，并观察向更小距离更新的传播过程。

假设格子 A 已经关联到障碍种子 s。A 可以把 s 的坐标传给邻居 B，让 B 计算自己到 s 的直线距离。如果这个候选距离比 B 原先保存的距离更小，B 就更新距离和种子关联，并加入待处理队列。

B 入队表示：它刚刚获得了更好的距离信息，接下来需要把这个信息继续传给邻居。 队列中的任务随着传播不断产生；取出一个格子进行处理，又可能使其他格子入队。

一种常用安排是优先处理当前候选距离较小的格子，让障碍信息从近处逐渐向远处扩展。桶队列利用栅格坐标的整数特点，把这个处理顺序组织起来。

8.2 用欧式平方距离确定桶号

设待处理格子的整数下标为 i=(i_x, i_y, i_z)，它当前关联的障碍种子下标为 s=(s_x, s_y, s_z)。三个方向的格子边长均为 r，单位为米。用格子为单位的平方距离 P 作为优先级：

$$P=(i_x-s_x{)}^2+(i_y-s_y{)}^2+(i_z-s_z{)}^2,d=r\sqrt{P}$$

其中 d 是以米为单位的候选欧式距离。各方向的下标差都是整数，因此 P 是非负整数，可以直接作为桶号。开平方保持数值的大小顺序，所以按 P 排队与按 d 排队具有相同的先后关系，还能省去排队时的开平方计算。

以二维网格为例，障碍种子位于 (0,0)，分辨率 r=0.10 m。此时：

$$P=i_x^2+i_y^2,d=0.10\sqrt{P}\mathrm{m}$$

格子下标	平方距离 P	候选距离 d	所在桶
(1,0)	1²+0²=1	0.100 m	桶 1
(0,1)	0²+1²=1	0.100 m	桶 1
(1,1)	1²+1²=2	0.141 m	桶 2
(2,0)	2²+0²=4	0.200 m	桶 4
(2,1)	2²+1²=5	0.224 m	桶 5
(1,2)	1²+2²=5	0.224 m	桶 5

例如，(2,1) 与 (1,2) 到种子的距离相同，因此进入同一个桶。桶号表达距离优先级，桶里的元素保存需要处理的格子坐标。同一个距离层上的不同位置，可以在同一桶里等待传播。

8.3 跟着一个障碍种子，看入桶和出桶的过程

继续使用上面的例子，选择上下左右四个邻居。为了便于阅读，下面只列出第一象限中的部分格子：

1. 把障碍种子放入桶 0。 种子 (0,0) 的距离为 0，其他格子的初始距离设为无穷大。
2. 从桶 0 取出种子。 邻居 (1,0)、(0,1) 收到种子坐标，计算得到 P=1。它们更新距离，分别进入桶 1。
3. 处理桶 1 中的格子。 假设先取出 (1,0)，它把种子坐标 (0,0) 传给邻居。其中 (2,0) 算出 P=4，进入桶 4；(1,1) 算出 P=2，进入桶 2。已有相同或更小距离的邻居保持原记录。
4. 继续取最小非空桶。 桶 1 处理完后，先处理桶 2，再处理桶 4。格子 (1,1) 又可以把种子信息传给 (2,1)、(1,2)，使它们以 P=5 加入桶 5。

在第三步中，(1,1) 保存的距离是 0.10√2 m。计算使用的是它与种子 (0,0) 的坐标差，沿途的格子负责传递种子坐标。

随着格子依次出桶，越来越远的区域获得距离和种子关联。当待处理队列为空时，这一轮传播结束。

8.4 多个障碍如何竞争同一个格子

一个格子可能先收到较远障碍的信息，随后又收到较近障碍的信息。每次收到候选种子时，都重新比较距离。

例如，格子 (2,1) 原先关联到障碍 (0,0)，保存 P=5。随后在 (3,1) 新增一个障碍，其信息传播到该格子时，会得到新的候选值：

$$P_{\mathrm{new}}=(2-3{)}^2+(1-1{)}^2=1$$

因此，该格子改为关联新障碍，距离更新为 0.10 m，并按优先级 1 安排后续传播。队列中较小的桶也可以重新出现。

8.5 同一个格子两次入队，旧任务如何处理

一种常见的队列管理方式，会同时维护两份信息：

• 地图中的最新记录：格子当前关联的障碍种子及其距离优先级，找到更近的障碍后就更新。
• 队列中的任务记录：保存“要处理哪个格子”和“这次入队时的优先级”，用于安排之后的传播。

把上面的格子 (2,1) 记为 G。假设优先级为 5 的旧任务还在队列中等待时，G 收到了更近障碍的信息，优先级改善为 1。此时可以保留旧任务，再追加一条新任务：

时刻	地图中 G 的最新优先级	队列中关于 G 的任务
第一次获得距离并入队	5	(G, 5)，放在桶 5
发现更近的障碍，再次入队	1	保留桶 5 中的 (G, 5)，追加桶 1 中的 (G, 1)

旧任务中的 5 是入队时保存的数值；地图更新后，它仍然保留这个数值。 因此，同一个格子会暂时对应两条待处理任务。

接下来，队列按优先级取出任务。假设 G 的距离在此期间保持为 1：

1. 先取出 (G, 1)。 查询地图，G 当前保存的优先级也是 1，两者一致。于是读取 G 当前关联的障碍坐标，继续向邻居传播。
2. 后来取出 (G, 5)。 查询地图，G 当前保存的优先级已经是 1。这条任务所依据的距离已经被更小的距离替换，因此丢弃这条旧任务，继续取下一个任务。

这里的“过期”，指的是任务入队时依据的距离已经被更新。丢弃的是旧任务记录，地图中 G 的最新距离和障碍关联继续保留。

这种做法把旧任务的清理推迟到出队时：距离改善时只需追加新任务，省去了在队列中寻找并删除旧任务的操作；出队时再比较优先级，让有效任务承担后续传播。

图 6：左图示意候选格子的分桶方式；新候选 q=(2,1) 关联到种子 (0,0)，平方距离为 5，因此进入桶 5。取元素时，从当前最低的非空桶开始。右图示意不同邻域提供的信息传播方向，第 9 节继续说明邻域选择的作用。

8.6 桶队列怎样节省调度开销

普通二叉堆也可以按候选距离组织待处理格子。若队列中有 Q 个元素，插入和取最小值通常需要 O(log Q) 次结构调整。

如果桶索引使用预先分配的数组，插入就成为“找到桶号，追加一个元素”，单次通常为 O(1)。取元素时，可以用一个游标找到接下来的非空桶。空桶扫描范围、桶的数量和索引结构，共同决定队列的整体开销。

同一桶中的元素优先级相同，可以按简单的先进先出或后进先出规则处理。这样减少了逐个维护全序关系的工作。

文献 [6] 的 uniform-cost 思路强调按累计代价组织距离传播，并利用栅格代价结构提高效率。OctoMap 相关的 dynamicEDT3D 模块也采用按整数平方距离分组的桶优先队列。实际容器可以采用直接寻址数组或稀疏映射；直接寻址的桶号访问为常数时间，稀疏映射则按所选容器完成查找。OctoMap 的八叉树负责空间占据组织，距离更新队列负责安排传播任务。

9. 多邻域传播：一个格子出队后，把信息传给谁

第 8 节讲了如何从桶队列中选出下一个待处理格子。格子出队以后，还要决定把它关联的障碍种子坐标传给哪些格子。这组准备接收信息的格子，就叫当前格子的“传播邻域”。

第 8 节的例子已经使用过这个概念：每次只访问上下左右四个邻居，就是选择了四邻域。这一节继续沿用“传递障碍种子坐标、比较候选距离、更新后入队”的过程，讨论怎样选择接收信息的邻居。

9.1 从四邻域到更多方向

假设刚刚出队的格子下标为 i=(x,y)，可以采用以下几种选择：

邻域选择	这一次准备访问哪些格子	传递信息的特点
四邻域	(x−1,y)、(x+1,y)、(x,y−1)、(x,y+1)	沿上下左右方向传递
八邻域	四邻域，再加四个斜对角格子	可以直接把信息传给斜对角位置
扩展邻域	再加入相对偏移 (2,1)、(1,2) 及其对称位置等	一次可以把信息传到更远的格子

图 6 右图的中心表示当前处理的格子，箭头终点表示本次准备访问的邻居。蓝色箭头对应八邻域，橙色箭头示意更远的邻居。图中的坐标轴表示相对于当前格子的格子偏移。

在三维中，也可以按接触关系选择邻居：共享面的有 6 个，连同共享棱的共有 18 个，再加上共享角点的共有 26 个。

9.2 选出邻居以后，怎样计算它的候选距离

把刚出队的格子记为 i，把它当前关联的障碍种子坐标记为 s(i)，把本次访问的某个邻居记为 j。这里 i、j、s(i) 都是整数格子坐标，r 是每个格子的边长，单位为米。

邻域选择确定接收者 j；i 把种子坐标 s(i) 传给 j；j 再计算自己到这个种子的直线距离。 对应公式为：

$$d_{\mathrm{candidate}}(j)=r\Vert j-s(i){\Vert }_2$$

如果这个候选距离比 j 原先保存的距离更小，就更新 j 的距离和种子关联，并将 j 加入桶队列，等待它继续向自己的邻居传播。这正好接回第 8 节的入队过程。

以单个障碍种子 (0,0) 和目标格子 (1,1) 为例：四邻域可以经由 (1,0) 传递两次，让种子信息到达目标；八邻域可以从种子直接传递一次。两种情况下，目标收到的种子坐标都是 (0,0)，算出的候选距离都是 r√2。

这个例子说明了两件事：传播路线由邻域连接决定；每个候选距离则由接收格子与障碍种子的坐标差计算。增加斜向连接，可以缩短信息传递经过的链条。

9.3 更多方向为什么能帮助找到更好的候选

多个障碍同时存在时，格子会比较收到的候选。在“每格只保留当前最近种子、距离改善后才继续传播”的方案中，一个种子的候选如果在某个中间格子被更近的种子取代，就会在该处停止向外传递。增加邻域方向，可以提供跨过这些中间格子的传递路径。

看一个二维例子。障碍种子分别位于 A=(0,0)、B=(2,−1)、C=(−1,2)，我们希望求目标格子 Q=(2,2) 的距离。下表列出 Q 及其四个相邻格子到各个种子的平方距离，数值越小表示越近：

格子	到 A 的平方距离	到 B 的平方距离	到 C 的平方距离	最近种子
Q 左边的 (1,2)	5	10	4	C
Q 右边的 (3,2)	13	10	16	B
Q 下边的 (2,1)	5	4	10	B
Q 上边的 (2,3)	13	16	10	C
目标 Q=(2,2)	8	9	9	A

表中每个格子的平方距离，都从该格子自身的位置出发计算。例如，Q 左边的格子 (1,2) 距离 C=(−1,2) 两格，所以保存 P=4。它传给 Q 的是 C 的坐标；Q=(2,2) 距离同一个 C 三格，重新计算后得到 P=9。传播过程中接收格子会依据自己的位置计算候选距离。

Q 的四个相邻格子分别更靠近 B 或 C，它们会向 Q 提供 B 或 C 的种子坐标。采用上述队列规则的四邻域传播，在这个例子中会为 Q 留下平方距离 9。

Q 左下方的斜对角格子 (1,1) 则更靠近 A：它到 A、B、C 的平方距离分别为 2、5、5。采用八邻域后，(1,1) 可以把 A 的坐标直接传给 Q。Q 算出平方距离 8，便把原先的 9 更新为 8。若 r=0.10 m，对应距离就从 0.300 m 改善为约 0.283 m。

图 7：两幅图使用相同的障碍种子和格子坐标，颜色与字母表示格子当前关联的种子，P 表示该格保存的平方距离。左图中，i=(1,1) 尝试把 A 的坐标传给上方、右方邻居；这两个格子到 A 的候选平方距离为 5，而已有距离为 4，因此保留 C、B。Q 从四个直接邻居收到 B 或 C 的候选，得到 P=9。右图新增 i→Q 的斜向连接，A 的坐标直接到达 Q，给出更小的 P=8。箭头表示候选信息的传递。

在这个例子中，增加斜向邻居提供了一条额外的种子信息传递路径，让 Q 获得了更近的候选。更远的邻域也可以提供类似的跨格连接。

9.4 多邻域的计算取舍

邻域较小时，每个出队格子需要检查的候选较少；邻域扩大后，一次处理会访问更多位置，同时增加传播方向、缩短部分传递链条。总耗时取决于每次检查的数量，以及整个过程中产生了多少次更新和入队。

多邻域方法可以组合不同范围的邻域，在不同传播阶段或条件下使用它们。文献 [7] 研究的就是利用多个邻域进行欧式距离传播，在候选覆盖、距离精度与计算量之间作出安排。

把第 8 节与本节连起来看，一次处理依次完成四件事：桶队列选出格子 i；邻域给出接收者 j；距离公式计算 j 到候选种子的距离；改善的结果再加入桶队列。

10. 从河流测绘看完整系统的效率

文献 [8] 讨论小型飞行机器人在河流环境中的感知与建图。树冠遮挡可能影响 GPS 和岸线可见性，机载平台还受到重量、功耗与计算资源限制。系统结合视觉、激光、惯性信息以及间歇可用的 GPS，估计机器人运动、识别河流并构建障碍地图。

从地图原理看，这篇工作的作用在于把几项设计放回完整任务中：位姿估计让不同时间的观测对齐；可见性与传感器模型解释当前观测；局部环境表示为飞行路径提供障碍信息；各模块的更新频率与数据规模需要适应机载资源。

这提供了一个实用的优化视角：先找出任务真正需要的空间范围、地图细节和更新时间，再为这些信息选择合适的存储、融合与距离更新方式。最终得到的是能够持续服务运动规划的环境表示。

11. 文献索引与阅读重点

下面按首次引用的顺序列出八篇参考文献，并把每篇工作的主要作用对应到本文内容。阅读时可以先找到感兴趣的建图环节，再沿相应文献了解设计细节。

编号	对应的学习主题	建议阅读时关注的问题
[1] Ewok	随机器人移动的三维循环地图、局部轨迹调整	窗口移动时怎样复用空间数据；怎样把环境更新交给平滑轨迹优化
[2] Schauwecker、Zell	可见性射线、概率占据和双目测量误差	一次观测怎样给自由与占据提供证据；噪声如何改变证据强度
[3] Voxblox	TSDF 融合、稀疏体素块与增量 ESDF	多帧表面测量怎样融合；变化怎样传递到可供规划查询的距离场
[4] Lau 等，2013	动态环境中的栅格空间表示	距离、最近障碍关联与空间骨架怎样共同服务导航
[5] Lau 等，2010	欧式距离地图与 Voronoi 的增量更新	新增和删除障碍分别触发怎样的传播
[6] Verwer 等，1989	按代价组织传播及高效队列	怎样利用距离代价的结构减少队列维护开销
[7] Cuisenaire、Macq，1999	多邻域欧式距离传播	邻域覆盖怎样影响候选传播、精度与速度
[8] Scherer 等，2012	资源受限平台上的多传感器感知与建图	定位、可见性、环境表示与计算资源怎样协同

[1] V. Usenko, L. von Stumberg, A. Pangercic, D. Cremers. Real-Time Trajectory Replanning for MAVs using Uniform B-splines and a 3D Circular Buffer. IROS, 2017. 论文页面 · DOI

[2] K. Schauwecker, A. Zell. Robust and efficient volumetric occupancy mapping with an application to stereo vision. ICRA, 2014. DOI

[3] H. Oleynikova, Z. Taylor, M. Fehr, R. Siegwart, J. Nieto. Voxblox: Incremental 3D Euclidean Signed Distance Fields for On-Board MAV Planning. IROS, 2017. 论文页面 · 项目的 ESDF 生成说明

[4] B. Lau, C. Sprunk, W. Burgard. Efficient grid-based spatial representations for robot navigation in dynamic environments. Robotics and Autonomous Systems, 2013. DOI

[5] B. Lau, C. Sprunk, W. Burgard. Improved updating of Euclidean distance maps and Voronoi diagrams. IROS, 2010. DOI

[6] B. J. H. Verwer, P. W. Verbeek, S. T. Dekker. An efficient uniform cost algorithm applied to distance transforms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989. DOI

[7] O. Cuisenaire, B. Macq. Fast Euclidean Distance Transformation by Propagation Using Multiple Neighborhoods. Computer Vision and Image Understanding, 1999. DOI

[8] S. Scherer, J. Rehder, S. Achar, H. Cover, A. Chambers, S. Nuske, S. Singh. River mapping from a flying robot: state estimation, river detection, and obstacle mapping. Autonomous Robots, 2012. 作者机构页面 · DOI