自動駕駛技術框架梳理
無人駕駛系統的核心可以概述為三個部分：感知（Perception），規劃（Planning）和控制（Control），這些部分的交互以及其與車輛硬件、其他車輛的交互可以用下圖表示：
感知是指無人駕駛系統從環境中收集信息并從中提取相關知識的能力。其中，環境感知（Environmental Perception）特指對于環境的場景理解能力，例如障礙物的位置，道路標志/標記的檢測，行人車輛的檢測等數據的語義分類。一般來說，定位（Localization）也是感知的一部分，定位是無人車確定其相對于環境的位置的能力。
規劃是無人車為了某一目標而作出一些有目的性的決策的過程，對于無人駕駛車輛而言，這個目標通常是指從出發地到達目的地，同時避免障礙物，并且不斷優化駕駛軌跡和行為以保證乘客的安全舒適。規劃層通常又被細分為任務規劃（Mission Planning），行為規劃（Behavioral Planning）和動作規劃（Motion Planning）三層。
最后，控制則是無人車精準地執行規劃好的動作的能力，這些動作來源于更高的層。?
01 感知
環境感知
為了確保無人車對環境的理解和把握，無人駕駛系統的環境感知部分通常需要獲取周圍環境的大量信息，具體來說包括：障礙物的位置，速度以及可能的行為，可行駛的區域，交通規則等等。無人車通常是通過融合激光雷達（Lidar），相機（Camera），毫米波雷達（Millimeter Wave Radar）等多種傳感器的數據來獲取這些信息，本節我們簡要地了解一下激光雷達和相機在無人車感知中的應用。
激光雷達是一類使用激光進行探測和測距的設備，它能夠每秒鐘向環境發送數百萬光脈沖，它的內部是一種旋轉的結構，這使得激光雷達能夠實時的建立起周圍環境的3維地圖。
通常來說，激光雷達以10Hz左右的速度對周圍環境進行旋轉掃描，其掃描一次的結果為密集的點構成的3維圖，每個點具備（x,y,z）信息，這個圖被稱為點云圖（Point Cloud Graph），如下圖所示，是使用Velodyne VLP-32c激光雷達建立的一個點云地圖：
激光雷達因其可靠性目前仍是無人駕駛系統中最重要的傳感器，然而，在現實使用中，激光雷達并不是完美的，往往存在點云過于稀疏，甚至丟失部分點的問題，對于不規則的物體表面，使用激光雷達很難辨別其模式，在諸如大雨天氣這類情況下，激光雷達也無法使用。
為了理解點云信息，通常來說，我們對點云數據進行兩步操作：分割（Segmentation）和分類（Classification）。其中，分割是為了將點云圖中離散的點聚類成若干個整體，而分類則是區分出這些整體屬于哪一個類別（比如說行人，車輛以及障礙物）。分割算法可以被分類如下幾類：
- 基于邊的方法，例如梯度過濾等；
- 基于區域的方法，這類方法使用區域特征對鄰近點進行聚類，聚類的依據是使用一些指定的標準（如歐幾里得距離，表面法線等），這類方法通常是先在點云中選取若干種子點（seed points），然后使用指定的標準從這些種子點出發對鄰近點進行聚類；
- 參數方法，這類方法使用預先定義的模型去擬合點云，常見的方法包括隨機樣本一致性方法（Random Sample Consensus，RANSAC ）和霍夫變換(Hough Transform，HT)；
- 基于屬性的方法，首先計算每個點的屬性，然后對屬性相關聯的點進行聚類的方法；
- 基于圖的方法；
- 基于機器學習的方法；
在完成了點云的目標分割以后，分割出來的目標需要被正確的分類，在這個環節，一般使用機器學習中的分類算法，如支持向量機（Support Vector Machine，SVM）對聚類的特征進行分類，最近幾年由于深度學習的發展，業界開始使用特別設計的卷積神經網絡（Convolutional Neural Network，CNN）對三維的點云聚類進行分類。
然而，不論是提取特征-SVM的方法還是原始點云-CNN的方法，由于激光雷達點云本身解析度低的原因，對于反射點稀疏的目標（比如說行人），基于點云的分類并不可靠，所以在實踐中，我們往往融合激光雷達和相機傳感器，利用相機的高分辨率來對目標進行分類，利用Lidar的可靠性對障礙物檢測和測距，融合兩者的優點完成環境感知。
在無人駕駛系統中，我們通常使用圖像視覺來完成道路的檢測和道路上目標的檢測。道路的檢測包含對道路線的檢測（Lane Detection），可行駛區域的檢測（Drivable Area Detection）；道路上路標的檢測包含對其他車輛的檢測（Vehicle Detection），行人檢測（Pedestrian Detection），交通標志和信號的檢測（Traffic Sign Detection）等所有交通參與者的檢測和分類。
車道線的檢測涉及兩個方面：第一是識別出車道線，對于彎曲的車道線，能夠計算出其曲率，第二是確定車輛自身相對于車道線的偏移（即無人車自身在車道線的哪個位置）。一種方法是抽取一些車道的特征，包括邊緣特征（通常是求梯度，如索貝爾算子），車道線的顏色特征等，使用多項式擬合我們認為可能是車道線的像素，然后基于多項式以及當前相機在車上掛載的位置確定前方車道線的曲率和車輛相對于車道的偏離。
可行駛區域的檢測目前的一種做法是采用深度神經網絡直接對場景進行分割，即通過訓練一個逐像素分類的深度神經網絡，完成對圖像中可行駛區域的切割。
交通參與者的檢測和分類目前主要依賴于深度學習模型，常用的模型包括兩類：
- 以RCNN為代表的基于Region Proposal的深度學習目標檢測算法（RCNN，SPP-NET，Fast-RCNN，Faster-RCNN等）；
- 以YOLO為代表的基于回歸方法的深度學習目標檢測算法（YOLO，SSD等）；?
02 定位
在無人車感知層面，定位的重要性不言而喻，無人車需要知道自己相對于環境的一個確切位置，這里的定位不能存在超過10cm的誤差，試想一下，如果我們的無人車定位誤差在30厘米，那么這將是一輛非常危險的無人車（無論是對行人還是乘客而言），因為無人駕駛的規劃和執行層并不知道它存在30厘米的誤差，它們仍然按照定位精準的前提來做出決策和控制，那么對某些情況作出的決策就是錯的，從而造成事故。由此可見，無人車需要高精度的定位。
目前使用最廣泛的無人車定位方法當屬融合全球定位系統（Global Positioning System，GPS）和慣性導航系統（Inertial Navigation System）定位方法，其中，GPS的定位精度在數十米到厘米級別之間，高精度的GPS傳感器價格也就相對昂貴。融合GPS/IMU的定位方法在GPS信號缺失，微弱的情況下無法做到高精度定位，如地下停車場，周圍均為高樓的市區等，因此只能適用于部分場景的無人駕駛任務。
地圖輔助類定位算法是另一類廣泛使用的無人車定位算法，同步定位與地圖構建（Simultaneous Localization And Mapping，SLAM）是這類算法的代表，SLAM的目標即構建地圖的同時使用該地圖進行定位，SLAM通過利用已經觀測到的環境特征確定當前車輛的位置以及當前觀測特征的位置。
這是一個利用以往的先驗和當前的觀測來估計當前位置的過程，實踐上我們通常使用貝葉斯濾波器（Bayesian filter）來完成，具體來說包括卡爾曼濾波（Kalman Filter），擴展卡爾曼濾波（Extended Kalman Filter）以及粒子濾波（Particle Filter）。
SLAM雖然是機器人定位領域的研究熱點，但是在實際無人車開發過程中使用SLAM定位卻存在問題，不同于機器人，無人車的運動是長距離的，大開放環境的。在長距離的運動中，隨著距離的增大，SLAM定位的偏差也會逐漸增大，從而造成定位失敗。
在實踐中，一種有效的無人車定位方法是改變原來SLAM中的掃描匹配類算法，具體來說，我們不再在定位的同時制圖，而是事先使用傳感器如激光雷達對區域構建點云地圖，通過程序和人工的處理將一部分“語義”添加到地圖中（例如車道線的具體標注，路網，紅綠燈的位置，當前路段的交通規則等等），這個包含了語義的地圖就是我們無人駕駛車的高精度地圖（HD Map）。
在實際定位的時候，使用當前激光雷達的掃描和事先構建的高精度地圖進行點云匹配，確定我們的無人車在地圖中的具體位置，這類方法被統稱為掃描匹配方法（Scan Matching），掃描匹配方法最常見的是迭代最近點法（Iterative Closest Point ，ICP），該方法基于當前掃描和目標掃描的距離度量來完成點云配準。
除此以外，正態分布變換（Normal Distributions Transform，NDT）也是進行點云配準的常用方法，它基于點云特征直方圖來實現配準。基于點云配準的定位方法也能實現10厘米以內的定位精度。
雖然點云配準能夠給出無人車相對于地圖的全局定位，但是這類方法過于依賴事先構建的高精度地圖，并且在開放的路段下仍然需要配合GPS定位使用，在場景相對單一的路段（如高速公路），使用GPS加點云匹配的方法相對來說成本過高。?
03 規劃
任務規劃
無人駕駛規劃系統的分層結構設計源于2007年舉辦的DAPRA城市挑戰賽，在比賽中多數參賽隊都將無人車的規劃模塊分為三層設計：任務規劃，行為規劃和動作規劃，其中，任務規劃通常也被稱為路徑規劃或者路由規劃（Route Planning），其負責相對頂層的路徑規劃，例如起點到終點的路徑選擇。
我們可以把我們當前的道路系統處理成有向網絡圖（Directed Graph Network），這個有向網絡圖能夠表示道路和道路之間的連接情況，通行規則，道路的路寬等各種信息，其本質上就是我們前面的定位小節中提到的高精度地圖的“語義”部分，這個有向網絡圖被稱為路網圖（Route Network Graph），如下圖所示：
這樣的路網圖中的每一個有向邊都是帶權重的，那么，無人車的路徑規劃問題，就變成了在路網圖中，為了讓車輛達到某個目標（通常來說是從A地到B地），基于某種方法選取最優（即損失最小）的路徑的過程，那么問題就變成了一個有向圖搜索問題，傳統的算法如迪科斯徹算法（Dijkstra’s Algorithm）和A*算法（A* Algorithm）主要用于計算離散圖的最優路徑搜索，被用于搜索路網圖中損失最小的路徑。
行為規劃
行為規劃有時也被稱為決策制定（Decision Maker），主要的任務是按照任務規劃的目標和當前的局部情況（其他的車輛和行人的位置和行為，當前的交通規則等），作出下一步無人車應該執行的決策，可以把這一層理解為車輛的副駕駛，他依據目標和當前的交通情況指揮駕駛員是跟車還是超車，是停車等行人通過還是繞過行人等等。
行為規劃的一種方法是使用包含大量動作短語的復雜有限狀態機（Finite State Machine，FSM）來實現，有限狀態機從一個基礎狀態出發，將根據不同的駕駛場景跳轉到不同的動作狀態，將動作短語傳遞給下層的動作規劃層，下圖是一個簡單的有限狀態機：
如上圖所示，每個狀態都是對車輛動作的決策，狀態和狀態之間存在一定的跳轉條件，某些狀態可以自循環（比如上圖中的循跡狀態和等待狀態）。雖然是目前無人車上采用的主流行為決策方法，有限狀態機仍然存在著很大的局限性：首先，要實現復雜的行為決策，需要人工設計大量的狀態；車輛有可能陷入有限狀態機沒有考慮過的狀態；如果有限狀態機沒有設計死鎖保護，車輛甚至可能陷入某種死鎖。
動作規劃
通過規劃一系列的動作以達到某種目的（比如說規避障礙物）的處理過程被稱為動作規劃。通常來說，考量動作規劃算法的性能通常使用兩個指標：計算效率（Computational Efficiency）和完整性（Completeness），所謂計算效率，即完成一次動作規劃的處理效率，動作規劃算法的計算效率在很大程度上取決于配置空間（Configuration Space），如果一個動作規劃算法能夠在問題有解的情況下在有限時間內返回一個解，并且能夠在無解的情況下返回無解，那么我們稱該動作規劃算法是完整的。
配置空間：一個定義了機器人所有可能配置的集合，它定義了機器人所能夠運動的維度，最簡單的二維離散問題，那么配置空間就是[x, y]，無人車的配置空間可以非常復雜，這取決于所使用的運動規劃算法。
在引入了配置空間的概念以后，那么無人車的動作規劃就變成了：在給定一個初始配置（Start Configuration），一個目標配置（Goal Configuration）以及若干的約束條件（Constraint）的情況下，在配置空間中找出一系列的動作到達目標配置，這些動作的執行結果就是將無人車從初始配置轉移至目標配置，同時滿足約束條件。
在無人車這個應用場景中，初始配置通常是無人車的當前狀態（當前的位置，速度和角速度等），目標配置則來源于動作規劃的上一層——行為規劃層，而約束條件則是車輛的運動限制（最大轉角幅度，最大加速度等）。
顯然，在高維度的配置空間來動作規劃的計算量是非常巨大的，為了確保規劃算法的完整性，我們不得不搜索幾乎所有的可能路徑，這就形成了連續動作規劃中的“維度災難”問題。目前動作規劃中解決該問題的核心理念是將連續空間模型轉換成離散模型，具體的方法可以歸納為兩類：組合規劃方法（Combinatorial Planning）和基于采樣的規劃方法（Sampling-Based Planning）。
運動規劃的組合方法通過連續的配置空間找到路徑，而無需借助近似值。由于這個屬性，它們可以被稱為精確算法。組合方法通過對規劃問題建立離散表示來找到完整的解，如在Darpa城市挑戰賽（Darpa Urban Challenge）中，CMU的無人車BOSS所使用的動作規劃算法，他們首先使用路徑規劃器生成備選的路徑和目標點（這些路徑和目標點事融合動力學可達的），然后通過優化算法選擇最優的路徑。
另一種離散化的方法是網格分解方法（Grid Decomposition Approaches），在將配置空間網格化以后我們通常能夠使用離散圖搜索算法（如A*）找到一條優化路徑。
基于采樣的方法由于其概率完整性而被廣泛使用，最常見的算法如PRM（Probabilistic Roadmaps），RRT（Rapidly-Exploring Random Tree），FMT（Fast-Marching Trees），在無人車的應用中，狀態采樣方法需要考慮兩個狀態的控制約束，同時還需要一個能夠有效地查詢采樣狀態和父狀態是否可達的方法。后文我們將詳細介紹State-Lattice Planners，一種基于采樣的運動規劃算法。
04 控制
控制層作為無人車系統的最底層，其任務是將我們規劃好的動作實現，所以控制模塊的評價指標即為控制的精準度。控制系統內部會存在測量，控制器通過比較車輛的測量和我們預期的狀態輸出控制動作，這一過程被稱為反饋控制（Feedback Control）。
反饋控制被廣泛的應用于自動化控制領域，其中最典型的反饋控制器當屬PID控制器（Proportional-Integral-Derivative Controller），PID控制器的控制原理是基于一個單純的誤差信號，這個誤差信號由三項構成：誤差的比例（Proportion），誤差的積分（Integral）和誤差的微分（Derivative）。
PID控制因其實現簡單，性能穩定到目前仍然是工業界最廣泛使用的控制器，但是作為純反饋控制器，PID控制器在無人車控制中卻存在一定的問題：PID控制器是單純基于當前誤差反饋的，由于制動機構的延遲性，會給我們的控制本身帶來延遲，而PID由于內部不存在系統模型，故PID不能對延遲建模，為了解決這一問題，我們引入基于模型預測的控制方法。
- 預測模型：基于當前的狀態和控制輸入預測未來一段時間的狀態的模型，在無人車系統中，通常是指車輛的運動學/動力學模型；
- 反饋校正：對模型施加了反饋校正的過程，使預測控制具有很強的抗擾動和克服系統不確定性的能力。
- 滾動優化：滾動地優化控制序列，以得到和參考軌跡最接近的預測序列。
- 參考軌跡：即設定的軌跡。
下圖表示模型預測控制的基本結構，由于模型預測控制基于運動模型進行優化，在PID控制中面臨的控制延時問題可以再建立模型考慮進去，所以模型預測控制在無人車控制中具有很高的應用價值。
05 結語
在本結我們概述了無人駕駛系統的基本結構，無人駕駛軟件系統通常被劃分為三層：感知，規劃和控制。從某種程度上而言，無人車在這種分層體系下就可以看作是一個“載人機器人”，其中，感知具體包括環境感知和定位，近年來深度學習的突破，使得基于圖像和深度學習的感知技術在環境感知中發揮了越來越重要的作用，借助人工智能，我們已經不再局限于感知障礙物，而逐漸變成理解障礙物是什么，理解場景，甚至預測目標障礙物的行為，機器學習和深度學習的內容我們將在后面兩章詳細了解。
在實際的無人車感知中，我們通常需要融合激光雷達，相機和毫米波雷達等多種測量，這里涉及到的如卡爾曼濾波，擴展卡爾曼濾波等融合算法以及激光雷達。
無人車和機器人的定位方法眾多，目前主流的方法一是使用GPS+慣性導航系統融合的方法，二是基于Lidar點云掃描匹配的方法，將重點介紹ICP，NDT等基于點云匹配的算法。
規劃模塊內部也被分成三層：任務規劃（也被稱為路徑規劃），行為規劃和動作規劃，后文會介紹基于路網和離散路徑搜索算法的任務規劃方法，在行為規劃中，我們將重點介紹有限狀態機在行為決策中的應用，在動作規劃算法層，重點介紹基于采樣的規劃方法。
無人車的控制模塊我們往往會使用基于模型預測的控制方法，但是在了解模型預測控制算法之前，作為對基礎反饋控制的了解，我們前面了解了PID控制器。接著我們學習兩類最簡單的車輛模型——運動學自行車模型和動力學自行車模型，最后，我們介紹模型預測控制。
雖然將無人車理解為機器人并且使用機器人開發的思維處理無人車系統是目前工業界的共識，但是也不乏一些單純使用人工智能或者是智能體來完成無人駕駛的案例。其中基于深度學習的端到端無人駕駛和基于強化學習的駕駛智能體是目前的研究熱點。
