无人驾驶的基本算法及简单介绍

更多腾讯海量技术文章，请关注云加社区：https://cloud.tencent.com/developer/column

作者：人工智能的秘密

摘要

本文以日本无人驾驶开源软件Autoware为参考，汇总分析了无人驾驶所涉及的基本算法，最后给出了在一些典型数据集上测试的效果。

介绍

本文将自动驾驶算法部分分成以下三个部分：场景识别、路径规划及车辆控制。每一类别都是由多种算法组成的。例如场景识别需要定位，物体检测及追踪算法。路径规划通常由任务、运动规划组成，车辆控制则对应路径跟随。下图1，显示了算法基本的控制及数据流。接下来本文将按照下图来组织文章结构，顺序介绍自动驾驶平台上的相关算法。

定位

定位是自动驾驶中最基本及重要的问题之一。尤其是在城市道路上，定位的精确度决定了自动驾驶的可靠性。Autoware采用Normal Distribution Transform(NDT)配准算法[1]。为了进一步提高精度，Autoware又采用了[2]中的方法，并配合高质量的3D Lidar传感器及3D高精地图实现了厘米级的定位结果。通过上书文献，本文猜测Autoware采用NDT算法有两大原因：

该算法可以被应用到3D场景中

该算法的时间复杂度与地图大小无关（点云中点的个数）

定位也是构建3D地图的关键性技术。因为3D雷达传感器实时产生3D点云数据，如果无人车定位准确的话，那么在每经过一次扫描，一份3D地图就能够被创建并更新。最近autoware又增加了些定位方法如：gnss、icp等。

目标检测

一旦定位到无人车，下一步就是检测物体，比如车辆、行人及交通信号灯来避免产生交通事故及触犯交通规则。Autoware均能实现上述要求，但是本文重点关注移动物体（车辆、行人）的检测。Autoware采用的是Deformable Part Models(DPM)算法来识别车辆及行人[3]。

DPM算法由Felzenszwalb于2008年提出，是一种基于部件的检测方法，对目标的形变具有很强的鲁棒性。目前DPM已成为众多分类、分割、姿态估计等算法的核心部分，Felzenszwalb本人也因此被VOC授予”终身成就奖”。该算法连续几年获得VOC检测冠军。 除了使用图像处理技术，autoware也使用了基于欧式距离聚类的技术对3D点云数据进行分析并检测物体。点云聚类是为了获得无人车与物体直接的聚类而不是分类，距离信息可以被用作图像处理之后的物体跟踪。这种根据多种传感器的数据结合的方法被称作传感器融合技术。 其他的关于道路检测、交通信号灯识别就基本上是调用的opencv库了。

目标跟踪

由于前面提到的物体检测是对图像及点云数据每一帧的处理结果，为了接下来能预测物体的轨迹（任务、运动规划需要），需要协同时间序列上其他帧的信息。Autoware使用了两种算法来解决追踪问题。第一个是卡尔曼滤波，该算法有一个线性假设前提：无人车必须得匀速行驶[4]。该算法时间复杂度很低、满足实时性要求。第二个是粒子滤波，该方法是为了弥补卡尔曼滤波的不足的，因为可以应用到非线性场景[5]。 Autoware主要根据具体给定的场景来使用这两种算法。

投影与重投影

Autoware实现的场景识别是由摄像头及雷达传感器结合的传感器融合技术支持的。通过校准摄像头及雷达来获得传感器融合技术的外来参数，autoware将3D点云信息投射到图像上从而获得了图像的深度信息并将目标检测的密集区域滤除。目标检测的结果也可重投影到3D点云上。这种投影与重投影比较简单，只会涉及些普通的投射变换。

任务规划

Autoware仅仅提供了一个基本的任务规划策略。在非结构化场景中，比如说停车场，autoware提供了一个A∗算法用来寻找到达目的地的最短路径[6-7]。在结构化的环境中，采用共形时空栅格法[8]。

