羅飛，白夢(mèng)偉

（華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海 200237）

0 引言

隨著汽車行業(yè)的快速發(fā)展和城市出行人口的增多，交通情景問(wèn)題復(fù)雜度越來(lái)越高，如何在復(fù)雜的交通情景下作出決策成為一個(gè)熱點(diǎn)問(wèn)題［1］。交通情景問(wèn)題涉及多種領(lǐng)域，如道路改建、擁堵預(yù)測(cè)、路徑規(guī)劃、信號(hào)燈控制等。其中，不良的路徑規(guī)劃和信號(hào)燈控制決策可能導(dǎo)致長(zhǎng)時(shí)間的交通延遲、車輛擁堵、額外的車輛燃油消耗和環(huán)境污染，受到了許多研究人員的關(guān)注。

面對(duì)路徑規(guī)劃問(wèn)題，目前的解決思路包括基于索引的A*（Index Based A Star，IBAS）算法［2］、Floyd-A*算法［3］、基于動(dòng)態(tài)圖的K條最短路徑（KShortest Paths in Dynamic Graphs，KSP-DG）［4］算法等。其中，IBAS 算法對(duì)傳統(tǒng)的A*算法［5］進(jìn)行了改進(jìn)，為每個(gè)頂點(diǎn)構(gòu)造了三個(gè)索引，以處理未知頂點(diǎn)坐標(biāo)對(duì)路徑規(guī)劃的影響，然而難以滿足更復(fù)雜的路徑規(guī)劃需求；Floyd-A*算法分為基于A*算法的行程查找器和基于Floyd 算法［6］的成本估計(jì)器兩部分，用于處理最短時(shí)間的行程規(guī)劃問(wèn)題，然而計(jì)算效率有待提高；KSP-DG 算法改進(jìn)了K條最短路徑（KShortest Paths，KSP）算法［7］，將圖劃分為多個(gè)子圖進(jìn)行處理，使算法可部署于分布式環(huán)境，然而在未知條件下的表現(xiàn)能力有限［8］。另外，由于針對(duì)路徑規(guī)劃問(wèn)題設(shè)計(jì)的算法難以遷移到其他優(yōu)化問(wèn)題中，應(yīng)用范圍具有局限性。

面對(duì)交通信號(hào)燈控制決策問(wèn)題，目前常用的決策方法包括自組織的交通燈（Self-Organizing Traffic Lights，SOTL）算法［9］、最大壓力算法［10］等。其中，SOTL 算法在得知當(dāng)前道路上紅燈車輛等待數(shù)量、綠燈車輛行駛數(shù)量信息后，基于最小相位時(shí)間、相位改變閾值等超參數(shù)，選擇后續(xù)的交通信號(hào)相位動(dòng)作；該算法依賴的超參數(shù)較多，經(jīng)驗(yàn)性的參數(shù)取值容易導(dǎo)致最終結(jié)果的不確定性，且無(wú)法適應(yīng)動(dòng)態(tài)環(huán)境。最大壓力算法根據(jù)當(dāng)前的交通環(huán)境計(jì)算各個(gè)交通信號(hào)相位的車流壓力，之后選擇具有最大壓力的相位作為后續(xù)的動(dòng)作；然而該算法本質(zhì)上屬于貪心算法，在求解過(guò)程中容易陷入局部最優(yōu)，最終的方案具有一定的局限性。

針對(duì)以上算法在路徑規(guī)劃問(wèn)題、交通信號(hào)燈控制問(wèn)題中表現(xiàn)能力有限、需要經(jīng)驗(yàn)知識(shí)等問(wèn)題，近年來(lái)，研究者提出利用強(qiáng)化學(xué)習(xí)算法來(lái)解決上述問(wèn)題。其中，文獻(xiàn)［11］使用Q-Learning 算法解決交通信號(hào)燈控制問(wèn)題，但是需要合理設(shè)計(jì)馬爾可夫決策過(guò)程（Markov Decision Process，MDP），以提高算法的表現(xiàn)能力；文獻(xiàn)［8］基于Dyna 算法［12］，利用Sarsa 算法在行為選擇上較為保守的特性，減少了路徑規(guī)劃問(wèn)題中車輛的碰撞次數(shù)，但實(shí)驗(yàn)基于靜態(tài)交通環(huán)境，未討論動(dòng)態(tài)變化情況下的交通情景問(wèn)題決策；文獻(xiàn)［13-15］使用深度強(qiáng)化學(xué)習(xí)算法，分別基于改進(jìn)深度Q 網(wǎng)絡(luò)的NDQN（improved Deep Q Network）算法、多智能體的自適應(yīng)交通信號(hào)控制器集成網(wǎng)絡(luò)（Multi-Agent Reinforcement Learning for Integrated Network of Adaptive Traffic Signal Controllers，MARLIN-ATSC）算法、最大壓力的MPLight 算法，解決交通信號(hào)燈控制問(wèn)題；然而，深度強(qiáng)化學(xué)習(xí)算法在解決交通信號(hào)燈控制問(wèn)題上的計(jì)算時(shí)間成本較高、建模復(fù)雜，需要通過(guò)大量的樣本學(xué)習(xí)，無(wú)法快速得到解決方案。

