基于多目標(biāo)協(xié)同演化算法的大規(guī)模自動(dòng)駕駛策略

劉章杰 李慧云

1(中國科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

2(中國科學(xué)院人機(jī)智能協(xié)同系統(tǒng)重點(diǎn)實(shí)驗(yàn)室 深圳 518055)

3(粵港澳人機(jī)智能協(xié)同系統(tǒng)聯(lián)合實(shí)驗(yàn)室 深圳 518055)

1 引 言

隨著經(jīng)濟(jì)的發(fā)展和車流密度的增加，城市交通擁堵日益嚴(yán)重，造成出行成本增加、通勤時(shí)間變長、事故率上升、經(jīng)濟(jì)損失增大和環(huán)境污染加劇等問題[1-2]。如何實(shí)現(xiàn)大規(guī)模車輛協(xié)調(diào)駕駛，在平均速度、事故率等全局優(yōu)化問題上取得突破已成為當(dāng)前研究的重點(diǎn)和難點(diǎn)。

基于優(yōu)化的中心化調(diào)度方法在較小的場景中能充分利用計(jì)算資源，因此在給定目標(biāo)函數(shù)和約束條件的情況下，可采用中心化模型求解器進(jìn)行優(yōu)化求解。然而，中心化的優(yōu)化算法(包括強(qiáng)化學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和模糊邏輯等[3])的計(jì)算復(fù)雜度隨著交叉口數(shù)量、車輛規(guī)模、道路網(wǎng)絡(luò)復(fù)雜程度以及車輛之間可能的沖突關(guān)系等的增加呈指數(shù)增長[4]。即使未來的計(jì)算能力足夠大，由于信息傳輸?shù)难舆t、丟失和計(jì)算時(shí)間，中心化服務(wù)器也很難實(shí)時(shí)響應(yīng)交通請(qǐng)求。這是因?yàn)榻煌ňW(wǎng)絡(luò)具有高度動(dòng)態(tài)、瞬時(shí)變化的特點(diǎn)，所以幾乎不可能以中心化的優(yōu)化方法及時(shí)處理真實(shí)的交通事件和調(diào)度規(guī)劃交通網(wǎng)絡(luò)中的車輛。

而傳統(tǒng)的演化算法(如遺傳算法[5]等)和一些智能優(yōu)化算法(如蟻群算法、粒子群算法[6-7]等)，帶有分布式的特點(diǎn)，能很好地處理規(guī)模龐大(地圖復(fù)雜、車輛數(shù)量多)的問題。例如，研究人員引入分布式節(jié)點(diǎn)，針對(duì)整體交通流，提出蟻群算法和粒子群算法，綜合考慮局部和全局最優(yōu)的影響，不斷調(diào)整搜索方向和搜索速度，并根據(jù)個(gè)體適應(yīng)度進(jìn)行迭代演化，在整體上能夠較好地處理大規(guī)模優(yōu)化問題[8-9]。針對(duì)交通流調(diào)度優(yōu)化問題，研究人員引入粒子群優(yōu)化算法，對(duì)交通流和車輛進(jìn)行分布式調(diào)度調(diào)整，從而緩解交通擁堵的情況[10]。

但在車路協(xié)同網(wǎng)絡(luò)中，傳統(tǒng)的演化算法和智能優(yōu)化算法存在以下問題：(1)僅創(chuàng)建單一種群，因?yàn)樵谲嚶穮f(xié)同網(wǎng)絡(luò)中，車輛種類十分多元化，包括乘用車、商用車等，單一的種群環(huán)境不能滿足演化的需要，同時(shí)在利用局部和全局信息上存在不充分的地方；(2)在對(duì)個(gè)體進(jìn)行評(píng)價(jià)時(shí)，僅考慮個(gè)體在當(dāng)前環(huán)境下的適應(yīng)度，未能充分考慮在車路協(xié)同網(wǎng)絡(luò)中個(gè)體車輛對(duì)其鄰域環(huán)境的影響，以及個(gè)體之間的競爭與合作、個(gè)體與環(huán)境之間、種群之間協(xié)作競爭的影響；(3)傳統(tǒng)的演化算法和智能優(yōu)化算法在演化進(jìn)程中，容易收斂到局部最優(yōu)并且收斂速度較慢。

