基于上下文感知的室内路径规划研究

林 雕，宋 国 民，游 雄，贾 奋 励，邓 晨

(信息工程大学，河南 郑州 450001)

基于上下文感知的室内路径规划研究

林 雕，宋 国 民，游 雄，贾 奋 励，邓 晨

(信息工程大学，河南 郑州 450001)

为实现精细化的室内导航服务，综合考虑室内空间特性以及上下文感知应用需求，定义了规范化的室内导航模型数据结构，设计了室内POI数据模型，并针对不同类型POI给出了对应的POI与导航模型的转换方法。具体分析了时间、位置、用户、拥挤、事件5类典型上下文信息对路径规划的影响并建立对应的描述模型。基于所提空间模型与上下文信息模型，提出了上下文感知的路径规划实现流程与方法，并针对拥挤情况、事件两类上下文信息的特点建立了对应的权值更新方法。设计了两组不同上下文背景条件下的室内路径规划模拟实验，通过比较分析其最优路径结果，验证了本文所提模型与方法的有效性。

室内路径规划；室内POI建模；上下文建模；上下文感知；权值更新

0 引言

随着城市的快速发展与扩张，大型建筑物逐渐成为人们生活中开展各类活动的基本场所。但建筑物内部构造复杂、功能分区多样，加剧了空间认知负担，使人们在商场、医院等大型公共场所的寻路变得愈加困难[1]。因此，室内导航已成为当前GIS与位置服务领域的研究热点。面向室内导航应用，当前已提出多种室内空间模型，其中以几何图模型应用最为广泛，这类模型可同时描述空间的几何以及拓扑特征，建模的方式主要有中轴变换[1-4]以及“门—门”[5-7]两种。不同于几何模型，语义模型[8,9]侧重于空间的语义层次建模，通常采用本体的建模方法对空间进行描述，并可借助其推理功能实现以用户为中心的室内导航。纵然目前在室内空间建模方面已取得较多成果，但路径规划本身仍以最短距离或时间为主要择路条件，对路径规划中所受上下文影响因素考虑较为简单(通常限于用户上下文)。实际上，室外的智能交通应用中已将天气、交通拥挤等上下文纳入到导航应用的考虑当中[10-12]。

因此，面向个性化、智能化室内路径导航服务需求，本文重点关注不同上下文背景下的室内路径规划。首先，在笔者先前所提语义导航模型[13]基础上，对其数据结构进行扩展，并提出路径规划关键空间要素POI的数据结构及其与导航模型的关联方法，以构建上下文感知的室内路径规划所需空间模型基础。接着，以是否对用户通行行为产生影响为上下文建模对象选取准则，重点对5种典型上下文要素的特点进行分析并构建其对应的上下文描述模型。然后，基于所提室内空间模型与上下文模型，提出上下文感知的室内路径规划的实现流程和关键算法。最后，通过实验对所提模型与方法的有效性做出验证。

1 面向上下文感知的室内空间数据模型设计

1.1 基于图的室内导航数据模型

面向上下文感知应用需求，文献[13]提出基于图的语义室内导航概念模型及其对应的数据结构，但其所定义数据结构相对简单，仅限于通用拓扑数据字段。为实现对上下文感知路径规划相关语义信息的描述，需对原有数据结构进行扩展与改进，定义便于统一存储、管理及应用的数据结构。

分析该语义室内导航概念模型可知，其中节点和边均可表示多类空间对象，但各种对象不同属性对导航的影响有所差异。例如，通道材质的粗糙程度以及门槛的高低都将影响轮椅用户的通行，此类属性主要对不同类型用户通行产生影响，而房间的公私属性则主要影响不同身份用户的通行。图模型数据结构设计中，若将所有对象的所有属性均作为对应节点或边的属性字段，势必造成数据结构臃肿，增大数据管理和检索的难度。本质上，导航图模型属性字段定义的目的是为了实现对导航相关语义信息的描述。因此，此处重点对限制用户通行的语义信息进行描述，通过给边额外增加 “受限用户类型”、“受限用户身份”、“通行方向”以及“开关时间”4个属性项将不同对象不同属性对用户的通行限制进行统一描述，以实现对图模型的简洁、规范化的定义。改进后的节点与边数据结构如表1与表2所示。其中，“受限用户类型”、“受限用户身份” 分别与下一节用户上下文中的类型和身份相对应。

