基于區域分割的交通仿真死鎖處理算法研究

趙 春，方 敏

(四川大學錦城學院 計算機科學與軟件工程系，四川 成都 611731)

基于區域分割的交通仿真死鎖處理算法研究

趙 春，方 敏

(四川大學錦城學院 計算機科學與軟件工程系，四川 成都 611731)

多智能體交通仿真系統出于減少通信量的目的，在采用虛擬交警對交通區域實施空間分割后，局部區域中的智能體不可能也無法感知處于不斷動態變化的整體交通環境，也就無法適時地疏導交通，以致會引起系統中的某些控制節點出現死鎖，進而會引發全局死鎖效應。為此，采用基于觸發器消息的智能體通信機制，通過在發生死鎖時系統發送專用的死鎖消息給處于死鎖節點處負責調度指揮的智能體，使其在提供的死鎖消息處理函數中采用基于隊列結構的運動物體調度策略來解除死鎖，進而實現死鎖節點處運動物體之間的避讓效果，以解決控制節點處的死鎖現象。仿真實驗結果表明，所提出的死鎖處理算法可有效處理多智能體交通仿真系統中的控制節點死鎖現象，能在最大程度上提高實時交通自動控制的效率和效益。

仿真；智能體；死鎖；調度

1 概 述

基于智能體的計算機仿真技術采用“自底向上”的研究策略，用智能體模擬現實系統中主體的行為和它們彼此間的相互作用，從而模擬出系統的整體性質和演化過程[1]。這樣的研究方法與交通系統微觀仿真研究所遵循的“由部分到整體”的思路基本一致。地面交通仿真需要每個運動物體擁有主動發起從起點到終點的行駛行為，并在行駛過程中能夠感知外部交通環境的變化，及時做出適當反應[2]。智能體代表了現實世界中具有智能性的自治實體[3]。基于智能體的交通仿真方法是采用智能體對交通系統底層中的各組成元素(如運動物體、行人、交通燈、交叉口和路段等)實施仿真建模，并通過這些智能體固有的行為方式和彼此之間的相互影響和作用來模擬整個交通環境[4-6]。多智能體系統主要研究智能體之間的相互協作與競爭[7-8]。智能體通過通信行為彼此聯系和影響。智能體之間的通信方式在很大程度上影響著系統整體的信息復雜度[9]。

采用觸發器消息的智能體通信是一種有效的通信方式。根據通用觸發器系統模型，智能體在完成某一動作后觸發對應的觸發器，發出特定消息。其他智能體都能通過觸發器消息感知到外部環境的變化，并做出反應。集中化的觸發器系統能夠根據觸發器消息的優先級和影響范圍對其進行過濾，從而保證智能體對高優先級消息的優先處理[10]。然而系統在通信過程中的信息量依然很大。選擇給部分智能體賦予類似交警的行為特征，讓其負責控制和調度局部交通，從而實現對整個交通系統空間的區域分割，是一種能夠切實降低整體通信量的有效策略[11]。

但在采用區域分割降低整體通信量的同時，卻會給交通系統帶來附加的影響。即將會導致單個智能體對于整體交通環境的不可感知，以致無法根據道路的實時使用狀況做出適當的反應來調整自己的行駛路線，從而出現死鎖現象，即多個運動物體在同一道路中出現阻塞的情況。

區域分割策略導致了這種局部死鎖現象的形成。結合典型的控制節點死鎖情況，提出采用隊列結構來分別表示駛入車輛與駛出車輛集合的方法，從而重新定義了負責指揮交通的智能體結構，設計出了死鎖的判定算法；并通過對常用避讓算法的對比分析，提出了一種新的死鎖處理算法。該算法基于觸發器的智能體通信機制，創建了專用的死鎖消息和消息處理函數；發生局部節點死鎖時，系統發送消息給節點處負責控制調度的智能體，使其通過消息處理函數對經過該節點的運動物體實施有效調度，以解除死鎖，從而達到了避免因局部死鎖而引發全局死鎖的效果。

2 交通仿真中的死鎖

對于地面交通的計算機仿真，交通環境可以看作若干個離散時間點上的環境狀態的集合：E={et0,et1,…,etm}。運動物體需要在每個時間點上感知當前的環境狀態，并做出適當反應。如果將運動物體所能做出的反應用集合C表示，則運動物體(MO)就可以表示成函數：MO:E→C。要為函數MO提供輸入，就需要運動物體在每個離散時刻都要感知到外部環境，獲得在各個時刻的環境狀態。定義S(MOi,t)表示第i個運動物體在時刻t的狀態信息，則在一個包含n個運動物體的交通環境中，第k個運動物體在t時刻所需要感知的外部環境為：et=。如果認為每個運動物體在每個離散時刻的狀態信息為一個單位的信息量，則在每個離散時刻由運動智能體構成的多智能體系統中所需傳輸的信息總量為n×(n-1),即信息量為O(n2)。為降低每個離散時刻需要傳遞的信息量，可以通過給部分智能體賦予類似交警的行為特征，讓其負責指揮和調度局部交通，從而對整個交通區域進行分割，以分化需要傳輸的信息量[12-13]。

