【自动驾驶决策规划】PRM算法

1 基于采样的路径规划方法

路径搜索常用方式之一是基于网格的的方法&＃xff08;grid-based method&＃xff09;&＃xff0c;如A*算法&＃xff0c;但基于网格的方法复杂度较高&＃xff0c;与求解空间的维度相关&＃xff0c;且得到的路径比较僵硬&＃xff0c;对于车辆或移动机器人来说都不是很友好。

另外一种路径规划是基于采样的方法&＃xff08;sampling method&＃xff09;&＃xff0c;包括以下模块&＃xff1a;

• 随机或确定性选择函数&＃xff0c;在采样空间确定点
• 采样评估函数&＃xff0c;来选择合适采样点
• 距离函数&＃xff0c;确定待扩展点与当前之间的距离

这些模块可以构建出图或树结构来探索可行域内的可行轨迹。采样方法不是以最优为目的&＃xff0c;只能得到近似最优解&＃xff0c;好处是在解空间内探索效率较高&＃xff0c;能快速得到满足要求的可行解

典型的基于采样的方法包括RRTs&＃xff08;Rapidly Exploring Random Trees&＃xff09;和PRMs&＃xff08;Probabilistic roadmaps&＃xff09;&＃xff0c;RRT更适合为单体轨迹规划提供有效的轨迹&＃xff0c;PRM更适合为多体轨迹规划提供路线图&＃xff08;roadmap graph&＃xff09;

2 PRM过程

PRM算法是通过对空间进行大量采样来构建路线图&＃xff0c;用于后续的特定查询。路线图是无向连接图&＃xff0c;车辆或机器人可以路线图上由任意一点移动到其他点。点与点连接线最简单的就是直线。路线图构建好之后可以采用经典的A*算法来搜索路径。

PRM算法构建路线图过程如下所示。

3 PRM一些细节

• 由于PRM算法是随机从空间采样&＃xff0c;对于障碍物附近&＃xff0c;可以增大采样稠密度来提升路线图的有效性&＃xff0c;或者可以通过基于特定概率函数进行采样
• 构建路线图的简单的做法是选择直线&＃xff0c;但不满足运动学特征&＃xff0c;会出现运动方向突变&＃xff0c;所以需要局部优化或者连接线采用其他曲线