【学习笔记002】基于搜索的路径规划

😀

比较基础，简单过一下

基础概念

配置空间

机器人配置（Robot Configuration）：能够完整描述机器人当前状态的一组参数。例如，平面移动机器人通常用表示位置和朝向。

自由度 (DOF): 完整描述机器人配置所需的最少独立变量数量。例如有3个变量，因此机器人有3个自由度。

配置空间（Robot configuration space）:由机器人所有可能配置构成的空间。若机器人有n个自由度，那么配置空间通常是n维的。

一个机器人姿态对应 C-space 中的一个点：机器人从起点移动到终点，就相当于一个点在配置空间中沿着一条曲线运动。

在真实工作空间（workshop）中，机器人有一定的大小和形状，不能简单地把它当作质点。转换到配置空间后：

将机器人缩成一个点；

根据机器人的尺寸，把真实障碍物向外“膨胀”；

膨胀后的区域称为 C-obstacle（配置空间障碍区）；

机器人点可以安全存在的区域称为 C-free（自由空间）。

因此：

图中左侧是现实的工作空间；右侧将机器人变成红色小点，同时黑色障碍物周围增加了蓝色区域。只要机器人点不进入蓝黑区域，真实机器人就不会与障碍物碰撞。在配置空间（C-space）中表示障碍物可能极其复杂。因此，在实际应用中通常采用近似但更保守的表示方法。

所以，路径规划就是在中，找到一条从起点到终点的无碰撞路径。

一句话概括：把机器人缩成点、把障碍物变大，然后进行点的路径规划。

基于图的搜索方法。

路径规划环境可以表示成一张图：

节点：机器人可能到达的状态或位置；

边：机器人可以执行的移动；

：起点；

：目标点。

搜索从起点开始，不断探索相邻节点，形成一棵搜索树。找到目标后，沿每个节点记录的父节点反向追踪，就能得到起点到目标的路径。图中的红线就是最终路径。

其实就是深度搜索DFS与广度搜索BFS，没什么，跳过

启发式搜索

其中：

g(n)：从起点到当前节点的实际代价；

h(n)：从当前节点到终点的估计代价；

f(n)：经过当前节点到达终点的预计总代价。

Dijkstra’s Algorithm

Dijkstra 只使用已经产生的实际代价：。它不知道目标在哪个方向，因此会从起点向各个方向均匀扩展。即使目标就在右侧，它也可能搜索起点周围大量与目标无关的节点，造成较大的时间和内存开销。

A* 同时考虑两部分：

其中：

g(n)：从起点到节点n的实际累计代价；

h(n)：从n到目标的估计剩余代价；

f(n)：经过n到达目标的预计总代价。

A* 每次从优先队列中取出f(n)最小的节点。

可以这样理解：

Dijkstra 只看g(n)：已经花了多少钱；

贪心搜索只看h(n)：看起来还剩多远；

A* 看g(n)+h(n)：预计总共需要多少钱。

这个很熟悉了

工程考虑

一般栅格地图采用8邻域（考虑斜边）。此时欧式距离不是最好的启发函数，不是很“紧”，只得是有能更接近真实最短代价的求法。如图的Octile distance（八方向距离）。

比如下图就是水平走三次，斜着两次，距离是

在 A* 搜索中，多个节点可能具有相同的评价值 f(n)=g(n)+h(n)，此时需要使用 Tie Breaker 决定节点的扩展顺序。

常用方法是在 (f) 相同时，优先扩展 (h) 更小的节点，即优先选择更接近目标的节点，从而减少无效搜索。

也可以使用节点到起点—终点直线的偏离程度作为次级指标，使搜索方向更加集中，生成的路径更自然。

严格的 Tie Breaker 只改变同一 (f) 值下的扩展顺序，因此不会破坏 A* 的最优性。

如果通过放大启发函数或添加扰动来打破平局，则可能提高搜索速度，但也可能破坏启发函数的可采纳性，进而失去严格的最优性保证。

Jump Point Search

普通 A* 通常把相邻格子加入 Open List，而 JPS 会向前扫描很远，只把重要的“跳点”加入 Open List。

灰色格子：可剪枝邻居

白色格子：自然邻居。自然邻居是符合当前运动方向、不能直接删除的邻居。

红色格子：强制邻居。我认为定义就是从X的父节点到强制邻居的更便宜的路或者是和当前代价一样的路径被截断了。

当前节点只要拥有强制邻居，当前节点本身就成为跳点。 对角搜索过程中，如果某个位置的水平或竖直递归能够找到另一个跳点或目标，那么这个对角位置本身也会成为跳点。

对角跳跃比直线跳跃多一条重要规则：

每向对角方向前进一步，都要分别沿两个直线分量进行递归扫描。

原因是：最优路径可能在这个位置从对角运动转为直线运动。如果不进行这些直线检查，就可能直接从旁边跳过去，从而漏掉正确路径。

算法流程：

从 x 沿某个直线方向不断向前扫描：

如果下一格是障碍物或越界，本次扫描失败；

如果遇到目标节点，目标就是跳点；

如果当前格子拥有强制邻居，当前格子就是跳点；

否则继续沿相同方向扫描。

图中有三个跳点。

JPS 的本质可以概括为：

在规则栅格中跳过不会导致路径决策变化的普通节点，只在目标、障碍物引起的转折点以及必要的方向切换位置进行 A* 搜索。

义父，请我喝杯蜜雪冰城吧。