趙 春，方 敏

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

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

趙 春，方 敏

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

多智能體交通仿真系統(tǒng)出于減少通信量的目的，在采用虛擬交警對交通區(qū)域?qū)嵤┛臻g分割后，局部區(qū)域中的智能體不可能也無法感知處于不斷動態(tài)變化的整體交通環(huán)境，也就無法適時地疏導(dǎo)交通，以致會引起系統(tǒng)中的某些控制節(jié)點出現(xiàn)死鎖，進而會引發(fā)全局死鎖效應(yīng)。為此，采用基于觸發(fā)器消息的智能體通信機制，通過在發(fā)生死鎖時系統(tǒng)發(fā)送專用的死鎖消息給處于死鎖節(jié)點處負責(zé)調(diào)度指揮的智能體，使其在提供的死鎖消息處理函數(shù)中采用基于隊列結(jié)構(gòu)的運動物體調(diào)度策略來解除死鎖，進而實現(xiàn)死鎖節(jié)點處運動物體之間的避讓效果，以解決控制節(jié)點處的死鎖現(xiàn)象。仿真實驗結(jié)果表明，所提出的死鎖處理算法可有效處理多智能體交通仿真系統(tǒng)中的控制節(jié)點死鎖現(xiàn)象，能在最大程度上提高實時交通自動控制的效率和效益。

仿真；智能體；死鎖；調(diào)度

1 概 述

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

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

但在采用區(qū)域分割降低整體通信量的同時，卻會給交通系統(tǒng)帶來附加的影響。即將會導(dǎo)致單個智能體對于整體交通環(huán)境的不可感知，以致無法根據(jù)道路的實時使用狀況做出適當(dāng)?shù)姆磻?yīng)來調(diào)整自己的行駛路線，從而出現(xiàn)死鎖現(xiàn)象，即多個運動物體在同一道路中出現(xiàn)阻塞的情況。

區(qū)域分割策略導(dǎo)致了這種局部死鎖現(xiàn)象的形成。結(jié)合典型的控制節(jié)點死鎖情況，提出采用隊列結(jié)構(gòu)來分別表示駛?cè)胲囕v與駛出車輛集合的方法，從而重新定義了負責(zé)指揮交通的智能體結(jié)構(gòu)，設(shè)計出了死鎖的判定算法；并通過對常用避讓算法的對比分析，提出了一種新的死鎖處理算法。該算法基于觸發(fā)器的智能體通信機制，創(chuàng)建了專用的死鎖消息和消息處理函數(shù)；發(fā)生局部節(jié)點死鎖時，系統(tǒng)發(fā)送消息給節(jié)點處負責(zé)控制調(diào)度的智能體，使其通過消息處理函數(shù)對經(jīng)過該節(jié)點的運動物體實施有效調(diào)度，以解除死鎖，從而達到了避免因局部死鎖而引發(fā)全局死鎖的效果。

2 交通仿真中的死鎖

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

在整體的交通空間被分割成為若干小的區(qū)域以后，運動智能體不再需要感知其他運動物體，而是僅僅只需要感知負責(zé)指揮其歸屬區(qū)域的智能體所發(fā)出的指令[14]。因此，運動物體可以重新表示為MO:Order→AC，Order表示指揮智能體所發(fā)出的指令集合。如果把每個運動物體在每個離散時刻的狀態(tài)信息和每個指揮智能體所發(fā)出的指令都視為一個單位的信息量，則在一個包含n個運動物體的交通系統(tǒng)中，每個離散時刻所需傳輸?shù)男畔⒘靠山档蜑镺(n)。

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

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

圖1 一個控制VP處形成的死鎖現(xiàn)象

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

在交通模型中，每一個負責(zé)指揮交通的智能體VP都擁有結(jié)構(gòu)體變量roadRecord，它保存了該VP管轄下所有道路的相關(guān)信息：

structroadRecord

{

intnodeId; //道路遠端節(jié)點的ID

pointnodePos; //遠端節(jié)點的坐標(biāo)

doubleroadWidth; //道路寬度

doubleroadLength; //道路長度

introadType; //道路類型

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

moListinQueue; //駛?cè)氲能囕v隊列

moListoutQueue; //駛離的車輛隊列

//關(guān)于該條道路的地圖信息

vectorvpath;

}

moList采用隊列結(jié)構(gòu)，記錄了道路的駛?cè)肱c駛離車輛信息，定義如下：

structmoList

{

intmoNum; //隊列中車輛的數(shù)量

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

doublemaxWidth;

//隊列中的車輛記錄

std::vectormos;

}

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

算法1：判定死鎖

begin

lock←true//初始化死鎖標(biāo)志

//獲取VP控制的道路數(shù)量

length←vp.roads.length

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

whilelength>0

//判斷道路的駛?cè)腙犃惺欠駷榭?/p>

ifvp.roads[length].inQueue=null

//道路駛?cè)腙犃袨榭?，解除死鎖標(biāo)志

lock←false

break

else

length←length-1

end

3 死鎖解除算法

