赵 春，方 敏

(四川大学锦城学院 计算机科学与软件工程系，四川 成都 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