分布式环境下基于多Agent的人群模拟的研究与应用

魏超,余腊生

（中南大学信息科学与工程学院,湖南长沙410083）

0 引言

一些大型公共设施的安全危机事件,如：恐怖袭击、重大火灾、公众聚集场所人员踩踏、危险化学制品泄漏爆炸、重大道路交通事故等,如果处置不当,不仅会带来巨大的人员伤亡和经济损失,还会给国家造成重大的负面政治影响。我国每年因公共安全问题造成的GDP损失高达百分之六,夺去二十万人的生命[1][2]。当前最通用的方法是模拟人群逃亡的过程,并对模拟的结果对公共设施做相应的修改。

基于agent的分布式人群模拟,相对于传统的人群模拟技术有很大的改进,具有更好的灵活性与可扩充性。它克服了机器性对人群数量的限制。

1 相关工作

在虚拟仿真研究领域,目前还没有找到非常有效的模型来模拟人群运动。我们知道,传统的模型存在很多限制。许多研究者在最大人群模拟数量与行为的多样性之间找平衡点。例如,AvneeshSud和他的团队提出了在复杂动态环境下,实时路径规划的新方法。他们引进了一种新的数据结构叫做多agent导航图,该图由第一序列与第二序列的Voronoi图构成[3][4]。YongqingYe与QinggeJi在2007年提出了基于大规模人群分层路径规划的非实时算法[5]。此外,Avneesh Sud提出了在复杂动态环境下,通过设置适当的路标,大规模自治的Agent同时执行全局路径规划的模型[6]。另外,MubbasirKapadia提出了操控力行为的交互式框架,在不同的时间步长内,计算出周围Agent与环境的变化,以利益驱动agent的行为[7]。还有,Hao Jiang和他的团队提出了在复杂环境下语义模型的方案[8],RussellGayle和他的团队提出了一个基于C/S模型的网络拓扑结构[9][10]。

本论文中,我们将介绍一个基于多agent的分布式人群模拟系统,这个适用于复杂动态环境。我们便用了可扩展性系统结构与高效的搜索算法,因此,可以模拟大量的人群。

2 人群疏散仿真系统的框架

基于多Agent的人群疏散仿真系统( Multi-Agent Simulation System,MASS)的体系结构如图 2-1所示。该系统由六个基本模块组成：几何图形引擎,人员生成器,全局数据库,人群疏散模拟引擎,事件注册器及可视化工具。

图2 -1疏散计算框架

(1)几何图形引擎用来构造虚拟的物理环境(如建筑物或火车站等)。障碍物、出口、空间、楼层布局、出口指示牌等环境信息能很方便地用CAD工具(如AutoCAD,ADT等)定义。

(2)人员生成器动态地生成虚拟Agent来代表疏散人员,人员生成器根据人类特征(如年龄、身高、体重、性别等)及建筑物的类型(如医院、办公楼、车站、体育场等)生成不同类型的群体。随建筑物类型不同,人员的组成及人员的行为也是有很大不同的。这个模型能够很好地根据不同的建筑物类型生存不同的人员。

(3)全局数据库维护所有有关的地理环境与模拟过程中的Agent的信息。这些信息包括状态参数(如精神紧张程度、行为层次、所处位置等)。该数据库还用于支持个体间的相互作用和对环境做出反应。

(4)事件记录器用于捕获数据和回放模拟过程。模拟结果可被记录下来做进一步的分析,例如,为了获得疏散模式和统计资料。捕获的事件也可以用来比较已知的和存档的方案。

(5)可视化工具对于显示仿真结果非常重要。在我们系统中,采用了OGRE来实现的,当接收到Agent的位置,然后动态生成并显示2D/3D的视觉图像。

(6)人群仿真引擎是多Agent仿真系统的核心模块。按照行为模式和分类规则,人员生成器在生成一个Agent的时候,给每个Agent分配特有的行为模型。个体行为模式由三个子系统组成——感知系统、行为系统、执行系统,我们将会在后面的章节做详细讨论。人群的模拟引擎的基本算法步骤如图2-2所示。

图2 -2人群仿真引擎的基本步骤

这种设计使得整个系统高效模块化,能非常方便地加入新的行为模式和规则,以便今后进一步研究动态人群行为。

3 基于Agent模型的行为仿真

