一種基于合作博弈論的自動駕駛車道變更模型

劉 超 丁 箐

(中國科學技術大學軟件學院 安徽 合肥 230051)

0 引 言

自動駕駛[1]近年來受到越來越多的關注，而車道變更[2-4]是自動駕駛技術中最重要也是最具有挑戰性的任務。違法的和危險的車道變更會引起嚴重的交通事故、大量的經濟損失以及人口傷亡。研究安全有效的車道變更模型對于自動駕駛領域就顯得尤為重要。

已有文獻中車道變更模型可以分為非合作模型與合作模型兩種。非合作模型主要可以分為基于規則的變道模型、基于非合作博弈的變道模型，以及其他非合作模型等。文獻[5]提出了一種基于規則的變道模型，車輛通過進行一系列的判斷來決定是否可以變道。由于缺乏與其他車輛的交流與合作，該模型在很多情境下并不適用。文獻[6]提出了一種基于非合作博弈的模型，通過模擬人工變道過程，使用信號燈以及小步橫移和周圍車輛交互，進行變道。由于車輛間不進行合作，在變道過程中無法始終保持車輛之間的安全距離。文獻[7]則提出了一種基于Stackelberg博弈的模型，它通過挑選具有充足車距的目標車輛來完成變道行為。文獻[8]則提出了一種在互聯車輛間傳遞信息來完成變道的非合作博弈方法。非合作車道變更模型一般是對周圍環境進行分析預測來做出最大化自身收益的選擇。但車輛間不進行合作就很難保證整體收益最大化，甚至在極端情況下可能無法完成變道。其他諸如基于機器學習[9]、強化學習以及馬爾可夫決策模型也同樣忽略了合作的重要性。

事實上，車道變更的本質就是車輛之間進行合作的結果。文獻[10]認為在整個車道變更過程中，車輛之間進行合作可以極大提高車輛之間的安全性。文獻[11]針對在人類監控之下的自動駕駛車輛，設計了基于社會狀態和交易補償的博弈策略來激勵車輛完成合作變道行為。文獻[12]設計了一個多Agent的馬爾可夫博弈模型，同時使用深度強化學習來求出博弈解。作者提出了一種被動-主動合作變道框架來刻畫變道過程，每一個參與車輛通過調整自己的行為來達到博弈的納什均衡。文獻[13]假設車輛想要變道時，周圍車輛通過提供車距來配合它完成變道。由于車輛間不進行交互，速度可能產生大幅度變化，引起強烈的駕駛不適感。由于沒有采取任何措施來激勵車輛，很難保證車輛一定會參與合作。

本文首次將合作博弈理論應用到車道變更領域，提出了一種針對自動駕駛車輛的新穎的變道模型。該模型將想要變道的車輛以及它周圍的車輛作為一個整體，內部的每一個參與者進行合作，以提高整體收益為目的，同時每一個參與者的個體收益也能夠增加。本文首先提出了用于兩車合作的納什討價還價博弈模型，然后擴展為三車合作博弈模型，分別求出了對應的納什討價還價解[17]和夏普利值[18]。在個體收益分配方案中加入了支付補償部分實現收益的可轉移性，起到激勵車輛積極參與合作的作用。該模型保證了變道過程中車輛間整體安全距離得到有效的保持，車輛整體通行速度增加的同時駕駛舒適性也得到提升。

1 系統模型

假設在車道變更過程中，變道車輛與周圍車輛作為一個整體，其內部車輛通過協作實現加速與減速來完成變道過程。隨后這些車輛通過納什討價還價博弈以及三人合作博弈完成整體收益的分配。

圖1為一個簡單真實車道變更場景，在納什討價還價模型中，carA打開信號燈，想要變更車道到Lane-3，carB選擇合作，創造出空間來配合carA完成變道。在三車合作博弈模型中，當carA想要變道時，carB以及carC都選擇合作來完成變道過程。

圖1 車道變更問題的場景圖

(1)

(2)

(3)

xij(t)=xi(t)-xj(j)

(4)

(5)

ΔVθ=Vθ(t=n)-Vθ(t=1)

(6)

(7)

(8)

式中：Wθ是carθ的舒適性收益;aθ(t)代表t時刻車輛的加速度。

2 基于合作博弈的車道變更模型

本節首先提出兩車合作博弈模型，然后擴展到三車輛的合作博弈模型。

2.1 基于納什討價還價的車道變更模型

兩人合作博弈就是納什討價還價博弈，假設參與者1與參與者2進行合作所獲得的整體收益為u(1,2)。經過一系列協商后，參與者1所獲得的個體收益為p1，參與者2為p2，同時p1+p2=u(1,2)。則(p1,p2)為整體收益的一種分配方案，所有可能的(p1,p2)組成了納什討價還價博弈的可行配置集合，記為F。如果雙方協商不成功，合作無法達成，(u(1),u(2))就是談判的破碎點，u(1)、u(2)即為參與者不合作時的收益。

