室内路径规划作为室内导航的重要组成部分，主要涉及室内定位、场景建模及寻路算法等内容。目前，室内定位主要通过特定设备(如红外、超声波发射器等)、WiFi信号(如测距、指纹定位等)和移动传感器(如加速度传感器、陀螺仪等)等实现^[1-2]，在一定程度上能够满足室内导航的需求。室内场景通常较为复杂，路径规划受到多重约束条件的限制，但目前多数研究主要考虑了距离、时间和地标等因素，已无法满足日益纷繁的室内路径导航的需求^[3-7]。因此，如何将场景建模、多约束条件与寻路算法三者进行有机结合就显得尤为重要。

目前场景建模模型主要包括基于符号和基于几何的模型^[8]，其代表分别为图模型和格网模型。在室内路径规划中，约束条件的分布是连续且非均衡的，如地标的影响、灯光强度的衰减等，所以需要一种精细化的建模方法。图模型通过“节点-边”表达场景拓扑关系与连通性，较为粗糙且不利于多约束条件的集成和叠加分析^[9]。相比之下，格网模型以规则单元(正三角形、正方形和正六边形等)对室内空间进行剖分，可实现更为精细的场景表达(精细程度由剖分单元大小决定)，且每个单元可有效集成多种约束条件，方便叠加分析计算^[10]。另外，室内路径规划相较于室外，其通行并不受严格的线性约束，前进方向是任意的，因此具有各向同性的正六边形相比邻域不一致的正四边形，在处理邻域问题时更具优势，但由于正六边形存储结构复杂，其应用相对较少^[11]。文献[12]提到的基于正六边形的正交行列坐标系和优化存储结构能有效解决数据存储复杂的问题，并成功应用于多约束条件下的海洋区域路径规划。据此，本文将正六边形应用于室内场景建模，以发挥其在精细化场景建模、叠加分析计算及各向同性的作用。

寻路算法作为路径规划的核心，需要有效兼顾多约束条件并具有良好的效率，主要包括迪杰斯特拉（Dijkstra）算法、蚁群算法、遗传算法、神经网络算法、A^*算法等。其中A^*算法作为启发式搜索算法，可将约束条件作为启发因素，缩小搜索范围以提高效率^[13]，被普遍应用于最优路径查找。算法核心在于启发因素的选取及对路径代价的合理估计，本文根据已有研究将约束条件概括为基于场景自身和基于应用偏好，并构建了一种采用正六边形格网对室内场景建模，根据应用偏好选取约束条件作为A^*算法的启发因素，配置影响权重并进行叠加分析计算，得到多样且个性化的路径的室内路径规划算法模型。基于此模型，本文以距离、地标辨识度、行人密集度3个约束因素为例，说明多约束条件对路径规划的影响及其与场景建模和寻路算法有机结合的优越性。

1 正六边形室内场景建模

正六边形室内场景建模是通过正六边形对室内平面进行剖分，并赋值被分割平面的环境属性及语义信息。而采用正六边形作为剖分单元，是由于正六边形中心至其邻域中心距离一致，具有各向同性特征，相比正方形的共边和对角邻域形式，扩展更均衡^[11]，在处理邻域关系时更具优势。

1.1   正六边形坐标系

坐标系作为场景建模的基础，其定义应满足格网定位、距离量算等需求。已有的正六边形坐标系主要包括正交行列、三斜轴和极坐标3类^[11]。正六边形可通过边长l和宽度w来描述，其中$w = \sqrt 3 l$，根据其摆放角度，分为顶角型和平顶型两种形态，如图 1(a)、图 1(b)所示。

图  1  正六边形三斜轴坐标系示意图

Figure  1.  Diagram of Regular Hexagonal Coordinate System with Three Inclined Axes

下载: 全尺寸图片 幻灯片

本文选择顶角型正六边形的三斜轴坐标系O-xyz进行建模，如图 1(c)所示。红色为x轴，绿色为y轴，蓝色为z轴，3个坐标轴与水平方向夹角分别为30°、150°、270°，单位长度$s = 3l/2$。格网坐标原点为$O(0, 0, 0)$，从格网中心g₁分别向x、y、z轴作垂线，与坐标轴交于点a、b、c，则g₁的坐标为：

此外，三斜轴坐标具有x+y+z=0的特性，所以只需计算出两个坐标轴的值便可得到第三个坐标轴的值。在六边形格网坐标下，距离表示从某一格网至另一格网经过的最少格网数，其计算公式为：

例如，图 1(c)存在距离值${L_{{g_2}, {g_3}}} = 6$，即表明从g₂到g₃至少要经过6个格网。与正方形格网相比，在距离计算时不需要平方和开根号等复杂运算，可以有效提升以距离作为启发因素的寻路算法的运行效率。

1.2   约束条件