本文提出基于協(xié)同演化算法的大規(guī)模無人駕駛系統(tǒng)決策優(yōu)化方法，建立面向網(wǎng)聯(lián)汽車的多目標(biāo)優(yōu)化決策的博弈演化平臺(tái)。通過構(gòu)造網(wǎng)格道路模型，建立簡化的車輛運(yùn)動(dòng)學(xué)模型，使得其中的各車輛之間以近鄰博弈的方式進(jìn)行交互。同時(shí)引入多種群環(huán)境和真實(shí)的道路交通環(huán)境，構(gòu)建真實(shí)道路模型和車輛動(dòng)力學(xué)模型。在演化進(jìn)程中，充分考慮不同種群個(gè)體之間、個(gè)體與環(huán)境之間的影響。最終，基于設(shè)計(jì)的獎(jiǎng)勵(lì)函數(shù)，模擬生物種群相互競爭合作的演化進(jìn)程，從而在整體上觀察網(wǎng)絡(luò)中種群自發(fā)涌現(xiàn)的分布特點(diǎn)，尋找不同環(huán)境下的最優(yōu)駕駛策略。

2 相關(guān)研究進(jìn)展

2.1 駕駛策略空間

隨著車聯(lián)網(wǎng)技術(shù)的發(fā)展，良好的駕駛策略可以有效減少交通負(fù)荷并提高整體平均速度以及交通網(wǎng)絡(luò)吞吐量，而設(shè)計(jì)不當(dāng)?shù)鸟{駛策略則可能會(huì)導(dǎo)致交通擁堵甚至造成交通事故[11-12]。駕駛策略可以分為 3 類[13-15]：保守型、理性型和激進(jìn)型。其中，保守型駕駛策略總是以相對(duì)較低的速度行駛；理性型策略根據(jù)交通環(huán)境來調(diào)整速度和行為，若前車速度較小且有足夠的變道空間時(shí)，則選擇變道加速超車；激進(jìn)型策略總是以高速行駛，且在前車速度較小時(shí)總是會(huì)選擇超車。

本文基于 3 類駕駛行為策略的特點(diǎn)，給出形式化的說明，并引入 q 態(tài)模型和狀態(tài)轉(zhuǎn)換機(jī)，形式化地描述 3 類策略在駕駛過程中的特點(diǎn)，擴(kuò)展駕駛策略空間，在競爭與合作的更廣泛的水平上探索各類策略交互的過程和結(jié)果。

2.2 協(xié)同演化算法

將達(dá)爾文的進(jìn)化理論應(yīng)用在自動(dòng)化問題研究方面已有較長時(shí)間。Fogel 等[16]提出了進(jìn)化規(guī)劃，以尋求針對(duì)眾多工程問題的最佳解決方案。但是，進(jìn)化算法通常用于單個(gè)物種，當(dāng)一個(gè)物種進(jìn)化時(shí)，物種之間的選擇壓力隨之改變，其他物種也會(huì)做出反應(yīng)并最終適應(yīng)它——這導(dǎo)致物種之間的高度適應(yīng)性現(xiàn)象[17-18]。研究人員通過引入?yún)f(xié)同演化算法來探索兩個(gè)或多個(gè)物種之間的相互作用[19]，觀察多個(gè)對(duì)象通過競爭或相互協(xié)作，從而促進(jìn)整體的發(fā)展[20]。從數(shù)學(xué)的角度來看，協(xié)同演化具有博弈論的動(dòng)態(tài)特征，最終通過連續(xù)演化的過程達(dá)到穩(wěn)定的平衡狀態(tài)[21]。

