基于PgRouting 图计算的人员精确定位轨迹还原技术

闫启宏 李 健 杜朋浩

（贵州黔西能源开发有限公司，贵州 黔西 551500）

1 引言

煤矿井下人员定位系统在遏制超定员生产、事故应急救援、领导下井带班管理、特种作业人员管理、防止人员进入危险区域、及时发现未按时升井人员、持证上岗管理、井下作业人员考勤等方面发挥着重要作用。杨娟等（2015）[1]等根据煤矿井下巷道分布特点,应用RSSI 定位算法,提出基于节点协作的精确定位算法。魏霜（2014）[2]利用煤矿企业现有的工业数据网络,基于物联网技术设计了一种煤矿井下人员实时精确定位系统。

目前市场主流人员精确定位系统的人员轨迹展示，都是基于预先绘制的预设定路径，即将相邻定位设备以一定方式进行连接，然后按照预设轨迹和当前设备状态进行人员轨迹计算，大多采用树形结构，其拓扑模型用存储点和弧段的编号描述图形之间的关系，对所有可能性路线进行穷举。

这种展示方式存在几个问题：（1）以定位设备二维坐标为中心，当设备发生位移或替换后需要重新计算；（2）设备坐标与巷道拓扑关系耦合度高，需要专业软件技术人员进行操作，无法适应煤矿动态变化；（3）计算结果无GIS 数据库支持拓展性不高，无法进行预设外的轨迹路径计算。

随着矿山物联网技术的发展，基于UWB 等窄带物联技术的人员精确定位硬件解决方案日趋成熟，为井下人员定位的研究[3]提供了新的思路和理论基础。本文在前人研究的基础上，以贵州黔西县青龙煤矿为研究实例，提出了一种基于pgRouting图计算的人员精确定位轨迹还原技术，精确还原了人员井下运动轨迹，取得较好效果。

2 PgRouting 简介

pgRouting 是 以PostGIS/PostgreSQL 地 理 空 间数据库为基础进行路径分析，从起点开始计算与各点的最短路径和终点的最短路径之和，逐个取出找到最短路径。

pgRouting 安装先下载编译包后解压缩，将lib目录下文件复制到PostgreSQL 的lib 目录下，在PostgreSQL 数据库中执行share/contrib 目录下的sql脚本即可。

此解决方案优点是：数据和属性可由许多客户端修改，例如QGIS 通过JDBC、ODBC 或直接使用Pl/pgSQL。数据更改可以通过路由引擎即时反映，无需预先计算。其核心功能包括：

（1）所有最短路径组合（Johnson 算法）；

（2）所有最短路径组合（Floyd-Warshall 算法）；

（3）最短 A* 路径；

（4）双向 Dijkstra 最短路径；

（5）双向 A* 最短路径；

（6）Dijkstra 最短路径；

（7）行车距离；

（8）K-最短路径，多候选路径；

（9）K-Dijkstra，一对多最短路径；

（10）旅行销售人员（Traveling Sales Person）；

（11）TRSP（Turn Restriction Shortest Path）。

3 解决思路

3.1 以导向点数据构建井巷工程拓扑关系

煤矿井巷工程是在地质体内开掘的，同一水平巷道存在T 形交叉、Y 形交叉、十字形交叉、X 形交叉、错位交叉等常规拓扑结构。因巷道功能不同，不同水平的井巷工程从空间上存在立体分离式交叉、立体交叉等复杂的空间关系。相比地面路网，其拓扑关系比路网更加复杂，空间属性更强，且井巷工程会随着煤矿的生产过程中开拓、打密闭阻断等过程，不断改变现有拓扑关系。因此构造井巷工程拓扑关系的基本数据要采用煤矿常用的勘探设计数据和生产过程数据，便于收集，易于维护，能够映射客观世界。

一般煤矿会根据地质勘测资料和矿井设计，计算导向点的坐标，并根据导向点坐标来指导实际现场施工。地质、测量相关科室和部门会根据实际施工进展情况定期更新和维护导向点坐标，因此可以作为构建GIS 空间数据的基础数据。

