規(guī)劃中通過結(jié)合高進(jìn)度地圖，定位和預(yù)測來構(gòu)建車輛的軌跡。
第一步：路徑導(dǎo)航瓦糟，如從A地道B地，將地圖數(shù)據(jù)作為輸入蚜退，并輸出可行駛路徑
路徑規(guī)劃目標(biāo)：找到從地圖上的A地到B地的最佳路線闰靴。
路由
路線規(guī)劃使用三個輸入：
地圖：地圖數(shù)據(jù)包括公路網(wǎng)和實時交通信息
我們當(dāng)前在地圖上的位置
我們的目的地：通常取決于車輛的乘客
世界地圖
從地圖A-B，無人駕駛通常貨沿道路搜索有沒有任何路徑钻注，稱作搜索蚂且。Apollo也利用搜索來查找路徑，但搜索算法更智能幅恋，在搜索之前將地圖重新格式化成“圖形”的數(shù)據(jù)結(jié)構(gòu)膘掰，該圖形由“節(jié)點”和“邊緣”組成。
可以對從一個節(jié)點到另一節(jié)點所需要的成本進(jìn)行建模佳遣，從實際中就可以得出從1-3所需成本是比1到其它節(jié)點的要少识埋，從上圖可知，藍(lán)色的為低成本零渐。在計算機(jī)領(lǐng)域里窒舟，人們已經(jīng)發(fā)現(xiàn)許多用于從圖形中搜索路徑的算法，所以將地圖裝換為圖形有利于無人駕駛車搜索路徑诵盼。
網(wǎng)格世界
從初始節(jié)點開始惠豺，還需要相鄰的八個節(jié)點中哪個是最有希望的最佳候選節(jié)點，對每個候選節(jié)點都要考慮兩件事：
首先：計算候選節(jié)點到開始節(jié)點的成本风宁；
然后：計算從候選節(jié)點到最后節(jié)點的成本洁墙，可以自己定義計算成本的規(guī)則，比如有交通堵塞等情況戒财。
定義：
g:代表從初始節(jié)點到候選節(jié)點的成本
h:表示候選節(jié)點到目標(biāo)節(jié)點的成本
f:表示兩個值的和热监，值越小，表示成本越低饮寞。
A*算法
通過g,h值相加得到的f值來確定最佳路線孝扛，如下圖，最佳路線是網(wǎng)右轉(zhuǎn)幽崩，f值最小苦始。
從路由到軌跡
高等級地圖只是規(guī)劃過程的一部分，我們需要構(gòu)建沿這條道路的低等級軌跡慌申，意味找要處理地圖上沒有的物體陌选，如其它車輛，行人及自行車等蹄溉。如試圖與調(diào)頭的車輛互動咨油。這一級別的規(guī)劃稱為軌跡生成。
3D軌跡
軌跡生成目的是：生成由一系列路徑點所定義的軌跡类缤，每個路徑點都分配了一個時間戳和速度臼勉，讓一條曲線與這些路徑點擬合邻吭，生成軌跡的幾何表征餐弱，移動的障礙物可能會暫時阻擋部分路段，路段的每個路徑點都有一個時間戳，將時間戳與預(yù)測模塊的輸出結(jié)合起來膏蚓，以確保車輛在通過時瓢谢，路徑上的每個點都未被占用。這些時間戳創(chuàng)建了一個三維軌跡驮瞧。
評估一條軌跡
如何評估一條軌跡氓扛，采用成函數(shù)，選擇成本最低的路徑论笔。軌跡成本由各種規(guī)范和處罰組成采郎。
如下圖考慮到了：
車輛偏離中心線的距離
可能發(fā)生碰撞
速度限制
舒適度
通過將這些成本計算成數(shù)字，最終的出最佳的路徑狂魔。
車輛甚至可以在不同環(huán)境中使用不同的成本函數(shù)蒜埋。
Frenet坐標(biāo)
- 笛卡爾坐標(biāo)系
通常我們使用笛卡爾坐標(biāo)系來描述物體的位置，但對于車輛來說最楷，確不是最佳的選擇整份，我們即使能夠知道車輛的(x,y)坐標(biāo)，我們不知道路在哪里籽孙，很難知道車輛行駛了多遠(yuǎn)烈评，以難以確定車輛是否偏移車道中心。
- Frenet坐標(biāo)系
描述了汽車相對于車道的位置犯建，在Frenet框架中讲冠，s代表沿道路的距離，已被稱為縱坐標(biāo)适瓦，d表示與縱向線的位移沟启，已被稱為橫坐標(biāo)，在道路的每個點犹菇，橫軸與縱軸都是垂直的德迹。
縱坐標(biāo)表示車輛行駛距離，橫坐標(biāo)表示車輛偏離中心線的距離揭芍。
路徑速度解耦規(guī)劃
路徑-速度解耦規(guī)劃將軌跡規(guī)劃劃分為兩步：
路徑規(guī)劃：生成候選曲線胳搞，這是車輛可行駛的路徑，我們使用成本函數(shù)對每條路徑進(jìn)行成本評估称杨，該函數(shù)包含平滑肌毅，安全性，與車道中心的偏離姑原，以及我們想要考慮的其它的任何因素悬而。按成本對路徑進(jìn)行排名，并選擇成本最低的路徑锭汛。
速度規(guī)劃：路徑規(guī)劃之后就考慮速度的規(guī)劃笨奠，我們可能希望改變在該路段是的速度袭蝗，我們需要選擇的事與路徑點相關(guān)的一系列速度，而不是單個速度般婆，該系列稱之為“速度曲線”到腥，可以用優(yōu)化功能為路徑選擇，受到各種限制的良好速度曲線蔚袍，通過將路徑曲線和速度曲線相結(jié)合乡范，可構(gòu)建車輛的行駛軌跡。
路徑生成與選擇
