交叉口Agent 間的博弈學(xué)習(xí)協(xié)調(diào)方法

夏新海，許倫輝

(1.華南理工大學(xué)土木與交通學(xué)院，廣東廣州510640 2.廣州航海高等專(zhuān)科學(xué)校港航管理系，廣東廣州510725)

Agent是能夠?qū)崟r(shí)地、動(dòng)態(tài)地、自主地與不斷變化著的外部環(huán)境進(jìn)行交互的智能規(guī)劃控制系統(tǒng)，它可以感知并作用于環(huán)境，并且具有希望通過(guò)行為的執(zhí)行而達(dá)到一定的目標(biāo)。Multi-agent system是指由一組具有一定資源和能力、相對(duì)獨(dú)立、相互作用的Agent組成的系統(tǒng)。Multi-agent system的協(xié)調(diào)是指每個(gè)自主Agent對(duì)其目標(biāo)、資源、思維狀態(tài)等進(jìn)行合理安排，以調(diào)整各自的決策和行為，最大限度地實(shí)現(xiàn)各自目標(biāo)。協(xié)調(diào)研究是Multi-agent system研究的核心。目前已經(jīng)有一些對(duì)于Multi-agent system的協(xié)調(diào)的研究，如李凡長(zhǎng)［1］提出了Multi-agent system的一些協(xié)調(diào)組合設(shè)計(jì)模型，包括Agent拉丁方矩陣?yán)碚摰?王立春［2］利用協(xié)商－協(xié)商過(guò)程－協(xié)商線程的概念建立了一個(gè)多邊－多問(wèn)題協(xié)商模型，并且支持Agent在協(xié)商過(guò)程中的學(xué)習(xí)?？傮w來(lái)說(shuō)，目前對(duì)于Multi-agent system的協(xié)調(diào)模型主要用到BDI模型，協(xié)商模型，自協(xié)調(diào)模型、協(xié)作規(guī)劃模型等。主要的協(xié)調(diào)方法主要涉及到基于對(duì)策論的顯式協(xié)調(diào)和基于社會(huì)規(guī)則的隱式協(xié)調(diào)，以及用到一些學(xué)習(xí)方法。

目前基于Multi-agent的協(xié)調(diào)在開(kāi)放、分布、復(fù)雜系統(tǒng)中得到廣泛的應(yīng)用。以城市交叉口系統(tǒng)為例，城市交叉口系統(tǒng)在具有分布式、多干擾、不確定性特點(diǎn)的同時(shí)，又具有很強(qiáng)的自組織、自學(xué)習(xí)、自穩(wěn)定的特點(diǎn);而Multi-agent system具有分布式結(jié)構(gòu)、很強(qiáng)的自學(xué)習(xí)自組織能力，同時(shí)又具有相互間的協(xié)調(diào)功能，與城市區(qū)域多交叉口系統(tǒng)在結(jié)構(gòu)上、機(jī)理上具有很大的相似性，因此將基于Multi-agent的協(xié)調(diào)在城市交叉口協(xié)調(diào)控制中的應(yīng)用已經(jīng)受到國(guó)內(nèi)外越來(lái)越多的重 視。Burmeister 和 SUSAN［3－4］提 出 了 Multiagent在交通運(yùn)輸中應(yīng)用的思路;歐海濤［5］提出了一種基于遞歸建模的多智能體協(xié)調(diào)方法及多智能體的貝葉斯學(xué)習(xí)方法并應(yīng)用于城市交通系統(tǒng)中;馬壽峰［6］采用對(duì)策論與社會(huì)規(guī)則相結(jié)合的方法實(shí)現(xiàn)了兩個(gè)路口控制Agent間的協(xié)調(diào)問(wèn)題?？偟膩?lái)說(shuō)，Multi-agent應(yīng)用在城市交叉口協(xié)調(diào)時(shí)在協(xié)調(diào)模型、方法、機(jī)制等方面的研究還不夠。筆者將 Multiagent技術(shù)應(yīng)用在城市交叉口的協(xié)調(diào)控制中，建立一種基于Multi-agent的協(xié)調(diào)機(jī)制，并用分布式Q學(xué)習(xí)方法和對(duì)策論作為其實(shí)現(xiàn)策略，驗(yàn)證了基于Multiagent的城市交叉口信號(hào)協(xié)調(diào)方法的有效性。

1 基于Multi-agent的協(xié)調(diào)機(jī)制

