秋月琥珀

Indoor Coverage Path Planning: Survey, Implementation, Analysis

kohaku

贡献

覆盖路径规划

准备工作

地图分割

使用地图分割数据集中的地图提供分割，为每个单独的房间创建网格地图。

房间方向归一化

网格的方向选择会对覆盖路径规划算法的性能产生重大影响。

将网格地图与墙面的主方向对其，用白色表示可进入区域，黑色表示障碍，用 Canny 边缘检测算法恢复房间轮廓，然后用 OpenCV 中的 Hough 直线检测器。拟合出一组近似于房间围墙和障碍物的直线。从 1m 最小要求的线长开始，如果线太少就减少目标值。线的方向收集到 10° bins 的直方图中，取直方图最大 bin 中的线提供的精确平均旋转。

覆盖区域

支持用任意四边形定义覆盖区域

对于半径为 r 的圆形的以机器人为中心的覆盖装置，最多使用 l=2r 的正方形网格

牛耕式覆盖路径规划 Boustrophedon Coverage Path Planning

使用 Boustrophedon 细胞分解，遍历地图水平线的每一列，计算连通性，连通性增加时候封闭当前 cell，并开启两个新 cell， 降低时候当前两个 cell 封闭，并开启一个新 cell

分解完的网格可以使用旅行商问题获得最优路径，在每个 cell 中按主方向平行扫描，使得旋转运动最少

基于网格的旅行商覆盖路径规划 Grid-based Traveling Salesman Coverage Path Planning

根据准备工作将房间地图分解为有规则间距的单元格网格 G，单元格大小为 I，网格仅在地图可到达的区域生成或与原点最大偏移量为 I 的区域.

在单元格集 G 上求解旅行商问题

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

所有网格细胞都认为是神经元，与八个直接邻居有一条连接。

下一个神经元 Pn 根据激活状态 x 在每一步中选择要访问的神经元。j∈1,2,...,8，机器人的移动方向变化 Δθj，常数c。选择得分最高的邻居，即使已经访问过。

如果被卡住，需要沿着导致更远的未访问神经元。移动过后所有神经元都被更新，并选择下一个动作，直到完全访问。

基于网格的本地能量最小化 Grid-based Local Energy Minimization

房间被网格 G 填充，间距为 l，机器人从房间的一个角落 p0 开始，每个访问过的网格单元格放入列表 L。下一个目标位置从能量最小化网格中选出

p=(x,y,θ) 表示当前姿态，n 为潜在的下一个位置的坐标。平移距离 dt（单位为 l），转动距离 dr（单位为Π/2）。 N(n) 表示 8 个n周围的邻居 Nb8(n) 中尚未访问的位置数量的一半并作为一个使机器人停留在已经处理过的单元格边的吸引项。如果 8 个邻居中有未访问的，则选择其中一个作为下一姿态，如果都访问过了，下一姿态 n 将从未访问网格 G\L 中得出。

这个算法不会主动访问单元格两次，并在所有单元格被访问后结束。可以应用于不完整的地图和实时更新的地图。

基于等高线的覆盖路径规划 Contour Line-based Coverage Path Planning

不需要单元格和方向归一化，可以直接在房间地图上计算。

计算 Voronoi 图，找出地图上距离障碍物远的点，将 Voronoi 图在关键点上划分独立中心，临界点在局部最小值处，临界点与最近的障碍物点连接，划分覆盖空间

在每个 Voronoi 单元格中生成等距等高线

凸传感器覆盖路径规划 Convex Sensor Placement Coverage Path Planning

找到地图的最小传感器覆盖，找到观察位置的最短连接路径

算法评估

主观吸引力参数