煤矿井下应急逃生最优路径规划算法研究综述

赵慧敏 李超 曾庆田

摘 要：近年来国家对矿山的安全生产工作日益重视，但矿山灾害事故仍时有发生。在矿山事故发生后，如何确定一条最佳避灾救援路线，指导受灾人员安全撤离，从而将突发事故的影响和伤亡人数降到最低，成为目前矿山应急突发事故处理方法的重点研究方向。针对煤矿井下避灾救援路径的最优规划问题进行综述，首先从井下突发事故的静态最优路径规划算法和动态最优路径规划算法两方面揭示煤矿井下路径规划的基本方法，然后介绍复杂环境影响下的应急救援路径规划，最后总结煤矿井下应急逃生路径规划研究面临的问题与挑战。

关键词：应急逃生路径；路径规则；动态最短路径算法；静态最短路径算法

DOI：10.11907/rjdk.173012

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2018）005-0001-05

Abstract：In recent years， despite the state has paid more and more attention to the safety production of mine， accidents continue to happen. How to determine an optimal rescue route for avoiding disasters， which will minimize the impact of accidents and the number of casualties， has become the key research direction of mine emergency handling methods. This paper summarizes the optimal planning problem of mine disaster avoidance and rescue route. Firstly， the basic method of mine route planning is revealed from two aspects： static and dynamic optimal path planning algorithm. Then the current research of the emergency rescue route planning under the complex environment is summarized. The problems and challenges of mine emergency escape route planning are summed up by the end.

Key Words：emergency escape route； path planning； static optimal path planning algorithm； dynamic optimal path planning algorithm

0 引言

近年来，我国对原材料和能源的需求日益增加，采矿业发展迅速，行业规模不断扩大。然而，我国矿山数量大、分布广、管理松散，并且存在部分矿山开釆不正规、安全生产投入不充足等问题，企业安全管理无法跟上产业规模发展，给矿山安全生产带来极大隐患，也导致矿山事故频繁发生。在对国内外煤矿典型事故进行研究分析时发现：当煤矿井下发生炮烟中毒、窒息事故和火灾事故时，人员死亡主要发生在人员逃生或逃生受阻过程中[1]。因此，在矿山事故发生后，如何确定一条最佳避灾救援路线，指导受灾人员安全撤离，最大程度地降低事故影响，成为目前矿山紧急事故处理系统的研究重点。

现有求解最短路径的方法在不考虑外界环境影响情况下，可分为静态最短路径算法、动态最短路径算法两大类。其中静态路径算法包括Dijkstra算法、A*算法等，动态路径算法包括蚁群算法、Bellman-Ford算法、SPFA算法等。然而，对于煤矿井下复杂环境下的路径规划又有很大不同，常见的矿山重大灾害主要有：地质灾害、火灾、水灾、有毒有害气体等事故灾害。针对不同灾害，对应相应的逃生策略。本文将从煤矿井下逃生最优路径算法实现、环境影响下的路径规划两方面对煤矿井下突发事故应急逃生最优路径规划算法研究进行综述，并对未来的研究趋势进行展望。

1 最优逃生路径规划算法

1.1 静态最短路径算法

静态最短路徑规划算法是最早出现的路径选择算法，是指在外界环境不变的条件下，计算出一条逃生最短路径。本文针对最具代表性的Dijkstra算法、A*算法进行综述。

1.1.1 Dijkstra算法

Dijkstra算法由EWDijkstra于1959年提出，是图论研究中的一个经典算法，旨在寻找图中两节点之间的最短路径，主要特点是以某节点为起点逐渐向外扩散，一层层解决最短路径问题，直至扩散到目的节点为止。Dijkstra算法实现步骤如下[2-3]：

Dijkstra算法应用范围非常广，例如：煤矿井下大规模人群疏导、多点路由、测绘科学、物流运输、智能交通系统等。近年来，国内外对Dijkstra算法进行了大量研究，取得了不少成果。这些研究主要集中在两方面：①对Dijkstra算法本身的改进；②根据Dijkstra算法进行应用研究。Dijkstra算法在不同领域的应用如表1所示。

