基于團樹傳播的強化學習交通信號協調控制的研究

吳冬，康琦，張輪，汪鐳

?

基于團樹傳播的強化學習交通信號協調控制的研究

吳冬，康琦，張輪，汪鐳

摘 要：針對當前城市交通信號控制效率低下，致使車輛在道路交叉口等待時間較長，停車次數較多等問題，提出了一種新型的基于團樹傳播算法的強化學習控制方法來協調控制網絡級交通。分別重點介紹強化學習算法與以聯合樹算法為代表的團樹傳播算法如何與交通控制相結合以及聯合樹算法是如何實現聯合動作推理的。選取24個交叉口組成的路網為研究對象，在交通仿真軟件VISSIM中進行仿真，軟件可讀取當前環境的狀態，選取車輛的平均延誤和平均停車次數作為性能指標，同時，分別與相鄰路口簡單協調的強化學習控制算法、無學習的LQF算法控制效果進行比較。

關鍵詞：交通信號控制；強化學習；團樹傳播；協調控制

0 引言

城市交通是當前社會經濟發展的重要一環，城市中心區交通運行效率的提高可以為城市

帶來巨大的效益。若僅依靠增加道路建設，不僅花費巨額的政府財政，而且隨著路網密度的增大，對于交通管理也是一大難題。所以，科學的交通管理與控制，充分發揮路網通行能力

成為解決交通問題的有效途徑。當前，國際上較為流行的交通信號控制系統有：以SCOOT和SCATS為代表的基于實時信息的集中式系統，以OPAC和RHODES為代表的利用動態尋優來獲取信號設置的系統。大部分交通模型計算復雜，大規模實施困難，而且控制系統沒有利用經驗知識來做出最優決策。

交通控制問題作為基本的決策問題，很多學者采用馬爾科夫決策過程（MDP），應用動態規劃或強化學習的方法解決信號控制問題。研究表明，強化學習對于解決諸如交通路網的動態環境問題有著較好的控制效果。交通信號的協調控制問題可以利用多智能體協調控制框架，各方學者研究了強化學習在交通信號協調控制領域的作用。

Medina等人也將Q學習應用在包含5個交叉口的干線信號控制場景中，在可變交通需求情況下針對緊急事件進行干線協調控制[1]。Medina和Benekohal一同也做了類似的研究，將Q學習應用到包含2×3和3×3個路口的近飽和路網中[2]。

本文應用聯合樹算法(JTA)獲得網絡間的聯合動作推理，基于Q學習算法，模擬24個路口組成的路網，并與相鄰路口Q值共享的簡單協調算法以及無學習的自適應算法LQF做比較。

1 強化學習

1.1 強化學習與Q學習算法

強化學習將學習看做一個不斷試探與評價的過程。智能體（agent）選擇某一動作作用于環境，環境在接受該動作后狀態發生改變，同時產生一個強化信號（獎勵或懲罰）回饋給智能體，智能體根據環境當前的狀態和強化信號再選擇下一個動作，選擇的宗旨是使收到正的回饋值（獎賞）的概率增大。強化學習基本原理圖如圖1所示：

圖1　強化學習原理圖

交通信號燈控制系統，被控對象是交通流，控制執行機構是信號燈，通過控制信號燈各相位之間的切換，達到最優控制效果。那么信號燈控制的目的就轉變為根據交通流的實際采集情況，決定是否應當切換目前正在通行的相位。

強化學習中應用最為廣泛的是Q學習算法，幾乎現有的強化學習算法都可以看作是Q學習算法的變種。Q學習算法是一個離線（Off-policy）的TD控制方法，為基于累計折扣的強化學習算法，最優動作值的估計的更新依賴于各種假設的動作，而不是根據學習策略所選擇的實際行動，行為決策與值函數的迭代是相互獨立的。

1.2 強化學習交通控制系統結構

在智能體結構中，所有元素間都有著緊密的聯系，智能體和環境之間的交互過程如圖2所示：

圖2　智能體與環境交互結構圖

