自动驾驶实时路径规划算法简介（Local search局部搜索）

在上一节自动驾驶实时路径规划算法简介（RRT 和Lattice Planner）中介绍了

找到车辆要遵循的最佳几何路径有两个方法：

a） 通过增量采样或离散几何结构（即增量搜索）找到最佳的动作序列。

b） 从多个最终状态中找到最佳操作（即局部搜索）。

增量搜索我们在上一节（点击阅读自动驾驶实时路径规划算法简介（RRT 和Lattice Planner））介绍了。

接下来我们分享：

局部搜索

实时搜索整个图（什么是实时搜索点击自动驾驶实时路径规划算法简介（RRT 和Lattice Planner））并不总是有效的；因此，一些方法使用有限的视界，无论是在时间还是空间上。

在局部搜索级别，用于道路自动驾驶的最流行的技术可能是搜索空间包含某个几何曲线（例如回旋曲线或样条曲线）以及该曲线的几个横向位移。然后通过一个代价函数对每个候选路径进行评估，考虑到距离和时间成本、加速和碰撞检查。

横向位移产生的路径一般可分为两类：

（i）车辆作用空间的横向移动

（ii）车辆状态空间中的横向位移

下图展示出了相对比较：

在复杂的动态环境中，横向移动的轨迹可能无法很好地执行（Gu和Dolan，2012）。因为他不是朝着目标搜索整个状态空间，这样会在无限时间范围内需要大量的计算能力（用于构建状态空间）。Benenson等人提出的部分运动规划（Partial Motion Planning-PMP）可以使用。PMP使用短时间范围与RRT相结合，并利用不可避免碰撞状态（ICS）的概念（即无法避免碰撞的车辆状态定义）进行安全检查。不可避免的碰撞状态保证不会发生碰撞，但需要对车辆周围环境有充分的了解（Althoff等人，2011年），而PMP方法通常接近最佳状态保证（Kushleyev和khachev，2009年）。如下图所示，如果找到不可避免碰撞状态（ICS），则搜索替代路径，并且在每个时刻以RRT方式展开步骤节点。

总之，横向移动的轨迹和PMP方法都旨在找到适合车辆行驶的最佳下一个动作（就路径作为一个动作而言）。迂回轨迹在动作或状态空间中采样最终条件，而PMP方法使用RRT在有限的时间范围内进行规划。对于车道和道路边界以及其他交通参与者的运动而言，对状态空间进行采样的技术可能会导致平滑和安全的路径。这与PMP和对动作空间进行采样的技术相矛盾，这可能导致适应大量障碍物处理的路径不可行。

参考文献：

1，Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions -Christos Katrakazas a , Mohammed Quddus a, , Wen-Hua Chen b,1 , Lipika Deka a

2，Partial Motion Planning Framework for ReactivePlanning Within Dynamic Environments

3，Multi-layer occupancy grid mapping for autonomous vehicles navigation

文中部分图片版权归其所有

*未经准许严禁转载和摘录-加入我们的知识星球Vehicle可以下载以上参考资料。