自动驾驶威廉希尔官方网站 计算分析以及路径规划的问题

导读

环境模型（不同于环境理解），再加上路径搜索就构成了路径规划。通常，环境模型有三大类，分别是栅格法、可视图法、自由空间法。路径搜索的算法比较多，如：Dijkstra、Floyd-Warshall、A+算法、层次法、动作行为法、势场域法、栅格法、模糊逻辑法、拓扑法、惩罚函数法、遗传算法、interwetten与威廉的赔率体系 退火法、蚁群法和神经网络法等。

无人驾驶汽车的威廉希尔官方网站 路线已经确定，那就是轮式机器人的威廉希尔官方网站 路线。轮式机器人威廉希尔官方网站 完全适用于无人驾驶汽车，这已经从2007年的DARPA大赛一直到最近谷歌、福特、百度等的无人驾驶试验汽车，有了超过十年的验证。目前所有无人驾驶汽车基础算法的研究都源自机器人威廉希尔官方网站 。

无人驾驶汽车需要解决三个问题：即环境感知及实时定位，计算分析以及路径规划，还有就是控制执行。今天我们来讨论一下计算分析以及路径规划的问题。

首先我们来说明一下以下三个概念：路径规划、避障规划、轨迹规划。

路径规划通常指全局的路径规划，也可以叫全局导航规划，从出发点到目标点之间的纯几何路径规划，无关时间序列，无关车辆动力学。

避障规划又叫局部路径规划，又可叫动态路径规划，也可以叫即时导航规划。主要是探测障碍物，并对障碍物的移动轨迹跟踪（Moving Object Detection and Tracking，一般缩写为MODAT），做出下一步可能位置的推算，最终绘制出一幅包含现存碰撞风险和潜在碰撞风险的障碍物地图，这个潜在的风险提示是100毫秒级，未来需要进一步提高，这对传感器、算法的效率和处理器的运算能力都是极大的挑战，避障规划不仅考虑空间还考虑时间序列，在复杂的市区运算量惊人，可能超过30TFLOPS，这是无人车难度最高的环节。未来还要加入V2X地图，避障规划会更复杂，加入V2X地图，基本可确保无人车不会发生任何形式的主动碰撞。

轨迹规划则源自机器人研究，通常是说机械臂的路径规划。 在无人车领域，轨迹规划的定义感觉不统一。有人将避障规划与轨迹规划混淆了。轨迹规划应该是在路径规划和避障规划的基础上，考虑时间序列和车辆动力学对车辆运行轨迹的规划，主要是车纵向加速度和车横向角速度的设定。将设定交给执行系统，转向、油门、刹车。如果有主动悬挂，那么轨迹规划可能还要考虑地形因素。

三大规划是无人车最复杂的部分，算法多不胜数，让人眼花缭乱，这也是百度、谷歌和苹果等科技巨头要切入无人车领域的主要原因，这些科技巨头最擅长的就是算法的优化整合。当然传统车厂如福特和丰田，拥有对车辆动力学的绝对优势，在此领域实力并不比科技巨头要差，尤其是丰田，从开源SLAM到KITTI，软件实力丝毫不次于谷歌。

全局型路径规划不算复杂，前提是有拓扑级地图，这对地图厂家来说很容易的。对于非地图厂家是有点麻烦的，不过只能算小麻烦。所以我们重点讲避障规划，避障规划的前提是对周围环境有深刻的理解，有一个非常完善实时的的环境理解。

有了环境模型（不同于环境理解），再加上路径搜索就构成了路径规划。通常，环境模型有三大类，分别是栅格法、可视图法、自由空间法。路径搜索的算法就多了，Dijkstra、Floyd-Warshall、A+算法、层次法、动作行为法、势场域法、栅格法、模糊逻辑法、拓扑法、惩罚函数法、遗传算法、模拟退火法、蚁群法和神经网络法等。需要指出的是，大多数算法都是诞生于六十年代。

