基于MDP的多智能體交通信號燈控制的設計與研究

蔣耀基

摘要：智能交通系統(tǒng)作為21世紀交通運輸體系的發(fā)展方向，受到了世界各國的廣泛重視，它是解決現(xiàn)代交通擁擠、有效提高道路利用率的有效途徑。通常的智能交通系統(tǒng)未能很高效的解決交通堵塞問題，但多智能體系統(tǒng)是人工智能學科的一個新興熱門研究領(lǐng)域，本文提出了用多智能體系統(tǒng)解決交通主干道信號燈的配飾系統(tǒng)，從而提高了車輛通行效率。

針對路口信號燈配時優(yōu)化問題，本研究提出一種采用多智能體協(xié)作求解問題的分布式方法，并將信號燈配時優(yōu)化問題建模成最優(yōu)約束滿足問題（OCSP）進行求解。這使得單個路口的優(yōu)化運算量大大下降，處理實際交通中的實時動態(tài)情況的能力得到提高，獲得了較為顯著的優(yōu)化效果。由于采用了分布式求解，系統(tǒng)的穩(wěn)定性也得到了保證。

1、智能體的協(xié)作關(guān)系建立

根據(jù)實際道路的特點不難發(fā)現(xiàn)，任意路口的到達車輛是通過該路口的相鄰路口放行所產(chǎn)生的，我們將這些路口的“鄰居”稱為鄰接路口。顯然，如果鄰接路口的放行策略不得當，使得路口車輛的到達率超過了路口的流出率，就會產(chǎn)生擁堵。為了避免路口擁堵現(xiàn)象的產(chǎn)生，路口智能體之間必須進行適當?shù)摹敖涣髋c協(xié)作”，控制各個路口做出合適的信號燈決策。

（1）主干道路口節(jié)點之間的邏輯關(guān)系網(wǎng)絡建立

多智能體系統(tǒng)協(xié)作控制的基礎(chǔ)是個體智能體之間的邏輯網(wǎng)絡關(guān)系。既然我們將實際道路網(wǎng)中的路口抽象成智能體網(wǎng)絡拓撲結(jié)構(gòu)的節(jié)點，那么將路口之間的物理連接關(guān)系抽象成網(wǎng)絡拓撲結(jié)構(gòu)的邊，即可形成了路口智能體節(jié)點的通信基礎(chǔ)。

我們通過示路口節(jié)點智能體之間的邏輯網(wǎng)絡關(guān)系。針對路口智能體網(wǎng)絡中的任一節(jié)點用集合來表示與路口節(jié)點的“鄰居”，其中每一個元素代表一個與邏輯相連的路口節(jié)點，由此不難得出：代表鄰接節(jié)點數(shù)目（即是“邊”數(shù)），當然正常情況下，對于實際道路，與節(jié)點相鄰接的節(jié)點數(shù)一般為3或4個。

路口智能體節(jié)點之間完成了邏輯關(guān)系網(wǎng)絡的建立之后，將具備一定的信息共享能力，為路口智能體節(jié)點之間協(xié)作，提供數(shù)據(jù)基礎(chǔ)

（2）信號燈優(yōu)化問題的求解

根據(jù)之前對于問題的描述及建模可知，我們將整個城市主干道路口設計為一個多智能體系統(tǒng)，每個路口擁有一個智能體節(jié)點，那么，可以將路口的各個車道的放行優(yōu)化控制看作是單個智能體（Agent）占用資源求解問題。根據(jù)交通運行的特點，我們可以將任意路口的各個車道放行優(yōu)化問題應用于最優(yōu)約束滿足問題（DCSP）框架下進行求解。

在本優(yōu)化方案中，我們將最優(yōu)約束滿足問題分成兩個部分：

1.獲得滿足約束條件的解全集；

2.通過適當?shù)姆绞綇慕獾娜羞x取最優(yōu)解。

2、通過MDP決策尋找最優(yōu)解

