摘 要：無信號交叉口車輛通行調(diào)度問題是智能交通領(lǐng)域的研究重點(diǎn)，由于車輛通行順序決策問題的解空間隨著車輛數(shù)增加而指數(shù)級增長，在保證實(shí)時(shí)性的同時(shí)找到較優(yōu)通行順序成為無信號交叉口通行調(diào)度的一大問題。針對該問題提出一種基于自適應(yīng)蒙特卡羅樹搜索算法的無信號交叉口車輛通行調(diào)度方法，采用分層式框架，上層集中式順序決策，下層分布式軌跡規(guī)劃。首先，建立基于沖突點(diǎn)的交叉口模型，將網(wǎng)聯(lián)車加入到待搜索隊(duì)列中，根據(jù)交叉口中的車輛通行特點(diǎn)設(shè)計(jì)通行順序的蒙特卡羅樹搜索流程，以總通行時(shí)間為指標(biāo)建立評價(jià)函數(shù)，然后針對不同交通情景設(shè)計(jì)自適應(yīng)探索系數(shù)及其他超參數(shù)，使算法在求解不同車輛數(shù)時(shí)以及搜索的不同時(shí)期保持最佳狀態(tài)。軌跡規(guī)劃環(huán)節(jié)以加速度二范數(shù)為目標(biāo)函數(shù)，以速度、加速度以及始終點(diǎn)位置等為約束，建立最優(yōu)控制命題求解車輛軌跡。最后，進(jìn)行實(shí)驗(yàn)，結(jié)果表明該算法相較于其他算法在數(shù)值仿真和微縮平臺實(shí)驗(yàn)中最大優(yōu)化幅度分別達(dá)到33.42%和38.04%，為無信號交叉口車輛通行調(diào)度提供了一個(gè)有效解決方案。

關(guān)鍵詞：智能交通； 無信號交叉口車輛通行調(diào)度； 蒙特卡羅樹搜索； 智能網(wǎng)聯(lián)車； 微縮平臺

中圖分類號：U495 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2024）07-023-2087-06

doi：10.19734/j.issn.1001-3695.2023.11.0544

Vehicle traffic scheduling strategy at unsignalized intersectionsunder vehicle road coordination

Abstract：The vehicle traffic scheduling problem at unsignalized intersections is the research focus in the field of intelligent transportation. Because the solution space of vehicle traffic order decision problem increases exponentially with the increase of the number of vehicles， finding the optimal traffic sequence while ensuring the real-time performance has become a major problem for traffic scheduling at unsignalized intersections. To solve this problem， this paper proposed a vehicle traffic scheduling method at unsignalized intersections based on adaptive Monte Carlo tree search algorithm， which used a hierarchical framework， upper level centralized sequential decision-making， and lower level distributed trajectory planning. Firstly， the intersection model based on the conflict point was established， the connected vehicles were added to the queue to be searched， the Monte Carlo tree search process of the traffic sequence was designed according to the vehicle traffic characteristics in the intersection， the evaluation function was established with the total traffic time as the index， and then the adaptive exploration coefficient and other super parameters were designed for different traffic situations， so that the algorithm could maintain the best state in solving different vehicle numbers and different search periods. In the trajectory planning process， the acceleration two norm was taken as the objective function， and the speed， acceleration and the position of the starting point were taken as constraints to establish the optimal control proposition to solve the vehicle trajectory. Finally， experiments were carried out， and the results show that compared with other algorithms， the maximum optimization amplitude of this algorithm in numerical simulation and micro platform experiment is 33.42% and 38.04% respectively， which provides an effective solution for vehicle traffic scheduling at unsignalized intersections.

Key words：intelligent transportation; unsignalized intersection vehicle traffic scheduling; Monte Carlo tree search（MCTS）; connected automatic vehicle（CAV）; miniature platform

0 引言

近年來，新能源汽車迅速發(fā)展，汽車電動化技術(shù)逐漸成熟，汽車智能化拉開序幕［1］。早在2011年，國家科技部已設(shè)立“智能車路協(xié)同關(guān)鍵技術(shù)研究”主題項(xiàng)目，到2022年清華大學(xué)智能研究院牽頭發(fā)表《面向自動駕駛的車路協(xié)同關(guān)鍵技術(shù)與展望》2.0版本，“車路協(xié)同”概念在被逐步完善與實(shí)踐。在所有交通場景中，約50%的城市交通事故發(fā)生在交叉口［2］，是造成城市交通擁堵的主要原因。因此無信號交叉口是車路協(xié)同技術(shù)的重點(diǎn)應(yīng)用場景，被認(rèn)為是緩解交通擁堵和提高安全性的最有潛力的方法之一［1，3］。智能網(wǎng)聯(lián)車（CAV）的V2X（vehicle to everything）技術(shù)使得CAV可以與相鄰車輛共享其駕駛狀態(tài)和意圖［4］，實(shí)現(xiàn)車路協(xié)同控制，更好地協(xié)調(diào)其運(yùn)動，緩解交通擁堵。

