侯運(yùn)鋒，龔朝暉

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

1 引 言

對(duì)交通系統(tǒng)的建模和控制是避免交通擁堵和減少交通事故的關(guān)鍵.在車(chē)路協(xié)同環(huán)境下，智能交通系統(tǒng)，特別交叉口的車(chē)輛通行控制方法已經(jīng)成為各國(guó)的研究重點(diǎn).經(jīng)過(guò)多年的發(fā)展，產(chǎn)生了諸如美國(guó)的智能駕駛，歐盟的智能交通系統(tǒng)(Intelligent Transportation Systems，ITS).智能交通系統(tǒng)基于先進(jìn)的傳感器和信息通信等技術(shù)，實(shí)現(xiàn)車(chē)輛與車(chē)輛、車(chē)輛與道路之間的信息交互，保證車(chē)輛在復(fù)雜的交通環(huán)境下的行駛安全，對(duì)道路交通實(shí)施主動(dòng)控制.

Pandit等[1]基于車(chē)路信息交互提出了交叉口車(chē)輛的在線調(diào)度算法(Oldest Job First，OJF).該算法利用圖論對(duì)路口的交通動(dòng)作進(jìn)行建模.交叉口車(chē)輛所有的交通動(dòng)作表示為圖的一個(gè)頂點(diǎn).若兩個(gè)動(dòng)作發(fā)生沖突，則在其對(duì)應(yīng)頂點(diǎn)之間連接一條直線.互相發(fā)生沖突的車(chē)輛不能同時(shí)調(diào)度.由于OJF每次只處理最先到達(dá)交叉口的車(chē)輛，所以信號(hào)燈的切換過(guò)于頻繁，難以在實(shí)際中應(yīng)用.為了提高交通運(yùn)輸效率，趙文天等[2]提出(Frame-based Traffic Scheduling，F(xiàn)TS)算法，該算法采取和OJB相同的車(chē)輛調(diào)度模式，不同的是FTS將一個(gè)時(shí)間段內(nèi)路口的車(chē)輛積攢到一起處理，有效地減少了相位的切換次數(shù)和車(chē)輛的等待時(shí)間.Kamal等人[3]基于車(chē)路協(xié)同技術(shù)，根據(jù)當(dāng)前時(shí)刻各個(gè)路段上的車(chē)輛行駛狀態(tài)在線優(yōu)化信號(hào)燈相位的時(shí)間配比，并提前一個(gè)周期廣播給路段上所有車(chē)輛，車(chē)輛根據(jù)廣播調(diào)整自身速度，以最短停車(chē)時(shí)間通過(guò)路口.另外，隨著人工智能技術(shù)的發(fā)展，基于智能算法的信號(hào)配時(shí)優(yōu)化技術(shù)也得到了長(zhǎng)足發(fā)展[4，5].

傳統(tǒng)信號(hào)燈控制方式[1-5]同一時(shí)刻只允許互不沖突相位上的車(chē)輛通過(guò).為確保安全，每個(gè)相位最后幾秒通常設(shè)置為黃燈時(shí)間.在黃燈時(shí)間路段上的所有車(chē)輛都不被允許駛?cè)虢徊婵?相位之間的頻繁切換會(huì)導(dǎo)致信號(hào)周期單位時(shí)間內(nèi)黃燈時(shí)間占比增加，從而降低交叉口的通行能力.

上官偉等[6]在車(chē)路協(xié)同環(huán)境下，設(shè)計(jì)了基于時(shí)延Petri網(wǎng)(Petri Net，PN)的無(wú)信號(hào)交叉口控制方法.該方法依據(jù)時(shí)延PN模型，將交叉口當(dāng)作車(chē)輛行駛的共享區(qū)域，以最小化交叉口車(chē)輛消散時(shí)間為優(yōu)化目標(biāo)，由路側(cè)單元的中央控制器給不同路段上的車(chē)輛分配路權(quán).該算法認(rèn)為交叉口為一個(gè)單獨(dú)的路權(quán)，為了保證行駛安全，所有與當(dāng)前正在通過(guò)交叉口的車(chē)輛行駛軌跡發(fā)生沖突的車(chē)輛都不被允許駛?cè)虢徊婵?這在一定程度上浪費(fèi)了有限交叉口物理空間資源.

Febbraro 等[7-10]將交叉路口細(xì)分為不同的空間區(qū)域.每個(gè)空間區(qū)域最多容納一輛車(chē)輛.每一個(gè)空間區(qū)域采用一個(gè)PN單元來(lái)建模.空間區(qū)域的最大車(chē)容量為描述該空間區(qū)域庫(kù)所的令牌數(shù)量.Wang等[11]提出了一種雙模塊交叉口PN表示方法，其中第一個(gè)模塊將交叉口細(xì)分為不同的空間區(qū)域，然后對(duì)其進(jìn)行建模.每個(gè)空間區(qū)域同樣最多只能容納一輛車(chē)輛.第二個(gè)模塊對(duì)交叉口的交通信號(hào)系統(tǒng)進(jìn)行建模.然后，將兩個(gè)模塊耦合在一起實(shí)現(xiàn)對(duì)交叉口車(chē)輛通行的控制.在該模型中，作者認(rèn)為從西到北的左轉(zhuǎn)車(chē)輛和從東到南的左轉(zhuǎn)車(chē)輛屬于同一相位的不同階段，需要分別執(zhí)行.然而，現(xiàn)實(shí)中相向行駛的左轉(zhuǎn)車(chē)輛可以共享同一空間區(qū)域而不發(fā)生碰撞.顯然，基于劃分空間的車(chē)輛控制方法中[7-11]每個(gè)空間區(qū)域最多只能容納一輛車(chē)輛的設(shè)定影響了交叉口的車(chē)輛吞吐能力.

