作者的話： 本文是關於馬爾可夫理論的一些學習筆記和思考，請帶著批判的眼光閱讀。
機器學習一共有三個分支，有監督學習、無監督學習和強化學習。強化學習是系統從環境學習以使得獎勵最大的機器學習。強化學習和有監督學習的不同在於教師信號。強化學習的教師信號是動作的獎勵，有監督學習的教師信號是正確的動作。
強化學習算法理論的形成可以追溯到上個世紀七八十年代，近幾十年來強化學習算法一直在默默地不斷進步，真正火起來是最近幾年。代表性的事件是DeepMind 團隊於2013年12月首次展示了機器利用強化學習算法在雅達利遊戲中打敗人類專業玩家，其成果在2015年發布於頂級期刊《自然》上；2014年，谷歌將DeepMind 團隊收購。2016年3月，DeepMind開發的AlphaGo程序利用強化學習算法以4:1擊敗世界圍棋高手李世石，至此強化學習算法引起更多學者的關注。如今，強化學習算法已經在如遊戲，機器人等領域中開花結果。各大科技公司，如谷歌，facebook，百度，微軟等更是將強化學習技術作為其重點發展的技術之一。可以說強化學習算法正在改變和影響著這個世界，掌握了這門技術就掌握了改變世界和影響世界的工具。
現在網上有一些強化學習的教程，這些教程都來自世界頂尖名校，如2015年David Silver的經典課程Teaching ，2017年加州大學伯克利分校Levine, Finn, Schulman的課程 CS 294 Deep Reinforcement Learning, Spring 2017 ，卡內基梅隆大學的2017 春季課程Deep RL and Control 。吳恩達的Deep learning 也很棒，可以在網易公開課或者它的官網看到。
那麼，在自動駕駛領域，強化學習如何應用呢？在之前的文章中，我曾經提過道路使用者之間動態博弈的問題，這個問題在一定程度上可以簡化成一個馬爾可夫決策過程，而強化學習可以通過大量的數據訓練，給這個馬爾可夫決策過程求最優解，使得車輛能夠獲得更好的路徑規劃策略。對於靜態目標，因為「狀態」並不會隨著自車的動作變化，所以個人理解並不適用馬爾可夫模型。
馬爾可夫理論由俄國數學家A.A.馬爾可夫於1907年提出，這個理論包括一些基本概念和衍生的理論，簡稱馬爾可夫全家桶（啊哈哈），包括：
- 馬爾可夫性質（Markov Property）
- 馬爾可夫過程/馬爾可夫鏈（Markov Process/ Markov Chain）
- 馬爾可夫決策過程（Markov Decision Process/ MDP）
- 隱馬爾可夫模型 （Hidden Markov Model/ HMM）
- 不完全可觀察馬爾可夫決策過程( Partially Observable Markov Decision Process/ POMDP)
馬爾可夫理論和其他理論結合還有大量的應用，在此不一一羅列。
馬爾可夫性質
馬可夫性質（英語：Markov property）是概率論中的一個概念，因為俄國數學家安德雷·馬爾可夫得名。當一個隨機過程在給定現在狀態及所有過去狀態情況下，其未來狀態的條件概率分布僅依賴於現在狀態；換句話說，在給定現在狀態時，它與過去狀態（即該過程的歷史路徑）是條件獨立的，那麼此隨機過程即具有馬爾可夫性質。
用數學來表示就是：
假設X為變化過程中的某個狀態，那麼隨機變量 X1, … , Xn 的數列被稱為「狀態空間」， Xn 的值是在時間 n 的狀態。如果 Xn+1 對於過去狀態的條件概率分布P僅是 Xn 的一個函數，與Xn-1, ... , X1均無關，即
則上面這個恆等式可以被看作是馬爾可夫性質。
馬爾科夫決策過程
馬爾可夫決策過程是基於馬爾可夫過程理論的隨機動態系統的最優決策過程。馬爾可夫決策過程是序貫決策的主要研究領域。它是馬爾可夫過程與確定性的動態規劃相結合的產物，故又稱馬爾可夫型隨機動態規劃，屬於運籌學中數學規劃的一個分支。
馬爾可夫決策過程可以用一個五元數(s,a,P,R,γ) 來描述，其中：
s 是一組有限的狀態集(a finite set of states)；
a 是一組有限的動作集(a finite set of actions or As is the finite set of actions available from states) ；
Pa(s,s′)=Pr(st+1=s′|st=s,at=a) 表示在時間 t 狀態s 採取動作a 可以在時間 t+1 轉換到狀態 s′ 的概率；
Ra(s,s′) 表示通過動作a 狀態從 s 轉換到s′ 所帶來的及時收益（或者是預期及時收益）
γ∈[0,1] 是折扣因子(discount factor)，表示未來收益和當前收益之前的差別，就是各個時間的收益所佔的比重不同。
馬爾可夫決策過程並不要求S 或者A 是有限的，但基礎的算法中假設它們由有限的。
MDP 的動態過程如下：某個智能體(agent)的初始狀態為s0，然後從 a中挑選一個動作a0執行，執行後，agent 按P(s1| s0,a0)概率隨機轉移到了下一個s1狀態，s1∈ P(s0,a0)。然後再執行一個動作a1，就轉移到了s2，接下來再執行a2…，我們可以用下面的圖表示狀態轉移的過程。
如果回報rn是根據狀態s和動作a得到的，則MDP還可以表示成下圖：
MDP的關鍵問題在於尋找一個策略：在狀態 s 選擇策略π(s)， 組成一個策略函數π，我們的目的在於選擇一個策略函數π 可以最大化累積收益R(T)：
求解R(T)max，需要用到最優貝爾曼方程。而尋找最優策略的具體算法，包括了價值迭代、策略迭代、蒙特卡洛算法和Q學習算法等，後面再慢慢研究.
隱馬爾可夫模型
隱馬爾可夫模型 (Hidden Markov Model) 是另一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數，然後利用這些參數來作進一步的分析。下圖是一個三個狀態的隱馬爾可夫模型狀態轉移圖，其中x 表示隱含狀態，y 表示可觀察的輸出，a 表示狀態轉換概率，b 表示輸出概率。
下圖顯示了天氣的例子中隱藏的狀態和可以觀察到的狀態之間的關係。我們假設隱藏的狀態是一個簡單的一階馬爾科夫過程，並且他們兩兩之間都可以相互轉換。
對 HMM 來說，有如下三個重要假設，儘管這些假設是不現實的。
假設1：馬爾可夫假設（狀態構成一階馬爾可夫鏈）
假設2：不動性假設（狀態與具體時間無關）
假設3：輸出獨立性假設（輸出僅與當前狀態有關）
隱藏的狀態和可觀察到的狀態之間有一種概率上的關係，也就是說某種隱藏狀態 H 被認為是某個可以觀察的狀態 O1 是有概率的，假設為 P(O1 | H)。如果可以觀察的狀態有3種，那麼很顯然 P(O1 | H)+P(O2 | H)+ P(O3 | H) = 1。
這樣，我們也可以得到一個另一個矩陣，稱為混淆矩陣 (confusion matrix)。這個矩陣的內容是某個隱藏的狀態被分別觀察成幾種不同的可以觀察的狀態的概率，在天氣的例子中，這個矩陣如下圖：
上邊的圖示都強調了 HMM 的狀態變遷。而下圖則明確的表示出模型的演化，其中綠色的圓圈表示隱藏狀態，紫色圓圈表示可觀察到狀態，箭頭表示狀態之間的依存概率，一個 HMM 可用一個5元組 { N, M, π，A，B } 表示，其中：
- N 表示隱藏狀態的數量，我們要麼知道確切的值，要麼猜測該值
- M 表示可觀測狀態的數量，可以通過訓練集獲得，
- π={πi} 為初始狀態概率
- A={aij} 為隱藏狀態的轉移矩陣 Pr(xt(i) | xt-1(j))
- B={bik} 表示某個時刻因隱藏狀態而可觀察的狀態的概率，即混淆矩陣，Pr(ot(i) | xt(j))。
在狀態轉移矩陣和混淆矩陣中的每個概率都是時間無關的，即當系統演化時，這些矩陣並不隨時間改變。對於一個 N 和 M 固定的 HMM 來說，用 λ={ π, A, B } 表示 HMM 參數。
在正常的馬爾可夫模型中，狀態對於觀察者來說是直接可見的。這樣狀態的轉換概率便是全部的參數。而在隱馬爾可夫模型中，狀態並不是直接可見的，但受狀態影響的某些變量則是可見的。每一個狀態在可能輸出的符號上都有一概率分布。因此輸出符號的序列能夠透露出狀態序列的一些信息。
從上面的原理中可以看出，HMM並不特別適合自動駕駛，實際上它也更多的被應用於智能翻譯和語義識別。
部分可觀察馬爾可夫決策過程
部分可觀察馬爾可夫決策過程是一個「通用化」的馬爾可夫決策過程，POMDP模擬程序決策過程，其中假設系統動態由MDP確定，但程序不能直接觀察基礎狀態。相反，它必須基於一組觀察和觀察概率以及基礎MDP來維持可能狀態集合的概率分布。POMDP在自動駕駛和機器人的路徑規劃上有著應用。
POMDP可以對車輛或自身所處的環境進行建模，也可以用一個七元數(S,A,P,R,Ω,O,γ) 來描述：
S 是一組有限狀態集；
A 是一組有限動作集；
P 是狀態轉移矩陣，Pa(s′|s)=P(s′|s,a) 表示在時間 t 狀態 s 採取動作 a 可以在時間 t+1 轉換到狀態s′ 的概率；
R:S×A→R 是收益函數，R(s,a) 表示在狀態 s 執行動作 a 帶來的收益；
Ω 是一組觀察結果集，就是傳感器獲得的環境數據；
O 是條件觀察概率，就是在觀察到環境數據 o 時，有多大概率確定自己處於狀態s;
γ∈[0,1] 是折扣因子
上面的描述有些過於抽象，舉個例子，比如下面這個場景：
黑色的自車直行，藍色的目標車有向右移動的橫向速度
我們可以這麼理解POMDP在這個場景下的應用：
S - 目標車輛左轉（向自車右方轉向）
A - 自車直行
P - 自車直行，目標車輛向右移動，且下一步繼續向右移動的概率
R - 自車直行的收益函數
O - 觀測到目標車輛向右移動，目標車輛的意圖為左轉的概率
γ - 折扣因子
「目標車輛向右移動」是一個可以被傳感器感知到的「表象」，但我並不知道它下一步是不是真的想要左轉，還是僅僅為了避讓它旁邊的行人或是地上的坑，「左轉」是一個意圖，無法直接被傳感器感知，但左轉這個狀態會決定下一步自車應該如何做出動作，而自車的動作又會產生「收益」，比如是否會發生碰撞和駕駛員的舒適感，又比如對向車輛是否可以通行（涉及到整體交通效率，如果在一個窄路上對向車輛無法通行，可能導致自車也無法通行，反而影響到自車收益）。
這個模型是否有效的關鍵，在於是否正確的設計了S，A，P的定義，比如S和A應該是車輛縱向和橫向動態兩個狀態向量組成的矩陣，它們不僅僅是左轉右轉這麼簡單，還應當和動作幅度有關。而P顯然涉及到人類駕駛員的認知習慣，需要大量的數據來進行統計。對於R，O，γ，則可以通過數據的訓練和參數調整來優化。另外個人比較好奇的是，馬爾可夫性質的核心是「無記憶」，但如果對向車輛在連續的幾個cycle持續向某一個方向移動，且達到了一定的幅度，那麼它左轉的可能性顯然要大於小幅度的橫向移動或者單幀的移動（這裡還涉及到傳感器測量精度和信號濾波等問題），這明顯的存在著「記憶性」，那麼這樣應用馬爾可夫模型是否可以取得良好的效果需要測試，可能的優化也是存在的。
總的來說，馬爾可夫模型是理論基礎，但實際在自動駕駛路徑規劃上的應用，還需要很多「改良」。另外自車需要對多個目標同時進行路徑規劃和仲裁，做一個完善的應用依然需要大量的研究。
看看果殼機動的其他文章
汽車電控系統（二）- 轉向系統
自動駕駛相關的實時定位技術
汽車電控系統（一） - 制動系統
量子計算機詳解（下）
量子計算機詳解（上）
自動駕駛的數據融合到底融合了什麼？（續）
自動駕駛的數據融合到底融合了什麼？
禁止混水摸魚 - SAE J3016新版解讀
當談論架構的時候，我們在談什麼
好的需求文檔怎麼寫？
高能預警！Super Cruise來襲！
Euro NCAP 的自動駕駛路線指引
可能是最專業的自動駕駛等級解讀
長按二維碼關注果殼機動，時刻保持科技前沿