在無信號交叉口對CAV進(jìn)行協(xié)同控制的關(guān)鍵問題是確定CAV通過交叉口的最優(yōu)順序［5，6］。國內(nèi)外學(xué)者對交叉口通行順序決策問題進(jìn)行了相關(guān)研究［7～9］。文獻(xiàn)［10］首先提出了基于預(yù)留的算法來控制不同車道上兩車經(jīng)過同一路口時(shí)避免發(fā)生碰撞，該算法的核心思路是先到先服務(wù)（first come first service，F(xiàn)CFS）。也有學(xué)者在FCFS的基礎(chǔ)上對路口多車協(xié)同的求解方法和優(yōu)化目標(biāo)作出進(jìn)一步改進(jìn)［11，12］。Carlino等人［13］在FCFS基礎(chǔ)上提出了基于拍賣的路口場景協(xié)同決策方法，其性能優(yōu)于先進(jìn)先出策略，但中高車流場景下的通行效果仍不理想?；陬A(yù)留的方法核心在于獲得無沖突通行順序，并未考慮到通行順序的最優(yōu)性。為提高通行效率，基于優(yōu)化的順序決策方法被提出。Müller等人［14］將車輛通過沖突區(qū)的順序轉(zhuǎn)換為一個(gè)混合整數(shù)規(guī)劃問題，在確定好車輛通行順序之后，再據(jù)此規(guī)劃車輛的時(shí)空軌跡。Ahn等人［15］在優(yōu)化模型中進(jìn)一步考慮了安全因素。然而優(yōu)化方法的解空間隨著車輛數(shù)的增多呈指數(shù)增長，使其難以滿足實(shí)時(shí)性要求。為提高求解速度，已有研究對交叉口模型做了較多簡化，比如將整個(gè)交叉口視為沖突點(diǎn)，這也使得算法求解出的通行順序與真實(shí)交叉口車輛通行情況有一定差距。Chen等人［16］建立了基于沖突點(diǎn)的交叉口模型，采用圖搜索的方法進(jìn)行求解，但其重點(diǎn)在于獲得無沖突車輛通行順序，并未對結(jié)果的最優(yōu)性進(jìn)行論證。Li等人［6］將車輛通行順序規(guī)劃問題的解空間描述成一個(gè)樹型結(jié)構(gòu)，采用蒙特卡羅樹搜索方法求解車輛通行順序。Xu等人［17］沿用文獻(xiàn)［6］提出的樹型解空間表示法，并結(jié)合啟發(fā)式規(guī)則以提高搜索效率，但兩者在交叉口的建模上均采用了將交叉口沖突區(qū)分解為小塊沖突區(qū)的方式，并未考慮交叉口內(nèi)同時(shí)通行多輛車的情況。Pei等人［18］定義了車輛通行狀態(tài)，構(gòu)建小尺度的狀態(tài)空間，并通過動態(tài)規(guī)劃搜索出通行順序，盡管獲取到了小尺度狀態(tài)空間中的最優(yōu)解，但存在壓縮狀態(tài)空間過程中丟失最優(yōu)解的問題。李磊等人［19］通過選取局部最優(yōu)組合的方式，快速獲取到了安全可行的通行解，但對全局最優(yōu)性欠缺考慮。

如前所述，現(xiàn)有工作大多側(cè)重于通過特定的方法獲得通行順序，側(cè)重于無沖突解決方案的可行性，忽視了交通效率。有些研究為了弱化最優(yōu)性和計(jì)算復(fù)雜度的矛盾，對交叉口沖突模型進(jìn)行簡化，使得其搜索空間已失去全局最優(yōu)性。因此，考慮最優(yōu)通行順序的無信號交叉口調(diào)度問題尚未得到較好解決。本文提出了一種無信號交叉口通行調(diào)度方法，將問題解耦為上層集中式順序決策和下層分布式控制兩部分。上層順序決策環(huán)節(jié)中建立基于沖突點(diǎn)的無信號交叉口模型，并改進(jìn)蒙特卡羅樹搜索流程，對算法的超參數(shù)進(jìn)行優(yōu)化，平衡搜索結(jié)果的最優(yōu)性與搜索的實(shí)時(shí)性。下層軌跡規(guī)劃根據(jù)給出的車輛到達(dá)時(shí)間建立最優(yōu)控制命題求解最優(yōu)軌跡。最后進(jìn)行仿真和實(shí)驗(yàn)，證明該方法的有效性和優(yōu)越性。

1 無信號交叉口車輛協(xié)同調(diào)度框架

1.1 無信號交叉口模型

由于交叉口存在多重形態(tài)，本文選擇典型雙向四車道交叉口進(jìn)行研究，后續(xù)可拓展至更為復(fù)雜的交叉口。如圖1所示，由于右拐車道的路徑未與其他車道相沖突，所以并未包含右拐車道。入口車道編號為0～7，每條道路包含左轉(zhuǎn)和直行車道。整個(gè)交叉口區(qū)域分為沖突區(qū)和控制區(qū)。其中，控制區(qū)內(nèi)沖突區(qū)外的車道長度為L ，單個(gè)車道寬度為W，沖突區(qū)域邊長為LS。