不同室内场景与应用偏好下的路径规划往往涉及不同的约束条件，最常见的便是障碍物、时间、距离等。但是，现实需求已不仅仅满足于最短路径，而要更多顾及应用偏好，提供更加多样且个性化的路径选择^[4-5]。综合已有研究，将室内路径规划约束条件主要概括为两种：基于场景自身的约束条件和基于应用偏好的约束条件，具体分类如表 1所示。

表  1  室内路径规划约束条件分类表

Table  1.  Classification of Indoor Route Planning Constraints

一级分类	二级分类	约束条件	描述
场景自身	空间几何	墙壁	建筑物的轮廓，限制了路径规划进行的范围
		廊道	公共的可通行区域
		房间	具有公、私有属性的通行区域
		门窗	连通房间与廊道，通行具有时限性
		障碍物	房间或廊道内阻碍通行的可移动或固定的物体
		楼梯、扶梯及直梯	不同楼层间的通道
	环境属性	灯光	灯光的明暗度
		地板	地板的光滑度
		标语	标识指引
		楼层平面图	楼层结构示意图
	语义	开放时间	通行区域具有时限性
		宽度	可通行域的宽敞度
		权限	通行区域区分为公共和私有，需具有相应权限
应用偏好	机器人	转向	转向消耗较大，尽量避免转向
	行人	距离	起点至终点的距离
		辨识度	路径辨识的难易程度，需考虑地标可见性
		行人密度	行人分布密集程度
		安全性	路径沿途的风险
		宽敞性	路径沿途开阔程度
		跨楼层方式	楼梯、扶梯、直梯
		味道	路径沿途的气味

下载: 导出CSV 

| 显示表格

1.3   室内场景建模

室内结构复杂，针对§1.2中分析的室内路径规划约束条件，选取廊道、障碍物、墙壁、地标点和行人分布等进行场景建模。建模过程主要分为三个过程：（1）将选取的室内元素矢量化(如室内结构平面图)。（2）根据给定分辨率建立坐标系。（3）结合数值微分（digital differential analyzer，DDA）算法和种子算法对矢量化数据进行六边形剖分，并为剖分格网赋值约束条件信息，得到室内场景格网集合。对图 2(a)中所示室内场景进行六边形剖分建模，得到如图 2(b)所示的结果，通过六边形格网表示室内场景，并将约束条件叠加至格网，使得关键信息得以保留，更好地辅助后续路径规划。

图  2  室内场景建模示意图

Figure  2.  Diagram of Indoor Scene Modeling

下载: 全尺寸图片 幻灯片

2 应用偏好及约束条件建模

由于室内场景、路径规划的目标对象等不同，往往对应不同的应用偏好，本文选取距离、辨识度、行人密度3个约束条件，对其在路径规划中的影响进行说明，并建立相应计算模型。

2.1   辨识度与地标强度格网

在室内导航中，多达85%的路径描述涉及地标，地标可以辅助行人更好地辨识方向和定位，提升路径的辨识度，增加路径选择的正确性^[5]。已有研究在路径规划中考虑地标的影响，但是仍存在一些问题：仅考虑地标在可视范围内的影响，超出可视范围则影响消失；地标点影响强度由近至远单一递减，可能会导致规划路径过于趋向地标。因此本文建立了地标点影响强度先均衡、后衰减的模型，即在可视范围R内其影响强度恒定，当超出R后强度线性衰减，至2R时衰减为0。结合正六边形室内场景建模和地标强度衰减模型，本文建立了地标强度格网(landmark strength grid，LSG)，即在场景建模得到的格网集合基础上，通过衰减模型计算格网地标强度。过程如下：首先确定地标格网l_i，根据地标功能性、可视性等因素设置其最大强度S_li及可视范围R_li；然后以该格网为中心执行六邻域扩散，扩散时，根据地标强度衰减模型，地标l_i对格网g_n的影响强度为S_{li, gn}，计算公式如下：

同一格网g_n可能同时受多个地标影响，其综合地标强度S(g_n)表示为各个地标点影响强度之和，计算公式如下：

式中，N为格网g_n处可见的地标个数。如图 3(a)中所示的室内场景，包括3个地标点l₁、l₂、l₃，1个水池，可视范围分别为20、12和12格网单元。假设水池高度较低，不影响地标可视性，其地标强度格网如图 3(b)所示；假设水池高度较高，行人和地标间不能通视，此时建立地标强度格网如图 3(c)所示。

图  3  地标强度格网示意图

Figure  3.  Diagram of Landmark Strength Grids

下载: 全尺寸图片 幻灯片

比较图 3(b)和图 3(c)发现，水池通视性影响到了地标强度格网的构建，图 3(c)中红框标记处，由于水池的阻挡，l₁和l₃的影响未能到达，导致强度较图 3(b)偏低。