針對(duì)上述問(wèn)題本文在車(chē)路協(xié)同模式下提出了一種無(wú)信號(hào)交叉口微觀建模方法.該方法將交叉口劃分為不同的空間區(qū)域，并把不同的區(qū)域設(shè)為不同的路權(quán)資源，智能車(chē)輛通過(guò)不同的空間區(qū)域需要向路側(cè)單元申請(qǐng)相應(yīng)的路權(quán)使用權(quán)，路側(cè)單元根據(jù)車(chē)輛行駛信息實(shí)時(shí)控制車(chē)輛的通行.不同于之前的工作[7-11]，本文認(rèn)為每個(gè)路權(quán)的最大容量要根據(jù)車(chē)輛的行駛方向?qū)崟r(shí)確定.例如，同一相位上的兩輛相向而行的左轉(zhuǎn)車(chē)輛的行駛軌跡不會(huì)發(fā)生沖突可以同時(shí)占用一個(gè)路權(quán).然而，不同相位上的一輛左轉(zhuǎn)車(chē)輛和一輛直行車(chē)輛的行駛軌跡會(huì)發(fā)生沖突，為保證安全，這兩輛車(chē)不能共享同一個(gè)路權(quán).路權(quán)資源要根據(jù)到達(dá)該資源車(chē)輛的行駛方向來(lái)確定其最大車(chē)容量.在此基礎(chǔ)上，構(gòu)建無(wú)信號(hào)交叉口資源調(diào)度模型，以最大化交叉口的通行效率為目標(biāo)，在線計(jì)算無(wú)交叉口車(chē)輛調(diào)度方案.所設(shè)計(jì)方案在保證車(chē)輛通行安全性的同時(shí)充分考慮了路權(quán)資源最大容量的動(dòng)態(tài)變化特性，力求達(dá)到“見(jiàn)縫插針”的效果.與此同時(shí)，基于無(wú)信號(hào)交叉口物理空間的車(chē)輛調(diào)度方式不存在由于相位切換而導(dǎo)致的黃燈時(shí)間占比增加的問(wèn)題，進(jìn)一步提升了交叉口車(chē)輛吞吐能力.

2 研究對(duì)象

2.1 交叉路口

本文選用如圖1所示雙向兩車(chē)道交叉口作為研究對(duì)象，所闡述方法同樣適用于雙向四車(chē)道交叉口和T型交叉口.圖1所示交叉口一共有8條路段，分別為路段1～8.模型構(gòu)建的基本思想是將交叉口物理空間劃分為互不相交的路權(quán).如圖1所示，交叉口被劃分為5個(gè)互不相交的路權(quán)a、b、c、d、e.車(chē)輛通過(guò)交叉口的過(guò)程中不可避免地要占用某些路權(quán).例如，從路段1直行駛向路段5的車(chē)輛需要依次占用路權(quán)a、d.從路段3左轉(zhuǎn)進(jìn)入路段5的車(chē)輛需要依次占用路權(quán)b、e、d.從路段2右轉(zhuǎn)進(jìn)入路段8的車(chē)輛要占用路權(quán)c.不同的車(chē)輛在通過(guò)交叉口的過(guò)程中可能會(huì)占用相同的路權(quán)，例如，從路段1直行駛向路段5與從路段4直行駛向路段8都需要占用路權(quán)d.為了保證車(chē)輛行駛的安全，需要定義每個(gè)路權(quán)的最大車(chē)容量.

圖1 本文所討論交叉口結(jié)構(gòu)圖Fig.1 Intersection discussed in this paper

本文認(rèn)為各個(gè)路權(quán)的最大車(chē)容量是動(dòng)態(tài)變化，每個(gè)路權(quán)的最大車(chē)容量要根據(jù)駛?cè)胲?chē)輛的行駛方向動(dòng)態(tài)確定.交叉口相向行駛的左轉(zhuǎn)車(chē)輛不會(huì)發(fā)生碰撞，因而，從路段1左轉(zhuǎn)駛向路段8的車(chē)輛和從路段2左轉(zhuǎn)駛向路段7的車(chē)輛可以同時(shí)共享路權(quán)a、e、c.這時(shí)候，路權(quán)a、e、c的車(chē)容量可設(shè)為2.同理，從路段3左轉(zhuǎn)駛向路段5的車(chē)輛和從路段4左轉(zhuǎn)駛向路段6的車(chē)輛可以同時(shí)共享路權(quán)b、e、d.此時(shí)路權(quán)b、e、d的車(chē)容量為2.其他情況下，路權(quán)a、b、c、d、e同一時(shí)刻最多容納1輛車(chē)輛.例如，若路權(quán)a被一輛由路段1或者路權(quán)b駛?cè)氲闹毙熊?chē)輛占用，那么此時(shí)其他任何車(chē)輛不被允許駛?cè)肼窓?quán)a，路權(quán)a的最大車(chē)容量為1.

2.2 控制模式

目前智能無(wú)信號(hào)交通控制方式主要分為中央控制站控制模式和車(chē)車(chē)協(xié)同控制模式，本文采用中央控制站控制模式，中央控制站控制模式中車(chē)輛主要和路側(cè)智能設(shè)備進(jìn)行通信，避免了不同車(chē)輛之間的大量信息交互，從而在一定程度上降低了系統(tǒng)對(duì)無(wú)線通信網(wǎng)絡(luò)的要求.

本文所考慮的無(wú)信號(hào)交叉口控制系統(tǒng)主要由3部分組成：