表1 节点数据结构Table 1 Node data structure

表2 边数据结构Table 2 Edge data structure

1.2 室内POI数据模型

POI是用户路径规划中重点关注的一类信息，目前对室内的POI分类与组成尚无统一定义。文献[14]认为室内路径规划中的POI主要是指用户寻路过程中可能的起始点或终止点，主要包括房间、建筑物出口以及服务设施(如饮水机)三类空间对象。由于概念模型中仅将建筑物出口抽象表示为节点，并未将房间和服务设施两类POI抽象为独立的图元。因此，当选定某一POI作为路径规划的起点或终点时就涉及如何将POI转换到路网中指定位置的问题。针对该问题，设计如表3所示POI数据结构，其字段有ID、类型、名称、对应室内对象类型及ID、几何边界、定位点、语义位置以及关联出口(包括类型和原始ID)。其中关联出口主要包括门和窗户两类，房间关联出口是指可进出该房间的门或窗户；建筑物出口的关联出口则为其自身；对服务设施而言，若处于房间内部则其关联出口与所处房间相同，反之则为空。

表3 POI数据结构Table 3 POI data structure

基于该POI数据模型，当选定某一POI作为路径规划起点或终点时，其与图模型转换方法如下：1)选定POI类型为房间：将该POI所有关联的出口作为备选的起始节点或终止节点，分别计算多条备选路线的权值，其中权值最小路线所对应的首节点或末节点即为当前的起始或终止节点。2)选定POI类型为建筑物出口：此时直接将其转换为路网中对应的建筑物出口节点即可。3)选定POI类型为服务设施：首先判断该POI关联出口是否为空，若为空则表示该POI处于走廊内部，此时计算距该POI定位点最近的节点或边，并将其与最近节点或者对应的最近边垂足点相连动态加入路网。若不为空则将其与对应的关联出口相连动态加入原有路网。

2 面向路径规划的上下文建模

上下文是一个非常宽泛的概念，通常需根据应用的特点，选取与当前应用关系最为密切的上下文信息并对其进行建模。借鉴文献[15]对位置服务上下文的描述，本文上下文建模主要考虑用户本身及所处环境中描述其状态、影响其通行的上下文信息。进一步区分可将路径规划上下文分为客观空间环境、用户自身特性以及动态变化的外部环境。客观环境主要指用户所处的建筑物环境，上章室内空间建模的实质即为对客观空间环境的单独建模。因此，本章主要考虑对用户自身特性以及动态变化的外部环境两类上下文的描述。参照智能室外导航中上下文建模内容，结合对典型室内路径规划情况的分析，此处重点研究“拥挤”和“事件”两类动态变化的外部环境上下文信息。另外，由于现实世界中的客观实体与现象均具有时空属性，本文将时间和位置作为基础上下文要素也纳入上下文的建模当中。下面以时间、位置、用户、拥挤、事件5类典型上下文信息建模为案例，对面向室内路径规划的上下文建模进行分析。

2.1 时间

在情景中，时间是一个触发变化的因素[16]。时间数据包括时间点、时间段两种。对应数据结构如下：

时间点：TimePoint=(year,month,day,hour,minitue,second)

时间段：TimeSegment=(TimePointi,TimePointj)

其中，时间点是定义在特定时区下的某一时刻，通过年、月、日、时、分、秒来描述，路径规划中的特征时间点主要有用户发出请求时刻，室内设施开关转换时间点等。时间段由两个时间点组合而成，如门的打开与关闭时间点共同组成门的打开时间段。

基于时间点发生的先后顺序可推断出时间点之间的关系，分别用“<”、“=”、“>”表示之前、同时、之后3种时间关系。基于时间点关系，可进一步判定时间点与时间段之间的包含关系，如某一门打开时间段为(TimePoint1,TimePoint2)，若当前的时间点TimePoint满足TimePoint1≤TimePoint≤TimePoint2，则可判定该门处于可通行状态。