在過去 20 年中，演化算法(Evolutionary Algorithms)已被證明是解決多目標(biāo)優(yōu)化問題的有效方法。由于種群的本質(zhì)，多目標(biāo)協(xié)同演化算法能夠在單個(gè)算法執(zhí)行中生成一組權(quán)衡的解決方案(稱為非主導(dǎo)解決方案)，而不必像通常使用數(shù)學(xué)編程技術(shù)那樣執(zhí)行一系列獨(dú)立的方案。此外，多目標(biāo)協(xié)同演化算法可以成功地應(yīng)用于具有諸如多邊、不連續(xù)和不連續(xù)可行區(qū)域等困難特征的問題。另一方面，協(xié)同演化算法是傳統(tǒng)演化算法的擴(kuò)展，已應(yīng)用于多目標(biāo)優(yōu)化問題的解決方案，從而推動(dòng)了新算法和分析公式的開發(fā)，這些算法和分析公式同時(shí)也推動(dòng)了協(xié)同演化算法研究的最新發(fā)展，并在多目標(biāo)協(xié)同演化算法中開辟了新的研究路徑。 協(xié)同演化算法在相應(yīng)的環(huán)境下構(gòu)建多個(gè)子種群的方法有：隨機(jī)分解、模型構(gòu)建和擾動(dòng)構(gòu)建。其中，隨機(jī)分解為隨機(jī)選擇基因的順序，通過事先評(píng)估或預(yù)實(shí)驗(yàn)決定分組的數(shù)量和大??；模型構(gòu)建為基于已有的演化模型構(gòu)建種群和個(gè)體數(shù)量，在演化過程中動(dòng)態(tài)實(shí)施種群更新演化；擾動(dòng)構(gòu)建為通過隨機(jī)擾動(dòng)或噪聲的方式，對(duì)決策變量進(jìn)行擾動(dòng)式分解。

與傳統(tǒng)演化算法相比，協(xié)同演化算法充分考慮種群之間以及種群與環(huán)境之間的相互影響，并且充分考慮種群、個(gè)體之間的競爭與合作水平；在評(píng)估個(gè)體時(shí)考慮該個(gè)體與其他種群個(gè)體之間的交互關(guān)系，在解決大規(guī)模全局優(yōu)化問題時(shí)具有多層次、多操作、多選擇的特點(diǎn)，在高維度、多目標(biāo)、大規(guī)模等問題中具有收斂速度快、優(yōu)化質(zhì)量高、可擴(kuò)展性良好的優(yōu)勢。

3 問題描述與系統(tǒng)設(shè)計(jì)

3.1 問題描述

3.2 車輛模型

其中，vt為車輛t時(shí)刻的速度； 為車輛t時(shí)刻的加速度；xt為車輛t時(shí)刻的幾何中心橫坐標(biāo)；yt為車輛t時(shí)刻幾何中心的縱坐標(biāo)；αt為車輛t時(shí)刻的車姿角度；θt為車輛t時(shí)刻的方向盤轉(zhuǎn)角；xc為信號(hào)燈幾何中心的橫坐標(biāo)；yc為信號(hào)燈幾何中心的縱坐標(biāo)；dt為車輛t時(shí)刻與信號(hào)燈的距離。

3.3 道路模型

將柵格長度gl設(shè)為等于車輛長度，從而使得每一個(gè)柵格中的車輛中心位不超過一輛。如圖 1 所示，車輛A的中心位于網(wǎng)格gr3,2中，車輛B的中心位于另一個(gè)網(wǎng)格gr3,3中。隨后，本文采用公式(4)定義狀態(tài) 的二進(jìn)制狀態(tài)。當(dāng)車輛中心點(diǎn)落入網(wǎng)格中時(shí)，網(wǎng)格將被占用，其狀態(tài)為 1；當(dāng)網(wǎng)格內(nèi)部沒有車輛時(shí)，狀態(tài)為 0。

利用本文所構(gòu)建的道路模型和車輛模型，單個(gè)車輛將僅與其相鄰車輛間接交互。因此，在每一個(gè)時(shí)間步長，將交互復(fù)雜度從n！(n為一個(gè)車鄰域內(nèi)車輛數(shù)量)降到n。這樣大大降低了模型的復(fù)雜性，并增強(qiáng)了可擴(kuò)展性。

圖1 車輛與道路模型Fig. 1 Vehicle and road model

3.4 策略的形式化表達(dá)

本文對(duì)多種候選駕駛策略進(jìn)行探索。

(1)保守型策略(即完全合作)：初始以最大速度行駛，當(dāng)前車的速度較慢時(shí)減速，不超車，避免強(qiáng)烈地使用油門和剎車。

