基于A＊算法的智能車多紅綠燈信號交叉口通行的經(jīng)濟(jì)車速規(guī)劃研究

金輝，牛若飛

（北京理工大學(xué) 機(jī)械與車輛學(xué)院，北京 100081）

紅綠燈信號交叉口是城市交通中常見的駕駛場景.紅綠信號燈在指揮車輛于交叉口處的行駛中扮演著重要的角色，在宏觀層面上，交通流的速度、流量、密度都受其影響[1].而對于單個(gè)車輛，在紅綠燈信號交叉口處的等待及啟停都無疑增加了行駛成本，因此車輛在紅綠燈信號交叉口的通行措施對燃油消耗有顯著影響.

現(xiàn)有研究中，基于優(yōu)化的控制算法將采用各種優(yōu)化算法，利用前瞻距離內(nèi)的信息進(jìn)行規(guī)劃，在極大地提高了能量效率的同時(shí)可以根據(jù)駕駛員風(fēng)格進(jìn)行規(guī)化[2?3]，常見的算法有A*、動(dòng)態(tài)規(guī)劃等[4?5].紅綠燈信號交叉口處的經(jīng)濟(jì)駕駛算法中，考慮優(yōu)化時(shí)包含的交通燈數(shù)量，可以將問題分為單信號燈問題以及多信號燈問題.

在單信號燈優(yōu)化方面，HU 等[6]通過規(guī)劃電動(dòng)智能網(wǎng)聯(lián)車輛通過信號燈交叉口處的速度來提高經(jīng)濟(jì)性，使得電動(dòng)智能網(wǎng)聯(lián)車輛的經(jīng)濟(jì)性得到大幅的提高.YAO 等[7]利用分割矩形算法優(yōu)化智能網(wǎng)聯(lián)車輛的軌跡以保證不停車通過紅綠燈信號交叉口，從而提高車輛的經(jīng)濟(jì)性.在多信號燈優(yōu)化方面，冷江昊等[8]將多紅綠燈通行建模為有向無環(huán)圖，并利用動(dòng)態(tài)規(guī)劃求初始解再利用二次優(yōu)化求得最終解.但其只考慮到綠燈的影響并只選擇有限路線，同時(shí)只使用勻速通行的燃油消耗為代價(jià)函數(shù)來進(jìn)行規(guī)劃，因此還需要進(jìn)一步考慮到紅燈的影響以及使用更精確的代價(jià)函數(shù).LIU 等[9]利用深度學(xué)習(xí)，通過設(shè)置合理的獎(jiǎng)勵(lì)函數(shù)，訓(xùn)練算法將車輛接收到的關(guān)鍵環(huán)境信息作為輸入，最終輸出最大化累積獎(jiǎng)勵(lì)的加速度.與單信號燈相比，多信號燈的優(yōu)化問題更為復(fù)雜，但優(yōu)化效果更好.相對于全程而言，單信號燈優(yōu)化更側(cè)重于局部的優(yōu)化，無法最大限度的提高車輛全局行駛的燃油經(jīng)濟(jì)性，因此優(yōu)化效果要低于多信號燈通行優(yōu)化.

為了能夠快速得到多燈通行的最優(yōu)經(jīng)濟(jì)駕駛策略，將采用A*算法進(jìn)行優(yōu)化.需要建立多紅綠燈信號交叉口的時(shí)空拓?fù)鋱D，以及考慮到現(xiàn)實(shí)工況，將利用動(dòng)態(tài)規(guī)劃得到車輛行駛的經(jīng)濟(jì)速度序列以及燃油消耗做為邊集的權(quán)重，以獲得最優(yōu)的經(jīng)濟(jì)駕駛策略.論文第1 部分將介紹車輛燃油經(jīng)濟(jì)性優(yōu)化問題，并提出最優(yōu)問題的模型；第2 部分將首先離散車輛的動(dòng)力學(xué)模型與燃油消耗模型，并以此為基礎(chǔ)計(jì)算車輛的燃油消耗，然后建立多紅綠燈信號交叉口的時(shí)空拓?fù)鋱D，最后根據(jù)前述條件給出A*算法的具體步驟；第3 部分將分析A*算法在經(jīng)濟(jì)駕駛中的性能表現(xiàn)；在第4 部分給出結(jié)論.

