基于室内路网的跨楼层路径规划技术的设计与实现

黄科佳 ,李少杰左 尧蔡文文李绍俊3,宋关福3,钟耳顺4

(1. 北京超图软件股份有限公司,北京 100015;2. 北京航空航天大学,北京 100191;3. 国家测绘局 地理信息基础软件与应用工程中心,北京100101;4. 中国科学院地理科学与资源研究所,北京 100101)

0 引 言

随着移动互联网技术的不断发展以及智能移动终端的普及,基于位置的信息服务变得流行起来,逐渐为大众所接受和使用[1-3].同时,随着室内混合智能定位技术的发展,室内位置服务需求越来越旺盛.作为室内位置服务的核心技术之一,室内路径规划与导航成为研究和应用的热点[4-6].

室内路径规划是从复杂的室内环境中,找到起点到终点之间满足一定约束条件的有效的最优路径,它可以结合室内定位技术与移动通信技术,实现室内实时动态导航,支撑室内公共安全、应急救援、商业智能和大众服务等应用[7-8].如当我们置身于大型商场和机场等复杂建筑物的内部时,室内路径规划技术可以利用精确的定位技术确定我们的位置,并基于室内地图和路网数据,利用最优路径算法计算位置之间的有效路径,从而帮助我们找到和到达指定的地点(卫生间、ATM和商家等).

但是,一些路径规划技术往往基于单层网络拓扑模型而设计,由于模型缺少楼层之间的连通信息,而不能实现跨楼层导航算法分析.后来,随着跨楼层导航算法的出现,跨楼层的路径规划、导航及定位得以实现[4,7-9].但这些传统跨楼层导航算法基于楼层连接通达规则,往往需要多次遍历楼层信息.具体来说,首先,将室内道路拓扑生成单一楼层路网文件,按照多个楼层通达规则,通过与上一个楼梯或下一个楼梯的连接信息互相将楼层关联起来,组织成数据结构独立、存储结构共用的统一路网分析文件.在路径分析时根据起点坐标和当前楼层连通的其他任一楼层的楼梯坐标,遍历出当前楼层和接近目的地楼层的下一个楼层连接耗费最少的连接点坐标;然后,通过该连接点启动遍历下一个接近目的地楼层的最近连接点,找出最近的连接点并更新之前的连接耗费,按照此楼层连接信息遍历规则,继续遍历更加靠近目的地所在的楼层,找到目的地所在楼层后,再根据单楼层内两点最佳路径分析算法找到耗费最少的路径,将目的地楼层的这条路径和目的地楼层上一次通过其他楼层到达目的地的路径做比较,存在更少耗费的路径则更新上一楼层的连接点坐标.按照此遍历规则直到将最少耗费遍历至起点,得到连接室内跨楼层目的地和起点的最短距离路径[9-11].该方法基于单层路网通过楼梯关联单层路网的连通规则,路径分析结果准确,但路径分析空间复杂度较大,路径分析耗费时间也较长.此外,跨楼层导航网络模型设计还面对着多楼层间相对坐标不一致的情况.

针对这些问题,本文研究设计了多层网络拓扑模型,将楼层与楼层、楼梯与楼梯的路由连接信息构建成楼层联通网络,并提取联通网络生成跨多层路网的路网分析模型文件,通过逐层分析的方法实现跨楼层的路径规划.本方法在路径分析时,不需要多次遍历单楼层和其他楼层的连通性,直接从路网分析模型获取即可,降低了路径分析的空间复杂度,同时也降低了搜索连通楼梯的时间耗费.另外,本研究还基于多次网络分析法,将多点路径规划拆分成多次进行分析,以支持跨楼层、多站点路径导航、规划.

1 跨楼层路径规划算法的设计

1.1 跨楼层路网的生成和位置点接收

