适用于无信号交叉口的图表可解释规划方法：通过求解空间压缩优化车道时间协调

《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：Graph interpretable planning for signal-free intersections: Optimizing lane-time coordination through solution space compression

　　李运飞|罗东宇|王江峰|齐崇凯|杨志成
北京交通大学交通与运输学院，中国北京市海淀区上远村3号，邮编100044

摘要
在高度连接和自动化的交通系统中，传统的交通信号灯存在显著的效率限制，使得无信号灯交叉口控制成为一种有前景的替代方案。为了提高交叉口的效率同时保持较低的计算成本，本文提出了一种用于无信号灯交叉口车辆路径规划的可解释图模型（IGM）。该模型由两个互补的模块组成。在冲突区，轨迹变形图编码了冲突点的占用约束，并在全方向转向车道（ADTL）配置下共同确定入口车道分配和车辆通过顺序，从而压缩了解决方案空间并实现了高效的实时规划。在准备区，基于时间等价节点的轨迹规划超图明确模拟了变道和速度调整过程，以确保车辆在进入交叉口之前的轨迹可行性。IGM通过与八个基准模型进行评估，包括基于预约的控制、全局无冲突、子区无冲突和固定车道配置。实验结果表明，所提出的方法在效率、适应性和计算成本方面表现更优。IGM实现了最高的吞吐量（约5932辆/小时），并保持了较低的平均延迟，从1000辆/小时时的0.01秒到6000辆/小时时的6.25秒。结果还强调了协调ADTL配置与主动入口车道分配的重要性，因为没有车道分配的基于ADTL的模型可能由于车道利用效率低下而表现不佳。此外，IGM对不平衡的转向分布表现出强的适应性，并在交通需求增加的情况下保持了稳定的优化时间，支持实时的无信号灯交叉口控制。

引言
联网和自动化的车辆（CAVs）不需要像人类驾驶员那样探索未知环境；相反，它们对环境有全面的了解（Zhang等人，2023年）。一旦CAVs变得普遍，像交通灯这样的工具（人类驾驶时代的标志）可能会因为其显著的效率缺陷（包括时间损失和对动态交通流的适应能力差）而被边缘化（Hu等人，2021年）。取而代之的是高度集中的、无信号灯的控制系统（Lu等人，2022年；Chen和Englund，2016年）。早期关于无信号灯交叉口控制的研究包括（Kolodko和Vlacic，2003年）对合作自动化交叉口系统的初步实现，而Dresner和Stone（2004年、2005年、2006年）提出了基于预约的多智能体框架，该框架随后发展成了自主交叉口管理（AIM）范式。这种方法将交叉口划分为不同的子区域，车辆发送到达时间的请求以缓解冲突（He等人，2018年；Azadi等人，2023年）。基于预约的AIM仅需要传输预约请求，通信需求较低（Li等人，2013年；Stevanovic和Mitrovic，2019年）。然而，这些方法本质上遵循先进先出（FIFO）原则（He等人，2018年），只能确保车辆按到达顺序通过，而不能根据最小化全局延迟的目标调整通过顺序，导致交叉口容量降低（Xu等人，2020年）。因此，研究人员逐渐将注意力转向更加灵活和高效的基于优化的方法。
与预约策略不同，优化方法旨在通过主动调整车辆通过顺序和轨迹来实现无冲突的合作，主要通过处理时间和空间维度中的车辆通过顺序问题来实现。在时间维度上，建立了一个小的解决方案空间，并使用适当的排队理论方法使车辆能够以紧凑的顺序通过（Pei等人，2022年）；在空间维度上，减少了无冲突区域的范围，放宽了不兼容车辆的约束并提高了空间利用率（Xu等人，2020年）。通过优化车辆通过顺序和到达时间，可以提高容量。然而，大多数研究仍然遵循来自人类驾驶时代的固定车道策略（Cai等人，2022a）。相比之下，由He等人（2018年）首次提出的全方向转向车道（ADTL）策略取消了进入车道的固定转向方向分配，充分利用了车道容量，并更有效地适应了变化的交通流量。与无车道方法相比，ADTL在保持部分车道结构的同时允许灵活的车道使用。虽然无车道方法完全消除了车道边界，代表了空间资源利用的终极灵活性（Naderi等人，2024a；Naderi等人，2024b），但它们在安全验证和计算复杂性方面面临重大实施挑战。因此，基于ADTL的策略在灵活性和可实现性之间提供了一个实际的折中方案，使其成为自动驾驶车辆交通控制的一个有前景的方向。
从设计角度来看，ADTL最初是为了消除车辆在交叉口上游和下游路段进行变道操作的需要，从而减少由变道行为引起的道路拥堵和安全风险（He等人，2018年；Li等人，2013年）。然而，作为道路系统的瓶颈，交叉口的容量通常远低于上游和下游路段的容量，因此应优先考虑交叉口的效率（Wei等人，2017年）。在100% CAV的环境中，可以精确规划变道行为以避免交通波动（Lee和Park，2012年）。因此，通过将主动入口车道分配与基于ADTL的策略相结合来优化交通，最大化交叉口空间的利用已成为一个可行和必要的研究方向。与传统固定车道策略的优化方法相比，这种方法可以进一步提高交叉口的时空效率。然而，ADTL的固有特性为车辆提供了更大的灵活性，导致冲突点（CPs）的数量显著增加。例如，一个四车道双车道的固定车道交叉口有52个CPs，而基于ADTL的交叉口有116个CPs。CPs的增加导致解决方案空间的扩大和计算需求的指数级增长，使得为固定车道开发的现有方法不足以应对ADTL的计算要求。因此，解决由于CPs激增导致的解决方案空间扩大问题是有效规划ADTL配置下无信号灯交叉口交通流的关键。解决方案空间的大小与内部约束密切相关。内部约束指的是模型或算法中嵌入的条件，它们提前过滤掉不符合特定要求的案例，确保生成的解决方案从一开始就满足这些条件。相比之下，外部约束通常用于确定已经生成的解决方案的可行性（Yao和Johnson，1997年）。一个好的算法可以最大化内部约束，有效过滤掉大量无效解决方案，压缩可行解决方案空间，并构建一个小的解决方案空间（Wei等人，2017年）。因此，扩展内部约束并开发有效的方法来减少解决方案空间对于建立一个小的解决方案空间至关重要。
此外，为了将主动入口车道分配与基于ADTL的策略相结合以优化交通，需要在车辆到达交叉口之前对它们的运动轨迹进行建模和优化，以验证优化模型的可行性。然而，大多数现有研究没有考虑冲突区之前的变道行为（Zhao等人，2024a），或者假设车辆可以立即切换到特定车道（Xu等人，2022a；Zhou等人，2024），而没有区分准备区和冲突区的速度差异（Cai等人，2022b）。实际上，由于转向速度限制和容量差异等因素，道路段上的平均速度往往超过交叉口的平均速度（Mollu等人，2018年）。将现有方法应用于基于ADTL的交叉口控制时，发现了两个挑战：（1）如何加强内部约束并构建一个小的解决方案空间。在时间维度上，应尽可能紧凑地安排车辆；在空间维度上，应放宽多余的无冲突约束以提高空间利用率。（2）如何在基于ADTL的策略下共同确定车辆的入口车道分配，从而优化交叉口交通流。这一过程还必须考虑变道过程和速度调整，以确保车辆在交叉口的到达时间和位置是可行的。
为了解决基于ADTL的无信号灯交叉口的挑战，引入了一种可解释图模型（IGM）。通过构建轨迹变形图，冲突区内车辆的冲突无序约束在可解释图结构中得到了全面的表示。交叉口中车辆的三维时空约束首先被转换为一个降维（1.5D）图，由一个连续维度和一个离散维度组成。这种转换将每个冲突点（CP）处的复杂排队问题重新表述为一个轨迹变形问题。结果，可以构建一个紧凑且小的解决方案空间，提高时间和空间效率。通过建立车辆轨迹规划超图，准备区内的非碰撞轨迹规划约束在可解释的超图结构中表示，从而构建优化的轨迹规划解决方案。主要贡献如下：
（1）为基于ADTL的无信号灯交叉口开发了一个基于图的解决方案空间压缩框架。所提出的轨迹变形图将CP占用约束编码为可解释的结构，大大减少了ADTL引入的扩大冲突交互下的可行解决方案空间。
（2）提出了一个联合优化框架，以协调ADTL配置下的入口车道分配和冲突区通过时间。该框架通过明确耦合车道分配和通过时间调度，而不是将它们独立处理，扩展了现有的ADTL研究。
（3）进一步为准备区开发了轨迹规划超图，明确模拟了变道和速度调整过程。这使得计划的入口车道和到达时间在物理上可行，从而将冲突区调度与准备区轨迹执行联系起来。

