留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

顾及地标可视性的室内导航路径优化算法

刘涛 张星 李清泉 方志祥

刘涛, 张星, 李清泉, 方志祥. 顾及地标可视性的室内导航路径优化算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
引用本文: 刘涛, 张星, 李清泉, 方志祥. 顾及地标可视性的室内导航路径优化算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
LIU Tao, ZHANG Xing, LI Qingquan, FANG Zhixiang. An Indoor Pedestrian Route Planning Algorithm Based on Landmark Visibility[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
Citation: LIU Tao, ZHANG Xing, LI Qingquan, FANG Zhixiang. An Indoor Pedestrian Route Planning Algorithm Based on Landmark Visibility[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387

顾及地标可视性的室内导航路径优化算法

doi: 10.13203/j.whugis20150387
基金项目: 

国家自然科学基金 41301511

国家自然科学基金 41371377

国家自然科学基金 41371420

深圳市科技计划项目 JCYJ20140418095735587

深圳市科技计划项目 ZDSY20121019111146499

深圳市科技计划项目 JSGG20121026111056204

深圳大学科研启动基金 2016064

详细信息
    作者简介:

    刘涛, 博士生, 主要从事行人导航方法研究。liuzimo@whu.edu.cn

    通讯作者: 李清泉, 博士, 教授。liqq@szu.edu.cn
  • 中图分类号: P208

An Indoor Pedestrian Route Planning Algorithm Based on Landmark Visibility

Funds: 

The National Natural Science Foundation of China 41301511

The National Natural Science Foundation of China 41371377

The National Natural Science Foundation of China 41371420

Shenzhen Scientific Research and Development Funding Program JCYJ20140418095735587

Shenzhen Scientific Research and Development Funding Program ZDSY20121019111146499

Shenzhen Scientific Research and Development Funding Program JSGG20121026111056204

Scientific Research Fund of Shenzhen University 2016064

More Information
    Author Bio:

    LIU Tao, PhD candidate, specializes in pedestrian navigation and location based service.liuzimo@whu.edu.cn

    Corresponding author: LI Qingquan, PhD, professor.liqq@szu.edu.cn
图(5) / 表(3)
计量
  • 文章访问数:  1246
  • HTML全文浏览量:  71
  • PDF下载量:  491
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-10-08
  • 刊出日期:  2017-01-05

顾及地标可视性的室内导航路径优化算法

doi: 10.13203/j.whugis20150387
    基金项目:

    国家自然科学基金 41301511

    国家自然科学基金 41371377

    国家自然科学基金 41371420

    深圳市科技计划项目 JCYJ20140418095735587

    深圳市科技计划项目 ZDSY20121019111146499

    深圳市科技计划项目 JSGG20121026111056204

    深圳大学科研启动基金 2016064

    作者简介:

    刘涛, 博士生, 主要从事行人导航方法研究。liuzimo@whu.edu.cn

    通讯作者: 李清泉, 博士, 教授。liqq@szu.edu.cn
  • 中图分类号: P208

摘要: 提出了一种构建室内行人通行网络的方法,利用矢量建筑图自动构建室内建筑、地标的可视关系,建立行人导航通行规则,支持室内导航路径规划。实验结果表明,此方法能够有效描述室内行人通行规则,并满足拓扑网络构建的实时性需求,减少大规模存储与维护室内路网的压力。在此基础上提出了一种多目标导航路径优化算法,该算法时间开销较低,能够实时地进行路径规划,得到的最优路径与最短路径相比具有更高的地标可见性和覆盖率。

English Abstract

刘涛, 张星, 李清泉, 方志祥. 顾及地标可视性的室内导航路径优化算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
引用本文: 刘涛, 张星, 李清泉, 方志祥. 顾及地标可视性的室内导航路径优化算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
LIU Tao, ZHANG Xing, LI Qingquan, FANG Zhixiang. An Indoor Pedestrian Route Planning Algorithm Based on Landmark Visibility[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
Citation: LIU Tao, ZHANG Xing, LI Qingquan, FANG Zhixiang. An Indoor Pedestrian Route Planning Algorithm Based on Landmark Visibility[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 43-48. doi: 10.13203/j.whugis20150387
  • 随着社会的迅猛发展,基于位置的服务(location based service,LBS)受到越来越多的关注,室内外一体化的智能位置需求日益增长。目前,室内外一体化行人导航系统缺乏在室内环境下的精确定位方法和路径优化方法。已有的室内定位方法主要包括基于无线电信号[1-2]的方法和基于惯性传感器[3-4](航位推算)的方法等,可以在一定程度上满足室内定位需求。进行路径规划需要已知行人通行网络,目前构建室内行人通行网络的方法仍需要很多人工操作,无法满足自动化、实时化的导航需求。因此,自动构建室内通行网络,实时地规划行人导航路径,对于室内外一体化的行人导航具有重要意义。

    国内外对路径规划的研究主要集中在机器人路径选择和智能避障方面。对于行人的导航路径规划方法,文献[5]针对三维室内模型提出了一种多级室内路径规划方法,但最终得到的路径并不符合人们的行走习惯。文献[6]利用三角网剖分的思想实现了室内路网构建,但是这种方法需要大量的人工交互,算法的时间开销大,无法满足实时性需求。文献[7]应用图论的方法提出了一种基于语义的室内导航模型,但这种模型属于概念模型,无法直接应用到室内的路径规划。文献[8]针对三维建筑模型提出了室内空间自动提取方法,但是需要已知室内的三维模型。根据目前的国内外研究现状,本文提出了一种自动构建室内行人通行网络的方法。该方法利用室内建筑平面图构建行人通行网络,可以满足实时性的导航需求,能够有效地降低导航系统对室内路网数据的存储量。

    地标作为导航寻路的关键要素,可以降低寻路过程中的认知负担、增强导航信心,对于安抚感情和保证寻路决策的正确性有很大作用[9]。目前国内外已经有研究利用地标来增强路径引导信息[10-11]、使用地标及空间认知对行人导航路径进行规划[12-13]。但是大部分的研究没有考虑到地标的可见性,以及路径方向对地标选择的影响。地标相对路径是否可见,以及路径方向引起的地标识别难易程度的变化,可直接影响行人在导航中对地标的利用效率。特别是在室内导航环境中,地标的可见性受到室内复杂结构、障碍物等诸多因素的干扰,其可见性相比室外会大大降低。因此,本文在构建行人通行网络的基础上顾及地标可视范围,综合考虑路径方向、路径的地标覆盖率、路径距离等多个目标的影响,使用多目标蚁群算法[14]得到了适合行人导航的最优路径。

    • 本文使用可视图法构建室内建筑的拓扑网络。其原理是将起点和环境中的所有其他顶点进行组合连接,要求起点和各个顶点之间的连线不能穿越障碍物,即直线是“可视的”。图 1(a)1(b)分别表示建筑物内部和建筑物之间的可视关系。在图 1(a)中,与顶点S可视的点包括ABHEGF,编码所有与S可视的顶点并进行存储就构建了顶点间的拓扑关系。任意两点间连通的线段表示为可达的通行链接,对室内地图所有顶点构建可视的连通关系,就构成了基础通行网络。

      图  1  室内通行拓扑链接及通行规则

      Figure 1.  Indoor Pedestrian Walking Links and Walking Rules

    • 传统可视图法构建的拓扑关系中没有考虑“可达性”的问题。通行节点之间是否可达,不仅要求两点之间是否可视,还要考虑行人导航中的通行规则。一条从起点O到终点D的路径,在没有通行规则约束的情况下,可能的行人规划路径为O-A-B-E-D,如图 1(d)所示,而实际位于B点的行人是不可能穿越墙壁到达E点。在通行规则约束下则排除了上述路径的可能性,得到的规划路径为O-A-B-C-D,如图 1(c)所示。因此,根据行人的实际通行情况,建立通行规则,排除那些不符合逻辑的规划路径,对于行人导航来说十分必要。

      利用可视图构建的拓扑网络定义行人导航路径通行规则:设当前节点为V,与当前节点可视的候选节点集合为S={Vi},可能的通行方向为VVi,当前节点与其前一节点通行方向为VV

      规则一如果V所在墙体边的个数小于或等于1,则VVi一定可达。

      规则二如果V所在的墙体边个数大于1,则根据VV的方向判断V属于墙体的哪一侧,与V所在墙体相反的Vi不可达。

      其中,规则一如图 1(e)所示,A点所在墙体边个数为1,且O点与A点可视,固通行方向OA点可达。规则二如图 1(f)所示,B点所在的墙体边个数为3,根据OB的通行方向判断出B点位于墙BC的下侧和墙BE的左侧,而候选点D位于BC的下侧和BE的右侧,故D点不可达。

    • 现有的行人导航模型对地标或兴趣点的存储通常只包含编号、坐标和类型等信息,没有涉及到地标对于路径的拓扑关联描述。一方面,地标的可见性是路径引导的重要因素,特别是在室内导航环境下,其内部建筑的结构复杂、遮挡物多、能见度差等因素降低了地标的可见性。另一方面,路径与地标的相对位置方向对于地标引导路径也非常重要,路径方向与地标的夹角越小,行人对地标的易识别性就越强,对地标的利用机会就越大。因此,考虑地标的可见性和路径的方向建立室内路径与地标的可见关系十分必要。

      建立室内地标的可视拓扑关系需要对具体的室内环境选择特定的能见度阈值R。对每个地标建立半径为R的可视区域。判断通行链接是否经过地标的可视区域,记录通行链接与可视区域边界的交点坐标,并计算地标覆盖通行链接的长度,用于路径规划时计算路径的地标属性。如图 2(a)所示,地标的可见范围与通行链接的交点为p1p2p3p4p5p6图 2(b)中,计算通行链接被地标覆盖的长度需要判断是否被障碍物遮挡,不被遮挡且穿过地标可视区域的通行链接被赋予较大的权重用于路径规划。

      图  2  地标与通行链接的关系

      Figure 2.  Relationship Between Landmark and Walking Links

    • 在室内导航环境中,地标的可见性受室内复杂结构、障碍物等诸多因素的干扰,其可用性也相应降低。为了验证本文提出的室内行人通行网络模型的有效性,发挥室内地标在可见范围内的导航帮助,本文提出了顾及室内可视地标的行人导航路径规划方法,使用多目标优化的蚁群算法平衡了路径距离、地标利用率和地标个数对导航路径的影响。

    • 目前的行人导航系统中,多达85%的路径描述涉及地标,依据地标选择行人导航路径已经有很多研究[11-13]。地标相对于路径的距离和方向是选择导航路径的重要标准。路径的方向与可见地标的夹角越小,行人就越容易发现和利用地标;另一方面,地标的可视区域覆盖路径长度相对于路径总长度的比例越高,行人越能够有机会发现和利用地标作为导航线索。如图 3所示,路径OE与地标S1S2的可视范围相交于FGHI。路段OA被地标S1覆盖的长度为FA,与地标的夹角为a1;路段AB被地标S1覆盖的长度为AG,夹角为a2;路段BC被地标S2覆盖的长度为HI,与地标的夹角为a3。其中,a1 < a3 < 90°,a2> 90°。行人在路段OA上发现地标S1相比在路段BC上发现地标S2容易,利用地标S1的时间大于利用S2的时间。本文定义路段的地标利用率为:

      图  3  路径的地标利用率

      Figure 3.  Usage of Landmarks on an Indoor Route

      $$ U\left( i \right) = \left\{ {\begin{array}{*{20}{l}} {\frac{\alpha }{S},S > 0}\\ {0,{\rm{其他}}} \end{array}} \right. $$ (1)

      式中,a是路段方向与可见地标的夹角;S是地标覆盖路段的比率。路径的地标利用率为:

      $$ {R_U}\left( n \right) = \sum\limits_{i = 1}^n {U\left( i \right)} $$ (2)

      RU的值越小,路径的地标利用率越高。

    • 本文使用蚁群算法的主要目的是多目标优化路径距离、路径地标利用率和地标个数等因素,得到地标利用率高、经过地标个数多、行程距离短的最优路径。

      首先利用蚁群算法的信息素模型来创建路径节点的候选解集,假设路径节点i在蚂蚁k的下一步可选节点集合中,其选择节点i的概率pki为:

      $$ p_i^k = \left\{ {\begin{array}{*{20}{l}} {\frac{{{{\left[ {{\tau _i}\left( t \right)} \right]}^\alpha } \cdot \left[ {{\eta _i}\left( t \right)} \right]\beta }}{{\sum {{{\left[ {{\tau _i}\left( t \right)} \right]}^\alpha } \cdot {{\left[ {{\eta _i}\left( t \right)} \right]}^\beta }} }},i \in {S_k}}\\ {0,{\rm{其他}}} \end{array}} \right. $$ (3)

      式中,τi(t)表示节点在t时刻的信息素数量;a是用于控制τi(t)影响的参数;ηi(t)是用于提供启发信息的优化函数;β是用于控制ηi(t)影响的参数;Sk是当前节点i在下一步可到达的相邻节点的集合。为了提高算法的收敛速度,本文使用当前路段方向与终点方向的夹角作为启发函数,如图 4所示,ωm2-m3m2-目的地之间的夹角。越小的ω,表示m3的期望越大。因此,定义启发函数为ηi(t)=eλcosω,其中λ是用于控制ω影响的参数。

      图  4  蚁群算法启发函数

      Figure 4.  Heuristic Function of Ant Colony Algorithm

      应用蚁群算法进行多目标优化的关键是将多目标问题转换成单目标[16],利用单目标解更新信息素。本文选择路径方法考虑路径距离D、路径的地标利用率RU和经过地标数量M。定义转换为单目标后的解V,有:

      $$ \min \left( V \right) = {w_1} \cdot D + {w_2} \cdot {R_U} + {w_3} \cdot M $$ (4)

      式中,w1w2w3是3种优化目标的权重。由于目标具有不同的尺度与量纲,需要对其进行单位化,使得V能够描述多个目标的综合影响。式(4)可以转换为:

      $$ \begin{array}{*{20}{l}} {\min \left( {V'} \right) = {w_1} \cdot \frac{{D - {D_{\min }}}}{{{D_{\max }} - {D_{\min }}}} + {w_2} \cdot }\\ {\frac{{{R_U} - {R_{{U_{\min }}}}}}{{{R_{{U_{\max }}}} - {R_{{U_{\min }}}}}} + {w_3} \cdot \frac{{{M_{\max }} - {M_{\min }}}}{{{M_{\max }} - {M_{\min }}}}} \end{array} $$ (5)

      式中,DmaxRUmaxMmax分别为给定区域内DRUM的最大值;DminRUminMmin分别为DRUM的最小值。使用单位化后的解V′更新信息素的公式为:

      $$ {\tau _i}\left( {t + 1} \right) = \left( {1 - \rho } \right){\tau _i} + \Delta \tau _i^k\left( t \right) $$ (6)
      $$ \Delta \tau _i^k\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\frac{Q}{{V'}},{\rm{成功}}}\\ {0,{\rm{其他}}} \end{array}} \right. $$ (7)

      式中,ρ是信息素挥发速度,ρ∈[0, 1];Q是信息素总量。

    • 根据上述求解模型,利用多目标蚁群算法求解最优路径的步骤为:(1)数据预处理。利用前文介绍的方法构建室内通行网络,以及地标与通行网络的拓扑关系,按照定义的通行规则约束,得到节点的可达禁忌表。(2)蚁群算法初始化。设定最大迭代次数T、每次迭代的蚂蚁总数量M、信息素的影响系数a、启发函数的影响系数β、信息素挥发系数ρ等参数的值。将M只蚂蚁放在搜索路径的起点。(3)将迭代后成功找到终点的蚂蚁取出,更新每只成功蚂蚁路径上的信息素。(4)重复步骤(3),直到最大搜索次数。(5)输出每次迭代中的蚂蚁的V值和路径,直到路径不发生明显变化。

    • 实时构建室内行人路网的方法有助于减小数据存储压力。经测试,本文算法对于包含321个节点、291条边、17个地标的矢量地图,构建室内行人拓扑网络的时间开销为1.38 s。本文算法可用于室内外一体化的行人导航。系统不需要存储每栋建筑的室内路网数据,当用户请求室内路径规划时,可调用算法实时生成室内路网和规划路径。

    • 选择深圳大学科技楼地下一层为实验区域,采集室内地标,利用本文介绍的方法构建了室内通行拓扑网络,如图 5(a)所示。在实验区域内选择4组OD分别利用本文算法与最短路径算法(shortest path algorithm, SPA)进行比较,如图 5(b)所示。实验区域参数如表 1,分别赋予3个优化目标相同的权重,多目标蚁群算法参数见表 2。本文算法对4组OD的平均时间开销为1.80 s,实验结果能够满足导航路径规划的实时性需求。

      表 1  实验区域内优化目标参数

      Table 1.  Optimization Parameters of Study Area

      w1 w2 w3 Dmax/m Dmin/m RUmax RUmin Mmax Mmin
      1/3 1/3 1/3 2 000 0 2 000 0 20 0

      表 2  多目标蚁群算法参数

      Table 2.  Parameters of Ant Colony Algorithm

      最大迭代次数 迭代蚂蚁数量 a β ρ λ
      30 20 0.5 5 0.2 0.5
    • 图 5展示了实验区域内本文算法得到的最优路径和SPA算法得到的最短路径结果。可以看出,本文算法构建的室内通行网络能够支持室内行人导航路径规划;得到的最优路径虽然增加了导航路径的行程距离,但是经过了更多室内地标,使得路径方向与地标方向的偏离度小、路径的地标覆盖率高。

      图  5  室内通行拓扑网络及优化导航路径

      Figure 5.  Generation of the Indoor Walking Networks and Optimized Route

      表 3中可以看出,SPA算法的距离比本文算法的距离短,但不超过60 m。表 3中的平均路径偏离度表示当路段经过地标的可见范围时,路径方向与地标夹角的平均值。地标覆盖率表示路径长度被地标可见范围覆盖的比例。可见,本文算法得到的最优路径的地标覆盖率明显高于SPA算法,行人行走最优路径对地标的利用时间和利用机会要大于最短路径。对于OD1OD3OD4本文算法的平均路径偏离度小于SPA算法,偏离度越小越有利于行人辨识和利用地标。对于OD2,本文算法的平均路径偏离度大于SPA算法。可见,平均路径偏离度与路径经过的地标数量有很大相关性。因此,本文利用的多目标优化蚁群算法能够平衡多种优化目标,得到的最优路径更加贴近行人导航的需求。

      表 3  行人路径比较结果

      Table 3.  Comparison Results of Pedestrian Routes

      OD 算法 距离/m 地标数量 平均路径偏离度/(°) 地标覆盖率/%
      1 SPA
      本文算法
      266
      323
      4
      7
      68
      45
      28
      39
      2 SPA
      本文算法
      267
      304
      2
      6
      18
      25
      14
      39
      3 SPA
      本文算法
      277
      334
      4
      6
      28
      27
      24
      31
      4 SPA
      本文算法
      273
      306
      5
      6
      59
      20
      28
      35
    • 本文提出了一种构建室内行人通行网络的方法,利用室内矢量地图自动建立符合通行规则的步行网络。在此基础上,本文提出了一种多目标优化行人导航路径方法,能够平衡路径距离、地标可见程度、地标个数等因素对路径的影响,满足实时规划路径的需求。实验结果表明,本文提出的通行拓扑网络构建及行人路径优化算法均具有较高的运行效率,时间消耗降低,能够为室内外一体化的行人导航应用提供数据与方法支撑。

参考文献 (14)

目录

    /

    返回文章
    返回