在整體的交通空間被分割成為若干小的區域以后，運動智能體不再需要感知其他運動物體，而是僅僅只需要感知負責指揮其歸屬區域的智能體所發出的指令[14]。因此，運動物體可以重新表示為MO:Order→AC，Order表示指揮智能體所發出的指令集合。如果把每個運動物體在每個離散時刻的狀態信息和每個指揮智能體所發出的指令都視為一個單位的信息量，則在一個包含n個運動物體的交通系統中，每個離散時刻所需傳輸的信息量可降低為O(n)。

區域分割策略雖然能夠有效降低每個離散時刻需要傳遞的信息量，但這種空間分割策略卻造成了每個參與交通的智能體只能對自己所處的局部環境進行感知，而不能獲得整個交通環境的全部信息。因此，整個環境對于單個智能體是不可觀察的。而車輛的運動、避讓和速度變化等動作在時刻改變著交通環境的狀況。由于環境的不可觀察性和動態性，造成交通系統在運行過程中會出現死鎖現象。這種死鎖現象的顯著特征表現為道路上的某個運動物體會一直被要求重新尋路，或者某個路口的各條道路上的運動物體因為互為障礙而出現阻塞。

交通仿真系統中的死鎖問題雖然是一個全系統的死鎖問題，但是往往是由于系統中某個控制節點的死鎖引起的全局效應。對于一個控制節點，最常見的死鎖情況如圖1所示。

圖1 一個控制VP處形成的死鎖現象

MO1、MO2、MO3、MO4的預定路線分別為r1(v1,v0,v2),r2(v2,v0,v1),r3(v3,v0,v4)和r4(v4,v0,v3)。位于v0處的負責調度指揮的智能體(VP)所管轄的四條道路上都有運動物體駛入。此時VP將會檢查每一個將要進入的運動物體是否能按照預定路線通行；如果不能，則使用空閑道路來實施避讓。由于每條道路最多只允許一個運動物體通行，且VP管轄下的四條道路都被駛入的運動物體占用，因此VP無法使用空閑道路對任何一個運動物體實施避讓，從而造成死鎖。

在交通模型中，每一個負責指揮交通的智能體VP都擁有結構體變量roadRecord，它保存了該VP管轄下所有道路的相關信息：

structroadRecord

{

intnodeId; //道路遠端節點的ID

pointnodePos; //遠端節點的坐標

doubleroadWidth; //道路寬度

doubleroadLength; //道路長度

introadType; //道路類型

boolsingleWay; //該道路是否分時單行

moListinQueue; //駛入的車輛隊列

moListoutQueue; //駛離的車輛隊列

//關于該條道路的地圖信息

vectorvpath;

}

moList采用隊列結構，記錄了道路的駛入與駛離車輛信息，定義如下：

structmoList

{

intmoNum; //隊列中車輛的數量

//隊列中車輛的最大寬度

doublemaxWidth;

//隊列中的車輛記錄

std::vectormos;

}

可以注意到，這種死鎖現象的一個重要特點就是對于VP而言，它管轄下的所有道路的道路記錄roadRecord中的結構體InQueue(駛入的車輛隊列)都不為空，沒有一條道路上的OutQueue(駛離的車輛隊列)是可用的。需要說明的是，考慮到每條道路最多只允許有一個運動物體通行，因此每條道路的InQueue隊列與OutQueue隊列不能同時可用。為處理死鎖現象，可首先根據這種死鎖現象的特征來設計算法，判定死鎖是否產生。

算法1：判定死鎖

begin

lock←true//初始化死鎖標志

//獲取VP控制的道路數量

length←vp.roads.length

//遍歷VP控制的所有道路

whilelength>0

//判斷道路的駛入隊列是否為空

ifvp.roads[length].inQueue=null

//道路駛入隊列為空，解除死鎖標志

lock←false

break

else

length←length-1

end

3 死鎖解除算法

在基于觸發器消息的多智能體交通仿真系統中，智能體對外部環境的獲得，由主動感知變為被動感知。只有當外部環境發生變化時，智能體才會被觸發器消息通知。而集中化消息觸發器所具有的分發機制，使得環境信息的傳播由整個區域內的廣播變為點到點的傳播。

如果出現道路阻塞，運動智能體一般可以根據實際情況采取以下兩種避讓算法中的一種來處理死鎖問題。