3.2 人员轨迹数据的采集

人员定位系统为满足国家数据采集要求，按《煤矿安全生产在线监测联网备查系统通用技术要求和数据采集标准》要求提供数据生成工具。该工具可以连接人员定位系统主备机服务器，根据人员数据变化情况，生成符合标准格式要求的交换文件。精确定位系统会根据人员移动情况，生成具有三维坐标的轨迹数据。

架设数据采集服务器（图1），使用Flume 对交换文件进行侦听。当每10 s 产生交换文件后，将报文内容抽取至Kafka 消息中间件进行数据缓存，同时将数据推送给前端GIS 和大数据解决方案进行持久化。

图1 人员轨迹数据采集

3.3 人员轨迹数据还原

如图2 所示，巷道共有D1～D4 四个导向点数据。P1、P2 为人员精确定位间隔10 s 间推送的2 次坐标数据。前端渲染页面如直接按P1-＞P2 的数据进行绘制，将产生P1 至P2 虚线效果，与实际不符。

图2 人员轨迹数据还原

因此，需要对人员轨迹数据坐标进行还原，即补齐中间缺失的D2、D3 坐标数据，构建P1-＞D2-＞D3-＞P2 的轨迹坐标数据，使人员模型按照巷道进行移动。

4 轨迹还原的实现方法

轨迹还原的技术路线如图3 所示。

4.1 以导向点坐标构建拓扑计算

根据采掘工程平面图，按巷道逐个提取导向点坐标，并构造拓扑节点表。如图4 所示巷道共由四个导向点构成。

（1）按表1 数据结构创建拓扑表，用以存放图计算的点坐标数据。

表1 点坐标数据表

（2）按巷道，组织导向点数据，填充源顶点、目标顶点坐标。

（3）根据源顶点、目标顶点坐标，构造线段计算长度，并填充cost 字段。

（4）调用PgRouting 的拓扑计算函数pgr_createTopology，对拓扑表进行填充，构建井巷工程拓扑关系。

4.2 基于实时数据的轨迹绘制

人员轨迹数据中人员位置是精确定位系统推送的北京54 坐标系的经纬度和高程数据。根据两次推送的坐标数据对人员模型以动画方式进行移动。需要以下几个步骤：

（1）根据人员坐标数据查找最近的拓扑节点ID。根据导向点数据自动生成拓扑顶点表，是PgRouting 的核心数据对象，根据图计算的方式自动生成各导向点之间的拓扑关系。根据PostGis 提供的空间计算函数stdistance，求取距离开始坐标最近的拓扑节点。

（2） 利 用PgRouting 的 图 计 算 函 数pgr_dijkstra，根据源顶点和目标顶点ID，求取途径的拓扑节点ID。该函数可以按开始节点和结束节点，自动计算所有途径节点ID 及导向点。

（3）人员轨迹还原。根据途径拓扑节点的坐标构建途经路线，比照人员轨迹数据的开始坐标和结束坐标，对途经路线进行截取，并将人员途径最终轨迹返回。

5 试验效果

基于该技术的系统在贵州能化青龙煤矿运行10个月，共截取1200 人/天的人员轨迹数据进行测试，该算法对局部巷道复杂拓扑结构、定位分站设备缺失、人员轨迹数据缺失具有极强的鲁棒性。平均GIS 人员位置显示和实际位置误差不超过0.3 m，满足实时性要求。

6 结论及展望

该技术以图技术为基础，以煤矿导向点为节点，根据连接关系构建边数据，进而构建空间拓扑关系。路径规划不用预先以穷举方式进行设定，具体轨迹数据还原等算法不依赖于某系统，根据人员或设备的绝对经纬度坐标即可进行轨迹还原。

该技术可以通过维护两节点之间的cost、reverse_cost 等属性，可以动态改变拓扑关系，如打密闭或局部发生灾变后，可进行动态拓扑关系计算，将现有无向图动态改变成有向图应用方式，在避灾路线计算等应急指挥方面也有明显优势。