Dijkstra算法自提出以来一直是最优路径研究的热点，也是目前寻优策略中最实用的算法，其它路径寻优算法大多是在Dijkstra算法基础上演化发展而来。因此，可以说Dijkstra算法是最基础的路径寻优算法。

1.1.2 A*算法

A*算法是解决有附加条件最短路径问题的有效算法，优先搜索距离目标节点可能性较大的节点，对当前节

然而，经典的A*算法只注重了搜索精度，而忽略了搜索效率，一般只适用于复杂度较低的路径问题。为提高算法执行效率，国内学者对其进行了改进，该算法应用领域也极其广泛。A*算法在不同领域的应用如表2所示。

对于A*算法的研究，国内外侧重点有所不同。国外的相关研究可追溯到上世纪七八十年代，文献[22]系统讲解了从A*算法定义到算法最优性证明的全过程；文献[23]主要研究了A*算法中的启发式函数选取。而国内的研究主要集中在10年前，近年来热度有所降低。已有研究主要针对地面紧急情况，从遍历节点方面进行完善，而对于煤矿灾害紧急救援的研究较少。因此，在煤矿灾害紧急救援方面还需进行深入研究。

1.2 动态最短路径算法

在煤矿灾害发生时，随着时间推移，巷道安全性也会随之改变，应用静态最短路径算法求得的最优解尚不能完全满足逃生需求。为了适应煤矿井下多变的环境，进而出现了动态最短路径算法。

蚁群算法是20世纪90年代意大利学者Dorigo M等[24]从生物群体进化机制中受到启发，通过模拟自然界蚂蚁搜索路径行为，提出的一种新型群智能算法。该算法具有正反馈、分布式计算与富有建设性的贪婪启发式搜索的特点，主要用于求解组合优化问题。蚁群算法实现步骤如下：

从当前可查阅的文献看，上世纪90年代关于蚁群算法的研究主要在国外，国内从1998年末才开始出现少量公开报道和研究成果。蚁群算法发展的“瓶颈”问题是算法收敛性和连续空间寻优，因此国内外学者围绕这两个核心问题作了大量研究。例如，早期的有Gutjarh WJ[25]最先从有向图论角度对特定的改进蚁群算法BGAS的收敛性进行证明，通过选择合理的参数保证蚁群算法收敛性并收敛到全局最优解；Stuezle T 和Dorigo M[26]提出一类改进蚁群算法——ACOgb算法，并在理论上分析了其收敛性，得出当迭代次数无限增大时，算法收敛到全局最优解。

根据历年来对蚁群算法的改进，越来越多的学者将蚁群算法运用于煤矿井下矿山灾难研究中。在煤矿井下灾难中经常会出现局部火灾、水灾等现象，王伟杰[27]、李兴宇[28]结合巷道实际长度，引入了巷道当量长度邻接矩阵，利用蚁群算法对局部巷道的应急救援求解出救援最短路径，为救援提供理论支撑与实际执行路线；樊雯婧、卢才武[29]提出粒子群和蚁群混合算法，即利用粒子群算法搜索蚁群算法参数α、β、ρ，再反馈到蚁群算法中，对多救护队最优救援路径进行搜索，提高了全局搜索能力。将该算法应用于煤矿井下矿山全局灾害应急处理救援的路径选择中，不但收敛速度得到了大幅提高，而且在避免陷入局部最优解方面取得了很好的效果。

蚁群算法体现了其在路径动态优化中的优越性，在很多领域均有应用。对于煤矿井下矿山救援系统，由于煤矿井下地形复杂、环境多变等特点，导致很多寻优路径算法在应用时受到限制，蚁群算法是目前煤矿井下路径寻优实施效果最好的算法，因此值得进一步深入研究。

2 复杂环境下的最优路径规划

