基于團(tuán)樹傳播的強(qiáng)化學(xué)習(xí)交通信號協(xié)調(diào)控制的研究

吳冬，康琦，張輪，汪鐳

?

基于團(tuán)樹傳播的強(qiáng)化學(xué)習(xí)交通信號協(xié)調(diào)控制的研究

吳冬，康琦，張輪，汪鐳

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

關(guān)鍵詞：交通信號控制；強(qiáng)化學(xué)習(xí)；團(tuán)樹傳播；協(xié)調(diào)控制

0 引言

城市交通是當(dāng)前社會經(jīng)濟(jì)發(fā)展的重要一環(huán)，城市中心區(qū)交通運(yùn)行效率的提高可以為城市

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

成為解決交通問題的有效途徑。當(dāng)前，國際上較為流行的交通信號控制系統(tǒng)有：以SCOOT和SCATS為代表的基于實(shí)時(shí)信息的集中式系統(tǒng)，以O(shè)PAC和RHODES為代表的利用動態(tài)尋優(yōu)來獲取信號設(shè)置的系統(tǒng)。大部分交通模型計(jì)算復(fù)雜，大規(guī)模實(shí)施困難，而且控制系統(tǒng)沒有利用經(jīng)驗(yàn)知識來做出最優(yōu)決策。

交通控制問題作為基本的決策問題，很多學(xué)者采用馬爾科夫決策過程（MDP），應(yīng)用動態(tài)規(guī)劃或強(qiáng)化學(xué)習(xí)的方法解決信號控制問題。研究表明，強(qiáng)化學(xué)習(xí)對于解決諸如交通路網(wǎng)的動態(tài)環(huán)境問題有著較好的控制效果。交通信號的協(xié)調(diào)控制問題可以利用多智能體協(xié)調(diào)控制框架，各方學(xué)者研究了強(qiáng)化學(xué)習(xí)在交通信號協(xié)調(diào)控制領(lǐng)域的作用。

Medina等人也將Q學(xué)習(xí)應(yīng)用在包含5個(gè)交叉口的干線信號控制場景中，在可變交通需求情況下針對緊急事件進(jìn)行干線協(xié)調(diào)控制[1]。Medina和Benekohal一同也做了類似的研究，將Q學(xué)習(xí)應(yīng)用到包含2×3和3×3個(gè)路口的近飽和路網(wǎng)中[2]。

本文應(yīng)用聯(lián)合樹算法(JTA)獲得網(wǎng)絡(luò)間的聯(lián)合動作推理，基于Q學(xué)習(xí)算法，模擬24個(gè)路口組成的路網(wǎng)，并與相鄰路口Q值共享的簡單協(xié)調(diào)算法以及無學(xué)習(xí)的自適應(yīng)算法LQF做比較。

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

1.1 強(qiáng)化學(xué)習(xí)與Q學(xué)習(xí)算法

強(qiáng)化學(xué)習(xí)將學(xué)習(xí)看做一個(gè)不斷試探與評價(jià)的過程。智能體（agent）選擇某一動作作用于環(huán)境，環(huán)境在接受該動作后狀態(tài)發(fā)生改變，同時(shí)產(chǎn)生一個(gè)強(qiáng)化信號（獎勵(lì)或懲罰）回饋給智能體，智能體根據(jù)環(huán)境當(dāng)前的狀態(tài)和強(qiáng)化信號再選擇下一個(gè)動作，選擇的宗旨是使收到正的回饋值（獎賞）的概率增大。強(qiáng)化學(xué)習(xí)基本原理圖如圖1所示：

圖1　強(qiáng)化學(xué)習(xí)原理圖

交通信號燈控制系統(tǒng)，被控對象是交通流，控制執(zhí)行機(jī)構(gòu)是信號燈，通過控制信號燈各相位之間的切換，達(dá)到最優(yōu)控制效果。那么信號燈控制的目的就轉(zhuǎn)變?yōu)楦鶕?jù)交通流的實(shí)際采集情況，決定是否應(yīng)當(dāng)切換目前正在通行的相位。