(1)假定運動物體MO1從節點ni到節點nj，途經控制節點nk，則行駛路徑可表示為r1(ni,nk,nj)；運動物體MO2由節點nj到節點nh，同樣途經控制節點nk，則行駛路徑可表示為r2(nj,nk,nh)。MO1在t1時刻到達nk節點，MO2在t2時刻到達nk節點。設W(x)表示x的寬度，如果t1

(2)運動智能體MO1和MO2的行駛路徑分別為r1和r2。如果r1和r2的方向相逆、寬度相同，且道路寬度小于MO1和MO2的寬度之和，即(r1=-r2)Λ(W(r1)=W(r2)<(W(MO1)+W(MO2)))，則MO1和MO2必然相撞。因此MO1或MO2必須重新選路，以避免相撞。

由于每條道路最多只允許有一個運動物體通行，因此在一條道路上不可能出現多個運動物體同時逆向行駛的現象。在這種情況下，上述兩種在多智能體交通仿真系統中常用的避讓算法都是無效的。為此，可以創建一個專用的死鎖消息和消息處理函數。在產生死鎖時，系統對位于產生死鎖節點位置處的VP(位于v0處)發送一個死鎖消息，然后由VP來負責調度運動物體，從而解除死鎖。對應的消息處理函數的邏輯主要包括：

(1)VP給管轄內所有道路InQueue隊列中的MO(運動智能體)發送停止消息，MO全部停止運動。

(2)VP獲取并判定所有MO的優先級(假定MO1、MO2、MO3、MO4的優先級依次降低)，發送消息讓優先級最高的MO1駛入，在距離v0較近處停止等待。

(3)VP在MO3與MO4之間選擇優先級較高的MO3，將其暫時地從道路(v0,v3)的InQueue隊列中刪除。

(4)MO2駛向v0，在離v0較近處轉向v3；并將MO2從道路(v0,v3)的OutQueue隊列中刪除，進入道路(v0,v3)的InQueue隊列。

(5)恢復之前暫時刪除的MO3到道路(v0,v3)的InQueue隊列中。

(6)MO1繼續駛入，順利通過v0。

此時死鎖解除，剩下的其他運動物體則可以在VP的調度下利用MO1通過v0以后空閑出來的道路實施避讓，從而均順利通過v0。

算法2：解除死鎖

begin

//停止所有運動物體的移動

callstopMOS()

//判定VP控制的所有道路的駛入隊列是否為空

whilevp.roads.inQueue<>null

//選擇優先級高的運動物體駛向VP

callhpMODriveToVP()

//清除優先級高的運動物體通過VP的阻礙

callclearObstruction()

//讓優先級高的運動物體通過VP

callhpMOPassVP()

end

4 算法效果

圖2顯示處于v0處的VP發現了自己處于特殊的死鎖狀態。這時它向所有行駛在自己管轄內的四條道路上的車輛發送停止駛入消息，四輛車停止了行駛。圖3顯示v0處的VP讓優先級最高的車輛MO1駛入，并在到達后停止。

圖2 四輛車同時駛向v0形成死鎖

圖3 優先級最高的MO1最先駛向v0

圖4表示v0處的VP將車輛MO3從道路(v0,v3)的InQueue隊列中暫時刪除(這種刪除不影響車輛在地圖上的顯示，只是車輛暫時不在其道路的InQueue隊列中)，并且同時給車輛MO2一條特別的消息，讓其駛向(v0,v3)并且在距離v0較近處掉頭；然后將MO2加入到(v0,v3)道路的InQueue隊列中；之后恢復MO3到(v0,v3)道路的InQueue隊列中。至此死鎖解除，v0處VP的消息處理函數結束。處于v0控制下的四輛車可以利用簡單的避讓算法順利通過v0。

圖4 MO2駛入道路(v0,v3)并掉頭

圖5表示在阻礙被清除的情況下，v0處的VP恢復車輛MO1的運動狀態，車輛通過v0進入了(v0,v2)駛向v2。在此之后，車輛MO2駛過v0進入(v0,v1)；MO4進入道路(v0,v1)實施避讓，MO3通過v0；最后MO4通過v0。至此，四輛車全部通過了控制點v0。

圖5 MO1通過v0

在死鎖處理過程中，還可能會出現一些更為復雜的情況。比如在某個VP管轄的四條道路中，其中有一條道路之前是空閑的，其他三路的車輛在接近控制點v0時，突然在先前空閑的道路上出現一輛車向v0點駛來。這種情況說明位于v0處的VP在消息處理函數中，首先應該計算需要臨時駛入車輛并掉頭的道路是否滿足駛入車輛的要求；如果發現不滿足，VP可以命令在這些道路上的車輛先都向遠離VP的方向倒退最遠距離，以保證如上例中的車輛MO2能夠臨時進入道路(v0,v3)。

