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

　　圖1智能汽車示意圖

　　隨著計(jì)算機(jī)技術(shù)、電子技術(shù)、圖像處理等信息處理技術(shù)研究的發(fā)展，研究人員開始將各種先進(jìn)的技術(shù)應(yīng)用于汽車控制上，輔助駕駛員進(jìn)行汽車的操縱控制，如目前已經(jīng)實(shí)用化的制動(dòng)防抱控制系統(tǒng)、驅(qū)動(dòng)力控制系統(tǒng)、四輪轉(zhuǎn)向系統(tǒng)以及汽車穩(wěn)定性控制系統(tǒng)等。在這些汽車電子控制系統(tǒng)研究的基礎(chǔ)上，結(jié)合蓬勃發(fā)展的智能化信息處理技術(shù)，逐步產(chǎn)生了一個(gè)新興的交叉學(xué)科-車輛的自動(dòng)駕駛(又稱為智能汽車)。未來(lái)實(shí)用化的智能汽車將最大限度地減少交通事故、提高運(yùn)輸效率、減輕駕駛員操縱負(fù)擔(dān)，從而提高整個(gè)道路交通的安全性、機(jī)動(dòng)性與汽車行駛的主動(dòng)安全性?？萍疾坑?001年已正式啟動(dòng)實(shí)施了十五計(jì)劃中的國(guó)家科技攻關(guān)計(jì)劃重大項(xiàng)目“智能交通系統(tǒng)關(guān)鍵技術(shù)開發(fā)和示范工程”來(lái)提高我國(guó)整個(gè)運(yùn)輸系統(tǒng)的管理水平和服務(wù)水平，提高效率和安全性，車輛的自主駕駛是實(shí)現(xiàn)ITS(Intelligent Transport System,智能交通系統(tǒng))的關(guān)鍵。

　　圖2智能交通系統(tǒng)示意圖

　　車輛自主駕駛系統(tǒng)從本質(zhì)上講是一個(gè)智能控制機(jī)器，其研究?jī)?nèi)容大致可分為信息感知、行為決策及操縱控制三個(gè)子系統(tǒng)。路徑規(guī)劃是智能車輛導(dǎo)航和控制的基礎(chǔ)，是從軌跡決策的角度考慮的，可分為局部路徑規(guī)劃和全局路徑規(guī)劃。全局路徑規(guī)劃的任務(wù)是根據(jù)全局地圖數(shù)據(jù)庫(kù)信息規(guī)劃出自起始點(diǎn)至目標(biāo)點(diǎn)的一條無(wú)碰撞、可通過(guò)的路徑。目前正在研究的有準(zhǔn)結(jié)構(gòu)化道路環(huán)境多種約束條件下的路徑規(guī)劃技術(shù)，自然地形環(huán)境下的路徑規(guī)劃技術(shù)，以及重規(guī)劃技術(shù)等。由于全局路徑規(guī)劃所生成的路徑只能是從起始點(diǎn)到目標(biāo)點(diǎn)的粗略路徑，并沒有考慮路徑的方向、寬度、曲率、道路交叉以及路障等細(xì)節(jié)信息，加之智能車輛在行駛過(guò)程中受局部環(huán)境和自身狀態(tài)的不確定性的影響，會(huì)遇到各種不可測(cè)的情況。因此，在智能車輛的行駛過(guò)程中，必須以局部環(huán)境信息和自身狀態(tài)信息為基礎(chǔ)，規(guī)劃出一段無(wú)碰撞的理想局部路徑，這就是局部路徑規(guī)劃。通常路徑規(guī)劃的方法有:空間搜索法、層次法、動(dòng)作行為法、勢(shì)場(chǎng)域法、柵格法、模糊邏輯法和神經(jīng)網(wǎng)絡(luò)法等。

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

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

　　車輛路徑規(guī)劃問(wèn)題中的幾個(gè)關(guān)鍵點(diǎn):路網(wǎng)模型、路徑規(guī)劃算法和交通信息的智能預(yù)測(cè)，涉及的方面較多，本文主要針對(duì)路徑規(guī)劃過(guò)程做簡(jiǎn)單的探討。

　　一.問(wèn)題引入

　　我們嘗試解決的問(wèn)題是把一個(gè)游戲?qū)ο?gameobject)從出發(fā)點(diǎn)移動(dòng)到目的地，如圖2所示。路徑搜索(Pathfinding)的目標(biāo)是找到一條好的路徑——避免障礙物、敵人，并把代價(jià)(燃料，時(shí)間，距離，裝備，金錢等)最小化。運(yùn)動(dòng)(Movement)的目標(biāo)是找到一條路徑并且沿著它行進(jìn),當(dāng)游戲?qū)ο箝_始移動(dòng)時(shí)，一個(gè)老練的路徑搜索器(pathfinder)外加一個(gè)瑣細(xì)的運(yùn)動(dòng)算法(movementalgorithm)可以找到一條路徑，游戲?qū)ο髮?huì)沿著該路徑移動(dòng)而忽略其它的一切。一個(gè)單純的運(yùn)動(dòng)系統(tǒng)(movement-onlysystem)將不會(huì)搜索一條路徑(最初的“路徑”將被一條直線取代)，取而代之的是在每一個(gè)結(jié)點(diǎn)處僅采取一個(gè)步驟，即朝著某個(gè)方向行進(jìn)一段距離，同時(shí)需要考慮周圍的障礙物環(huán)境避免碰撞的產(chǎn)生。顯然，同時(shí)使用路徑搜索(Pathfinding)和運(yùn)動(dòng)算法(movementalgorithm)將會(huì)得到最好的效果。

　　移動(dòng)一個(gè)簡(jiǎn)單的物體(object)看起來(lái)是容易的，而路徑搜索是復(fù)雜的，為什么涉及到路徑搜索就產(chǎn)生麻煩了？考慮以下情況：

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

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

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

　　淺談車輛自動(dòng)駕駛軌跡規(guī)劃的作用

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

　　二、問(wèn)題描述

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

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

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

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

　　1.Dijkstra算法

　　圖6Dijkstra算法動(dòng)態(tài)圖

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

　　2.Lee算法

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

　　3.Floyd算法

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

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

　　圖7A*算法動(dòng)態(tài)示意圖

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

　　5.雙向搜索算法

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

　　6.蟻群算法

　　圖8蟻群算法示意圖

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

　　此外,還有實(shí)時(shí)啟發(fā)式搜索算法、基于分層路網(wǎng)的搜索算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法及模糊理論等,由于實(shí)際需求不同對(duì)算法的要求和側(cè)重點(diǎn)也會(huì)有所不用,所以也出現(xiàn)了許多以上算法的各種改進(jìn)算法。大多數(shù)算法應(yīng)用于求解車輛路徑規(guī)劃問(wèn)題時(shí)都會(huì)存在一定的缺陷,所以目前的研究側(cè)重于利用多種算法融合來(lái)構(gòu)造混合算法。

　　四.總結(jié)

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

　　圖9多導(dǎo)航器協(xié)調(diào)規(guī)劃示意圖

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