在基于觸發(fā)器消息的多智能體交通仿真系統(tǒng)中，智能體對外部環(huán)境的獲得，由主動感知變?yōu)楸粍痈兄Ｖ挥挟?dāng)外部環(huán)境發(fā)生變化時，智能體才會被觸發(fā)器消息通知。而集中化消息觸發(fā)器所具有的分發(fā)機制，使得環(huán)境信息的傳播由整個區(qū)域內(nèi)的廣播變?yōu)辄c到點的傳播。

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

(1)假定運動物體MO1從節(jié)點ni到節(jié)點nj，途經(jīng)控制節(jié)點nk，則行駛路徑可表示為r1(ni,nk,nj)；運動物體MO2由節(jié)點nj到節(jié)點nh，同樣途經(jīng)控制節(jié)點nk，則行駛路徑可表示為r2(nj,nk,nh)。MO1在t1時刻到達nk節(jié)點，MO2在t2時刻到達nk節(jié)點。設(shè)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必須重新選路，以避免相撞。

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

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

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

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

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

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

(6)MO1繼續(xù)駛?cè)?，順利通過v0。

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

算法2：解除死鎖

begin

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

callstopMOS()

//判定VP控制的所有道路的駛?cè)腙犃惺欠駷榭?/p>

whilevp.roads.inQueue<>null

//選擇優(yōu)先級高的運動物體駛向VP

callhpMODriveToVP()

//清除優(yōu)先級高的運動物體通過VP的阻礙

callclearObstruction()

//讓優(yōu)先級高的運動物體通過VP

callhpMOPassVP()

end

4 算法效果

圖2顯示處于v0處的VP發(fā)現(xiàn)了自己處于特殊的死鎖狀態(tài)。這時它向所有行駛在自己管轄內(nèi)的四條道路上的車輛發(fā)送停止駛?cè)胂?，四輛車停止了行駛。圖3顯示v0處的VP讓優(yōu)先級最高的車輛MO1駛?cè)?，并在到達后停止。

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

圖3 優(yōu)先級最高的MO1最先駛向v0

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

圖4 MO2駛?cè)氲缆?v0,v3)并掉頭

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

圖5 MO1通過v0

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

如果發(fā)現(xiàn)用來暫時駛?cè)氲牡缆繁容^短，不能滿足兩輛車同時停下(其中一輛還要掉頭，而調(diào)頭比停止需要占用更大的道路長度)，或者需要讓路的道路，如上例中的(v0,v3)線上駛?cè)氲能囕v太多，需要做的處理太多時，處理函數(shù)可以采用一種簡單的處理辦法。比如發(fā)消息讓(v0,v2)道路上所有InQueue隊列中的車輛調(diào)頭，讓它們在自動尋路系統(tǒng)的支持下重新尋路。而其他道路的車輛則在系統(tǒng)的調(diào)度下依次通過v0處的VP。

5 結(jié)束語

針對交通仿真系統(tǒng)中可能出現(xiàn)的死鎖現(xiàn)象，通過進行多方位分析，提出了建設(shè)性的解決思路，并優(yōu)化設(shè)計算法，在基于系統(tǒng)結(jié)構(gòu)可嵌入的原則下，實現(xiàn)了一種新的死鎖處理算法，使得交通仿真系統(tǒng)能夠避免大多數(shù)的死鎖情況發(fā)生。

交通的實際情況總是千變?nèi)f化。對于交通仿真系統(tǒng)來說，所提出的算法可以根據(jù)出現(xiàn)的新情況新問題研究相應(yīng)的對策，最大程度上保證交通管理在不需要用戶干預(yù)的情況下，自動、高效地完成交通的自動控制任務(wù)。

[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] 張飛舟,曹學(xué)軍,孫 敏.基于多智能體的城市交通集成控制系統(tǒng)設(shè)計[J].北京大學(xué)學(xué)報:自然科學(xué)版,2008,44(2):289-292.

[4] 郭建鋼,伍雄斌.多智能體技術(shù)在交通系統(tǒng)協(xié)調(diào)控制中的應(yīng)用[J].華東交通大學(xué)學(xué)報,2005,22(6):38-41.

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

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

[7] 何 濤,白振興.多智能體系統(tǒng)設(shè)計的關(guān)鍵技術(shù)研究[J].現(xiàn)代電子技術(shù),2006,29(14):31-34.

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

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

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

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

[12] 吳 越,周學(xué)農(nóng).智能協(xié)作技術(shù)在交通管理中的應(yīng)用[J].系統(tǒng)工程,2001,19(1):52-55.

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

[14] 李振龍,趙曉華.基于Agent的區(qū)域交通信號協(xié)調(diào)控制[J].武漢理工大學(xué)學(xué)報:交通科學(xué)與工程版,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 網(wǎng)絡(luò)出版時間：2017-03-07

四川省應(yīng)用基礎(chǔ)項目(2010JY0023)

趙 春(1978-)，男，碩士，副教授，研究方向為數(shù)據(jù)庫技術(shù)、互聯(lián)網(wǎng)應(yīng)用。

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