交叉口的車輛沖突主要發(fā)生在沖突區(qū)內(nèi)，將各車道在沖突區(qū)內(nèi)通行路徑的交點(diǎn)定義為沖突點(diǎn)，圖1沖突區(qū)內(nèi)一共包含16個(gè)沖突點(diǎn)。根據(jù)車輛所在的車道信息可確定其通過交叉口的路徑，當(dāng)兩車在沖突區(qū)內(nèi)的路徑存在交點(diǎn)且交點(diǎn)處兩車的通行時(shí)間窗存在重疊，則兩車有碰撞關(guān)系，如圖1中車輛所示，A車和C車、E車屬于無碰撞關(guān)系，A車和B車、D車屬于有碰撞關(guān)系。不存在碰撞關(guān)系的車道在表1中列出。

每輛進(jìn)入控制區(qū)的CAV都將被分配一個(gè)唯一的標(biāo)識Vi，車輛間是否存在沖突關(guān)系可以通過車道編號在表1中進(jìn)行查詢。針對無信號交叉口車輛通行順序決策問題，提出如下假設(shè)：a） 交叉口內(nèi)所有車輛均為CAV；b） CAV在進(jìn)入控制區(qū)前已換道至目標(biāo)車道；c） 不考慮CAV與其他設(shè)備通信過程中丟包的情況；d） 車輛在沖突區(qū)內(nèi)的行駛速度恒定。

1.2 車輛協(xié)同調(diào)度框架

本文針對集中式調(diào)度復(fù)雜度高的問題，采用雙層控制框架，上層為交叉口管理層，下層為車輛控制層，將通行順序決策和車輛軌跡規(guī)劃控制進(jìn)行解耦，降低問題復(fù)雜度，如圖2所示。交叉口管理層采用集中式架構(gòu)，交叉口中央服務(wù)器獲取交叉口內(nèi)的車輛信息，完成車輛通行順序決策。車輛控制層采用分布式架構(gòu)，各CAV獨(dú)自完成軌跡規(guī)劃和控制的工作。為避免全連接通信帶來的巨大通信負(fù)擔(dān)，采用車輛分組通信機(jī)制。交叉口管理層只與車輛通行組中的組長進(jìn)行通信，通行組組長與同組的車輛進(jìn)行通信。通行組組長定義為同組中最接近沖突區(qū)的車輛。

交叉口管理層需要具有高動態(tài)響應(yīng)能力，以應(yīng)對動態(tài)變化的交通情況。因此設(shè)計(jì)了一種以固定時(shí)間周期更新的順序決策策略，服務(wù)器以固定時(shí)間間隔檢測交叉口內(nèi)的車輛情況，若交叉口內(nèi)存在新增車輛，則調(diào)用順序決策算法，否則保持上次的決策結(jié)果。

2 順序決策方法

在車輛數(shù)目較多時(shí)，樹搜索方法通常無法在有限的計(jì)算資源和時(shí)間內(nèi)探索完所有的節(jié)點(diǎn)。本文使用MCTS與剪枝規(guī)則來提高搜索效率，并使搜索結(jié)果盡可能接近最優(yōu)解。

2.1 基于蒙特卡羅樹搜索的通行順序決策算法

蒙特卡羅樹搜索包含選擇、拓展、模擬和反向傳播四個(gè)主要步驟。搜索結(jié)束的條件為達(dá)到設(shè)定迭代次數(shù)或計(jì)算時(shí)間，或搜索結(jié)果超過一定回合數(shù)不發(fā)生變化。

搜索中各步驟的功能為：a）選擇。選擇UCB值最大的節(jié)點(diǎn)。b）拓展。在未完全拓展的節(jié)點(diǎn)下添加一個(gè)新子節(jié)點(diǎn)。c）模擬。對新創(chuàng)建的子節(jié)點(diǎn)使用隨機(jī)策略進(jìn)行探索，直到葉節(jié)點(diǎn)（最底層節(jié)點(diǎn)），對結(jié)果進(jìn)行評價(jià)。d）反向傳播。將模擬的結(jié)果沿新節(jié)點(diǎn)向上反饋至根節(jié)點(diǎn)，更新所有父節(jié)點(diǎn)的信息。

其中，使用置信上界（upper confidence bound，UCB）對節(jié)點(diǎn)價(jià)值進(jìn)行評估，不僅考慮該節(jié)點(diǎn)的當(dāng)前價(jià)值，也將節(jié)點(diǎn)的被選擇次數(shù)納入考量，其計(jì)算公式為

首先對車輛信息進(jìn)行預(yù)處理，由于控制區(qū)內(nèi)不允許換道，車輛具有先進(jìn)先出的特征，所以采用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)保存交叉口各車道的車輛。以圖1中的車輛為例，生成的待搜索隊(duì)列如圖3所示。車輛通行順序決策問題可轉(zhuǎn)換為由所有可能的通行順序組成的解空間中的樹搜索問題，每個(gè)葉節(jié)點(diǎn)包含車輛通行順序信息和待搜索隊(duì)列信息。其中，ROOT節(jié)點(diǎn)的通行順序?yàn)榭涨掖阉麝?duì)列中包含所有的車輛。