1)自治車(chē)輛：當(dāng)具有智能車(chē)載系統(tǒng)的車(chē)輛進(jìn)入路口感應(yīng)區(qū)域時(shí)，車(chē)輛能夠?qū)⒆陨頎顟B(tài)信息實(shí)時(shí)發(fā)送給智能路側(cè)系統(tǒng)，并且能夠?qū)崟r(shí)接收智能路側(cè)系統(tǒng)的指令信息.

2)智能路側(cè)單元：作為交叉口的“大腦”，與交叉口區(qū)域內(nèi)的自治車(chē)輛進(jìn)行信息交互，獲取車(chē)輛的實(shí)時(shí)狀態(tài)信息；路側(cè)單元基于所構(gòu)建模型，利用優(yōu)化算法，得到最優(yōu)車(chē)輛通行序列，實(shí)時(shí)向車(chē)輛分配交叉口各個(gè)區(qū)域的使用權(quán)，引導(dǎo)車(chē)輛通過(guò)交叉口.

3)協(xié)同信息交互系統(tǒng)：自治車(chē)輛和智能路側(cè)系統(tǒng)的信息傳輸載體.

3 交叉口模型

3.1 有限自動(dòng)機(jī)

智能交通系統(tǒng)具有高度并發(fā)性、資源共享性以及動(dòng)態(tài)性，而在描述系統(tǒng)異步性和并發(fā)性方面，有限自動(dòng)機(jī)具有顯著的優(yōu)勢(shì).本文利用有限自動(dòng)機(jī)構(gòu)建無(wú)信號(hào)交叉口路權(quán)調(diào)度模型.所構(gòu)建模型考慮了路權(quán)最大容量的動(dòng)態(tài)變化特性，充分地利用了有限的交叉口物理空間.

有限自動(dòng)機(jī)(Finite States Automaton，F(xiàn)SA)可以表示為一個(gè)5元組G=(X,E,f,Γ,x0)，其中，X是有限狀態(tài)集合；E是有限事件集合；f:X×E→X是狀態(tài)激活函數(shù)；Γ是活躍事件函數(shù)，任給x∈X，Γ(x)={σ∈E:f(x,σ)!}，其中，f(x,σ)!表示f(x,σ)有定義；x0是初始激活狀態(tài).E*表示由E中元素組成的事件發(fā)生序列集合.根據(jù)事件是否可控，E被分割為可控事件集合Ec和不可控事件集合Euc，即E=Ec∪Euc.f的定義閾按以下方式從E擴(kuò)展至E*：對(duì)于空事件發(fā)生序列ε，f(x,ε)=x；任給事件發(fā)生序列s∈E*和事件σ∈E，f(x0,sσ)=f(f(x0,s),σ).

事件的發(fā)生必須滿足某些限制條件.將事件發(fā)生條件函數(shù)引入到FSA模型中，往往可以為系統(tǒng)的模擬和分析提供便利.本文對(duì)FSA模型做進(jìn)一步拓展，定義了普遍意義下的FSA(Generalized Finite States Automaton，GFSA)模型.GFSA可以描述為6元組G=(X,E,f,Γ,x0,c)，其中，(X,E,f,Γ,x0)是一個(gè)普通FSA模型，c:E→{0,1}是事件發(fā)生條件函數(shù).給定x∈X和σ∈E，其中，f(x，σ)!若當(dāng)前時(shí)刻狀態(tài)x處于激活狀態(tài)，并且事件σ滿足發(fā)生條件，即c(σ)=1，那么，事件σ允許發(fā)生，否則，不被允許發(fā)生.

3.2 模型構(gòu)建

為了更好地表述模型的構(gòu)建過(guò)程，對(duì)模型中所使用符號(hào)做如下解釋?zhuān)簲?shù)字1-8表示路段1～8；字母a、b、c、d、e分別表示路權(quán)a、b、c、d、e；字母s、r、l分別表示直行、右轉(zhuǎn)、左轉(zhuǎn)車(chē)輛.事件σxzk，其中，x，z=1，…，8，a，…，e，k=l，s，r，表示一輛k類(lèi)型車(chē)輛由x駛?cè)雤，比如，事件σ1as表示一輛直行車(chē)輛由路段1駛?cè)肼窓?quán)a；事件σael表示一輛左轉(zhuǎn)車(chē)輛由路權(quán)a駛?cè)肼窓?quán)e；事件αxk，其中，x=1，…，4，k=l，s，r，表示一輛k類(lèi)型車(chē)輛由路段x到達(dá)交叉口，比如，事件α1s表示一輛直行車(chē)輛由路段1到達(dá)交叉路口.

本文構(gòu)建交叉口模型的過(guò)程分為4步：1)構(gòu)建各個(gè)路權(quán)的FSA模型；2)構(gòu)建交叉口各個(gè)方向上的車(chē)輛到達(dá)FSA模型；3)交叉口FSA模型由各個(gè)路權(quán)FSA模型和交叉口各個(gè)方向上的車(chē)輛到達(dá)FSA模型并行產(chǎn)生；4)定義交叉口FSA模型的事件發(fā)生條件函數(shù)，構(gòu)建交叉路口的GFSA模型.

3.2.1 所有路權(quán)的FSA模型

路權(quán)a～e的FSA模型分別如圖2(a)-圖2(e)所示，分別記做G1～G5.G1中所有狀態(tài)的具體定義如下：狀態(tài)0表示路權(quán)a空置；狀態(tài)1表示路權(quán)a被一輛由路段1駛?cè)氲淖筠D(zhuǎn)車(chē)輛占用；狀態(tài)2表示路權(quán)a被一輛由路權(quán)e駛?cè)氲淖筠D(zhuǎn)車(chē)輛；狀態(tài)3表示路權(quán)a被一輛由路段1駛?cè)氲淖筠D(zhuǎn)車(chē)輛和一輛路權(quán)e駛?cè)氲淖筠D(zhuǎn)車(chē)輛同時(shí)占用；狀態(tài)4表示路權(quán)a被一輛由路段1駛?cè)氲闹毙熊?chē)輛占用；狀態(tài)5表示路權(quán)a被一輛由路段1駛?cè)氲挠肄D(zhuǎn)車(chē)輛占用；狀態(tài)6表示路權(quán)a被一輛由路權(quán)b駛?cè)氲闹毙熊?chē)輛占用.