深度強(qiáng)化學(xué)習(xí)算法存在計(jì)算速度慢和建模復(fù)雜的問(wèn)題，而傳統(tǒng)強(qiáng)化學(xué)習(xí)算法基于表格形式的價(jià)值估計(jì)［16］，在建模和計(jì)算速度上具有優(yōu)勢(shì)，但由于傳統(tǒng)強(qiáng)化學(xué)習(xí)算法與環(huán)境之間存在交互成本、動(dòng)作選擇策略、收斂速度和精度等問(wèn)題，需要改進(jìn)。已有的改進(jìn)算法中，快速Q(mào) 學(xué)習(xí)（Speedy QLearning，SQL）［17］、連續(xù)過(guò)松弛Q 學(xué)習(xí)（Successive Over-Relaxation Q-Learning，SOR Q-Learning）［18］、廣義快速Q(mào) 學(xué)習(xí)（Generalized SQL，GSQL）算法［19］沒(méi)有考慮到交互成本和動(dòng)作選擇策略；Dyna-Q 算法建立了環(huán)境模型，通過(guò)集成學(xué)習(xí)、規(guī)劃與交互，降低了交互成本［12］，但仍然使用貪婪策略作為動(dòng)作選擇方式，且Q函數(shù)的更新仍然采用傳統(tǒng)的Q-Learning算法方式，具有改進(jìn)空間。

本文將Dyna-Q 算法中環(huán)境模型設(shè)計(jì)為經(jīng)驗(yàn)池，并針對(duì)動(dòng)作選擇構(gòu)建一種直接策略，基于GSQL 算法提出一種結(jié)合了經(jīng)驗(yàn)池技術(shù)和直接策略的改進(jìn)強(qiáng)化學(xué)習(xí)算法——GSQLDSEP（Generalized Speedy Q-Learning with Direct Strategy and Experience Pool），以加快算法的收斂和提高收斂精度；之后將GSQL-DSEP 算法應(yīng)用到出租車司機(jī)搭乘問(wèn)題中，縮短搭乘決策的路徑長(zhǎng)度；隨后通過(guò)城市交通仿真（Simulation of Urban Mobility，SUMO）軟件仿真交通信號(hào)燈系統(tǒng)，構(gòu)建出離散環(huán)境下的馬爾可夫決策過(guò)程，并應(yīng)用GSQL-DSEP 算法，減少交通信號(hào)燈系統(tǒng)中車輛的整體等待時(shí)間。

1 強(qiáng)化學(xué)習(xí)算法優(yōu)化

1.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)的執(zhí)行過(guò)程是智能體與環(huán)境不斷交互的過(guò)程，用于解決馬爾可夫決策過(guò)程建模的問(wèn)題。一般情況下，馬爾可夫決策過(guò)程包含了S、A、R、P 在內(nèi)的四個(gè)要素。其中，S 為智能體的狀態(tài)表示，A 為智能體的行為表示，R 為環(huán)境的獎(jiǎng)勵(lì)概率函數(shù)表示，P 為環(huán)境的狀態(tài)轉(zhuǎn)移概率函數(shù)表示。強(qiáng)化學(xué)習(xí)算法的智能體最直接的學(xué)習(xí)目標(biāo)是在與環(huán)境不斷交互中產(chǎn)生最大的累積獎(jiǎng)勵(lì)。智能體和環(huán)境的交互如圖1所示。

圖1 智能體和環(huán)境的交互示意圖Fig.1 Schematic diagram of interaction between agent and environment

智能體和環(huán)境的交互任務(wù)可以分為無(wú)限時(shí)長(zhǎng)交互和回合式交互，而無(wú)限時(shí)長(zhǎng)交互可轉(zhuǎn)換為最大時(shí)長(zhǎng)為T的回合式交互以便統(tǒng)一表示。在一個(gè)時(shí)間周期T內(nèi)，智能體在時(shí)刻t獲取到獎(jiǎng)勵(lì)rt后，該時(shí)刻下智能體未來(lái)能夠獲取到的獎(jiǎng)勵(lì)和Gt如式（1）所示。其中，由于尚未得到的獎(jiǎng)勵(lì)常常具有不確定性，且遠(yuǎn)離時(shí)刻t時(shí)不確定性更大，因此式（1）一般添加衰減因子γ，以逐次降低未來(lái)獎(jiǎng)勵(lì)的權(quán)重。