煤矿井下灾难类型包括瓦斯事故、顶板事故、运输事故、透水事故、火灾、煤与瓦斯突出事故等。由于煤矿井下环境的复杂性和煤矿灾难类型的多样性，导致传统的最短路径规划并不一定是最优规划。因此，需要在最短路径规划基础上，融合复杂环境和灾难类型进行路径的最优规划。本章着重总结煤矿灾难发生后的最优路径规划。

目前改进的Dijkstra算法可以求得源节点到目标节点的最短路径，但在发生煤矿灾难事故时，距离最短并不意味着用时最短，因为巷道逃生具有特殊性，在通行巷道中可能存在多个影响人员逃生的因素。除考虑灾害本身对巷道通行的影响外，还需要考虑多种因素对巷道通行的影响，点与点之间的距离不再是绝对距离而是一个相对长度[30-31]。因此，将当量长度概念引入到煤矿井下灾难最优逃生路线研究中，用于表示巷道通行的难易程度。

现有文献对于煤矿井下灾害的研究主要集中在水灾与火灾上，文献[35]借助矿井突变理论，对矿井突水的发生与事故应急救援、三维可视化应急救援系统设计与实现进行了深入研究；文献[36]运用全生命周期理论，建立以物联网为中心的信息共享平台，并结合灾后巷道的当量长度实施逃生与救援行动，以降低煤矿突水灾害的救援成本，提高对灾情的反应能力与救援效率；文献[27]-[29]中，王伟杰、李兴宇、樊雯婧等将蚁群算法运用于矿井火灾救援的最短路径研究中，随着时间推移，根据路况及环境影响，将不同情况下的当量长度输入系统，动态计算并输出实时路线；文献[37]中，李兴东针对现有矿井火灾时期避灾路线求解软件存在的不足，提出通过有烟巷道与安全地点判定、最短路线计算，自动选择避灾安全地点和求解避灾路线的方法；文献[38]则综合考虑火灾救援各影响因素，提出当量长度的概念及其求解方法，并引入避灾与救灾路径优化模型中，建立了矿井火灾救援辅助决策支持系统。

总体而言，对于煤矿灾难的路径规划研究大多集中在煤矿井下突水与火灾事故上，而对其它灾害方面的研究相对较少，很多工作还需继续完善。

3 煤矿井下最优路径研究趋势

煤炭是我国的第一大能源，在一次能源结构中占66.3%左右。然而我国矿难多发，给人民生命财产造成了巨大损失，因此需要不断研究矿难的特征及规律，尽量避免灾难发生。一旦矿难发生，也要有更优异的算法求解最优逃生路径，以便在最大程度上降低损失。

路径规划问题是应急救援中最重要的组成部分，地面应急救援系统如今已初步完善，然而对于煤矿井下救援系统，Dijkstra算法是现有最短路径算法的起源，其它算法基本是在其基础上的改进，并由最早的单源静态最短路径发展为现在的动态最优路径。动态最短路径的选择是路径优化的重点，根据现有文献可知，目前对于煤矿井下的最优路径规划算法还不够完善，未来有待研究的关键点有：

（1）环境复杂性与人员健康损失度对最优路径算法的影响。通过阅读文献可知，目前在矿山人员救援撤退的最优路径研究中心，都只考慮了巷道的当量长度，并未考虑灾害时期巷道的安全性，以及人员在逃生过程中的能量消耗问题。因此，未来研究方向应考虑巷道的环境因素与安全性两个方面，通过当量长度与人员健康损失度对人员的最优逃生路径进行分析研究。

（2）路径最大流量限制对最优路径算法的影响。现有算法对外界环境因素考虑尚不全面，仅考虑了自然环境，而未考虑人为因素，比如从众行为。中国人有很明显的“随大流”意识，当矿难发生时，系统给煤矿井下人员输出不同的逃生路径，若小众人员跟着大部分人跑同一条巷道，则会造成拥挤。因此，在设计算法时，应考虑人们的从众行为，进而设计更优的逃生路线。当对道路的最大流量进行限制时，将会对最终的救援规划产生颠覆性影响。

