动态环境感知的多目标室内路径规划方法

周 艳 ，陈 红 ，张叶廷 ，黄悦莹 ，张鹏程 ，杨卫军

（1.电子科技大学资源与环境学院，四川 成都 611731；2.电子科技大学大数据研究中心，四川 成都 611731；3.武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉 430072；4.广州市城市规划勘测设计研究院，广东 广州510060）

室内路径规划主要应用于室内导航[1-3]和应急疏散[4-5]等领域.近年来，随着人们对复杂室内环境导航需求的日益增长，Google 地图、必应地图、百度地图等众多知名地图服务供应商都已将室内导航作为地图服务的必备功能之一.

相关研究为室内导航提供了不同的路径规划思路，主要可分为：基于三维模型语义信息[6-7]、增强用户语义信息[8-9]和顾及上下文信息的3 类室内路径规划方法[10-11].这些方法的优点是在规划室内路径时，不同程度上考虑了影响导航的语义信息，提高了路径规划的实用性.第1 类方法重点考虑了室内三维模型的几何语义信息；第2 类方法将用户信息及其行为语义纳入导航路径规划中；第3 类方法考虑了环境上下文和用户偏好语义，提供了以用户为中心的个性化路径规划服务.上述方法的不足之处在于：现有的室内路径规划方法主要是针对单一目标的路径规划问题设计的（解决两点之间的室内路径规划），而在现实生活中，用户往往具有面向多目标的室内路径规划需求；此外，实际寻径过程中的环境语义是动态变化的，现有方法在路径规划时往往将语义信息作为静态约束条件，难以适应导航环境的动态变化.

为此，本文提出动态环境感知的多目标室内路径规划方法，考虑到室内动态环境信息是影响室内路径规划合理性与有效性的重要决定因素，将室内路径复杂度、拥挤程度与阻断事件等室内多维动态环境语义建模并量化，统一整合到室内导航路网模型中，基于Dijkstra 算法设计了顾及室内动态环境变化的室内路径规划方法，以满足用户个性化的多目标室内导航需求.

1 顾及环境语义的室内导航路网模型

室内导航路网模型是实现室内路径规划和导航服务的基础[12].目前的室内导航路网模型以几何图模型应用最为广泛，这类模型可同时描述室内空间的几何特征和拓扑特征，建模的方式主要有对偶图模型[13]和门-门模型[14]两种.本文提出顾及环境语义的室内导航路网模型，扩展节点-边表示的室内导航图模型，将室内路径复杂度、拥挤程度与阻断事件等动态环境语义建模并量化，统一整合到室内导航路网模型中，为实现动态环境感知的多目标室内路径规划提供导航路网模型支持.

1.1 室内导航路网模型扩展

基于图模型的基本思想，室内导航空间可以抽象为节点-边表达的几何模型.其中，房间和门抽象为几何中心，表示为节点，走廊以中心线的形式抽象表达为边；节点与节点、节点与边（即房间-门、门-走廊）之间根据实际路径的连通性，建立节点-边之间的连接，实现室内导航路径连通，依此形成节点-边表示的室内导航路网模型.为了满足用户个性化导航需求，本文对节点-边表示的室内导航路网模型进行了扩展，如图1所示.

图1 扩展的室内导航路网模型Fig.1 Enhanced indoor navigation road network model

（1）增加了影响用户室内路径选择的垂直组件，用于表达三维空间垂直方向上的可达路径.垂直组件划分为电梯、扶梯、楼梯3 类，以便于结合用户偏好（如残疾人轮椅更适宜选择电梯等）合理规划室内导航路径，满足用户个性化室内导航需求.垂直组件在各楼层的出口表示为节点，垂直方向的连通性由垂直节点之间的连接边表示；

（2）增加了影响用户选择路径复杂程度的其它节点，如附加节点和拐弯节点.附加节点用于表示门与走廊之间、垂直组件与走廊之间的连接点，其数目一定程度上影响室内导航路网的复杂程度；拐弯节点表示导航过程中路径方向发生变化的转折点，导航路径中过多的拐弯可能会增加用户路径认知障碍，降低导航路径清晰性；

（3）房间细分为单门房间和多门房间.单门房间只有一个门节点连接走廊与房间，而多门房间有多个门节点与走廊连接，从而可以在路径规划时提供更多的室内导航路径选择；

