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

趙 春，方 敏

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

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

趙 春，方 敏

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

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

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

1 概 述

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

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

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

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

2 交通仿真中的死鎖

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

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

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

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

圖1 一個(gè)控制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處的負(fù)責(zé)調(diào)度指揮的智能體(VP)所管轄的四條道路上都有運(yùn)動(dòng)物體駛?cè)搿４藭r(shí)VP將會(huì)檢查每一個(gè)將要進(jìn)入的運(yùn)動(dòng)物體是否能按照預(yù)定路線通行；如果不能，則使用空閑道路來(lái)實(shí)施避讓。由于每條道路最多只允許一個(gè)運(yùn)動(dòng)物體通行，且VP管轄下的四條道路都被駛?cè)氲倪\(yùn)動(dòng)物體占用，因此VP無(wú)法使用空閑道路對(duì)任何一個(gè)運(yùn)動(dòng)物體實(shí)施避讓，從而造成死鎖。

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

structroadRecord

{

intnodeId; //道路遠(yuǎn)端節(jié)點(diǎn)的ID

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

doubleroadWidth; //道路寬度

doubleroadLength; //道路長(zhǎng)度

introadType; //道路類型

boolsingleWay; //該道路是否分時(shí)單行

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

moListoutQueue; //駛離的車輛隊(duì)列

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

vectorvpath;

}

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

structmoList

{

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

//隊(duì)列中車輛的最大寬度

doublemaxWidth;

//隊(duì)列中的車輛記錄

std::vectormos;

}

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

算法1：判定死鎖

begin

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

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

length←vp.roads.length

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

whilelength>0

//判斷道路的駛?cè)腙?duì)列是否為空

ifvp.roads[length].inQueue=null

//道路駛?cè)腙?duì)列為空，解除死鎖標(biāo)志

lock←false

break

else

length←length-1

end

3 死鎖解除算法

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

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

(1)假定運(yùn)動(dòng)物體MO1從節(jié)點(diǎn)ni到節(jié)點(diǎn)nj，途經(jīng)控制節(jié)點(diǎn)nk，則行駛路徑可表示為r1(ni,nk,nj)；運(yùn)動(dòng)物體MO2由節(jié)點(diǎn)nj到節(jié)點(diǎn)nh，同樣途經(jīng)控制節(jié)點(diǎn)nk，則行駛路徑可表示為r2(nj,nk,nh)。MO1在t1時(shí)刻到達(dá)nk節(jié)點(diǎn)，MO2在t2時(shí)刻到達(dá)nk節(jié)點(diǎn)。設(shè)W(x)表示x的寬度，如果t1

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

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

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

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

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

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

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

(6)MO1繼續(xù)駛?cè)耄樌ㄟ^(guò)v0。

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

算法2：解除死鎖

begin

//停止所有運(yùn)動(dòng)物體的移動(dòng)

callstopMOS()

//判定VP控制的所有道路的駛?cè)腙?duì)列是否為空

whilevp.roads.inQueue<>null

//選擇優(yōu)先級(jí)高的運(yùn)動(dòng)物體駛向VP

callhpMODriveToVP()

//清除優(yōu)先級(jí)高的運(yùn)動(dòng)物體通過(guò)VP的阻礙

callclearObstruction()

//讓優(yōu)先級(jí)高的運(yùn)動(dòng)物體通過(guò)VP

callhpMOPassVP()

end

4 算法效果

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

圖2 四輛車同時(shí)駛向v0形成死鎖

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

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

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

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

圖5 MO1通過(guò)v0

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

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

5 結(jié)束語(yǔ)

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

交通的實(shí)際情況總是千變?nèi)f化。對(duì)于交通仿真系統(tǒng)來(lái)說(shuō)，所提出的算法可以根據(jù)出現(xiàn)的新情況新問(wèn)題研究相應(yīng)的對(duì)策，最大程度上保證交通管理在不需要用戶干預(yù)的情況下，自動(dòng)、高效地完成交通的自動(dòng)控制任務(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ì)[J].北京大學(xué)學(xué)報(bào):自然科學(xué)版,2008,44(2):289-292.

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

[5] 吳繼偉,楊定鵬,蕭蘊(yùn)詩(shī).多智能體協(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è)計(jì)的關(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] 王龍飛,陳 紅,李 揚(yáng),等.多智能體在城市交通系統(tǒng)中應(yīng)用現(xiàn)狀綜述[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2010,19(1):198-203.

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

[11] 賀 雷,劉正熙,毌攀良.基于通用觸發(fā)器系統(tǒng)的地面交通仿真[J].計(jì)算機(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é)報(bào),2000,28(12):52-55.

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

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

趙 春(1978-)，男，碩士，副教授，研究方向?yàn)閿?shù)據(jù)庫(kù)技術(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