以圖3所示的待搜索隊(duì)列為例，介紹如何運(yùn)用樹搜索方法進(jìn)行通行順序決策。首先創(chuàng)建根節(jié)點(diǎn)ROOT，根節(jié)點(diǎn)中的通行順序置為空，初始化根節(jié)點(diǎn)的待搜索隊(duì)列。在搜索的第一層，ROOT節(jié)點(diǎn)從待搜索隊(duì)列的頭部選擇拓展車輛，可選的車輛包括A、B、C、D，以選擇C車為例，生成子節(jié)點(diǎn)C，其待搜索隊(duì)列繼承自ROOT節(jié)點(diǎn)并刪除其中的車輛C。子節(jié)點(diǎn)重復(fù)以上拓展流程，直到待搜索隊(duì)列中的車輛為空。搜索過程如圖4所示，其中紅色加粗節(jié)點(diǎn)的待搜索隊(duì)列信息如圖5所示。

2.2 車輛通行組

通過上述樹搜索獲得的通行順序如圖4所示為CBDEA，僅包含車輛通過交叉口時(shí)的先后順序信息，因而將其稱為車輛通行序列（order of car，OC），其無法體現(xiàn)同一時(shí)刻交叉口內(nèi)通過多輛CAV。為提高車輛通行效率，盡可能讓無碰撞關(guān)系的車輛同時(shí)通過交叉口沖突區(qū)。在此將可同時(shí)通過交叉口的無碰撞車輛組合稱為車輛通行組。車輛通行組可有效減少沖突區(qū)中無車輛通行的空窗期，提高交叉口沖突區(qū)的利用率。需要注意的是，若上一通行組中包含多臺車輛，則下一通行組中的車輛需要全面考慮與上一通行組中不同車輛的碰撞關(guān)系，進(jìn)而設(shè)置無碰撞的最快到達(dá)時(shí)間。將車輛通行序列轉(zhuǎn)換為車輛通行組序列（order of group，OG）的方法如算法1所示。

算法1 成組通行算法

其中：tg為成組閾值，若兩車的到達(dá)時(shí)間相差超過tg，則兩車將單獨(dú)成組，其取值為車輛在交叉口沖突區(qū)中的平均通行時(shí)間。

通過算法1將搜索出的通行序列轉(zhuǎn)換為車輛通行組序列，結(jié)果如圖6所示，通行組由5組縮減少到了3組，有效提高了交叉口沖突區(qū)的利用率。

2.3 通行組序列價(jià)值評估

對車輛通行組序列進(jìn)行價(jià)值評估是搜索過程中的重要環(huán)節(jié)，其評價(jià)的準(zhǔn)確性直接影響到算法求解出的通行順序的優(yōu)劣。首先計(jì)算第i輛車最快到達(dá)交叉口的時(shí)間，假設(shè)Vi前方不存在其他車輛且不存在沖突車輛，Vi以自由流速度從其當(dāng)前所在位置行駛到?jīng)_突區(qū)所需要的時(shí)間為最小到達(dá)時(shí)間，如式（2）所示。

其中：disi為第i輛車距離沖突區(qū)的距離；vf為自由流速度。

由于通行組中可能存在多輛車，所以估算通行組的到達(dá)時(shí)間時(shí)需要考慮到前一通行組中的所有車輛，存在沖突的車輛先后經(jīng)過同一沖突點(diǎn)時(shí)需要保持安全跟車距離dsafe，采用恒定車頭時(shí)距（constant time headway，CTH）進(jìn)行計(jì)算。

dsafe=th×v+dminsafe（3）

其中：th為固定車頭時(shí)距；dminsafe為最小安全距離。

本文目標(biāo)在于提高交叉口整體的通行效率，因而對通行組序列的評價(jià)指標(biāo)與其總通行時(shí)間相關(guān)，關(guān)于車輛通行組序列總通行時(shí)間test的計(jì)算如算法2所示。

算法2 通行順序評估算法

算法2中，tassign，OG［i］［j］為OG中第i組中的第j輛車的安排到達(dá)時(shí)間；tmin，OG［i］［j］為第i組中的第j輛車的最快到達(dá)時(shí)間。

評價(jià)通行組序列優(yōu)劣的原則為總通行時(shí)間短的葉節(jié)點(diǎn)評分高，反之評分低，通行時(shí)間與評價(jià)分?jǐn)?shù)呈負(fù)相關(guān)。因此采用恒大于通行時(shí)間的值減去通行時(shí)間作為該通行順序的評分，評價(jià)公式如下：

goal=（tmin+tsafe×k）-test（4）