由圖2(a)可知，模型G1的初始激活狀態(tài)為0，路權(quán)a空置.若此時(shí)一輛左轉(zhuǎn)車(chē)輛從路段1駛?cè)隺，伴隨事件σ1al的發(fā)生，系統(tǒng)激活狀態(tài)1，此時(shí)允許一輛左轉(zhuǎn)車(chē)輛從e駛?cè)隺，除此之外，其他占用路權(quán)a的行為都會(huì)導(dǎo)致車(chē)輛相撞而被嚴(yán)格禁止.假設(shè)此時(shí)一輛左轉(zhuǎn)車(chē)輛從e駛向a，伴隨著事件σeal的發(fā)生，系統(tǒng)激活狀態(tài)3.此時(shí)路權(quán)a被兩輛左轉(zhuǎn)車(chē)輛同時(shí)占用，其他車(chē)輛不被允許駛?cè)肼窓?quán)a.接下來(lái)，如果一輛車(chē)輛離開(kāi)a進(jìn)入e，伴隨著事件σacl的發(fā)生，路權(quán)a中只剩下一輛由路權(quán)e駛?cè)氲淖筠D(zhuǎn)車(chē)輛，系統(tǒng)激活狀態(tài)2.接下來(lái)若由路權(quán)e駛?cè)肼窓?quán)a的車(chē)輛離開(kāi)a進(jìn)入路段7，便隨著事件σa7l發(fā)生，系統(tǒng)激活初始狀態(tài)0，路權(quán)a空置.當(dāng)系統(tǒng)狀態(tài)3處于激活狀態(tài)時(shí)，若路權(quán)a中一輛車(chē)輛離開(kāi)a進(jìn)入路段7，便隨著事件σa7l的發(fā)生，a中只剩一輛由路段1駛?cè)氲淖筠D(zhuǎn)車(chē)輛，系統(tǒng)激活狀態(tài)1.此時(shí)若這輛左轉(zhuǎn)車(chē)輛離開(kāi)a前往e，路權(quán)a空置，系統(tǒng)激活初始狀態(tài)0.

圖2 路權(quán)a、b、c、d、e的FSA模型Fig.2 FSA models for section a、b、c、d、e

另一方面，在初始狀態(tài)0，事件σ1as、σ1ar、σbas發(fā)生后，系統(tǒng)分別激活狀態(tài)4、5、6.除非接下來(lái)這些車(chē)輛離開(kāi)a進(jìn)入接下來(lái)的路權(quán)或路段，其他任何車(chē)輛不被允許駛?cè)隺.由于路權(quán)b、c、d的FSA模型和G1具有較強(qiáng)的可類(lèi)比性，為了更加簡(jiǎn)潔，不再分析G2～G4的狀態(tài)演化過(guò)程.

G5中所有狀態(tài)的具體定義如下：狀態(tài)0表示路權(quán)e空置；狀態(tài)1表示路權(quán)e被一輛由路權(quán)a駛?cè)氲淖筠D(zhuǎn)車(chē)輛占用；狀態(tài)2表示路權(quán)e被一輛由路權(quán)c駛?cè)氲淖筠D(zhuǎn)車(chē)輛占用；狀態(tài)3表示路權(quán)e被一輛由路權(quán)a駛?cè)胱筠D(zhuǎn)車(chē)輛和一輛由路權(quán)c駛?cè)氲淖筠D(zhuǎn)車(chē)輛同時(shí)占用；狀態(tài)4表示路權(quán)e被一輛由路權(quán)b駛?cè)氲淖筠D(zhuǎn)車(chē)輛占用；狀態(tài)5表示路權(quán)e被一輛由路權(quán)b駛?cè)胱筠D(zhuǎn)車(chē)輛和一輛由路權(quán)d駛?cè)氲淖筠D(zhuǎn)車(chē)輛同時(shí)占用；狀態(tài)6表示路權(quán)e被一輛由路權(quán)d駛?cè)氲淖筠D(zhuǎn)車(chē)輛占用.

區(qū)域e可以同時(shí)容納一輛從路權(quán)a和路權(quán)c，或者路權(quán)b和路權(quán)d駛?cè)氲能?chē)輛.但是，當(dāng)一輛來(lái)自路權(quán)a或者路權(quán)c的車(chē)輛駛?cè)雲(yún)^(qū)域e時(shí)，路權(quán)b和路權(quán)d的車(chē)輛被嚴(yán)格禁止駛?cè)肼窓?quán)e(如圖2(e)所示，σbel和σdel在狀態(tài)1、2、3沒(méi)有定義).同理，當(dāng)一輛來(lái)自路權(quán)b或者路權(quán)d的車(chē)輛駛?cè)肼窓?quán)e時(shí)，路權(quán)a和路權(quán)d的車(chē)輛被嚴(yán)格禁止駛?cè)肼窓?quán)e(σael和σcel在狀態(tài)4、5、6沒(méi)有定義).

3.2.2 交叉口各個(gè)方向上的車(chē)輛到達(dá)FSA模型

圖3(a)-圖3(d)模擬了路段1～4上的車(chē)輛到達(dá)交叉口的過(guò)程.圖3(a)-圖3(d)所示模型分別記做G6～G9.

