基于室內(nèi)路網(wǎng)的跨樓層路徑規(guī)劃技術(shù)的設(shè)計(jì)與實(shí)現(xiàn)

黃科佳 ,李少杰左 堯蔡文文李紹俊3,宋關(guān)福3,鐘耳順4

(1. 北京超圖軟件股份有限公司,北京 100015;2. 北京航空航天大學(xué),北京 100191;3. 國家測繪局 地理信息基礎(chǔ)軟件與應(yīng)用工程中心,北京100101;4. 中國科學(xué)院地理科學(xué)與資源研究所,北京 100101)

0 引 言

隨著移動互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展以及智能移動終端的普及,基于位置的信息服務(wù)變得流行起來,逐漸為大眾所接受和使用[1-3].同時,隨著室內(nèi)混合智能定位技術(shù)的發(fā)展,室內(nèi)位置服務(wù)需求越來越旺盛.作為室內(nèi)位置服務(wù)的核心技術(shù)之一,室內(nèi)路徑規(guī)劃與導(dǎo)航成為研究和應(yīng)用的熱點(diǎn)[4-6].

室內(nèi)路徑規(guī)劃是從復(fù)雜的室內(nèi)環(huán)境中,找到起點(diǎn)到終點(diǎn)之間滿足一定約束條件的有效的最優(yōu)路徑,它可以結(jié)合室內(nèi)定位技術(shù)與移動通信技術(shù),實(shí)現(xiàn)室內(nèi)實(shí)時動態(tài)導(dǎo)航,支撐室內(nèi)公共安全、應(yīng)急救援、商業(yè)智能和大眾服務(wù)等應(yīng)用[7-8].如當(dāng)我們置身于大型商場和機(jī)場等復(fù)雜建筑物的內(nèi)部時,室內(nèi)路徑規(guī)劃技術(shù)可以利用精確的定位技術(shù)確定我們的位置,并基于室內(nèi)地圖和路網(wǎng)數(shù)據(jù),利用最優(yōu)路徑算法計(jì)算位置之間的有效路徑,從而幫助我們找到和到達(dá)指定的地點(diǎn)(衛(wèi)生間、ATM和商家等).

但是,一些路徑規(guī)劃技術(shù)往往基于單層網(wǎng)絡(luò)拓?fù)淠Ｐ投O(shè)計(jì),由于模型缺少樓層之間的連通信息,而不能實(shí)現(xiàn)跨樓層導(dǎo)航算法分析.后來,隨著跨樓層導(dǎo)航算法的出現(xiàn),跨樓層的路徑規(guī)劃、導(dǎo)航及定位得以實(shí)現(xiàn)[4,7-9].但這些傳統(tǒng)跨樓層導(dǎo)航算法基于樓層連接通達(dá)規(guī)則,往往需要多次遍歷樓層信息.具體來說,首先,將室內(nèi)道路拓?fù)渖蓡我粯菍勇肪W(wǎng)文件,按照多個樓層通達(dá)規(guī)則,通過與上一個樓梯或下一個樓梯的連接信息互相將樓層關(guān)聯(lián)起來,組織成數(shù)據(jù)結(jié)構(gòu)獨(dú)立、存儲結(jié)構(gòu)共用的統(tǒng)一路網(wǎng)分析文件.在路徑分析時根據(jù)起點(diǎn)坐標(biāo)和當(dāng)前樓層連通的其他任一樓層的樓梯坐標(biāo),遍歷出當(dāng)前樓層和接近目的地樓層的下一個樓層連接耗費(fèi)最少的連接點(diǎn)坐標(biāo);然后,通過該連接點(diǎn)啟動遍歷下一個接近目的地樓層的最近連接點(diǎn),找出最近的連接點(diǎn)并更新之前的連接耗費(fèi),按照此樓層連接信息遍歷規(guī)則,繼續(xù)遍歷更加靠近目的地所在的樓層,找到目的地所在樓層后,再根據(jù)單樓層內(nèi)兩點(diǎn)最佳路徑分析算法找到耗費(fèi)最少的路徑,將目的地樓層的這條路徑和目的地樓層上一次通過其他樓層到達(dá)目的地的路徑做比較,存在更少耗費(fèi)的路徑則更新上一樓層的連接點(diǎn)坐標(biāo).按照此遍歷規(guī)則直到將最少耗費(fèi)遍歷至起點(diǎn),得到連接室內(nèi)跨樓層目的地和起點(diǎn)的最短距離路徑[9-11].該方法基于單層路網(wǎng)通過樓梯關(guān)聯(lián)單層路網(wǎng)的連通規(guī)則,路徑分析結(jié)果準(zhǔn)確,但路徑分析空間復(fù)雜度較大,路徑分析耗費(fèi)時間也較長.此外,跨樓層導(dǎo)航網(wǎng)絡(luò)模型設(shè)計(jì)還面對著多樓層間相對坐標(biāo)不一致的情況.