2.2   行人密度与行人分布热力格网

在路径规划中，行人的分布情况也影响着路径的选择，且具有两面性，如行人密集度对于安保人员意味着风险，是正影响，需要靠近，而对于乘客则意味着拥堵，是负影响，需要避让。行人分布情况可以通过获取行人在室内的位置信息得到，而位置信息往往为离散的点，不能直接应用于路径规划。核密度估计(kernel density estimation，KDE)可以利用离散点估计得到其在连续空间的分布规律。本文根据室内行人位置信息，通过核密度估计算法，模拟得到室内行人在连续格网空间的热力分布情况，建立了行人热力格网(pedestrian heat grid，PHG)，格网的分布密度估计$K\left({{g_n}} \right)$计算公式如下：

式中，N表示与格网${{g_n}}$距离小于或等于h的行人格网p_i的总数；${L_{{g_n}, {p_i}}}$表示格网${{g_n}}$与行人格网p_i的距离; k为空间权重系数，在参数预设时，已有研究表明k对热力分布影响不大，根据4次空间权重方程可设为3/4；h为距离衰减阈值，其值需要根据场景情况加以考虑。

3 A^*算法与约束条件应用

基于六边形格网的场景建模更为精细，但同时带来较大的计算消耗，需要采取缩小搜索范围、分解搜索过程等策略来提高算法效率。A^*算法作为启发式搜索算法，通过设置启发因素，引导算法向前进可能性最大的方向搜索，能有效缩小搜索范围和提高搜索效率，公式如下：

式中，F(n)为节点n至终点D的总代价估计值; G(n)为从起点O搜索到探查点n实际付出代价；H(n)为节点n至终点D的估计代价。

在正六边形场景建模基础上，针对特定应用偏好选取适当的约束条件作为A^*算法的启发因素，则探测格网${{g_n}}$的总代价估值为既定代价加上各个启发因素与所占比重乘积的累加，计算公式如下：

此外，本文选取距离、辨识度和行人密度3个限制条件作为启发因素，但是由于3种启发因素量纲并不统一，需先对其进行归一化操作，公式如下：

式中，$L{g_n}, {g_D}$为格网${{g_n}}$与目标格网${{g_D}}$的距离；$L{g_n}, {g_D}$为起点所在格网${{g_O}}$与目标格网${{g_D}}$的距离; $S\left({{g_n}} \right)$为格网${{g_n}}$的地标强度；${S_{{\rm{min}}}}$、${S_{{\rm{max}}}}$分别为地标强度的最小、最大值；$K({g_n})$为格网${{g_n}}$的行人热力；${K_{{\rm{min}}}}$、${K_{{\rm{max}}}}$分别为行人热力的最小、最大值。因此，根据式（7），可以得到本文选取的3种约束条件基于正六边形的A^*算法估值函数表达式，即：

式中，${w_L}$、${w_S}$、${w_K}$分别为距离、地标强度、行人热力启发因素的权重，且${w_L} + {w_S} + {w_K} = 1$。

4 实验与评价

4.1   数据准备

本文选取武汉市某商贸广场第八层室内场景作为实验区域，通过百度地图矢量化得到室内矢量结构图，如图 4(a)所示。分辨率设置对于场景建模不可忽视，本文分别设置为0.2 m、0.5 m、1 m、2 m分辨率进行对比实验，发现0.2 m和0.5 m分辨率下，室内结构能得到很好的模拟，而分辨率为1 m和2 m时，一些较窄的通道和细节丢失。对于室内行人分布情况，选取0.5 m作为格网分辨率，并设置辐射范围为1 m、2 m、3 m进行核密度估计，当辐射范围为2 m时，能兼顾算法效率和模拟结果。据此采用更接近行人步长的0.5 m分辨率，将距离衰减阈值h设置为4格网单元，利用采集的地标点和模拟的室内行人分布数据，分别建立室内地标强度格网和室内行人热力格网(假设为负影响，避开拥挤区域)，并利用式(9)和式(10)进行归一化处理，其结果如图 4(b)和图 4(c)所示。

图  4  实验区域室内场景、地标强度格网及行人热力格网

Figure  4.  Indoor Scene, Landmark Strength Grid and Pedestrian Heat Grid of Experimental Area

下载: 全尺寸图片 幻灯片

4.2   多约束条件及权重配置

实验选取距离、辨识度与行人密度3个限制条件，配置了5组权重系数，如表 2所示，其路径规划结果分别记为${P_{{\rm{SPA}}}}$、${P_L}$、${P_{L + S}}$、${P_{L + K}}$及${P_{L + S + K}}$。NULL表示不考虑启发因素，即简单路径分析（simple path analysis，SPA）；L表示以距离作为启发因素；L+S表示考虑距离和地标强度两个启发因素；L+K表示考虑距离和行人热力两个启发因素；而L+S+K则表示兼顾距离、地标强度及行人热力3个因素。

