2025年ipa 覆盖算法分析（二）

参考

Indoor coverage path planning: Survey, implementation, analysis. 多种覆盖算法的实现和对比

上篇文章

Grid-based Traveling Salesman Coverage Path Planning 基于栅格旅行商覆盖路径算法

基于栅格的旅行商问题（TSP）规划器将房间地图的可访问区域分解为一系列栅格单元。覆盖路径规划问题的解决方案是寻找一条访问所有栅格单元，且全局最短的路径。栅格单元之间的移动距离近似于它们的最短路径的长度，该最短路径由原始房间地图上的 A* 算法计算。

TSP 通过 Concorde 求解器，或者遗传算法，或者简单但快速的最近邻方法近似求解。

Neural Network-based Coverage Path Planning 基于神经网络的覆盖路径算法

基于神经网络的覆盖路径规划器受神经动力学启发。

神经动力学简介

神经元通过动作电位来传递信号。信号的传递和产生与细胞膜两侧的电势差相关，该电势差称作膜电位。神经元处于休息状态，其膜电位保持恒定，被称为静息电位。在动作电位到达后，膜电位会发生变化并最终衰减回静息电位。如果变化是正的，则是兴奋性信号。如果变化是负的，则是抑制性信号。

神经网络建模

将房间地图栅格化作为机器工作空间 W，障碍物在 W 中属于不可访问区域。把 W 中的可访问区域作为神经网络空间 S，神经网络中每个栅格单元都称为神经元。神经元最多与 8 个相邻的神经元直接连接，如图 fig.17。

W 空间中的未访问区域和 S 空间中相邻的神经元提供兴奋信号，W 空间中的障碍物提供抑制信号。每个神经元的相邻神经元构成子集 R_i 。那么第 i 个神经元的信号值分流公式（shunting equation）表示为：

$\frac{d x_i}{dt}=-Ax_i+(B-x_i)([I_i]^++\sum^{k}_{j=1}{w_{i,j}[x_j]^+})-(D+x_i)[I_i]^- \quad (1)$

A：非负常量，表示神经信号被动衰减率，模拟了真实神经元在无外部刺激情况下会恢复到静息电位。

B：非负常量，表示神经信号上限，也就是最大兴奋值。

D：非负常量，表示神经信号下限，也就是最大抑制值。

k：第 i 个神经元的相邻神经元数目。

I_i ：第 i 个神经元的外部输入信号。

$I_i = \begin{cases} E \\ -E \\ 0 \\ \end{cases}$

E 是一个远大于 B 的正常数，E 表示来自未访问区域的信号，-E 表示来自障碍物的信号。 $[I_i]^++\sum^{k}_{j=1}{w_{i,j}[x_j]^+}$ 表示兴奋信号的输入， [I_i]^- 表示抑制信号的输入。

兴奋 [a]^+ 和抑制 [a]^- 都是线性阈值函数，类似 $[a]^+=max\{a,0\}$ 和 $[a]^-=max\{-a,0\}$ ，只有达到阈值才被激活输出值，否则输出 0 表示未激活。这里模拟了真实神经元需要接收刺激达到阈值才会触发动作信号。

$w_{i,j}$ ：表示第 i 个神经元与其第 j 个相邻神经元之间的关联性权重，不同的相邻神经元影响力不同。

在论文中，关联性权重 $w_{i,j}$ 被进一步表示为 $w_{i,j}-f(|q_i-q_j|)$ ，f(a) 是关于神经元之间欧氏距离的单调递减函数。描述神经元离得越远，影响力越低。

$x_{j}$ ：表示相邻的第 j 个神经元的神经信号值。

需要注意上面的神经元信号的计算公式是对时间的微分。

通过遍历所有神经元计算根据公式(1)来更新整个神经网络信号值。论文只是说神经元通过相邻边来“传播”更新，但未说明具体方法。