1.1 Agent間的協(xié)調(diào)過(guò)程

以城市交叉口協(xié)調(diào)為例，城市區(qū)域內(nèi)各交叉口處的交通流是相互關(guān)聯(lián)的。為每個(gè)交叉口設(shè)立一個(gè)Agent，稱(chēng)為路口 Agent。路口Agent之間是平等自治的關(guān)系。每個(gè)自治的路口Agent代表一個(gè)路口的利益。設(shè)立一個(gè)管理Agent負(fù)責(zé)若干個(gè)路口Agent的協(xié)調(diào)管理。路口Agent和管理Agent統(tǒng)稱(chēng)為T(mén)SCA(Traffic Signal Control Agent)。路口Agent主要由學(xué)習(xí)器、行為決策器、通訊模塊、協(xié)調(diào)模塊組成。學(xué)習(xí)器根據(jù)實(shí)測(cè)的交通數(shù)據(jù)判斷是否有符合條件的規(guī)則，如果有，則執(zhí)行該規(guī)則，從而確定信號(hào)控制方案。協(xié)調(diào)模塊則負(fù)責(zé)分析路口Agent所控路口目前的交通狀態(tài)，決定是否有必要向其它路口Agent發(fā)送消息，并處理路口Agent間的協(xié)調(diào)問(wèn)題。通訊模塊主要負(fù)責(zé)與管理Agent及相鄰路口Agent的通訊，行為決策器主要解決路口Agent的推理決策功能?；贛uli-agent的城市交叉口協(xié)調(diào)控制主要通過(guò)TSCA的協(xié)調(diào)達(dá)到交通流信號(hào)控制的最優(yōu)化。

路口Agent和管理 Agent間的協(xié)調(diào)過(guò)程如下(通過(guò)引入擁擠度閥值):①如果路口Agent某相位的擁擠度沒(méi)有超過(guò)閥值，則路口Agent可以采用自主式信號(hào)控制;②當(dāng)路口Agent某相位的擁擠度超過(guò)了閥值，則路口Agent需要與相鄰的路口Agent進(jìn)行交互;③若協(xié)調(diào)策略存在，每個(gè)路口Agent按照該協(xié)調(diào)策略進(jìn)行信號(hào)控制，本次交互結(jié)束;如果協(xié)調(diào)策略不存在，則與上一級(jí)管理Agent進(jìn)行交互;④管理Agent對(duì)其所轄的路口Agent進(jìn)行協(xié)調(diào)，尋求協(xié)調(diào)策略;如果管理Agent對(duì)其所轄的路口Agent協(xié)調(diào)失敗，則與相鄰的管理Agent進(jìn)行交互，尋求協(xié)調(diào)策略，否則，各個(gè)路口Agent按照原策略進(jìn)行控制。

1.2 資源動(dòng)態(tài)協(xié)調(diào)配置模型

城市交叉口協(xié)調(diào)中存在資源沖突、目標(biāo)沖突、結(jié)果沖突等，由于城市交叉口間的交通流具有較強(qiáng)的關(guān)聯(lián)性，單獨(dú)追求某一交叉口通行能力的提高和延誤的減少而不考慮路口之間的相關(guān)性，可能引起關(guān)聯(lián)路口更大的延誤。

對(duì)于單交叉口Agent，設(shè)Q(n－1)p為在第n－1個(gè)周期，p相位綠燈信號(hào)末該方向車(chē)輛滯留數(shù);qkp為p相位第k秒到達(dá)的車(chē)輛數(shù);off－c為交叉口駛離率;tpg為 p相位綠燈時(shí)間，則有［7］:

式中:tdr為當(dāng)前相位紅燈方向車(chē)輛排隊(duì)等待時(shí)間;tdg為從上一周期該相位綠燈信號(hào)結(jié)束到當(dāng)前時(shí)間內(nèi)綠燈方向車(chē)輛排隊(duì)等待時(shí)間;td為平均等待時(shí)間;Tn為信號(hào)周期時(shí)間長(zhǎng);M為相位數(shù)。

這里以一個(gè)TSCA為一個(gè)角色，對(duì)第i個(gè)區(qū)域內(nèi)包含n個(gè)關(guān)聯(lián)的角色TSCA的資源協(xié)調(diào)配置可以抽象表示為［8］:

