從算法層解讀，自動駕駛的「軌跡規(guī)劃」是如何實現的？

車輛路徑規(guī)劃問題中路網模型、路徑規(guī)劃算法和交通信息的智能預測為關鍵點。

由于駕駛員的駕駛工作繁重，同時隨著汽車擁有量的增加，非職業(yè)駕駛員的數量增多，導致交通事故頻繁發(fā)生。如何提高汽車的主動安全性和交通安全性已成為急需解決的社會性問題。

?圖1 智能汽車示意圖

隨著計算機技術、電子技術、圖像處理等信息處理技術研究的發(fā)展，研究人員開始將各種先進的技術應用于汽車控制上，輔助駕駛員進行汽車的操縱控制。在這些汽車電子控制系統研究的基礎上，結合蓬勃發(fā)展的智能化信息處理技術，逐步產生了一個新興的交叉學科——車輛的自動駕駛(又稱為智能汽車)。未來實用化的智能汽車將最大限度地減少交通事故、提高運輸效率、減輕駕駛員操縱負擔，從而提高整個道路交通的安全性、機動性與汽車行駛的主動安全性。科技部于2001年已正式啟動實施了十五計劃中的國家科技攻關計劃重大項目“智能交通系統關鍵技術開發(fā)和示范工程” 來提高我國整個運輸系統的管理水平和服務水平，提高效率和安全性，車輛的自主駕駛是實現ITS(Intelligent Transport System,智能交通系統)的關鍵。

?圖2 智能交通系統示意圖

車輛自主駕駛系統從本質上講是一個智能控制機器，其研究內容大致可分為信息感知、行為決策及操縱控制三個子系統。路徑規(guī)劃是智能車輛導航和控制的基礎，是從軌跡決策的角度考慮的，可分為局部路徑規(guī)劃和全局路徑規(guī)劃。

全局路徑規(guī)劃的任務是根據全局地圖數據庫信息規(guī)劃出自起始點至目標點的一條無碰撞、可通過的路徑。目前正在研究的有準結構化道路環(huán)境多種約束條件下的路徑規(guī)劃技術，自然地形環(huán)境下的路徑規(guī)劃技術，以及重規(guī)劃技術等。由于全局路徑規(guī)劃所生成的路徑只能是從起始點到目標點的粗略路徑，并沒有考慮路徑的方向、寬度、曲率、道路交叉以及路障等細節(jié)信息，加之智能車輛在行駛過程中受局部環(huán)境和自身狀態(tài)的不確定性的影響，會遇到各種不可測的情況。因此，在智能車輛的行駛過程中，必須以局部環(huán)境信息和自身狀態(tài)信息為基礎，規(guī)劃出一段無碰撞的理想局部路徑，這就是局部路徑規(guī)劃。通常路徑規(guī)劃的方法有:空間搜索法、層次法、動作行為法、勢場域法、柵格法、模糊邏輯法和神經網絡法等。

汽車自動駕駛任務可以分為三層，如圖3所示，每層執(zhí)行不同任務，包括上層路徑規(guī)劃、中層行駛行為規(guī)劃和下層軌跡規(guī)劃。

?圖3 汽車自動駕駛任務

上層路徑規(guī)劃在已知電子地圖、路網以及宏觀交通信息等先驗信息下，根據某優(yōu)化目標得到兩點之間的最優(yōu)路徑，完成路徑規(guī)劃的傳感信息主要來自于GPS定位信息以及電子地圖。中層行駛行為規(guī)劃是指根據主車感興趣區(qū)域內道路、交通車等環(huán)境信息，決策出當前時刻滿足交通法規(guī)、結構化道路約束的最優(yōu)行駛行為，動態(tài)規(guī)劃的行駛行為序列組成宏觀路徑。行為規(guī)劃的傳感信息主要來自車載傳感器如雷達、照相機等，用以識別道路障礙、車道線、道路標識信息和交通信號燈信息等。下層軌跡規(guī)劃是指在當前時刻，以完成當前行車行為為目標，考慮周圍交通環(huán)境并滿足不同約束條件，根據最優(yōu)目標動態(tài)規(guī)劃決策出的最優(yōu)軌跡。同時，車輛的動力學約束也會在下層得到體現，下層軌跡規(guī)劃除了必要的外部環(huán)境信息外，還需要對主車狀態(tài)信息進行測量或估計。

