考慮博弈的多智能體強化學習分布式信號控制

曲昭偉，潘昭天，陳永恒，李海濤，王 鑫

(吉林大學交通學院，長春130022)

0 引言

實現(xiàn)閉環(huán)反饋自適應控制的多智能體強化學習(Multi-agent Reinforcement Learning，MARL)技術為交通網(wǎng)絡信號控制領域研究提供了一種新的解決方法[1].Thorpe[2]設計了一種邊界恒定流量輸入，車輛具有速度隨機性的交通模擬器，采用車輛數(shù)、信號持續(xù)時間、距交叉口距離等因素劃分交通狀態(tài)，并討論其對SARSA算法應用于路網(wǎng)交通信號控制適用性的影響.Abdulhai等[3]設計了一個泊松到達率的四路交叉口，模擬2 h內(nèi)不同的高峰狀況，采用Q學習對相位順序和持續(xù)時間進行控制并取得良好效果，驗證了MARL在交通信號控制上的優(yōu)越性.Balaji等[4]將借鑒鄰近智能體交通數(shù)據(jù)的改進Q學習方法應用于城市交通干線分布式控制，通過對綠燈時間等參數(shù)調(diào)節(jié)，達到減少總延誤的目標.Zhu等[5]在協(xié)作多智能體框架的強化學習中嵌入節(jié)點樹算法用于對交叉口節(jié)點最優(yōu)聯(lián)合動作的精確推理，調(diào)整相序，降低擁堵，減少排放.但文獻[4-5]的方法對通信和計算等要求隨著路網(wǎng)范圍增大呈幾何增長，故基于獨立動作MARL(Independent Action Multi-agent Reinforcement Learning,IA-MARL)的分布式控制是路網(wǎng)信號控制合理選擇.

文獻[2-4]中，MARL框架的決策過程多采用貪婪搜索或softmax策略，是建立在其自身累積的歷史經(jīng)驗之上進行的，在面臨路網(wǎng)中不均衡和波動的交通需求時，反饋控制延遲是不可避免的.若要更好地響應不均衡和波動的交通需求，IAMARL的決策過程應當具有主動應對局部交通狀態(tài)變化的能力.博弈論中混合策略納什均衡求解是在不確定競爭條件下求取最優(yōu)解的方法.局部交通狀態(tài)變化可視為博弈中的不確定競爭條件，故采用混合策略納什均衡改進IA-MARL的決策過程是恰當?shù)?

本文在IA-MARL框架的基礎上，引入博弈論中混合策略納什均衡的概念改進IA-MARL的決策過程，針對改進引入JS散度定義自適應學習率，提出考慮博弈的多智能體強化學習(Multi-agent Reinforcement Learning Based on the Game,GMARL)框架，克服IA-MARL只能根據(jù)自身歷史經(jīng)驗進行決策，不能快速響應路網(wǎng)交通需求不均衡和波動的缺陷.

1 框架提出

1.1 IA-MARL

采用Q因子形式給出IA-MARL中智能體的Q因子更新過程為

1.2 G-MARL框架

為解決IA-MARL面臨路網(wǎng)中不均衡和波動的交通需求時反饋控制延遲問題，在IA-MARL基礎上，引入博弈過程改進IA-MARL的決策過程，提出G-MARL的框架，如圖1所示.

圖1給出從道路網(wǎng)絡層面到具體交叉口智能體內(nèi)部G-MARL結(jié)構(gòu)的抽象過程：(I)是道路網(wǎng)絡示例，包含6個交叉口，9個出入口，以及其間的雙向道路；(II)是道路網(wǎng)絡拓撲無向圖，節(jié)點表示智能體，無向?qū)嵕€表示智能體之間的拓撲關系；(III)是智能體鄰近關系拓撲集合簡圖，每一個鄰近關系拓撲圖都包含核心智能體(放射無向?qū)嵕€節(jié)點)、鄰近關系(無向?qū)嵕€)、非鄰近關系(無向虛線)；(IV)是智能體A4控制邏輯示例，包含3個輸入(鄰近競爭智能體混合策略集，外界環(huán)境的狀態(tài)，控制動作的回報)和1個輸出過程(控制動作)；(V)是智能體A4的G-MARL經(jīng)驗更新框架，其中，G-MARL的決策過程在1.3節(jié)中說明，G-MARL學習率的自適應設置將在1.4節(jié)中介紹.

