基于PgRouting 圖計(jì)算的人員精確定位軌跡還原技術(shù)

閆啟宏 李 健 杜朋浩

（貴州黔西能源開(kāi)發(fā)有限公司，貴州 黔西 551500）

1 引言

煤礦井下人員定位系統(tǒng)在遏制超定員生產(chǎn)、事故應(yīng)急救援、領(lǐng)導(dǎo)下井帶班管理、特種作業(yè)人員管理、防止人員進(jìn)入危險(xiǎn)區(qū)域、及時(shí)發(fā)現(xiàn)未按時(shí)升井人員、持證上崗管理、井下作業(yè)人員考勤等方面發(fā)揮著重要作用。楊娟等（2015）[1]等根據(jù)煤礦井下巷道分布特點(diǎn),應(yīng)用RSSI 定位算法,提出基于節(jié)點(diǎn)協(xié)作的精確定位算法。魏霜（2014）[2]利用煤礦企業(yè)現(xiàn)有的工業(yè)數(shù)據(jù)網(wǎng)絡(luò),基于物聯(lián)網(wǎng)技術(shù)設(shè)計(jì)了一種煤礦井下人員實(shí)時(shí)精確定位系統(tǒng)。

目前市場(chǎng)主流人員精確定位系統(tǒng)的人員軌跡展示，都是基于預(yù)先繪制的預(yù)設(shè)定路徑，即將相鄰定位設(shè)備以一定方式進(jìn)行連接，然后按照預(yù)設(shè)軌跡和當(dāng)前設(shè)備狀態(tài)進(jìn)行人員軌跡計(jì)算，大多采用樹(shù)形結(jié)構(gòu)，其拓?fù)淠Ｐ陀么鎯?chǔ)點(diǎn)和弧段的編號(hào)描述圖形之間的關(guān)系，對(duì)所有可能性路線進(jìn)行窮舉。

這種展示方式存在幾個(gè)問(wèn)題：（1）以定位設(shè)備二維坐標(biāo)為中心，當(dāng)設(shè)備發(fā)生位移或替換后需要重新計(jì)算；（2）設(shè)備坐標(biāo)與巷道拓?fù)潢P(guān)系耦合度高，需要專業(yè)軟件技術(shù)人員進(jìn)行操作，無(wú)法適應(yīng)煤礦動(dòng)態(tài)變化；（3）計(jì)算結(jié)果無(wú)GIS 數(shù)據(jù)庫(kù)支持拓展性不高，無(wú)法進(jìn)行預(yù)設(shè)外的軌跡路徑計(jì)算。

隨著礦山物聯(lián)網(wǎng)技術(shù)的發(fā)展，基于UWB 等窄帶物聯(lián)技術(shù)的人員精確定位硬件解決方案日趨成熟，為井下人員定位的研究[3]提供了新的思路和理論基礎(chǔ)。本文在前人研究的基礎(chǔ)上，以貴州黔西縣青龍煤礦為研究實(shí)例，提出了一種基于pgRouting圖計(jì)算的人員精確定位軌跡還原技術(shù)，精確還原了人員井下運(yùn)動(dòng)軌跡，取得較好效果。

2 PgRouting 簡(jiǎn)介

pgRouting 是 以PostGIS/PostgreSQL 地 理 空 間數(shù)據(jù)庫(kù)為基礎(chǔ)進(jìn)行路徑分析，從起點(diǎn)開(kāi)始計(jì)算與各點(diǎn)的最短路徑和終點(diǎn)的最短路徑之和，逐個(gè)取出找到最短路徑。

pgRouting 安裝先下載編譯包后解壓縮，將lib目錄下文件復(fù)制到PostgreSQL 的lib 目錄下，在PostgreSQL 數(shù)據(jù)庫(kù)中執(zhí)行share/contrib 目錄下的sql腳本即可。

此解決方案優(yōu)點(diǎn)是：數(shù)據(jù)和屬性可由許多客戶端修改，例如QGIS 通過(guò)JDBC、ODBC 或直接使用Pl/pgSQL。數(shù)據(jù)更改可以通過(guò)路由引擎即時(shí)反映，無(wú)需預(yù)先計(jì)算。其核心功能包括：

（1）所有最短路徑組合（Johnson 算法）；

（2）所有最短路徑組合（Floyd-Warshall 算法）；

（3）最短 A* 路徑；

（4）雙向 Dijkstra 最短路徑；

（5）雙向 A* 最短路徑；

（6）Dijkstra 最短路徑；

（7）行車距離；

（8）K-最短路徑，多候選路徑；

（9）K-Dijkstra，一對(duì)多最短路徑；

（10）旅行銷售人員（Traveling Sales Person）；

（11）TRSP（Turn Restriction Shortest Path）。

3 解決思路

