自动驾驶中的路径规划

　　通常认为自动驾驶系统的四大模块分别是感知、定位、规划、控制，其中规划是根据各类传感器采集的车辆周围的环境和位置、以及当前车辆状态等信息来规划车辆行驶轨迹。
　　这里有一个常见的道德问题，如下图所示。如果车辆没有刹车，我们必须选择牺牲谁。虽然不太可能，但这个话题让我们想知道如果自动驾驶汽车必须自己做出决定，他会如何做。
　　01 .
　　预测
　　第一步是预测车辆周边环境的每个元素在未来几秒钟内会做什么，包括周边机动车辆、行人的状态，交通标志状态等。对于预测周边环境，通常有几种方法：
　　1. 对于每种可能的情况（汇入高速公路、交叉路口等），为车辆的所有可能轨迹建模。
　　2. 根据当前的观察，使用机器学习建立 与训练数据的 相似性，从而将其与轨迹相关联。
　　在对轨迹进行建模时，必须考虑周边车辆的所有可能动作。以汇入高速为例。
　　进入高速公路
　　周边车辆可能的动作如下：  保持在它的车道上，这意味着：
　　- 加速，
　　- 减速，让我们在他面前通过，
　　- 保持匀速，忽略我们  改变车道，这将使我们更容易。
　　所以我们有四种可能的情况来定义汇入高速公路。
　　自动驾驶系统通过对车辆传感器的实时输入来计算主路上车辆实时的位置以及速度，从而决定是否换挡和变道。在这个案例中有四种可能的场景，因此具有多模式分布，这意味着每个场景都有一个随着主车道车辆状态而变化的概率。
　　该技术实现了轨迹的可行性，但是它只关注什么是可能的，而不是过去已经做了什么。
　　数据驱动(机器学习)方法
　　像其他机器学习算法一样，我们定义了两个阶段，一个训练阶段和一个预测阶段。
　　训练阶段收集有关车辆历史的大量数据并从这些数据中学习。我们可以让数百辆汽车在十字路口完成数百种不同的行为。
　　每个集群实际上是车辆可以遵循的典型轨迹。这种技术的优点是依赖于数据，因此依赖于过去的场景。我们驾驶和收集数据的次数越多，我们对行为的估计就越精确。
　　这两种方法非常不同，实际上反映了自动驾驶汽车行业的现实。有些人依赖于具有数学预测的确定性案例，而另一些人则依赖于使用人工智能的统计数据。公司的这种选择更广泛地扩展到许多问题，例如使用 LiDAR 的感知与使用相机的感知。
　　02 .
　　做决策
　　一旦对环境的未来进行了估计，就可以做出决策。检测到行人如何刹车？如何加速或变道？
　　但是我们首先要做的事是环境分类。无论我们是在高速公路上还是在停车场，选择都不一样。生成轨迹时会考虑几个标准，特别是安全性、可行性、效率和合法性。还可以考虑其他变量，例如乘客的舒适度。  决策方法——有限状态机
　　第一种可以使用的决策方法是有限状态机。其原理是根据情况定义汽车的可能状态。在高速公路上，汽车的状态可能是留在车道上，向左变道，或向右变道。根据交通状况，我们改变状态，例如超车。
　　状态的选择通常使用成本函数进行。对于每个可能的场景，我们计算独立成本（到障碍物的距离、合法性……），并将它们相加。成本最低的方案获胜。
　　在这里，我们定义什么是重要的。我们不能做不可能或危险的动作。
　　Total_Cost = Feasibility_Cost * 5+ Security_Cost * 4 + Legality_Cost * 3+ Comfort_Cost * 2 + Speed_Cost * 1
　　速度成本函数
　　在速度成本函数中，我们不希望车速低于最低限速或超过最大限速。因此，我们根据速度定义一个递减的成本，然后在速度限制之后达到最大值。
　　在谈到自动驾驶时，决策是一个非常微妙的话题。我们必须考虑到当前的情况，并从这一点上决定一切可以做的事情。然后我们必须权衡每种可能性的利弊，最后选择最佳解决方案。  轨迹生成
　　在这一步中，有必要使用一个不同于笛卡尔坐标系的坐标系。因为笛卡尔坐标系考虑了尺寸（x；y），但如果我们想要找到与道路相关的方向。Frenet 坐标包含两个轴，一个 s 轴表示相对于轨道的前进，而 ad 轴表示到车道中心的距离。这个标记是我们用来估计我们的轨迹是否偏离车道中心或者车辆是否在我们前面或后面的标记。
　　Frenet与笛卡尔坐标
　　当我们决定超车时，算法会生成多个决策轨迹，并根据可行性、安全性、合法性、效率、舒适性等标准选择最佳轨迹……
　　为了生成这个轨迹，我们创建了一个通过航路点的五级多项式。航路点是包含 3 个维度的路径点：
　　S：纵向距离；
　　D：横向距离；
　　T：必须通过该点的时刻，目标速度；
　　轨迹是通过所有这些点的曲线。这些点位于空间和时间上。它们告诉我们何时移动到特定 (x;y) 位置以及移动速度有多快。如果您想在人行横道处刹车，我们会创建到人行横道的点，并设置一个递减的速度，使其达到停止区域的点的速度。  路径规划
　　刚刚研究了低层轨迹的生成。更高的等级呢？如何决定走哪条街？还有哪些其他路径规划算法？
　　有几个算法系列来规划从起点到终点的路径。在这些算法中，我们将世界视为一个包含障碍、起点和目标的网格。
　　下面主要关注基于采样的算法和强化学习算法。  基于采样的算法
　　这个算法使用比较多，因为它在计算时间方面非常有效，另外其又分离散型和连续型。
　　连续环境与离散环境
　　在离散规划器中，我们将世界视为一个网格。可以使用广度优先搜索、Dijkstra、A*等算法快速地找到最短路径，而不必探索整个地图。  A*
　　在非常流行的A* (A-star)算法中，我们只使用启发式函数探索地图的一部分。在地图上的每个点上，我们都标明了到目标的距离。A*不会系统地探索每一条可能的路径，而是只选择探索那些能让我们更接近目标的路径。
　　Dijkstra vs A*
　　A* 是 Dijkstra 算法的一种变体，它专注于通过做最少的工作来寻找到特定位置的最佳路径。因此它在自动驾驶中非常有效。上图展示了 A* 的运行情况。
　　在连续规划器中，主要使用的算法包括混合 A*、快速探索随机树 ( RRT ) 等算法。  混合 A*
　　Hybrid A * 试图通过分解运动来接近连续世界的现实。我们不是从一个方格到另一个方格，而是尝试几个短动作——总是选择让我们更接近目标的动作。这意味着该算法同时是离散和连续的。生成的轨迹也可以更加流畅，因为它们考虑了最大转向角、物理轨迹……
　　混合 A*  强化学习
　　一种越来越流行的方法是强化学习。这种机器学习技术包括从经验中学习。如果我们想右转，我们让汽车做一个随机选择，如果它是好的，它会得到一个积极的奖励，如果不是，一个消极的奖励。在训练过程中，汽车能够了解是什么导致了积极的奖励，并重现了它。这项技术是当今最接近人类学习的技术。
　　03 .
　　结论
　　自主导航是一个令人兴奋的主题。我们用直觉和眼睛驾驶，尊重道路规则。要在计算机中重现这一点，我们必须看到、定位自己、预测其他车辆的行为，最后综合法律或乘客舒适度等约束条件做出决定。在机器后面，一个人告诉我们在某些情况下我们必须赋予哪些行动特权。机器只复制它所教的内容。这个主题为大量的研究和实验工作留下了空间。它将使汽车达到真正的L5级自动驾驶。