表  2  启发因素选择及权重配置表

Table  2.  Choice and Weight Configuration of Heuristic Factors

启发因素	wL	wS	wK
NULL	0	0	0
L	1	0	0
L+S	1/2	1/2	0
L+K	1/2	0	1/2
L+S+K	1/3	1/3	1/3

下载: 导出CSV 

| 显示表格

4.3   六边形与四边形对比

为了论述正方形与六边形在室内路径规划方面的差异，本实验分别通过六边形和四边形对实验区域建模，分别选取了两组起点O和终点D，并考虑距离启发因素得到的路径结果O₁D₁、O₂D₂如图 5所示。

图  5  基于四边形和六边形的路径规划结果

Figure  5.  Route Planning Results Based on Square and Hexagon

下载: 全尺寸图片 幻灯片

通过对比图 5(a)和图 5(b)，可以发现基于六边形的路径更加符合目标导向的寻路行为。而对比图 5(c)和图 5(d)，发现在距离和遍历格网数方面，六边形也均存在优势。

4.4   多约束条件对比

为了讨论多约束条件对室内路径规划的影响及基于六边形路径规划解决方案的有效性，本文在实验区域内选取4组OD，分别根据上文的权重配置进行了5次路径规划，并展示了O₁D₁路径结果，如图 6所示。

图  6  室内路径规划结果图

Figure  6.  Results of Indoor Route Planning

下载: 全尺寸图片 幻灯片

图 6从视觉上分别标记出了行人热力较高的区域A₁和地标强度较高的区域A₂，以及两个关键转折点p₁和p₂。对比5条路径可发现，${P_{L + K}}$和${P_{L + S + K}}$绕过了区域A₁，说明在导航中顾及行人热力的启发条件可有效回避人群拥挤的区域；${P_{L + S}}$、${P_{L + K}}$及${P_{L + S + K}}$都经过了区域A₂，其中${P_{L + K}}$和${P_{L + S + K}}$在行人热力因素下为了回避拥挤区域A₁到达了点p₁，后续路径经过区域A₂从距离上也能解释，但是${P_{L + S}}$在并未回避拥挤区域A₁而到达点p₂的情况下，依然折向右方经过了区域A₂，说明在导航中顾及地标强度的路径可有效引导行人经过地标强度较高区域。可以看出，本文提出的顾及多约束条件室内路径规划是有效的。

另外，为了定量化阐述以上结果，本文选择了距离、平均行人热力、平均地标强度和遍历格网数等指标对4组OD的不同路径进行了统计分析，其结果如图 7所示。从距离指标上看，${P_{{\rm{SPA}}}}$距离总是略短于其他路径的距离，但其遍历格网数却明显高于其他路径，表明不考虑任何启发因素，虽能找到距离最短路径，但效率较低。如果考虑距离因素，可大幅降低搜索范围，并得到最短路径或者次优解，如${P_{L + S}}$、${P_{L + K}}$及${P_{L + S + K}}$。但从平均地标强度和平均行人热力等指标观察，路径${P_{{\rm{SPA}}}}$和${P_L}$路径规划并不一定最优，其可能会经过不易辨识或者比较拥挤的区域，而${P_{L + S}}$、${P_{L + K}}$及${P_{L + S + K}}$等考虑了地标强度或者行人热力，能一定程度上克服该缺点。例如，在考虑地标强度因素时，${P_{L + K}}$和${P_{L + S + K}}$都能经过更易辨识的区域，平均地标强度也会更高，如图 7(c)所示；在考虑行人热力因素时，${P_{L + K}}$和${P_{L + S + K}}$都能避开拥挤区域，平均行人热力明显降低，如图 7(d)所示。总体来说，顾及多约束条件的室内路径规划算法可兼顾不同启发因素对路径规划的影响，得到更符合应用偏好的路径。

图  7  不同启发因素下路径结果对比

Figure  7.  Comparison of Routes Considering Different Heuristic Factors

下载: 全尺寸图片 幻灯片

5 结语

室内路径规划受到多种限制条件的影响，在考虑室内场景的空间几何、环境属性信息的同时，还需兼顾应用偏好。六边形格网模型可以有效集成多种约束条件，且方便进行叠加分析计算，而各向同性特性也使其在处理邻域问题时具有优势。A^*算法可以有效考虑多启发因素的影响，得到符合应用偏好的路径。本文旨在提供一种通用的室内场景建模、约束条件及寻路算法有机结合的解决方案，并以距离、辨识度和行人密度为例，说明其在路径规划中的影响及应用。实验表明，该方案能够有效顾及各个因素，并提供更符合应用偏好的路径。