無人駕駛的基本演算法及簡單介紹

更多騰訊海量技術文章，請關注云加社區：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.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！