無信號交叉口車輛通行控制研究

錢怡杉

（上海理工大學光電信息與計算機工程學院，上海 200093）

0 引言

近幾年來，我國機動車保有量平均每年增加1 400 萬輛左右。隨著機動車保有量的增加，城市的擁堵問題愈發嚴重，進而引發車輛延誤、交通事故等一系列問題。然而，大部分城市無法通過擴建新的交通設施緩解所面臨的交通壓力。城市道路交叉路口作為交通網絡的樞紐點，它對車輛的疏導能力直接影響道路的通行效率。在現有的交通設施條件下，如何提高交叉路口的車輛吞吐能力已成為各國研究的熱點。我國城市交叉路口的交通控制模式主要采用信號控制方案，因而信號控制方案的優劣直接影響到我國城市道路交通系統的運行效率。其中，在全球廣泛應用的交通信號控制系統SCOOT［1］（Split Cycle Offset Optimization Technique），能夠對交通信號網絡進行實時自適應控制。雖然SCOOT 系統具有一個靈活而且準確的實時交通模型，并且能夠用來制定信號配時方案，但其相位不能自動增減，相序不能自動改變的局限性導致通行車輛不必要的停車，從而影響了交叉口的通行效率。

2006 年之后，基于協同管控的智能交通系統建設引起了各國政府的重視，產生了諸如美國的智能駕駛、歐盟的智能交通系統（Intelligent Transportation Systems，ITS）行動計劃等。為了順應未來交通系統的發展，我國目前正致力于研究開發智能車路協同系統。智能車路協同系統是通過車—車、車—路的信息交互，實現車輛與基礎設施之間的智能協同和配合，達到優化利用系統資源、提高道路交通安全、緩解交通擁堵的目的。近幾年來，智能車路協同系統已經成為現代智能交通系統的基礎性研究內容，智能交通系統原有和新增的所有功能、服務均可在車路協同環境下展開。許多學者在車路協同環境下，對智能交通系統，特別是有信號和無信號交叉口的車輛通行控制方法進行了大量研究。

1 相關工作

針對有信號交叉路口，Pandit 等［2］利用圖論對路口的交通動作進行建模，并在此基礎上提出交叉口車輛的在線調度算法。該算法每次只處理最先到達交叉口的車輛且相互沖突的兩個相位上的車輛，不能做到同時調度。為了減少相位的切換次數和車輛的等待時間，文獻［3］對文獻［2］中的算法進行了改進，將一個時間段內路口的車輛積攢到一定數量再一起處理。為提高車輛通行效率，文獻［4］基于時延賦色Petri 網模型，構建最小化輸入路段車輛數的優化方程；文獻［5］基于元胞自動機，采用延遲時間作為性能指標，提出多交叉口信號配時規劃算法；文獻［6］基于混合Petri 網模型，提出一種以最小化各相位車輛的停留時間為目的的優化感應控制方法；文獻［7］通過禁止弧控制各相位綠燈延長時間；文獻［8］提出基于K 近鄰短時交通流預測的自適應控制策略；文獻［9］則提出車路協同環境下最小化車輛均延誤的交叉口實時控制優化方法。

針對無信號交叉口，Dresner 等［10］提出將交叉路口劃分為網格狀，并提出基于預留模式的車輛交叉路口通行控制方案。預留申請被車輛接受，并保持車速直至通過交叉路口。與其它兩種交叉路口車輛控制方案進行比較發現，基于網格狀模型的預留控制模式的車輛通行方案遠優于傳統交叉路口信號控制模式；Lee 等［11-12］在車路協同環境下，討論了無信號交叉口車輛安全通行的控制方法，該方法的主要思想是避免車輛之間軌跡沖突；Raravi 等［13］提出一種車—車協同環境下的車輛通行控制算法；Ahmane 等［14］在車—車協同環境下，提出一種帶乘法器的賦時Petri 網模型，并通過對模型的分析得到相應的車輛通行順序控制策略；Basma 等［15］在車—路協同環境下，采用中央控制站的控制模式，設計一個無信號交叉口的防碰撞系統，該系統將交叉口的傳感器檢測到的信息傳遞給智能路測系統，智能路測系統根據得到的信息預測車輛的行駛軌跡進而避免車輛碰撞；上官偉等［16］在車路協同環境下，設計基于時延Petri 網的無信號交叉口控制方法。該方法依據時延Petri網模型，得到路權的分配結果，對交叉口車輛進行協調控制，引導車輛通過交叉口。文獻［17-20］將交叉路口劃分為不同的空間區域，每個空間區域擁有固定的最大車容量，每一個空間區域采用一個Petri 網單元進行建模。