車輛路徑規(guī)劃問題中的幾個關鍵點：路網模型、路徑規(guī)劃算法和交通信息的智能預測，涉及的方面較多，本文主要針對路徑規(guī)劃過程做簡單的探討。

一.問題引入

我們嘗試解決的問題是把一個游戲對象(game object)從出發(fā)點移動到目的地，如圖2所示。路徑搜索(Pathfinding)的目標是找到一條好的路徑——避免障礙物、敵人，并把代價(燃料，時間，距離，裝備，金錢等)最小化。運動(Movement)的目標是找到一條路徑并且沿著它行進,當游戲對象開始移動時，一個老練的路徑搜索器(pathfinder)外加一個瑣細的運動算法(movement algorithm)可以找到一條路徑，游戲對象將會沿著該路徑移動而忽略其它的一切。一個單純的運動系統(movement-only system)將不會搜索一條路徑(最初的“路徑”將被一條直線取代)，取而代之的是在每一個結點處僅采取一個步驟，即朝著某個方向行進一段距離，同時需要考慮周圍的障礙物環(huán)境避免碰撞的產生。顯然，同時使用路徑搜索(Pathfinding)和運動算法(movement algorithm)將會得到最好的效果。

移動一個簡單的物體(object)看起來是容易的，而路徑搜索是復雜的，為什么涉及到路徑搜索就產生麻煩了？考慮以下情況：

?圖4 避碰路徑規(guī)劃

物體(unit)最初位于地圖的底端并且嘗試向頂部移動，物體掃描的區(qū)域中(粉紅色部分)沒有任何東西顯示它不能向上移動，因此它持續(xù)向上移動。在靠近頂部時，它探測到一個障礙物然后改變移動方向，然后它沿著U形障礙物找到它的紅色的路徑。相反的，一個路徑搜索器(pathfinder)將會掃描一個更大的區(qū)域(淡藍色部分)，但是它能做到不讓物體(unit)走向凹形障礙物而找到一條更短的路徑(藍色路徑)。

針對以上情形，如圖5所示，可以擴展一個運動算法，用于對付上圖所示的障礙物，或者避免制造凹形障礙，或者把凹形出口標識為危險的(只有當目的地在里面時才進去)。比起一直等到最后一刻才發(fā)現問題，路徑搜索器能提前作出規(guī)劃，選擇一條更優(yōu)的運動路徑。

?圖5 避障優(yōu)化路徑規(guī)劃方法

二、問題描述

汽車軌跡規(guī)劃及智能決策是實現汽車智能化的關鍵技術之一，其主要任務是依據環(huán)境感知系統處理后的環(huán)境信號以及先驗地圖信息，在滿足汽車行駛諸多約束的前提下，以某性能指標最優(yōu)為目的，規(guī)劃出車輛的運動軌跡。

智能車的自動駕駛行為即是將車從起始位姿“搬運”到目標位姿，車輛的運動限制在路面上、同時其運動學及動力學模型使得其不能像空中的無人機一樣隨意調整航向角，因此，規(guī)劃的路徑除了考慮路程最短、無碰撞外還需要考慮車輛運動軌跡的可執(zhí)行性。

三.車輛路徑規(guī)劃算法

根據車輛導航系統的研究歷程, 車輛路徑規(guī)劃算法可分為靜態(tài)路徑規(guī)劃算法和動態(tài)路徑算法。靜態(tài)路徑規(guī)劃是以物理地理信息和交通規(guī)則等條件為約束來尋求最短路徑，靜態(tài)路徑規(guī)劃算法已日趨成熟, 相對比較簡單, 但對于實際的交通狀況來說,其應用意義不大。動態(tài)路徑規(guī)劃是在靜態(tài)路徑規(guī)劃的基礎上, 結合實時的交通信息對預先規(guī)劃好的最優(yōu)行車路線進行適時的調整直至到達目的地最終得到最優(yōu)路徑。下面介紹幾種常見的車輛路徑規(guī)劃算法。

1. Dijkstra算法

?圖6 Dijkstra算法示意圖

Dijkstra（迪杰斯特拉）算法是最短路算法的經典算法之一，由E.W.Dijkstra在1959年提出的。該算法適于計算道路權值均為非負的最短路徑問題，可以給出圖中某一節(jié)點到其他所有節(jié)點的最短路徑，以思路清晰,搜索準確見長。相對的，由于輸入為大型稀疏矩陣,又具有耗時長，占用空間大的缺點。其算法復雜度為O(n²)，n為節(jié)點個數。

