夏新海，許倫輝

(1.華南理工大學(xué)土木與交通學(xué)院，廣東廣州510640 2.廣州航海高等?？茖W(xué)校港航管理系，廣東廣州510725)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

［2］王立春.多 Agent多問題協(xié)商模型［J］.軟件學(xué)報，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é)報，2003，6(3):273 －278.

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

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

［9］李英.多Agent系統(tǒng)及其在預(yù)測與智能交通系統(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］沙志仁，黃敏.道路交叉口指路標志定量分析指標及方法研究［J］.重慶交通大學(xué)學(xué)報:自然科學(xué)版，2009，28(5):926－929.

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