在这个MASS系统中,每个人员都被表示为一个自治的Agent模型,Agent可以通过感知系统与虚拟环境及其它Agent相互交互。由于人群中的个体在行为上有很大差别,因此我们把人群归为几个类型,如老人、小孩,男人、女人等,并对这些类型建立不同的Agent行为模型。 Agent的行为模型主要由三个子系统组成：感知系统,行为系统,运动系统；这些子系统实现了Agent感知环境的状态信息,行为模型制定决策等功能(如图3-1)。涂晓媛在模拟人工鱼的行为采用了类似的模型[10]。

图3 -1自治Agent的三大系统

3.1 感知系统

每个Agent的感知系统由一个或多个感知器构成。一个感知器又包含三个要素：输入参数,感官机制,以及输出参数。输入参数是由感知器探测到的一些有关环境状态的信息。感官机制是一组处理数据的算法,它的输入参数为感知到的环境状态信息,并把输出结果交给行为系统。

感知系统参数含有视觉、听觉、情绪状态,以及其它一些影响Agent在疏散过程中做出决策的参数。目前,在MASS中应用了一套计算 Agent虚拟视觉的方法。虚拟视觉的输入参数包括出口、集结点、其他Agent,以及障碍物等。对于感官机制,我们采用“视觉体积”定义视觉范围(图3-2),该方法把视觉范围看成一个圆锥体(由顶角与高度两个参数限定)。圆锥的体积代表了Agent的可视范围——一个对象对Agent可视是指它处在这个圆锥里面,并没有被任何障碍阻挡。

图3 -2视觉体积

图3 -3点测试算法

计算Agent的虚拟视觉一直是计算机图形学研究的热点,目前已研究出许多有效的方法。根据前人的实验结果,我们采用了一种混合计算模型(即结合点测试算法和光线跟踪算法相结合)。结点检测算法是用来确定出口或某个可达的点是否在视野范围内。假设人眼位于O点,最大视角为θ、可视距离为Vr(如图 3-2),我们用该算法测试点P是否在视野范围内,如图3-3所示。因为结点测试算法只对少量的点(即出口与结点集)进行测试,因此它设计简单且计算高效。

光跟踪算法主要用来计算静态障碍物的可见性。一个有趣的视觉现象是,个体并不是同时看见他们可视范围内的所有对象。个体在某一时刻通常只会将注意力集中在一个对象上,由于该对象的某些特征对个体的吸引最大。因此,没有必要计算在个体可视范围内的所有物体,而只需计算那一时刻所关注的物体即可。当有人员的周围存在大量的物体时,我们首先会对离他最近的物体做测试。假设人眼位点O,可视距离为Dr,M∈( 0,1]的一个实数,ε是一个很小的大于0的常量,图3-4描述了光线跟踪算法判断障碍物是否在可视范围内。

该算法可以很好地用于探测附Agent周围的障碍物,以避免Agent在移动过程中与障碍物发生碰撞。该算法与人的视觉机制十分相似,同时它的效率也是较高的。

图3 -4光测试算法

3.2 Agent 的行为系统

行为系统好比Agent的大脑。根据从感知系统收到的数据,Agent在内部因素(即心理因素和社会因素)的作用下做出行为决策。行为系统的主要组成部分是一个基于决策树一组决策规则,在决策树中,非叶子结点代表条件或某些操作,而叶节点表示一个行为决策。不同的决策树会生成不同的行为决策行为。

在人群疏散模型中,心理因素与社会因素作为制定决策的主要依据：

(1)对环境的熟悉程度：这一因素在系统中表示为,在Agent的记忆空间中存储的出口列表。总的原则是,Agent在疏散过程中往往会选择存储在记忆空间中的出口。

(2)决策类型：由于人物特征(如性格、经验)各不相同,不同类型的Agent对应不同的决策树。每一个决策类型由一个特定的决策树的形式表现出来。

(3)疏散的紧张程度：这一因素用来模拟心理压力对Agent行为的影响。总的来说,出口越拥挤Agent就越希望快速地通过出口,这样就会导致群体的竞争行为。在这个系统中,出口负载参数是一个介于0到 1之间的浮点数,“1”表示出口达到了最大负载。

