交叉口Agent 間的博弈學習協調方法

夏新海，許倫輝

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

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

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

1 基于Multi-agent的協調機制

1.1 Agent間的協調過程

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

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

1.2 資源動態協調配置模型

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

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

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

這里以一個TSCA為一個角色，對第i個區域內包含n個關聯的角色TSCA的資源協調配置可以抽象表示為［8］:

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

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

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

當對資源的需求發生變化時，設一次協調只能有一個TSCA需要的資源份額發生變化。設角色TSCA rain需要的資源發生變化，αin≠α′in，則:

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

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

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

2 Agent間協調實現方法

對策論是研究人類社會交互的最佳數學工具，許多學者應用對策論進行多Agent系統中協調的研究。這里采用對策論和分布式Q-學習方法相結合來實現Agent間的協調。

2.1 基于對策論的協調的實現

以城市交叉口協調為例，TSCA間的對策協調方法可以描述為一個4元組

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

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

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

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

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

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

2.2 對策論的協調方法中效益函數U的確定

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

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

根據Q值進行行為選擇時，根據文章1.1對策論方法求解Nash均衡，作為Q學習策略選擇的依據。

3 在城市交叉口協調中的應用分析

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

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

表1 區域交叉口協調效果對比Tab.1 The comparison of the coordination results

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

4 結論

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

［1］李凡長.Agent的協調組合設計模型研究［J］.小型微型計算機系統，2002，23(2):246 －249.

［2］王立春.多 Agent多問題協商模型［J］.軟件學報，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和貝葉斯學習的城市交通多智能體系統［J］.控制與決策，2001，16(3):291 －295.

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

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

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

［9］李英.多Agent系統及其在預測與智能交通系統中的應用［M］.南昌:華東理工大學出版社，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］.重慶交通大學學報:自然科學版，2009，28(5):926－929.

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