第四章、移动机器人的路径规划6
一、概率路线图
用于在更多起点和更多目标点之间进行路径搜索的方法。
步骤：
1.学习阶段
构建*空间的路线图或无向图
路线图最初是一个空集，通过下面方式构建：
从空闲空间中随机选择包含在映射中的配置qrand
找到扩展映射所需的节点Qn，这些节点可以通过选择K个最近邻节点(Qn)或所有到qrand的距离小于某个预定义参数D的近邻节点来找到。如下图。
在第一次或者接下来几次寻找，不会找到节点。所有从qrand到完全位于空闲空间的节点Qn的简单连接都包含在映射中。重复此过程，直到映射包含所需的N个节点。
2.寻找阶段
将当前的起始点和目标点连接到图上，利用图路径搜索算法寻找最优路径。
在路径搜索阶段，需要的起始点和目标点通过*空间与来自地图的尽可能近的节点连接。
然后使用路径搜索算法来寻找从起点到终点的路径。
第一步、第二步不需要分开执行。
说明：
该方法对于多*度机器人是非常有效的。
在两个区域之间找到一条狭窄通道的路径可能会有问题。这个问题可以通过桥接测试添加额外的节点来解决，在某条直线上选择三个相邻的随机点，如果最外面的点与障碍物发生碰撞，而中间的点没有碰撞，则中间的点作为一个节点包含在地图中。如下图