針對這些問題,本文研究設(shè)計(jì)了多層網(wǎng)絡(luò)拓?fù)淠Ｐ?將樓層與樓層、樓梯與樓梯的路由連接信息構(gòu)建成樓層聯(lián)通網(wǎng)絡(luò),并提取聯(lián)通網(wǎng)絡(luò)生成跨多層路網(wǎng)的路網(wǎng)分析模型文件,通過逐層分析的方法實(shí)現(xiàn)跨樓層的路徑規(guī)劃.本方法在路徑分析時,不需要多次遍歷單樓層和其他樓層的連通性,直接從路網(wǎng)分析模型獲取即可,降低了路徑分析的空間復(fù)雜度,同時也降低了搜索連通樓梯的時間耗費(fèi).另外,本研究還基于多次網(wǎng)絡(luò)分析法,將多點(diǎn)路徑規(guī)劃拆分成多次進(jìn)行分析,以支持跨樓層、多站點(diǎn)路徑導(dǎo)航、規(guī)劃.

1 跨樓層路徑規(guī)劃算法的設(shè)計(jì)

1.1 跨樓層路網(wǎng)的生成和位置點(diǎn)接收

跨樓層路網(wǎng)生成模塊,主要完成室內(nèi)地圖數(shù)據(jù)的獲取,并生成多層道路網(wǎng)絡(luò)數(shù)據(jù)和樓層間的垂直連通數(shù)據(jù),如圖1所示.它將原始的室內(nèi)GIS地圖數(shù)據(jù)進(jìn)行分層處理,生成多層網(wǎng)絡(luò)拓?fù)淠Ｐ?用于后續(xù)的路徑規(guī)劃分析.同時,從原始地圖數(shù)據(jù)的樓梯、電梯、扶梯等數(shù)據(jù)中提取出所有樓梯的連通信息,根據(jù)樓梯樓層信息(如樓層ID),生成樓層間的連通信息表,并將樓層連通信息、樓梯類型信息、位置信息等生成樓層連通數(shù)據(jù)庫,用于之后的跨樓層的路徑分析.

圖1 數(shù)據(jù)處理流程Fig.1 Data processing fl ow

位置點(diǎn)接收模塊,接收用戶輸入的位置信息.位置信息由室內(nèi)定位信號提供,基于手持設(shè)備的氣壓計(jì)和地磁傳感源,然后通過無線Wifi技術(shù)獲取高程信息,結(jié)合樓層高程表匹配用戶點(diǎn)所在的樓層.最后,根據(jù)通信協(xié)議,將其轉(zhuǎn)換成地理坐標(biāo).如果只進(jìn)行兩點(diǎn)之間的最優(yōu)路徑規(guī)劃,則位置信息只需要包括起點(diǎn)和終點(diǎn)的地理坐標(biāo).如果需要進(jìn)行多點(diǎn)路徑規(guī)劃,則還應(yīng)該至少包括1個途經(jīng)點(diǎn)的坐標(biāo)位置.

1.2 跨樓層路徑規(guī)劃的設(shè)計(jì)