本文的其余部分结构如下：第2节提供了有关无信号灯交叉口的相关工作概述。第3节介绍了相关概念和框架。第4节详细介绍了冲突区和准备区的可解释图方法。第5节进行了不同输入的比较实验并分析了结果。第6节总结了文章并概述了未来的研究方向。

文献综述
鉴于关于ADTL配置的研究很少，且方法论与固定车道配置有相似之处，首先对固定车道配置下的AIM策略进行了全面回顾，然后概述了关于ADTL配置的有限研究。一些研究关注每辆车本身的好处（Sun和Kim，2024年）。Li等人（2022年）将所有冲突车辆作为领导者和追随者的对进行分配。每辆车都最大化最小值。

初步工作
本节提供了一些相关概念。然后，提出了一种专为专用自动驾驶车辆区域定制的可解释图方法。该方法包括两个主要组成部分：冲突区的轨迹变形图和准备区的轨迹规划超图。

方法论
IGM框架分为两个部分：冲突区的轨迹变形图和准备区的轨迹规划超图。

实验
为了探索ADTL和固定车道之间的效果比较，以及CP无冲突策略和全局无冲突策略之间的比较，使用MATLAB R2021a在配备Intel Core i7-14700KF@3.4GHz处理器的计算机上进行了实验模拟。

结果与讨论
在本节中，IGM与模型1-8进行了比较，并从三个角度评估了这些模型：操作可行性、公平性和有效性。此外，还比较了不同目标方向输入比例下每个模型的延迟。冲突区的代码和可视化已开源：https://github.com/asldkjhgf/signal-free-intersection.git。

结论
本研究提出了一种用于ADTL配置下无信号灯交叉口控制的IGM。所提出的框架使用基于图的结构表示车辆交互，实现可解释的轨迹规划和高效优化。在冲突区，开发了一种轨迹变形图来编码冲突点占用约束并压缩可行解决方案空间。在准备区，基于时间等价节点理论的轨迹规划超图…

作者贡献声明
李运飞：撰写——原始草稿，可视化，方法论，概念化。
罗东宇：撰写——原始草稿，形式分析。
王江峰：方法论，资金获取。
齐崇凯：项目管理，形式分析。杨志成：可视化技术、形式化分析。利益冲突声明：作者声明他们没有已知的财务利益冲突或可能影响本文所述工作的个人关系。