无信号交叉口车辆通行控制研究

钱怡杉

（上海理工大学光电信息与计算机工程学院，上海 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 结语

本文构建了一个无信号交叉口微观模型，该模型下通行车辆的时间自动机模型并行产生，充分考虑了车辆在通行过程中需要使用的物理空间资源。并且，基于安全性、灵活性、高效性等控制指标设计了车辆在线调度算法。实验结果表明，所设计算法在车流量较小时具有很好的鲁棒性，能够及时有效地放行交叉口的车辆。较传统固定相位有信号控制方式，所提出的控制模式使得交叉路的车辆通行能力得到进一步提升。如何实现多个交叉口、路段之间的协同控制则是后续研究的重点。