網(wǎng)絡(luò)分析模塊,采用雙向遍歷的A*最短路徑分析算法[12-14],進(jìn)行跨樓層多途經(jīng)點(diǎn)路徑規(guī)劃如圖2所示.系統(tǒng)首先判斷用戶輸入的起點(diǎn)和終點(diǎn)是否在同一樓層,若是,則進(jìn)行單次路徑分析,從該起點(diǎn)所在樓層的道路網(wǎng)絡(luò)數(shù)據(jù)中選擇滿足距離最近、通行時間最短、運(yùn)輸費(fèi)用最低、行駛最安全和/或通行容量最大等不同約束條件的路徑,作為所述起點(diǎn)與終點(diǎn)之間的路徑規(guī)劃.

圖2 網(wǎng)絡(luò)分析流程圖Fig.2 Flow chart of network analysis

如果起點(diǎn)和終點(diǎn)不在同一樓層,則從樓層連通數(shù)據(jù)庫中選擇滿足前述約束條件的連通起點(diǎn)樓層和終點(diǎn)樓層的垂直連通設(shè)施(如樓梯等);分別從起點(diǎn)和終點(diǎn)樓層的道路網(wǎng)絡(luò)數(shù)據(jù)中選擇滿足預(yù)設(shè)條件的起點(diǎn)位置與起點(diǎn)樓層的垂直連通設(shè)施(如樓梯)位置之間的路徑L1、終點(diǎn)樓層的垂直連通設(shè)施(如樓梯)位置與終點(diǎn)位置之間的路徑L2;連接路徑L1、樓層間的垂直連通設(shè)施形成的通道和路徑L2,得到所述起點(diǎn)與終點(diǎn)之間的路徑規(guī)劃.

1.3 跨樓層路徑規(guī)劃的循環(huán)控制

如果輸入的位置信息中包括至少1個途經(jīng)點(diǎn),那么將進(jìn)行多途經(jīng)點(diǎn)分析.多途經(jīng)點(diǎn)分析是利用多次網(wǎng)絡(luò)分析,將多點(diǎn)路徑規(guī)劃拆分為多次分析,并基于分析結(jié)果高效地實(shí)現(xiàn)了路徑引導(dǎo)功能,從而實(shí)現(xiàn)帶有途經(jīng)點(diǎn)的多點(diǎn)路徑規(guī)劃.

循環(huán)控制模塊的作用就是在位置點(diǎn)接收模塊收到用戶輸入的位置點(diǎn)之后,按起點(diǎn)、途經(jīng)點(diǎn)和終點(diǎn)的順序依次獲取2個位置點(diǎn)分別作為新的起點(diǎn)和終點(diǎn),循環(huán)調(diào)度網(wǎng)絡(luò)分析模塊建立所述新的起點(diǎn)和終點(diǎn)之間的路徑規(guī)劃,并將所有路徑連接起來作為最終的路徑規(guī)劃結(jié)果.

為方便描述,本文以垂直連通設(shè)施中的樓梯為例說明多途經(jīng)點(diǎn)分析的具體流程,如圖3所示.根據(jù)用戶輸入信息,判斷當(dāng)前起點(diǎn)和終點(diǎn)是否在同一樓層;若是,則從當(dāng)前起點(diǎn)樓層的道路網(wǎng)絡(luò)數(shù)據(jù)中選擇滿足約束條件的路徑L0,作為當(dāng)前起點(diǎn)與終點(diǎn)之間的路徑規(guī)劃.若不是,則在多層道路網(wǎng)絡(luò)數(shù)據(jù)和樓層間的垂直連通數(shù)據(jù)中,選擇滿足約束條件的連通當(dāng)前起點(diǎn)和終點(diǎn)所在樓層的樓梯,以及當(dāng)前起點(diǎn)與樓梯位置之間的路徑L1,和當(dāng)前終點(diǎn)樓層的樓梯位置與當(dāng)前終點(diǎn)之間的路徑L2,連接路徑L1、樓梯形成的通道L3和路徑L2,得到當(dāng)前起點(diǎn)與終點(diǎn)之間的路徑規(guī)劃;如此循環(huán),直到判斷出當(dāng)前終點(diǎn)是用戶輸入的終點(diǎn)為止.