（4）边扩展为走廊、垂直边和房间内连接边.走廊以中心线的形式抽象表达为边；垂直边表示垂直方向上的连接边，垂直边与垂直组件的节点产生节点-边关联，用于表达楼层之间的垂直方向导航路径；房间内连接边表示房间节点与门节点之间的连接路径，可用于多门房间内部的导航路径规划.

为直观起见，本文以图2所示的室内三维几何模型为例，基于扩展的室内导航路网模型，构建由节点-边表示的室内导航路网.图2（a）表示的室内三维几何模型共包含四层，鉴于各楼层导航路网建模过程大同小异，因而此处主要以第二层为例详细说明.首先将图2（a）中的房间和门分别按其二维投影的几何中心抽象表达为节点，如R1、R2、R3、R4 等表示房间节点；D1、D2、D3、D4 表示相应房间的门节点.房间细分为单门房间（R1、R2、R3、R4 等）和多门房间（R12）.对于单门房间，建立房间节点与门节点之间的连接边（L1、L2、L3、L4 等）；对于多门房间，建立房间节点与多个门节点（D11、D12、D13）之间的房间内连接边（L12、L13、L14）；同时在多门房间中建立门-门节点的房间内连接边（L11、L15、L16）.

图2 室内导航路网建模实例Fig.2 An example for indoor navigation road network modelling

本文模型增加了垂直组件，垂直组件在各楼层的出口表示为节点，垂直方向的连通性用垂直节点之间的连接边表示.本文将垂直组件划分为电梯、扶梯和楼梯3 类，如图3所示.垂直组件的出口与门类似，可以抽象表示为节点，相邻楼层的垂直组件出口节点通过垂直边（电梯）或斜边（扶梯与楼梯）连接；楼梯的形态通常有两种：楼梯直接连通楼层走廊和楼梯经层间转折后连通楼层走廊，如图3（c）所示.对于后一种楼梯，除了将楼梯连接走廊的出口视为节点以外，还需要将楼梯的层间转折抽象为节点，建立节点-节点的斜边连接.电梯和楼梯一般同时具有上行和下行方向语义，而扶梯通常具有单向上行或单向下行语义，图3（b）表示了具有上行方向语义的扶梯路径.通过增加垂直组件（电梯、扶梯、楼梯），可以在节点-边表达的室内导航路网模型中引入方向语义约束，同时也为满足特殊用户（如乘坐轮椅用户）的个性化路径服务需求提供了可能性.

图3 室内垂直组件导航路径建模Fig.3 Navigation route modelling of indoor vertical components

室内导航路网模型中，在边上添加附加节点，用于表示门与走廊的连接点，以及垂直组件与走廊的连接点.附加节点的位置均选择走廊中心线上与连接节点距离最近的点，如图2（b）中的A1、A2、A3、A4 表示门与走廊相连接的附加节点，A8、A9 表示垂直组件（分别对应楼梯V1、V2）连接走廊的附加节点.考虑到导航路径中过多的拐弯会增加用户路径认知障碍，降低路径清晰性，本文在模型中区分了拐弯节点.值得说明的是，拐弯节点并不是建模过程中物理生成的一类节点，而是在导航路径规划时产生的一类用于标识导航路径方向发生变化的转折点.当路径中两条连接边斜率不同时，同时关联两条连接边的节点被判定为拐弯节点.理论上而言，任何节点（包括门节点、房间节点和附加节点）都有可能成为拐弯节点，路网中的拐弯节点是动态变化的.比如，图2（b）中，当从房间R1 到房间R4 规划一条导航路径时，门节点D1 与附加节点A1、附加节点A4 与门节点D4 依次被判定为拐弯点；但如果规划一条从房间R1 到电梯V1 的路径，此时A4 与D4 就不再是拐弯节点.因此，拐弯节点的作用主要是服务于导航路径规划，旨在判定拐弯数量从而辅助导航路径决策，而不是直接用于构建室内导航路网模型.

综上所述，图2以一个楼层为例说明了室内导航路网的建模过程，其它楼层同理可得，不再赘述.

1.2 顾及环境信息的导航语义表达

本文从以下三方面表达顾及环境信息的室内导航语义.

（1）路径复杂度