如果發現用來暫時駛入的道路比較短，不能滿足兩輛車同時停下(其中一輛還要掉頭，而調頭比停止需要占用更大的道路長度)，或者需要讓路的道路，如上例中的(v0,v3)線上駛入的車輛太多，需要做的處理太多時，處理函數可以采用一種簡單的處理辦法。比如發消息讓(v0,v2)道路上所有InQueue隊列中的車輛調頭，讓它們在自動尋路系統的支持下重新尋路。而其他道路的車輛則在系統的調度下依次通過v0處的VP。

5 結束語

針對交通仿真系統中可能出現的死鎖現象，通過進行多方位分析，提出了建設性的解決思路，并優化設計算法，在基于系統結構可嵌入的原則下，實現了一種新的死鎖處理算法，使得交通仿真系統能夠避免大多數的死鎖情況發生。

交通的實際情況總是千變萬化。對于交通仿真系統來說，所提出的算法可以根據出現的新情況新問題研究相應的對策，最大程度上保證交通管理在不需要用戶干預的情況下，自動、高效地完成交通的自動控制任務。

[1]RoozemondDA.Usingintelligentagentsforpro-active,real-timeurbanintersectioncontrol[J].EuropeanJournalofOperationalResearch,2001,131(2):293-301.

[2]Chaib-DraaB,MoulinB,MandiauR,etal.Trendsindistributedartificialintelligence[J].ArtificialIntelligenceReview,1992,6(1):35-66.

[3] 張飛舟,曹學軍,孫 敏.基于多智能體的城市交通集成控制系統設計[J].北京大學學報:自然科學版,2008,44(2):289-292.

[4] 郭建鋼,伍雄斌.多智能體技術在交通系統協調控制中的應用[J].華東交通大學學報,2005,22(6):38-41.

[5] 吳繼偉,楊定鵬,蕭蘊詩.多智能體協作方法及其應用研究[J].控制與決策,2004,19(2):216-218.

[6]AlmejalliK，DahalK，HossainA.Anintelligentmulti-agentapproachforroadtrafficmanagementsystems[C]//Controlapplications,intelligentcontrol.[s.l.]:IEEE,2009:825-830.

[7] 何 濤,白振興.多智能體系統設計的關鍵技術研究[J].現代電子技術,2006,29(14):31-34.

[8]HirankittiV,KrohkaeJ,HoggerC.Amulti-agentapproachforintelligenttraffic-lightcontrol[J].WorldCongressonEngineering,2007,79(3):116-121.

[9] 王龍飛,陳 紅,李 揚,等.多智能體在城市交通系統中應用現狀綜述[J].計算機系統應用,2010,19(1):198-203.

[10] 史 樂,李 輝,原江波.基于消息通信的多智能體系統的應用[J].計算機應用,2008,28(2):531-534.

[11] 賀 雷,劉正熙,毌攀良.基于通用觸發器系統的地面交通仿真[J].計算機應用,2007,27(11):2623-2625.

[12] 吳 越,周學農.智能協作技術在交通管理中的應用[J].系統工程,2001,19(1):52-55.

[13] 歐海濤,張衛東,張文淵,等.基于多智能體技術的城市智能交通控制系統[J].電子學報,2000,28(12):52-55.

[14] 李振龍,趙曉華.基于Agent的區域交通信號協調控制[J].武漢理工大學學報:交通科學與工程版,2008,32(1):130-133.

Investigation on Deadlock Resolution Algorithm for Traffic Simulation with Region Segmentation

ZHAO Chun,FANG Min

(Department of Computer Science and Software,Jincheng College of Sichuan University,Chengdu 611731,China)

After the whole traffic region is partitioned by the virtual traffic police for the purpose of reducing traffic in the multi-agent traffic simulation system,and the traffic cannot be directed in time because the dynamic overall traffic environment is unobserved for those agents in local region.For this reason,those regional deadlocks will be triggered in some control nodes,which result in the global deadlock effect.To solve this problem,using the communication mechanism based on trigger message,the system sends a specialized deadlock message to the agent responsible for the traffic command of the control node when deadlock occurred.By using the method of dispatching moving objects based on queue structure in the message processing function for deadlock resolution,avoidance between the moving objects can be achieved to solve the problem of the deadlock.The simulation results show that the proposed algorithm can effectively settle those deadlocks at the control nodes in the multi-agent traffic simulation system,and farthest promote the efficiency and benefit of dynamic traffic auto-control.

simulation；agent；deadlock；dispatching

2016-05-26

2016-09-08 網絡出版時間：2017-03-07

四川省應用基礎項目(2010JY0023)

趙 春(1978-)，男，碩士，副教授，研究方向為數據庫技術、互聯網應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0921.046.html

TP391

A

1673-629X(2017)05-0025-05

10.3969/j.issn.1673-629X.2017.05.006