2.2 位置

室内位置信息主要有几何位置和语义位置两种描述方式，几何位置通过定义在笛卡尔坐标系下的三维坐标描述，语义位置则通过地址和属性对其进行描述。对应数据结构如下:

坐标位置：CoordLocation=({(x1,y1,z1),…(xn,yn,zn)},reference)

语义位置：SecLocation=(adress(floor,num,name),attribute(function,owner))

其中，坐标位置分为点状、线状、面状和体状4种，不同类型位置对应坐标描述不同，reference表示该坐标位置对应的参考坐标系，既可是世界坐标系也可是局部坐标系。语义位置的地址包括楼层、房间号、名称，属性则内含功能与所属两个属性项。

几何位置与语义位置描述的侧重点以及描述方式上存在较大差异。实际路径规划上下文信息中可能同时存在两种不同形式的位置信息，但最终都需将其转换到图模型中对应的节点或边上，从而用于支持路径分析。路径规划中需重点对一些特征位置信息进行关注，如用户当前位置、路径规划请求中的起点与终点位置以及事件和拥堵情况所发生的区域位置。

2.3 用户

用户是路径规划应用的主体与核心所在，不同用户在通行能力、通行权限以及其他个体特征上均存在一定差异，定义用户数据结构为：

User=(id,name,type,identity,preference,location,time)

id、name、type、identity、preference分别表示用户标识、姓名、类型、身份、路径偏好，location和time则表示用户当前位置和用户发出请求的时刻。其中，用户类型主要包括普通用户、听觉障碍用户、视觉障碍用户、移动障碍用户(轮椅用户)等，不同类别的用户对应的通行能力不同。用户身份主要依据用户的室内通行权限进行划分，一般可将其分为工作人员和非工作人员两类，也可根据实际情况对其进一步细化，如可将医院工作人员划分为医生与护士。用户的室内路径偏好可初步划分为垂直通道偏好和水平通道偏好两类。其中垂直通道偏好主要由“不走楼梯”、“不走电梯”以及“不走扶梯”中的一项或多项组合描述。水平通道偏好主要通过“只走主通道”描述，选取该偏好表示不能将房间内部的路网作为最优路径。

2.4 拥挤

交通拥挤状况为室外车辆导航中重点考虑的一个上下文因素，主要通过车流量的大小来描述实时交通状况。类似的，室内通行中也存在拥挤情况，特别是在大型商场、火车站等人员密集场所，人群的通行速度和拥挤状况密切相关。

拥堵的发生与人们的生产、生活以及社会活动相关，具有周期性变化特征[17]。例如，商场一般在周末、节假日等时间容易出现拥堵，而工作日的人流量一般较小，同一天内通常上班时间人流量较小，下班时间人流量较大。因此，根据其周期性变化特点，将一年的日期分为不同类别，并针对某一类日期的特定情况，将一天的时间划分为不同时段。实际应用中，可基于对某一类建筑物实测人流数据的统计分析对日期的类型和时段进行划分，日期类别定义如下：

Type={ts1,…,tsn}

所有的类别构成类别集，具体的一天必定属于类别集合中的某一特定类别。类别集定义为：

Typeset={p1，…,pm}

式中:m∈N表示类别数量；pi∈Type表示第i个类别(1≤i≤m)。

需指出的是，与室外不同，各类建筑环境下的时间分类分段有所区别。例如，火车站和商场的拥挤时间分段有所差异，商场的人流量主要与用户休闲时间相关，火车站的拥挤时间则与列车的出发及到达时间密切相关。因此，针对不同类型的建筑物需建立对应的拥堵情况时间分类分段描述。

基于以上对时间分类分段的论述，定义拥挤情况数据结构：

Jam=(id,(p,ts),location,level)

id表示时间分类分段标识，组合(p,ts)中p表示该时间分区对应的日期类型，ts表示时间分区，location表示该时间分区对应的拥堵区域，level表示对应的拥挤程度。其中，定性地将level划分为正常、轻度拥挤、中度拥挤、重度拥挤4类情况。