室内导航路径的复杂程度直接影响到解释、说明和可视化表达导航路径的难易程度，同时也影响到用户理解、记忆以及执行路径导航指示的难易程度.相关认知研究表明，导航路径复杂程度的重要性不亚于路径长度，用户在选择路径时，往往更愿意选择较为简单的导航路径（即使其长度与最短路径相比略有增加），因为它存在更少的认知障碍、更便于理解和导航[15-16].路径复杂度表明了用户理解、说明、记忆以及执行路线导航指示的难易程度[17-18]，尤其当用户面对复杂建筑的陌生室内环境时，考虑导航路径的复杂性显得尤为必要.研究表明，拐弯数直接反映了路径的复杂程度，在人类常用的数十种路径选择标准中，拐弯数是人们最常用的标准之一[19]，导航路径中的拐弯数越多，给用户造成的导航体验越复杂，即使是在用户对路网十分熟悉的情况下仍然如此[20].鉴于拐弯数在路径决策中的重要性，本文采用路径拐弯数表达导航路径的复杂程度，据此，路径复杂度语义可以描述为

其中，number_turns为导航路径中的拐弯数.

（2）拥挤程度

导航环境的拥挤程度是影响用户导航体验舒适性的重要因素.特别是在大型商场、火车站等人员密集的复杂室内导航环境中，路径的拥挤程度成为影响用户路径选择的重要决策因素之一.鉴于室内导航环境的拥挤程度直接影响到用户室内导航体验的舒适性，本文将室内导航环境拥挤程度的语义描述为

其中，crowd_type表示室内导航环境的拥挤程度.拥挤程度可以通过人群的通行速度来描述，拥挤程度不同对行人通行速度的影响也不同，通行速度可以通过人流密度反映，人流密度表明了单位面积上行人的数目.本文借鉴文献[21]提出的通行速度（V，m/s）和人流密度（ρ，人/m2）的关系模式，使用表1定义的取值范围对室内导航环境的拥挤程度划分等级.据此，crowd_type可分为畅通、轻度、缓慢和堵塞4 种.crowd_range表示拥挤程度对应的区域长度；Tc表示拥挤程度对应的时间区间，由crowd_range与V之比得到.

表1 拥挤程度与人流量对应情况Tab.1 Degree of crowdedness and corresponding flow density

（3）阻断事件

导航环境中的阻断事件是导致路径中断、影响路径可达性的主要因素.室内导航中常见的阻断情况有设施故障、突发事故、人为阻断等.为了描述阻断事件对室内导航的影响，本文将导航环境中的阻断事件语义表达为

其中，Tes为受阻断事件影响的时间区间，event_range为阻断事件的影响区域，描述室内导航路网中受阻断事件影响的节点集合，event_range={v1,v2,···,vn}，其中n为室内路网模型中受阻断事件影响节点个数，v1、v2、 …、vn为室内路网模型中受阻断事件影响的各节点，若该节点可达，取值为1，若该节点不可达，取值为0，此时，则可能导致相关节点也不可达.

1.3 室内环境语义感知的导航通行成本

将多维环境信息的导航语义引入室内导航路网模型中，可以使基于节点-边表达的室内导航路网模型不仅具有路径规划需要的几何信息，同时包含路径复杂度、拥挤程度和阻断事件等多维环境感知的室内导航语义信息，从而有效增强用户室内导航的舒适性体验.为此本文顾及室内环境语义信息，提出可量化的导航通行成本函数G为

式中：ωc为 拥挤程度 (C)的 权重系数；ωt为路径复杂度 (T)的 权重系数；ωe为阻断事件 (E)的权重系数；为节点vi、vj间路径拥挤程度的成本函数；α为系数，可以根据表1的拥挤程度指定（畅通、轻度、缓慢和堵塞对应的 α分别取1.0、2.0、4.0和8.0）；为vi和vj之 间的欧氏距离.fturn(Vm)为路径复杂度的成本函数，可由导航路径中的拐弯数计算决定，Vm为 导航路径中的拐弯节点的集合；fevent(Vn)为阻断事件的成本函数，Vn为受阻断事件影响的节点集合，集合中节点可达，fevent(Vn)=1，节点不可达，fevent(Vn)→0.

ωc、 ωt和 ωe可以根据室内环境语义的重要程度进行权值分配，权值满足式（3）.

根据室内导航环境的动态变化可以不断更新通行成本函数值，以节点间的导航通行成本作为室内导航路网的边长，即可得到融合了动态环境语义的室内导航路网，此时，顾及室内环境语义的导航路径规划就转化为基于室内导航路网求解室内导航路径的最优通行成本问题.

