基于群体智能的人群疏散路径规划仿真研究

刘 弘

( 1) 山东师范大学信息科学与工程学院，250358，济南；2) 山东省分布式计算机软件新技术重点实验室，250014，济南 )

1 引 言

近年来，随着社会经济的高速发展，各种聚集了大量人群的大型公共活动不断增多，这其中的安全问题引起了越来越多的关注.在一些人员密集的公共建筑场所内，由于建筑设计上的不合理，以及应急管理方面的不到位，当发生各种紧急突发事件、人员需要紧急撤离时，容易造成疏散人群的拥挤和阻塞，甚至发生严重的人员踩踏事故.研究突发事件下人群疏散的行为特征及运动规律，对于促进建筑物的合理设计，加强安全管理，从而有效地预防和减少各种突发情况下人员的伤亡，具有十分重要的意义.

突发事件下的人群疏散运动是一个非常复杂的过程.组织人员进行疏散实验，虽然针对性强，获得的信息量大，但是实验费用和人员安全问题是不可回避的，所以计算机仿真模拟成为研究突发事件下人群疏散的最主要方法.通过对密集人群疏散过程的仿真，可以再现行人在疏散过程中的动态行为特性，模拟密集人群在疏散过程中拥挤的产生机理、传播过程和流量分布趋势.对事故易发区如出口和拥挤区域的流量密度分布进行分析，可以为拥挤事故的预防和控制提供科学的理论基础.

密集人群的疏散行为特性研究是行人流理论的一个分支，与常规情况下的行人流相比，行人的疏散行为不仅包含了从当前位置到目的地的移动行为，还包含了出口和路径的选择行为.尤其是在内部结构复杂的大型公共场所中，行人的出口和路径选择行为决定了人群的流量分布以及疏散效率.因此，行人的疏散行为具有宏观和微观的双重特性.宏观层面，行人期望以最快的速度到达目的地，并且会根据获取的外界环境信息调整自己的决策和行为；微观层面，行人会根据选择的目的地方向进行速度和位置的更新，并且在移动过程中尽量避免与其他行人发生拥挤和碰撞.行人疏散行为的宏观因素和微观因素相互关联、相互影响，共同影响人群的疏散过程.

行人的疏散行为具有许多与常态下不同的特性.首先，行人遇到紧急情况时会产生紧张、恐慌的心理，本能的反应是希望以最快的速度逃离危险区域.疏散过程中，行人的移动速度往往要髙于通常条件下的走行速度.其次，行人会根据实时的环境信息，动态地选择和变更疏散时间较短的出口和路径.因此，行人出行的目的地以及路径是动态变化的.第三，行人之间会进行信息的传递，不断更新自己的信息集合以做出更优的选择.疏散开始时，行人首先会根据视野信息和历史信息做出初始的判断，例如判断出口的位置、估算疏散的时间.如果行人对场所不熟悉，则将跟随周围的行人进行移动.疏散过程中，行人之间将会互相交换信息集合，以获取更全面的信息，从而选择疏散时间较短的路径.因此，行人的疏散行为还具有一定的自组织特性.

人们从生物进化机理和一些物理现象中受到启发,从而提出了许多用以解决复杂优化问题的群智能优化算法,它具有高效的优化性能、无须问题特殊信息等优点.群智能优化算法是计算智能的一个重要分支，受到了各领域广泛的关注和应用，在许多领域(包括过程控制、机器学习、智能交通、经济预测和工程优化等)取得了显著的成绩.在解决疏散问题的建模方法中,蚁群算法及微粒群算法已经有相关的研究及应用.

2016年,中国工程院启动了“中国人工智能2.0”重大咨询项目,认为未来的人工智能将是人、计算机和互联网融合在一起运行的智能系统.数据驱动学习,深度整合多种媒体的非结构化数据,人机和脑机交互,成为群体智能系统.