在完成了問題的建模，獲得了約束滿足的解全集以后，就將進行最重要的環(huán)節(jié)——尋找信號燈配時優(yōu)化問題的最優(yōu)求解。隨著人工智能技術(shù)的不斷發(fā)展，產(chǎn)生了很多尋找最優(yōu)解的模型，較為典型的有 BDI，MDP 等。結(jié)合城市主干道路口信號燈配時優(yōu)化問題的特點，由于問題的初始狀態(tài)S（即是原始車輛數(shù)目），可以通過傳感器實時獲取，同時信號燈的決策行為具有無后效性，即是其只取決于當前狀態(tài)，不受之前狀態(tài)的影響，因此選取 MDP 決策模型來作為尋找最優(yōu)解的方案較為合適。MDP 決策模型（馬爾可夫決策模型）包括：1.初始狀態(tài) S；2.行為方案集合 A；3.效用函數(shù)R（s，a）；4.轉(zhuǎn)移模型T=表示 S 狀態(tài)通過行為方案 A達到了新的狀態(tài)S。

根據(jù)MDP的數(shù)學模型，結(jié)合本系統(tǒng)：初始狀態(tài)S即是各自車道的初

始車輛數(shù)目；系統(tǒng)的行為A即是各自執(zhí)行智能體的動作；轉(zhuǎn)移模型 T=，即是各個執(zhí)行智能體的運算過程；效用函數(shù)R即是根據(jù)執(zhí)行智能體的獨立計算，選取能使下個時刻路口車輛數(shù)目最少的行為。決策時序模擬圖如下圖3-3所示：

3、配時優(yōu)化系統(tǒng)的智能體系統(tǒng)建立

在完成了信號燈配時優(yōu)化系統(tǒng)的工作平臺搭建以后，就將進行配時優(yōu)化系統(tǒng)的本質(zhì)——智能體系統(tǒng)的建立。為了使路口智能體系統(tǒng)之間能夠達成協(xié)作，實現(xiàn)信號燈配時優(yōu)化，本系統(tǒng)將在每個路口節(jié)點上，將設置一個智能體系統(tǒng)，并進行分層，具體劃為：管理智能體與執(zhí)行智能體兩類：

整個系統(tǒng)的運行流程，定時獲取所有鄰接路口的各車道車輛數(shù)目情況；路口管理智能體通過鄰接路口共享的車輛數(shù)目信息，對鄰接路口將要作出的信號燈決策進行預估，并通過預估的結(jié)果，計算獲得自身路口各個車道的輸入車輛數(shù)目；路口各個車道對應的執(zhí)行智能體，均以自身控制的車道信號燈為綠燈為前提，通過交叉沖突規(guī)則，生成各自的交叉沖突列表并比照交叉沖突列表，將產(chǎn)生沖突的車道對應的信號燈設置為紅燈；管理智能體收集所有執(zhí)行智能體各自運算出的下個時刻路口車輛總數(shù)，選取數(shù)目最小的結(jié)果所對應的車道，設置此車道對應信號燈為綠燈，再比照此車道的交叉沖突列表，將導致交叉沖突的車道信號燈設置為紅燈，其余為綠燈，生成信號燈決策結(jié)果。

4、結(jié)論

將城市交通主干道問題進行了抽象描述，并用建立了路口的數(shù)學模型，根據(jù)智能體間的協(xié)作關(guān)系，建立了主干道路口節(jié)點間的邏輯網(wǎng)絡關(guān)系，并通過信號燈的約束滿足問題進行信號燈控制求解，通過 MDP 決策算法進行解的最優(yōu)化處理，在理論上實現(xiàn)了多智能體協(xié)作控制城市主干道信號燈。

參考文獻：

[1]Nationwide Personal Transportation Survey. US Department of Transportation .1980Vergil G.Stover and Frank J.Koepke. Transportation and Land Development.Institute ofTransportation Engineers. Washington DC.1998

[2] 王煒，過秀成，交通工程學.南京：東南大學出版社，2000

[3] 全永，城市交通控制.北京：人民交通出版社，1989

[4] 何顯慈等，交通系統(tǒng)工程.武漢：華中理工大學出版社，1989

[5] Wooldridge M， Dunne P E，On the computational complexity of coalitional resource games.Artilicial Intelligence， 2006， 170：835-87