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

訓練過程.gif

需求分析

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

• 安全性
  安全性具體表現(xiàn)為遵守交通規(guī)則爆侣，避免交通事故萍程。
  假設(shè)有一個簡化的世界，路口的交通燈是老式交通燈兔仰，不帶左右轉(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)下自己的所有行動對應(yīng)的分數(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)驗可循躬它，因此探索因子應(yīng)該大一些腾啥，越往后，探索因子可適當減小冯吓，偶爾根據(jù)以往經(jīng)驗決定動作倘待，偶爾冒險決定動作。
具體在程序中的使用就是：探索因子為0-1桑谍，產(chǎn)生一個0-1的隨機數(shù)延柠，如果隨機數(shù)小于等于探索因子，則冒險锣披，大于贞间，則根據(jù)以往經(jīng)驗贿条，這樣小車的每個動作就有一定概率是冒險，一定概率是以往經(jīng)驗增热。
至此整以，動作選擇部分完畢。

具體實現(xiàn)

代碼太多且涉及優(yōu)達學城的版權(quán)峻仇，因此不貼了公黑，核心邏輯根據(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是沒有意義的靡狞。