圖3 多途經(jīng)點(diǎn)分析流程圖Fig.3 Flow chart of multi-path point analysis

最后,為了進(jìn)一步提高算法效率,本研究還采用分塊數(shù)據(jù)組織方法,通過查詢單位空間范圍(512X512像素區(qū)域)替代查詢?nèi)晥D區(qū)域,降低查詢時檢索數(shù)據(jù)庫的讀表數(shù)目,大幅度降低搜索最近節(jié)點(diǎn)坐標(biāo)的耗時;通過單位空間區(qū)域的管理,復(fù)用了節(jié)點(diǎn)坐標(biāo)數(shù)據(jù),直接通過內(nèi)存數(shù)組線性存儲,提高路網(wǎng)節(jié)點(diǎn)坐標(biāo)數(shù)據(jù)的存取效率.然后還采用了雙向搜索算法,在延續(xù)A*啟發(fā)式算法自適應(yīng)特點(diǎn)的同時,由于兩個方向過濾的結(jié)果更早地接近最終結(jié)果,在搜索空間上約減少近一半,由于搜索的空間范圍大大地減少,在搜索時間復(fù)雜度上減少約3/4.與非雙向A*算法相比,雙向A*算法成功搜索到最優(yōu)路徑時,參與搜索的路網(wǎng)節(jié)點(diǎn)數(shù)目減少,生成最優(yōu)結(jié)果的時間縮短.

2 跨樓層路徑規(guī)劃算法的實(shí)現(xiàn)

本研究以北京市某大型商場數(shù)據(jù)為例,該數(shù)據(jù)包括地面六層購物區(qū)域,每層區(qū)域建立獨(dú)立的地圖數(shù)據(jù)和路網(wǎng)數(shù)據(jù),基于室內(nèi)藍(lán)牙、Wi-Fi信號、地磁場等定位技術(shù),獲得移動設(shè)備的室內(nèi)坐標(biāo),傳入算法分析系統(tǒng),并通過二三維一體化進(jìn)行展示數(shù)據(jù).系統(tǒng)支持位置的自動搜索、商鋪查詢以及電梯信息展示等功能.

2.1 實(shí)驗(yàn)環(huán)境與方法

本研究基于面向?qū)ο蠹夹g(shù)、算法設(shè)計(jì)技術(shù)、數(shù)據(jù)庫技術(shù)來實(shí)現(xiàn)不同樓層之間多個途經(jīng)點(diǎn)的實(shí)時導(dǎo)航功能.系統(tǒng)實(shí)驗(yàn)使用Supermap iServer 8C+tomcat7.0 32位作為室內(nèi)定位服務(wù)器的開發(fā)以及部署環(huán)境,使用Eclipse 4.3 32位+Android SDK 4.3作為室內(nèi)路徑分析和地圖導(dǎo)航系統(tǒng)的開發(fā)環(huán)境,通過MongoDB 3.0 32位+SQLite 32位進(jìn)行數(shù)據(jù)存儲和管理.

實(shí)驗(yàn)通過藍(lán)牙定位或Wi-Fi信號強(qiáng)度定位或者地磁場強(qiáng)定位等技術(shù),獲取移動智能終端(Android/iPhone/Windows Phone)的位置,采集定位粗差數(shù)據(jù),并將數(shù)據(jù)上傳至Supermap iServer服務(wù)器,通過查詢服務(wù)器在初始化階段導(dǎo)入的完整數(shù)據(jù)庫表,獲取真實(shí)室內(nèi)定位的坐標(biāo).然后,基于實(shí)際導(dǎo)航場景(路線分析導(dǎo)航、目的地分析導(dǎo)航、偏航分析導(dǎo)航等方法)確定路徑分析的起點(diǎn)和終點(diǎn)以及途經(jīng)點(diǎn),調(diào)用路徑分析接口進(jìn)行實(shí)時分析.并將分析結(jié)果實(shí)時展示在地圖中,支持導(dǎo)航模式切換.導(dǎo)航過程通過循環(huán)控制模塊確定分析結(jié)果的準(zhǔn)確性和實(shí)時性.如果路線發(fā)生偏移或者行走路線改變,系統(tǒng)還會智能地實(shí)時更新路徑分析起點(diǎn)和途經(jīng)點(diǎn),分析最優(yōu)路徑并進(jìn)行繼續(xù)導(dǎo)航服務(wù),直至系統(tǒng)導(dǎo)航到目的地.