式中:Ri為資源描述，包括資源價(jià)格，這里可以選為某一區(qū)域交叉口單位時(shí)間通行能力的提高額度或者延誤的減少程度;αi1，...，αin為 n個(gè) TSCA所需要的資源份額，這里可以選為各個(gè)路口通行能力的提高額度或者延誤的減少程度;βi1，...，βin為 n個(gè)TSCA所承擔(dān)的空閑資源份額;γi為空閑資源占總資源的份額。

設(shè) raij表示某一角色 TSCA，αij>0，βij≥0 ，并滿足

定義:當(dāng) βij=0 時(shí)，d(βij，0)=0;當(dāng) βij>0 時(shí)，d(βij，0)=1 。

當(dāng)對(duì)資源的需求發(fā)生變化時(shí)，設(shè)一次協(xié)調(diào)只能有一個(gè)TSCA需要的資源份額發(fā)生變化。設(shè)角色TSCA rain需要的資源發(fā)生變化，αin≠α′in，則:

rain對(duì)空閑資源的承擔(dān)，要么 β′in=βin，保持不變;要么隨需求變化采用公式(5):

對(duì)其它角色TSCA raij，j=1，…，n－1 ，若βin=1 ，則 β′ij=βij=0，否則由式(6)計(jì)算，保持彼此間相對(duì)份額不變:

對(duì)于不承擔(dān)空閑資源的角色TSCA，調(diào)整后依然無(wú)需承擔(dān)空閑資源開(kāi)銷(xiāo)，即如果βij=0，則β′ij=0，j=1，…，n。

2 Agent間協(xié)調(diào)實(shí)現(xiàn)方法

對(duì)策論是研究人類(lèi)社會(huì)交互的最佳數(shù)學(xué)工具，許多學(xué)者應(yīng)用對(duì)策論進(jìn)行多Agent系統(tǒng)中協(xié)調(diào)的研究。這里采用對(duì)策論和分布式Q-學(xué)習(xí)方法相結(jié)合來(lái)實(shí)現(xiàn)Agent間的協(xié)調(diào)。

2.1 基于對(duì)策論的協(xié)調(diào)的實(shí)現(xiàn)

以城市交叉口協(xié)調(diào)為例，TSCA間的對(duì)策協(xié)調(diào)方法可以描述為一個(gè)4元組

2)A為交通實(shí)體所有可能的策略或者行動(dòng)的集合，A=C(m)×S(n)，則A中一共有m×n種執(zhí)行策略組合。

C(m)為調(diào)整策略，m為C中策略個(gè)數(shù)，如取C(m)={紅燈時(shí)間加4 s，紅燈時(shí)間加8 s，紅燈時(shí)間減4 s，紅燈時(shí)間減8 s，保持不變};

設(shè)S(n)為行動(dòng)策略，其值由路口相位決定，n為S中策略個(gè)數(shù)，以四相位路口為例，可以取S(n)={東西直行及右轉(zhuǎn)，南北直行及右轉(zhuǎn)，東西左轉(zhuǎn)，南北左轉(zhuǎn)相位}。

3)U為T(mén)SCA所獲得的效益。經(jīng)常用到的計(jì)算利益的指標(biāo)有車(chē)輛延誤時(shí)間、車(chē)輛停車(chē)次數(shù)等，采用1.2的Q值，Q值大小反映行為策略的優(yōu)劣。

4)I表示每個(gè)TSCA擁有的信息，包括其他TSCA的特征和行動(dòng)策略信息。

此協(xié)調(diào)途徑中，每個(gè)TSCA依據(jù)它所擁有的信息I，在S中選擇合適的策略，通過(guò)不斷的交互，則協(xié)調(diào)策略為納什均衡策略，即:

2.2 對(duì)策論的協(xié)調(diào)方法中效益函數(shù)U的確定