2 室内多目标路径规划方法

经典最优路径规划算法主要有Dijkstra、A*、Floyd 和Bellman-Ford（BF）算法等，其特点如表2所示.与Floyd、BF 算法相比，Dijkstra 算法具有简单易行的优点，能够获得全局最优解，虽然对于很长距离的路径规划效率不如A*，但就室内路径规划而言，Dijkstra 算法效率并无明显差别，为此，本文基于扩展的节点-边室内导航路网模型，将顾及室内动态环境语义的通行成本函数值作为室内导航路网的边长，基于Dijkstra 经典寻径算法实现室内多目标路径规划.

表2 经典最优路径规划算法Tab.2 Classic optimal path planning algorithms

顾及室内动态环境语义的多目标寻径方法如图4所示.

图4 室内多目标路径规划流程Fig.4 Flow chart of indoor multi-objective routing

（1）构建室内导航路网

基于本文扩展的节点-边室内导航路网模型，构建用于寻径的室内导航路网；设置室内导航路网中各边长的初始值为 ∞；

（2）确定导航起始点和多目标点

设置用户导航的起始点S和需要访问的k个目标点的集合TargetList 为{T1,T2,···,Tk}，Tk为多目标寻径中的第k个目标点；设置CloseList 集合存放已遍历的目标点，初始化为空；设置PathList 集合存放起始点到目标点的导航路径，初始化为空；

（3）计算导航通行成本G*，更新室内导航路网

本文算法融合了室内导航环境语义信息，将节点间的G*作为室内导航路网的边长.因此，基于当前的室内导航环境语义信息，通过计算节点间G*值，可以有效融合环境动态变化，实现室内导航路网更新；

（4）顾及环境语义信息的多目标寻径方法

①利用Dijkstra 算法，寻找起始节点S到Target-List 中每个目标点的最短路径（即最低通行成本路径）D(T1)D(T2)···D(Tk)，从中选取具有最短路径的目标点TL满 足：D(TL)=min{D(T1),D(T2),···,D(Tk)}.

②若D(TL)=∞，说明TargetList 当中所有目标点均不可达，跳转至（6），算法结束；否则，将起始点S到目标点TL的导航路径添加到PathList 集合，并将TL从TargetList 集合移动至已遍历目标点集合CloseList；

③判断TargetList 集合是否为空.如果TargetList非空，设置TL为 新的起始点，即S=TL，跳转至（3）；若TargetList 为空，说明目标点均已遍历；

（5）输出

多目标路径集合PathList，算法结束.

3 实验与结果讨论

本文实验选用如图5（a）所示建筑物三维几何模型，以通行成本代价为边长权值，构建顾及环境语义的室内导航路网，其对应四层楼的室内导航路网节点-边拓扑结构如图5（b）所示.通过设置拥挤情况和阻断事件等不同的环境语义信息，分析比较环境语义对室内导航路径规划的影响，验证说明顾及动态环境语义的多目标路径规划方法的可行性.

图5 三维室内导航路网模型Fig.5 3D indoor navigation road network model

（1）导航环境拥挤情况对室内路径规划的影响

导航环境的拥挤程度是影响用户路径选择的重要因素，为了说明导航拥挤情况对室内路径规划的影响，暂不考虑其它环境语义的影响，分别针对两种典型的拥挤情况，模拟用户请求规划一条从起始节点S（节点编号为0）到多目标节点T1、T2、T3 和T4（节点编号分别为26、105、163 和234）的室内导航路径，拥挤情况环境语义设置如表3所示.情景1规划路径如图6（a）黑色路线所示；情景2 中，分别设定了轻度、缓慢和堵塞3 种拥挤程度的路段，室内多目标导航路径的规划结果如图6（b）所示.

表3 实验1 环境语义Tab.3 Environment semantics of experiment 1

图6 拥挤情况对多目标室内路径规划的影响Fig.6 Impact of indoor multi-objective planning route with degree of crowdedness

为了说明导航环境拥挤情况对通行效率的影响，根据表1，取不同拥挤情况的通行速度中值（轻度、缓慢和堵塞的取值分别为1.24、0.69、0.30）测算不考虑避让拥堵路段的Dijkstra 算法通行时间，并与本文避开拥堵路段的规划路径通行时间进行时间比较（畅通的通行速度取值1.40），其结果如图7所示，3 种情况下本文方法的通行时间分别节约了19.7、124.3、23.7 s，节约的通行时间的百分比平均提升了17%，表明本文算法避开拥堵路段的导航时间通行成本更优.