1 車輛燃油經(jīng)濟(jì)性優(yōu)化問題

1.1 問題總結(jié)

A*算法是一個(gè)成熟的算法，常見于有障礙物時(shí)的路徑搜索等場景中.而動(dòng)態(tài)規(guī)劃則常用于優(yōu)化算法，需要遍歷所有的狀態(tài)來獲得最優(yōu)的結(jié)果，因此時(shí)間復(fù)雜度為O(N2)，同時(shí)多紅綠燈信號交叉口中狀態(tài)數(shù)多且存在紅燈無法通行的狀態(tài)使得算法的計(jì)算成本過高.在本研究中，由于速度規(guī)劃屬于最優(yōu)化處理，并不能直接通過搜索得到，因此改進(jìn)并利用A*算法用于實(shí)時(shí)計(jì)算，并利用動(dòng)態(tài)規(guī)劃算法建立對應(yīng)的時(shí)空拓?fù)鋱D.建圖為離線操作，不會影響A*算法的計(jì)算時(shí)間，使得算法具有實(shí)時(shí)在線應(yīng)用的能力.

為了使A*算法能夠搜索到最小的燃油消耗以及得到其對應(yīng)的速度規(guī)劃，將建立對應(yīng)的拓?fù)鋱D.本研究將選擇動(dòng)態(tài)規(guī)劃建立速度序列與燃油消耗對應(yīng)的時(shí)空拓?fù)鋱D，因此首先利用動(dòng)態(tài)規(guī)劃算法求解車輛在兩個(gè)時(shí)空點(diǎn)之間的經(jīng)濟(jì)速度規(guī)劃.通過增加時(shí)間的成本函數(shù)，解決了如何在約定時(shí)間內(nèi)到達(dá)目標(biāo)，基于此可以獲得經(jīng)濟(jì)速度規(guī)劃，以及對應(yīng)的燃油消耗.

1.2 最優(yōu)控制問題

本研究以傳統(tǒng)內(nèi)燃機(jī)汽車為研究對象，并利用高精度地圖提供信號燈的相位信息，通過優(yōu)化算法規(guī)劃車輛的速度軌跡，使車輛能夠滿足高效、節(jié)能、安全舒適的行駛要求.最終的目標(biāo)函數(shù)為車輛行駛的燃油消耗；而車輛的最大通過時(shí)間由車輛行駛的最小速度約束決定；車輛的安全舒適性目標(biāo)則由車輛的加速度約束決定.定義車輛的行駛時(shí)間為T(s)；狀態(tài)量為車輛的位移與速度x=(s,v)T，控制量為車輛的牽引力矩與制動(dòng)力矩u=Tb+Td，牽引力矩Td(N·m)為正值，制動(dòng)力矩Tb(N·m)為負(fù)值，二者單一存在，則最優(yōu)控制問題為

式中：Qf為車輛發(fā)動(dòng)機(jī)的瞬時(shí)燃油消耗，mL；vmin,vmax為車輛的速度限制，km/h，分別滿足車輛最長通過時(shí)間與道路車速限制；Tbc和Tdc分別為車輛的制動(dòng)力矩和牽引力矩限制，N·M，這二者約束將由路面附著系數(shù)、車輛的舒適性、發(fā)動(dòng)機(jī)最大輸出轉(zhuǎn)矩以及車輛最大制動(dòng)力決定；=f(x(t),u(t))為車輛的狀態(tài)方程.

2 智能車輛通過多燈經(jīng)濟(jì)行駛模型

2.1 車輛動(dòng)力學(xué)模型

對于建模，采用以下假設(shè)：良好的交通條件，沒有其他車輛的干擾；路面附著狀況良好，輪胎不打滑.定義車輛的行駛時(shí)間為T(s)；狀態(tài)量為車輛的距離與速度x=(s,v)T，控制量為車輛的牽引力矩與制動(dòng)力矩u=Tb+Td，牽引力矩Td為 正值，制動(dòng)力矩Tb為負(fù)值，二者單一存在，因此車輛的動(dòng)力學(xué)方程可以表述為[4]