傳統的有信號調度模式同一時刻只允許同一相位上的車輛通過。為確保安全，當前相位上的車輛在駛離交叉口之前其他相位上的車輛不能進入交叉口。這在一定程度上浪費了交叉口有限的物理空間資源。并且，傳統無信號的控制模式往往假定同一時刻同一物理區域只能被一輛車輛所占用，然而實際過程中，兩輛相向而行的左轉車輛可以共享同一物理空間而不發生碰撞。針對上述問題，本文提出一種基于時間自動機的無信號交叉路口車輛通行控制方法。該方法首先結合車路協同系統關鍵技術，將交叉口劃分為不同的空間區域，將不同的區域設為不同的路權資源；其次，對于每一輛需要通過交叉路口的車輛，根據其需求先后占用的路權資源構建有限時間自動機模型；再次，通過耦合當前時刻所有通行車輛的時間自動機模型，建立交叉路口車輛通行動態模型；最后，考慮不同物理空間資源最大車容量的動態變化特性，以安全性、靈活性、高效性為控制目標設計最優控制器，并以最佳方式引導車輛通過交叉路口。

2 模型構建

為了方便表述，本文研究對象為雙向單車道交叉口，所設計的控制算法同樣適應于雙向兩車道、雙向四車道以及其他類型的交叉口。如圖1 所示，所研究交叉口被劃分為5 個互不相交的空間區域（路權資源），分別為區域A、區域B、區域C、區域D、區域E。車輛在通過交叉口的過程中需要先后占用不同的空間區域。例如，從路段1 駛向路段5的直行車輛需要先后占用區域A、區域C；從路段2 駛向路段5的左轉車輛需要先后占用區域B、區域E、區域C；從路段4 駛向路段7的右轉車輛需要占用區域D。當車輛到達交叉口或者正在通過交叉口時需要向控制器申請相應路權的使用權，控制器在接收到申請后，根據當前時刻交叉口路權占用情況實時引導車輛通過交叉路口。

Fig.1 The intersection discussed in this paper圖1 本文研究的交叉路口

2.1 時間自動機模型

本文使用時間自動機模型［21］模擬車輛通過交叉口的過程。在介紹時間自動機的概念之前，首先引入自動機的定義。

自動機是一個六元組G=(X,Σ,f,Γ,x0,Xm)，其中，X表示有限離散狀態空間；Σ表示有限事件集合；f:X×Σ→X表示狀態遷移函數；Γ:X→2Σ表示可行事件函數：任意給定x∈X，Γ(x)={σ∈Σ:f(x,σ)!}，其中，符號“!”表示有定義；x0表示起始狀態；Xm表示標記狀態集合。

Σ*表示由Σ中元素組成的事件序列集合。f的定義域按照以下方式從X×Σ擴展至X×Σ*：對于空事件序列ε，f(x,ε)=x；任意給定事件序列s∈Σ*和事件σ∈Σ，f(x0,sσ)=f(f(x0,s),σ)。L(G):={s∈Σ*|f(x0,s)!}表示自動機G所產生的系統語言。Lm(G):={s∈Σ*|f(x0,s) ∈Xm}表示自動機G所產生的標記語言。

為了表示時間的流逝，時間自動機將代表一個單位時間流逝的特殊事件“tick”引入到普通自動機中。帶有“tick”事件的時間自動機表示為，其 中=Σ?{tick}表示時間自動機的有限事件集合，表示時間自動機的可行事件函數。

2.2 基于時間自動機的車輛通行模型

本文對每一輛達到交叉口的車輛構建時間自動機模型。由圖1 可知，任意一輛到達交叉口的車輛可能來自路段1、2、3、4。一旦車輛到達交叉口，接下來可能發生3 種交通行為：直行、左轉、右轉。由此可知，所有到達交叉口的車輛總共可以分為12 類。對于每一類，需要分別構建一個時間自動機模型。圖2（a）、（b）和（c）分別描述了一輛來自路段1的左轉、右轉和直行車輛通過交叉口的動態過程。

Fig.2 Timed automata model for a left-turn，go-straight and right-turn vehicle coming from road 1圖2 來自路段1的左轉、直行、右轉車輛時間自動機模型

為了更好地描述模型，模型事件中每個數字和字母的具體含義如下：數字“1”，……，“8”分別代表“路段1”，……，“路段8”，字母“a”“b”“c”“d”和“e”分別代表“區域A”“區域B”“區域C”“區域D”和“區域E”。字母“l”“r”和“s”分別代表“左轉”“右轉”和“直行”。例如，事件σ1al表示一輛左轉車輛由路段1 駛入區域A，事件σeas表示一輛直行車輛從區域E 駛入區域A。為了方便，假定所有事件可以在一個時間單位內執行完畢。