智能體通過接收環境中的信息，確認包括信號燈、車輛、檢測器在內的實時狀態。學習系統根據接收到的狀態信息與獎勵信息進行知識學習，并進行動作決策，由執行器來執行控制動作。當行為作用于路口后，路口的交通狀態將改變，經過一定的時間間隔，檢測器再次將檢測到的路口狀態傳遞給智能體，并計算得到一個回報獎懲值反饋給學習系統，學習系統將根據提供的獎懲值修正更新狀態-動作對的Q值，并再次根據交通狀態進行決策。獎懲值的預測首先需要對當前狀態與上一狀態進行比較，接著執行一個模型來確定期望的性能指標的該變量。狀態-動作對的Q值更新需要利用預測的獎勵值與上一狀態的Q值。值函數能夠提供折扣的狀態-動作對的預測值。

智能體確定最優動作及學習過程是基于最優選擇的，但是Q-learning算法并不強迫智能體選擇執行最優動作。換言之，盡管策略可能一直變化，但學習過程一直是最優的。例如，智能體可以使用探索策略而非一直使用方法。

2 圖模型與交通信號協調控制

在貝葉斯網（BN）的推理中，可分為精確推理算法和近似推理算法兩類。當BN規模不大時，可以進行精確推理，即精確地計算待求變量的后驗概率[3]。我們的研究對象為24個路口，規模不算太大，因此可以采用精確推理方法。而精確推理算法主要有：多樹傳播的推理算法；團樹傳播的方法；基于組合優化的求解方法和桶消元推理算法[4]。本課題采用的是一種團樹傳播的算法：聯合樹算法。

聯合樹算法源于計算機科學中的機器學習，根據已知數據計算某個結點或一系列結點的條件概率，是解決圖模型中的推理問題的一種算法。圖模型中的條件概率推理問題和交通信號的協調控制問題在某種程度上是相通的。一種典型的計算條件概率的方法是應用最大后驗概率法，如公式（1）：

A是觀測數據，E是先驗概率，P（E|A）表示后驗概率，因為P（A）為常量，所以最大化后驗概率在一定意義上就相當于最大化聯合概率。

通過引入概率勢函數，聯合概率P（A，E）可表達為公式（2）：

其中，n表示BN網絡中的節點數。

對（2）式取對數，（1）式可等效為公式（3）：

而多智能體強化學習算法目標就是使局部Q值的加和最大化，即公式（4）：

通過比較公式（3）（4）我們發現，利用強化學習解決交通信號的協調控制問題等價于圖模型中的聯合概率最大化問題。兩者目標都是通過把整體網絡分解為若干局部子區域來優化性能且兩者都有馬爾科夫特性；在概率模型中，一個節點的條件概率依賴于其相鄰節點。而在協調圖網絡中，一個節點的行為依賴于相鄰節點的行為。應用到交通信號控制領域，一個交叉口的交通路況直接影響著相鄰路口的路況，兩個路口距離越近，對對方路口的交通影響越大。信念傳遞算法適用于協調圖問題，因為它充分利用相鄰節點間的依賴關系，而團樹傳播算法中有一種聯合樹算法正是一種可以用來解決網絡協調問題的信念傳遞算法，這也充分解釋了聯合樹算法能用于交通信號控制領域，以較好地進行聯合動作推理。

3 聯合樹算法

聯合樹算法是一種團樹傳播算法，在本文中用于強化學習的聯合動作推理環節。先將貝葉斯網絡轉化為一種二次結構（SS），再通過對二次結構的推理得到BN推理的精確結果。二次結構（SS）有兩部分構成：聯合樹（JT）和概率勢（PP）。其中聯合樹又由團集和邊集構成。概率勢就是指與團和邊相關的概率勢。JT是一種由團集C中元素和邊集S中元素連接而成的樹結構。其中，團和邊滿足JT特性，即任何兩個和之間路徑上的每個團包含在內，相鄰兩個團之間的邊= 。

聯合樹算法包含以下步驟[4]：