2.5 事件

事件是指环境中所发生的影响用户通行的特殊情况，主要对通道的通行状态产生影响，根据其特征将事件数据结构定义为：

Event=(id,type,time,location,level)

id表示事件标识，type表示事件类型，time表示事件的生命周期(包括发生与持续的时间)，location表示事件发生位置，通常为某一区域，level表示事件等级。其中，事件类型包括设施故障，计划活动，突发事故3类，设施故障是指室内通行设施运营的突发情况，如电梯停运。计划活动是指提前计划将要发生的影响通道通行状态的行为，如安全警戒区域设定、室内道路改造等。突发事故是指偶然发生的影响道路通行的事件，如火灾。事件等级主要通过道路的影响程度定义，分为轻微、中等、严重、特别严重4级。

拥挤和事件的数据结构具有一定的相似性，也可将拥挤看作是一类特殊的事件。上文是对其数据结构进行单独定义，而非对通道人流量的实时、定量建模，因为实际应用中难以完全实现对室内区域拥挤情况的实时处理、分析，而基于人流统计分析的定性建模方式则有利于提高上下文的感知效率。

3 上下文感知的路径规划算法

上下文感知的室内路径规划流程如图1所示，不同阶段所受上下文的影响有所差异。其中，权值初始化以通行时间为路网的初始权值；初始路网的构建则是根据起点和终点所在楼层动态构建用于路径分析的楼层路网。下面重点对“确定起始与终止节点”、“确定可用路网”、“权值更新”3个关键阶段进行分析。

图1 上下文感知的室内路径规划流程Fig.1 Flow chart of context-aware indoor routing

(1)确定起始与终止节点。确定起始与终止节点是指将用户原始路径规划请求中的起点和终点转换到路网中对应的节点。原始路径规划请求中的起点和终点主要来源有：交互界面选择、用户输入以及用户当前位置3类，包括几何和语义两种位置表现形式。根据位置描述形式的不同，对应的转换过程有所区别。若为语义位置，则将其与POI匹配，并利用1.2节所提POI到节点转换方式确定其对应的起始或终止节点；若为坐标位置，首先判断该坐标点位置是否位于某一房间内部，若成立则建立该点与房间对应出口之间的连接关系，进而动态加入到路网当中；反之则将该点与距离其最近节点或最近边垂足点相连动态加入路网。

(2)确定可用路网。确定可用路网是指根据上下文背景条件排除初始路网中不可用的路径。主要涉及用户类型、用户身份及用户请求时间3类上下文信息，分别对应于导航模型数据格式中的“受限用户类型”、“受限用户身份”及“开关时间”3个字段。通过对初始路网中所有的边进行遍历，判断当前各类上下文信息是否属于其对应的受限范围，若成立则将该边权值设定为无穷大即可，反之则不作处理。

(3)权值更新。权值更新是指根据当前的上下文背景条件对可用路网的边权值进行更新。首先将用户的请求时间与拥挤以及事件上下文的时间信息进行匹配，确定当前时刻下两类上下文对应的影响区域，然后对区域内受影响的边进行加权处理。两类上下文对应影响因子如下：

拥堵情况影响因子μ：不同的拥挤等级对行人的通行速度影响大小不同，一般用人流大小表示室内通道的拥挤程度，其重要衡量指标为人流密度(单位面积上人员的数目)。灾害救援领域研究中已提出了多种行人速度和人流的关系公式[18,19]，借鉴文献[18]中所提水平通道速度和人流的关系模型(式(1))，对不同道路拥堵等级下对应人流量大小以及平均速度做出规范，并通过平均速度除以正常速度(此处为1.4 m/s)确定其对应的μ值(表4)。

(1)

式中：V表示行人的通行速度(m/s)，ρ表示人流量大小(人/m2)。

表4 拥堵情况影响因子Table 4 Impact factor of congestion

事件影响因子λ：根据事件影响程度的大小设定相应的权值，此处侧重于对于事件所产生影响的定性建模，主观对其赋权：影响程度分为轻微、中等、严重和特别严重，对应赋值分别为0.9、0.6、0.3和0.01。权值越大表示所受事件影响越小，未受事件影响的区域的权值则为1。应用中，可根据实际情况对影响因子作相应调整。