(2)激進(jìn)型策略(即完全競爭)：總是以最高速度行駛，遇到前車的速度較慢時(shí)始終超車。

(3)理性型策略(介于完全合作與完全競爭之間)：溫和地使用油門和剎車，遇到前車的速度較慢時(shí)，可選擇超車或減速。

對(duì)于理性型策略，本文采用 q 態(tài) Potts 模型描述其競爭和合作的不同程度。

3.5 算法流程

本文探索候選策略步驟如下：

(1)初始化道路和車輛種群，其中隨機(jī)設(shè)置車輛目的地。

圖2 狀態(tài)轉(zhuǎn)換圖Fig. 2 State transition diagram

(2)根據(jù)車輛運(yùn)動(dòng)學(xué)模型運(yùn)行車輛以及模擬交通信號(hào)燈，直到所有車輛到達(dá)目的地。在每個(gè)時(shí)間步長更新道路環(huán)境(即網(wǎng)格狀態(tài))。

(4)獲得總體種群車輛得分的平均值μ和標(biāo)準(zhǔn)差δ。根據(jù)圖 3 所示的后代繁衍規(guī)則，確定每個(gè)單獨(dú)車輛的后代數(shù)量。繁衍完成后，歸一化種群數(shù)量和大小，確保交通流密度不變，繼續(xù)下一代模擬運(yùn)行。其中，后代繁衍規(guī)則進(jìn)行 3 個(gè)層次的劃分。

圖3 后代繁衍數(shù)量根據(jù)得分?jǐn)?shù)據(jù)而有所不同F(xiàn)ig. 3 The number of offspring varies according to the scores

圖4 系統(tǒng)流程圖Fig. 4 System flow chart

4 實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析系

4.1 實(shí)驗(yàn)環(huán)境

4.1.1 道路環(huán)境

在不失一般性的前提下，本文選擇廣東省深圳市的一個(gè)城市交通場景(圖 5 黑色虛線)進(jìn)行實(shí)驗(yàn)。其中，道路總長超過 4.5 km，每條車道寬 3.75 m，符合中國道路的建設(shè)標(biāo)準(zhǔn)。實(shí)驗(yàn)中，從 OSM(開放式街道地圖)中導(dǎo)入矢量地圖，其中每個(gè)車道由中心線上的一組點(diǎn)表示，然后通過等間隔插值對(duì)車道中的點(diǎn)進(jìn)行采樣，以獲得每個(gè)網(wǎng)格的中心點(diǎn)以及該點(diǎn)的曲率，以建立 3.3 小節(jié)中介紹的道路網(wǎng)格模型。

圖5 城市道路環(huán)境Fig. 5 Urban road environment

4.1.2 車輛

車輛總數(shù)設(shè)置為 340，最初在該區(qū)域內(nèi)隨機(jī)分布，并根據(jù)不同的策略分為多個(gè)種群。交通密度大約為 0.006 輛/m2。需要說明的是，該水平的車輛密度在城市高速公路中非常常見。例如，Jing 等[22]研究給出的實(shí)際交通數(shù)據(jù)顯示，北京主干路網(wǎng)的平均交通流量每天超過 16 h 高于 0.005 輛/m2。

實(shí)驗(yàn)中，所有車輛的目的地均為隨機(jī)設(shè)置。在車輛的生命周期中，每輛車都會(huì)根據(jù)自己的策略與其他車輛及道路交互，從而影響其他車輛并促進(jìn)整體發(fā)展。

4.1.3 交通燈調(diào)度

在城市交通中，常見使用的交通信號(hào)燈為固定時(shí)間片輪轉(zhuǎn)算法，其中每個(gè)時(shí)間片長度為 8 s。

4.1.4 候選駕駛策略

本文共對(duì) 3 種候選駕駛策略進(jìn)行研究：(1)保守型策略——不超車，以最大速度行駛，當(dāng)前車的速度較慢時(shí)減速，保持不超車；(2)理性型策略——以最大速度行駛，當(dāng)前方車輛的速度較慢且有足夠變道超車的空間時(shí)變道超車；(3)激進(jìn)型策略——以最高速度行駛，且始終超車。