2.Lee算法

Lee算法最早用于印刷電路和集成電路的路徑追蹤, 與Dijkstra算法相比更適合用于數據隨時變化的道路路徑規(guī)劃, 而且其運行代價要小于Dijkstra 算法。只要最佳路徑存在, 該算法就能夠找到最佳優(yōu)化路徑。Lee算法的復雜度很難表示, 而且對于多圖層的路徑規(guī)劃則需要很大的空間。

3. Floyd算法

Floyd算法是由Floyd于1962年提出的, 是一種計算圖中任意兩點間的最短距離的算法?？梢哉_處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包，Floyd-Warshall算法的時間復雜度為O(n³)，空間復雜度為O(n²)，n 為節(jié)點個數。與對每一節(jié)點作一次Dijkstra算法的時間復雜度相同，但是實際的運算效果比Dijkstra算法要好。

4.啟發(fā)式搜索算法——A* 算法

?圖7 A* 算法動態(tài)示意圖

啟發(fā)式搜索有很多的算法，如: 局部擇優(yōu)搜索法、最好優(yōu)先搜索法、A* 算法等。其中A* 算法是由Hart、Nilsson、Raphael等人首先提出的，算法通過引入估價函數，加快了搜索速度，提高了局部擇優(yōu)算法搜索的精度，從而得到廣泛的應用，是當前較為流行的最短路算法。A* 算法所占用的存儲空間少于Dijkstra算法。其時間復雜度為O(bd)，b為節(jié)點的平均出度數，d為從起點到終點的最短路的搜索深度。

5. 雙向搜索算法

雙向搜索算法由Dantzig提出的基本思想，Nicholson正式提出算法。該算法在從起點開始尋找最短路徑的同時也從終點開始向前進行路徑搜索,最佳效果是二者在中間點匯合，這樣可縮短搜索時間。但是如果終止規(guī)則不合適，該算法極有可能使搜索時間增加1倍，即兩個方向都搜索到最后才終止。

6. 蟻群算法

?圖8 蟻群算法示意圖

蟻群算法是由意大利學者M.Dorigo等于1991年提出的，它是一種隨機搜索算法, 是在對大自然中蟻群集體行為的研究基礎上總結歸納出的一種優(yōu)化算法，具有較強的魯棒性，而且易于與其他方法相結合，蟻群算法的算法復雜度要優(yōu)于Dijkstra算法。

此外, 還有實時啟發(fā)式搜索算法、基于分層路網的搜索算法、神經網絡、遺傳算法及模糊理論等，由于實際需求不同對算法的要求和側重點也會有所不用，所以也出現了許多以上算法的各種改進算法。大多數算法應用于求解車輛路徑規(guī)劃問題時都會存在一定的缺陷，所以目前的研究側重于利用多種算法融合來構造混合算法。

四.總結

目前, 投入市場應用的成熟車輛導航系統大多基于靜態(tài)的路徑規(guī)劃, 然而面對存在眾多不穩(wěn)定因素的交通現實, 用戶并不滿足于現有的系統。尤其是發(fā)生交通事故和交通堵塞時, 靜態(tài)路徑規(guī)劃不能及時改變路線。因此, 車輛導航動態(tài)路徑規(guī)劃就成為新一代智能車輛導航系統的研究熱點問題。車輛動態(tài)路徑規(guī)劃基于歷史的、當前的交通信息數據對未來交通流量進行預測, 并用于及時調整和更新最佳行車路線, 從而有效減少道路阻塞和交通事故。

?圖9 多導航器協調規(guī)劃示意圖

隨著計算機科學技術、無線通信技術以及交通運輸業(yè)的高速發(fā)展，車輛導航系統的動態(tài)路徑規(guī)劃研究趨勢還將向多導航器相互協調規(guī)劃的方向發(fā)展?，F在的車輛導航都是單個車輛為對象進行路徑引導，而沒有考慮到總體的大局協調，這樣容易引起新的交通擁塞等問題，所以多導航器協調規(guī)劃將是一種更加符合實際需求的規(guī)劃方法。

參考文獻：

1、 考慮全局最優(yōu)性的汽車微觀動態(tài)軌跡規(guī)劃

2、 車輛導航動態(tài)路徑規(guī)劃的研究進展

3、 Adaptive Routing for road traffic