2.2 實(shí)驗(yàn)結(jié)果與分析

本研究實(shí)驗(yàn)分析得到2 941條單一道路數(shù)據(jù),并將其制作成矢量數(shù)據(jù)集,用于導(dǎo)航服務(wù)和查詢服務(wù)的底圖和路徑分析的路網(wǎng)模型.然后,將得到的4173條Wi-Fi和基站信號強(qiáng)度制作成指紋數(shù)據(jù)庫,作為匹配定位算法的參照.最后,為了進(jìn)一步說明本算法對于跨樓層室內(nèi)導(dǎo)航算法性能的提升,我們將本文算法與傳統(tǒng)室內(nèi)路徑規(guī)劃算法進(jìn)行性能對比,對比測試結(jié)果見表1.

表1 兩種導(dǎo)航算法測試結(jié)果Tab.1 The test results of two navigation methods

我們發(fā)現(xiàn),本研究的路徑分析算法在多線程資源充分利用的前提下,平均下載速度比傳統(tǒng)室內(nèi)路徑規(guī)劃算法快14%左右.并且在路網(wǎng)節(jié)點(diǎn)的個數(shù)越多時即數(shù)據(jù)量越大時,平均路徑分析時間越少,用戶體驗(yàn)越好.

2.3 結(jié)果展示

將獲取路徑規(guī)劃的路線結(jié)果和當(dāng)前用戶的位置結(jié)果通過圖形繪制接口繪制到終端屏幕,呈現(xiàn)給用戶瀏覽,以及響應(yīng)UI交互動作.如導(dǎo)航過程中,分別將導(dǎo)航路線構(gòu)造成一條線符號對象,導(dǎo)航位置構(gòu)造成一個復(fù)合CAD點(diǎn)符號對象,導(dǎo)航起終點(diǎn)構(gòu)造成兩個點(diǎn)符號對象,通過圖形繪制接口OpenGL將符號映射成紋理對象并拷貝到屏幕進(jìn)行顯示;實(shí)時導(dǎo)航路段和衛(wèi)星導(dǎo)航信號等導(dǎo)航引導(dǎo)信息構(gòu)造成窗體界面模板,直接獲取路徑規(guī)劃的結(jié)果并實(shí)時加載到模板進(jìn)行顯示,如圖4所示.

圖4 室內(nèi)跨樓層路徑規(guī)劃實(shí)現(xiàn)圖Fig.4 The realization of indoor navigation

3 結(jié)束語

目前,路徑規(guī)劃技術(shù)往往基于單層路網(wǎng)而設(shè)計(jì),只能實(shí)現(xiàn)單一樓層的路線規(guī)劃,不支持跨樓層的路徑規(guī)劃.基于此,本研究基于逐層分析的方法來實(shí)現(xiàn)各個樓層的路徑規(guī)劃算法,實(shí)現(xiàn)跨樓層位置點(diǎn)之間的路徑規(guī)劃.同時,通過設(shè)置途經(jīng)點(diǎn)的方式,實(shí)現(xiàn)室內(nèi)跨樓層的多點(diǎn)位置服務(wù),從而進(jìn)一步完善室內(nèi)跨樓層位置服務(wù),為用戶提供更好的室內(nèi)位置服務(wù).本文方法可以解決現(xiàn)有技術(shù)不支持跨樓層多點(diǎn)路徑分析的問題,實(shí)現(xiàn)室內(nèi)跨樓層的多點(diǎn)位置服務(wù),從而能夠進(jìn)一步為用戶提供更好的室內(nèi)位置服務(wù).