跨楼层路网生成模块,主要完成室内地图数据的获取,并生成多层道路网络数据和楼层间的垂直连通数据,如图1所示.它将原始的室内GIS地图数据进行分层处理,生成多层网络拓扑模型,用于后续的路径规划分析.同时,从原始地图数据的楼梯、电梯、扶梯等数据中提取出所有楼梯的连通信息,根据楼梯楼层信息(如楼层ID),生成楼层间的连通信息表,并将楼层连通信息、楼梯类型信息、位置信息等生成楼层连通数据库,用于之后的跨楼层的路径分析.

图1 数据处理流程Fig.1 Data processing fl ow

位置点接收模块,接收用户输入的位置信息.位置信息由室内定位信号提供,基于手持设备的气压计和地磁传感源,然后通过无线Wifi技术获取高程信息,结合楼层高程表匹配用户点所在的楼层.最后,根据通信协议,将其转换成地理坐标.如果只进行两点之间的最优路径规划,则位置信息只需要包括起点和终点的地理坐标.如果需要进行多点路径规划,则还应该至少包括1个途经点的坐标位置.

1.2 跨楼层路径规划的设计

网络分析模块,采用双向遍历的A*最短路径分析算法[12-14],进行跨楼层多途经点路径规划如图2所示.系统首先判断用户输入的起点和终点是否在同一楼层,若是,则进行单次路径分析,从该起点所在楼层的道路网络数据中选择满足距离最近、通行时间最短、运输费用最低、行驶最安全和/或通行容量最大等不同约束条件的路径,作为所述起点与终点之间的路径规划.

图2 网络分析流程图Fig.2 Flow chart of network analysis

如果起点和终点不在同一楼层,则从楼层连通数据库中选择满足前述约束条件的连通起点楼层和终点楼层的垂直连通设施(如楼梯等);分别从起点和终点楼层的道路网络数据中选择满足预设条件的起点位置与起点楼层的垂直连通设施(如楼梯)位置之间的路径L1、终点楼层的垂直连通设施(如楼梯)位置与终点位置之间的路径L2;连接路径L1、楼层间的垂直连通设施形成的通道和路径L2,得到所述起点与终点之间的路径规划.

1.3 跨楼层路径规划的循环控制

如果输入的位置信息中包括至少1个途经点,那么将进行多途经点分析.多途经点分析是利用多次网络分析,将多点路径规划拆分为多次分析,并基于分析结果高效地实现了路径引导功能,从而实现带有途经点的多点路径规划.

循环控制模块的作用就是在位置点接收模块收到用户输入的位置点之后,按起点、途经点和终点的顺序依次获取2个位置点分别作为新的起点和终点,循环调度网络分析模块建立所述新的起点和终点之间的路径规划,并将所有路径连接起来作为最终的路径规划结果.

为方便描述,本文以垂直连通设施中的楼梯为例说明多途经点分析的具体流程,如图3所示.根据用户输入信息,判断当前起点和终点是否在同一楼层;若是,则从当前起点楼层的道路网络数据中选择满足约束条件的路径L0,作为当前起点与终点之间的路径规划.若不是,则在多层道路网络数据和楼层间的垂直连通数据中,选择满足约束条件的连通当前起点和终点所在楼层的楼梯,以及当前起点与楼梯位置之间的路径L1,和当前终点楼层的楼梯位置与当前终点之间的路径L2,连接路径L1、楼梯形成的通道L3和路径L2,得到当前起点与终点之间的路径规划;如此循环,直到判断出当前终点是用户输入的终点为止.

图3 多途经点分析流程图Fig.3 Flow chart of multi-path point analysis

最后,为了进一步提高算法效率,本研究还采用分块数据组织方法,通过查询单位空间范围(512X512像素区域)替代查询全视图区域,降低查询时检索数据库的读表数目,大幅度降低搜索最近节点坐标的耗时;通过单位空间区域的管理,复用了节点坐标数据,直接通过内存数组线性存储,提高路网节点坐标数据的存取效率.然后还采用了双向搜索算法,在延续A*启发式算法自适应特点的同时,由于两个方向过滤的结果更早地接近最终结果,在搜索空间上约减少近一半,由于搜索的空间范围大大地减少,在搜索时间复杂度上减少约3/4.与非双向A*算法相比,双向A*算法成功搜索到最优路径时,参与搜索的路网节点数目减少,生成最优结果的时间缩短.

