常用地图结构和基础知识

1、Occupancy grid map 占用栅格图

• 最稠密--每隔一个距离就要进行切分（当每个格子切的比较小也就是分辨率比较大的时候，内存非常大）
• 结构化
• 坐标索引查询，O(1)

https://github.com/ANYbotics/grid_map

2、Octo-map 八叉树地图

环境中没有障碍物的地方，就用大的方块表示，当大方块里面有小部分有障碍物，就递归地切分下去，直到包含了障碍物为止。

• 稀疏的
• 结构化
• 非直接索引查询

https://octomap.github.io/

3、Voxel hashing 体素哈希

通过二重哈希表来存储障碍物边界的每个voxel（单元栅格）

https://github.com/niessner/VoxelHashing

用于基于RGBD的3D视觉图像重建：

https://www.robots.ox.ac.uk/~victor/infinitam/

4、Point cloud map 点云地图

• 无序
• 无索引查询

https://pointclouds.org/

5、TSDF map (Truncated Signed Distance Functions) 截断的有符号距离函数

距离值：曲面外部为正值，内部为负值，并且可以以距离的大小来进行截断，比如正负两米内的点保留。

典型应用：

https://github.com/personalrobotics/OpenChisel

6、ESDF map（Euclidean Signed Distance Functions）欧式有符号距离函数

TSDF不截断的话，就是ESDF

当进行轨迹规划时，需要知道机器人距离障碍物的梯度，所以不需要进行截断。

开源：

• 全局：https://github.com/ethz-asl/voxblox     https://github.com/HKUST-Aerial-Robotics/FIESTA
• 港科大-无人机做局部地图规划：https://github.com/HKUST-Aerial-Robotics/Teach-Repeat-Replan

7、其他

Free-space Roadmap：随机采样的概率路线图，用凸多面体来表示路径点，再连接起来

Voronoi Diagram Map：利用ESDF提取地图的骨架--拓扑结构，稀疏