本文研究的具體實(shí)驗(yàn)參數(shù)如表 1 所示。

表1 實(shí)驗(yàn)參數(shù)列表Table 1 The list of experiment parameters

4.2 實(shí)驗(yàn)結(jié)果

本文在模擬仿真環(huán)境中 4.5 km 的道路上進(jìn)行了 340 輛汽車的實(shí)驗(yàn)。其中，本文實(shí)驗(yàn)采用 Python 開發(fā)。

圖 6 為 3 種候選策略種群演化結(jié)果。由于交通流密度較大，激進(jìn)型策略出現(xiàn)了大量事故(圖 6(b))，受激進(jìn)型策略的影響，保守型策略和理性型策略同樣產(chǎn)生事故(急速剎車)。從圖 6(c)可看出，激進(jìn)型和理性型策略取得較高的平均速度，而保守型策略的較低。經(jīng)過 50 代演化后，理性型策略勝出，保守型策略和激進(jìn)型策略均被淘汰(圖 6(a))。

另外，本文引入變道因子 p 來描述更多的中間候選策略。中間策略描述為：當(dāng)遇到前車較低速度且有足夠超車空間時(shí)，變道超車；當(dāng)沒有足夠空間時(shí)，則以概率p超車。例如，“0.3 型中間策略”表示在沒有足夠變道空間時(shí)以 0.3 的概率變道。

圖6 三種候選策略種群演化結(jié)果Fig. 6 Result of evolution for multi-population with 3 candidate policies

如圖 7(a)所示，當(dāng)出現(xiàn)多代事故為 0 后，種群分布處于收斂狀態(tài)(事故為 0，各種群速度接近)，各策略層次分明，與變道因子 p 呈現(xiàn)反相關(guān)(激進(jìn)型策略實(shí)際上是 p＝1)。圖 7(c)顯示，保守策略的平均速度明顯較低，所以被快速淘汰；圖 7(b)顯示，整體事故隨著演化進(jìn)程逐步降低，最后趨于 0。

4.3 討論與分析

從上述實(shí)驗(yàn)結(jié)果可知，在確保安全和有足夠空間的情況下，應(yīng)該保持高速行駛(低速時(shí)應(yīng)該加速)；交通流密度較高時(shí)，不應(yīng)該頻繁變道及劇烈加速，否則容易引起事故，造成交通擁堵；而在交通流密度較低時(shí)，駕駛策略應(yīng)偏向于激進(jìn)策略，在道路資源利用率上更加充分，同時(shí)速度上具有明顯的優(yōu)勢。

圖7 多種候選策略(包括 3 種中間策略)種群演化結(jié)果Fig. 7 Result of evolution for multi-population with 6 candidate policies

在引入基于 q 態(tài)模型的中間策略、擴(kuò)展了駕駛策略空間后，種群分布表現(xiàn)出了明顯的層次性。在交通流密度較高時(shí)，策略表現(xiàn)與變道因子大致呈反相關(guān)關(guān)系。其中在 9～12 代，“0.3 型中間策略”表現(xiàn)最優(yōu)，事故率為 0，平均速度較“0 型中間策略”略微占優(yōu)，總體得分最高。這表明在駕駛過程中，對(duì)于安全距離和足夠變道空間的評(píng)估不能過于謹(jǐn)慎，否則可能會(huì)浪費(fèi)道路資源，降低車輛平均速度。