強(qiáng)化學(xué)習(xí)中應(yīng)用最為廣泛的是Q學(xué)習(xí)算法，幾乎現(xiàn)有的強(qiáng)化學(xué)習(xí)算法都可以看作是Q學(xué)習(xí)算法的變種。Q學(xué)習(xí)算法是一個(gè)離線（Off-policy）的TD控制方法，為基于累計(jì)折扣的強(qiáng)化學(xué)習(xí)算法，最優(yōu)動作值的估計(jì)的更新依賴于各種假設(shè)的動作，而不是根據(jù)學(xué)習(xí)策略所選擇的實(shí)際行動，行為決策與值函數(shù)的迭代是相互獨(dú)立的。

1.2 強(qiáng)化學(xué)習(xí)交通控制系統(tǒng)結(jié)構(gòu)

在智能體結(jié)構(gòu)中，所有元素間都有著緊密的聯(lián)系，智能體和環(huán)境之間的交互過程如圖2所示：

圖2　智能體與環(huán)境交互結(jié)構(gòu)圖

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

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

2 圖模型與交通信號協(xié)調(diào)控制

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

聯(lián)合樹算法源于計(jì)算機(jī)科學(xué)中的機(jī)器學(xué)習(xí)，根據(jù)已知數(shù)據(jù)計(jì)算某個(gè)結(jié)點(diǎn)或一系列結(jié)點(diǎn)的條件概率，是解決圖模型中的推理問題的一種算法。圖模型中的條件概率推理問題和交通信號的協(xié)調(diào)控制問題在某種程度上是相通的。一種典型的計(jì)算條件概率的方法是應(yīng)用最大后驗(yàn)概率法，如公式（1）：

A是觀測數(shù)據(jù)，E是先驗(yàn)概率，P（E|A）表示后驗(yàn)概率，因?yàn)镻（A）為常量，所以最大化后驗(yàn)概率在一定意義上就相當(dāng)于最大化聯(lián)合概率。

通過引入概率勢函數(shù)，聯(lián)合概率P（A，E）可表達(dá)為公式（2）：

其中，n表示BN網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。

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

而多智能體強(qiáng)化學(xué)習(xí)算法目標(biāo)就是使局部Q值的加和最大化，即公式（4）：

通過比較公式（3）（4）我們發(fā)現(xiàn)，利用強(qiáng)化學(xué)習(xí)解決交通信號的協(xié)調(diào)控制問題等價(jià)于圖模型中的聯(lián)合概率最大化問題。兩者目標(biāo)都是通過把整體網(wǎng)絡(luò)分解為若干局部子區(qū)域來優(yōu)化性能且兩者都有馬爾科夫特性；在概率模型中，一個(gè)節(jié)點(diǎn)的條件概率依賴于其相鄰節(jié)點(diǎn)。而在協(xié)調(diào)圖網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)的行為依賴于相鄰節(jié)點(diǎn)的行為。應(yīng)用到交通信號控制領(lǐng)域，一個(gè)交叉口的交通路況直接影響著相鄰路口的路況，兩個(gè)路口距離越近，對對方路口的交通影響越大。信念傳遞算法適用于協(xié)調(diào)圖問題，因?yàn)樗浞掷孟噜徆?jié)點(diǎn)間的依賴關(guān)系，而團(tuán)樹傳播算法中有一種聯(lián)合樹算法正是一種可以用來解決網(wǎng)絡(luò)協(xié)調(diào)問題的信念傳遞算法，這也充分解釋了聯(lián)合樹算法能用于交通信號控制領(lǐng)域，以較好地進(jìn)行聯(lián)合動作推理。

3 聯(lián)合樹算法

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

聯(lián)合樹算法包含以下步驟[4]：

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

BN轉(zhuǎn)化為JT，該過程包含4步：

a. 建立Moral圖。首先找出每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，將同一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)用無向邊兩兩連接，同時(shí)將有向圖改成無向圖，這樣得到的圖稱為Moral圖；

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

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

d.構(gòu)造聯(lián)合樹。往上一步找到的團(tuán)中添加一些邊和分隔節(jié)點(diǎn)就可以得到一顆聯(lián)合樹。

以24個(gè)路口組成的路網(wǎng)如圖3所示：

圖3　24個(gè)路口組成的路網(wǎng)

轉(zhuǎn)化得到的JT圖如圖4所示：

圖4　24個(gè)路口轉(zhuǎn)化成的JT

二、引入概率勢

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

