基于博弈學(xué)習(xí)的多Agent城市交通協(xié)調(diào)控制

1、基于博弈學(xué)習(xí)的多Agent城市交通協(xié)調(diào)控制基于博弈學(xué)習(xí)的多Agent城市交通協(xié)調(diào)控制引言隨著經(jīng)濟(jì)的高速開(kāi)展，城市交通擁擠現(xiàn)象日益嚴(yán)重，如何有效地解決城市交通問(wèn)題顯得愈來(lái)愈突出，它直接影響城市經(jīng)濟(jì)的開(kāi)展和居民生活的質(zhì)量。解決交通擁堵問(wèn)題的主要方法是通過(guò)建立交通流的數(shù)學(xué)模型，運(yùn)用運(yùn)籌學(xué)和控制理論來(lái)控制和優(yōu)化整個(gè)交通系統(tǒng)，但由于交通系統(tǒng)的復(fù)雜性、交通流模型的局限性等因素，控制優(yōu)化的效果并不理想。因此，隨著智能控制的快速開(kāi)展，一些先進(jìn)的控制理論和方法，特別是智能控制的方法開(kāi)始應(yīng)用于城市交通控制1-3。城市交通中的每個(gè)出行者可以建模為一個(gè)本文由論文聯(lián)盟.Ll.搜集整理Agent，每個(gè)Agent的決策要受

2、到其他Agent決策的影響，博弈論是描繪這種互相影響的決策行為的最正確工具，因此將博弈論與多Agent結(jié)合應(yīng)用于交通協(xié)調(diào)控制已經(jīng)成為城市交通研究的熱點(diǎn)4-5。周晶等6對(duì)公交網(wǎng)絡(luò)系統(tǒng)的經(jīng)營(yíng)博弈問(wèn)題進(jìn)展了研究分析，以公交車車費(fèi)作為經(jīng)營(yíng)者的決策變量，建立了經(jīng)營(yíng)者之間廣義Nash平衡博弈模型，并將之轉(zhuǎn)化成一個(gè)擬變分不等式問(wèn)題再進(jìn)展求解；鄭長(zhǎng)江等7對(duì)城市中無(wú)信號(hào)控制路段運(yùn)用博弈論進(jìn)展了分析；李靜等8運(yùn)用博弈論的概念與方法，剖析人們對(duì)公共道路和公交客源的利用，研究公交運(yùn)營(yíng)規(guī)模的互相影響，博弈結(jié)果證明了對(duì)公交運(yùn)營(yíng)進(jìn)展宏觀協(xié)調(diào)的必要性和重要性；黃園高等9對(duì)N個(gè)人合作博弈的Nash及演化平衡策略進(jìn)展分析，通過(guò)實(shí)

3、例運(yùn)用生物動(dòng)態(tài)復(fù)制理論驗(yàn)證演化平衡策略的有效性。Paissan等10主要分析了在十字路口發(fā)生交互的出行者采用不同策略下的不同支付本錢，通過(guò)動(dòng)態(tài)模擬受教育程度高的出行者會(huì)采取合作行為，大大減緩了交通路口堵塞的可能，指出了對(duì)出行者進(jìn)展教育的必要性。不管是智能控制還是結(jié)合博弈方法，都是在完全理性人假設(shè)的根底上，把所有的出行者都?xì)w結(jié)為一類進(jìn)展研究無(wú)視了個(gè)體出行者之間的差異性，而事實(shí)上個(gè)體之間的差異是存在的，這也是在協(xié)調(diào)過(guò)程中必須考慮的問(wèn)題。為了處理個(gè)體之間的差異，首先介紹博弈學(xué)習(xí)理論的思想，在此根底上提出一種路口出行者之間的多Agent博弈學(xué)習(xí)協(xié)調(diào)方法，通過(guò)實(shí)例分析與仿真實(shí)驗(yàn)，證明該方法是可行的。1博

