Yang, Fan, et al. "FAR planner: Fast, attemptable route planner using dynamic visibility update." 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022. PDF

1. 概述

基于可见性图的规划方法

• 主要困难：在构建可见性图时，需要进行大量的计算，特别是在复杂三维环境中。（构建多边形）

• 主要优点：具有快速重新规划方面的优势，以及处理未知和部分已知环境的能力。

贡献点

• 提出一种多边形提取和增量可见性图构建的两层算法框架；

• 该框架能够动态地调整可见性图，以便在未知的环境下进行可尝试的导航并处理动态障碍；

实验结果： 在未知的和部分已知的环境中，达到了基准测试的最先进规划性能。

彩色曲线是从蓝点开始到红点结束的车辆轨迹。

青色线：在导航过程中建立的可见性图，用于引导车辆达到目标。

红色区域：观察到的全局环境。

黄色区域：表示用于更新局部图的局部环境。

2. 方法

2.1 障碍多边形的提取与记录

对于地面车辆，通常会在系统中运行一个地形可穿越性分析模块来分析地形特征。该模块从激光雷达或深度摄像机进行距离测量，输出$S$表示障碍物。根据$S$中的数据，构造二值图像，对二值图像做平均过滤，生成模糊图像，由此提取多边形组。从每个多边形中提取顶点，并根据内角清除部分顶点，得到最终的多边形。

2.2 两层可视性图的动态更新

通过增量的方式，只更新车辆附近的区域，由此对可视性图进行逐步更新，将计算均匀地分配到每个数据帧，有效降低了计算代价。

构建局部层： 对于$\mathcal E_{local}$中超过阈值的边，忽略了连接一个或两个多边形的不必要的边，并保留了“传递”边

更新全局层： 在局部上构造局部可见性图后，将局部与全局合并，更新与局部重叠区域的全局区域。

• 对局部图和全局图的顶点进行关联。
• 通过迭代消除离群值关联。
• 对局部边进行合并。

2.3 可视性图的规划

给定当前位置和目标位置，想在可视性图$G$中搜索当前点和目标点之间的最短路径。

• 首先将$p_{position}$和$p_{goal}$添加为全局层上的两个顶点，并将它们连接到具有非阻塞可见性边的$P^l_{global}$中的顶点。
• 在$\mathcal L_{global}$上运行广度优先搜索，如果有路径可用，则找到$p_{position}$和$p_{goal}$之间的最短路径。

2.4 扩展到三维多层可视性图

扩展三维版本的方法是将环境建模为多个水平切片，并提取多层多边形。

3. 实验

实验平台为地面车辆和无人机

实验内容：车辆：室内、室外、大型隧道；无人机：室外

中等尺度、中等复杂的室内环境中的地面车辆模拟：

数据分析：

4. 结论

通过构造可视性图，来实现一个底层的场景图，具有快速重新规划方面的优势，以及处理未知和部分已知环境的能力。

通过分层和增量的方式来降低运算量