‧ 想讓自動駕駛更安全，這個問題很重要

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

隨著電腦技術、電子技術、影像處理等資訊處理技術研究的發展，研究人員開始將各種先進的技術應用於汽車控制上，輔助駕駛員進行汽車的操縱控制，如目前已經實用化的制動防抱控制系統、驅動力控制系統、四輪轉向系統以及汽車穩定性控制系統等。

（圖1 智能汽車示意圖）

在這些汽車電子控制系統研究的基礎上，結合蓬勃發展的智慧化資訊處理技術，逐步產生了一個新興的交叉學科-車輛的自動駕駛（又稱為智慧汽車）。

未來實用化的智慧汽車將最大限度地減少交通事故、提高運輸效率、減輕駕駛員操縱負擔，從而提高整個道路交通的安全性、機動性與汽車行駛的主動安全性。

對岸中國的科技部於2001年已正式啟動實施了十五計畫中的國家科技攻關計畫重大專案“智慧交通系統關鍵技術開發和示範工程” 來提高該國整個運輸系統的管理水準和服務水準，提高效率和安全性，車輛的自主駕駛是實現ITS(Intelligent Transport System,智慧交通系統)的關鍵。

（圖2 智慧交通系統示意圖）

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

全域路徑規劃的任務，是根據全域地圖資料庫資訊，規劃出自起始點至目標點的一條無碰撞、可通過的路徑。目前正在研究的有準結構化道路環境，多種約束條件下的路徑規劃技術，自然地形環境下的路徑規劃技術，以及重規劃技術等。

由於全域路徑規劃所生成的路徑，只能是從起始點到目標點的粗略路徑，並沒有考慮路徑的方向、寬度、曲率、道路交叉以及路障等細節資訊，加之智慧車輛在行駛過程中受局部環境和自身狀態的不確定性的影響，會遇到各種不可測的情況。

因此，在智慧車輛的行駛過程中，必須以局部環境資訊和自身狀態資訊為基礎，規劃出一段無碰撞的理想局部路徑，這就是局部路徑規劃。通常路徑規劃的方法有:空間搜索法、層次法、動作行為法、勢場域法、柵格法、模糊邏輯法和神經網路法等。

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

上層路徑規劃在已知電子地圖、路網以及宏觀交通資訊等先驗資訊下，根據某優化目標得到兩點之間的最優路徑，完成路徑規劃的傳感資訊主要來自於 GPS 定位資訊以及電子地圖。中層行駛行為規劃是指根據主車感興趣區域內道路。

交通車等環境資訊，決策出當前時刻滿足交通法規、結構化道路約束的最優行駛行為，動態規劃的行駛行為序列組成宏觀路徑。行為規劃的傳感資訊主要來自車載感測器，如雷達、照相機等，用以辨識道路障礙、車道線、道路標識資訊和交通信號燈資訊等。

下層軌跡規劃是指在當前時刻，以完成當前行車行為為目標，考慮周圍交通環境並滿足不同約束條件，根據最優目標動態規劃決策出的最優軌跡。同時，車輛的動力學約束也會在下層得到體現，下層軌跡規劃除了必要的外部環境資訊外，還需要對主車狀態資訊進行測量或估計。

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

| 問題引入

我們嘗試解決的問題是把一個遊戲物件（game object）從出發點移動到目的地，如圖2所示。路徑搜索(Pathfinding)的目標是找到一條好的路徑——避免障礙物、敵人，並把代價（燃料，時間，距離，裝備，金錢等）最小化。運動（Movement）的目標是找到一條路徑，並且沿著它行進，當遊戲物件開始移動時，一個老練的路徑搜索器（pathfinder）外加一個瑣細的運動演算法（movement algorithm）可以找到一條路徑，遊戲物件將會沿著該路徑移動而忽略其它的一切。

一個單純的運動系統（movement-only system）將不會搜索一條路徑（最初的“路徑”將被一條直線取代），取而代之的是在每一個結點處僅採取一個步驟，即朝著某個方向行進一段距離，同時需要考慮周圍的障礙物環境避免碰撞的產生。顯然，同時使用路徑搜索(Pathfinding)和運動演算法（movement algorithm）將會得到最好的效果。

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

（圖4 避障路徑規劃）

物體（unit）最初位於地圖的底端並且嘗試向頂部移動，物體掃描的區域中(粉紅色部分)沒有任何東西顯示它不能向上移動，因此它持續向上移動。在靠近頂部時，它探測到一個障礙物然後改變移動方向，然後它沿著U形障礙物找到它的紅色的路徑。

相反的，一個路徑搜索器（pathfinder）將會掃描一個更大的區域（淡藍色部分），但是它能做到不讓物體(unit)走向凹形障礙物而找到一條更短的路徑(藍色路徑）。

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

（圖5 避障優化路徑規劃方法）

| 問題描述

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

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

| 車輛路徑規劃演算法

根據車輛導航系統的研究歷程，車輛路徑規劃演算法可分為靜態路徑規劃演算法，和動態路徑演算法。靜態路徑規劃是以物理地理資訊，和交通規則等條件，為約束來尋求最短路徑，靜態路徑規劃演算法已日趨成熟，相對比較簡單，但對於實際的交通狀況來說,其應用意義不大。

動態路徑規劃是在靜態路徑規劃的基礎上，結合即時的交通資訊對預先規劃好的最優行車路線，進行適時的調整直至到達目的地最終得到最優路徑。下面介紹幾種常見的車輛路徑規劃演算法。

1. Dijkstra演算法

（圖6 Dijkstra演算法動態圖）

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

2．Lee演算法

Lee演算法最早用於印刷電路和積體電路的路徑追蹤，與Dijkstra演算法相比更適合用於資料隨時變化的道路路徑規劃，而且其運行代價要小於Dijkstra 算法。只要最佳路徑存在，該演算法就能夠找到最佳優化路徑。Lee演算法的複雜度很難表示，而且對於多圖層的路徑規劃則需要很大的空間。

3. Floyd演算法

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

4．啟發式搜索演算法——A* 演算法

（圖7 A* 演算法動態示意圖）

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

5．雙向搜索演算法

雙向搜索演算法由Dantzig 提出的基本思想，Nicholson正式提出演算法。該演算法在從起點開始尋找最短路徑的同時，也從終點開始向前進行路徑搜索，最佳效果是二者在中間點匯合，這樣可縮短搜索時間。

但是如果終止規則不合適, 該演算法極有可能使搜索時間增加1倍，即兩個方向都搜索到最後才終止。

6. 蟻群演算法

（圖8 蟻群演算法示意圖）

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

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

| 四．總結

目前, 投入市場應用的成熟車輛導航系統大多基於靜態的路徑規劃，然而面對存在眾多不穩定因素的交通現實，用戶並不滿足於現有的系統。尤其是發生交通事故和交通堵塞時, 靜態路徑規劃不能及時改變路線。

因此，車輛導航動態路徑規劃，就成為新一代智慧車輛導航系統的研究熱點問題。車輛動態路徑規劃基於歷史的、當前的交通資訊資料，對未來交通流量進行預測，並用於及時調整和更新最佳行車路線，從而有效減少道路阻塞和交通事故。