Motion Planning学习笔记一：配置空间、图、图搜索、图遍历
2026-10-30 20:53:05
配置空间是学习路径规划的基础，绝大多数路径规划算法都是基于配置空间提出的。在配置空间中，机器人将变成一个质点，而机器人本身的大小和形状将会与障碍物做一个结合，以便进行碰撞检测。
- 工作空间与配置空间的对比：
机器人的工作空间是指机器人所能达到的空间点的集合。在此空间中，机器人是有大小和形状的，因此很难进行运动规划。
配置空间中，机器人被视为一个质点，从而简化了碰撞检测问题。
- 复杂度的处理：
当机器人在工作空间中存在多个自由度时，转换到配置空间会变得复杂。
常用的近似方法是，将机器人看作一个球体，然后在配置空间中以球体半径为长度膨胀所有障碍物。
图是由节点和边组成的表达方式，用于描述节点与节点之间的关系。
节点与边的关系：
无向：机器人可以在任意连接的节点之间移动。
有向：节点与节点只能根据箭头方向移动。
权重：机器人在节点间移动的代价，可以是距离、能量、时间等。
常用地图：
栅格地图：每个节点之间天然形成连接，适用于基于搜索的路径规划方法。
基于采样生成的地图：需要基于采样生成节点并连接，适用于基于采样的路径规划方法。
图搜索是路径规划中的核心部分，其总体框架和两种基本的图遍历算法如下。
总体框架：
建立一个容器，包含所有要访问的节点。
容器由初始节点进行初始化。
循环过程：
根据预先设定好的目的或指标弹出一个节点（访问一个节点）。
拓展：获取所有该节点的相邻节点。
将这些相邻节点储存到容器中。
结束循环（容器为空或得到目标路径）。
三个关键问题：
什么时候结束循环？
容器为空或找到目标路径。
如果图是循环的那该怎么办？
使用另一个容器记录已访问节点，防止死循环。
按照什么样的规则来弹出节点？
后续会进行分析。
两种基本的图遍历算法：
深度优先搜索（DFS）：后进先出（LIFO），每次访问都会优先访问容器中最深的节点。
特点：一条路径搜索到底，没有找到目标则回溯再搜索其他路径。
可能不是最优解。
动图展示：
广度优先搜索（BFS）：先进先出（FIFO），每次访问都会优先访问容器中最先进入的节点。
特点：一层一层地搜索完，直到找到目标。
会找到全局最优路径。
动图展示：
广度优先搜索VS.深度优先搜索：
广度优先搜索更有利于找到最短路径，因此通常将其作为图搜索的基础。
启发式搜索（Heuristic search）：
弹出节点的方式靠自定义的规则（启发）进行。
启发的本质是猜测目标节点与当前节点的距离，必须容易计算，否则降低搜索效率。
常用的启发规则有欧式距离和曼哈顿距离。
动图展示（无障碍物与有障碍物）：
总结：启发式搜索在无障碍物时能快速得到最优路径，但在有障碍物时可能得到次优路径；广度优先搜索虽然耗时更长，
热门标签