1.3 G-MARL決策過程

基于Q的IA-MARL的決策過程是在自身經(jīng)驗Q值分布的基礎上，采用貪婪策略或玻爾茲曼探索策略對決策做出選擇.

圖1的G-MARL采用相鄰智能體的歷史經(jīng)驗Q值分布作為其混合策略分布的估計，通過求解智能體應對相鄰智能體混合策略的納什均衡解，將其作為自身決策的混合策略分布，再在該分布上通過玻爾茲曼探索做出決策.具體過程如下.

圖1 考慮博弈的多智能體強化學習(G-MARL)框架Fig.1 Framework of game-based multi-agent reinforcement learning(G-MARL)

(1)相鄰智能體的歷史經(jīng)驗Q值分布提取.從智能體i的鄰近智能體集合I-i中獲取鄰近智能體j，在面臨xj時采用aj的Q值Qj(xj,aj)分布，即

式中：Pj(aj|xj)是智能體在面臨xj時選擇aj的概率，全部的Pj(aj|xj)，aj∈Aj，Aj為智能體j的動作空間，即Pj構(gòu)成智能體j在面臨xj時的混合策略σj，σj∈σ-i，σ-i為臨近智能體集合I-i對應的混合策略集合.

(2)智能體i混合策略的納什均衡求解.在已知對手采用混合策略的預期上，采用混合策略納什均衡(Mixed Strategy Nash Equilibrium，MSNE)[6]求解智能體i的最佳混合策略為

式中：混合策略σi是交叉口智能體i在面臨xi時選擇控制動作ai在動作空間Ai上的概率分布；是智能體i同對手采用混合策略σ-i的最佳應對混合策略；ui是智能體i的收益函數(shù).

(3)智能體i的決策過程.根據(jù)智能體i的混合策略納什均衡(MS-NE)策略分布，采用玻爾茲曼探索獲取智能體i在面臨xi時執(zhí)行ai的概率，即

式中：是改進后得到的智能體i決策混合策略分布.改進后的決策機制可以通過局部的經(jīng)驗交換間接自適應全局的狀態(tài)變化，進而獲取快速適應外部環(huán)境波動的能力.

1.4 G-MARL學習率

學習率α值大小與智能體的學習速度相關，α值偏大會對學習積累經(jīng)驗遺忘，α值偏小會產(chǎn)生學習效率下降，這里采用JS散度(Jensen-Shannon divergence)結(jié)合1.3節(jié)改進的決策過程設置學習率α更新機制，賦予每一個智能體獨自的自適應學習率為

根據(jù)JS散度定義，展開式(5)為

式(6)右側(cè)第2項同樣可以采用式(7)的形式求取.這里，式(5)～式(7)中的概率分布見1.3節(jié)，Pi是智能體i在動作空間Ai(xi)上的歷史經(jīng)驗決策混合策略分布，求解方法見1.3節(jié)Pj.

JS散度可以度量概率分布和Pi的距離且具備兩種優(yōu)點：①對稱性，②具有固定的值域范圍，即[ 0,1 ].根據(jù)優(yōu)點②采用JS散度值更新智能體的學習率是可行的.此外，優(yōu)點①則可以忽略由于兩個概率分布的對比位置帶來不對稱性的影響，使概率分布之間的差異性得到統(tǒng)一描述.

因此，引入JS散度定義學習率，不僅可以賦予每一個智能體以自適應的學習率，還可以度量智能體自身的歷史經(jīng)驗和對局部環(huán)境的經(jīng)驗估計之間的差異，使智能體能夠自我調(diào)節(jié)經(jīng)驗更新速度.此外，該方法還能夠提升智能體對外部環(huán)境變化的敏感度.

2 路網(wǎng)分布式信號控制的參數(shù)配置

使車輛在路網(wǎng)中暢通行駛，降低車輛行程時間是路網(wǎng)分布式信號控制的主要目標.為合理驗證G-MARL的有效性，避免在路網(wǎng)分布式信號控制應用中狀態(tài)空間、動作空間劃分等定義差異的影響，將用于路網(wǎng)分布式信號控制的IA-MARL和G-MARL相應參數(shù)統(tǒng)一定義.受數(shù)值模擬計算資源限制，道路網(wǎng)絡分布式控制中應用G-MARL和IA-MARL需降低空間復雜度：智能體狀態(tài)空間(交通狀態(tài)劃分)需要簡化，智能體的動作空間(信號控制策略集合)需要簡化.