下面说明下我的猜测：如图 fig.18，以一个神经元为传播半径增长步进，以机器为中心扩散传播。每次更新第 l 轮半径 L_l 以内的未更新神经元 $x_k\{L_l\}$ 的信号值，首先暂存这些待更新神经元的旧信号值 $V_{old}\{x_k\{L_l\}\}$ ，然后再按照公式 (1) 更新，因为计算涉及相邻神经单元信号值，所以在计算 $x_k\{L_l\}$ 信号值时候，会使用到神经元 $x_{k+1}\{L_l\}$ 信号值。此时就要使用前面保存起来的旧信号值 $V_{old}\{x_{k+1}\{L_l\}\}$ 计算了。待这轮半径计算好后，再把数据一起更新到本轮的待更新神经元 $x_k\{L_l\}$ 中。

图 fig.18 中，第一轮传播是半径 L1 蓝色圆圈内的浅蓝色神经元需要更新；第二轮传播是半径 L2 紫色圆圈内的浅紫色神经元需要更新；第三轮传播是半径 L3 红色圆圈内的浅红色神经元需要更新；第四轮 ......

在全覆盖路径计算中，还需要考虑机器转弯，越小的转弯提供越大的兴奋信号值。

下一个机器位置记作 p_n ，相邻神经元的信号值 x_j ，其更新公式由 (1) 提供。 $\Delta \theta_j$ 是机器从当前神经元位置移动到相邻神经元位置的转角变换量，c 是正常数，表示转角信号值权重：

$p_n \Leftarrow x_{p_n} = \max_{1 \le j \le 8}{\{x_j + c(1-\frac{\Delta \theta_j}{\pi})\}}, \quad \Delta \theta_j \in [0,\pi] \quad (2)$

神经网络需要计算所有神经元的神经信号值，但是机器的移动仅仅考虑相邻神经元信号差，机器会朝着相邻最高信号值的方向移动。

如图 fig.19，是论文中的一个示例。A 图是一个测试环境，机器位于大概 [5,0] 的位置，此时整体的神经网络信号值分布情况（论文中称为 dynamic activity landscape）如 B 图。B 图 x y 轴对应 A 图的 x y 轴，z 轴是神经信号值，红色框出来的区域对应 A 图中障碍物区域。

需要注意到的是图 fig.19 中左侧区域是弓字型路径，这说明在公式(1)中， $w_{i,j}[x_j]^+$ 中对当前机器侧方的兴奋值输入权重更大，甚至比公式 (2) 中补充的 0 转角信号值还要高些！

如图 fig.20，要实现弓字路径，机器左侧信号值要比前方信号更加强才行。

但在最开始的规划中机器又是如何走直线的？如图 fig.21。

论文对外部兴奋信号的输入没有作具体说明，很多地方推敲起来都有疑点。

Grid-based Local Energy Minimization 基于栅格的局部能量最小算法

将地图可访问区域栅格化，栅格大小为 l。从房间角落（x，y最大或最小的可访问栅格） p0 开始遍历地图，把访问过的栅格添加到列表 L 中。从地图中选择能量（代价）最小的未访问栅格作为下一个目标：

$E(p,n)=d_t(p,n)+d_r(p,n)+N(n) \quad (3)$

$d_t(p,n)=\frac{\sqrt{(p_x-n_x)^2+(p_y-n_y)^2}}{l} \quad (4)$

$d_r(p,n)=\frac{||p_\theta-n_\theta||_{angle}}{\pi / 2} \quad (5)$

$N(n)=4-\sum_{k \in Nb_8(n)}{\frac{|k\cap L|}{2}} \quad (6)$

p = (x, y, θ) 表示当前机器人位姿，n 是候选目标栅格的坐标。

公式 (4) 计算欧式距离代价，单位是栅格单元 l。

公式 (5) 计算旋转代价，以 π/2 为单位。这里可以把除以 π/2 的动作看做缩放。因为公式 (4) (5) (6) 最后要求和，需要平衡 3 类代价的权重。 $n_\theta$ 是 p(x,y,θ) 转向 n(x,y) 的角度，如图 fig.22 所示，head 是当前机器朝向，α 是转向候选点 N 的角度，角度在 [0, π] 范围内。