供水水質對水表計量準確度的影響，體現在兩個方面：①水體化學指標含量高，例如pH值在8.0以上，硫酸鹽和氯化物的含量在180mg/L以上，會導致管道內部結垢，改變正常的過水流態，繼而造成計量偏差[2]。②水體中含有雜質，例如泥沙、絲麻等，隨著時間延長，雜質積累數量增多，如果堆積在水孔附近，會減小水孔截面積，因水流速度加快影響計量準確度。

BN轉化為JT，該過程包含4步：

a. 建立Moral圖。首先找出每個節點的父節點，將同一個節點的父節點用無向邊兩兩連接，同時將有向圖改成無向圖，這樣得到的圖稱為Moral圖；

b.Moral圖的三角化。在Moral圖中添加一些無向邊,添加的原則是將圖中大于3的環的兩非相鄰節點連接起來,使得每個環含有不超過3個節點，完成Moral圖的三角化。對Moral圖的三角化其實就是對頂點的一一刪除過程；

c.確定所有的團。對上一步得到的Moral圖,找到所有團，為組成聯合樹做準備。團是三角化后Moral圖中的最大全連通子圖；

d.構造聯合樹。往上一步找到的團中添加一些邊和分隔節點就可以得到一顆聯合樹。

以24個路口組成的路網如圖3所示：

圖3　24個路口組成的路網

轉化得到的JT圖如圖4所示：

圖4　24個路口轉化成的JT

二、引入概率勢

考慮如下有向圖如圖5所示：

圖5　（a）有向圖（b）轉化后的圖

圖5（a），聯合概率如公式（6）：

P（U）表示聯合概率。

在圖5（b）的聚類圖中，我們引入一種稱為概率勢的變量來描述團的特性，

ψ(D, C) =p(D|C), ψ(C, B) = p(C|B), ψ(B, A) = p(B|A)p(A), ψ(C) = 1, ψ(B) = 1,公式（6）變為公式（7）：

三 消息傳遞過程

初始狀態下，我們令節點V和W的概率勢分別為和,分離器的概率勢為.

在前向傳遞過程（即從V向W方向傳播過程）中，如圖6所示：

圖6　消息傳遞圖

信息從節點V向下游傳播，S和W概率勢更新如公式（8）、（9）：

同理，后向傳遞從W向上游傳遞信息。概率勢更新過程如公式（10）、（11）

4 仿真結果與實驗分析

基于JTA算法的強化學習交通信號協調控制，我們采用四種相位：東-西方向直行和右轉；南-北方向直行和右轉；西-北左轉和東-南左轉；南-西左轉和北-東左轉。學習要素設計如下：

回報函數 動作定義 動作選擇策略 動作空間 狀態空間排隊長度 可變相序(a , a ) i　 j(s , s ) i　 j

其中，表示智能體i的動作，表示智能體i的狀態。為驗證本文算法的有效性，采用對比策略，同時設計出相鄰路口Q值分享的簡單協調算法、最大排隊長隊優先自適應控制LQF算法。在VISSIM中建立路網模型，建立24個路口，首先要把路網轉化為聯合樹，如上文圖4，路口通過C#.NET編程技術驅動VISSIM的COM接口，實現對路網的控制。實驗采用兩種場景，可以通過設置車流量來實現以下兩種場景

場景一：車流量適中，交通順暢

場景二：車流量較大，交通擁擠

分別得出平均延誤時間與平均停車次數，并與另外3種算法對比，如表1、表2所示：

表一　平均延誤

表二　平均停車次數

我們從整體路網的角度分析，無論是在交通順暢還是擁堵的狀態下，JTA算法的平均延誤要比相鄰路口Q值共享的平均延誤低；在場景二下，相鄰路口Q值共享算法的平均停車次數低于JTA算法，這是因為交通擁堵的情況下，JTA算法為了為了制止下游路口的交通回流，限制了上游路口的車輛流動。總之，JTA算法控制效果優于簡單的Q學習算法，JTA算法把路網當做整體，以達到整體性能最優為目標進行決策。基于簡單的Q值共享的策略，協調性差，很多情況下只能保證局部最優。