在互联网环境下，海量的人类智能与机器智能相互赋能增效，形成人机物融合的“群智空间”，以充分展现群体智能.其本质上是互联网科技创新生态系统的智力内核，将辐射包括从技术研发到商业运营整个创新过程的所有组织及组织间关系网络.因此，群体智能的研究不仅能推动人工智能的理论技术创新，同时能对整个信息社会的应用创新、体制创新、管理创新、商业创新等提供核心驱动力.

2 人群疏散仿真模型

在大规模人群疏散中，不同个体组合成一个群体,群体中的个体和个体之间又存在着交互作用，这种交互作用呈现出明显的非线性特征[1].个体的行为特点使得群体行为表现为各种能量的汇聚、冲突、平衡、失衡，以及群体性趋向和排斥等现象[2].上述现象决定了对疏散人群运动规律的建模十分困难.因此，如何在针对非常规突发事件的大规模人群疏散中，结合各种人的心理状态、行为特征、运动规律及交互作用等各种不确定性因素，建立合理的仿真模型，是一个亟需解决的问题.

微观仿真模型中具有代表性的有社会力模型、元胞自动机模型及基于Agent的模型.

社会力模型是由Helbing等[3]提出的一种基于多粒子自驱动系统框架的模型,以经典Newton力学为基础，假设个体在疏散过程中受到三种力的作用: 驱动力、人和人之间的作用力以及人和障碍物之间的作用力.所谓社会力，就是个体在疏散中受到的来自于其他人及周围环境的这些物理、心理、社会上的相互作用的统称.该模型得到了同行的高度评价，并作为封面文章发表在Nature杂志上[4].迄今为止，社会力模型已被公认为是对疏散时的个体动力学特征进行仿真模拟的最有代表性的数学模型，主要原因就是它能够很好地模拟出人群运动中诸如“快即是慢”、拱形拥堵等复杂现象.国内外学者在Helbing的研究基础上，对社会力模型进行了诸多改善和发展[5-7].

社会力模型独特的优点在于较强的真实性，能体现人群运动的自组织现象.但社会力模型也有其局限，它是一种从微观角度、针对个体进行建模的模型，需要设定复杂的建模规则，并且计算的时间复杂度为O(N2)，即随着疏散人数N的增大，计算时间将急剧增长，因此，当涉及到区域性的大规模人群疏散时，计算效率会很低.

元胞自动机(Cellular Automaton， CA)是一种离散的微观模型[8]，是在有限元胞自动机的基础上发展起来的，用于分析和模拟几何空间内的现象.构成元胞自动机的每一个部件被称为“元胞”，在空间网格上，这些元胞有规则地排列在一起组成了元胞空间，每个元胞有自己的属性，并且随着每个时间步的改变而改变.元胞自动机具有一些特定的局部规则，且在时间和空间上处于离散状态.元胞在当前刻的状态仅仅与上一刻该元胞的状态有关.用于研究人群动力学并且基于元胞自动机的代表性模型是由 Ansgar Kirchner[9]提出来的.加拿大的 Henein 和 White 在文献[10]中对 Kirchner的元胞自动机模型进行了改进，并利用基于多智能体技术的计算机模拟对疏散过程中的人群行为进行了分析.在其提出的模型中阐述了人群中的个体伤亡是由于个体之间的相互作用力达到一定的阈值，并给出了个体之间相互作用力遵循的四个基本规则.元胞自动机模型已经在人群疏散仿真研究中受到高度重视[11].

元胞自动机模型由于其规则简单，计算速度快，资源耗费少， 适于大规模人群的计算机模拟.但是，在行人运动和疏散模型中元胞的智能性还比较欠缺，忽视了群体作用的影响，模拟结果与实际情况偏差比较大，这是元胞自动机单独用于模拟人群行为的局限之处.

Agent-based 的模型是当前研究的热点之一[12,13].这种仿真模型建模的对象不是整个人群，而是人群中的每一个个体，将每个个体定义为一个计算对象.定义对象的状态属性和行为规则，在疏散模拟中，个体根据所处的环境，获取环境的反馈信息，依据被定义的行为规则，采取相应的行动.