这还仅仅是2D层面的，3D层面的将更加复杂。每一种算法下面还有再细分的算法，让人看了头晕目眩。因为很少有文献说3D路径算法，我们就多说几句，3D路径算法大体可以分为五类，取样算法（Sampling）、节点算法（Node）、工程数学模型算法（Mathematics）、仿生学算法（Bioinspired)、混合算法（MultiFusion）。以取样型算法为例，下面可以再分主动型与被动型。主动型下面还可以再细分。

1.取样型3D路径规划

2.节点型算法下面再分三大类

3.环境建模方面，栅格法是公认最成熟的算法，栅格法应该也是安全系数最高的算法，也是最耗运算资源的算法。不过无人车要考虑安全，安全是第一位的，成本是第二位的，同时有英伟达和英特尔这样的半导体巨人在不断提高运算性能，运算资源不用过多考虑。

4.栅格法把工作空间分割成规则而均匀的含二值信息的栅格。在机器人移动的过程中，栅格的尺寸和位置不变。二值信息分别表示该栅格处是否有障碍，没有障碍的栅格称为自由栅格，否则为障碍栅格。栅格的尺寸通常和机器人的基本移动步长相适应，故机器人移动转化成从一个自由栅格移动到下一个自由栅格，机器人移动的路长对应于机器人爬过的栅格数。栅格法直观且建模相对较容易，因此得到了广泛的应用。

5.另外两种算法，可视图法和自由空间法和栅格法相比的优点是比较灵活，对运算资源消耗少。缺点很明显，障碍物多少与算法复杂程度成正比，算法太复杂时可靠性就降低，同时不太适合动态环境，要求运动速度变化尽量小。栅格法的缺点是如果分辨率高，对运算资源和内存需求较高。显然，可视图法和自由空间法适合机器人，栅格法更适合无人车，这在业内差不多已经是定论。这和传感器也有部分关系，视觉系统难以适应太精细的格栅法，因为视觉系统的要做精细的定量边界分割是不可能的，而激光雷达非常适合栅格法。

路径搜索方面，典型的如Dijkstra （迪杰斯特拉）算法。

Dijkstra（迪杰斯特拉）算法是最短路算法的经典算法之一，由E.W.Dijkstra在1959年提出的。该算法适于计算道路权值均为非负的最短路径问题，可以给出图中某一节点到其他所有节点的最短路径，以思路清晰，搜索准确见长。相对的，由于输入为大型稀疏矩阵，又具有耗时长，占用空间大的缺点。

轨迹规划则研究的很少，因为大部分科技公司都没能力在车辆动力学领域一展拳脚。科技公司都将精力花在如何生成轨迹上，而对于生成的轨迹是否满足运动学约束、侧滑约束以及执行机构约束，即轨迹的可行性，研究相对较少。对于无人车这一受非完整性约束的系统，研究人员通常基于车体模型进行轨迹规划。按照车体模型的精确程度，轨迹规划方法可以进一步分为基于模型预测控制(Model predictive control, MPC) 以及基于几何轨线的规划方法。基于模型预测的无人车轨迹规划方法首先由 Kelly A和NagyB提出。

对于移动机器人来说，轨迹生成问题主要研究如何生成一系列动作，使得机器人由初始状态到达目标状态。对于无人车来说，其初始状态包括其二维坐标(x, y)、 航向角 ψ 以及曲率 κ。

实际情况远比这复杂，还需要建立大量的数学方程。良好的规划必须建立对周边环境，尤其是动态环境的深刻理解。这就是下面要阐述的自动驾驶核心威廉希尔官方网站 第三部分：MODAT。

感知、决策（路径规划）、定位都是基于传感器或软件系统的，这也是科技类厂家的强项，不过线控执行系统则是传统汽车产业（不一定是整车厂）的绝对强项，这也是科技类厂家注定无法独立造车的主要原因，无论是谷歌还是百度，都必须要与传统汽车产业联合，才能进军无人车领域。有机会我们说说线控执行。