路徑規(guī)劃主要包含兩個(gè)步驟：建立包含障礙區(qū)域與自由區(qū)域的環(huán)境地圖，以及在環(huán)境地圖中選擇合適的路徑搜索算法，快速實(shí)時(shí)地搜索可行駛路徑。路徑規(guī)劃結(jié)果對(duì)車輛行駛起著導(dǎo)航作用。它引導(dǎo)車輛從當(dāng)前位置行駛到達(dá)目標(biāo)位置。
環(huán)境地圖表示方法
根據(jù)不同的表示形式，環(huán)境地圖表示方法主要分為度量地圖表示法，拓?fù)涞貓D表示法等。
1、度量地圖表示法
度量地圖表示法采用坐標(biāo)系中的格柵是否被障礙物占據(jù)的方式來(lái)描述環(huán)境特征，分為幾何表示法和空間分解法。
幾何表示法利用包括點(diǎn)、線、多邊形在內(nèi)的幾何元素來(lái)表示環(huán)境信息。相比于其他環(huán)境地圖表示方式，幾何特征地圖更為緊湊，有利于位置估計(jì)和目標(biāo)識(shí)別;缺點(diǎn)是環(huán)境幾何特征提取困難。幾何特征地圖適合于在環(huán)境已知的室內(nèi)環(huán)境提取一些簡(jiǎn)單的幾何特征，而室外環(huán)境下的幾何特征較難提取。常用的幾何地圖有Voronoi圖、概率路圖等。
空間分解法是把環(huán)境分解為類似于格柵的局部單元，根據(jù)他們是否被障礙物占據(jù)來(lái)進(jìn)行狀態(tài)描述。如果格柵單元被障礙物占據(jù)，則為障礙格柵;反之，則為自由格柵。空間分解法通常采用基于格柵大小的均勻分解法和遞階分解法。均勻分解法中的格柵大小均勻分布，占據(jù)格柵用數(shù)值表示。均勻分解法能夠快速直觀地融合傳感器信息;但是，均勻分解法采用相同大小格柵會(huì)導(dǎo)致存儲(chǔ)空間巨大，大規(guī)模環(huán)境下路徑規(guī)劃計(jì)算復(fù)雜度高。為了克服均勻分解法中存儲(chǔ)空間巨大的問(wèn)題，遞階分解法把環(huán)境空間分解為大小不同的矩形區(qū)域，從而減少模型所占用的內(nèi)存空間。
均勻格柵地圖是度量地圖路徑規(guī)劃中最常用的。它把環(huán)境分解為一系列離散的格柵節(jié)點(diǎn)。所有格柵節(jié)點(diǎn)大小統(tǒng)一，均勻分布。格柵用值占據(jù)方式來(lái)表示障礙物信息。例如使用最簡(jiǎn)單的二值表示方法，1表示障礙格柵，不可通行;0表示自由格柵。
當(dāng)用均勻格柵地圖表示環(huán)境信息后，格柵節(jié)點(diǎn)之間只有建立一定的連接關(guān)系才能保證能從起點(diǎn)搜索到目標(biāo)點(diǎn)的有效路徑。
2、拓?fù)涞貓D表示法
拓?fù)涞貓D模型選用節(jié)點(diǎn)表示道路上的特定位置，并用節(jié)點(diǎn)與節(jié)點(diǎn)間的關(guān)系來(lái)表示道路間聯(lián)系。這種地圖表示方法具有結(jié)構(gòu)簡(jiǎn)單、存儲(chǔ)方便、全局連貫性好、規(guī)劃效率高、魯棒性強(qiáng)等特點(diǎn)，適合于大規(guī)模環(huán)境下的道路規(guī)劃，但它包含信息量少，需借助其他傳感器來(lái)對(duì)道路環(huán)境做進(jìn)一步描述。
路徑規(guī)劃算法
目前路徑規(guī)劃方法分類大致如下：
路徑規(guī)劃圖
比較常用的路徑規(guī)劃算法為基于采樣的路徑規(guī)劃算法以及基于搜索路徑規(guī)劃算法。
1、基于采樣的路徑規(guī)劃算法
基于采樣的路徑規(guī)劃算法很早便開(kāi)始用于車輛的路徑規(guī)劃中，比較常見(jiàn)的基于采樣的規(guī)劃算法有概率圖算法(Probabilistic Road Map， PRM)和快速隨機(jī)擴(kuò)展樹(shù)算法(Rapidly-exploring Random Tree，RRT)。
概率圖算法是在規(guī)劃空間內(nèi)隨機(jī)選取N個(gè)節(jié)點(diǎn)，之后連接各節(jié)點(diǎn)，并去除于障礙物接觸的連線，由此得到一個(gè)可行路徑。顯然，當(dāng)采樣點(diǎn)太少，或者分布不合理時(shí)，PRM算法是不完備的，但可以增加采樣點(diǎn)使該算法達(dá)到完備，所以PRM是概率完備但不是最優(yōu)的。
PRM算法
快速隨機(jī)擴(kuò)展樹(shù)最初主要用于解決含有運(yùn)動(dòng)學(xué)約束的路徑規(guī)劃問(wèn)題。由于RRT在狀態(tài)空間中采用隨機(jī)采樣確定擴(kuò)展節(jié)點(diǎn)，不需要預(yù)處理，搜索速度快。因此這種算法作為一種快速搜索算法在路徑規(guī)劃問(wèn)題中獲得廣泛應(yīng)用。
RRT算法
2、基于搜索的路徑規(guī)劃算法
基于搜索的路徑規(guī)劃算法通過(guò)搜索表示環(huán)境信息的環(huán)境地圖來(lái)獲得最終的路徑。比較有代表性的算法有Dijkstra算法和A算法。
Dijkstra算法是典型的廣度優(yōu)先搜索算法。它是一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生的最短路徑的方法，是求解最短路徑的經(jīng)典算法之一。Dijkstra算法是一種貪心算法，它在每一步都選擇局部最優(yōu)解，以產(chǎn)生一個(gè)最優(yōu)解。這也會(huì)導(dǎo)致該算法的時(shí)間復(fù)雜度較高，在圖規(guī)模較大時(shí)，該算法的計(jì)算速度慢，很難滿足路徑規(guī)劃實(shí)時(shí)性的要求。
A*算法是經(jīng)典的啟發(fā)式搜索算法，它是由Dijkstra算法改進(jìn)而來(lái)的。其最顯著的特點(diǎn)就是在搜索過(guò)程中增加了啟發(fā)函數(shù)，通過(guò)給定啟發(fā)函數(shù)來(lái)減少搜索節(jié)點(diǎn)，從而提高路徑搜索效率。研究表明，A*算法搜索得到的路徑能夠同時(shí)滿足實(shí)時(shí)性和最優(yōu)性要求。
3、結(jié)語(yǔ)
現(xiàn)實(shí)環(huán)境遠(yuǎn)比這要復(fù)雜，良好的規(guī)劃必須建立對(duì)周邊環(huán)境的深刻理解，另外還需要建立大量的數(shù)學(xué)方程，以及需要考慮障礙物、車道線、路徑曲率、曲率變化率以及車輛速度、加速度等多種因素的影響。