4、弈學(xué)習(xí)定理11-12每個(gè)有限策略博弈，在連續(xù)的概率空間上，總存在混合納什平衡。博弈學(xué)習(xí)理論theryflearningingaes是描繪具有目的的有限理性參與者，如何通過(guò)逐步的調(diào)整策略來(lái)到達(dá)某一平衡點(diǎn)的。博弈學(xué)習(xí)是通過(guò)博弈學(xué)習(xí)主體的策略空間S*t來(lái)影射利益函數(shù)U*t+1的過(guò)程，通過(guò)學(xué)習(xí)Learning，改變學(xué)習(xí)值Learns，a，得到新的最正確Nash平衡值，即函數(shù)U*t+1=fS*t，滿足U*t+1BD*t，tt0，BD*t表示參與主體學(xué)習(xí)后的最正確平衡點(diǎn)13-14。假定博弈參與者可以選擇兩種行為方式合作和對(duì)抗d，ri表示選擇行為ii=，d參與者在群體中的比例，N0i1群體中選擇行為i的初始

5、人數(shù)，Prt，rtd表示在t+1時(shí)刻選擇行為的概率，Nti表示到t時(shí)刻選擇行為i的人數(shù)，Nt表示t時(shí)刻群體總的人數(shù)，那么rti=Nti/Nt表示t時(shí)刻選擇行為i的比例，rt+1i=Nt+1i/Nt+1表示t+1時(shí)刻選擇行為i的比例，因此t+1時(shí)刻選擇行為i的群體的比例的期望為Ert+1i|rti=rti+1/Nt+1*Pti-rti，記向量rt=rt，rtd，假設(shè)r*=r*，r*d是一個(gè)穩(wěn)定的平衡點(diǎn)。那么可以構(gòu)造如下一個(gè)動(dòng)態(tài)的博弈學(xué)習(xí)過(guò)程。1初始化，給定N0和N0d的值以及利益函數(shù)Ur和Udr的表達(dá)式；2根據(jù)t時(shí)刻的情況，通過(guò)一定的數(shù)學(xué)方法計(jì)算Prt，rtd及Pdrt，rtd，轉(zhuǎn)3；3根據(jù)Er

6、t+1i|rti的表達(dá)式進(jìn)展迭代，通過(guò)學(xué)習(xí)值Learns，a的更新，預(yù)計(jì)可能出現(xiàn)的結(jié)果，根據(jù)利益函數(shù)U*t+1進(jìn)展調(diào)整rti，轉(zhuǎn)4；4判斷，給定任意小正數(shù)，假設(shè)|rt-r*|且|rtd-r*d|，完畢；否那么轉(zhuǎn)2。通過(guò)上面的描繪可以看出，博弈學(xué)習(xí)的主要特征如下：1與傳統(tǒng)理論中完全理性人的假設(shè)不同，在博弈學(xué)習(xí)理論中，參與者是有限理性的或者自私的。受參與者的偏好、知識(shí)程度、所處的環(huán)境條件等各種因素的影響，參與者的認(rèn)知、學(xué)習(xí)或推斷才能是有限制的，即策略空間S*t是有條件限制的。2博弈學(xué)習(xí)理論針對(duì)的是一個(gè)動(dòng)態(tài)變化過(guò)程。在每個(gè)時(shí)間段，參與者都根據(jù)自己所獲得的信息，根據(jù)經(jīng)歷和自己的利益不斷學(xué)習(xí)調(diào)整其策略和

7、學(xué)習(xí)值Learns，a，即：U*t+1=fS*t。一般，參與者所搜集的信息為：自己的行動(dòng)歷史、所有參與者的行動(dòng)歷史、其他參與者所采用的策略及收益，博弈學(xué)習(xí)理論是經(jīng)過(guò)長(zhǎng)時(shí)間的學(xué)習(xí)演化以后的一個(gè)長(zhǎng)期結(jié)果。其中博弈學(xué)習(xí)Learns，a的方法為設(shè)群體規(guī)模為S，選擇合作的初始群體規(guī)模為S0合作：首先在一個(gè)交互的群體中區(qū)分出每個(gè)Agent的狀態(tài)，使這兩個(gè)群體隨機(jī)進(jìn)展博弈學(xué)習(xí)選擇行動(dòng)策略，進(jìn)而提出兩個(gè)學(xué)習(xí)概率Px選擇合作的向選擇競(jìng)爭(zhēng)的學(xué)習(xí)的概率和P1-x選擇競(jìng)爭(zhēng)的向選擇合作的學(xué)習(xí)的概率。假定博弈群體采取合作方式會(huì)到達(dá)平衡，那么經(jīng)過(guò)博弈P1-x會(huì)隨著博弈學(xué)習(xí)越來(lái)越大，而Px隨著進(jìn)化的開(kāi)展越來(lái)越小P1-x和Px