2.1 狀態(tài)空間劃分

假設路網(wǎng)中的信號控制交叉口均為四路交叉口，則智能體i面臨的交通狀態(tài)可用向量表示，進口道d的狀態(tài)分量表示交叉口d方向進口道的路段交通狀態(tài)，d∈{e ,w,s,n}，e,w,s,n分別表示東、西、南、北進口道，構(gòu)建公式為

式中：ρd為交叉口d方向進口道路段上車輛數(shù)占比；yji為路段lji上車輛數(shù)；為路段lji容納最大車輛數(shù)，j∈I-i；free、resistance和jam分別表示自由態(tài)、阻塞態(tài)和擁堵態(tài)3種交通狀態(tài).取自由態(tài)臨界指標φfree=0.5，擁堵態(tài)臨界指標φjam=0.8對道路面臨的交通狀態(tài)進行簡單劃分.

2.2 動作空間劃分

根據(jù)文獻[7]，動作空間Ai的結(jié)構(gòu)如圖2所示，將智能體i在交叉口的控制動作定義為：，即選擇行駛方向(道路1、2)，同一組不同且不沖突的車流行駛方向(環(huán)2)構(gòu)成的信號控制相位.

這里需要注意的是：G-MARL和IA-MARL均采用無周期無固定相序信號控制優(yōu)化方式，路網(wǎng)各智能體間隔固定時間并行控制路網(wǎng)中各個交叉口信號相位變化

圖2 雙環(huán)相位結(jié)構(gòu)Fig.2 Phase structure of dual-ring

2.3 收益函數(shù)

智能體i面臨xi執(zhí)行ai且鄰近智能體I-i面臨狀態(tài)x-i執(zhí)行聯(lián)合動作a-i的收益函數(shù)為

2.4 回報函數(shù)

為實現(xiàn)對智能體i控制效果的評估，智能體i面臨xi時執(zhí)行ai的回報函數(shù)ri(xi,ai)定義為智能體i控制交叉口相鄰路段車輛數(shù)改變值Δyji的函數(shù)，即

2.5 其他參數(shù)

在G-MARL的應用中，貼現(xiàn)率γ體現(xiàn)了智能體對短期收益與長期收益之間關注程度的差異，本文不針對貼現(xiàn)率進行分析，將其取固定值0.5.

同理，IA-MARL的貼現(xiàn)率也設置為0.5，采用最佳學習率α=0.01.

3 數(shù)值模擬實驗場景配置及結(jié)果分析

實驗選用的道路網(wǎng)絡結(jié)構(gòu)及在路網(wǎng)中行駛車輛可行路徑示意圖如圖3所示.數(shù)值模擬實驗通過MATLAB編程實現(xiàn).采用兩種指標評價控制效果：單位行程時間，即車輛在每公里的行程時間(s/km)；單位車均延誤，即車輛在每公里的延誤時間(s/km).

圖3 實驗路網(wǎng)結(jié)構(gòu)及路徑提取示意圖Fig.3 Sketch of grid network and travel route

3.1 路網(wǎng)場景選取

合理選用路網(wǎng)規(guī)模，既降低計算資源消耗，又充分體現(xiàn)交叉口之間相互作用關系.采用3×3的格子網(wǎng)絡作為數(shù)值模擬實驗中的道路網(wǎng)絡，具體結(jié)構(gòu)及節(jié)點編號如圖3(a)所示.圖3(a)中：編號I表示交叉口節(jié)點，編號OD表示路網(wǎng)出入節(jié)點，各節(jié)點之間的無向線段表示雙向行駛道路，長度為1 000 m，通行能力為2 400 pcu/h.

3.2 轉(zhuǎn)向比設置

道路網(wǎng)絡中，交通流到達情況是隨機的，不能簡單地采用固定轉(zhuǎn)向比配置各交叉口，故根據(jù)OD目的地對轉(zhuǎn)向比進行分析，以圖3(b)為例.

(1)獲取到的交通流為OD4-OD7；

(2)將OD4-OD7中的可行路段全部提取出來，較遠徑上的路段用虛線表示，即圖3(b)中I；

(3)假設路網(wǎng)中行駛的車輛無繞行行為，避免車輛在路網(wǎng)繞行導致仿真結(jié)果偏差；