智能體在時(shí)刻t作出的行為選擇傾向于能夠獲取最大的Gt。定義智能體在狀態(tài)s和行為a下，獲得的未來(lái)獎(jiǎng)勵(lì)和的期望為Qπ，則最終得到的貝爾曼公式如式（2）所示，對(duì)應(yīng)的貝爾曼最優(yōu)公式如式（3）所示，其中p為狀態(tài)轉(zhuǎn)移概率函數(shù)，π為策略選擇概率函數(shù)。通過(guò)貝爾曼最優(yōu)公式，可以得到強(qiáng)化學(xué)習(xí)算法中Q-Learning 的更新公式如式（4）所示。

其中：α(s，a)為學(xué)習(xí)率；r為獎(jiǎng)勵(lì)值；s′為下一個(gè)狀態(tài)；a′為下一個(gè)行為。

1.2 本文算法GSQL-DSEP

本文提出一種利用直接策略和經(jīng)驗(yàn)池技術(shù)的廣義快速Q(mào) 學(xué)習(xí)算法（GSQL-DSEP）。在該算法中，利用優(yōu)化的貝爾曼公式和快速Q(mào) 學(xué)習(xí)以加快算法收斂；引入經(jīng)驗(yàn)池技術(shù)提高智能體交互經(jīng)驗(yàn)的利用率；使用直接策略提高行為選擇的均勻性。GSQL-DSEP 算法描述如下。

1.2.1 基于優(yōu)化貝爾曼公式的快速Q(mào)學(xué)習(xí)機(jī)制

Q-Learning 算法的一種改進(jìn)方法是使用兩個(gè)連續(xù)的“行為-價(jià)值”函數(shù)［17］，本文借鑒該思想以獲得比標(biāo)準(zhǔn)Q-Learning算法更快的收斂速度。定義在時(shí)刻k的Q函數(shù)為Qk，使用連續(xù)的“行為--價(jià)值”函數(shù)的快速Q(mào) 學(xué)習(xí)算法在更新過(guò)程中使用更新公式（5）～（6）。其中式（6）表示更新過(guò)程的最終規(guī)則，使用時(shí)依賴于式（5）的“行為-價(jià)值”函數(shù)。

Q-Learning 算法的另一種改進(jìn)方法是使用優(yōu)化的貝爾曼公式［18］，通過(guò)添加松弛量得到的Q函數(shù)更新公式如式（7）所示：

其中：參數(shù)w為松弛量，取值范圍在0 到w*之間。w*的計(jì)算方式如式（8）所示：

將優(yōu)化的貝爾曼公式和連續(xù)的“行為-價(jià)值”函數(shù)相結(jié)合，可進(jìn)一步提高Q-Learning 算法的收斂效果［19］。本文借鑒該思想，最終GSQL-DSEP 算法使用的Q函數(shù)更新公式如式（9）～（10）所示（算法1 中第7）行和第12）行使用該Q函數(shù)更新方法）：

其中：Qk+1表示k時(shí)刻需要計(jì)算的Q函數(shù)；Qk和Qk-1分別對(duì)應(yīng)前一時(shí)刻的Q′和前二時(shí)刻的Q"。

1.2.2 經(jīng)驗(yàn)池技術(shù)

Dyna-Q 算法提出了學(xué)習(xí)、規(guī)劃和交互進(jìn)行集成的思想［12］，本文借鑒該思想，設(shè)計(jì)了經(jīng)驗(yàn)池用于規(guī)劃與交互。經(jīng)驗(yàn)池的表示使用數(shù)組形式，初始化時(shí)即分配完整存儲(chǔ)空間，并計(jì)算空間使用量和存儲(chǔ)位置索引。存儲(chǔ)過(guò)程在智能體作出決策并獲得下一個(gè)狀態(tài)后，將該次所經(jīng)歷的狀態(tài)、行為、下一個(gè)狀態(tài)和獎(jiǎng)勵(lì)進(jìn)行打包，存儲(chǔ)到數(shù)組中，然后更新存儲(chǔ)位置索引和空間使用量。采樣過(guò)程對(duì)應(yīng)模擬經(jīng)驗(yàn)的生成，依據(jù)空間最大使用量，生成隨機(jī)索引從而獲取對(duì)應(yīng)的經(jīng)驗(yàn)信息。

基于經(jīng)驗(yàn)池技術(shù)的GSQL-DSEP 算法結(jié)構(gòu)如圖2 所示。從交互環(huán)境到實(shí)際經(jīng)驗(yàn)，然后進(jìn)行Q函數(shù)的更新，對(duì)應(yīng)算法1中第5）～8）行；從實(shí)際經(jīng)驗(yàn)利用經(jīng)驗(yàn)池進(jìn)行經(jīng)驗(yàn)存儲(chǔ)操作，然后從經(jīng)驗(yàn)池中采樣獲取模擬經(jīng)驗(yàn)，最后使用模擬經(jīng)驗(yàn)進(jìn)行Q 函數(shù)的更新，對(duì)應(yīng)于算法1 中的第9）～13）行。

圖2 GSQL-DSEP算法結(jié)構(gòu)Fig.2 Structure of GSQL-DSEP algorithm

1.2.3 直接策略