圖5　（a）有向圖（b）轉(zhuǎn)化后的圖

圖5（a），聯(lián)合概率如公式（6）：

P（U）表示聯(lián)合概率。

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

ψ(D, C) =p(D|C), ψ(C, B) = p(C|B), ψ(B, A) = p(B|A)p(A), ψ(C) = 1, ψ(B) = 1,公式（6）變?yōu)楣剑?）：

三 消息傳遞過程

初始狀態(tài)下，我們令節(jié)點(diǎn)V和W的概率勢分別為和,分離器的概率勢為.

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

圖6　消息傳遞圖

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

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

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

基于JTA算法的強(qiáng)化學(xué)習(xí)交通信號協(xié)調(diào)控制，我們采用四種相位：東-西方向直行和右轉(zhuǎn)；南-北方向直行和右轉(zhuǎn)；西-北左轉(zhuǎn)和東-南左轉(zhuǎn)；南-西左轉(zhuǎn)和北-東左轉(zhuǎn)。學(xué)習(xí)要素設(shè)計(jì)如下：

回報(bào)函數(shù) 動作定義 動作選擇策略 動作空間 狀態(tài)空間排隊(duì)長度 可變相序(a , a ) i　 j(s , s ) i　 j

其中，表示智能體i的動作，表示智能體i的狀態(tài)。為驗(yàn)證本文算法的有效性，采用對比策略，同時(shí)設(shè)計(jì)出相鄰路口Q值分享的簡單協(xié)調(diào)算法、最大排隊(duì)長隊(duì)優(yōu)先自適應(yīng)控制LQF算法。在VISSIM中建立路網(wǎng)模型，建立24個(gè)路口，首先要把路網(wǎng)轉(zhuǎn)化為聯(lián)合樹，如上文圖4，路口通過C#.NET編程技術(shù)驅(qū)動VISSIM的COM接口，實(shí)現(xiàn)對路網(wǎng)的控制。實(shí)驗(yàn)采用兩種場景，可以通過設(shè)置車流量來實(shí)現(xiàn)以下兩種場景

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

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

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

表一　平均延誤

表二　平均停車次數(shù)

我們從整體路網(wǎng)的角度分析，無論是在交通順暢還是擁堵的狀態(tài)下，JTA算法的平均延誤要比相鄰路口Q值共享的平均延誤低；在場景二下，相鄰路口Q值共享算法的平均停車次數(shù)低于JTA算法，這是因?yàn)榻煌〒矶碌那闆r下，JTA算法為了為了制止下游路口的交通回流，限制了上游路口的車輛流動。總之，JTA算法控制效果優(yōu)于簡單的Q學(xué)習(xí)算法，JTA算法把路網(wǎng)當(dāng)做整體，以達(dá)到整體性能最優(yōu)為目標(biāo)進(jìn)行決策。基于簡單的Q值共享的策略，協(xié)調(diào)性差，很多情況下只能保證局部最優(yōu)。

基于JTA的強(qiáng)化學(xué)習(xí)算法，與LQF自適應(yīng)控制算法相比，路網(wǎng)的平均延誤明顯要低，這也反映了系統(tǒng)級協(xié)調(diào)控制在交通信號控制中的作用。

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

圖7　單路口平均延誤

由圖7可得，對于單路口的車輛平均延誤而言，基于JTA的強(qiáng)化學(xué)習(xí)算法還是要明顯優(yōu)于沒有學(xué)習(xí)的LQF算法。

5 總結(jié)

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

參考文獻(xiàn)

[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] 劉俊娜.貝葉斯網(wǎng)絡(luò)推理算法研究[D].安徽：合肥工業(yè)大學(xué)，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-），男，同濟(jì)大學(xué)，碩士研究生，研究方向：智能控制，上海，201804 , 康 琦（1980-），男，同濟(jì)大學(xué)，副教授，研究方向：群體智能，進(jìn)化計(jì)算等，上海，201804 張 輪（1970-），男，同濟(jì)大學(xué)，教授。博士研究生導(dǎo)師．研究方向：交通信號控制。上海，201804 汪 鐳（1970-)，男，同濟(jì)大學(xué)，教授，博士研究生導(dǎo)師，研究方向：智能控制，上海，201804

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目（71371142，61174183）

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

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A