(4)排除繞路行為路徑，用以OD4為起點、OD7為終點的有向無環(huán)圖(圖3(b)中II)表示全部可能的行駛路徑；

(5)假設OD4-OD7方向的車輛以等概率行駛在圖3(b)中II的3條路徑上.

以上述方法，定義OD4-OD7方向車輛在交叉口I2行駛向I3和I5的概率均為0.5.交叉口I的轉(zhuǎn)向比根據(jù)各行駛方向車輛的轉(zhuǎn)向累積比例求得.

3.3 輸入流量設置

對比G-MARL和IA-MARL方法對交通需求波動的控制效果，在不均衡輸入流量的前提下采用泊松到達率作為應用場景.對圖2(a)中的格子網(wǎng)絡的輸入流量進行設置，具體流量流向如表1所示.在表1中，各OD方向的流量為泊松分布到達率輸入的均值.此外，以表1流量為基準流量，采用0.5～3.0作為比例系數(shù)對輸入流量進行調(diào)節(jié)，進一步分析G-MARL和IA-MARL方法關于流量輸入的敏感性.

表1 格子網(wǎng)絡各端點OD流量Table 1 OD flow at each endpoint of grid network

3.4 實驗結(jié)果分析

數(shù)值模擬運行3 600 s，為避免路網(wǎng)加載對評價結(jié)果造成偏差，剔除1～1 200 s的輸出結(jié)果.在基準流量輸入下，IA-MARL和G-MARL在行程時間和延誤方面的控制效果分別如圖4和圖5所示.關于流量輸入變化敏感性，IA-MARL和G-MARL在行程時間和延誤上的表現(xiàn)如圖6和圖7所示.

圖4 IA-MARL和G-MARL控制效果對比圖(單位行程時間)Fig.4 Comparison of results between IA-MARL and G-MARL(Unit travel time)

圖5 IA-MARL和G-MARL控制效果對比圖(單位車均延誤)Fig.5 Comparison of results between IA-MARL and G-MARL(Unit vehicle average delay)

圖6 IA-MARL和G-MARL的流量輸入敏感性(單位行程時間)Fig.6 Sensitivity of IA-MARL and G-MARL to flow input(Unit travel time)

圖7 IA-MARL和G-MARL的流量輸入敏感性(單位車均延誤)Fig.7 Sensitivity of IA-MARL and G-MARL to flow input(Unit vehicle average delay)

從圖4可見，G-MARL在單位行程時間上較IA-MARL累積改善59.94%.據(jù)圖5可知，G-MARL在單位車均延誤上較IA-MARL累積改善81.45%.分析圖6和圖7，隨著流量輸入的增長，G-MARL相對IA-MARL在單位行程時間和單位車均延誤方面改善效果均呈現(xiàn)先提升后下降的趨勢：①低流量輸入，交通需求低，路網(wǎng)暢通，G-MARL的改善效果不明顯；②中流量輸入，交通需求增長，路網(wǎng)承壓，G-MARL改善效果顯著；③高流量輸入，交通需求接近或超過道路通行能力且不均衡性和波動性降低，路網(wǎng)趨近飽和及過飽和，G-MARL和IA-MARL控制效果相近，微弱改善.驗證了GMARL方法能夠較好地應對道路網(wǎng)絡中不飽和情況下不均衡且波動的交通需求.

4 結(jié)論

本文研究交通需求不均衡和產(chǎn)生波動時對應的道路網(wǎng)絡信號分布式控制問題，針對IA-MARL決策只依據(jù)自身歷史經(jīng)驗，不能快速響應路網(wǎng)交通需求不均衡和波動的缺陷，考慮對局部網(wǎng)絡交通狀態(tài)獲取，提出基于G-MARL框架的道路網(wǎng)絡信號分布式控制方法，設計實驗道路網(wǎng)絡進行數(shù)值模擬仿真.通過仿真結(jié)果，分析網(wǎng)絡單位行程時間和單位車均延誤的變化情況，在路網(wǎng)OD流量輸入不均衡時，分析采用IA-MARL和G-MARL的兩種分布式控制方法在0.5～3.0倍流量輸入條件下對路網(wǎng)的控制效果，驗證了G-MARL框架的有效性，即應用基于G-MARL的分布式信號控制能夠有效降低車輛在不飽和且交通需求不均衡和波動的城市路網(wǎng)中的單位行程時間和單位車均延誤.