基于Agent的群体模型存在的最大问题是难以控制.一方面，当群体行为比较复杂时，要制定满足需要的规则比较困难，另一方面，这种模型将碰撞检测和全局路径规划分开，两种目标经常存在冲突，最终结果经常脱离预先的估计.如果为每个Agent都做全局运动规划，则计算开销太大.因此，基于Agent的群体模型往往只能用于处理较小规模的群体，并且在实时计算环境中很难应用.

宏观模型中，人群是作为整体来考虑的，人群中的所有人都具有同样的移动特性.人员之间的相互作用、人员的主观心理在模型中都得不到体现，这也造成了模型仿真结果的应用性不强.但是相对而言建模简单，对计算复杂度要求不高，对计算机资源要求很低，是早期主流的疏散仿真模型.

微观模型的研究对象为单个行人个体，考虑了个体之间的相互影响等行人细节，适用于复杂的环境.但是，由于考虑了细节，而且研究对象为个体，导致了计算复杂度过高，当仿真大规模人群疏散时，计算的时间急剧增加.

本研究结合宏观模型和微观模型的优点，建立一种混合模型，弥补两种模型在仿真大规模人群疏散时的不足.该模型采用多层次群体控制的方法.在群体模型中增加一个群组层，这样就形成了群、群组和个体的三层结构.该模型将群组视为主要控制对象，群组内选择引领个体，引领个体具有一定的记忆力和针对事件发生做出反应的能力，群组之间通过交流传递信息.因为大部分的计算针对组而非个体，计算量大大减少，可以实时地模拟规模较大的群体.这是本研究的重点之一.

3 群体智能优化算法在路径规划中的研究

群体智能[14](Swarm Intelligence)指的是“简单智能的主体通过合作表现出复杂智能行为的特性”.它具有分布式控制、全局信息传播、非直接通讯模式和自组织等特点，突出了群体中个体之间通过协作而表现出复杂行为的涌现现象.群体智能利用群体优势，使之在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了新的思路.

自然界中的群居昆虫，如蚂蚁、蜜蜂、鱼群、鸟群等，它们个体结构都十分简单，但是通过个体间的合作表现出来的行为能力却极其复杂.群居昆虫个体虽然无智能，但是通过合作从一定程度上体现出较高的“智能”.受这些社会性昆虫群体行为的启发，研究人员通过模拟这些群体的行为产生了一系列解决传统优化问题的群体智能算法，先后提出了模拟蚂蚁行为的蚁群算法(Ant Colony Optimization，ACO)[15]，模拟鸟类行为的微粒群算法(Particle Swarm Optimization，PSO)[16]、模拟青蛙觅食的混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)[17]和模拟蜜蜂觅食的人工蜂群算法(Artificial Bee Colony，ABC)[18，19]等.这些群体智能优化算法的出现，使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决，大大增强了人们解决和处理优化问题的能力.

人群疏散研究中的一个关键问题是如何对人群的运动路径进行规划.群体运动的复杂性和微妙性，造成群体路径规划一方面需要考虑环境约束，另一方面还需考虑群体中个体之间的交互影响.近年来，一些新的计算智能技术逐渐引入到路径规划中来，遗传算法、蚁群算法[20,21]、人工鱼群、微粒群算法[22]、人工蜂群算法[23-25]等应用于路径规划问题的研究成果不断涌现，同时也促进了各种方法的融合发展[26]，其中有代表性的是蚁群算法、微粒群算法和人工蜂群算法.

3.1蚁群算法蚁群算法以类似蚂蚁觅食的方式在求解复杂组合优化问题上取得了良好的仿真效果，疏散情况下的疏散对象所表现的自组织，从众等行为与蚂蚁觅食的行为非常相似，且蚁群算法的正反馈机制能够体现疏散个体对环境的感知和交互.所以，用蚁群算法求解疏散问题是适合的.付军栋等[27]结合某商场的工程实例，采用改进的蚁群算法规划出最佳的疏散路线，将平面疏散与垂直疏散融合，提出了三维疏散的方案，结果表明动态疏散蚁群算法在大型商场环境中可以有效躲避障碍物.