圖3 交叉口各個(gè)方向上的車(chē)輛到達(dá)FSA模型Fig.3 Vehicle arrival models for the intersection

以圖3(a)為例，若路段1上一輛直行車(chē)輛到達(dá)交叉口，便隨著事件α1s的發(fā)生，系統(tǒng)狀態(tài)2激活.由圖1可知，此時(shí)路段1上的右轉(zhuǎn)、直行車(chē)輛只能排在這輛直行車(chē)輛之后，等到這輛直行車(chē)輛駛?cè)雲(yún)^(qū)域a，即事件σ1as發(fā)生后，才能繼續(xù)到達(dá)交叉口.然而此時(shí)路段1上的左轉(zhuǎn)車(chē)輛可以不受直行車(chē)輛的影響駛?cè)胱筠D(zhuǎn)車(chē)道，因此事件α1l在狀態(tài)2有定義.當(dāng)一輛左轉(zhuǎn)車(chē)輛到達(dá)交叉口后，便隨著事件α1l的發(fā)生，系統(tǒng)狀態(tài)5激活.在左轉(zhuǎn)車(chē)輛駛?cè)雲(yún)^(qū)域a之前，即事件σ1al發(fā)生之前，路段1上的其他左轉(zhuǎn)車(chē)輛不能到達(dá)交叉口.

同理，當(dāng)初始狀態(tài)0處于激活狀態(tài)時(shí)若一輛右轉(zhuǎn)車(chē)輛到達(dá)交叉口，伴隨著事件α1r的發(fā)生，系統(tǒng)狀態(tài)1激活.此時(shí)可能存在一輛左轉(zhuǎn)車(chē)輛到達(dá)交叉口.若一輛左轉(zhuǎn)車(chē)輛到達(dá)交叉口，伴隨著事件α1l的發(fā)生，系統(tǒng)狀態(tài)4激活.

另外，當(dāng)初始狀態(tài)0處于激活狀態(tài)時(shí)若一輛左轉(zhuǎn)車(chē)輛到達(dá)交叉口，伴隨著事件α1l的發(fā)生，系統(tǒng)狀態(tài)3激活.此時(shí)可能存在一輛右轉(zhuǎn)或者直行車(chē)輛到達(dá)交叉口.若一輛右轉(zhuǎn)車(chē)輛到達(dá)交叉口，伴隨著事件α1r的發(fā)生，系統(tǒng)狀態(tài)4激活.若一輛直行車(chē)輛到達(dá)交叉口，伴隨著事件α1s的發(fā)生，系統(tǒng)狀態(tài)5激活.

G6中所有狀態(tài)的具體定義如下：狀態(tài)0表示路段1上沒(méi)有車(chē)輛到達(dá)交叉口；狀態(tài)1表示路段1上一輛右轉(zhuǎn)車(chē)輛到達(dá)交叉口；狀態(tài)2表示路段1上一輛直行車(chē)輛到達(dá)交叉口；狀態(tài)3表示路段1上一輛左轉(zhuǎn)車(chē)輛到達(dá)交叉口；狀態(tài)4表示路段1上一輛左轉(zhuǎn)車(chē)輛和一輛右轉(zhuǎn)車(chē)輛到達(dá)交叉口；狀態(tài)5表示路段1上一輛左轉(zhuǎn)車(chē)輛和一輛直行車(chē)輛到達(dá)交叉口.由于G7～G9和G6具有較強(qiáng)的可類(lèi)比性，為了更加簡(jiǎn)潔，不再分析G7～G9的狀態(tài)動(dòng)態(tài)演化過(guò)程.

3.2.3 交叉口FSA模型

各個(gè)FSA之間既相互獨(dú)立又互相影響，它們通過(guò)互相之間的共同事件相互作用.例如，σael是G1和G5共同定義的事件，若此時(shí)G1和G5的激活狀態(tài)分別為1和0，σael發(fā)生后G1和G6的激活狀態(tài)變?yōu)?和1.同理，σ1al是G1和G6共同定義的事件，若此時(shí)G1和G6的激活狀態(tài)分別為0和3，σ1al發(fā)生后G1和G6的激活狀態(tài)變?yōu)?和0.另外，α1s只在G6中有定義，若此時(shí)G6的激活狀態(tài)是0，α1s發(fā)生后只會(huì)導(dǎo)致G6的激活狀態(tài)變?yōu)?，其他FSA模型的狀態(tài)不會(huì)受影響.

為了將G1～G9耦合在一起，引入如下并行操作[12].給定H1=(Q1,∑1,δ1,Γ1,q01)和H2=(Q2,∑2,δ2,Γ2,q02)，H1和H2并行產(chǎn)生H=Ac(Q1×Q2,∑1∪∑2,δ,Γ1‖2,(q01,q02))，其中，任給(q1,q2)∈Q1×Q2和σ∈∑1∪∑2，若σ∈Γ1(q1)∩Γ2(q2)，那么，δ((q1,q2),σ)=(δ1(q1,σ),δ2(q2,σ))；若σ∈Γ1(q1)/∑2，那么，δ((q1,q2),σ)=(δ1(q1,σ),q2)；若σ∈Γ2(q2)/∑1，那么，δ((q1,q2),σ)=(q1,δ2(q2,σ))；其他情況，δ((q1,q2),σ)沒(méi)有定義.Ac表示取有限自動(dòng)機(jī)由初始狀態(tài)可到達(dá)部分.

交叉口FSA模型由G1～G9并行產(chǎn)生.正式地，基于有限物理空間的交叉口FSA模型為：

G=G1‖G2‖…‖G9=(X，E，f，Γ，x0)