其中：goal為當(dāng)前通行順序的得分；tmin為通行組中最快到達(dá)沖突區(qū)的車輛的到達(dá)時(shí)間；tsafe為不同車輛通過同一沖突點(diǎn)的安全間隔時(shí)間;k為通行組序列中包含的車輛數(shù)。其中，tmin+tsafe×k是按照逐車通行的方式估算出的最長通行時(shí)間，其恒大于等于估算出的通行時(shí)間。

2.4 自適應(yīng)參數(shù)

MCTS的搜索性能受到多個(gè)參數(shù)的影響，其中探索系數(shù)直接影響到搜索的速度和搜索結(jié)果的質(zhì)量。當(dāng)探索系數(shù)越大時(shí)，算法越傾向于探索新的節(jié)點(diǎn)，使得搜索結(jié)果質(zhì)量更高，但也增加了搜索時(shí)間。而探索系數(shù)減小時(shí)，算法傾向于選擇已知的利益最大的節(jié)點(diǎn)，減少對新節(jié)點(diǎn)的探索，提高了搜索速度，但求得的通行順序可能與最優(yōu)解差距較大。過去一般將探索系數(shù)設(shè)置為一定值，由于參與順序決策的車輛數(shù)在不斷變化，若以恒定的探索系數(shù)，在車輛數(shù)較少時(shí)將出現(xiàn)過早結(jié)束搜索的情況，導(dǎo)致結(jié)果不夠理想，而車輛數(shù)較多時(shí)可能導(dǎo)致求解失敗。為了在搜索速度和結(jié)果質(zhì)量間取得較好的平衡，應(yīng)根據(jù)參與順序決策的車輛數(shù)目來初始化探索系數(shù)。車輛數(shù)增多時(shí)，探索系數(shù)應(yīng)適當(dāng)減小以提高搜索速度，反之探索系數(shù)可適當(dāng)增大以提高求解質(zhì)量。不同車輛數(shù)時(shí)的初始探索系數(shù)如式（5）所示。

其中：Cinit為初始探索系數(shù)。當(dāng)車輛數(shù)小于10時(shí)，探索系數(shù)增大到2.6后繼續(xù)增加并未提高通行效率，而搜索時(shí)間卻隨之增大。當(dāng)車輛數(shù)大于10輛后，采用線性遞減的方法計(jì)算探索系數(shù)，車輛數(shù)達(dá)到50時(shí)，探索系數(shù)為0.04。

樹搜索前期時(shí)，由于探索的車輛較少，由此節(jié)點(diǎn)模擬出來的通行順序存在較大隨機(jī)性，不能真實(shí)地反映出當(dāng)前節(jié)點(diǎn)的價(jià)值，所以要保持一定的探索能力，加強(qiáng)對較優(yōu)解的發(fā)掘。隨著搜索的進(jìn)行，探索到的車輛數(shù)增多，節(jié)點(diǎn)模擬出的通行順序已能大致反映當(dāng)前節(jié)點(diǎn)的價(jià)值，因此可以減小探索系數(shù)以提高搜索速度。參考機(jī)器學(xué)習(xí)中的學(xué)習(xí)率衰減方法定義了衰減系數(shù)，用于實(shí)現(xiàn)算法的探索能力隨探索深入而下降，如式（6）所示。

其中：α為衰減系數(shù)；decayconst為衰減常數(shù)；decaysteps為衰減步長；n為當(dāng)前迭代次數(shù)。衰減后的探索系數(shù)為Cdecay=α×Cinit（7）

其中：Cdecay為隨迭代次數(shù)衰減的探索系數(shù)。

剪枝規(guī)則同樣是影響搜索速度的一重要因素，增大剪枝力度可以有效減小解空間。當(dāng)參與順序決策的車輛較多時(shí)，優(yōu)先探索較快到達(dá)的車輛，有利于提高搜索速度，對于距離較遠(yuǎn)的車輛進(jìn)行剪枝，剪枝參數(shù)如式（8）所示。

其中：可探索節(jié)點(diǎn)按車輛的到達(dá)時(shí)間進(jìn)行排序；carsearch為需要探索的子節(jié)點(diǎn)數(shù)，此范圍外的車輛即被剔除。

另一影響搜索的參數(shù)是總迭代次數(shù)，迭代次數(shù)過少可能導(dǎo)致探索不完全甚至無法獲得完整通行順序。迭代次數(shù)過多則可能導(dǎo)致算法計(jì)算時(shí)間過長，對已知最優(yōu)的通行順序進(jìn)行重復(fù)探索。對不同車輛數(shù)進(jìn)行測試，標(biāo)定結(jié)果為

其中：N為總迭代次數(shù)，當(dāng)車輛數(shù)達(dá)到50輛時(shí)，搜索時(shí)間為0.8 s。結(jié)合上述定義，最終的交叉口車輛通行順序決策如算法3所示。

算法3 基于自適應(yīng)蒙特卡羅樹搜索的通行順序決策算法

3 車輛軌跡規(guī)劃