确定上下文影响区域对应的影响因子后，即可进行权值的更新。拥挤与事件对应的权值更新公式分别为式(2)与式(3)，其中，ei、ej分别表示当前时间下拥堵区域与事件影响区域内的任意一条边。

weightei′=weightei×(1/μ)

(2)

weightej′=weightej×(1/λ)

(3)

4 实例分析

根据第一章所提室内导航模型，选取郑州某商场1、2层楼层平面图为数据源，构建对应的室内拓扑路网(图2)。以路径通行时间为权值，对其进行初始赋权，在此基础上展开不同情境下的路径规划实验。

图2 楼层1(左)和楼层2(右)的平面图以及对应的路网Fig.2 Floor plan of the first floor (left) and second floor (right) with their indoor network

此处侧重于方法的验证，采用模拟、预设等方式构建路径规划上下文仿真实验条件，分别设计两组实验，以证明本文所提模型与方法的有效性。实验1主要是对不同用户上下文背景的路径规划进行分析，实验2则开展不同拥挤情况和事件两类上下文背景条件下的路径规划实验，两组实验中均不受其他未标明上下文的影响。

实验1：实验条件如表5所示，图3为其对应结果。由图3可知，情境2与情境3所规划路线相同，但与情境1路线有所差异。其中情境2中由于房间143处于关闭状态，因此计算所得最优路线未包含该房间内部路段，转而途经141、142房间以及对应通道路段到达目的地。而情境3则由于145房间属于工作人员专用区域，对普通顾客而言该房间对应门所关联的水平边均为不可用边，进而导致其最优路径并未通过房间145。情境4中则由于当前用户偏好为“只走主通道”，使得其路线仅限于室内通道区域。

实验2：实验条件如表6所示，其对应结果见图4。

表5 实验1上下文背景Table 5 Context of experiment 1

图3 实验1最优路径Fig.3 Optimal routes of experiment 1

由图4可知，情景2与情境1路线差异较大，主要是由于在情景2中拥堵情况较为严重，从而使得楼层1和楼层2的路线均有所不同。对比情景2和情景3的路线可知，由于情景3中二楼事件发生区域与原有情景2的二楼最优路线部分恰好重合，因此路径规划过程中综合考虑两层楼路网的权值变化，重新推荐了一条与原有两条路线均有所不同的路线。

表6 实验2上下文背景Table 6 Context of experiment 2

图4 实验2最优路线Fig.4 Optimal routes of experiment 2

综合对上述两组实验的分析可知，本文所提模型与路径规划方法能够有效根据上下文背景条件推荐出适合当前应用情境的最优路径。

5 结语

针对上下文感知的路径规划需求，本文分别建立了空间与上下文两类信息的基础模型。空间建模中对已有导航模型数据结构进行扩展与改进，以实现对导航相关语义信息的统一、规范化表达，并提出了室内POI的数据模型及其与导航模型的关联方法；上下文建模部分提出了5类典型上下文信息的描述模型。结合上下文感知的路径规划流程具体分析了空间模型与上下文模型的结合方法，并给出其中路网权值更新的实现算法。通过实验验证了所提模型与方法能够有效针对不同上下文背景得出合理有效的最优路径。下一步工作将对上下文模型进行细化、扩展，并接入多源传感器信息，发展面向实地的上下文感知的室内路径导航系统。

[1] 温永宁,张红平,闾国年，等.基于房产空间数据的楼宇空间疏散路径建模研究[J].地球信息科学学报,2011,13(6):788-796.

[2] GILLIERON P V,MERNINOD B.Personal navigation system for indoor applications[C].11th IAIN World Congress,2003.21-24.

[3] LEE J.A three-dimensional navigable data model to support emergency response in microspatial built-environments[J].Annals of the Association of American Geographers,2007,97(3):512-529.

[4] THILL J C,DAO T H D,ZHOU Y.Traveling in the three-dimensional city:Applications inte planning[J].Journal of Transport Geography,2011,19(3):405-421.