通常強(qiáng)化學(xué)習(xí)算法采用貪婪策略用于行為選擇，導(dǎo)致動(dòng)作空間過(guò)大時(shí)，指定狀態(tài)下的行為選擇不夠均勻，難以更新所有動(dòng)作的價(jià)值估計(jì)，最終算法的收斂效果不夠穩(wěn)定。

因此本文構(gòu)建一種直接策略，如以下定義所示，并將其應(yīng)用到算法1 中；算法1 中的第5）行未使用貪婪策略，而是根據(jù)Q函數(shù)使用直接策略，以提升算法行為選擇的均勻性。

直接策略：在MDP 模型中獎(jiǎng)勵(lì)通常為負(fù)值的情況下，初始化后的函數(shù)價(jià)值估計(jì)全為0 時(shí)，可直接選取當(dāng)前狀態(tài)下最大價(jià)值的行為，替代貪婪策略。

使用直接策略后，由于初始化后的Q函數(shù)價(jià)值估計(jì)全為0，則每次算法更新后，動(dòng)作的價(jià)值估計(jì)都會(huì)變小，使算法下次選擇其他動(dòng)作，而動(dòng)作估計(jì)最終會(huì)收斂到穩(wěn)定值，策略變?yōu)榇_定性的行為選取。

1.3 強(qiáng)化學(xué)習(xí)算法性能分析

1.3.1 算法測(cè)試環(huán)境

本文使用Mdptoolbox 的Python 工具包作為工具，在Windows10 操作系統(tǒng)下的Python3.7 開發(fā)環(huán)境中進(jìn)行了算法性能測(cè)試。Mdptoolbox 工具包提供了Q-Learning、策略迭代、值迭代等強(qiáng)化學(xué)習(xí)傳統(tǒng)算法，并可以生成隨機(jī)的馬爾可夫決策過(guò)程場(chǎng)景，便于實(shí)現(xiàn)算法的對(duì)比與驗(yàn)證。隨機(jī)的馬爾可夫決策過(guò)程場(chǎng)景在建立時(shí)，設(shè)定馬爾可夫決策過(guò)程中的狀態(tài)個(gè)數(shù)和動(dòng)作個(gè)數(shù)后，會(huì)獲得一個(gè)隨機(jī)的獎(jiǎng)勵(lì)函數(shù)矩陣，以及一個(gè)隨機(jī)的狀態(tài)轉(zhuǎn)移概率函數(shù)矩陣。其中，獎(jiǎng)勵(lì)函數(shù)矩陣的取值為-1～+1，為了便于GSQL-DSEP 算法在該環(huán)境中的應(yīng)用，本文將該獎(jiǎng)勵(lì)函數(shù)矩陣整體減1，使得取值為-2～0。Mdptoolbox 生成的隨機(jī)場(chǎng)景將具體問(wèn)題進(jìn)行了抽象和歸納，相較于特定應(yīng)用場(chǎng)景而言更具有代表性。本文以Mdptoolbox 生成的隨機(jī)場(chǎng)景為算法的測(cè)試和對(duì)比環(huán)境，以增強(qiáng)實(shí)驗(yàn)對(duì)比結(jié)果的準(zhǔn)確性和可靠性。

1.3.2 評(píng)估比對(duì)方法

本文對(duì)比了Q-Learning算法、SQL算法、GSQL算法、Dyna-Q 算法和改進(jìn)的GSQL-DSEP 算法?？紤]到算法對(duì)比的公平性，本文參考了GSQL 算法在實(shí)驗(yàn)中選取的超參數(shù)，同樣選取狀態(tài)個(gè)數(shù)為10，動(dòng)作個(gè)數(shù)為5，每個(gè)回合長(zhǎng)度為100，執(zhí)行回合數(shù)為1 000，算法的選擇折扣因子γ為0.6，松弛量w為w*；考慮到算法對(duì)比的準(zhǔn)確性，本文的評(píng)估對(duì)比實(shí)驗(yàn)進(jìn)行了100 次，以最優(yōu)價(jià)值和Q函數(shù)計(jì)算得到估計(jì)價(jià)值的歐氏距離平均值作為度量方式。假定時(shí)刻t下共有狀態(tài)個(gè)數(shù)為N，使用q表示測(cè)試算法得到的價(jià)值估計(jì)函數(shù)，使用v*表示最優(yōu)的價(jià)值估計(jì)函數(shù)，則時(shí)刻t的測(cè)試算法誤差可以表示為：

假定第i次實(shí)驗(yàn)下的時(shí)刻t得到的誤差為，并假定100 次實(shí)驗(yàn)在時(shí)刻t得到的誤差平均值為，則本文最終使用均方誤差度量方式如式（12）所示：

