本文总结路径规划算法相关知识点。

地图结构

方格图

Occupancy grid map 特点：

  1. 最稠密
  2. 结构化
  3. 可根据坐标索引查询

八叉树

Octo-map 特点：

  1. 稀疏
  2. 结构化
  3. 非直接坐标索引查询

Voxel hashing

特点：

  1. 最稀疏
  2. 结构化
  3. 非直接坐标索引查询

点云

Point cloud map 特点：

  1. 无序
  2. 无索引查询

TSDF map

Truncated Signed Distance Functions map

ESDF map

Euclidean Signed Distance Functions map

图搜索基础

配置空间

  • 机器人配置：机器人上所有点的位置描述。
  • 机器人自由度 (DOF)
  • 配置空间 (C-space) ：包含 $n$ 维空间的所有可能机器人配置。

任意机器人姿态均可用配置空间中的一个点描述。

图

图包含节点和边，且点之间有连接关系。

图搜索

  1. 用一个容器存储所有需要被访问的节点。
  2. 容器初始状态为 $X_s$。
  3. 循环：
    • 根据先前定义的函数关系移除节点。
    • 扩散（包含所有邻节点）。
    • 将所有邻节点放入容器中。
  4. 容器为空时结束循环。

图搜索算法

广度优先搜索 (BFS)

广度优先搜索使用队列 (queue) 排序。

策略：移出/入容器内最浅层级的一个节点。

深度优先搜索 (DFS)。

深度优先搜索使用栈 (stack) 排序。

策略：移出/入容器内最深层级的一个节点。

又称为贪心算法。

定义：启发式算法是用函数关系推测目标的距离。

在某些情况下（如特定障碍物）可能会变为局部最优情形。

未完待续……