優(yōu)達學城的第四個項目，通過Q-Learning算法來實現(xiàn)一個簡單的無人車代駕程序。
先來一張訓練過程的動圖。

訓練過程.gif

需求分析

一個無人車需要滿足的最基本需求就是安全性和可靠性。安全性用來保證用戶安全，可靠性用來保證在限定時間內(nèi)將用戶送達目的地。安全性和可靠性劃分為A+、A、B、C、D、F六個等級

• 安全性
  安全性具體表現(xiàn)為遵守交通規(guī)則，避免交通事故。
  假設有一個簡化的世界，路口的交通燈是老式交通燈，不帶左右轉(zhuǎn)向指示燈。
  

  簡易世界
  
  紅線代表紅燈的路段。

  僅考慮紅綠燈就夠了嗎？？？

  NO?。?！

  根據(jù)一般的交通規(guī)則我們可以知道，紅燈時停止直行和左轉(zhuǎn)，但是可以右轉(zhuǎn)；綠燈時可以任意方向行駛。
  在該規(guī)則下，最可能引發(fā)安全隱患的情況有以下三種：

  • 綠燈時，想左轉(zhuǎn)，但是交叉方向有直行的車。（見圖1）
  • 紅燈時，想右轉(zhuǎn)，但是左側(cè)有直行車輛。（見圖2）

  • 綠燈時，想直行，但是右側(cè)有右轉(zhuǎn)車輛。（見圖3）

    
    
    引發(fā)安全隱患的情況

  因此確保安全性需要同時考慮紅綠燈、交叉方向車輛、左側(cè)車輛、右側(cè)車輛的意圖方向。

• 可靠性
  可靠性指按時到達目的地。由于路況的不確定，我們不能確定哪條路那種方式是最短時間消耗，比如遇到堵車，即使目的地就在前方，可能繞個道也比等待耗時短，所以這種情況下，我們只要時刻知道目的地的方位就行。

Q-Learning算法

我是通過查閱一個簡明的Q-learning教程和知乎上Flappy Bird學習Q-Learning理解的Q-Learning算法。
下圖是我畫的一個漫畫。

圖片發(fā)自簡書App

分數(shù)部分（獎勵）

用通俗易懂的語言來講（可能表述不嚴謹）Q-Learning算法，比如無人駕駛車，初始階段，小車不知道自己會遇到什么樣的狀態(tài)（路況），也不知道該采取什么樣的策略（前行？左轉(zhuǎn)？右轉(zhuǎn)？什么也不做？），每訓練一次可能遇到一種狀態(tài)，就把它記錄下來，比如這一次采取了前行的辦法，則世界根據(jù)這個動作給它一個打分，下一次又遇到了相同狀態(tài)，采取了左轉(zhuǎn)策略，則世界根據(jù)這個動作再給它一個打分……經(jīng)過數(shù)次訓練，小車可能知道了這種狀態(tài)下自己的所有行動對應的分數(shù)，在下一次遇到該狀態(tài)的時候，則采取分數(shù)最高的行動作為本次策略，結(jié)束了嗎？沒有，采取了分數(shù)最高行動之后，世界根據(jù)這個動作又要給小車一個打分，就意味著要刷新這一次分數(shù)，如何刷新呢？放棄原來的分數(shù)重新打分嗎？不，我們希望綜合原來的分數(shù)和本次的分數(shù)來打分，也就是Q-Learning公式中的學習率alpha

Q-Learning公式

公式中，t代表訓練輪次，s代表狀態(tài)，a代表動作，r（a）代表所采取的動作a的獎勵（分數(shù)），alpha代表學習率，gamma代表折扣因子，gamma后面的max代表下一個狀態(tài)中分數(shù)最高的動作的分數(shù)，不難發(fā)現(xiàn)，與簡明教程中房間不同，在無人車中，并不知道下一個狀態(tài)最高的動作是什么，因為路況是不確定的，所以令gamma=0，則公式便成了

簡化后的公式

動作選擇部分

除了分數(shù)部分，還有一個重要部分，動作選擇。每次該如何確定策略？引入一個探索因子epsilon。小車的動作選擇來源于以往經(jīng)驗和一丟丟“冒險”，就像我們學習新東西需要嘗試一樣，探索因子越大，小車越愛冒險，依據(jù)以往經(jīng)驗越少，探索因子越小，小車越拘束 ，依據(jù)以往經(jīng)驗越多。
不難想到，合適的探索因子是需要變化，比如一開始，小車什么都不知道，沒有經(jīng)驗可循，因此探索因子應該大一些，越往后，探索因子可適當減小，偶爾根據(jù)以往經(jīng)驗決定動作，偶爾冒險決定動作。
具體在程序中的使用就是：探索因子為0-1，產(chǎn)生一個0-1的隨機數(shù)，如果隨機數(shù)小于等于探索因子，則冒險，大于，則根據(jù)以往經(jīng)驗，這樣小車的每個動作就有一定概率是冒險，一定概率是以往經(jīng)驗。
至此，動作選擇部分完畢。

具體實現(xiàn)

代碼太多且涉及優(yōu)達學城的版權，因此不貼了，核心邏輯根據(jù)上下文的探討完全可以自己編碼實現(xiàn)，重要的是原理的理解。

狀態(tài)空間

根據(jù)需求分析，需要考慮的狀態(tài)有目的地方向、紅綠燈、交叉方向車輛、左側(cè)車輛、右側(cè)車輛，分別用waypoint、light、oncoming、left、right表示，waypoint有4種可能：forward、left、right、None，None代表到達目的地，算一種狀態(tài)，但不占狀態(tài)空間，因為到了目的地就不用判斷l(xiāng)ight之類了，所以waypoint有3種狀態(tài)，light有紅和綠兩種狀態(tài)，oncoming、left、right有forward、left、right、None四種狀態(tài)，則共有3x2x4x4x4=384種狀態(tài)，所以狀態(tài)空間的大小是384。

訓練輪次

根據(jù)我的代碼，每一輪有20次選擇，最極端的情況是20這20次學的同一種狀態(tài)的同一個動作，因此384種狀態(tài)，每種4個動作，想學完所有狀態(tài)，則需要384x4=1536輪訓練。

探索因子的衰減函數(shù)

探索因子的可選衰減函數(shù)有：

衰減函數(shù)

alpha的選擇

alpha參數(shù)需要自己調(diào)參，一般取0.5左右的值。

實現(xiàn)效果

隨機動作選擇

隨機動作選擇

可以看出，安全性和可靠性不管趨勢還是結(jié)果都完全隨機，很差。

用Q-Learning進行1500+輪訓練

1500+輪訓練

可以看出，事故越來越少，每個動作的評分也越來越高，可靠性也逐漸提高，且逐漸收斂。最終安全性和可靠性都較高。

用Q-Learning進行1500+輪訓練后的狀態(tài)文件截圖

1536輪訓練后的狀態(tài)文件截圖

經(jīng)過1500+次訓練后，學習到了382種狀態(tài)，還有2種沒學到，可能需要更多輪訓練，也可能不需要，人工智能算法都達不到絕對穩(wěn)定。

折扣因子gamma去哪了

智能車在行駛過程中只知道目的地的大方向，不知道距離目的地的距離，因此下一個狀態(tài)是不知道的，且起點和終點也不固定，因此用gamma是沒有意義的。