基于時間差分出租車智能規(guī)劃研究

張南楠，童 林，唐倩倩

（1.貴州電子信息職業(yè)技術(shù)學(xué)院，貴州 凱里 556000；2.六盤水師范學(xué)院，貴州 六盤水 553004）

引言

針對當(dāng)前的出租車運輸體系，主要存在如下問題。出租車空載率高。在一些大型城市，例如北京、廣州，每天空駛距離在40%左右[1]。如此高的比例，必然占用了社會道路交通的資源，造成路面擁堵，大氣污染，也阻礙了出租車駕駛員的收益。對于出租車運營管理不全面和不規(guī)范，導(dǎo)致存在司機(jī)拒載，違規(guī)拼車，故意繞路的情況，而乘客往往很難取證投訴，或者投訴之后沒有得到及時的反饋，導(dǎo)致整個出租車行業(yè)形象受損，惡性循環(huán)，使得出租車行業(yè)整體的發(fā)展受到阻礙[2]。

近年來很多國內(nèi)外研究者針對以上問題均開展了一系列研究，2017年，肖露艷[3]提出了一種基于啟發(fā)式搜索的夜間公交路線生成算法進(jìn)行夜間公交路線規(guī)劃。同年，由大連理工大學(xué)的張翔[4]收集到的出租車上下客GPS 數(shù)據(jù)進(jìn)行預(yù)處理，篩選出超時顧客的出行數(shù)據(jù)。提出了DBSCAN-PAM 混合聚類算法，選擇地球球面距離作為聚類算法中的相似度，從而提升聚類的精度，使用基本遺傳算法規(guī)劃最優(yōu)路線，目的使班車行駛距離最短。Lam 等人[5]提出了基于歷史數(shù)據(jù)的及時響應(yīng)方法。在當(dāng)前的交通信息和歷史數(shù)據(jù)沒有明顯變化時，按照之前的路線。Lin Jing Jie[6]提出了一種基于集合算子的模擬二元交叉的進(jìn)化多目標(biāo)拼車算法，此方法有效的減少了司機(jī)因拼客繞路帶來的資源利用不合理問題。以上算法雖然在一定程度上改進(jìn)了出租車資源利用不合理的問題，但是算法相對復(fù)雜，本文結(jié)合目前出租車智能規(guī)劃算法優(yōu)點的基礎(chǔ)上，引進(jìn)時間差分算法，對比其他算法的優(yōu)劣，設(shè)計構(gòu)造出出租車智能規(guī)劃仿真模型，實現(xiàn)出租車的智能規(guī)劃，以一片特定區(qū)域為標(biāo)本，通過爬蟲的方式獲取一定時間內(nèi)的真實數(shù)據(jù)，驗證模型的可靠性和高效性，發(fā)展不足和模型補(bǔ)充，實現(xiàn)出租車、乘客、社會資源的高效利用和利益最大化。

1 時間差分方法的基本思想

在機(jī)器學(xué)習(xí)的眾多模型中[7]，馬爾可夫決策過程是重要的數(shù)學(xué)模型之一，通過在該過程使用動態(tài)規(guī)劃、隨機(jī)采樣等方法，其可以求解使回報最大化的智能體策略，并在自動控制、推薦系統(tǒng)等主題中得到應(yīng)用。該過程主要由兩部分組成，其中一部分被稱為基于模型的動態(tài)規(guī)劃方法，在該方法下區(qū)分有策略迭代、值迭代、策略搜索等方法，其另一部分被稱作無模型的強(qiáng)化學(xué)習(xí)方法[8]，常見的有蒙特卡洛方法和時間差分方法（TD 方法）。作為一個被廣泛用于強(qiáng)化學(xué)習(xí)領(lǐng)域的方法，時間差分方法是強(qiáng)化學(xué)習(xí)理論中最重要的內(nèi)容，時間差分方法的核心思想可以用文字寫作為：

時間差分法是一個自展的算法[9]，意味著它可以運用估計的方法，針對前后兩個狀態(tài)值，可以用前一個狀態(tài)的估計值去預(yù)測另一個狀態(tài)的值。式中[target-OldEstimate]代表誤差，隨著智能個體不斷學(xué)習(xí)，能夠不斷縮小誤差值。StepSize 稱作學(xué)習(xí)率，范圍介于[0，1]，0 代表沒有學(xué)習(xí)，1 代表僅僅用了最近一步的信息，學(xué)習(xí)率會隨著時間增加而降低，直到飽和。

時間差分學(xué)習(xí)由蒙特卡洛算法演變而來[10]，稱之為contant-αMC，將其狀態(tài)更新值寫作：

其中Rt 稱為實際積累的累計回報，α 是學(xué)習(xí)率，式子可以看作用累積回報作為狀態(tài)函數(shù)的估計值[11]，計算st 的實際積累回報Rt 和當(dāng)前V（st）的偏差值，并用該偏差值乘學(xué)習(xí)率得到了V（st）的新估計值。為了解決蒙特卡洛算法中狀態(tài)值函數(shù)估計相互獨立[12]，需要經(jīng)驗環(huán)境的弊端，將 Rt 換成得到了 TD（0）的狀態(tài)值函數(shù)過的更新公式：