分布式Q強(qiáng)化學(xué)習(xí)算法適合用于TSCA間的協(xié)調(diào)的實(shí)現(xiàn)，具備一定的全局優(yōu)化的特征，收斂速度快，能對(duì)整個(gè)交通網(wǎng)絡(luò)具有較好的優(yōu)化能力。TSCA間對(duì)策過(guò)程中U值大小應(yīng)該能夠反映TSCA選擇不同行為策略所帶來(lái)的效益，而分布式Q學(xué)習(xí)算法中Q值大小反映策略的優(yōu)劣，所以取U=Q。據(jù)英國(guó)運(yùn)輸與道路研究所研究成果，只要圍繞每個(gè)TSCA與其相鄰TSCA協(xié)調(diào)能夠取得一個(gè)接近整體最優(yōu)的效果，那么整個(gè)路網(wǎng)的協(xié)調(diào)效果也是接近“整體最優(yōu)”。同時(shí)為了避免隨著被控路網(wǎng)路口數(shù)量的增加而導(dǎo)致TSCA之間的協(xié)調(diào)過(guò)于頻繁和復(fù)雜，限定每個(gè)TSCA只跟與其相鄰的TSCA進(jìn)行協(xié)調(diào)。因此，這里采用的分布式學(xué)習(xí)算法中每個(gè)TSCA通過(guò)與其相鄰TSCA上次交互信息的歷史學(xué)習(xí)來(lái)獲得其相鄰TSCA的獎(jiǎng)懲函數(shù)值，對(duì)值函數(shù)進(jìn)行更新。分布式Q學(xué)習(xí)中各TSCA利用其相鄰TSCA的獎(jiǎng)懲函數(shù)信息來(lái)更新值函數(shù)［9－12］:

式中:αi∈［0，1］為 TSCAi的學(xué)習(xí)速率;γi∈［0，1］為T(mén)SCAi的折扣因子;Ai為T(mén)SCAi所有可供選擇的行為的集合;si為T(mén)SCAi交通流環(huán)境的當(dāng)前狀態(tài);s′i為T(mén)SCAi交通流環(huán)境的下一個(gè)狀態(tài);n為T(mén)SCAi相鄰的所有其它TSCAi的數(shù)目;Qi(si，ai)為T(mén)SCAi的 Q 值函數(shù);Qi(s′i，a′i)為 TSCAi在下一個(gè)狀態(tài) s′i選擇行為a′i的 Q值函數(shù);ri(si，ai)為T(mén)SCAi的獎(jiǎng)懲函數(shù);rj(sj，aj)為與TSCAi的相鄰的TSCAj的獎(jiǎng)懲函數(shù)值(如果TSCA當(dāng)前決策經(jīng)過(guò)一定的通行時(shí)間之后先前的擁堵得到改善，獎(jiǎng)懲函數(shù)r>0，對(duì)剛才的決策進(jìn)行獎(jiǎng)勵(lì)，TSCA在以后類(lèi)似的交通狀態(tài)下會(huì)選擇這種行為策略;否則進(jìn)行懲罰，將通行權(quán)切換給其它相位);f(i，j)為T(mén)SCAi依賴TSCAj的獎(jiǎng)懲函數(shù)值程度的影響權(quán)值函數(shù)(如下游交叉口的交通壓力大于交叉口的交通壓力，此時(shí)相鄰下游交叉口j的獎(jiǎng)懲值對(duì)交叉口i的影響將增加，從而協(xié)調(diào)本TSCAi的行為決策，從而緩解下游交叉口交通壓力)。

根據(jù)Q值進(jìn)行行為選擇時(shí)，根據(jù)文章1.1對(duì)策論方法求解Nash均衡，作為Q學(xué)習(xí)策略選擇的依據(jù)。

3 在城市交叉口協(xié)調(diào)中的應(yīng)用分析

交叉口各個(gè)路口的到車(chē)狀況事先無(wú)法知道，必須預(yù)測(cè)。以主干道相鄰兩交叉口協(xié)調(diào)為例，兩個(gè)交叉口的信號(hào)均采用4個(gè)相位控制(分別為東西直行及右轉(zhuǎn)，南北直行及右轉(zhuǎn)，東西左轉(zhuǎn)，南北左轉(zhuǎn)相位)，以第2個(gè)交叉口東向入口，第2個(gè)交叉口Agent通過(guò)與第1個(gè)交叉口Agent進(jìn)行協(xié)調(diào)，得到上個(gè)周期第1個(gè)交叉口的到車(chē)狀況。設(shè)分別為第n個(gè)周期、第2個(gè)路口東向左轉(zhuǎn)、直行和右轉(zhuǎn)車(chē)道的預(yù)測(cè)車(chē)數(shù)。sn1ijk為第n個(gè)周期末、第1個(gè)路口、第i個(gè)相位、第k個(gè)方向、第j個(gè)車(chē)道離開(kāi)的車(chē)輛數(shù)，為路口左、直、右的預(yù)測(cè)分流比，于是有:

