【自动驾驶决策规划】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算法是随机从空间采样，对于障碍物附近，可以增大采样稠密度来提升路线图的有效性，或者可以通过基于特定概率函数进行采样构建路线图的简单的做法是选择直线，但不满足运动学特征，会出现运动方向突变，所以需要局部优化或者连接线采用其他曲线