模型中車輛整體的收益是由安全性、速度、舒適性三部分組成，如果這些收益無法在參與者間進行轉移，就會導致無法達到納什討價還價解。于是在個體收益分配方案中加入了交易補償部分(Upay)，使得收益可以在參與者之間進行轉移。這里首先提出了一種個體收益分配方案(pA,pB)如式(9)和式(10)所示，然后證明該方案就是本輪博弈的納什討價還價解。

(9)

(10)

式中：Upay是car A用于激勵其他車輛參與合作所支付補償的金額。

如車輛間談判失敗，carB不進行合作，假設其會繼續保持勻速行進而不減速，當兩車間距離小于一定數值，carA就會取消變道操作。當車輛不進行合作時，各自的收益u(A)與u(B)分別表示為:

(11)

(12)

如果一個可行配置(p1,p2)(其中p1≥u(1),p2≥u(2))是該博弈的納什討價還價解，當且僅當存在正整數λ1>0與λ2>0，使得λ1(p1-u(1))=λ2(p2-u(2))與λ1p1+λ2p2=maxy∈F(λ1p1+λ2p2)同時成立。

2.2 基于合作博弈的車道變更模型

在三車輛的合作博弈變道模型中，參與車輛的集合為N={A,B,C}，博弈的聯盟S為N的子集，同時一共包含2n-1個非空子集。聯盟S的收益函數V(S)表示為:

(13)

(14)

(15)

(16)

不同的聯盟有著不同的整體收益，但是本例中如果聯盟沒有car A的參與，就不會發生車道變更行為，則整個聯盟的收益為零。對于car B和car C而言，都需要car A參加聯盟，那樣它們才能獲得更高的個體收益。但car A是選擇car B或者car C或者兩者組成聯盟，則取決于car A在哪個聯盟中的個體收益更高。

在合作博弈論中，求解的方式有很多種，夏普利值是人們普遍認同且沒有歧義的求解合作博弈問題方式。式(17)使用夏普利值來求解聯盟S中參與者的收益。

(17)

式中：k是聯盟S中參與者的個數;n是大聯盟N中的參與者的個數。

與上述的納什討價還價博弈模型一樣，該博弈中的聯盟的收益也是由安全性、速度以及舒適度三個方面組成，但是這些收益同樣無法在參與者之間進行轉移，也就無法取到相對應的夏普利值。因此在本次博弈中個體的收益分配策略中加入了交易補償部分，來實現參與者之間收益的可轉移性。大聯盟中每一個個體的收益方案如下所示：

(18)

(19)

(20)

3 實驗與結果分析

本文采用MATLAB/simulink仿真軟件對基于納什討價博弈的車道變更模型以及基于合作博弈的車道變更模型進行了仿真驗證。在仿真實驗中的所有車輛都安裝了合作變道模塊，可以根據不同的場景進行合作，完成變道操作。在實驗中，每一個車輛都有自己的坐標位置、速度、加速度以及初始車道等相關參數，這些參數會在不同場景下的實驗中發生改變，當車輛的初始車道參數發生變化后，就意味著車道變更過程完成。我們還考慮了不同類型的車輛對我們提出模型的影響，將車輛類型分為大卡車、公交車、小汽車三種類型進行實驗。與此同時，不同類型車輛的安全車距以及最小車距是不同的，大卡車的安全車距大于公交車，公交車大于小汽車。由于實驗存在重復性，本文選擇了其中更困難的情況來進行實驗，而不考慮所有不同類型車輛的組合。實驗中car A為變道車輛，它的類型包括上述三種，car B為小汽車，car C為大客車。實驗目的主要有：① 驗證本文提出的模型是否有效地提升了所有車輛整體的收益；② 計算每一個參與者的個體收益和car A用于激勵其他車輛參與合作所需要的代價Upay。實驗的相關參數如表1所示。

表1 相關參數表

表1中：VA、VB和VC分別是car A、car B和car C的初始速度，XA、XB和XC是車輛的初始位置。同時amax是car A的最大加速度，Xsf1、Xsf2以及Xd分別是car A和car B的安全車距、car A與car C的安全車距以及車輛之間的最小車距，當car A為大卡車時，amax=1 m/s2，Xsf1=15 m，Xsf2=20 m，Xd=3m；car A為公交車時，amax=1.5 m/s2，Xxf1=12 m，Xxf2=18 m，Xd=2 m；car A為小汽車時，amax=2 m/s2，Xsf1=10 m，Xsf2=15 m，Xd=1 m。同時，LA、LB、LC分別是car A、car B、car C的初始車道。