[5] YUAN W J,SCHNEIDER M.iNav：An Indoor Navigation Model Supporting Length-Dependent Optimal Routing[M].Geospatial Thinking.Berlin:Springer,2010.299-313.

[6] LIU L,ZLATANOVA S.A"door-to-door"path-finding approach for indoor navigation[C].Proceedings of GeoInformation for Disaster Management Conference,2011.3-8.

[7] DAVIDE R,ZLATANOVA S,CLEMENTINI E.Route directions generation using visible landmarks[C].Proceedings of the Sixth ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness.ACM,2014.1-8.

[8] TSETSOS V,ANAGNOSTOPOULO C,KIKIRAS P.Semantically enriched navigation for indoor environments[J].International Journal of Web and Grid Services,2006,4(2):453-478.

[9] DUDAS P M,GHAFOURIAN M,KARIMI H A.ONALIN:Ontology and algorithm for indoor routing[C].Tenth International Conference on Mobile Data Management:Systems,Services and Middleware,2009.720-725.

[10] 齐晓飞,王光霞,周小军,等.导航地图情境建模[J].地理信息世界,2014,21(2):6-12.

[11] 梁晶.上下文感知计算及其在智能交通中的应用[D].长春：吉林大学,2011.

[12] 王江晴,康立山.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报(交通科学与工程版),2007,31(1):46-49.

[13] 林雕,宋国民,邓晨.基于图的语义室内导航模型构建研究[J].测绘工程,2015,24 (1):48-52.

[14] KARIMI H A,GHAFOURIAN M.Indoor routing for individuals with special needs and preference[J].Transactions in GIS,2010,14(3):299-329.

[15] 齐凌艳,陈荣国.位置服务的上下文信息模型[J].地球信息科学学报,2014,2:007.

[16] LIJDING M E M,BENZ H P,MERATNIA N,et al.Smart signs:Showing the way in smart surroundings[R].Technical Report TR-CTIT-06-20 Centre for Telematics and Information Technology,University of Twente,Enschede,2006.

[17] 郑年波,陆锋,李清泉.面向导航的动态多尺度路网数据模型[J].测绘学报,2010,39(4):428-433.

[18] LO S M,FANG Z,LIN P,et al.An evacuation model:The SGEM package[J].Fire Safety Journal,2004,39:169-190.

[19] PREDTECHENSKII V M,MILLILINSKII A I.Planning for Foot Traffic Flow in Buildings[M].India:Amerind Publishing Co,1983.

Study on the Context-Aware Indoor Path Planning

LIN Diao,SONG Guo-min,YOU Xiong,JIA Fen-li，DENG Chen

(InformationEngineeringUniversity,Zhengzhou450001,China)

To provide a more advanced and personalized indoor routing service for users in different scenarios,an refined indoor navigational data model is defined which provide a unified and concise description of the geometric,topological and semantic information of indoor space.As the significance of POI during the path planning,a POI data model is proposed,and classified into three types:room,building exit and services facility,then the conversion methods between each type and the navigational model are given respectively.Five typical contexts:time,location,user,congestion and event are selected as the components of the indoor routing context due to their significant influence on indoor routing,and corresponding descriptive model for each context is established along.Based on the proposed spatial and contextual models,the processes and methods of context-aware indoor routing are presented,which gives an elaborate interpretation on how to combine the two models together smoothly for the path planning.According to the features of congestion and events,two key weight updating algorithms are then built.Two simulated indoor routing experiments are designed for various preset indoor path planning scenarios,the results of which validated the effectiveness and efficiency of the proposed models and methods.

indoor path planning;indoor POI modeling;context modeling;context-aware;weight updating

2015-11-13；

2016-01-11

国家高技术研究发展计划(863)基金项目(2013AA12A202)；国家自然科学基金项目(41371382)

林雕(1991-)，男，博士研究生，主要研究方向为室内导航及室内空间建模。E-mail：srlind213@126.com

10.3969/j.issn.1672-0504.2016.03.002

P208

A

1672-0504(2016)03-0008-06