表 2 將本文方法與現(xiàn)有的一些文獻(xiàn)方法進(jìn)行對(duì)比。移動(dòng)模型(Mobility Model)[23]采用群體智能方法降低計(jì)算復(fù)雜度，由于采取演化規(guī)則不當(dāng)，導(dǎo)致?lián)矶鲁霈F(xiàn)，平均速度較低；本文采用協(xié)同演化的方法，并且設(shè)置良好的演化規(guī)則，避免了擁堵的出現(xiàn)。Zhou 等[24]提出的基于兩層混合模型的預(yù)測控制調(diào)度采用雙層模型、區(qū)域分割、信號(hào)燈調(diào)度的方法，增加了路口的吞吐量及減少了路口的等待時(shí)間，由于采用的最大速度約束不同，平均速度結(jié)果也不同。本文引入柵格道路模型，采用分布式算法，降低了仿真時(shí)間；但是由于本文實(shí)驗(yàn)信號(hào)燈采用時(shí)間片輪轉(zhuǎn)算法，路口吞吐量沒有較好的兼顧，后續(xù)工作可以進(jìn)一步改進(jìn)交通的調(diào)度方式。與上述兩種方法相比，由于本文為了探索駕駛策略對(duì)事故率的影響，在仿真環(huán)境下事故率仍然沒有為 0，未來工作可以考慮進(jìn)一步優(yōu)化事故率。國家統(tǒng)計(jì)局?jǐn)?shù)據(jù)[25]顯示，2019 年平均每月事故率為 0.804 ，本文多目標(biāo)優(yōu)化后事故率小于 0.5 ，提升了 37%。由此可見，本文方法在平均速度、事故率與現(xiàn)有方法相比均有一定程度的下降。

表2 不同仿真結(jié)果對(duì)比Table 2 The comparison of simulation result

實(shí)驗(yàn)配備為 2 GHz 處理器和 8 GB 內(nèi)存的 MacBook Pro，實(shí)驗(yàn)仿真時(shí)間為 3 min。由于本文采用分布式的協(xié)同演化算法，且柵格化道路之后，車輛之間采用間接交互的方式，個(gè)體車輛在每個(gè)時(shí)間步長內(nèi)僅與其領(lǐng)域內(nèi)的車輛進(jìn)行間接交互，故總體計(jì)算復(fù)雜度與車輛數(shù)量成線性關(guān)系，并且可以并行處理，因此可以擴(kuò)展本方法用于探索包含數(shù)百萬輛自動(dòng)駕駛汽車的城市級(jí)的駕駛策略。

5 總結(jié)與展望

由于城市自動(dòng)駕駛汽車具有大規(guī)模和高動(dòng)態(tài)特性的特點(diǎn)，因此不再適合采用中心化優(yōu)化調(diào)度算法。本文將大規(guī)模的城市自動(dòng)駕駛策略優(yōu)化問題表述為眾多子群體之間的多目標(biāo)優(yōu)化的協(xié)同演化問題，并希望觀察具有代表性的候選策略中最優(yōu)駕駛政策的自發(fā)涌現(xiàn)。

在模擬環(huán)境中進(jìn)行了 4.5 km 道路上不同交通流密度下(車輛數(shù)量分別為 170 輛、340 輛)的實(shí)驗(yàn)。結(jié)果顯示，理性型策略可以達(dá)到最佳效果；激進(jìn)型策略產(chǎn)生的事故最高，平均速度也略高；保守型駕駛策略表現(xiàn)最差，25 代后就被淘汰了。采取最佳策略后，事故總數(shù)和平均速度均取得了巨大的提升。其中，事故數(shù)量趨于 0，事故率降低為 0.05% 以下(降低 90%)；平均速度方面由于保守策略的占比下降得以顯著提升，由 13.8 m/s 提升到了 16.3 m/s(提升 30%)。

在此基礎(chǔ)上，本文引入基于 q 態(tài)模型的中間策略，并在相同環(huán)境下進(jìn)行了模擬演化實(shí)驗(yàn)，其中選取交通流密度為 0.006 輛/m2。在演化過程中，出現(xiàn)了明顯的分層趨勢，表現(xiàn)出在該交通流密度下，變道因子越高，策略表現(xiàn)越差的特點(diǎn)，經(jīng)過 15 代的演化進(jìn)程，多代事故數(shù)量趨于 0，各種群平均速度相差不大，種群比例保持相對(duì)穩(wěn)定，達(dá)到收斂狀態(tài)；在淘汰了保守策略后，平均速度達(dá)到了 16.4 m/s。在本文所提出的方法中，由于各車輛之間以近鄰博弈的方式進(jìn)行交互，使得計(jì)算復(fù)雜度與模擬的車輛規(guī)模大小呈線性關(guān)系，故可擴(kuò)展至包含百萬輛自動(dòng)駕駛汽車的城市級(jí)駕駛策略探索。