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

蔣耀基

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

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

1、智能體的協作關系建立

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

（1）主干道路口節點之間的邏輯關系網絡建立

多智能體系統協作控制的基礎是個體智能體之間的邏輯網絡關系。既然我們將實際道路網中的路口抽象成智能體網絡拓撲結構的節點，那么將路口之間的物理連接關系抽象成網絡拓撲結構的邊，即可形成了路口智能體節點的通信基礎。

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

路口智能體節點之間完成了邏輯關系網絡的建立之后，將具備一定的信息共享能力，為路口智能體節點之間協作，提供數據基礎

（2）信號燈優化問題的求解

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

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

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

2.通過適當的方式從解的全集中選取最優解。

2、通過MDP決策尋找最優解

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

根據MDP的數學模型，結合本系統：初始狀態S即是各自車道的初

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

3、配時優化系統的智能體系統建立

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

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

4、結論

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

參考文獻：

[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] 何顯慈等，交通系統工程.武漢：華中理工大學出版社，1989

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