公式 (6) 计算候选点附近的吸引力（其实是斥力，数值越低越优）。Nb8(n) 表示候选点 n 附近的 8 个相邻栅格，k 属于 Nb8(n)， $k \cap L$ 表示已访问的栅格， $\sum_{k \in Nb_8(n)}{\frac{|k\cap L|}{2}}$ 表示候选点 n 一半的已访问相邻栅格数量。公式 N(n) 表示一个候选点附近如果被访问过，说明这个位置附近的访问代价（能量）会比较低，那么机器去这个候选点的代价也可能比较低。公式 (6) 使得机器倾向于规划靠近已访问区域的路径。应用在清洁机器中这就是自动补扫功能了。

如图 fig.23，p 是机器当前位姿，前面灰色栅格表示障碍物。此时有 n0 和 n1 都是候选点，两个候选点的距离代价和旋转代价都一样，最后靠公式 (6) 决定下一个移动栅格：n0 的周围已访问栅格数量 4 比 n1 周围已访问栅格数量 2 多，机器下一步向 n0 移动。

算法还可以结合传感器实时感知，若候选点有碰撞风险可以跳过，选区其他候选点计算。当所有栅格被访问添加到列表 L 中时候结束算法。与神经网络规划类似，该过程也适用于实时更新中的地图，能够对移动障碍物做出反映。

论文没有说明候选点是如何选择的。当机器局部受困后，如果还要继续使用该算法脱困或转移位置，就需要适当的候选点来引导机器离开，此时候选点的选择比较讲究了。所以这个时候最简单的处理就是用 A* 规划路径脱困，到达未访问区域后再重新启用能量最小算法。不知道 ipa 中是怎么处理这种情况的。

Contour Line-based Coverage Path Planning 基于轮廓线的覆盖路径算法

基于轮廓线的覆盖算法不需要地图经过房间方向标准化处理，可以直接在原始房间地图上计算。

首先计算房间地图的 GVD 图，可以简单说 GVD 图就是房间地图中可访问区域的骨架。然后在 GVD 图中筛选出最近障碍物恰好是 2 个的 GVD 点，称为关键点，关键点往往出现在两个较大区域之间的狭窄通道处。关键点与其最近障碍物的连线得到关键线，关键线把房间地图划分出多个子区域单元。

这里有可能存在关键点密度比较高的问题，过滤多余关键点的方法可以参考 ipa 分区算法的 Voronoi 图分割部分。

如图 fig.24 中，a 图是测试环境图，b 图中的黑线是 GVD 图，c 图中空心圆点是关键点，d 图中虚线是关键线，e 图根据关键线和地图中的障碍物把房间划分出多个子区域单元，f 图把子区域单元进一步抽象做拓扑节点。

在每个子区域中，计算距离变换，表示每个可访问单元（如果是栅格地图，那么可访问单元就是栅格）到最近障碍物或区域边界的距离，从而生成一圈圈等距轮廓线。

轮廓线的间距定义为机器覆盖面积半径 2 倍： w_c=2*r_c ，轮廓线级数，也就是第 i 级轮廓线的距离变换值表示为： $c_i=r_c+i*w_c, \ i \ge 0$ ，这里要增加机器覆盖面积半径的偏移，因为机器靠近边界运行时候，跟踪的路径（轮廓线）与边界距离半个机身。轮廓线级数从区域边界向区域内部增长。

轮廓线之间用类似能量最低覆盖算法中的公式 (3) 来连接，不同子区域单元的轮廓线亦是如此。

图fig.25 是用 plotlylib 显示的 costmap2d 轮廓线图，大概显示了该算法规划的覆盖路径效果。

Convex Sensor Placement Coverage Path Planning 凸感知放置覆盖路径算法

这里直接介绍算法论文《Efficient Measurement Planning for Remote Gas Sensing with Mobile Robots》的内容。

该算法使用传感器来覆盖检测或感知地图的可访问空间。

问题描述

在栅格化的房间地图中，空间 O 表示障碍物的栅格集合，空间 S 表示可通行且传感器可感知的栅格集合。机器位姿定义为 $p_j=(a_j, \theta_j), \quad a_j \in S, \quad \theta \in \Theta$ 。论文中限制了机器只能够前进和旋转，旋转角度 $\Theta \in \{0, \frac{\pi}{2}, \pi, \frac{3\pi}{2}\}$ 。这个被约束的位姿 p_j 组成集合 P。

