【自动驾驶决策规划】PRM算法
·
1 基于采样的路径规划方法
路径搜索常用方式之一是基于网格的的方法（grid-based method），如A*算法，但基于网格的方法复杂度较高，与求解空间的维度相关，且得到的路径比较僵硬，对于车辆或移动机器人来说都不是很友好。
另外一种路径规划是基于采样的方法（sampling method），包括以下模块：
- 随机或确定性选择函数，在采样空间确定点
- 采样评估函数，来选择合适采样点
- 距离函数，确定待扩展点与当前之间的距离
这些模块可以构建出图或树结构来探索可行域内的可行轨迹。采样方法不是以最优为目的，只能得到近似最优解，好处是在解空间内探索效率较高，能快速得到满足要求的可行解
典型的基于采样的方法包括RRTs（Rapidly Exploring Random Trees）和PRMs（Probabilistic roadmaps），RRT更适合为单体轨迹规划提供有效的轨迹，PRM更适合为多体轨迹规划提供路线图（roadmap graph）
2 PRM过程
PRM算法是通过对空间进行大量采样来构建路线图，用于后续的特定查询。路线图是无向连接图，车辆或机器人可以路线图上由任意一点移动到其他点。点与点连接线最简单的就是直线。路线图构建好之后可以采用经典的A*算法来搜索路径。
PRM算法构建路线图过程如下所示。
3 PRM一些细节
- 由于PRM算法是随机从空间采样，对于障碍物附近，可以增大采样稠密度来提升路线图的有效性，或者可以通过基于特定概率函数进行采样
- 构建路线图的简单的做法是选择直线，但不满足运动学特征，会出现运动方向突变，所以需要局部优化或者连接线采用其他曲线
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
1
0- 0
已为社区贡献2条内容
所有评论(0)