1.3.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中，本文提出的GSQL-DSEP 算法需要使用經(jīng)驗(yàn)池，因此首先對(duì)經(jīng)驗(yàn)池的參數(shù)選取進(jìn)行了實(shí)驗(yàn)。在經(jīng)驗(yàn)池大小為20 000，選取經(jīng)驗(yàn)池采樣數(shù)量為1、3、5 時(shí)的GSQL-DSEP 算法結(jié)果如圖3 所示；在采樣數(shù)量為3，經(jīng)驗(yàn)池大小為20、200、2 000、20 000時(shí)的GSQL-DSEP 算法結(jié)果如圖4所示。從圖3～4 可以看出：采樣數(shù)量對(duì)GSQL-DSEP 算法的影響較大，而經(jīng)驗(yàn)池大小對(duì)GSQL-DSEP 算法影響較小。由于采樣數(shù)量的增加額外增加了計(jì)算成本，而經(jīng)驗(yàn)池大小在該測(cè)試中體現(xiàn)出的算法性能差異不明顯，綜合考慮適用性、計(jì)算成本和環(huán)境的差異性可能對(duì)算法產(chǎn)生的影響等，在后續(xù)不同的實(shí)驗(yàn)環(huán)境中，仍需進(jìn)行不同參數(shù)下的實(shí)驗(yàn)和具體參數(shù)的選定。

圖3 不同采樣數(shù)量下GSQL-DSEP算法表現(xiàn)Fig.3 Performance of GSQL-DSEP algorithm under different sampling numbers

圖4 不同經(jīng)驗(yàn)池大小下GSQL-DSEP算法表現(xiàn)Fig.4 Performance of GSQL-DSEP algorithm under different experience pool sizes

圖5 為Q-Learning 算法、SQL 算法、GSQL 算法、Dyna-Q 算法和提出的GSQL-DSEP 算法的均方誤差對(duì)比結(jié)果。其中，Dyna-Q 算法和GSQL-DSEP 算法的經(jīng)驗(yàn)池大小為20 000，經(jīng)驗(yàn)池采樣數(shù)量為3。從圖5 可以看出，GSQL-DSEP 算法與最優(yōu)值之間的均方誤差更小。其中，各算法的均方誤差MSEalg（alg∈｛GSQL-DSEP，Q-Learning，SQL，GSQL，Dyna-Q｝）分別為MSEGSQL-DSEP=2.48、MSEQ-Learning=4.29、MSESQL=4.27、MSEGSQL=4.09、MSEDyna-Q=3.05。根據(jù)式（13），相較于Q-Learning、SQL、GSQL、Dyna-Q 算法，GSQL-DSEP 算法的均方誤差值分別下降了42.2%、41.9%、39.4%、18.7%。實(shí)驗(yàn)結(jié)果表明，GSQL-DSEP 算法優(yōu)于對(duì)比的其他強(qiáng)化學(xué)習(xí)算法，可提升收斂精度。

圖5 不同強(qiáng)化學(xué)習(xí)算法的均方誤差對(duì)比Fig.5 Mean square error comparison of different reinforcement learning algorithms

2 交通情景問(wèn)題決策優(yōu)化

將GSQL-DSEP 算法應(yīng)用在交通情景中，用于解決出租車司機(jī)搭乘決策優(yōu)化問(wèn)題和交通信號(hào)燈控制決策優(yōu)化問(wèn)題。

2.1 出租車司機(jī)搭乘決策優(yōu)化

出租車司機(jī)搭乘決策問(wèn)題［20］的目標(biāo)是在交通環(huán)境中提供一套搭乘決策，最小化行駛路徑?jīng)Q策長(zhǎng)度。目前，該問(wèn)題由OpenAI 組織進(jìn)行了封裝和重新實(shí)現(xiàn)，以gym 工具包作為該問(wèn)題的調(diào)用接口。如圖6 為出租車司機(jī)搭乘環(huán)境的示意圖。其中，出租車使用半圓表示，且在5 × 5 網(wǎng)格中的初始位置隨機(jī)；RGBY（對(duì)應(yīng)紅色、綠色、藍(lán)色、黃色）四個(gè)位置隨機(jī)存放了乘客的等待位置和目的地；環(huán)境中同時(shí)也存在一些墻壁障礙。出租車需要在和環(huán)境的交互過(guò)程中，學(xué)習(xí)到載客和卸客的路徑規(guī)劃和決策。

圖6 出租車司機(jī)的搭乘環(huán)境Fig.6 Driving environment for taxi drivers

為了應(yīng)用強(qiáng)化學(xué)習(xí)策略解決出租車司機(jī)搭乘決策問(wèn)題，需要設(shè)定相應(yīng)的狀態(tài)表示、動(dòng)作表示、獎(jiǎng)勵(lì)函數(shù)和強(qiáng)化學(xué)習(xí)算法的超參數(shù)。在狀態(tài)表示的設(shè)定上，由于該環(huán)境空間大小為25，且有5 個(gè)可能的乘客位置（包括乘客在出租車內(nèi)）、4 個(gè)可能的目的地，因此最終的狀態(tài)個(gè)數(shù)為500；動(dòng)作空間、獎(jiǎng)勵(lì)函數(shù)和強(qiáng)化學(xué)習(xí)超參數(shù)的設(shè)定分別如表1～3 所示。