對圖2（a）所示自動機的構造做如下解釋：初始狀態表示一輛來自路段1的左轉車輛到達交叉口。若此時禁止車輛由路段1 駛入區域A（禁止事件σ1al的發生），系統狀態不會隨時間推移發生轉移直到σ1al執行，因此，在狀態0 定義了一個自循環事件tick。當車輛允許駛入區域A 后，隨著事件σ1al的發生，系統從狀態0 躍遷到狀態1。再經過一個時間單位，隨著事件tick的發生，車輛完成從路段1 駛入區域A的動作。相應地，系統從狀態1 躍遷到狀態2。接下來，如果σael被禁止發生，系統狀態同樣不會隨時間推移發生轉移，直到σael執行。因此，在狀態2 定義了自循環事件tick。事件σael執行后（經過一個單位時間），系統從狀態2躍遷到狀態3。以此類推，當系統到達狀態8（標記狀態），車輛離開交叉口。如圖2（b）、圖2（c）所示，可以相同方式得到一輛來自路段1的右轉車輛的時間自動機模型和一輛來自路段1的直行車輛的時間自動機模型，唯一不同的是表征右轉和直行車輛的時間自動機模型比表征左轉車輛時間自動機模型需要更少的狀態。表1 給出了圖2（a）所示自動機每個狀態的物理意義。

Table 1 Meaning of all the states in the automaton depicted in Fig.2（a）表1 圖2（a）所示自動機各狀態的含義

3 優化控制

3.1 問題描述

假設初始時刻一共有n輛車到達交叉口。對于每輛車輛k（k∈{1,2…,n}），構建如上文所描述的時間自動機。各車輛在通過交叉口的過程中既相互獨立又相互影響，它們可能會在同一時刻選擇通過同一空間區域。為了將自動機，……，耦合在一起，引入并行操作［10］。給定時間自動機G1=(X1,Σ1,f1,Γ1,x01,Xm1) 和時間自動機G2=(X2,Σ2,f2,Γ2,x02,Xm2)，自動機G1和G2并行操作（記作G1||G2）后產生自動機G=Ac(X1×X2,Σ1?Σ2,f,Γ1||2,(x01,x02),Xm1×Xm2)，其中，如果σ∈Γ1(x1)?Γ2(x2)，則f((x1,x2),σ)=(f(x1,σ),f(x2,σ))；如 果σ∈Γ1(x1)Σ2，則f((x1,x2),σ)=(f(x1,σ),x2)；如 果σ∈Γ2(x2)Σ1，則f((x1,x2),σ)=(x1,f(x2,σ))；其他情況沒有定義。Ac(·)表示取自動機由初始狀態可到達部分。無信號交叉口車輛通行動態過程表征為：圖3給出了表征由一輛來自路段1的直行車輛和一輛來自路段3的右轉車輛所構成的無信號交叉口車輛通行模型。

Fig.3 System model generated by a go-straight vehicle from road 1 and a right-turn vehicle from road 3圖3 來自路段1的直行車輛和來自路段3的右轉車輛所生成的系統模型

以狀態（2，1）為例，狀態2 和狀態1 分別表示當前時刻直行車輛（由路段1 駛入區域A）和右轉車輛（由路段3 駛入區域C）所處狀態。在狀態（2，1）處有定義的事件（事件σacs、事件tick）可以理解為當前時刻可能發生的事件集合。例如，若此時在一個單位時間流逝之前有使能事件σacs，直行車輛從區域A 駛入區域C。由于右轉車輛此時處于區域C，兩輛車發生碰撞。同理，當系統處于狀態（4，1）時直行車輛和右轉車輛同時占用區域C，車輛發生碰撞。

無信號交叉口的車輛通行控制問題可以簡單描述為：尋找一條耗時最短事件序列（tick數最少），確保系統從初始狀態（0，0）（所有車輛駛入交叉口）經歷一系列的安全狀態（避免到達狀態（3，1）、（4，1））后最終到達標記狀態（6，2）（所有車輛駛離交叉口）。具體地，設計控制器執行滿足以下3 個控制目標最優事件序列：①安全性：所有通行車輛彼此間無碰撞；②無死鎖：所有通行車輛不得相互阻擋，影響彼此通行；③高效性：所有車輛以最短時間通過交叉口。

3.2 優化控制

本文在線設計符合安全性、無死鎖、高效性的最優控制器。設計過程分為3 步：