3.1 以導(dǎo)向點(diǎn)數(shù)據(jù)構(gòu)建井巷工程拓?fù)潢P(guān)系

煤礦井巷工程是在地質(zhì)體內(nèi)開(kāi)掘的，同一水平巷道存在T 形交叉、Y 形交叉、十字形交叉、X 形交叉、錯(cuò)位交叉等常規(guī)拓?fù)浣Y(jié)構(gòu)。因巷道功能不同，不同水平的井巷工程從空間上存在立體分離式交叉、立體交叉等復(fù)雜的空間關(guān)系。相比地面路網(wǎng)，其拓?fù)潢P(guān)系比路網(wǎng)更加復(fù)雜，空間屬性更強(qiáng)，且井巷工程會(huì)隨著煤礦的生產(chǎn)過(guò)程中開(kāi)拓、打密閉阻斷等過(guò)程，不斷改變現(xiàn)有拓?fù)潢P(guān)系。因此構(gòu)造井巷工程拓?fù)潢P(guān)系的基本數(shù)據(jù)要采用煤礦常用的勘探設(shè)計(jì)數(shù)據(jù)和生產(chǎn)過(guò)程數(shù)據(jù)，便于收集，易于維護(hù)，能夠映射客觀世界。

一般煤礦會(huì)根據(jù)地質(zhì)勘測(cè)資料和礦井設(shè)計(jì)，計(jì)算導(dǎo)向點(diǎn)的坐標(biāo)，并根據(jù)導(dǎo)向點(diǎn)坐標(biāo)來(lái)指導(dǎo)實(shí)際現(xiàn)場(chǎng)施工。地質(zhì)、測(cè)量相關(guān)科室和部門會(huì)根據(jù)實(shí)際施工進(jìn)展情況定期更新和維護(hù)導(dǎo)向點(diǎn)坐標(biāo)，因此可以作為構(gòu)建GIS 空間數(shù)據(jù)的基礎(chǔ)數(shù)據(jù)。

3.2 人員軌跡數(shù)據(jù)的采集

人員定位系統(tǒng)為滿足國(guó)家數(shù)據(jù)采集要求，按《煤礦安全生產(chǎn)在線監(jiān)測(cè)聯(lián)網(wǎng)備查系統(tǒng)通用技術(shù)要求和數(shù)據(jù)采集標(biāo)準(zhǔn)》要求提供數(shù)據(jù)生成工具。該工具可以連接人員定位系統(tǒng)主備機(jī)服務(wù)器，根據(jù)人員數(shù)據(jù)變化情況，生成符合標(biāo)準(zhǔn)格式要求的交換文件。精確定位系統(tǒng)會(huì)根據(jù)人員移動(dòng)情況，生成具有三維坐標(biāo)的軌跡數(shù)據(jù)。

架設(shè)數(shù)據(jù)采集服務(wù)器（圖1），使用Flume 對(duì)交換文件進(jìn)行偵聽(tīng)。當(dāng)每10 s 產(chǎn)生交換文件后，將報(bào)文內(nèi)容抽取至Kafka 消息中間件進(jìn)行數(shù)據(jù)緩存，同時(shí)將數(shù)據(jù)推送給前端GIS 和大數(shù)據(jù)解決方案進(jìn)行持久化。

圖1 人員軌跡數(shù)據(jù)采集

3.3 人員軌跡數(shù)據(jù)還原

如圖2 所示，巷道共有D1～D4 四個(gè)導(dǎo)向點(diǎn)數(shù)據(jù)。P1、P2 為人員精確定位間隔10 s 間推送的2 次坐標(biāo)數(shù)據(jù)。前端渲染頁(yè)面如直接按P1-＞P2 的數(shù)據(jù)進(jìn)行繪制，將產(chǎn)生P1 至P2 虛線效果，與實(shí)際不符。

圖2 人員軌跡數(shù)據(jù)還原

因此，需要對(duì)人員軌跡數(shù)據(jù)坐標(biāo)進(jìn)行還原，即補(bǔ)齊中間缺失的D2、D3 坐標(biāo)數(shù)據(jù)，構(gòu)建P1-＞D2-＞D3-＞P2 的軌跡坐標(biāo)數(shù)據(jù)，使人員模型按照巷道進(jìn)行移動(dòng)。

4 軌跡還原的實(shí)現(xiàn)方法

軌跡還原的技術(shù)路線如圖3 所示。

4.1 以導(dǎo)向點(diǎn)坐標(biāo)構(gòu)建拓?fù)溆?jì)算

根據(jù)采掘工程平面圖，按巷道逐個(gè)提取導(dǎo)向點(diǎn)坐標(biāo)，并構(gòu)造拓?fù)涔?jié)點(diǎn)表。如圖4 所示巷道共由四個(gè)導(dǎo)向點(diǎn)構(gòu)成。