式中：v為車輛的速度，m/s；m為車輛質(zhì)量，kg；g為重力加速度；f(?)為 滾動(dòng)阻力系數(shù)；CD(?)為空氣阻力系數(shù)；A為汽車縱向迎風(fēng)面積；ρ為空氣密度，kg/m3；Te為發(fā)動(dòng)機(jī)的輸出轉(zhuǎn)矩，N·m；Fb為制動(dòng)器作用在車輪上的等效力，N.

為了能夠獲得車輛在各個(gè)位置的狀態(tài)信息，需要將狀態(tài)方程從時(shí)間域轉(zhuǎn)變?yōu)榭臻g域，同時(shí)將速度單位統(tǒng)一為km/h，則有

再利用前向歐拉即可將系統(tǒng)的狀態(tài)方程離散化

式中：vk和vk+1分別為第k階段和第k+1 階段的速度，km/h；sk為 第k階段時(shí)車輛已經(jīng)行駛的位移，m；?s為相鄰兩階段之間的距離，m.

2.2 車輛燃油消耗及車輛速度序列

如上所述將利用動(dòng)態(tài)規(guī)劃對兩個(gè)時(shí)空點(diǎn)之間的車輛速度進(jìn)行規(guī)劃，提高經(jīng)濟(jì)燃油性.因此為了能夠獲得較精確燃油消耗，需要采用瞬時(shí)燃油消耗模型，本研究采用了一種稱為BIT-TFCM 模型的瞬時(shí)燃油消耗模型[10].瞬時(shí)燃油消耗模型可以根據(jù)車輛的瞬時(shí)速度以及加速度得到車輛的燃油消耗，具體建模計(jì)算方法見文獻(xiàn)[10].將燃油消耗模型在距離上離散化可得:

式中：Qf為車輛發(fā)動(dòng)機(jī)瞬時(shí)燃油消耗，mL；vk為第k階段時(shí)的速度，km/h；tk為第k階段的時(shí)間，s；sk為第k階段時(shí)車輛已經(jīng)行駛的位移，m；?s為相鄰兩階段之間的距離，m.

則經(jīng)過離散后，車輛在每階段時(shí)的成本函數(shù)為：

為了得到車輛在各個(gè)階段燃油消耗以及速度序列，將采用動(dòng)態(tài)規(guī)劃對其進(jìn)行經(jīng)濟(jì)車速規(guī)劃.最低速度約束為vmin= 7.8 km/h，即離合器已完全接合的車輛速度；最高速度為道路限速vlimit.因此車輛多階段速度優(yōu)化模型為

式中：Q0為車輛未達(dá)到最低速度的燃油消耗，mL.根據(jù)優(yōu)化模型，利用動(dòng)態(tài)規(guī)劃可以計(jì)算出車輛的燃油消耗.

由式(7)可得，計(jì)算起始點(diǎn)與終止點(diǎn)兩個(gè)狀態(tài)點(diǎn)之間的燃油消耗時(shí)，需要對兩個(gè)狀態(tài)點(diǎn)的速度、位移及通行時(shí)間進(jìn)行約束，同時(shí)x(k+1)=G(x(k),u(k),?s)，即k+1 處的狀態(tài)需要由k處的狀態(tài)遞推得到，即間接值無法獲得兩端的約束.同時(shí)速度v與位移s均需要滿足兩端約束，因此選擇在位移上離散，并以速度為每個(gè)階段的狀態(tài)，時(shí)間為間接獲得值.當(dāng)需要對時(shí)間做出約束時(shí)，可以增加其對應(yīng)的目標(biāo)函數(shù)，同時(shí)對其進(jìn)行歸一化處理，則可以得到新的優(yōu)化模型.

式中 λ(?)為權(quán)重，通過更新λ即可獲得對應(yīng)時(shí)間內(nèi)的速度序列.

模擬車輛起步過程，以車輛通過150 m 長的直道為例，車輛參數(shù)見表1.根據(jù)文獻(xiàn)[11]，設(shè)置車輛終端狀態(tài)的速度目標(biāo)為經(jīng)濟(jì)定速巡航速度49.6 km/h[11]，設(shè)置λ分別為1 和0，獲得燃油經(jīng)濟(jì)性速度序列及車輛擋位信息，如圖1 所示.