（3）安全舱最大容量对最优路径选择的影响。现有系统求解最优逃生路线，仅能解决最快路径与最低费用问题，然而其大多数仅考虑了工作面到安全舱这段距离，对于到达安全舱之后的安排鲜有涉及。也即是说现有算法是在安全舱不受限制的条件下进行的，但在真实情况下，安全舱会受到氧气供应、空间大小等很多因素影响。假若安全舱已达到最大容量，还有人员被导航引导过来，则会造成二次消费，不仅增加了财产损失，更重要的是在危机情况下会造成更多人员伤亡。所以未来的煤矿井下救援系统路径算法设计应该考虑安全舱的最大容量问题。

（4）最优路径与分配人员次序问题。在考虑以上两个因素的情况下，输出的最优路径也许和工作面人员数量不匹配，当最优路径所能容纳的人数小于工作面上的人员时，则要将一部分人分配到次优路径上去。关于人员以何种标准进行分配也是未来煤矿井下救援系统需要考虑的重点。例如身高、体重、心理素质、职位高低、文化水平高低等因素，都可作为未来最优路径算法研究的关注点。

因此，未来煤矿井下救援系统对于最优路径的选择问题可以更多地考虑这些变化因素，从而研究出更加合理、可行的逃生与救援路线，最大限度地减少安全风险以及对社会财产带来的损失。

4 结语

针对煤矿井下突发事故应急逃生的最优路径规划问题，本文首先综述了静态最优路径算法与动态最优路径算法的起源与发展，接着详细介绍了具体算法在矿井发生灾难时的具体应用，进而分析现有算法各自的优点与不足，最后提出煤矿井下最优路径选择研究尚有待完善的地方。但以上所有成果仅限于复杂度较低的灾难类型，例如矿井突水、矿井火灾，而对于其它灾难类型的研究非常少。煤矿井下突变时期环境非常复杂，比如瓦斯爆炸、煤尘爆炸、瓦斯突出等，对于这种蔓延性较快的事故，针对其复杂环境开展路径规划将是未来研究的重点和难点。

参考文献：

[1] 田洪现，杨维.基于无线局域网的矿山井下定位技术研究[J].煤炭科学技术，2008，36（5）：72-75.

[2] 张仕伟，孙亚南，朱轶殊，等.煤矿井下人员非连续性移动路径研究[J].煤矿安全，2017，48（6）：116-118.

[3] 侯运炳，夏兴，闫旭，等.基于矿井地理网络模型的最短路径改进算法[J].煤炭科学技术，2011，39（2）：103-105.

[4] 郭东.基于Virtools的煤矿井下逃生系统的研究[D].太原：太原理工大学，2016.

[5] 宋国娟.基于极限学习机的煤矿突水预测及避险路线优化研究[D].徐州：中国矿业大学，2016.

[6] 郭东，张宏.Dijkstra算法在井下逃生培训系统中的应用[J].煤矿安全，2015，46（11）：91-94.

[7] 赵祎，翟守忠，李富伟.改进Dijkstra算法在矿山应急避险引导系统中的应用[J].矿业研究与开发，2013（6）：88-90.

[8] 周耀东，曹志国，李翠平.基于改进Dijkstra算法的矿山突水可视化仿真[J].金属矿山，2010（10）：123-125.

[9] 孙佳，孙殿阁，蒋仲安.矿井应急救援中最佳避灾路线的改进Dijkstra算法实现[J].中国矿业，2005，14（6）：46-48.

[10] 王树西，吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学，2012，39（5）：223-228.

[11] 董俊，黄传河.改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J].计算机科学，2012，39（10）：245-247.

[12] IDWAN S， ETAIWI W.Dijkstra algorithm heuristic approach for large graph[J]. Journal of Applied Sciences， 2011.

[13] MEDEIROS F L L， SILVA J D， SIM D. A Dijkstra algorithm for fixed-wing UAV motion planning based on terrain elevation[C].Brazilian Conference on Advances in Artificial Intelligence. Springer-Verlag， 2010：213-222.