交叉口管理層求解最優(yōu)通行順序后可由算法2求得每輛CAV的分配到達(dá)時(shí)間。各CAV在獲取到分配的到達(dá)時(shí)間后，結(jié)合自車所在位置以及當(dāng)前行駛狀態(tài)信息進(jìn)行軌跡規(guī)劃。由于控制區(qū)內(nèi)車輛不需要進(jìn)行換道，只需進(jìn)行車輛縱向運(yùn)動控制，在此采用二階運(yùn)動學(xué)模型：

其中：pi（t）為車輛i在t時(shí)刻的位置；vi（t）為車輛i在t時(shí)刻的速度；ui（t）為車輛i在t時(shí)刻的加速度。已知當(dāng)前狀態(tài)和末端狀態(tài)的情況下，可以使用優(yōu)化方法獲得車輛的軌跡，為使車輛能耗盡可能降低，目標(biāo)函數(shù)設(shè)置為加速度的二范數(shù)，如式（11）所示。

為確保車輛的控制輸入和速度能在允許的范圍內(nèi)，優(yōu)化過程中對其進(jìn)行了如下限制：

其中：umin為最小加速度；umax為最大加速度；vmin為最小速度；vmax為最大速度。

車輛的始末狀態(tài)可直接獲得，初始時(shí)間為t0i，末端時(shí)間為tfi=t0i+tassigni，tassigni為車輛i的安排行駛時(shí)間，初始位置為p0i，末端位置為pfi，初始速度為v0i，末端速度定義為沖突區(qū)的車輛行駛速度vfi。最終建立軌跡規(guī)劃最優(yōu)控制命題如下：

采用商用求解器Cplex求解式（13），獲得車輛的加速度控制量。

4 仿真與實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，選擇經(jīng)典的先到先得算法（文獻(xiàn)［10］）、基于圖優(yōu)化的決策算法（文獻(xiàn)［16］）、基于MCTS的樹搜索算法（文獻(xiàn)［17］）進(jìn)行對比，對比的指標(biāo)為交叉口車輛通行時(shí)間，驗(yàn)證方法包含數(shù)值仿真和微縮平臺實(shí)驗(yàn)。

4.1 數(shù)值仿真

在不同車流量情況下每個(gè)決策時(shí)刻參與決策的車輛數(shù)將有所不同，選擇10、20、30、40、50輛五種不同車輛數(shù)的場景對算法的計(jì)算效率和車輛通行時(shí)間進(jìn)行數(shù)值仿真，每種車輛數(shù)進(jìn)行五組仿真取平均通行時(shí)間作為結(jié)果。更高車流量的情況可通過滾動時(shí)域法對交叉口內(nèi)的車輛進(jìn)行滾動求解通行順序。仿真所使用電腦的CPU為i5-12400，內(nèi)存為16 GB，操作系統(tǒng)為Windows 10，編程語言為Python。

分別對五種車輛數(shù)時(shí)的場景進(jìn)行仿真分析，結(jié)果如圖7和表2所示。從圖7可以看出，在車輛數(shù)較少時(shí)各算法的性能差異較小，這是由于車輛數(shù)較少，解空間較小，可以成組通行的車輛較少，進(jìn)而算法間較難拉開差距。隨著車輛數(shù)的增加，解空間增大，可成組通行的車輛增多，因而各算法的性能差距逐漸拉大。

在相同數(shù)量車輛的場景下，總體的通行時(shí)間是評價(jià)決策算法的重要指標(biāo)，通行時(shí)間越短意味著算法對于交叉口沖突區(qū)的利用率越高。如表2所示，在不同車輛數(shù)場景下，本文算法相比文獻(xiàn)［10］，通行時(shí)間分別縮短了23.1%、23.59%、26.72%、30.27%、33.42%；相比文獻(xiàn)［16］，通行時(shí)間分別縮短了4.64%、6.54%、8.73%、12.28%、15.08%；相比文獻(xiàn)［17］，通行時(shí)間分別縮短了3.9%、4.74%、5.78%、7.4%、8.08%。綜上可得，本文算法相比于其他算法在不同車輛數(shù)情況下的通行效率均為最高，且隨著車輛數(shù)的增加，通行效率的提升逐漸增大。

對優(yōu)化的幅度進(jìn)行分析，優(yōu)化幅度隨車輛數(shù)增加的增量在文獻(xiàn)［10］上為0.49%、3.13%、3.55%、3.15%；在文獻(xiàn)［16］上為1.9%、2.19%、3.55%、2.8%，在文獻(xiàn)［17］上為0.84%、1.04%、1.62%、1.04%。車輛數(shù)較少時(shí)的優(yōu)化漲幅呈增大趨勢，當(dāng)車輛數(shù)由40增加到50時(shí)，優(yōu)化的增幅開始降低。分析可得，交叉口存在一個(gè)最大車輛通行能力上限，車輛數(shù)小于40時(shí)未達(dá)到該上限，隨著車輛數(shù)增多本文算法相對于其他算法的縮短通行時(shí)間越多，當(dāng)達(dá)到交叉口通行能力的瓶頸后繼續(xù)增大車輛數(shù)，此時(shí)后方的車輛進(jìn)入排隊(duì)通行狀態(tài)，本文算法相對于其他算法的優(yōu)化程度開始降低。