表1 出租車動(dòng)作空間定義Tab.1 Definition of taxi action space

表2 出租車獎(jiǎng)勵(lì)函數(shù)定義Tab.2 Definition of taxi reward function

表3 出租車超參數(shù)設(shè)定Tab.3 Hyperparameter setting for taxis

由于迭代過(guò)程累積獎(jiǎng)勵(lì)隨機(jī)性較大，因此本文取每20次迭代的平均獎(jiǎng)勵(lì)值作為評(píng)價(jià)，評(píng)估長(zhǎng)度為30，并重復(fù)10 次實(shí)驗(yàn)求取平均值作為最終的評(píng)價(jià)指標(biāo)。GSQL-DSEP 算法存在經(jīng)驗(yàn)池大小和經(jīng)驗(yàn)池采樣數(shù)量?jī)蓚€(gè)超參數(shù)，在出租車司機(jī)搭乘決策問(wèn)題中，不同的超參數(shù)對(duì)該算法的影響如圖7～8 所示。圖7 顯示了在經(jīng)驗(yàn)池采樣數(shù)量為3 的情況下，經(jīng)驗(yàn)池大小為20、200、2 000、20 000 時(shí)的平均路徑長(zhǎng)度變化。從圖7可以看出，不同的經(jīng)驗(yàn)池大小對(duì)前期的收斂速度具有一定影響，更大的經(jīng)驗(yàn)池對(duì)收斂速度具有部分提升作用，但對(duì)最終的收斂結(jié)果影響不大。圖8 顯示了在經(jīng)驗(yàn)池大小為20 000的情況下，經(jīng)驗(yàn)池采樣數(shù)量為1、3、5 時(shí)的平均路徑長(zhǎng)度變化。從圖8 可以看出，采樣數(shù)量多則收斂速度變快，但對(duì)最終的收斂結(jié)果同樣影響不大，且更多的采樣數(shù)量會(huì)引入額外的計(jì)算開銷。根據(jù)上述實(shí)驗(yàn)結(jié)果，在后續(xù)的對(duì)比實(shí)驗(yàn)中，GSQL-DSEP 算法經(jīng)驗(yàn)性地選取經(jīng)驗(yàn)池大小為20 000、采樣數(shù)量為3。

圖7 經(jīng)驗(yàn)池大小對(duì)決策路徑長(zhǎng)度的影響Fig.7 Influence of experience pool sizes on decision path length

圖8 采樣數(shù)量對(duì)決策路徑長(zhǎng)度的影響Fig.8 Influence of sampling numbers on decision path length

將傳統(tǒng)強(qiáng)化學(xué)習(xí)算法、其他改進(jìn)算法以及本文提出的GSQL-DSEP 算法應(yīng)用到該環(huán)境中，最終結(jié)果如圖9～10 所示，相應(yīng)算法的平均決策路徑長(zhǎng)度為L(zhǎng)ENalg（alg∈｛GSQL-DSEP，Q-Learning，SQL，GSQL，Dyna-Q｝）。最終結(jié)果表明，在面向最優(yōu)路徑?jīng)Q策的選取過(guò)程中，相較于Q-Learning、SQL、GSQL、Dyna-Q 算法，GSQL-DSEP 算法得到的累積獎(jiǎng)勵(lì)更高；各算法所對(duì)應(yīng)的決策路徑長(zhǎng)度分別為：LENGSQL-DSEP=13.345、LENQ-Learning=16.62，LENSQL=16.3，LENGSQL=16.16，LENDyna-Q=16.315，即GSQL-DSEP 所對(duì)應(yīng)的決策路徑最短。根據(jù)式（14），相較于Q-Learning、SQL、GSQL、Dyna-Q 算法，GSQLDSEP 算法的平均路徑長(zhǎng)度分別縮短了約19.7%、18.1%、17.4%、18.2%。結(jié)果表明，相較于傳統(tǒng)強(qiáng)化學(xué)習(xí)算法，GSQL-DSEP 算法能夠縮短出租車司機(jī)搭乘問(wèn)題中的決策路徑長(zhǎng)度。

圖9 不同算法在出租車路徑規(guī)劃中的累積獎(jiǎng)勵(lì)對(duì)比Fig.9 Comparison of cumulative reward among different algorithms in taxi path planning

圖10 不同算法決策路徑長(zhǎng)度對(duì)比Fig.10 Comparison of decision path length amongdifferent algorithms

2.2 交通信號(hào)燈控制決策優(yōu)化

交通信號(hào)燈控制決策優(yōu)化，能夠提升現(xiàn)有交通網(wǎng)絡(luò)的利用效率，減少交通系統(tǒng)中車輛的整體等待時(shí)間。本節(jié)首先在交通信號(hào)控制仿真軟件SUMO（Simulation of Urban MObility）中建立十字路口的交通信號(hào)燈控制MDP 模型，然后將強(qiáng)化學(xué)習(xí)算法應(yīng)用在交通信號(hào)燈控制問(wèn)題上，以減少車輛的等待時(shí)間。