[14] TINTOR V， RADUNOVI J. Distributed Dijkstra sparse placement routing algorithm for translucent optical networks[J]. Photonic Network Communications， 2009，18（1）：55-64.

[15] 辛煜，梁华为，杜明博，等.一种可搜索无限个邻域的改进A*算法[J].机器人，2014，36（5）：627-633.

[16] 钱红昇，葛文锋，钟鸣，等.基于分层的改进A算法在路径规划中的应用[J].计算机工程與应用，2014，50（7）：225-229.

[17] 李志建，郑新奇，王淑晴，等.改进A*算法及其在GIS路径搜索中的应用[J].系统仿真学报，2009，21（10）：3116-3119.

[18] 史辉，曹闻，朱述龙，等.A*算法的改进及其在路径规划中的应用[J].测绘与空间地理信息，2009，32（6）：208-211.

[19] 王帅.煤矿井下基于改进A*算法的移动机器人路径规划[J].煤矿机械，2008（11）：65-67.

[20] 高松，陆锋，段滢滢.一种基于双向搜索的K则最优路径算法[J].武汉大学学报：信息科学版，2008，33（4）：418-421.

[21] 段莉琼，朱建军，王庆社，等.改进的最短路径搜索A*算法的高效实现[J].海洋测绘，2004，24（5）：20-22.

[22] DECHTER R， PEARL J. Generalized best-first search strategies and the optimality of A*[J]. Journal of the Acm， 1985，32（3）：505-536.

[23] HART P E， NILSSON N J， RAPHAEL B. Correction to "aformal basis for the heuristic determination of minimum cost paths"[M]. ACM， 1972.

[24] DORIGO M， MANIEZZO V， COLORNI A. Positive feedback as a search strategy [R]. Technical Report， Politecnico di Milano， Italy， 1991.

[25] Gutjahr W J. A graph-based ant system and its convergence[J].Future Generation Computer System， 2000，16（8）：873-888.

[26] STUEZLE T， DORIGO M. A short convergence proof for a class of ant colony optimization algorithms[J].IEEE Transactions on Evolutionary Computation，2002，6（4）：358-365.

[27] 王偉杰.基于蚁群算法的矿井火灾救灾最短路径研究[J].煤炭技术，2012，31（9）：40-41.

[28] 李兴宇.基于蚁群算法的矿井应急救援最短路径研究[J].煤炭技术，2013，32（1）：102-103.

[29] 樊雯婧，卢才武.用群智能算法确定井下火灾多救护队最优路径[J].金属矿山，2014，43（1）：133-136.

[30] 汪金花，张亚静，朱令起，等.井下避险最优路径机理与数学建模研究[J].金属矿山，2013，42（5）：128-130.

[31] 杨琰，廖伟志，李文敬，等.基于Petri网的顾及转向延迟的最优路径算法[J].计算机工程与设计，2013，34（10）：3643-3648.

[32] 李隆庭.基于井下避难碉室系统的煤矿应急模型研究[D].北京：首都经济贸易大学，2012：26-41.

[33] 卢国菊，王飞.矿井火灾时期K则最优避灾路径研究[J].煤矿安全，2013，44（4）：35-37.

[34] 刘勇.基于蚁群算法的应急救援最优路径研究[D].北京：中国地质大学，2010.

[35] 符辉，毛善君，骆云秀.矿井突水蔓延线路生成算法及实现[J].煤炭科学技术，2013，41（3）：104-106.

[36] 赵普生，胡俊粉.井下被困人员救援技术及装备现状分析[J].煤炭科学技术，2009，37（8）：38-45.

[37] 李兴东.矿井火灾时期避灾路线的确定及其应用程序[J].煤矿安全，2001，32（12）：20-22.

[38] 李健威，蔡峰.煤矿井下应急救援与交通指挥系统的研究[J].煤炭科学技术，2011，39（2）：84-88，93.

（责任编辑：黄 健）