（1）按表1 數(shù)據(jù)結(jié)構(gòu)創(chuàng)建拓?fù)浔恚靡源娣艌D計(jì)算的點(diǎn)坐標(biāo)數(shù)據(jù)。

表1 點(diǎn)坐標(biāo)數(shù)據(jù)表

（2）按巷道，組織導(dǎo)向點(diǎn)數(shù)據(jù)，填充源頂點(diǎn)、目標(biāo)頂點(diǎn)坐標(biāo)。

（3）根據(jù)源頂點(diǎn)、目標(biāo)頂點(diǎn)坐標(biāo)，構(gòu)造線段計(jì)算長(zhǎng)度，并填充cost 字段。

（4）調(diào)用PgRouting 的拓?fù)溆?jì)算函數(shù)pgr_createTopology，對(duì)拓?fù)浔磉M(jìn)行填充，構(gòu)建井巷工程拓?fù)潢P(guān)系。

4.2 基于實(shí)時(shí)數(shù)據(jù)的軌跡繪制

人員軌跡數(shù)據(jù)中人員位置是精確定位系統(tǒng)推送的北京54 坐標(biāo)系的經(jīng)緯度和高程數(shù)據(jù)。根據(jù)兩次推送的坐標(biāo)數(shù)據(jù)對(duì)人員模型以動(dòng)畫(huà)方式進(jìn)行移動(dòng)。需要以下幾個(gè)步驟：

（1）根據(jù)人員坐標(biāo)數(shù)據(jù)查找最近的拓?fù)涔?jié)點(diǎn)ID。根據(jù)導(dǎo)向點(diǎn)數(shù)據(jù)自動(dòng)生成拓?fù)漤旤c(diǎn)表，是PgRouting 的核心數(shù)據(jù)對(duì)象，根據(jù)圖計(jì)算的方式自動(dòng)生成各導(dǎo)向點(diǎn)之間的拓?fù)潢P(guān)系。根據(jù)PostGis 提供的空間計(jì)算函數(shù)stdistance，求取距離開(kāi)始坐標(biāo)最近的拓?fù)涔?jié)點(diǎn)。

（2） 利 用PgRouting 的 圖 計(jì) 算 函 數(shù)pgr_dijkstra，根據(jù)源頂點(diǎn)和目標(biāo)頂點(diǎn)ID，求取途徑的拓?fù)涔?jié)點(diǎn)ID。該函數(shù)可以按開(kāi)始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)，自動(dòng)計(jì)算所有途徑節(jié)點(diǎn)ID 及導(dǎo)向點(diǎn)。

（3）人員軌跡還原。根據(jù)途徑拓?fù)涔?jié)點(diǎn)的坐標(biāo)構(gòu)建途經(jīng)路線，比照人員軌跡數(shù)據(jù)的開(kāi)始坐標(biāo)和結(jié)束坐標(biāo)，對(duì)途經(jīng)路線進(jìn)行截取，并將人員途徑最終軌跡返回。

5 試驗(yàn)效果

基于該技術(shù)的系統(tǒng)在貴州能化青龍煤礦運(yùn)行10個(gè)月，共截取1200 人/天的人員軌跡數(shù)據(jù)進(jìn)行測(cè)試，該算法對(duì)局部巷道復(fù)雜拓?fù)浣Y(jié)構(gòu)、定位分站設(shè)備缺失、人員軌跡數(shù)據(jù)缺失具有極強(qiáng)的魯棒性。平均GIS 人員位置顯示和實(shí)際位置誤差不超過(guò)0.3 m，滿足實(shí)時(shí)性要求。

6 結(jié)論及展望

該技術(shù)以圖技術(shù)為基礎(chǔ)，以煤礦導(dǎo)向點(diǎn)為節(jié)點(diǎn)，根據(jù)連接關(guān)系構(gòu)建邊數(shù)據(jù)，進(jìn)而構(gòu)建空間拓?fù)潢P(guān)系。路徑規(guī)劃不用預(yù)先以窮舉方式進(jìn)行設(shè)定，具體軌跡數(shù)據(jù)還原等算法不依賴于某系統(tǒng)，根據(jù)人員或設(shè)備的絕對(duì)經(jīng)緯度坐標(biāo)即可進(jìn)行軌跡還原。

該技術(shù)可以通過(guò)維護(hù)兩節(jié)點(diǎn)之間的cost、reverse_cost 等屬性，可以動(dòng)態(tài)改變拓?fù)潢P(guān)系，如打密閉或局部發(fā)生災(zāi)變后，可進(jìn)行動(dòng)態(tài)拓?fù)潢P(guān)系計(jì)算，將現(xiàn)有無(wú)向圖動(dòng)態(tài)改變成有向圖應(yīng)用方式，在避災(zāi)路線計(jì)算等應(yīng)急指揮方面也有明顯優(yōu)勢(shì)。