蚁群算法采用分布式并行计算机制，易于与其他启发式方法结合，具有较强的鲁棒性等优点，尤其是在求解复杂的组合优化问题方面的优势，使其在短期内得到了很大发展，其应用领域也不断得到扩展.但同时也有搜索时间长、收敛速度慢、容易发生停滞、易于陷入局部最优解等不足.

3.2微粒群算法来源于对鸟类捕食行为的模拟，微粒群优化算法中的每一个解都被看作是搜索空间中的一个粒子(疏散对象)，每个粒子拥有一个由优化函数确定的适应值，通过存储记忆可知到目前为止发现的自身最好位置和当前位置.除此之外，每个粒子还保持了到目前为止整个群体中所有粒子搜索发现的全局最好位置.粒子自身的飞行经验(自身经验)和同伴经验(社会经验)使其具有动量不断尝试跳出当前位置直至移动至最优位置.这种仿生机制非常自然地适合于对人群疏散过程进行模拟抽象.也就是说，每个疏散个体可以抽象为一个粒子，依据当前自身状态与邻域疏散个体不断交互学习，从而不断发现新的疏散路径信息.与疏散过程相似，这也是一个动态过程.使用粒子群优化算法预测疏散时间的模型由Izquierdo J等[28]提出，该模型使用微观粒子模拟个体的疏散行为，以粒子到出口的距离最短为目标，研究了出口大小和疏散时间的关系.

微粒群算法是一种基于种群的启发式优化算法，由于其参数设置少，实现简单，并且具有较好的寻优特性、收敛速度快等特点，使其得到迅速发展.微粒群算法最突出的一个特点就是收敛速度快，但这个特点同时也带来了算法早熟收敛的问题.

3.3人工蜂群算法人工蜂群算法是一种新的群智能进化算法，算法具有全局收敛、适应范围宽、设置参数少、本质并行性等优点[29].但ABC 算法的研究刚刚开始，在算法参数的自适应、算法改进、与其他算法的比较与混合等诸多问题上有待进一步研究.

人工蜂群算法是通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度.它具有很强的发现最优解的能力，这是因为算法利用了引领蜂和跟随蜂寻路的正反馈机制，在一定程度上可以加快进化过程.而且蜜蜂间不断进行信息交流和传递，从而能够相互协作，有利于发现较好解.由于在人工蜂群算法中使用概率规则而不是确定性规则指导搜索，不必知道其他先验的信息，所以该算法有极好的鲁棒性和广泛的适用性.但人工蜂群算法又是一种新型的随机优化算法，其研究刚刚起步，还存在很多问题有待深入改进和解决.例如算法的收敛性、理论依据；算法的改进研究，特别是与其它进化算法的结合；以及完善ABC算法在复杂领域的应用，将其用于解决现实中的实际问题等，都需要我们进一步的研究和探讨[30].

人工蜂群算法结合全局搜索和局部搜索的方法来使蜜蜂在食物源的探索和开采两个方面达到较好的平衡，它在函数优化方面的性能优于差分进化和微粒群等算法.但是，目前人工蜂群算法作为一种新的随机优化算法，在接近全局最优解时，仍旧存在着搜索速度变慢、过早收敛、个体的多样性减少、甚至陷入局部最优解等问题.

但是随着对其研究的深入化，人工蜂群算法的性能将不断完善，算法的寻优能力、与他算法的结合，以及在复杂领域中，人工蜂群算法的应用都有待进一步探索.

群体智能具有天然的分布式和自组织特征.它在没有集中控制且不提供全局模型的前提下表现出了明显的优势，为求解复杂优化问题、实施路径规划提供了新的思路.由于群体智能的灵感来源于自然界中生物的群体行为特性，因此利用群体智能算法进行人群疏散仿真具有其它方法无法比拟的优势.首先，群体智能仅仅需要对个体行为进行建模，通过个体之间的协作与交互突现出复杂的群体智能行为，因此具有实现简单、计算复杂度低的优势.其次，群体智能是对自然界客观存在的群体行为的提取与总结，基于群体智能的人群疏散仿真具有更好的仿真效果与逼真度.因此，利用群体智能的典型算法进行人群疏散仿真理论上可行，具有良好的理论研究意义及实际可用价值.