2 仿真實驗設(shè)計

2.1 實驗?zāi)Ｐ?/h3>

本次實驗基于VISUAL STUDIO 平臺，嘗試在出租車智能規(guī)劃問題使用時間差分法來解決問題，結(jié)合時間差分法中的SARSA 和Q-learning 學(xué)習(xí)方法，得出和分析實驗結(jié)果。

為了使研究更加順利，我們將實際生活中的地圖抽取出規(guī)則的一部分，抽象成方格地圖用于研究，即將研究地圖的尺寸定義為長寬相等的一塊正方形區(qū)域，可以指定其地圖的尺寸分別是 5×5，10×10，20×20 等等。以長寬分別為十個單位為例，在地圖中以白色方格代表可行走路線，黑色方格代表障礙物即不允許行走路線。如圖1，我們選擇了10×10 共100 個格子組成的區(qū)域，將每一個方格從1 一直到100 進(jìn)行編號，用文件將數(shù)據(jù)存儲。我們可以假定出發(fā)點，例如左上角的方格，設(shè)置成智能體開始行走的出發(fā)點，將右下角設(shè)置成終點，智能體出租車需要在避開障礙物，即黑色格子的前提下，尋找到達(dá)終點的最合適路線。并且在實驗的最后，能夠?qū)崿F(xiàn)任意設(shè)置一個起點，一個終點，和一系列障礙點，都能夠讓智能體出租車找到一條移動距離最短的線路。

圖1 模擬實驗圖

2.2 實驗環(huán)境

作為馬爾科夫鏈的分支，時間差分法可以遵循馬爾科夫決策過程，針對該路徑規(guī)劃問題，將馬爾科夫四元組定義：

狀態(tài)：針對10×10 共一百個格子的區(qū)域，我們用1 到100 共一百個數(shù)將其表示，狀態(tài)1 定義為左上角格子對應(yīng)的狀態(tài)，向下向右擴(kuò)展，狀態(tài)100 定義為右下角格子的狀態(tài)，進(jìn)行標(biāo)號。同時使用二值的方法，將所有障礙點設(shè)置為-1，所有可通過的點設(shè)置為1，起始點定義為0，終點定義為2。當(dāng)智能體運動過程中，一旦觸碰到障礙物，及賦值狀態(tài)為-1 的點，或智能體到達(dá)終點，即狀態(tài)賦值為2的點，則終止本次訓(xùn)練，將智能體重新選擇初始位置，進(jìn)行下一次循環(huán)訓(xùn)練。

動作：規(guī)定在每一個方格中，智能體有且只有上下左右四個動作之一，從一個格子移動到相鄰的四個方格中間的一個，不能斜向沿著對角線移動，不能跨越一個格子向被跨越格子的相鄰及更遠(yuǎn)的格子移動，每次移動都將被記錄，嘗試通過一個變量來表示和存儲這些動作。

獎勵：使用強(qiáng)化信號，對智能體的行為進(jìn)行獎勵或者懲罰。若智能體到達(dá)右下角位置，給予1 的獎勵，當(dāng)智能體到達(dá)障礙物所在的格子，會得-1 的獎勵，即懲罰。

轉(zhuǎn)移概率：假設(shè)成功按照預(yù)定進(jìn)行轉(zhuǎn)移的概率為90%，即允許智能體收到動作指令后，有一定的概率偏差，不符合動作指令的預(yù)期，其有90%的概率能夠到達(dá)指定的位置，10%的概率不按照指令運動。

2.3 實驗參數(shù)

圖2 SARSA 方法

獎勵折扣因子：獎勵折扣因子決定智能體更看重眼前的立即回報，還是看重長遠(yuǎn)的未來回報，取值介于0 和1 之間。當(dāng)獎勵折扣因子越接近于0，說明智能體是“近視”，即智能體看重當(dāng)前得到的立即回報；當(dāng)獎勵折扣因子趨近于1，即智能體看重未來回報。在路徑規(guī)劃問題中，給予一定數(shù)量的訓(xùn)練，智能體一般能夠找尋到最優(yōu)路徑，即將實驗進(jìn)行到終止?fàn)顟B(tài)，因此將獎勵折扣因子設(shè)置成0.7，未來匯報和立即回報占據(jù)的比重接近。

學(xué)習(xí)速率：學(xué)習(xí)速率是一個取值0 和1 之間的實數(shù)。在參數(shù)設(shè)置過程中，如果學(xué)習(xí)速率的值太小，速度很慢，算法遲遲不收斂；若學(xué)習(xí)速率太大，算法反應(yīng)過于劇烈，會導(dǎo)致算法收斂誤差較大獲得不正確的值。在本實驗中，將學(xué)習(xí)速率定義為0.01。