由于文獻(xiàn)［10，16］的算法均為一次遍歷便可獲得結(jié)果，決策結(jié)果受車輛初始位置影響，在計(jì)算時(shí)間上不具備比較性。所以這里與同為啟發(fā)式搜索算法的文獻(xiàn)［17］進(jìn)行比較，仿真計(jì)算時(shí)間如表3所示。可以看出文獻(xiàn)［17］的計(jì)算時(shí)間隨著車輛數(shù)增長呈現(xiàn)較大的增長趨勢，車輛數(shù)為50時(shí)的計(jì)算時(shí)間超過6 s，本文算法僅為0.8 s，縮短了86.7%。

4.2 微縮平臺實(shí)驗(yàn)

在微縮平臺上進(jìn)行進(jìn)一步算法有效性驗(yàn)證。微縮平臺基于機(jī)器人操作系統(tǒng)（robot operating system，ROS）開發(fā)，微縮車輛為搭載樹莓派4B的阿克曼底盤小車，通過安裝在頂部的相機(jī)對車輛進(jìn)行定位，微縮車輛通過Wi-Fi與服務(wù)器進(jìn)行通信，如圖8所示。服務(wù)器配置為CPUi5-12600，內(nèi)存16 GB，系統(tǒng)Ubuntu 20.6，編程語言為Python。微縮平臺整體尺寸按照真實(shí)交叉口尺寸13∶1縮小，由于平臺硬件性能限制，小車最高行駛速度為0.22 m/s，對應(yīng)真實(shí)交通環(huán)境下的低速交通情況。

實(shí)驗(yàn)設(shè)計(jì)了五個(gè)不同的場景，盡可能包含不同的交叉口車輛分布情況，如圖9所示。

由于實(shí)驗(yàn)車輛數(shù)較少，各算法的計(jì)算時(shí)間均小于10 ms，在此情況下將著重對比車輛通行時(shí)間，結(jié)果如圖10和表4所示。

由圖10可以看出，本文算法在不同的場景下均能獲得較低的通行時(shí)間。這是因?yàn)?，文獻(xiàn)［10，16］受車輛位置到?jīng)_突區(qū)距離的影響，在特定情況下也能獲得較好的通行效率，但多數(shù)情況下的通行順序與最優(yōu)通行順序差距較大。文獻(xiàn)［17］雖然也是啟發(fā)式搜索算法，但由于采用較為粗粒度的交叉口模型，限制了交叉口利用率的提高。由表4可以看出，本文算法相對于文獻(xiàn)［10］的優(yōu)化幅度從0.3%到41.18%不等，而在仿真中的優(yōu)化幅度為23.1%到33.42%。分析可知，車輛數(shù)較少時(shí)文獻(xiàn)［10］的性能受車輛分布影響較大，而本文算法在不同的車輛分布情況下均能獲得接近最優(yōu)解的通行順序，體現(xiàn)在優(yōu)化幅度上就是0.3%到41.18%的大跨度。隨著車輛數(shù)的增多，結(jié)合不同車輛分布情況，一定程度上降低了不同車輛分布的極端情況，因此本文算法相對于文獻(xiàn)［10］的優(yōu)化幅度區(qū)間縮小為23.1%到33.42%。同樣，文獻(xiàn)［16，17］存在和文獻(xiàn)［10］類似的缺點(diǎn)。

5 結(jié)束語

本文針對無信號交叉口車輛通行調(diào)度問題，建立基于沖突點(diǎn)的交叉口模型，提出一種自適應(yīng)蒙特卡羅樹搜索的順序決策算法。首先將車輛通ac814468655d4be4abf56afdbd8919a1a863577205a998b4a39e20d4b029d207行順序決策問題轉(zhuǎn)換為樹搜索問題，引入蒙特卡羅搜索思想并對超參數(shù)進(jìn)行魯棒性優(yōu)化，獲得通行順序后計(jì)算各車到達(dá)沖突點(diǎn)的時(shí)間，建立最優(yōu)控制命題求解車輛軌跡。經(jīng)實(shí)驗(yàn)驗(yàn)證，本文算法相較于其他算法在不同車流量時(shí)均能有效提高交叉口通行效率，最高分別達(dá)到33.42%、15.08%、8.08%，并且在高車流量情況下同時(shí)求解50輛車時(shí)的平均計(jì)算時(shí)間低于0.8 s，為無信號交叉口車輛通行調(diào)度提供了一個(gè)有效解決方案。

參考文獻(xiàn)：

［1］Guo Qiangqiang， Li Li， Ban Xuegang. Urban traffic signal control with connected and automated vehicles： a survey［J］. Transportation Research Part C： Emerging Technologies， 2019，101： 313-334.

［2］Bühm A. Delay-sensitive wireless communication for cooperative dri-ving applications［M］. Halmstad： Halmstad University Press， 2013.

