今天這篇文章作為之前6.1 Apollo規(guī)劃的補(bǔ)充，詳細(xì)介紹下EM Planner

1. EM Planner 中的EM的含義

最大期望算法 Expectation Maximum

最大期望算法在統(tǒng)計(jì)中被用于尋找，依賴于不可觀察的隱性變量的概率模型中，參數(shù)的最大似然估計(jì)。

在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率模型中尋找參數(shù)最大似然估計(jì)或者最大后驗(yàn)估計(jì)的算法，其中概率模型依賴于無(wú)法觀測(cè)的隱性變量。最大期望算法經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)的數(shù)據(jù)聚類（Data Clustering）領(lǐng)域。最大期望算法經(jīng)過(guò)兩個(gè)步驟交替進(jìn)行計(jì)算，第一步是計(jì)算期望（E），利用對(duì)隱藏變量的現(xiàn)有估計(jì)值，計(jì)算其最大似然估計(jì)值；第二步是最大化（M），最大化在E步上求得的最大似然值來(lái)計(jì)算參數(shù)的值。M步上找到的參數(shù)估計(jì)值被用于下一個(gè)E步計(jì)算中，這個(gè)過(guò)程不斷交替進(jìn)行。

EM簡(jiǎn)單教程

EM是一個(gè)在已知部分相關(guān)變量的情況下，估計(jì)未知變量的迭代技術(shù)。EM的算法流程如下：

初始化分布參數(shù)

重復(fù)直到收斂：

E步驟：根據(jù)隱含數(shù)據(jù)的假設(shè)值，給出當(dāng)前的參數(shù)的極大似然估計(jì)。

M步驟：重新給出未知變量的期望估計(jì)。應(yīng)用于缺失值。

2. 變道超車在EM Planner中是如何考慮的？

對(duì)于路徑規(guī)劃而言，變道是重要的組成部分。一般的方法是在所有可能的車道上進(jìn)行基于cost的最優(yōu)解搜索。不過(guò)這種方法也有以下的缺點(diǎn)：

搜索空間要拓展到不同的車道，算法資源占用相對(duì)較多。

不同車道對(duì)應(yīng)了不同的交規(guī)，在同樣的計(jì)算框架下不容易實(shí)現(xiàn)。

因此在apollo里面使用了如下的Framework，對(duì)不同可能的目標(biāo)車道分別進(jìn)行優(yōu)化尋找最優(yōu)解，最后的Decider決定最終的路徑。

上圖中的E-Step對(duì)應(yīng)的基于隱含數(shù)據(jù)的假設(shè)值（當(dāng)前規(guī)劃的Trajectory）進(jìn)行的極大似然估計(jì)（Path Planning）。

M-Step對(duì)應(yīng)的是重新給出未知變量的期望估計(jì)（Velocity Planning，然后合成完整的Trajectory）。

最后的Trajectory decider會(huì)根據(jù)不同Trajectory的cost，交規(guī)還有車況選擇一條最優(yōu)的trajectory。

3. Path 和 Speed 迭代算法

Path

EM Planner會(huì)迭代式的對(duì)路徑和速度進(jìn)行優(yōu)化。首先基于上一步計(jì)算得到的trajectory也就是對(duì)自身運(yùn)動(dòng)的預(yù)測(cè)與其他運(yùn)動(dòng)物體的預(yù)測(cè)進(jìn)行碰撞檢測(cè)，講可能的碰撞點(diǎn)投射到SL圖中。這里在SL圖中只考慮低速移動(dòng)物體或?qū)ο蛐旭偟奈矬w，對(duì)于高速物體，EM Planner基于安全原因更傾向于變道。

整個(gè)路徑的規(guī)劃分為DP的粗糙規(guī)劃，和QP的平滑規(guī)劃，QP主要就是對(duì)DP的路徑進(jìn)行平滑處理。

這里Cost有三個(gè)組成部分：平滑Cost，離障礙物距離Cost，離引導(dǎo)線偏差Cost。

?

Nudge Decision包括nudge, yield和overtake，用來(lái)生成convex hull來(lái)進(jìn)行QP的spline優(yōu)化。

QP的Cost相對(duì)簡(jiǎn)單些，就是負(fù)責(zé)平滑的路徑一階二階三階倒數(shù)還有和DP結(jié)果與引導(dǎo)線的偏差。

Speed

速度優(yōu)化和路徑優(yōu)化類似，也是先來(lái)DP跟著QP。

Cost多了和目標(biāo)速度的偏差和與障礙物的距離。

?

?

4.實(shí)例

a. 上一個(gè)cycle的規(guī)劃，master vehicle 10m/s直行。

b. 第一次迭代，基于上一個(gè)cycle的預(yù)測(cè)，可能的碰撞區(qū)域位于S = 40m 處，映射到SD Graph進(jìn)行path優(yōu)化。

c. 基于優(yōu)化得到的Path進(jìn)行速度優(yōu)化，40m處因?yàn)榫嚯x障礙物較近，會(huì)減速到5m/s。

d. 這個(gè)時(shí)候因?yàn)?master vehicle 的 預(yù)測(cè)更新了，進(jìn)行第二次迭代，基于新的速度Profile，可能的碰撞（交叉）區(qū)域位于S = 30m 處，重新優(yōu)化Path

e. 基于新優(yōu)化得到的Path再次進(jìn)行速度優(yōu)化，迭代會(huì)一直進(jìn)行知道收斂。

總結(jié)

以上是生活随笔為你收集整理的【Baidu Apollo】6.3 EM规划算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。