3.1 基于納什討價還價模型的相關實驗

在本文提出的基于納什討價還價車道變更模型中，car A做最大加速的加速操作，直到速度達到Vmax后，保持勻速運動，同時car B進行相應的減速操作，保證車輛之間的安全車距，直到車輛之間的距離達到安全車距后，car A進行變更車道，操作完成后，車輛的車道參數發生變化。本文通過以下幾個實驗來仿真模擬正常交通狀況的納什討價還價變道模型。

實驗中橫坐標表示car A與car B初始位置的相對距離。圖2顯示了在不同相對距離之下，車輛之間合作與不合作時整體收益的對比。當車輛之間的相對距離足夠大時，合作與不合作對整體收益的影響很微小。但是隨著相對車距的逐漸減少，合作對整體收益的影響就遠遠大于它們不合作的時候。同時當相對車距很小時，不進行合作是無法完成變道的，整體收益降為零。從圖3可以看出，小汽車合作時獲得的整體收益大于公交車和大卡車，那是因為不同類型的車輛的安全車距不同，同等情況下，大卡車和公交車的安全車距是大于小汽車的，那么整體的安全性收益就會降低，同時大卡車和公交車的速度增量沒有小汽車大。

圖2 合作與不合作的整體收益對比

圖3 不同車輛類型下的整體收益

從圖4可以看出，car A的個體收益絕大多數情況是大于car B的個體收益的。當相對車距足夠大時，car A基本占了所有的收益，car A用于激勵car B進行合作的支付代價很小。但是隨著車距的逐漸減小，需要的支付代價越來越大，那么car B的收益逐漸增加，car A的收益逐漸減小。圖5中car A隨著車距變小和加速度變小，支付代價變得更大。當車距越來越小時，需要支付的代價就越來越大，同時加速度越大，需要支付的代價就越小。因為在車距比較小或者加速度比較小時，更需要其他車輛的合作，所以需要更大的支付代價來激勵其他車輛進行合作。

圖4 個體收益

圖5 不同加速度下的支付代價

3.2 基于合作博弈模型的相關實驗

基于合作博弈論的模型是由二人納什討價還價模型加入了car C，擴展而來的三車輛合作變道模型。其中，car A和car B進行合作的操作和上述的模型是一樣的，同時如果car C進行合作，那么它就會進行加速操作，保持與car A的安全車距來配合完成變道過程中。反之，則保持勻速運動。

在圖6中清楚地展示了大聯盟的整體收益遠遠高于其他聯盟。主要是因為所有參與者都參與合作時，安全性收益和速度增量就會更大。圖7中的實驗表明了小汽車類型的大聯盟整體收益大于其他類型的整體收益。那是因為其他類型車輛的安全車距大于小汽車，從而導致相應的整體的安全性收益小于小汽車類型的聯盟。與此同時，小汽車的速度增量也大于其他類型，所以小汽車類型的聯盟的整體收益最大。圖8則顯示了不同聯盟之下car A的夏普利值。實驗結果顯示，在大聯盟下的car A的夏普利值(car A的個體收益)相對于其他聯盟是最大的，那么car A就會選擇加入大聯盟。

圖6 不同聯盟之下的整體收益

圖7 不同車輛類型下大聯盟的收益

圖8 不同聯盟下的夏普利值

圖9給出了大聯盟中不同參與者的個體收益的變化趨勢。當相對車距足夠大時，car A對聯盟的影響最大，因為只需要支付很小的代價來激勵其他車輛完成變道操作，其他車輛收益相對較小。但是，隨著車距不斷減小，其他車輛的合作就顯得尤為重要，car A想要完成變道，就需要支付更多的代價，那么它的收益降低，其他車輛的收益就會增大。圖10則顯示了不同車距與不同加速度之下的car A需要支付代價Upay的變化。當車距變小和加速度變小時，car A支付代價更大。因為車距越小或者加速度越小時，更需要其他車輛的合作，所以需要更大的支付代價來激勵其他車輛進行合作。

圖9 大聯盟下不同參與者的夏普利值

圖10 大聯盟下的支付代價

4 結 語

本文首次將合作博弈理論應用到車道變更領域，提出了用于兩車合作的納什討價換博弈模型和三車合作的合作博弈模型，將想要變道的車輛以及它周圍的車輛看作為一個整體，整體內部的每一個參與者進行合作，并求出了相對應的納什討價解和夏普利值。同時本文在個體收益分配方案中加入了支付補償部分實現了收益的可轉移性，從而可以取得相對應的解，起到了激勵車輛積極參與合作的作用。實驗表明，進行合作，車輛整體收益有著大幅增長，同時合作的每一個參與者的個體收益也有著明顯的增加。