［3］楊瀾， 趙祥模， 吳國垣， 等. 智能網(wǎng)聯(lián)汽車協(xié)同生態(tài)駕駛策略綜述［J］. 交通運(yùn)輸工程學(xué)報(bào)， 2020， 20（5）： 58-72. （Yang Lan， Zhao Xiangmu， Wu Guoheng， et al. Review of collaborative ecological dri-ving strategies for intelligent networked vehicles［J］. Journal of Traffic and Transportation Engineering， 2020， 20（5）： 58-72.）

［4］Li Li， Wen Ding， Yao Danya. A survey of traffic control with vehicular communications［J］. IEEE Trans on Intelligent Transportation Systems， 2014， 15（1）： 425-432.

［5］Guler S I， Menendez M， Meier L. Using connected vehicle technology to improve the efficiency of intersections［J］. Transportation Research Part C： Emerging Technologies， 2014， 46： 121-131.

［6］Li Li， Wang Feiyue. Cooperative driving at blind crossings using intervehicle communication［J］. IEEE Trans on Vehicular Technology， 2006， 55（6）： 1712-1724.

［7］Rios-Torres J， Malikopoulos A A. A survey on the coordination of connected and automated vehicles at intersections and merging at highway on-ramps［J］. IEEE Trans on Intelligent Transportation Systems， 2017， 18（5）： 1066-1077.

［8］Li Shen， Shu Keqi， Chen Chaoyi， et al. Planning and decision-making for connected autonomous vehicles at road intersections： a review［J］. Chinese Journal of Mechanical Engineering， 2021， 34（1）： article No. 133.

［9］張毅， 裴華鑫， 姚丹亞. 車路協(xié)同環(huán)境下車輛群體協(xié)同決策研究綜述［J］. 交通運(yùn)輸工程學(xué)報(bào)， 2022， 22（3）： 1-18. （Zhang Yi， Pei Huaxin， Yao Danya. Review on collaborative decision-making of vehicle groups in vehicle-road collaborative environment［J］. Journal of Traffic and Transportation Engineering， 2022， 22（3）： 1-18.）

［10］Dresner K， Stone P. Multiagent traffic management： a reservation-based intersection control mechanism［C］//Proc of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems.Piscataway， NJ： IEEE Press， 2004： 530-537.

［11］張毅， 姚丹亞， 李力， 等. 智能車路協(xié)同系統(tǒng)關(guān)鍵技術(shù)與應(yīng)用［J］. 交通運(yùn)輸系統(tǒng)工程與信息， 2021， 21（5）： 40-51. （Zhang Yi， Yao Danya， Li Li， et al. Key technologies and applications of intelligent vehicle-road collaborative system［J］. Transportation System Engineering and Information， 2021， 21（5）： 40-51.）

［12］Meng Yue， Li Li， Wang Feiyue， et al. Analysis of cooperative dri-ving strategies for nonsignalized intersections［J］. IEEE Trans on Vehicular Technology， 2017，67（4）： 2900-2911.

［13］Carlino D， Boyles S D， Stone P. Auction-based autonomous intersection management［C］//Proc of the 16th International IEEE Conference on Intelligent Transportation Systems. Piscataway， NJ： IEEE Press， 2013： 529-534.

［14］Müller E R， Carlson R C， Junior W K. Intersection control for automated vehicles with MILP［J］. IFAC-PapersOnLine， 2016， 49（3）： 37-42.

［15］Ahn H， Del Vecchio D. Safety verification and control for collision avoidance at road intersections［J］. IEEE Trans on Automatic Control， 2017， 63（3）： 630-642.

［16］Chen Chaoyi， Xu Qing， Cai Mengchi， et al. A graph-based conflict-free cooperation method for intelligent electric vehicles at unsignalized intersections［C］//Proc of IEEE International Intelligent Transportation Systems Conference. Piscataway， NJ： IEEE Press， 2021： 52-57.

［17］Xu Huile， Zhang Yi， Li Li， et al. Cooperative driving at unsignalized intersections using tree search［J］. IEEE Trans on Intelligent Transportation Systems， 2019， 21（11）： 4563-4571.

［18］Pei Huaxin， Zhang Yuxiao， Zhang Yi， et al. Optimal cooperative driving at signal-free intersections with polynomial-time complexity［J］. IEEE Trans on Intelligent Transportation Systems， 2022， 23（8）： 12908-12920.

［19］李磊， 王文格， 彭景陽. 無信號交叉口網(wǎng)聯(lián)車調(diào)度與分布式控制策略［J］. 計(jì)算機(jī)應(yīng)用研究， 2022， 39（11）： 3346-3350. （Li Lei， Wang Wenge， Peng Jingyang. Combined vehicle scheduling and distributed control strategy at signalless intersection［J］. Application Research of Computers， 2022， 39（11）： 3346-3350.）

［20］Magnuson M. Monte Carlo tree search and its applications［J］. Scholarly Horizons： University of Minnesota， Morris Undergraduate Journal， 2015， 2（2）： article No.4.