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算法是随机从空间采样，对于障碍物附近，可以增大采样稠密度来提升路线图的有效性，或者可以通过基于特定概率函数进行采样
- 构建路线图的简单方法是选择直线，但不符合运动学特性，并且运动方向会发生突变，因此需要进行局部优化或使用其他曲线作为连接线.
文章出处登录后可见！
已经登录？立即刷新