如图 fig.26 所示，小圆圈表示机器，圆圈内的箭头表示机器的有限航向角，仅上下左右四个方向。有限航向角 + 空间 S 构成了机器的有限位姿集合 P。在运动学上，机器仅支持前进和旋转，由于位姿航向角受限，所以旋转角角度也受限。其中红色曲线并非表示机器弯曲前进，只是作图避开中间的小圆圈而已，机器实际还是直线前进的。

感知配置定义为 $c_i=(p_i,\phi_i, r_i)$ ， $p_i \in P$ 是机器位姿， $\phi_i$ 表示传感器圆心角大小， r_i 是感知半径。如图 fig.27。

感知规划

算法主要思路：选择最小数目的感知配置点，满足房间地图单元完全被感知到，然后这些感知配置点通过解决其旅行商问题找到最优最短路径。

如图 fig.28，传感器配置点的感知范围覆盖房间所有可访问单元。求解配置点的放置问题称为感知放置问题。

如图 fig.29 所示，(a) 图是测试环境图，(b) 图中黑色原点是候选感知配置点，(c) 图中通过 TSP 求解得到候选点的最优路径，同时使得感知覆盖地图所有可访问单元。

通过整数线性规划找到候选感知配置点的最小集合：

$\underset{C}{minimize}\ {C^T T_s}, \quad VC \succeq 1,C \in \{0,1\}$

C：是配置点选择序列，表示候选配置是否被选择，例如有一个候选配置点序列（列向量）为 $C_p=\{c_0, c_1, c_2, c_3, c_4\}$ ，那么此时有 $C=\{1, 0, 0, 1, 1\}$ 表示c0 c3 c4 被选择。 C^T 是 C 的转置得到行向量。

T_S ：是感知代价序列，列向量，表示配置点的感知代价多少。即 $T_S[i]=t^S_{C_i}$ ，i 是候选感知配置点集合 C_p 序号。

$VC \succeq 1$ ：表示至少有一个候选感知配置点？（不确定）

令 $a_i \in S$ 表示 S 中的栅格单元序列，令 n 表示候选感知配置点集合 C_p 数量，那么有二进制矩阵 V：

$V[a,c]= \begin{cases} 1 & if a \in V_P(c) \\ 0 & otherwise \end{cases}$

V[a,c] 等于 1 表示栅格单元 a 在候选点 c 的感知范围内。

论文使用最近邻算法解决 TSP 问题。

凸稀疏（CONVEX RELAXATION）优化

论文提出了一种迭代凸稀疏方法 conv-SPP 解决感知放置问题。

优化理论太抽象了......

覆盖效果对比

以机器 footprint 计算的覆盖效果。

以传感器感知范围计算的覆盖效果。

第一行是牛耕覆盖算法，第二行是栅格旅行商算法，第三行是神经网络覆盖算法，第四行是基于栅格的局部能量最小覆盖算法，第五行是轮廓覆盖算法，第六行是凸传感器覆盖算法。

第一列，第二列是无家具环境，第三列是带家具环境。

结论

牛耕覆盖算法在空旷环境能够提供漂亮的覆盖路径，但在复杂，混乱的环境中规划路径有些混乱。覆盖率偏高。

基于栅格的旅行商的覆盖算法计算量很大。

神经网络覆盖算法和局部能量最小覆盖算法的优点是能够实时规划，适应动态地图和动态障碍物的场景。

基于栅格的局部能量最小覆盖算法在杂乱环境中的规划能力十分优秀，但覆盖率偏低。

轮廓覆盖算法在以机器 footprint 覆盖（小覆盖面积）计算情况下，规划路径有较少的旋转，路径长度较短的优势。

凸传感器覆盖算法在以传感器感知覆盖计算的情况下表现优异。

2025年ipa 覆盖算法分析（二）

参考

相关论文

相关文章

上篇文章

Grid-based Traveling Salesman Coverage Path Planning 基于栅格旅行商覆盖路径算法