从国内外的研究现状来看，基于群体智能的方法在人群疏散仿真中的研究还比较少，但是已经引起相关领域研究人员的重视.

本研究在群体智能算法的基础上，以人群疏散仿真为应用领域，结合人群疏散社会力模型，在人工蜂群与疏散人群之间形成建模映射，从而构建基于群体智能算法的人群疏散仿真模型.研究成果将深化对突发事件下人群行为机理和动态演化规律的认识，为人群疏散应急决策提供依据，这在该研究领域还是很有竞争力的研究课题.

4 基于人工蜂群算法的路径规划与仿真

在公共场所内，人群中的行为簇现象会更加明显，而行人的聚集也会造成小群体，这些特征不论在模型搭建还是仿真模拟时都需要加以考虑.小团体可分为两类：第一类小团体从人群进入建筑物时就形成，成员一般由家人、情侣和朋友等组成，这类小团体成员少、内部联系紧密，定义为紧密型小团体；第二类小团体在逃生时形成，成员一般由对附近环境熟悉的人员吸引周围的人聚集成了小团体一起逃生，这类小团体成员多、内部联系不紧密，定义为逃生型小团体.

本研究采用人工蜂群算法，主要是根据出口处的拥挤度及人群到各出口的距离，合理的划分逃生型小群体，并选择引领者，为逃生型小群体在出口拥挤度及到出口的距离之间找一个动态的平衡.

图1 人工蜂群算法路径规划流程图

图1中，疏散场景属性为根据视频提取的场景信息.在人工蜂群算法中，合适的适应度函数是影响算法优化结果和效率的重要因素.本研究中，我们根据疏散仿真的要求定义适应度函数，根据出口处的拥挤度及人群到各出口的距离，将疏散人群划分为多个小群体，在各群组中选择引领者，引领者通过与导航Agent交互，动态选择到出口的路径.

4.1人工蜂群算法及其改进人工蜂群算法是建立在蜜蜂自组织模型和群体智能基础上的一种非数值优化的计算方法.算法的三个要素包括：食物源、雇佣蜂和非雇佣蜂；两种基本的自组织模式：为食物源招募蜜蜂和放弃某个食物源.食物源对应着优化问题的可行解，其质量由单一的参数“收益率”表示，收益率的大小决定了候选解的质量；雇佣蜂也称为引领蜂，与被采集的食物源相对应；侦查蜂和跟随蜂统称为雇佣蜂.在算法开始时，非雇佣蜂做如下两种选择：1) 成为侦察蜂，在蜂巢周围随机探索新食物源，以增强算法的全局搜索能力.当侦察蜂发现新的食物源后记录下该食物源的信息转为引领蜂.2) 成为跟随蜂，即等待在蜂巢中通过观看引领蜂跳摇摆舞的方式选择到哪个食物源进行采蜜.引领蜂首先对其对应的食物源进行邻域搜索，按照“贪婪”选择方式，如果搜索到的食物源收益率高于之前的食物源，则用新食物源的位置替换旧食物源的位置，否则保持食物源位置不变.然后对每个食物源计算其概率值，跟随蜂按照概率值大小选择所要采集的食物源，并像引领蜂一样对食物源的位置进行更新.ABC 算法就是通过蜜蜂不断地局部寻优最终使全局最优值凸现出来.

为了使传统的人工蜂群算法能用于人群疏散，我们对算法做了如下改进[23].

1) 将待疏散的人群与人工蜂群算法中的各参数做映射(如表1).

表1

2) 改进个体目标选择适应度函数.

根据疏散仿真的要求，采用公式(1) 和(2)设定个体的适应度值:

(1)

fiti=min{goalposik}.

(2)