探索步數(shù)：探索步數(shù)是允許智能體移動次數(shù)的上限值，將探索步數(shù)設(shè)定在500，即允許智能體在一次訓(xùn)練中做出500 個決策并對應(yīng)運動，若在500 次之后仍然沒有到達(dá)終點，則說明這個策略是不夠優(yōu)秀的，沒有必要繼續(xù)實驗，則選擇停止當(dāng)前訓(xùn)練，重新開始下一個訓(xùn)練循環(huán)。

誤差閾值：由于時間差分法中使用的是一種迭代的思想，通過不斷迭代訓(xùn)練可以將誤差盡可能縮小，為此設(shè)定一個終止條件，按照經(jīng)驗將誤差閾值設(shè)定為1e-6。

當(dāng)前算法中不需要進(jìn)行輸入，只需要讓智能體運動，并且到達(dá)位置后給出相應(yīng)的信號，在訓(xùn)練的最后，以算法收斂或算法失敗作為一次訓(xùn)練的終止。

3 仿真結(jié)果分析

在馬爾科夫決策過程的應(yīng)用中，時間差分法具有重要應(yīng)用，包括SARSA 和Q-learning 兩種方法，本設(shè)計中主要針對這兩種方法進(jìn)行實驗。

針對路徑規(guī)劃，我們采用10×10 的格子作為實驗范圍，針對起點和終點，我們定義每次智能體向上移動，會有0.90 的概率向上移動，0.05 的概率向左移動，0.15 的概率向右移動；當(dāng)智能體向右移動時，有0.90 的概率能夠向右移動，有0.05 的概率向上和向下移動，模擬了智能體在格子世界中獲得信號之后的行動判斷，模擬了不確定性?？梢允褂镁仃嚤硎巨D(zhuǎn)移概率：

圖3 Q-learning 方法

SARSA 算法是一種on-policy 的方法。設(shè)置好起始位置后，定義一個任意的初始動作，例如向左的動作，通過智能體與環(huán)境的交互，不斷更新算法策略，獲得獎懲。在規(guī)定的探索步數(shù)智能到達(dá)指定的重點位置，獲得函數(shù)的收斂和最優(yōu)。

使用Q-learning 算法設(shè)置同樣的起始條件，它是一種off-policy 的方法，通過樣本和環(huán)境交互，與SARSA 通過下一步狀態(tài)決定下一步行動不同，Q-learning 的算法更為激進(jìn)和冒險，通常直接選擇最優(yōu)路線，同時也增大了智能體“失敗”觸碰到障礙物的危險。

由圖2 和圖3 中可以看出，針對該問題，SARSA 方法和Q-learning 方法從直觀上在大多數(shù)狀態(tài)都是最優(yōu)，策略在每一個方格中采用的策略方法基本一致。針對每一次訓(xùn)練中前后兩次策略的差值反映了每一次狀態(tài)和對應(yīng)動作產(chǎn)生的錯誤偏差，針對兩種方法的收斂速度，在同一輪訓(xùn)練中將誤差累加，就可以反映出收斂偏差，即所處的狀態(tài)和采取動作的改變情況。隨著訓(xùn)練次數(shù)的變化，誤差越來越小趨近于零，當(dāng)前輪次的訓(xùn)練策略不再改變，能夠讓值函數(shù)收斂，停止訓(xùn)練。當(dāng)數(shù)值趨近于收斂之后，SARSA 的振幅會大于Q-learning，也符合Q-learning 更為激進(jìn)的策略，即off-policy 的策略。

同時在實驗過程中，會出現(xiàn)SARSA 和Q-learning 獲得結(jié)果不同的策略，即相對次優(yōu)策略。SARSA 采取的策略相對穩(wěn)定，總是采取相對最優(yōu)的策略，而Q-learning 根據(jù)當(dāng)前策略產(chǎn)生的樣本決定當(dāng)前動作，會導(dǎo)致比較冒險而造成不夠優(yōu)秀的策略。隨著訓(xùn)練次數(shù)的增加會逐漸固定路線，從而沿著當(dāng)前路徑不斷優(yōu)化，盡管可能探索和改變，還是能夠沿著原有的路線。

4 結(jié)束語

將時間差分方法引入出租車智能路徑規(guī)劃，智能出租車通過在模擬地圖中不斷與周圍環(huán)境交互來決定自己將會采取的行動，進(jìn)而選擇當(dāng)前步驟的最優(yōu)策略，利用SARSA 和Q-learning 的方法，使智能體在模擬地圖中不斷尋找到路線，通過和環(huán)境進(jìn)行交互來選擇當(dāng)前狀態(tài)的動作，增加對環(huán)境的熟悉程度并且不斷更新路線策略。避免了傳統(tǒng)方法中收斂過早導(dǎo)致準(zhǔn)確性不夠高的情況，實現(xiàn)得到最終的最優(yōu)結(jié)果。通過模型仿真證明將時間差分法應(yīng)用在基礎(chǔ)的路徑規(guī)劃中在模擬環(huán)境中是可行的，能夠合理避開障礙物和一些模擬的需要規(guī)避的禁行區(qū)域。