8、的初始值為P01-x和P0 x，S合作=S*P1-x+S0合作，顯然，結(jié)果選擇合作的規(guī)模越來(lái)越大，最終就會(huì)到達(dá)較好的平衡。3在博弈學(xué)習(xí)理論中，針對(duì)不同類型的參與者可以有不同的目的，參與者對(duì)自己所獲得的信息，根據(jù)自己的情況可以有不同的處理方式。這樣可以使參與者在不同的博弈學(xué)習(xí)中將以不同的方式或方法對(duì)策略進(jìn)展調(diào)整。博弈學(xué)習(xí)提供了一種不同于傳統(tǒng)理論的答案或解釋。傳統(tǒng)理論認(rèn)為，Nash平衡點(diǎn)是博弈規(guī)那么，參與人是完全理性的，其收益函數(shù)是在共同知識(shí)庫(kù)下產(chǎn)生的，由參與者通過(guò)分析得到結(jié)果。然而，在現(xiàn)實(shí)生活中對(duì)博弈參與者而言，完全理性的參與者是一個(gè)過(guò)高或者不實(shí)在際的要求15。例如，并非每一個(gè)參與者參與博弈過(guò)程

9、時(shí)，都有足夠的時(shí)間或才能進(jìn)展充分的理性合理推斷。針對(duì)此種缺陷，博弈學(xué)習(xí)理論就為Nash平衡點(diǎn)的產(chǎn)生或選擇提供了一種與傳統(tǒng)不同并且比較符合實(shí)際情況的解釋。2基于博弈學(xué)習(xí)的ulti-Agent協(xié)調(diào)定義1城市交通協(xié)調(diào)問(wèn)題可以定義為一個(gè)博弈：G=A，I，S，U，其中A為博弈協(xié)調(diào)中決策主體，參與者的集合A=Agent1，Agent2，Agentn，它是通過(guò)選擇行動(dòng)策略以最大化自己的效用程度；I是每個(gè)Agent擁有的信息，包括其他Agent的特征和行動(dòng)策略的信息；S為Agent的所有可能的策略或行動(dòng)的集合，一個(gè)Agent的所有的可行策略稱為它的策略空間，可以表示為S=S1，S2，Sn，每個(gè)參與者的策略可以

10、形式化為Si：Agentiaii=1，2，N，其中ai為參與者Agenti采取的行動(dòng)，即ai東西直行，南北直行，東西左轉(zhuǎn)，南北左轉(zhuǎn)；U為利益函數(shù)，是指在既定策略組合條件下Agent的得失情況，即在一個(gè)特定的策略組合下參與者得到的效用程度。出行者Agent的利益函數(shù)是出行者通過(guò)路口延誤時(shí)間最少，出行者Agent的利益函數(shù)是將時(shí)間、路段擁擠度、道路質(zhì)量、耗油量作為衡量效用的綜合指標(biāo)。定義2Nash平衡的定義：對(duì)于定義1給出的博弈，假定策略組合為S*=S*1，S*2，S*n，對(duì)任一博弈方i的策論si*，都是對(duì)其余博弈方策略的組合s*1，s*i-1，s*i+1，s*n的最正確對(duì)策，也即uis*1，s*

11、i-1，s*i，s*i+1，s*nuis*1，s*i-1，s*ij，s*i+1，s*n對(duì)任意sijSi都成立，那么稱s*1，s*n為G的一個(gè)納什平衡。其中S*i為第i個(gè)Agent選擇的策略，Ui為第i個(gè)Agent的利益函數(shù)，Si為第i個(gè)Agent的策略空間。2.1多智能體協(xié)調(diào)構(gòu)造雖然每個(gè)Agent的決策是獨(dú)立的，但是每一個(gè)Agent的決策會(huì)影響到其他Agent的決策，每一個(gè)Agent也受其他Agent決策的影響，因此一個(gè)Agent在做決策時(shí)，有必要考慮其他Agent可能采取的決策來(lái)決定自己的決策，各Agent之間必然會(huì)發(fā)生一定程度的沖突。為了進(jìn)展沖突消解，必須進(jìn)展相應(yīng)的協(xié)調(diào)分析。為此設(shè)計(jì)了一個(gè)