任給x=(x1,x2,…,x9)∈X,x1～x5，分別表示當(dāng)前時(shí)刻路權(quán)a～e所處狀態(tài)，x6～x9分別表示當(dāng)前時(shí)刻路段1～4上的車(chē)輛到達(dá)交叉口的情況.Γ(x)可以理解為當(dāng)前時(shí)刻可以選擇觸發(fā)而不會(huì)導(dǎo)致車(chē)輛相撞的事件集合.例如，任意給定激活狀態(tài)x=(1,0,0,0,0,3,0,0,0)，此時(shí)路段1上有一輛左轉(zhuǎn)車(chē)輛到達(dá)交叉口，另外路權(quán)a被一輛從路段1上駛?cè)氲淖筠D(zhuǎn)車(chē)輛占據(jù).若觸發(fā)事件σael∈Γ(x)，占用路權(quán)a的左轉(zhuǎn)車(chē)輛從路權(quán)a駛?cè)肼窓?quán)e，系統(tǒng)激活狀態(tài)(0,0,0,0,1,3,0,0,0).相反，若選擇觸發(fā)事件集合Γ(x)以外的事件，例如σ1al，則會(huì)導(dǎo)致兩輛車(chē)輛在路權(quán)a相撞.由于我們不能控制車(chē)輛是否到達(dá)交叉口，因而系統(tǒng)的不可控事件集合為Euc={σis,σir,σil：?i=1,2,3,4}，可控事件集合Ec=E/Euc.

3.2.4 交叉口GFSA模型

FSA模型可以表達(dá)系統(tǒng)所訪問(wèn)的狀態(tài)序列和導(dǎo)致這些狀態(tài)轉(zhuǎn)換的相關(guān)事件，但卻不能表達(dá)系統(tǒng)何時(shí)進(jìn)入特定的狀態(tài)或系統(tǒng)保持這種狀態(tài)的時(shí)間.然而，在模型的控制過(guò)程中我們常常需要考慮事件序列發(fā)生時(shí)間的長(zhǎng)短，因此，在交叉口的GFSAG=(X,E,f,Γ,x0,c)模型中我們定義了所有事件發(fā)生需要滿足的時(shí)鐘條件.

事件發(fā)生條件函數(shù)c定義如下：以事件σads和σ1as為例，不難發(fā)現(xiàn)，只有直行車(chē)輛從路段1完全駛?cè)肼窓?quán)a后，才有可能繼續(xù)從路權(quán)a駛?cè)肼窓?quán)d，所以說(shuō)事件σads只有在事件σ1as發(fā)生結(jié)束后才可能被觸發(fā).任意給定事件σ∈E，定義π(σ)為事件σ最近一次觸發(fā)距離當(dāng)前時(shí)刻的時(shí)長(zhǎng).若σ未曾發(fā)生，則定義π(σ)=0.根據(jù) 3.1節(jié)的定義，t(σ)為事件σ發(fā)生所需時(shí)間.若σ未曾發(fā)生，定義t(σ)=-∞.事件σads的發(fā)生條件函數(shù)可以定義為：如果π(σ1as)≥t(σ1as)，則c(σads)=1；否則，如果π(σ1as)

表1 可控事件發(fā)生條件Table 1 Occurrence conditions for controllable events

事件的σ1as發(fā)生條件則要根據(jù)路段1上車(chē)輛到達(dá)交叉口情況來(lái)決定.具體地，事件σ1as的發(fā)生條件函數(shù)定義為：如果π(α1s)≥t(α1s)，則c(σ1as)=1；如果π(α1s)

3.3 死鎖狀態(tài)

在無(wú)信號(hào)交叉口的控制過(guò)程中要防止死鎖的出現(xiàn).所謂死鎖是交叉口當(dāng)前車(chē)輛所處位置互相阻礙對(duì)方前行的一種狀態(tài).例如，若此時(shí)路a權(quán)被一輛由路段1駛?cè)氲闹毙熊?chē)輛占用，路權(quán)b被一輛由路段3駛?cè)氲闹毙熊?chē)輛占用，路權(quán)c被一輛由路段2駛?cè)胫毙熊?chē)輛占用，路權(quán)d被一輛由路段4駛?cè)氲闹毙熊?chē)輛占用.在當(dāng)前情形下，這4輛車(chē)輛互相阻礙對(duì)方的前進(jìn)方向都無(wú)法駛離當(dāng)前位置，因而形成死鎖.定義1正式地給出了死鎖狀態(tài)的定義.

定義1.任意給定x=(x1,x2,…,x9)∈X，如果不存在s∈E*使得f(x,s)=x0，則稱(chēng)狀態(tài)x為死鎖狀態(tài).

由定義1可知，死鎖狀態(tài)是一些不能返回初始狀態(tài)的狀態(tài).直觀上，當(dāng)系統(tǒng)到達(dá)這些狀態(tài)時(shí)，不存在通行序列使當(dāng)前交叉口通行車(chē)輛駛離交叉路口.在控制交叉口車(chē)輛通行的過(guò)程中，死鎖狀態(tài)是要嚴(yán)格禁止到達(dá)的.

4 優(yōu)化控制

本節(jié)設(shè)計(jì)控制器調(diào)節(jié)交叉口車(chē)輛的通行次序.不失一般性，可控事件σ∈Ec的發(fā)生條件記為π(σ′)≥t(σ′)，事件集合E記為E={σ1,σ2,…,σm}.設(shè)第k步，系統(tǒng)所處狀態(tài)、事件σ最近一次發(fā)生距離當(dāng)前時(shí)刻時(shí)長(zhǎng)、事件σ最近一次發(fā)生所需時(shí)間、選擇觸發(fā)的事件分別為xk、πk(σ)、tk(σ)、αk，定義Ψk=Ψ(xk,πk(σ1),…,πk(σm),tk(σ1),…,tk(σm),αk)為觸發(fā)事件ak需要等待的時(shí)間.以下算式計(jì)算得出了將當(dāng)前到達(dá)交叉口的車(chē)輛和交叉口內(nèi)的通行車(chē)輛完全排空所耗費(fèi)時(shí)間最少的車(chē)輛通行序列.