2 跨楼层路径规划算法的实现

本研究以北京市某大型商场数据为例,该数据包括地面六层购物区域,每层区域建立独立的地图数据和路网数据,基于室内蓝牙、Wi-Fi信号、地磁场等定位技术,获得移动设备的室内坐标,传入算法分析系统,并通过二三维一体化进行展示数据.系统支持位置的自动搜索、商铺查询以及电梯信息展示等功能.

2.1 实验环境与方法

本研究基于面向对象技术、算法设计技术、数据库技术来实现不同楼层之间多个途经点的实时导航功能.系统实验使用Supermap iServer 8C+tomcat7.0 32位作为室内定位服务器的开发以及部署环境,使用Eclipse 4.3 32位+Android SDK 4.3作为室内路径分析和地图导航系统的开发环境,通过MongoDB 3.0 32位+SQLite 32位进行数据存储和管理.

实验通过蓝牙定位或Wi-Fi信号强度定位或者地磁场强定位等技术,获取移动智能终端(Android/iPhone/Windows Phone)的位置,采集定位粗差数据,并将数据上传至Supermap iServer服务器,通过查询服务器在初始化阶段导入的完整数据库表,获取真实室内定位的坐标.然后,基于实际导航场景(路线分析导航、目的地分析导航、偏航分析导航等方法)确定路径分析的起点和终点以及途经点,调用路径分析接口进行实时分析.并将分析结果实时展示在地图中,支持导航模式切换.导航过程通过循环控制模块确定分析结果的准确性和实时性.如果路线发生偏移或者行走路线改变,系统还会智能地实时更新路径分析起点和途经点,分析最优路径并进行继续导航服务,直至系统导航到目的地.

2.2 实验结果与分析

本研究实验分析得到2 941条单一道路数据,并将其制作成矢量数据集,用于导航服务和查询服务的底图和路径分析的路网模型.然后,将得到的4173条Wi-Fi和基站信号强度制作成指纹数据库,作为匹配定位算法的参照.最后,为了进一步说明本算法对于跨楼层室内导航算法性能的提升,我们将本文算法与传统室内路径规划算法进行性能对比,对比测试结果见表1.

表1 两种导航算法测试结果Tab.1 The test results of two navigation methods

我们发现,本研究的路径分析算法在多线程资源充分利用的前提下,平均下载速度比传统室内路径规划算法快14%左右.并且在路网节点的个数越多时即数据量越大时,平均路径分析时间越少,用户体验越好.

2.3 结果展示

将获取路径规划的路线结果和当前用户的位置结果通过图形绘制接口绘制到终端屏幕,呈现给用户浏览,以及响应UI交互动作.如导航过程中,分别将导航路线构造成一条线符号对象,导航位置构造成一个复合CAD点符号对象,导航起终点构造成两个点符号对象,通过图形绘制接口OpenGL将符号映射成纹理对象并拷贝到屏幕进行显示;实时导航路段和卫星导航信号等导航引导信息构造成窗体界面模板,直接获取路径规划的结果并实时加载到模板进行显示,如图4所示.

图4 室内跨楼层路径规划实现图Fig.4 The realization of indoor navigation

3 结束语

目前,路径规划技术往往基于单层路网而设计,只能实现单一楼层的路线规划,不支持跨楼层的路径规划.基于此,本研究基于逐层分析的方法来实现各个楼层的路径规划算法,实现跨楼层位置点之间的路径规划.同时,通过设置途经点的方式,实现室内跨楼层的多点位置服务,从而进一步完善室内跨楼层位置服务,为用户提供更好的室内位置服务.本文方法可以解决现有技术不支持跨楼层多点路径分析的问题,实现室内跨楼层的多点位置服务,从而能够进一步为用户提供更好的室内位置服务.