论文链接
(字比较丑。。。)
O. Abstract
- 本文主要研究问题为快速增量构建ESDF地图
- 利用的索引数据结构和双链表数据结构
- 使用BFS算法来实现更新
I. Introduction
- 基于对于四旋翼飞行器的研究，真正有用的是自由空间
- 基于梯度的规划是必要的——能够使路径远离障碍物
2.1 两种ESDF方法
- 利用距离抛物线曲线全局计算ESDF
缺点：对于资源的需求量大、
-
每次只滑动一局部地图
缺点：抛弃了所有过去的地图信息，对于全局规划和重归化做得不够
2.2 Voxblox的方法
- 由TSDF映射到ESDF，利用BFS进行更新
- Error1: 比实际的欧式距离有更大误差
- Error2: TSDF投影距离可能高估到最近表面的实际距离
2.3 FIESTA
不依赖于任何特定的映射框架
扩展尽可能少的节点，获得接近最优的结果
II. Related Work
- 前人的关于ESDF的计算频繁，不能满足地图精度和更新频率要求，被限制性能
-
对于前面的两个Error
- 对于 Error2 ：从网格地图直接地增量计算ESDF，更加直接简单，直接解决 Error2
-
对于 Error1 ：Error1 只能被优化而不能被解决
-
不能被解决的原因：BFS方式得不到准确解，简单理解就是用有限小圆去覆盖大圆总有剩余空间
III. System Framework
**利用两个独立更新的队列分别做插入和删除，将二者进行归并得到 UpdateQueue **
IV. Data Structure
- Occupancy Grip Map: 用于整合占用信息
- Voxel Infomation Structure: 记录体素信息
- Index Data Structure: 体素坐标到体素信息的映射
- Doubly Linked Lists: 占用体素空闲时的ESDF更新
A. Occupancy Grip Map && Voxel Infomation Structure
- 在 OGM 中存储占有概率
- 概率占用信息存储在体素信息结构中
B. Indexing Data Structure
- 边界框已知且内存足够
将所有体素的 VIS 指针放入一个数组中，只需计算索引，返回对应的 VIS 指针
-
边界框未知或内存不够
用哈希表将体素坐标转换为对应的 VIS 指针
但是查找时仍然复杂
几个体素为一块，哈希表用于管理块，再用体素坐标找到对应的块 \rightarrow 块哈希 \leq 体素哈希，平均时间复杂度为 \theta(1)
C. Doubly Linked Lists
- 体素DLL：表示离障碍最近的所有体素
V. Algorithm
5.1 ESDF 更新初始化
5.2 ESDF 更新初始化
- 每个在 DLL 中的体素都要出迭代，每一项的状态都要清除到观测但未更新的状态
具体做法：将 coc 用 IP 替代；将 ESDF 设置为无穷大
5.3 关于有限预测的补丁
- 新观测到的体素可能只更新邻居而引起系统的不一致
- 新观测到的个体的 ESDF 可能不会从之前存在的体素中更新
VI. Result
VII. Thinking
优点和创新点
- 相较于 Voblox，解决了TSDF投影距离高估产生误差的问题
- 尽可能地扩展更少地节点和降低时间复杂度
0 条评论