其中goalposik为第k个安全出口相对于个体i的适应度值，xi表示第i个个体，exitk表示第k个安全出口，count[k]为当前时间选择第k个安全出口作为逃生目标的个体总数，sn表示群体规模，goalposi为个体i的目标位置，c1,c2为权重系数.由公式 (1) 可以看出，个体在进行目标选择时综合考虑了距离、人群密度和可达性等因素，使得个体能够在全局范围内自适应地选择适应度值最高的安全区域作为目标，以提高人群疏散的速度.

3) 引领者的选择.

引领者是根据适应度值在群组中选择的.适应度值的定义为

(3)

其中，w1和w2是权重值，w1+w2=1.xij是群组i中的第j个个体，k(xij) 是xij对场景的熟悉程度，d(xij)是从xij到所选择出口的距离.群组i中具有最高适应度值的个体被选择作为引领者.

4.2社会力模型及其改进Dirk Helbing根据人群行为特征，以牛顿力学为基础建立了社会力模型.社会力是指一个人运动时受到所处环境(包括环境中的人和物)对其施加的力，依据行人不同的动机和在环境中受到的影响，共有四种作用力的影响：自身驱动力、人和人之间的作用力、人和障碍物之间的作用力以及扰动力.这些力的合力作用于行人，产生一个加速度.在整个个体行走过程中，以及个体和个体之间始终存在一定的力的作用.例如，驱动力会引导个体朝目标方向前进；在个体身体接触之前，人和人之间的作用力使人群中的个体避免相互碰撞；人和环境之间的作用力使人群中的个体避免与障碍物碰撞.这个过程可以用经典牛顿第二定律来解释，表达式如下：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

我们的改进主要有以下两点：

1) 为了群组中的个体跟随引领者向出口移动，我们修改了跟随者对应的社会力模型，把原模型中自驱动力选择出口作为目标，改为以本群组的引领者作为目标[31].

将原始的社会力模型 (4) 改为跟随者对应的公式 (11).

(11)

主要的修改是对右边第一项：自驱动力.原始的自驱动力公式为

(12)

2) 在社会力模型中增加视觉因子.

由于行人的视野半径R有限，不能对全局的疏散状态熟知，在不可见安全出口区域，行人只能看到视野半径R内的目标，此时行人会随机行走，由于从众效应，往往会往疏散行人较多的方向进行移动.本研究引进了视觉因子，以便行人根据视野范围内的行人数量选择自己的方向[23].

原始的社会力模型中的心理力是各向同性的，即周围物体的排斥力是相同的，不考虑个体的视觉极限.为了保持团队中的个人行为一致，并观望未来执行动态全局规划和本地导航，我们在公式 (8) 中添加了可视化参数，扩展原始的社会力模型，相关公式如下所示：

(13)

Vis=λ(1+cosθ)/2+(1-λ)(1-cosθ)/4,

(14)

(15)

(16)

我们将人工蜂群算法与社会力模型结合，利用人工蜂群的群体智能寻优及交互机制，从宏观角度组织人群疏散，利用社会力模型的作用力聚集及避障，从微观角度更真实地仿真人群疏散，弥补两种模型在仿真人群疏散时的不足.本方法整体采用多蜂群人工蜂群算法群组并行疏散，进行全局路径规划，群组内部采用有引领者的社会力模型向目标移动疏散，进行局部路径规划.因为大部分的计算针对群组而非个体，计算量大大减少，可以实时地模拟规模较大的群体，为疏散演练提供帮助.

5 结 语

本文研究是在三项国家自然科学基金(基于计算智能的群体行为控制模型及路径生成研究(No.61272094), 基于群体智能的人群疏散仿真模型及动态路径规划方法研究(No. 61472232), 基于知识的人群疏散路径导航及仿真研究(No. 61876102 ) 的资助下完成的.在多年研究的基础上，我们开发了一个基于群体智能的人群疏散仿真平台，对我们提出的模型及方法进行了验证.正在进行的工作是结合视频数据驱动[32]，引入机器学习的方法[33]，通过训练逐渐提高疏散效率，建立基于知识的人群疏散路径导航[34]，为校园中快速人群疏散训练及应急管理提供支持.