(4)心理压力阈值：这个参数表示心理压力大小会影响Agent的决策,并导致Agent做出不同行为决策。例如,当Agent的心理压力低于某一阈值,那么Agent会排在出口队列的后面,而不在群体中表现出竞争行为。在我们的疏散模型中,每个人的心理压力值是各不相同的,并且对每个人心理压力阈值定义也不相同。

(5)羊群效应：这一因素反应了人类行为的社会学理论——当一个人不知道该做什么的时候,那么别人在做什么,他也跟着做什么。当一个Agent探测到多个出口的时候,那么在群体因素的影响下,他会走向群体最大的那个出口；否则就会走向最近的那个出口。

由于MASS是基于模块化设计的,在系统集成之前,我们可以对决策规则与行为系统等模块做单独测试——一个决策规则或行为事件可用指派给Agent用于测试。该设计灵活性且可扩展性好,能非常方便地将心理学与社会学相关的模块集成到系统中去。

图3 -5行为例程算法

3.3 执行系统

执行系统用来执行行为系统制定的行为决策。一个行为事件往往包含一个或多个操控行为,而每个操控行为通常包含一系列的移动。

在MASS中,行为决策代表了一个Agent的意图,如确定和选择出口,然后走向它。在图3-5讲述了行为事件执行的算法步骤。

操控行为的概念来源于机器人和人工生命。它以逼真的方式实现在虚拟环境下的现路径导航,组合一些操控行为可完成更高层次目标[6],如避开中间的障碍物移动到指定的目的地。对于每一个时间步长,操控行为的主函数都会：计算操控力并执行合法移动,在图3-6中作了算法描述。注意：合法移动受常数k的约束,因为某个时刻一个合法移动也许是不可能执行的(例如,当Agent处于一个密集的人群中)。一个移动事件的选择是根据某个决策行为的决策树来决定的。

一个特定的操控行为是由一组移动序列构成的。一个最基本最简单的移动可由Agent的制动器来完成,如‘前进一步’。移动基本步骤在图3-7中进行了描述。

在MASS中,我们定义了八种移动类型来模拟人群的疏散过程：前进,左转,右转,后转,左移,右移,后退,停止。

图3-6 操控行为算法

图3-7 移动算法

4 分布式网络模型

在大规模人群模拟实现中,计算机的体系结构会对我们的结果产生很大影响,我们常用的模型有：单机模型,集中式服务器—客户端模型,全分布式网络模型(P2P模型),基于黑板的分布式模型(P2P与集中式混杂模型)。在我们的实验中,选用了基于黑板的分布式模型,如图4-1所示。下面我们就分析这几种模型的优缺点及选择基于黑板的分布式模型的原因。

图4-1 混合模型网络拓扑结构

(1)单机模型这种结构的优点：结构最简单,易于实现。不用考虑网络延迟与客户端间的同步。缺点：对机器的性能要求较高,人群模拟的数量在很大程度上受到限制。

(2)集中式网络模型优点：结构相对简单,所有事务由服务器集中管理,客户端同步代价较小,每个客户端只需向客户端发请求,等待服务器的响应,实现起来也比较简单。缺点：服务器成为整个系统的瓶颈,整个系统的通信都需服务器的参与才能完成,一旦服务器出现问题,整个系统都不能工作,而且对服务器的性能要求较高。

(3) P2P模型优点：每个 Peer都能与其它 Peer独立通信,解决了集中式中服务器造成的瓶颈问题。在理论上可以模拟任意多个人群。缺点：为一个事务的同步,系统的通信量很庞大。每个Peer得向所有peer(除自己)发出询问,待收到应答后才能做出决定,时间复杂度为O( N2).

(4)混合模型优点：服务器用来同步,接受,发送,处理控制信号,降低了P2P系统中同步的通信代价,O( N2)到 O( N)。每个 Peer间都可完成通信,因此,除控制信号外的其它信号可采用端到端传送,无需服务器的参与,大大降低了服务器的负载。相对于以上三种,在很大程度上提高了整个系统的性能。缺点：相对复杂,不易维护,服务器仍然是整个系统的关节点。

混合式继承了第二种与第三种方式的优点。能够在普通的PC机群上模拟 100000个以上的人群。我们将地图分割成N块,每块地图对应网络中一个Peer,服务器将人群随机的分配到每个Peer中,每个虚拟人都能在整个环境中自由运动。当一个虚拟人从地图的一个分块走到另一个分块(既从一个Peer到另一个Peer中)时,这块地图对应的Peer会通知下块地图对应的Peer,并将这个虚拟人的所有状态(包含目标与路径)传送过去,且将结果报告给服务器。服务器将所有人的位置渲染出来。