图7 路径规划的通行时间比较Fig.7 Comparison of travel time in path planning

对比情景1 和情景2 的路径规划结果可以看出，路径规划过程中针对导航环境拥挤程度的不同，本文算法通过感知环境信息避开了拥堵路段，因而用时更少，且改变了路径规划的节点访问顺序，得到了与无拥堵情况下不同的室内规划路径.根据本文多目标路径导航算法原理分析可知，这是由于本文算法根据不同拥挤情况，对拥堵区域内受影响的导航路网边权进行了G*的权值更新，使得拥堵路段的导航成本增高，因而有可能改变多目标节点之间的室内路径规划路线，实现顾及环境拥挤情况的合理室内路径规划.

（2）动态环境感知的多目标室内路径规划

为了验证本文方法的有效性，综合考虑环境拥挤程度、阻断事件和路径复杂性等多维环境因素影响，模拟用户请求规划一条从起始节点S（节点编号24）到多目标节点T1、T2、T3 和T4（节点编号依次为28、102、159 和234）的室内导航路径.根据本文定义，多维环境语义中的路径复杂度主要取决于路径拐弯数，可由路网拓扑结构计算得到，因此表4主要针对环境拥挤程度和阻断事件进行环境语义设置.假设情景1 中模拟所有区域均不存在拥挤情况和阻断事件的理想路径规划情况；情景2 模拟方向语义约束的路径规划情况；情景3 中模拟多维导航环境中不同时刻、不同位置、不同拥挤程度和阻断事件情况下的路径规划情况.实验结果如图8所示，情景1 中，多目标节点的室内规划路径如图8（a）中黑色路线所示；为说明扶梯方向性语义的影响，情景2中，将3 楼到4 楼红色虚线箭头处的楼梯模拟为具有单向下行语义的扶梯，此时室内导航路径规划结果如图8（b）所示.由图8（a）和（b）可以看出，当垂直组件具有单向（上行或下行）方向语义约束时，规划路径发生了变化，这是由于在方向语义约束下，本文方法会将相关垂直组件设为不可用边，从而避开不可用边；情景3 中，假设t1时刻在图8（c）1 楼黄色区域出现轻度拥挤，t2时刻在图8（c）2 楼橘色区域出现缓慢程度的拥挤情况以及1 楼到2 楼的紫色节点处发生阻断事件，t3时刻在图8（c）4 楼红色区域出现堵塞情况，t4时刻不存在任何的拥挤和阻断情况，此时规划的路径如图8（c）所示.由图8（a）和（c）可以看出，两者规划的路径存在较大差异.在t1时刻的轻度拥挤情况没有影响路径的规划结果，但t2时刻拥挤程度变为缓慢以及阻断事件的发生直接导致访问节点由102 变为159，t3时刻的堵塞情况造成路径规划中以普通楼梯取代了电梯，使节点159 到节点234 的规划路线发生了变化.可以看出，环境拥挤程度较轻时，由于对导航通行成本影响较小，因而没有影响路径规划结果；环境拥挤程度加剧或出现阻断事件时，环境语义的动态变化引起路网相关边的导航通行成本函数动态更新，实验结果说明本文方法能够有效感知动态环境变化，规避环境拥堵和阻断事件发生路段，能合理规划室内导航路径.

表4 实验2 环境语义Tab.4 Environment semantics of experiment 2

图8 顾及环境语义的多目标规划路径Fig.8 Multi-objective planning route with environment semantics

4 结 论

面向复杂室内环境中的用户多目标导航需求，提出了综合考虑室内路径复杂度、拥挤程度和阻断事件的多目标室内路径规划方法.实验结果表明，本文方法能够通过顾及环境语义的导航通行成本函数实现对室内导航环境变化的动态感知，从而规避环境拥堵路段和阻断事件发生路段，为用户提供具有易达性、安全性与舒适性的室内多目标路径规划结果.后续研究将考虑用户个人行为语义与多维室内环境语义结合，为用户提供更具个性化的多目标室内路径规划服务.

致谢：智慧广州时空信息云平台建设项目（GZIT 2016-A5-147）资助.