2.2.1 交通信號(hào)燈控制MDP模型

本文首先基于點(diǎn)、邊和連接的三個(gè)配置文件生成基本的路況環(huán)境，然后使用netedit 軟件修改路徑信息，得到的仿真環(huán)境如圖11 所示，其中涉及的超參數(shù)如表4 所示。

表4 交通環(huán)境參數(shù)Tab.4 Traffic environmental parameters

圖11 信號(hào)燈控制環(huán)境Fig.11 Traffic light control environment

假定最快每1.2 秒從路口通行1 輛車，則路口最大的吞吐率為50 輛/分鐘，因此在仿真環(huán)境中出現(xiàn)的車輛頻率應(yīng)小于50 輛/分鐘。在車輛生成的過(guò)程中，考慮出現(xiàn)車輛的隨機(jī)性，因此本文使用Python 腳本在每次重置環(huán)境后，對(duì)車輛信息重新生成。

在交通信號(hào)燈控制問(wèn)題的動(dòng)作表示上，通常情況下，右轉(zhuǎn)信號(hào)燈為常綠狀態(tài)，車輛可以直接向右通行，而左轉(zhuǎn)和直行信號(hào)燈需要根據(jù)環(huán)境進(jìn)行設(shè)置。當(dāng)只有紅燈和綠燈時(shí)，原始動(dòng)作空間大小為（2 × 2）4，共256 個(gè)動(dòng)作。然而，這些動(dòng)作往往存在沖突問(wèn)題，如某車道信號(hào)燈全綠時(shí)，則對(duì)應(yīng)的左右車道信號(hào)燈應(yīng)該為紅色?；谝陨纤枷耄疚奶岢龅慕煌ㄐ盘?hào)燈控制動(dòng)作表示如表5 所示，總動(dòng)作個(gè)數(shù)減少到12，以每3個(gè)為一組，表示出右轉(zhuǎn)、直行和左轉(zhuǎn)的信號(hào)燈動(dòng)作。其中G為綠燈，R 為紅燈。在動(dòng)作切換時(shí)，為了安全行駛，本文自動(dòng)添加了黃燈作為過(guò)渡。

表5 信號(hào)燈動(dòng)作空間定義Tab.5 Definition of traffic signal action space

在交通信號(hào)燈控制問(wèn)題的狀態(tài)表示上，針對(duì)每個(gè)車道上的車輛數(shù)量，設(shè)定車輛多、中、少三種狀態(tài)。本文設(shè)定當(dāng)車輛數(shù)量小于4，則車輛為少；若車輛不小于4 且小于9，則車輛數(shù)量適中；否則車輛數(shù)量為多。由于共有四個(gè)車道，本文使用三進(jìn)制形式表示狀態(tài)，最終的狀態(tài)空間大小為81。

在交通信號(hào)燈控制問(wèn)題的獎(jiǎng)勵(lì)函數(shù)上，應(yīng)當(dāng)包含最終要解決的問(wèn)題，使最終車輛的整體等待時(shí)間最小，不出現(xiàn)車輛碰撞或急?，F(xiàn)象，且交通燈信號(hào)改變頻率不宜過(guò)快等?；谏鲜鱿敕?，本文使用的獎(jiǎng)勵(lì)函數(shù)定義如表6 所示，其中的K3在每個(gè)時(shí)間步為1，信號(hào)燈發(fā)生改變后K5為1，否則為0。

表6 信號(hào)燈控制的獎(jiǎng)勵(lì)函數(shù)定義Tab.6 Definition of reward function for traffic signal control

2.2.2 強(qiáng)化學(xué)習(xí)在交通信號(hào)燈控制中的應(yīng)用