5 实验结论与结果

在我们的实验中,我们采用了多种方法对系统进行测试并取得了较好的实验结果。我们的系统在一组处理器为AMD 4400+,内存1G的一组台式机上运行。在单机环境下,我们的系统能流畅地模拟4000人；在分布式环境下(15个 PEER),我们的系统能流畅地模拟50000人。下图 5-1为 4个 peer情况人群状态,人群运动状态。

图5-1 四个对等下实验结果

我们针对不同的情况,统计CPU利用率与循环一次所耗时间,结果如下表所示。表5-2为单机运行的结果,表5-3为两个 Peer运行的结果,表5-4为四个peer运行的结果。

表5 -2单机结果分析

在我们的实验中,尽量使整个系统达到负载均衡。从上表中我们可以清晰的看到,分布式系统能够模拟更多的人群。随着Peer的增加,模拟的总人数也会不断增加,但每个Peer的平均人数在减少。

6 实验结论与展望

在我们的论文中,我们介绍了一个基于agent的分布式人群模拟系统。我们利用agent的自治性与社会性很好地模拟了人群行为。此外,我们设计了一个P2P与 C/S相结合的混合网络模型,我们的实验取得了较好的效果。在分布式环境中,我们使用了地图分层策略,大大提高了路径规划的效率。实验结果展示,我们的系统非常成功并能很好地适用于大型公共设施人群运动情况。

在未来的工作中,我们将设计不同类型的Agent(如,小孩、老人、男人、女人),并对系统的一些算法进行优化,此外,我们应运用图形学知识,对人物的动作进行拟合,使人物的动作看起来更流畅。

[1] 徐高.人群疏散的仿真研究[D].西南交通大学,2003.

[2] G.Keith Still,Crowd Dynam ics:[PhD Thesis],UK:University ofWarw ick,2000.

[3] Xiaoshan Pan,Charles S.Han and Kincho H.Law;A Multi-Agent Based Simulation Framework for the Study of Human and Social Behavior in EgressAnalysis.

[4] AvneeshSud,Erik Andersen,Sean Curtis,Ming Lin,Dinesh Manocha;Real-time Path Planning for Virtual Agents in Dynamic Environments;Virtual Reality Conforence,2007,IEEE.10-14March,2007:91-98.

[5] Yongqing Ye,QinggeJi;Real.Real-Time Path Planning of Large-scale VirtualCrowd;Third InternationalConference on International Information Hiding and Multimedia Signal Processing,November26-28,2007,Kaohsiung,Taiwan.

[6] vneeshSud,Erik Andersen,Sean Curtis,Ming Lin,Dinesh Manocha;Real-time Navigation of IndependentAgents Using Adaptive Roadmaps;ACMSiggraph 2008.

[7] Mubbasir Kapadia,Shawn Singh,Brian Allen,Glenn Reinman,Petros Faloutsos,SteerBug:An Interactive Framework for Specifying and Detecting Steering Behaviors;Proceedings of the 2009 ACMSIGGRAPH/Eurographics Symposium on Computer Animation,August 01-02,2009,New Orleans,Louisiana.

[8] Hao Jiang,Wenbin Xu,Tianlu Mao,Chunpeng Li,Shihong Xia,Zhaoqi Wang;A Semantic Environment Model for Crowd Simulation in Multi-layered Complex Environment;Proceedings of the 16th ACMSymposium on Virtual Reality Software and Technology,November 18-20,2009,Kyoto,Japan.

[9] Russell Gayle,Dinesh Manocha,Navigating Virtual Agents in Online Virtual W orlds;Proceedings of the 13th international symposium on 3D web technology,August 09-10,2008,LosAngeles,California.

[10] Miguel Lozano,Pedro Morillo,Daniel Lew is,Dirk Reiners and Carolina Cruz-Neira;A Distributed Framework for Scalable Large-Scale Crowd Simulation;Virtual Reality,HCII2007,LNCS 4563,pp.111-121,2007.

[11] u,X.,ArtificialAnimals forComputerAnimation:Biomechanics,Locomotion,Perception,and Behavior,Ph.D Dissertation,Department of Computer Science,University of Toronto,1996.