表1 Carsim 某A 級轎車配置Tab.1 configuration of a carsim A

圖1 不同λ 時(shí)車輛經(jīng)濟(jì)起步速度圖Fig.1 Vehicle economic start speed diagram with different λ

當(dāng)λ為0 時(shí)，車輛只在起始時(shí)加速度較高以提前升擋，之后長期處于四擋加速，使得車輛通過降低部分加速效率使發(fā)動(dòng)機(jī)工作在高效區(qū)間保證了車倆的最優(yōu)燃油消耗性.當(dāng)λ為1 時(shí)，車輛會較早地提高至較高的速度，以降低部分燃油經(jīng)濟(jì)性為代價(jià)來降低車輛的通行時(shí)間.

2.3 信號交叉口時(shí)空拓?fù)鋱D

為了考量紅綠燈配時(shí)信息對車輛的速度影響，將建立其時(shí)空拓?fù)鋱D，使得兩個(gè)節(jié)點(diǎn)之間的燃油消耗與車輛的最優(yōu)速度一一對應(yīng).定義有n個(gè)紅綠燈信號交叉路口，下標(biāo)i為位于第i個(gè)信號交叉口處；將行駛目標(biāo)時(shí)間按照時(shí)間間隔dt離散為m階段，上標(biāo)k為處于第k階段.加上起點(diǎn)將獲得nm+1 個(gè)時(shí)空節(jié)點(diǎn)，同時(shí)當(dāng)前節(jié)點(diǎn)可以表示為

每個(gè)節(jié)點(diǎn)之間并不是相互連接的，節(jié)點(diǎn)之間的聯(lián)通狀態(tài)將代表車輛的狀態(tài)選擇.規(guī)定當(dāng)紅燈時(shí)，車輛只能從當(dāng)前紅綠燈節(jié)點(diǎn)前往當(dāng)前紅綠燈的其他節(jié)點(diǎn)；綠燈時(shí)，車輛同時(shí)可以前往下一個(gè)紅綠燈處的節(jié)點(diǎn).節(jié)點(diǎn)代表了在時(shí)間k時(shí)第i個(gè)紅綠燈的狀態(tài)信息.當(dāng)紅燈時(shí)車輛只能在當(dāng)前信號交叉口處繼續(xù)等待，則紅燈時(shí)的拓?fù)鋱D邊集為

當(dāng)綠燈時(shí)車輛可以選擇繼續(xù)前往下一信號交叉口處，則綠燈時(shí)的拓?fù)鋱D邊集為

當(dāng)車輛處于紅燈等待狀態(tài)時(shí)，邊集的權(quán)重為怠機(jī)時(shí)的燃油消耗Q0FmL；當(dāng)車輛處于綠燈通行狀態(tài)時(shí)時(shí)，邊集的權(quán)重為經(jīng)過動(dòng)態(tài)規(guī)劃計(jì)算后的燃油消耗Q1FmL.則建立的邊集如式(12)所示.

因此根據(jù)動(dòng)態(tài)規(guī)劃計(jì)算時(shí)空拓?fù)鋱D的流程如下：

⑦檢查是否滿足時(shí)間約束，否則更新λ返回2

⑧更新所有的EG

2.4 A＊算法模型

A*算法可以快速解決帶權(quán)重的有向圖上的最優(yōu)路徑搜索問題.通過設(shè)置兩個(gè)集合，OPEN 和CLOSED，A*將遍歷部分節(jié)點(diǎn)并得到最優(yōu)解.OPEN 集包含那些作為檢查候選的節(jié)點(diǎn).CLOSED 集包含那些已經(jīng)檢查過的節(jié)點(diǎn).每個(gè)節(jié)點(diǎn)還保留其父節(jié)點(diǎn)的信息，以便確定它是如何被找到的.同時(shí)在計(jì)算過程中需要記錄從節(jié)點(diǎn)Node至Node′的路徑成本g(n′)=g(n)+m(n,n′)，接著計(jì) 算該點(diǎn)的評價(jià)值F(n′)=g(n′)+h(n′)并 保存，同時(shí)根據(jù)拓?fù)鋱D中邊集的權(quán)重，定義啟發(fā)式為當(dāng)前節(jié)點(diǎn)到達(dá)終點(diǎn)的最優(yōu)經(jīng)濟(jì)燃油消耗，即：