使用GSQL-DSEP 算法和Q-Learning算法、SQL算法、GSQL 算法、Dyna-Q 算法，對(duì)設(shè)計(jì)好的MDP 模型進(jìn)行實(shí)驗(yàn)和仿真。在實(shí)驗(yàn)過(guò)程中，由于貪婪策略無(wú)法穩(wěn)定收斂，因此本文在該情景中對(duì)比的所有強(qiáng)化學(xué)習(xí)算法都采用直接策略。在經(jīng)驗(yàn)池大小的選取過(guò)程中，設(shè)定采樣數(shù)量為3，然后選取不同的經(jīng)驗(yàn)池大小進(jìn)行測(cè)試。首先，設(shè)定經(jīng)驗(yàn)池大小在200以上，算法最終累積獎(jiǎng)勵(lì)值變化較大，算法不夠穩(wěn)定；然后，設(shè)定經(jīng)驗(yàn)池大小為20 時(shí)，算法最終收斂到的累積獎(jiǎng)勵(lì)值為-103.04，性能有待提高；隨后，設(shè)定經(jīng)驗(yàn)池大小為2 時(shí)，最終收斂到的累積獎(jiǎng)勵(lì)值為-27.392，得到的結(jié)果較為理想。由于SUMO 軟件仿真和車輛生成過(guò)程的動(dòng)態(tài)性，并根據(jù)文獻(xiàn)［16］中8.3 節(jié)的分析，當(dāng)環(huán)境變化后，在過(guò)大的經(jīng)驗(yàn)池中，更舊的經(jīng)驗(yàn)數(shù)據(jù)存儲(chǔ)在經(jīng)驗(yàn)池中被采樣，影響了算法的更新過(guò)程，得到的結(jié)果具有局限性?；谏鲜鰧?shí)驗(yàn)結(jié)果，在經(jīng)驗(yàn)池采樣數(shù)量的選取過(guò)程中，設(shè)定經(jīng)驗(yàn)池大小為2 的情況下選取不同的采樣數(shù)量進(jìn)行測(cè)試。當(dāng)采樣數(shù)量為1 時(shí)，最終收斂的累積獎(jiǎng)勵(lì)為-102.743；而采樣數(shù)量為5 時(shí)，最終收斂的累積獎(jiǎng)勵(lì)為-27.292。在GSQL-DSEP 算法中，采樣數(shù)量決定了使用模擬經(jīng)驗(yàn)進(jìn)行算法更新的次數(shù)，當(dāng)使用可反映出環(huán)境動(dòng)態(tài)變化的經(jīng)驗(yàn)時(shí)，更多的更新次數(shù)有利于算法效果的進(jìn)一步提升，但計(jì)算量更大。綜合考慮算法效果和計(jì)算成本，后續(xù)選用的經(jīng)驗(yàn)池大小為2，采樣數(shù)量為3。

在面向最優(yōu)決策過(guò)程中，最終得到的每回合累積獎(jiǎng)勵(lì)如表7 所示，智能體決策下的車輛的總等待時(shí)間TIMEalg（其中，alg∈｛GSQL-DSEP，Q-Learning，SQL，GSQL，Dyna-Q｝）如表8 所示。根據(jù)式（15），相較于Q-Learning、SQL、GSQL、Dyna-Q 算法，GSQL-DSEP 算法的車輛總等待時(shí)間TIMEGSQL-DSEP分別減少了51.5%、51.5%、0%、3.4%。實(shí)驗(yàn)結(jié)果表明，相較于其他強(qiáng)化學(xué)習(xí)算法，應(yīng)用GSQL-DSEP 算法能夠獲取最大的累積獎(jiǎng)勵(lì)值，最終得出的車輛總等待時(shí)間具有更大優(yōu)勢(shì)。

表7 不同算法得到的信號(hào)燈控制最終累積獎(jiǎng)勵(lì)Tab.7 Final cumulative rewards of traffic signal control obtained by different algorithms

表8 不同算法得到的車輛總等待時(shí)間單位：sTab.8 Total waiting time of vehicles obtained by different algorithms unit：s

3 結(jié)語(yǔ)

強(qiáng)化學(xué)習(xí)算法可以解決交通情景下的出租車司機(jī)搭乘問(wèn)題和交通信號(hào)燈控制問(wèn)題。在算法方面，本文對(duì)強(qiáng)化學(xué)習(xí)算法進(jìn)行了優(yōu)化，結(jié)合了經(jīng)驗(yàn)池技術(shù)和直接策略提出了一種新的廣義快速Q(mào) 學(xué)習(xí)算法GSQL-DSEP，從算法對(duì)比實(shí)驗(yàn)可以看出，本文提出的GSQL-DSEP 算法相較于其他對(duì)比的強(qiáng)化學(xué)習(xí)算法提高了收斂精度。在應(yīng)用方面，GSQL-DSEP 算法在解決出租車司機(jī)搭乘決策優(yōu)化問(wèn)題時(shí)，縮短了搭乘決策的路徑長(zhǎng)度；在解決交通信號(hào)燈控制優(yōu)化問(wèn)題時(shí)，可獲得更高的累積獎(jiǎng)勵(lì)，得出的交通系統(tǒng)中車輛總等待時(shí)間更具優(yōu)勢(shì)。然而，GSQL-DSEP 算法仍然存在一些局限性。首先，如果應(yīng)用環(huán)境發(fā)生較大變化，則從經(jīng)驗(yàn)池中采樣的經(jīng)驗(yàn)難以模擬出變化后的環(huán)境信息，進(jìn)而導(dǎo)致后續(xù)收斂性不夠穩(wěn)定；其次，更多的采樣數(shù)量及其對(duì)應(yīng)的更新次數(shù)會(huì)引入額外的計(jì)算開銷，且算法的提升效果有限；最后，由于采用直接策略，應(yīng)用場(chǎng)景應(yīng)合理設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，保證在該算法下智能體行為選擇策略的探索性。