（1）確保系統安全。首先將系統中的所有非法狀態從系統中刪除（確保最終計算得到的車輛通行事件序列所到達的狀態是安全的）。如圖3 所示，若系統處于狀態（2，1），直行車輛處于區域A，右轉車輛處于區域C。如果接下來選擇使能事件σacs，則直行車輛由區域A 駛入區域C，兩輛車輛發生碰撞。定義類似（3，1）、（4，1）的狀態為非法狀態。假定區域A、B、C、D、E 同一時刻最多可容納兩輛相向行駛的車輛，其他情況下最多可容納一輛車輛。為了安全起見，首先將自動機中所有違反上述原則的狀態（非法狀態）刪除，所獲得的子自動機記作。可以發現，自動機只保留了所有可以使車輛安全通過交叉口的事件序列。

（2）確保系統無阻塞現象。若系統存在死鎖狀態，則稱系統是阻塞的，所謂死鎖狀態，是指從該狀態不能到達最終標記狀態（不能確保所有車輛通過交叉口）。圖4 給出了系統發生阻塞的兩種情形。

Fig.4 Two examples of system stagnation caused by improper movements of vehicles圖4 兩種由于車輛不正確移動造成的系統阻塞現象

在圖4（a）中，由北向南車輛的前進方向被由西向東的車輛阻礙，由西向東車輛的前進方向被由南向北的車輛阻礙，由南向北車輛的前進方向被由東向西的車輛阻礙，由東向西車輛的前進方向被由南向北的車輛所阻礙。在當前情形下，這4 輛車輛都無法駛離當前位置，因而形成阻塞。上述現象可表征為系統當前時刻到達一個死鎖狀態。的最大非阻塞子系統可通過刪除中所有滿足條件1 和條件2的狀態，其中，條件1 描述為x不是一個標記狀態；條件2 描述為從x出發不存在一條可以到達標記狀態的事件序列。本文記作的最大非阻塞子系統為H。

（3）確保控制策略的高效性。高效性要求從系統當前狀態出發到系統標記狀態結束的事件序列中選擇一條時間花費最短的事件序列（包含事件tick數量最少）。

為此，對H中的每一個變遷(x,σ) ∈XH×Σ，定義一個成本函數C:XH×Σ→?，其中? 是實數集。C(x,σ)是當系統處在狀態x時執行事件σ的成本。對所有的x∈XH和σ∈Σ，如 果σ=tick，那么定義C(x,σ)=1，否則，定義C(x,σ)=0。對于一個有限事件序列s=σ1σ2…σk∈L(H)，定 義si=σ1σ2…σi，i=1,2,…,k，且s0=ε，定義fH(x0,si)=xi。事件序列s的累積成本函數可用式（1）計算：

為了平衡計算過程的高效性和計算結果的最優性，本文的無信號車輛最優調度控制器求解描述如下：給定當前時刻系統所處狀態x∈XH，求解并執行滿足以下要求的最優事件序列，如式（2）。

其中，H(x) 表示H中從狀態x起的可到達部分；L≤N(H(x))={s∈L(H(x)):[fH(x,s) ∈Xm∧|s|≤N]∨[|s|=N]}表示L(H(x))中所有滿足：從狀態x起最終到達標記狀態且長度不超過N的事件序列，或者從狀態x起長度等于N的事件序列。

為了節省計算，本文僅計算從當前時刻開始，接下來N步之內的最優先車輛調度方案。在實施N步之后，本文策略是以最新到達的狀態為初始狀態并再次計算接下來N步的最優解。此外，給定系統H的現有狀態x∈XH，如果此時一輛車輛即將到達交叉口，模型H應該更新為H=H(x)||Gn+1，其中Gn+1為即將到達車輛的時間自動機模型。在模型更新后，需要按照上述方法重新計算最優控制器以滿足所有控制目標。最優控制策略，即優化函數，可根據深度優先算法計算得出。

4 實驗及仿真

為驗證文本模型和優化算法的有效性，使用PyCharm進行模型構建、模擬車輛生成，以及在線控制仿真。設計3個獨立實驗，第1 個實驗測試了平衡車流條件下（各交叉口到達車輛隨機數符合固定期望的泊松分布），測試在本文所設計控制器的控制下無信號交叉口的車輛排隊長度；第2 個實驗測試了平衡車流條件下在傳統固定的四相位有信號控制模式下交叉路口的車輛排隊長度；第3 個實驗測試了非平衡車流條件下（各交叉口到達車輛隨機數符合期望變化的泊松分布），在本文所設計控制器的控制下無信號交叉口的車輛排隊長度。