通過前面建立的時(shí)空拓?fù)鋱D將燃油消耗與最優(yōu)速度進(jìn)行對應(yīng)，使得兩時(shí)空節(jié)點(diǎn)的代價(jià)為車輛的燃油消耗，因此A*算法通過搜索時(shí)空拓?fù)鋱D上的節(jié)點(diǎn)即可獲得對應(yīng)的最優(yōu)速度規(guī)劃.A*算法搜索車輛最優(yōu)速度的偽代碼如下：

3 仿真與結(jié)果分析

本章通過構(gòu)建道路數(shù)據(jù)，使用Matlab2019a 與Carsim 聯(lián)合仿真，驗(yàn)證評價(jià)以A*規(guī)劃算法為基礎(chǔ)的經(jīng)濟(jì)駕駛的燃油經(jīng)濟(jì)性.

3.1 仿真參數(shù)

選擇Carsim 中的一款A(yù) 級轎車作為后續(xù)的研究對象，整車參數(shù)如表1 所示.路面附著系數(shù)選擇為φ=0.8，為了保證駕駛過程中的安全性和舒適性，規(guī)定車輛的最大加速度為2.5 m/s2.

3.2 道路數(shù)據(jù)

為了能夠更好地評價(jià)算法，測試的道路選擇北京理工大學(xué)東門到北京動(dòng)物園的一段路程，全長2.65 km，并經(jīng)過4 個(gè)紅綠燈信號燈，數(shù)據(jù)由高德地圖獲得.并根據(jù)導(dǎo)航結(jié)果，設(shè)定A*算法5 min 內(nèi)到達(dá)終點(diǎn)，設(shè)置時(shí)間間隔為1 s，則將離散為1 501 個(gè)時(shí)空節(jié)點(diǎn).

3.3 仿真結(jié)果及分析

文中采用Matlab/Simulink 與Carsim 聯(lián)合仿真環(huán)境對規(guī)劃出的車速軌跡進(jìn)行仿真驗(yàn)證，如圖2 所示.

圖2 Simulink 和Carsim 聯(lián)合仿真Fig.2 Schematic diagram of the co-simulation between Simulink and Carsim

為了驗(yàn)證A*算法規(guī)劃車速的有效性，文中采用定速巡航為對照組，根據(jù)文獻(xiàn)[11]可得veco= 49.6 km/h，驗(yàn)證多紅綠燈通行經(jīng)濟(jì)性規(guī)劃對燃油經(jīng)濟(jì)性的提升效果.為了驗(yàn)證A*算法的效果，采取3 種工況，一種是定速巡航且多次啟停的最差紅綠燈配時(shí)；一種為定速巡航能夠不啟停的最好紅綠燈配時(shí)；一種為設(shè)定時(shí)間的紅綠燈配時(shí).

3.3.1 最差紅綠燈配時(shí)

當(dāng)定速經(jīng)濟(jì)巡航面臨較多的啟停工況時(shí)，如圖3所示，經(jīng)過的4 個(gè)紅綠燈包含了4 次啟停，圖示上粗線代表紅燈時(shí)段，細(xì)線代表綠燈時(shí)段.表2 是這兩種算法的通行時(shí)間和油耗對比.

表2 A＊經(jīng)濟(jì)駕駛與經(jīng)濟(jì)巡航在最差紅綠燈配時(shí)下的通行時(shí)間和油耗對比Tab.2 Comparison of A＊ economic driving and economiccruise consumption

圖3 A*經(jīng)濟(jì)駕駛與經(jīng)濟(jì)巡航在最差紅綠燈配時(shí)下的對比Fig.3 Comparison between A-star economy driving and economy cruising with stops

從圖3 中可以看出，A*算法會采取盡量不停車的策略來避免車輛的頻繁啟動(dòng)消耗燃油，相對于定速巡航，減少了4 次啟停次數(shù)，因此燃油經(jīng)濟(jì)性得到了提高.由表2 可知, 相比于經(jīng)濟(jì)巡航，A*算法可以節(jié)省33.6%的油耗以及17.7%的通行時(shí)間.

3.3.2 最好紅綠燈配時(shí)

