張南楠，童 林，唐倩倩

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

引言

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

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

1 時(shí)間差分方法的基本思想

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

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

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

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

2 仿真實(shí)驗(yàn)設(shè)計(jì)

2.1 實(shí)驗(yàn)?zāi)Ｐ?/h3>

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

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

圖1 模擬實(shí)驗(yàn)圖

2.2 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

2.3 實(shí)驗(yàn)參數(shù)

圖2 SARSA 方法

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

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

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

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

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

3 仿真結(jié)果分析

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

針對(duì)路徑規(guī)劃，我們采用10×10 的格子作為實(shí)驗(yàn)范圍，針對(duì)起點(diǎn)和終點(diǎn)，我們定義每次智能體向上移動(dòng)，會(huì)有0.90 的概率向上移動(dòng)，0.05 的概率向左移動(dòng)，0.15 的概率向右移動(dòng)；當(dāng)智能體向右移動(dòng)時(shí)，有0.90 的概率能夠向右移動(dòng)，有0.05 的概率向上和向下移動(dòng)，模擬了智能體在格子世界中獲得信號(hào)之后的行動(dòng)判斷，模擬了不確定性。可以使用矩陣表示轉(zhuǎn)移概率：

圖3 Q-learning 方法

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

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

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

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

4 結(jié)束語(yǔ)

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