(1)

s.t.(?i=0,1,…,nk)ak+i∈Ec

(2)

f(xk,akak+1…ak+nk)=x0

(3)

其中，迭代過(guò)程為：

?z=k+1,k+2,…,k+nk,Ψz=Ψz-1+τz-1

(4)

(5)

對(duì)所有σ∈E，

(6)

(7)

xz=f(xz-1,az-1)

(8)

需要指出的是，雖然我們計(jì)算了接下來(lái)nk步內(nèi)的最優(yōu)車(chē)輛通行序列，然而該序列是基于當(dāng)前時(shí)刻交叉口的車(chē)輛情況計(jì)算得出的，在執(zhí)行上述序列的同時(shí)可能存在新的車(chē)輛到達(dá)交叉口(不可控事件的發(fā)生).因而，實(shí)際中我們只執(zhí)行所計(jì)算最優(yōu)通行序列中的第1步，在第1步執(zhí)行結(jié)束后，基于系統(tǒng)最新?tīng)顟B(tài)和參數(shù)，再次執(zhí)行上述優(yōu)化過(guò)程，計(jì)算下一步的通行控制策略.

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)設(shè)置

本文的仿真環(huán)境為MATLAB，仿真精度為1s，也就是說(shuō)系統(tǒng)每隔1s更新一次控制策略.本文假定1)各個(gè)駛向交叉口方向上單位時(shí)間內(nèi)的車(chē)輛到達(dá)數(shù)符合泊松分布；2)各個(gè)方向上的到達(dá)車(chē)輛右轉(zhuǎn)、直行、左轉(zhuǎn)的概率分別為0.2、0.4、0.4；3)所有事件的發(fā)生時(shí)間符合參數(shù)為0.5的指數(shù)分布.表2給出了事件發(fā)生時(shí)間概率分布關(guān)系.

表2 事件發(fā)生所需時(shí)間的概率分布關(guān)系Table 2 Distribution of the time taken to execute an event

5.2 仿真實(shí)驗(yàn)

本節(jié)展示了所設(shè)計(jì)基于交叉口有限物理空間的車(chē)輛調(diào)度算法(Spatial-based vehicle scheduling，SVS)在仿真周期內(nèi)的車(chē)輛排隊(duì)數(shù)，以及將有限車(chē)輛全部調(diào)度完畢的耗費(fèi)時(shí)間，并與目前交通控制系統(tǒng)中信號(hào)燈交通控制方式進(jìn)行對(duì)比分析.

首先考慮各個(gè)駛向交叉口方向上單位時(shí)間內(nèi)的車(chē)輛到達(dá)數(shù)符合數(shù)學(xué)期望一致的泊松分布的情況(平衡車(chē)流).不失一般性，假設(shè)數(shù)學(xué)期望為λ.

圖4 不同λ取值下車(chē)輛排隊(duì)長(zhǎng)度的比較Fig.4 Queue length with different values of λ

圖4給出了當(dāng)λ取不同數(shù)值時(shí)1200s內(nèi)交叉口車(chē)輛排隊(duì)總和.在圖4中每隔10s記錄一次車(chē)輛排隊(duì)數(shù)據(jù)，第10次取樣數(shù)據(jù)即為100s時(shí)交叉口車(chē)輛排隊(duì)長(zhǎng)度總和.如圖4所示，當(dāng)λ=0.1,0.125,0.15時(shí)，SVS能夠確保交叉路口的排隊(duì)車(chē)輛不高于25輛，顯示出了較強(qiáng)的魯棒性.當(dāng)λ=0.175時(shí)，隨著時(shí)間的增加，交叉口出現(xiàn)了大量的排隊(duì)車(chē)輛.這說(shuō)明基于單個(gè)交叉口的控制難以控制相對(duì)較大的車(chē)流量.此時(shí)需要多個(gè)相鄰交叉口、路段之間的協(xié)同控制.接下來(lái)，在平衡車(chē)流下測(cè)試了OJF算法[1]、FTS算法[2]和SVS算法在不同車(chē)流量下的表現(xiàn).

表3 3種算法在平衡車(chē)流下車(chē)輛排隊(duì)長(zhǎng)度比較Table 3 Comparison of queue lengths in three algorithms

表3給出了平衡車(chē)流下，在3種算法控制下交叉口車(chē)輛排隊(duì)數(shù)隨著參數(shù) 的變化過(guò)程.所有數(shù)據(jù)為4次實(shí)驗(yàn)的平均值，每次實(shí)驗(yàn)仿真時(shí)長(zhǎng)為10分鐘.通過(guò)表3可知，在不同車(chē)流量下，本文提出的SVS算法仿真周期內(nèi)排隊(duì)車(chē)輛明顯更??；特別是當(dāng)λ=0.1,0.125,0.15時(shí)，SVS較OJF和FTS顯示出較強(qiáng)的魯棒性.這是因?yàn)椋?dāng)車(chē)流量較小時(shí)，OJF算法和FTS算法需要多次切換相位以滿足控制需求，從而損失更多的時(shí)間(黃燈時(shí)間).當(dāng)λ=0.175時(shí)，F(xiàn)TS和SVS仿真周期內(nèi)的排隊(duì)車(chē)輛都呈現(xiàn)大幅度增長(zhǎng).當(dāng)交叉口的到達(dá)車(chē)輛趨向飽和時(shí)FTS相位切換的次數(shù)減小，然而，由于OJF每次只處理一輛車(chē)輛，其相位切換次數(shù)不會(huì)隨著車(chē)流的變化而發(fā)生明顯的變化，相比FTS由于相位的頻繁切換而導(dǎo)致的損失時(shí)間更大，因而，仿真周期內(nèi)OJF的表現(xiàn)明顯遜色于FTS和SVS.