12、三層協(xié)調(diào)構(gòu)造如圖1所示，下層是出行者之間的協(xié)調(diào)，中間是路口之間的協(xié)調(diào)，上層是區(qū)域之間的協(xié)調(diào)。其目的是根據(jù)實(shí)際的交通情況，最大限度地使出行者都能盡快順利通過(guò)各路口，它要求出行者之間進(jìn)展協(xié)調(diào)，保證路口通暢，進(jìn)而使得區(qū)域通暢，以到達(dá)全局的最優(yōu)。2.2基于多Agent的協(xié)調(diào)過(guò)程為方便起見(jiàn)，把路口的一個(gè)出行者Agent作為發(fā)起者，路口的其他出行者Agent作為參加者。出行者之間的協(xié)調(diào)可以概括為：發(fā)起者發(fā)出一個(gè)信號(hào)，每個(gè)參加者根據(jù)情況做出反響，參加者再對(duì)這些反響進(jìn)一步處理，可能會(huì)出現(xiàn)屢次提議反響處理的過(guò)程。在協(xié)調(diào)開(kāi)始前，每個(gè)出行Agent應(yīng)該具有知識(shí)庫(kù)，獲取方式如圖2所示?；诙郃gent的協(xié)調(diào)博弈過(guò)程描

13、繪如下：1假設(shè)車輛Agenti是發(fā)起者，行人Agentj是一個(gè)參加者，發(fā)起者已經(jīng)和參加者協(xié)商了n次，即FinFjn，其中Fi表示i發(fā)起協(xié)商；n0，+，說(shuō)明車輛Agenti已發(fā)送給行人Agentjn個(gè)提議。2發(fā)起者Agent知道在此之前的每個(gè)Agent的動(dòng)作。3車輛Agent使用博弈學(xué)習(xí)方法進(jìn)而決定他下一步的動(dòng)作。即Learns，aLearns+1，a+1，s是每個(gè)Agent可能的狀態(tài)終止或非終止，a是行動(dòng)策略集。4Fin+1Fjn+1，行人Agent接收到來(lái)自車輛Agent的第n+1次提議，就是車輛Agent的第n+1次的動(dòng)作。5車輛Agent更新博弈學(xué)習(xí)值Learns，a，推斷可能出現(xiàn)的情況

14、，根據(jù)利益函數(shù)選擇下一步的最正確動(dòng)作。2.3基于博弈學(xué)習(xí)的多Agent協(xié)調(diào)方法假設(shè)在無(wú)信號(hào)燈管理的盲區(qū)，為了使出行者都可以順利出行，把路口的多個(gè)出行者簡(jiǎn)化為參加者車輛Agent和發(fā)起者行人Agent，詳細(xì)博弈學(xué)習(xí)協(xié)調(diào)算法描繪為：初始化對(duì)每個(gè)s，a，初始化學(xué)習(xí)值Learns，a，假設(shè)行人aj獲得車輛ai的提議；循環(huán)直到st是終止?fàn)顟B(tài)，否那么執(zhí)行下面的操作。1行人aj執(zhí)行動(dòng)作at，調(diào)整學(xué)習(xí)值Learns，a，得到新的學(xué)習(xí)值Learnst+1，at+1并于車輛ai發(fā)起博弈協(xié)調(diào)；2根據(jù)新的學(xué)習(xí)值Learnst+1，at+1，調(diào)整策略空間St*，獲得新的Nash平衡，得到新的利益函數(shù)Ut+1*=fSt*

15、；3新的Nash平衡存在，車輛Agent和行人Agent向路口Agent反響，進(jìn)展下一個(gè)新的控制周期；否那么，回到1，尋找Nash平衡；4經(jīng)過(guò)約定次數(shù)的博弈學(xué)習(xí)協(xié)調(diào)后仍找不到Nash平衡，協(xié)調(diào)失敗，懇求人工干預(yù)。該算法的優(yōu)點(diǎn)如下：1具有較好的尋找平衡點(diǎn)的特性，對(duì)初值不敏感，初值處置選擇不當(dāng)時(shí)，可以通過(guò)博弈學(xué)習(xí)后，仍能找到好的平衡點(diǎn)，滿足控制的要求；2操作方便，不需要復(fù)雜的規(guī)那么，只需通過(guò)一個(gè)簡(jiǎn)單的博弈學(xué)習(xí)，便可尋找到平衡點(diǎn)；3不僅適宜理性群體優(yōu)化，也適宜有限理性群體優(yōu)化。2.4實(shí)例分析考慮有如圖3所示的博弈，它們之間為有限理性重復(fù)博弈，其合作競(jìng)爭(zhēng)的構(gòu)造滿足囚徒困境模型的要求。圖中R、S、T、P