基于JTA的強化學習算法，與LQF自適應控制算法相比，路網的平均延誤明顯要低，這也反映了系統級協調控制在交通信號控制中的作用。

以上我們從系統級角度分析了各個算法的性能。下面隨機選取一個路口（假設是路口9，場景二），由得到的仿真數據，我們將JTA算法， LQF算法繪制折線圖進行單路口級比較，如圖7所示：

圖7　單路口平均延誤

由圖7可得，對于單路口的車輛平均延誤而言，基于JTA的強化學習算法還是要明顯優于沒有學習的LQF算法。

5 總結

針對傳統強化學習控制方法僅考慮局部最優，智能體間無交互或交互較少的不足，本文研究了一種基于團樹傳播的強化學習算法，加強了智能體間的交互，考慮路網的整體效益，避免了陷入局部最優。本文重點分析了聯合樹算法與交通控制的結合點，以及聯合樹算法是如何進行聯合動作推理的。通過交通仿真軟件VISSIM模擬24個交叉口組成路網，改變路網的交通流量構造出順暢、擁堵兩種場景，分別進行仿真，并與無學習的LQF算法及簡單的Q學習算法做比較，驗證了基于團樹傳播的聯合樹算法的強化學習控制方法在交通網絡協調控制問題上的合理性與有效性，為交通網絡協調控制提供了新思路。

參考文獻

[1] Medina J C, Hajbabaie, Benekohal. Arterial traffic control using reinforcement learning agents and information from adjacent intersections in the state and reward structure[C].Intelligent Transportation Systems (ITSC), 2010 13th International IEEE Conference on. IEEE, 2010: 525-530.

[2] Medina JC, Benekohal R F. Reinforcement Learning Agents for Traffic Signal Control in Oversaturated Networks[C].T&DI Congress. 2011: 14

[3] 劉俊娜.貝葉斯網絡推理算法研究[D].安徽：合肥工業大學，2007

[4] Feng Zhu, et al. A junction-tree based learning algorithm to optimize network wide traffic control[C]: A coordinated multi-agent framework. Transport. Res. Part C (2015)

Clique-Tree Propagation Based on Learning Algorithm to Optimize Network Wide Traffic Control

Wu Dong, Kang Qi, Zhang Lun, Wang Lei
(College of Electronic and Information Engineering, Tongji University, Shanghai 201804, China)

Abstract:On account of the inefficiency of current traffic signal control system,resulting in long waits and more stops for most vehicles at the road intersections, this paper propose a novel reinforcement learning algorithm based on clique-tree propagation to optimize network wide traffic control.We focuses on how reinforcement learning and junction tree algorithm ,a typical Clique tree propagation algorithm,combined with traffic signal control and how the Junction tree algorithm achieve joint action reasoning. The algorithm is testd with a network containing 24 intersections,simulated in VISSIM, a traffic simulation software which can read the current state of the environment,choose the average vehicle delay and average number of stops as performance indicator.We also compare with simple reinforcement learning control algorithm which intersections coordinated with neighborhood and LQF algorithm.

Key words:Traffic Signal Control; Reinforcement Learning; Clique Tree Propagation; Coordinated Control

收稿日期：（2015.12.03）

作者簡介：吳 冬（1990-），男，同濟大學，碩士研究生，研究方向：智能控制，上海，201804 , 康 琦（1980-），男，同濟大學，副教授，研究方向：群體智能，進化計算等，上海，201804 張 輪（1970-），男，同濟大學，教授。博士研究生導師．研究方向：交通信號控制。上海，201804 汪 鐳（1970-)，男，同濟大學，教授，博士研究生導師，研究方向：智能控制，上海，201804

基金項目：國家自然科學基金項目（71371142，61174183）

文章編號：1007-757X(2016)02-0001-04

中圖分類號：TP391

文獻標志碼：A