圖5 馬爾科夫模型Fig.5 Markov model

上述實(shí)驗(yàn)認(rèn)為各個(gè)路段的車(chē)輛到達(dá)情況一致.然而在現(xiàn)實(shí)中每個(gè)路段的車(chē)輛到達(dá)情況隨著時(shí)間的變化會(huì)發(fā)生相應(yīng)變化.為描述這種變化，引入如圖5所示馬爾科夫模型.模型一共有兩個(gè)狀態(tài)，系統(tǒng)狀態(tài)的轉(zhuǎn)移概率分別為p1、p2、p3、p4.假設(shè)系統(tǒng)狀態(tài)的初始狀態(tài)為0.模型下一步的狀態(tài)只與系統(tǒng)當(dāng)前步所處狀態(tài)相關(guān)，而與之前所處狀態(tài)無(wú)關(guān)，并且狀態(tài)轉(zhuǎn)移概率不受時(shí)間的影響.假設(shè)當(dāng)模型處于狀態(tài)0時(shí)，車(chē)輛到達(dá)隨機(jī)數(shù)滿足數(shù)學(xué)期望為λ1的泊松分布，處于狀態(tài)1時(shí)，滿足數(shù)學(xué)期望為λ2的泊松分布.由于狀態(tài)在仿真過(guò)程的每一步都可能發(fā)生轉(zhuǎn)移，考慮到車(chē)輛的到達(dá)率在短時(shí)間內(nèi)發(fā)生改變的概率比較低，我們?cè)O(shè)定如下?tīng)顟B(tài)轉(zhuǎn)移概率：p1=0.8、p2=0.8、p3=0.2、p4=0.2.

表4 參數(shù)λ1和λ2的取值Table 4 Values of λ1 and λ2

表5 3種算法在非平衡車(chē)流下車(chē)輛排隊(duì)長(zhǎng)度比較Table 5 Comparison of queue lengths in three algorithm

表4給出了一些較大車(chē)流量下的參數(shù)取值.表5展示了當(dāng)參數(shù)λ1和λ2的取表4所列類(lèi)別的數(shù)值時(shí)，在3種算法的控制下，10min的仿真周期內(nèi)交叉口的車(chē)輛排隊(duì)情況.總體來(lái)講SVS的表現(xiàn)明顯要優(yōu)于OJF和FTS.OJF和FTS在非平衡車(chē)流下的表現(xiàn)要劣于其在平衡車(chē)流下的表現(xiàn).除類(lèi)別3外，SVS顯示出很好的車(chē)輛調(diào)度效果，對(duì)非平衡車(chē)流表現(xiàn)出很好的魯棒性.在類(lèi)別3，SVS出現(xiàn)一定的不穩(wěn)定性，但相對(duì)OJF和FTS，仍然顯示出了很好的控制效果.接下來(lái)我們測(cè)試當(dāng)路段1～4的車(chē)輛排隊(duì)數(shù)為5、10、15、20、25、30時(shí)，3種算法將車(chē)輛調(diào)度完畢所消耗時(shí)間.實(shí)驗(yàn)結(jié)果如圖6所示.

當(dāng)路段1～4的車(chē)輛排隊(duì)數(shù)為5、10、15、20、25、30時(shí)，SVS將所有車(chē)輛消散的平均耗時(shí)相比于FTS控制方法分別減少了43.1%、22.4%、25.7%、26%、19.1%和17.8%，相比于OJF控制方法分別減少了61.5%、53.3%、58%、63%、60.7%和59.5%.顯然，本文所提出SVS算法的平均車(chē)輛消散時(shí)間相比于OJF和FTS有比較明顯的減少.

圖6 3種算法車(chē)輛調(diào)度時(shí)間對(duì)比Fig.6 Comparison of scheduling time among three algorithms

6 總 結(jié)

智能交通是未來(lái)交通系統(tǒng)的發(fā)展趨勢(shì)，車(chē)路協(xié)同技術(shù)是是發(fā)展智能交通系統(tǒng)的重要一環(huán)，其目標(biāo)是實(shí)現(xiàn)自治車(chē)輛和智能路側(cè)設(shè)備之間的協(xié)同關(guān)系，確保交通系統(tǒng)的安全高效.本文就車(chē)路協(xié)同技術(shù)的問(wèn)題之一，無(wú)信號(hào)交叉口的車(chē)輛調(diào)度方法展開(kāi)了相應(yīng)研究.為實(shí)現(xiàn)車(chē)輛對(duì)交叉口有限物理空間的最大利用，將交叉口劃分為不同的區(qū)域資源，并建立相應(yīng)的資源調(diào)度模型，以最大化通行效率作為優(yōu)化目標(biāo)建立目標(biāo)函數(shù)，求解得到車(chē)輛的最優(yōu)通行次序.實(shí)驗(yàn)結(jié)果顯示，較傳統(tǒng)有信號(hào)控制方案，新方案在保證車(chē)輛行駛安全的同時(shí)，極大地提高了車(chē)輛通過(guò)交叉口的效率.

本文集中研究單個(gè)交叉口的車(chē)輛通行控制方法，接下來(lái)將考慮更加復(fù)雜的情況，對(duì)多個(gè)交叉口和道路之間的車(chē)輛協(xié)同調(diào)度方法展開(kāi)研究.