4.1 實驗1：平衡車流條件下無信號交叉口控制效果測試

首先在平衡車流下，測試本文提出的基于時間自動機模型的無信號交叉口車輛調度算法的表現。假設所有到達路口的車輛左轉、直行、右轉的概率分別為0.33、0.33、0.33。圖5 給出了平衡車流下當交叉口車輛到達數符合期望為0.5、0.75、1、1.25的泊松分布時，交叉口車輛排隊數平均值的4 次實驗結果。每次實驗仿真時長為1 000s。通過圖5 可知，當期望值為0.5、0.75、1、1.25 時，仿真周期內排隊車輛趨于穩定，車輛平均排隊長度分別穩定在0.7 輛、1.0輛、1.4 輛、2.0 輛左右，驗證了本文算法在平衡車流條件下具有較強的魯棒性。

Fig.5 Queue length of vehicles with steady traffic flow圖5 平衡車流下的車輛排隊長度

4.2 實驗2：平衡車流條件下傳統固定四相位有信號交叉口控制效果測試

圖6 給出了平衡車流下當交叉口車輛到達數符合期望為0.5、0.75、1、1.25的泊松分布時，在傳統固定的四相位有信號控制方式下交叉口車輛排隊數平均值的4 次實驗結果。其中，每個相位的持續時間為20s。每次實驗仿真時長為1 000s。由圖6 可知，較無信號的調度方式，固定相位有信號調度方式顯示出較大的波動性。當期望值為0.5、0.75、1、1.25 時，4 次實驗的車輛平均排隊長度分別為4.8、8.2、10.2、15.3 輛，比無信號控制方式平均排隊長度明顯增長。這是因為有信號控制方式需要多次切換相位，顯示為紅燈的相位上車輛被嚴格禁止通行，只有當該相位顯示為綠燈時，車輛才被允許放行。在車輛放行完畢后如果該相位依然顯示為綠燈，會造成交叉口有限物理空間上的浪費，進而影響交叉口的吞吐能力。與此同時，相位之間的頻繁切換會導致黃燈時間占比增加進而損失更多的車輛通行時間。

Fig.6 Queue length of vehicles at an intersection controlled by traffic light圖6 信號燈控制的交叉口車輛排隊長度

4.3 實驗3：非平衡車流條件下無信號交叉口控制效果測試

實驗1 和實驗2 認為交叉口的車輛到達率一成不變，然而現實中交叉口的車輛到達情況可能會隨著時間變化而發生改變。為此，在實驗3 引入如圖7 所示的馬爾科夫跳變模型，以模擬交叉口車輛到達率的動態變化過程。所考慮模型總共有兩個狀態，分別為Case 1 和Case 2。假設在模型處于狀態Case 1 時，交叉口車輛到達車輛數滿足均值為1的泊松分布，處于狀態Case2 時，交叉口車輛到達數滿足均值為2的泊松分布。當模型處于狀態Case1 時，其每一步由狀態Case1 跳轉至狀態Case2的概率為p2，保持不變的概率為p1。當模型處于狀態Case2 時，其每一步由狀態Case2 跳轉至狀態Case1的概率為p4，保持不變的概率為p3。由于狀態Case1、Case2 在仿真過程的每一步都存在發生轉移的概率，考慮到車輛到達率在短時間內發生改變的概率較低，因此設定如下狀態轉移概率：p1=0.8，p2=0.2，p3=0.8，p4=0.2。

Fig.7 Markov model圖7 馬爾可夫模型

圖8 給出了非平衡車流下交叉口車輛排隊數隨著時間的變化過程。實驗仿真時長為1 000s，每間隔20s 取一次車輛排隊長度的平均值。通過圖8 可知，非平衡車流條件下，排隊車輛呈現出一定的波動性，但總體趨于1～2 輛之間，仍然顯示出較強的魯棒性。

Fig.8 Queue length of vehicles with unsteady traffic flow圖8 非平衡車流下的車輛排隊長度

5 結語

本文構建了一個無信號交叉口微觀模型，該模型下通行車輛的時間自動機模型并行產生，充分考慮了車輛在通行過程中需要使用的物理空間資源。并且，基于安全性、靈活性、高效性等控制指標設計了車輛在線調度算法。實驗結果表明，所設計算法在車流量較小時具有很好的魯棒性，能夠及時有效地放行交叉口的車輛。較傳統固定相位有信號控制方式，所提出的控制模式使得交叉路的車輛通行能力得到進一步提升。如何實現多個交叉口、路段之間的協同控制則是后續研究的重點。