這里以主干道相鄰兩交叉口協(xié)調(diào)進(jìn)行分析，兩個(gè)交叉口的信號(hào)均采用4個(gè)相位控制(分別為東西直行及右轉(zhuǎn)，南北直行及右轉(zhuǎn)，東西左轉(zhuǎn)，南北左轉(zhuǎn)相位)，路口各個(gè)方向(左，直，右)的預(yù)測(cè)分流比為0.2，0.4，0.4，車(chē)輛的到達(dá)服從隨機(jī)分布，單位時(shí)間內(nèi)路口放行的車(chē)輛數(shù)為2 veh/s，兩交叉口間距為500 m，學(xué)習(xí)算法的學(xué)習(xí)速率為0.1，折扣因子為0.95，飽和流量為1 800 veh/h，最大排隊(duì)長(zhǎng)度為40 veh，各個(gè)相位最大綠燈時(shí)間105 s，最小綠燈時(shí)間15 s，黃燈時(shí)間1 s，全紅時(shí)間1 s，車(chē)輛平均啟動(dòng)時(shí)間2 s。采用本文的有協(xié)調(diào)和無(wú)協(xié)調(diào)方法的計(jì)算結(jié)果如表1。

表1 區(qū)域交叉口協(xié)調(diào)效果對(duì)比Tab.1 The comparison of the coordination results

隨著交通量的增大，總的車(chē)輛平均延誤和平均停車(chē)率逐漸增大，但在交通量相同的時(shí)候，有協(xié)調(diào)方法要比無(wú)協(xié)調(diào)方法明顯降低。當(dāng)流量增加到超過(guò)飽和流量時(shí)候，協(xié)調(diào)方法改善逐漸減弱，則必須在更多的相關(guān)聯(lián)的交叉口之間尋求協(xié)調(diào)。

4 結(jié)論

通過(guò)比較城市交叉口系統(tǒng)和Multi-agent system的相似性，引入交通信號(hào)控制 Agent，分析了Agent的協(xié)調(diào)過(guò)程，建立一種基于Multi-Agent的城市交叉口資源配置動(dòng)態(tài)協(xié)調(diào)模型，應(yīng)用了對(duì)策論作為協(xié)調(diào)實(shí)現(xiàn)途徑，并且以分布式Q強(qiáng)化學(xué)習(xí)中Q值更新作為其效用函數(shù)。通過(guò)對(duì)兩交叉口協(xié)調(diào)實(shí)例分析，車(chē)輛平均延誤和平均停車(chē)率均減少，證明了采用該協(xié)調(diào)方法的有效性。

［1］李凡長(zhǎng).Agent的協(xié)調(diào)組合設(shè)計(jì)模型研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2002，23(2):246 －249.

［2］王立春.多 Agent多問(wèn)題協(xié)商模型［J］.軟件學(xué)報(bào)，2002，13(8):1637－1643.

［3］Burmeister B，Haddadi A，Matylis G.Application of multi－agent systems in traffic and transportation［J］.IEEE Proceedings on Software Engineering，1997，144(1):51 －60.

［4］Susan E L.Issues in multi－ agent design systems［J］.IEEE Expert Intelligent Systems＆ Their Application，1997，12(2):18－26.

［5］歐海濤.基于RMM和貝葉斯學(xué)習(xí)的城市交通多智能體系統(tǒng)［J］.控制與決策，2001，16(3):291 －295.

［6］馬壽峰.一種基于agent協(xié)調(diào)的兩路口交通控制方法［J］.系統(tǒng)工程學(xué)報(bào)，2003，6(3):273 －278.

［7］黃艷國(guó)，許倫輝，鄺先驗(yàn).基于Multi-agent協(xié)調(diào)的區(qū)域交通信號(hào)優(yōu)化控制［J］.江西理工大學(xué)學(xué)報(bào)，2009，30(1):50－52.

［8］石純一.基于 Agent的計(jì)算［M］.北京:清華大學(xué)出版社，2007:102－106.

［9］李英.多Agent系統(tǒng)及其在預(yù)測(cè)與智能交通系統(tǒng)中的應(yīng)用［M］.南昌:華東理工大學(xué)出版社，2004:154－158.

［10］Roozemond D A，van der Veer P.Usability of intelligent agent systems in urban trafficmanagement［J］.Application of Artifical Intelligence in Engineering，1999(7):15 －18.

［11］沙志仁，黃敏.道路交叉口指路標(biāo)志定量分析指標(biāo)及方法研究［J］.重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版，2009，28(5):926－929.

［12］夏新海，唐德華.集裝箱碼頭物流作業(yè)Agent間的重構(gòu)［J］.重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版，2009，28(4):775－779.