當(dāng)經(jīng)濟(jì)巡航恰好可以不停車通過紅綠燈時(shí)，則A*算法規(guī)劃后的通行策略與經(jīng)濟(jì)巡航相同，如圖4所示，圖示上粗線代表紅燈時(shí)段，細(xì)線代表綠燈時(shí)段，表3 是這兩種算法的通行時(shí)間和油耗對比.

表3 A＊經(jīng)濟(jì)駕駛與經(jīng)濟(jì)巡航在最好紅綠燈配時(shí)下的通行時(shí)間和油耗對比Tab.3 Comparison of A＊ economic driving and economic cruise consumption

圖4 A*經(jīng)濟(jì)駕駛與經(jīng)濟(jì)巡航在最好紅綠燈配時(shí)下的對比Fig.4 Comparison of A-star economy driving and economy cruising without stop

3.3.3 設(shè)定紅綠燈配時(shí)

當(dāng)紅綠燈的配時(shí)設(shè)定處于前兩者狀態(tài)之間時(shí)，如圖5 所示，經(jīng)過的4 個(gè)紅綠燈包含了3 次啟停，圖示上粗線代表紅燈時(shí)段，細(xì)線代表綠燈時(shí)段.表4 是這兩種算法的通行時(shí)間和油耗對比.

表4 A＊經(jīng)濟(jì)駕駛與經(jīng)濟(jì)巡航在設(shè)定紅綠燈配時(shí)下的通行時(shí)間和油耗對比Tab.4 Comparison of A＊ economic driving and economic cruise consumption

圖5 A*經(jīng)濟(jì)駕駛與經(jīng)濟(jì)巡航在設(shè)定紅綠燈配時(shí)下的對比Fig.5 Comparison of A-star economy driving and economy cruising with middle situation

相比于經(jīng)濟(jì)巡航，A*算法雖然增加了4.5%的通行時(shí)間，但節(jié)省了22.8%的油耗.從圖中可以看出，A*算法會采取盡量不停車的策略來避免車輛的頻繁啟動(dòng)消耗燃油，相對于定速巡航，減少了3 次啟停次數(shù)，因此燃油經(jīng)濟(jì)性得到了提高.

通過實(shí)驗(yàn)仿真可以得到，A*算法可以避免車輛產(chǎn)生較多的啟停次數(shù)，從而提高車輛的燃油經(jīng)濟(jì)性.通過使用A*算法可以使車輛在面對多紅綠燈通行時(shí)保持較高的燃油經(jīng)濟(jì)性，從而實(shí)現(xiàn)經(jīng)濟(jì)駕駛的目標(biāo).

4 結(jié) 論

文中根據(jù)車輛動(dòng)力學(xué)模型以及瞬時(shí)燃油消耗模型，建立車輛行駛的優(yōu)化方程.同時(shí)根據(jù)動(dòng)態(tài)規(guī)劃得到兩個(gè)時(shí)空點(diǎn)之間的經(jīng)濟(jì)速度序列，并制定初始狀態(tài)、約束條件，以及利用總?cè)加拖淖鰹榇齼?yōu)化的成本函數(shù).最后使用紅綠信號燈的相位信息，建立多信號燈交叉口的時(shí)空拓?fù)鋱D，使車輛的燃油消耗與最優(yōu)速度序列相對應(yīng)，從而構(gòu)建了完整的多交通信號燈行駛優(yōu)化模型.然后利用A*算法求解智能車輛多紅綠燈信號交叉口行駛經(jīng)濟(jì)性車速軌跡規(guī)劃問題，并搭建Matlab/Simulink 和Carsim 聯(lián)合仿真環(huán)境，在2.65 km 的實(shí)際道路數(shù)據(jù)上進(jìn)行仿真，當(dāng)面對最差紅綠燈配時(shí)時(shí)，A*算法能夠提高33.6%的燃油經(jīng)濟(jì)性以及降低17.7%的通行時(shí)間，證明了多信號燈通行速度規(guī)劃的有效性.經(jīng)過驗(yàn)證，多信號燈通行下的經(jīng)濟(jì)駕駛能夠提升車輛的燃油經(jīng)濟(jì)性，具有較高的研究與實(shí)用價(jià)值.