16、表示不同的博弈策略對(duì)應(yīng)的受益值。博弈的四種結(jié)果：，表示互相合作，d，d表示互相反叛，d或d，表示博弈方之一單方面變節(jié)。假設(shè)該重復(fù)博弈有一大群有限理性的參與人，他們不可能一開(kāi)始就找到最正確的策略合作，合作，因此在參與人中有些是合作類型的，有些是不合作類型的，但這種類型不是事先給定的，而是根據(jù)參與人的習(xí)慣和得失在學(xué)習(xí)過(guò)程與策略調(diào)整中改變的，這就可以采用博弈學(xué)習(xí)協(xié)調(diào)算法。假設(shè)參與人群體中合作類型的比例是x，那么不合作類型是1-x，群體的博弈是隨機(jī)配對(duì)的，應(yīng)用上面的分析結(jié)果，用來(lái)表示參與人的收益，于是合作類型參與人的收益為：U=x*R+1-x*S不合作類型參與人的收益為：Ud=x*T+1-x*P參與人

17、的平均收益為：U=x*U+1-x*Ud于是通過(guò)求導(dǎo)可得合作類型的參與人比例的動(dòng)態(tài)變化可表示為：6，6，10，10是平衡點(diǎn)，出行者為了追求利益最大化，盡管初始博弈時(shí)不一定都選擇禮讓，但是通過(guò)博弈學(xué)習(xí)，利用多智能體協(xié)作算法，最終大都逐漸會(huì)選擇禮讓，禮讓組合。3仿真實(shí)驗(yàn)在atlab2022環(huán)境下基于以上的模型、實(shí)例和算法，對(duì)無(wú)交通信號(hào)的無(wú)人盲區(qū)十字路口的交通協(xié)調(diào)進(jìn)展仿真，假設(shè)車輛到達(dá)服從泊松分布，路口車輛的限制閾值為30，最大限制閾值為40，以通過(guò)路口的順利程度作為性能指標(biāo)，1表示最快通過(guò)，0表示堵塞，越接近1表示性能越好，反之那么性能較差。仿真通過(guò)對(duì)四種方法比照研究：1路口行人大都為了快速通過(guò)，盲

18、目采用搶行通過(guò)的方式，搶行比例較高。2路口行人通過(guò)智能控制協(xié)調(diào)，選擇通過(guò)方式。3路口行人通過(guò)簡(jiǎn)單博弈，通過(guò)判斷選擇出行方式。4路口行人通過(guò)博弈學(xué)習(xí)協(xié)調(diào)，選擇合理的通過(guò)方式。從圖4仿真結(jié)果可以看出，在路口流量較少時(shí)，幾種方法性能接近，在路口流量到達(dá)限制閾值時(shí)，普通方法會(huì)造成交通堵塞，而簡(jiǎn)單博弈方法和智能控制方法在車輛數(shù)目接近閾值時(shí)會(huì)變化速度較快，這兩種方法的性能比較接近，博弈方法性能稍高。從圖4的對(duì)照可以看出，博弈學(xué)習(xí)協(xié)調(diào)方法性能比較好，它的性能在0.5左右，可以很好地保證交通的暢通。在車輛數(shù)目超過(guò)閾值接近限制流量時(shí)，前幾種方法都容易出現(xiàn)交通擁堵現(xiàn)象，而博弈學(xué)習(xí)方法還有一定的協(xié)調(diào)才能，但在接近限制流量性能會(huì)快速下降，而且在車輛數(shù)目超過(guò)最大流量時(shí)博弈學(xué)習(xí)協(xié)調(diào)算法的作用就不明顯了，就需要尋求路口協(xié)調(diào)、區(qū)域協(xié)調(diào)或其他道路管理控制手段，有時(shí)還需要人工干預(yù)。從圖5中可以看出，利用博弈學(xué)習(xí)的方法，出行者會(huì)選擇一種比較合理的出行方式，使得等待時(shí)間相對(duì)較短，到達(dá)節(jié)約時(shí)間的目的，最終實(shí)現(xiàn)路口的快速