运动规划

Autoware实现的运动规划是半自治的。Autoware实现了基于交通规则机制的自动分配路线轨迹，比如说：换道、并道、通过等。在更复杂的情境下，例如停车或从操作失误中恢复，驾驶员可以对路径做出选择。Autoware提供的任务规划基本策略是如果在巡航道路上行驶，全程由商业化导航应用来接管车辆，一旦无人车需要超车或者靠近一个转弯路口才规划变道任务。

路径跟随

路径跟随就是控制无人车沿着motion planning生成的路径行驶。Autoware使用了Pure Pursuit算法[9]。

性能需求及比较

本节将汇总下上述任务的时间复杂度。在配备有Intel CPUs与Nvidia GPUs的计算机上，如果搜索区域比较大的话，A∗算法耗时最长，需要几秒甚至更多。这些都能通过并行计算使得算法运行更快，但是这并不重要，因为A∗算法通常用在mission planning中，对实时性要求不高，在需要的时候才会使用该算法。但是有些任务比如：motion planning、object detection and tracking对实时性的要求就很高。下面我们基于KITTI数据集看看一些业界领先水平的方法：

目标检测2D-car

指标说明：

数据：7481 training images and 7518 test images, 80.256 labeled objects

评价指标： Easy、Moderate、Hard这三个难易程度是根据图片的识别难度来划分的

目标检测3D-car

目标检测bird’s eye-car

视觉里程估计

指标说明：

数据：由22个立体图像序列组成，保存为png格式：我们提供了训练序列的11个序列（00-10）和训练序列的11个序列（11-21），其中训练序列有ground truth,测试序列没有。

Translation,Rotation这里计算所有给定长度的所有可能子序列的平移旋转误差。

追踪-car

指标说明：

数据集由 21 训练序列和 29测试序列组成，虽然训练集中标定了8种类别的目标，但是测试结果只按照行人与汽车跟踪来打分。

MOTA:目标跟踪准确度，MOTP:目标跟踪精确度，MT:在整个序列中超过80%的视频帧被跟踪的轨迹数，ML:视频中低于20%的视频帧被跟踪的轨迹数。等等

道路检测-urban

Reference

[1] Biber P, Strasser W. The normal distributions transform: a new approach to laser scan matching[C]// Ieee/rsj International Conference on Intelligent Robots and Systems. IEEE, 2003:2743-2748 vol.3.

[2] Magnusson M, Lilienthal A, Duckett T. Scan registration for autonomous mining vehicles using 3D-NDT[J]. Journal of Field Robotics, 2007, 24(10):803–827.

[3] Felzenszwalb P F, Girshick R B, Mcallester D, et al. Object Detection with Discriminatively Trained Part-Based Models[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 47(2):6-7.

[4] Kalman R E. A New Approach to Linear Filtering and Prediction Problems[J]. Journal of Basic Engineering Transactions, 1960, 82:35-45.

[5] Arulampalam M S, Maskell S, Gordon N, et al. A Tutorial on Particule Filters for Online NonLinear/Non-Gaussian Bayesian Tracking[J]. IEEE Transactions on Signal Processing, 2001, 50(2):174-188.

[6] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science & Cybernetics, 2007, 4(2):100-107.

[7] Pivtoraiko M, Knepper R A, Kelly A. Differentially constrained mobile robot motion planning in state lattices[J]. Journal of Field Robotics, 2009, 26(3):308-333.

[8] Pivtoraiko M, Knepper R A, Kelly A. Differentially constrained mobile robot motion planning in state lattices. Journal of Field Robotics (JFR), 26(3), 308-333[J]. Journal of Field Robotics, 2009, 26(3):308-333.

[9] Coulter R C. Implementation of the Pure Pursuit Path Tracking Algorithm[J]. Implementation of the Pure Pursuit Path Tracking Algorithm, 1992.