沙特国王大学视障室内导航系统的路径规划和可用性评估

沙特国王大学学报视觉障碍Abir Benabid Najjara，Al-Rama a，Arwa Rashed Al-Issab，Manar Hosnyba沙特阿拉伯沙特国王大学软件工程系b沙特阿拉伯沙特国王大学计算机科学系阿提奇莱因福奥文章历史记录：收到2021年2022年1月29日修订2022年3月3日接受2022年3月28日网上发售保留字：室内导航视障蚁群算法偏差检测可用性评估A B S T R A C T对于视障者来说，独立的室内导航是非常具有挑战性的，特别是在不熟悉的环境中。本文介绍了一个导航系统的VI，计划一个优化的路径，安全地将他们带到他们想要的目的地的开发过程。本研究的第一个贡献是提出了一个路径规划算法，基于著名的蚁群优化（ACO）技术。该算法计算出一个最优的路线，同时考虑到用户的经验，避免与固定的障碍物碰撞。该算法的输出包括VI用户的移动方向，这些方向通过音频命令传递给他们，以指导他们的移动。还实现了一个路径跟踪算法，以便当VI偏离最初预定义的路径时，计算出的路径会动态更新。该功能利用一个步进和偏差检测器，该检测器可以计数和监视用户的步进，并将其与预期路径相最后，一个彻底的可用性评估，包括视障和未受损的用户进行了评估，结果表明，该系统最终达到了预期的目标，在有效性，效率和最重要的是，用户满意度。版权所有©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍根据世界卫生组织的数据，至少有22亿人患有视力障碍或失明（世界卫生组织，2019）。最新的技术发展，特别是移动计算技术，可以为视障人士提供技术援助，帮助他们完成日常工作，提高他们的生活质量，并使他们能够融入社会。目前有各种各样的辅助技术，可穿戴的或手持式的，可用于帮助有障碍的用户。导航系统的巨大扩展极大地促进了辅助工具的发展，这些辅助工具引导VI人员，特别是在户外环境中。然而，VI所面临的最具挑战性的问题之一是在不熟悉的室内场所安全地导航。室内导航应用于医院、机场、购物中心、学校等（Alqahtani等人，2018年）。对于此类应用，大多数建议集中在室内位置，*通讯作者。电子邮件地址：abbenabid@ksu.edu.sa（A. Benabid Najjar）。沙特国王大学负责同行审查定 位 和 定 位 （ Sakpere 等 人 ， 2017 ） 和 / 或 障 碍 物 检 测（Veeranjaneyulu等人，2019年）的报告。相比之下，我们的工作重点是导航模块。这旨在帮助VI在不熟悉的室内环境中找到最佳路径，这对他们的独立性和安全性至关重要。因此，这项研究工作的主要动机是通过开发一个有用的室内导航移动应用程序，可以安全地将他们带到所需的目的地，以促进VI的导航过程。开发过程遵循以用户为中心的设计（UCD），因为VI用户是贯穿系统开发生命周期的焦点 系统要求最初是从在当地环境中进行的需求发现研究中提炼出来的（Hosny等人， 2015年）。本文提出的系统设计结合了移动设备中最先进的技术和路径规划和路径跟踪的优化技术。这项研究工作的贡献有三个方面：首先，路径规划是任何导航系统中的重要组成部分自20世纪70年代以来，路径规划问题一直是一个有趣的研究领域，特别是在机器人领域（ Patle 和 G 。 Babu L ， A.Pandey ， D.R. K. Parhi ， 和A.Jagadeesh，，2019）。它旨在找到两点之间的最佳路线，从而节省时间，精力和资源。然而，将这些技术从机器人领域引入导航系统，https://doi.org/10.1016/j.jksuci.2022.03.0041319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comA. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7015需要进一步的设计约束以确保使用者的安全此外，用于VI的最佳路径通常不简单地是最短路径，因为用户的偏好和需求可能由于底层路径特征和环境的景观而变化。因此，本文提出了一种路径规划算法，基于蚁群优化（ACO），一种技术，可以找到一个优化的路线，同时考虑到VI用户在算法的每一步和目标函数中都考虑了人的因素，特别是虚拟仪器用户的特殊需求其次，大多数导航系统具有路径跟踪机制，以保证导航的可靠性和正确性。系统应检查导航人员是否遵循建议的路径，并通知用户是否发生任何偏离。然而，对于完全依赖该系统安全地将其引导到所需目的地的VI来说，遵循导航员给出的指令尤其具有挑战性。因此，计算出的路径应动态更新时，一旦VI用户从最初规划的path.To实现这一点，我们建议的路径规划器集成了一个路径跟踪模块，检测任何偏离规划路径，提醒VI用户，并触发一个动态的路径重新规划。第三，虽然许多以前的研究只提供了一个模拟分析，而不是实时的应用程序和实验，本文提出并讨论了所提出的系统的可用性评估的结果。系统的可用性进行了评估的有效性，效率和用户满意度，涉及非VI和VI用户。虽然结果仍然是初步的，他们表明高精度和良好的用户本文的其余部分组织如下：在第2回顾了一些相关工作后，第3介绍了系统架构设计的概述。第四介绍了导航模块的设计与实现，包括蚁群算法的路径规划和路径跟随模块。第5节介绍了可用性评估，第6节讨论了这项工作的主要贡献和局限性以及可能的增强。第七节最后对未来的研究方向提出了一些思考。2. 相关作品目前有多种辅助技术可供残疾人使用。第一小节介绍了一些系统，提出了帮助VI在不同的环境中找到自己的方式。然后，第二部分重点介绍了一些启发性的ACO路径规划方法，特别是在机器人技术中提出的。最后，第三小节回顾了一些路径跟踪技术，其中计算的路径可以在检测到由于障碍物或没有正确地遵循指令而引起的偏差的情况下被更新。2.1. VI辅助导航在20世纪90年代，Meijer开发的一个系统（Meijer，1992），即vOICe，为盲人提供了图像到声音的渲染。该原型由一个数码相机连接到传统的眼镜，耳机和计算机所需的应用程序。该系统使用的立体视觉算法的输出，并将其分为五个垂直部分，对应于手振动警告用户在该方向上对应于该手指的随着手机的发展，Tapu et al. （Tapu等人， 2013）提出了一种实时系统，障碍物，并提醒部分VI用户关于它们，同时在未知环境中使用智能手机相机进行导航。实验表明，在识别障碍物的成功的结果。然而，如果相机的方向随着时间的推移不稳定因此，为了避免这种情况，他们建议使用非侵入性的胸部安装安全带。最近，视觉之声（SoV）项目（Caraiman等人，2019年）解决了这个问题的不同挑战性方面，如可穿戴性，实时操作，普及性，可用性和成本。基于立体视觉的组件在室外环境中执行场景重建和分割。还评估了VI用户的可用性。此外，Bansal等人（Bansal等人，2020）提出将立体视觉与超声波传感器相结合以检测实时环境中的障碍物。 所提出的系统使用立体视觉来识别和跟踪位于较远距离的物体，而超声波传感器用于检测位于较短距离的物体可以注意到，基于计算机视觉系统的开发和增强已经成为许多工作的主要研究主题。很少有研究提出了其他替代方案，例如使用RoboCart中提出的射频识别（RFID）（Kulyukin等人，2005年）的机器人辅助导航，以帮助VI人在室内超市，其中定位依赖于RFID标签部署到对象的环境。在路径规划计算方面，最常用的算法是Dijkstra算法. Nicolas Tissot（Tissot，2003）提出了一个VI室内导航系统的原型。该系统是为个人数字助理（PDA）设计的，有一些预定义的目的地，如最近的信息台。导航器模块然后负责使用Dijkstra算法计算两个位置之间的最佳路径Al-Ammar等人（xxxx）提出了一种用于盲人和VI的智能手机导航系统的设计。拟议的设计是基于一些假设，如VI可以识别障碍物，并避免不安全的地方使用白色手杖或依赖于他们的其他感官，如听觉。导航依赖于DijkstraHosny等人 （Hosny等人， 2015年）提出了一个室内导航系统的VI人谁使用电动轮椅。系统采用A* 算法进行路径规划，在算法的目标函数中考虑了虚拟仪器的需求和偏好路线的特点包括没有障碍物，转弯少，靠近墙壁，以及容纳线索和地标。最近，李才和小玲朱（蔡和朱，11月。 2018）提出使用安装有红外发射/接收模块和语音模块的传统手杖。利用红外技术检测障碍物，然后根据盲人与障碍物的距离通过语音模块通知用户。作者特别提出了蚁群算法，并通过仿真对系统进行了测试结果表明，ACO作为盲导的可行性。2.2. 路径规划对于路径规划模块，如下所述，许多方法都是从机器人领域得到启发的。关于动态环境中的机器人路径规划的最近详细调查可以在（Cai等人，2019年）;其中指出，包括ACO在内的反应式方法正在快速增长，移动机器人导航领域，因为它们优于实时导航问题的经典方法。A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7016一些工作提出了使用蚁群算法来解决路径规划问题。Yee Zi Cong和S. G. Ponnambalam（Yee andPonnambalam，2009）提出了一种用于寻找移动机器人路径的蚁群优化算法。我们做了几个假设，例如，在一个有静态障碍物的静态环境中，一只蚂蚁一次只移动到一个节点，并且没有对角线运动。 实验结果表明，蚁群算法优于现有的方法。Zeng Bi et al. （Zeng等人， 2009）改进了蚁群算法，使其在动态环境中为移动机器人寻找最优路径时更有效。该算法首先使用传感器获取仿真实验表明，改进算法在计算时间和收敛所需迭代次数方面均优于原算法Michael Brand等人（Brand等人，2010）提出了一种ACO，当机器人在动态环境中面对障碍物时，该ACO重新路由机器人。主要目标是在考虑两种信息素重新初始化方案的情况下，在网格网络中找到无碰撞的最短路径。在实验中，当比较两种方案时，它们实现了相同的路径长度，但是局部初始化在迭代次数方面优于全局初始化。最近，Kumar等人（Kumar等人，2020）通过提高信息素的蒸发速率来解决蚁群算法收敛缓慢的问题。他们提出了一种用于移动机器人的模糊ACO（FACO），其中路径信息素更新机制考虑了两种类型的路径，有利和不利。性能的FACO算法进行了评估，通过仿真，并表明它克服了收敛速度慢的问题。Shiguo等人 （Li等人， 2020）解决了机器人路径规划问题，不仅考虑了路径长度，而且考虑了转弯次数。采用A* 算法提高了收敛速度，并在信息素浓度计算中考虑了转折点。仿真结果从收敛性、迭代次数、路径长度和转弯次数等方面对改进蚁群算法的性能进行了Ma和Mei（Ma和Mei，2020）提出了一种改进的移动机器人ACO路径规划，以解决收敛速度慢，陷入局部最优和转弯次数的问题他们使用跳跃点搜索（JPS）策略来消除不太有希望的节点。通过仿真和实际移动机器人导航实验对算法的性能进行了评估，验证了改进算法在解决移动机器人路径规划问题上的有效性和高效性。2.3. 路径跟踪已经提出了旨在检测与建议路径的任何漂移或偏离的不同方法。这些方法取决于不同类型的技术，如GPS，Wi-Fi和不同的传感器。由于我们考虑的是室内环境和离线导航，使用大多数智能手机中嵌入的传感器是一个合适的解决方案来检测我们案例中的偏差Vinod Pathangay（Pathangay，2008）介绍了一种使用安装的摄像机检测VI用户偏离预定义路径的方法。在静态室内环境中考虑路径跟踪，该环境具有将与当前路径或测试路径进行比较的路径的预定义训练帧。实验Serra等人（Serra等人，2010）提出了一种依赖于航位推算定位的室内导航系统，其中基于先前已知的 位置来估计当前位置。该系统是在智能手机上开发的，以利用嵌入式传感器。分别使用罗盘和加速度计计算步数和方向。实验表明，在检测用户的位置和方向的良好效果。Link等人（Link等人，2011）提出了一种基于智能手机中嵌入的加速度计和指南针的逐向导航系统。使用生物信息学领域采用的序列比对方法完成预期步骤和检测步骤的匹配。在实验中，他们在户外环境中将他们的方法与GPS进行了比较，以测量精度。他们还在室内环境中测试了该系统，以显示其鲁棒性。最近，Zekany（Zékány，2019）采用了这种技术（Link等人，2011）;作为针对VI的室内定位系统的一部分。表1提供了上面讨论的一些相关研究的总结，并显示了本文与以前研究相比的主要贡献。可以注意到，许多现有的工作在导航的VI集中在障碍物检测使用立体视觉。讨论VI路径规划问题的少数作品建议使用Dijkstra或A* 算法，除了（Cai和Zhu，2018年11月）建议使用ACO。另一方面，蚁群算法在移动机器人导航领域已经证明了它的鲁棒性和高效性。 此外，如（Cai et al.，2019年），大多数现有的作品只提供了模拟分析，而不是实时应用和实验。从机器人领域引入这些技术并将其应用于导航系统需要进一步的设计约束，以确保用户的安全。这可以使用路径跟踪模块来实现。因此，本文提出将ACO路径规划和首次拟合技术（Link et al.，2011年）的路径跟踪，以建立一个完整的室内导航系统的VI。此外，我们提出的可用性评估的结果，涉及真正的VI用户，而不仅仅是模拟分析。3. 系统概述由于我们的系统是为视障人士开发的，因此采用了UCD方法，在设计过程的各个阶段都考虑到目标用户的特殊性。大多数辅助技术使用的传感器和人工制品对VI用户来说并不自然。然而，我们选择了让环境适应用户的需求，而不是强迫用户适应系统。本文建立在（Hosny等人，2015年），以收集从VI的要求。在（Hosny等人，2015年），作者调查了用户，以收集导航时的VI偏好。他们发现，大多数受访者更喜欢走直线，而有些人更喜欢走最短的路或沿着墙走。此外，定义了环境特征，并将路径特征分类为期望的或不期望的。这一分类方法在ACO中使用如第4.1节所述。环境被认为是已知的和静态的，这意味着障碍物的位置是预定义的，并且它们不会基于VI的移动而 图图1显示了系统的体系结构，包括四个主要模块，每个模块具有一组功能。第一个模块是管理员界面，部署在服务器端，负责地图创建和存储在位于远程服务器上的数据库中。第二模块，定位器，获取地图并使用信标或其他技术定位用户的当前位置。第三个模块是VI用户A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7017SBJIJ表1一些相关工作的总结。参考文献年度捐款VI导航路径ACO（Tapu等人，（2013年）在未知环境中使用智能手机摄像头进行静态和动态障碍物检测。（Caraiman等人，（2019年）2019年室外环境下的立体视觉场景重建与分割（Bansal等人， 2020年）在实时环境中使用超声波传感器的立体视觉进行障碍物检测。（Tissot，2003）2003年基于PDA的导航使用Dijkstra（xxxx）2011年使用Dijkstra算法的智能手机导航（Hosny等人，（2015年）使用A* 算法进行路径规划的VI室内导航轮椅系统（蔡和朱，2018年11月）2018装有红外线和语音模块并使用蚁群算法进行路径规划的规划（Yee和Ponnambalam，2009年）2009蚁群算法用于在已知环境中寻找移动机器人的路径。（Zeng等人，（2009年）改进了蚁群算法，用于动态环境下的路径搜索.（Brand等人，（2010年）当机器人在动态环境中遇到障碍物时，ACO重新路由机器人。（Kumar等人， 2020年）针对移动机器人的模糊蚁群算法收敛速度慢的问题，提出了一种模糊蚁群算法。（Li等人，2020年）2020年改进的ACO与A* 算法的移动机器人，同时考虑路径长度和转弯次数。（马和梅，2020）2020针对移动机器人，提出了一种基于跳跃点搜索的改进蚁群算法（JPS），旋转次数。Path following（Pathangay，2008）通过将路径的预定义训练帧与当前路径进行比较来进行偏差检测。（Serra等人，（2010年）智能手机室内导航系统，其中步骤和方向分别使用指南针和加速度计计算。（Link等人， 2011）2011步和偏差检测使用序列比对方法来检查预期步和检测步的匹配。（Zékány，2019）2019年基于（Link et al.，2011）作为VI的室内定位系统的一部分。本文2021使用ACO进行路径规划的VI的室内导航（Link等人，2011年），用于路径跟踪+涉及VI用户的可用性评估。目的地最后，第四个模块导航器是系统的核心，也是本文的重点。导航器负责动态路径规划过程，包括两个主要功能。首先，路径规划模块使用ACO算法计算路径然后，该模块从路径规划组件输入计算出的路径，在导航时跟踪路径，并检测任何偏差。如果出现偏差，它将通知路径规划组件该偏差，然后再次计算路径这将重复，直到VI用户到达所需的目的地。地图和构造最佳或接近最佳的路径，以下两个主要步骤（Talbi，2009），如图所示。 二、步骤1.该方法是由每只蚂蚁迭代地向部分解添加解分量，使用概率状态转移规则，直到得到完整解。如果一只蚂蚁到达一个已经被访问过的单元格或不可穿越的邻居，它可能会被杀死。蚂蚁根据连接当前细胞和下一个细胞的边缘上的信息素值选择下一个细胞。然后，蚂蚁将以如下定义的概率pij从节点i连续移动到节点j在该系统中，环境地图被建模为pa×gij1Þ大小相等的细胞（每个0.5米）。这栋楼有好几层，每个楼层被定义为网格并连接到其他楼层通过连接节点。除了障碍物外，地图还应识别任何特征，如地标、兴趣点、楼梯、墙壁和电梯的位置。此外，还定义了具有诸如蓝牙信标的传感器的节点。单元格具有诸如单元格类型、单元格权重、是否可遍历单元格和单元格图标等特征。管理员只需在初始化阶段提供此信息，然后将其保存到规划路径时使用的系统一个网站已经建立使用C#语言，以方便实验，并连接到SQL数据库服务器。该网站允许管理员登录系统并开始构建地图。该网站已使用RESTful（表述性状态转移）网络服务链接到Android应用程序，该服务收集所有所需数据并将其表示为XML网页。然后，在Android应用程序中读取此页面，并将所需数据存储到SQLite数据库中，以便在规划路径时使用。以下部分讨论导航器组件的设计、实现4. 导航模块i j¼P. sa×gb伊季哪里Sij是连接细胞i的边缘上的信息素的量和j.α是控制Sij的影响的参数。吉吉 是连接单元i和j的边的期望值。b是控制gij的影响的参数。过渡规则考虑到以下因素：- 信息素踪迹：它保存了好的、生成的解的属性;信息素踪迹的强度越大意味着路径越好。- 启发式信息：这个变量与问题有关，在构造解决方案时为蚂蚁提供线索在我们的方法中，这个启发式信息的值已被调整，以反映VI启发式信息gij在我们的ACO中定义如下：14.1. 路径规划模块gij¼ .aCijbDjcCdestð2Þ路径规划模块基于蚁群算法，该算法已应用于解决广泛的优化问题，并取得了成功的结果。ACO将处理后的哪里Cij是连接单元i和j的边的成本。Dj是下一个单元格j的期望值。A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7018J.... C¼x-xy-y3×ð ÞðpÞð Þ ¼1IJþ2Jð ÞFig. 1.室内导航系统架构。Cdest是从单元j开始到达期望目的地的估计成本。路径p的目标函数定义为：fp.xXC！.xXD！52pj2p在等式2中，启发式信息在大多数蚁群算法中是标准的，旨在减少到达目的地的总行驶距离。第二个组件旨在考虑VI的偏好和安全性。更具体地，计算小区的成本第三个部分是受启发式组件通常使用的A* 算法，其中考虑到估计的距离到达目的地。对于到达目的地的估计成本，我们使用曼哈顿距离定义为：destjj destj dest哪里y是指网格中单元的坐标。步骤2.这个步骤被称为信息素更新，并在两个阶段进行：。- 蒸发阶段：在此阶段，信息素按一定比例减少，以避免过早收敛，如以下函数所示，其中q是信息素蒸发速率：sij1/2-qsij8i;j21/2;n]jq2]0;1]4- 强化阶段：在这个阶段，信息素根据生成的解决方案进行更新。每个蚂蚁将增加与属于最佳路径的所选边相关联的信息素，其值与最佳获得路径p的质量成比例。根据以下等式，在所得到的路径上的信息素的量将增加一定量sij¼sijD其中，ni;jn是属于最佳路径p的边，并且D^f1其中fp是目标函数。并且它表示由每个蚂蚁获得的路径的总成本。该成本是基于两个标准计算的：1）Cij，在路径p中从单元i移动到单元j的成本，以及2）Dj，通过对单元中的特征的期望成本和不期望成本求和来计算的单元j在路径p中的期望性x1和x2是范围[0，1]中的权重，控制这两个标准的相对重要性，使得x1+x1= 1.0。该算法适用于网格环境。网格单元从0到N编号。要从一个单元格移动到另一个单元格，允许八种可能的移动（水平、垂直和对角线）。不应多次访问单元格，并且应在启动算法之前指定当目标单元被选择时，对于起始点的每个相邻单元，启发式信息将使用如下的等式22来对于垂直或水平单元，成本Ci j等于10，而对于对角单元，成本Ci j等于14（Zhang等人， 2012年）。为了计算合意性Dj，为每个单元中的期望特征和不期望特征这样做是图二. 提出的ACO算法的伪代码。a、b和c涉及控制每个分量的效果的不同权重。A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7019J通过给予期望的特征奖励（负惩罚）来降低它们的成本，并且用正惩罚来惩罚不期望的单元以增加它们的成本。当地图设计者指定单元格内容时，权重根据单元格期望值增加或减少5，如表2所示。最后一个分量是到目的地C dest的估计成本，其是使用如等式13中所定义的曼哈顿距离来计算的。在初始化变量之后，应该部署蚂蚁，其中每个蚂蚁将构造一个可能的解决方案。Talbi（Talbi，2009）建议从大量的蚂蚁开始。如果蚂蚁发现了一个可能的移动，在那里没有障碍物，节点还没有被访问，蚂蚁将继续前进;否则，它将被杀死，另一只蚂蚁将被部署。对于蚂蚁可以移动到的每个单元格，将计算转移概率，并选择概率最高的单元格。然后更新启发式信息和其他相关变量。重复上述步骤，直到达到最终目标当达到目标时，对所有节点进行信息素的蒸发，而对属于总成本最佳路径的节点进行强化4.2. 路径规划模块的实施和测试ACO最初是在Eclipse IDE上使用Java编程语言开发然后在修复所需参数后将其部署到Android应用程序上。必须调整这些参数，因为它们会影响算法的整体性能对ACO参数进行了逐一整定。最初，为每个参数指定一些推荐值;然后逐渐增加或减少。对于每个值，记录几次不同运行的结果，然后选择最佳参数值。考虑了两种不同的地图设计，20x20和30x40网格，包括墙、门、障碍物、兴趣点和地标。然后，ACO算法用不同的参数值对于a、b和q，除了推荐的值之外，在（Zhao and Zu ，2009 ）中进行了修正;a= 1.8，b= 1.5，q=0.2，我们考虑了另外四个值。对于蚂蚁的数量，我们考虑从10到40的随机值此外，我们没有指定一个固定的迭代次数来停止算法;相反，我们使它动态地依赖于迭代次数而没有改进。还测试的最后两个参数是目标函数中使用的权重（等式（5））x1x2。ACO的性能在以下方面进行了评估：目标函数以及处理时间。表3总结了基于参数调整过程的所选参数。然后使用这些参数在不同的标测图（8x8、20x20、30x40和80x80）上测试算法，每个标测图运行5次。在不同地图上运行算法的结果如表4所示，其中很明显，是稳定的除了第二张地图，所有的标准差5次运行中的目标函数为零。此外，几乎没有波动的计算路径的长度。最后，表2意愿分类。不想要的1. 最短路径（总距离）1.障碍物（不可穿越）2. 直线路径2. 障碍物附近（+5）3. 3.第三章：最后的约定楼梯/自动扶梯（不可穿越）4. 兴趣点附近（POI）（-5）4.靠近楼梯/自动扶梯（+5）对于相对较小到中等的地图，处理时间小于1秒，而对于最大的地图（80x80），处理时间约为3秒。此外，结果表明，所得到的路径满足路径约束，并实现了目标函数，在选择所需的细胞，避免障碍物，并步行附近的墙壁和地标。在图3中描绘的路径的部分中可以观察到，所计算的路径不一定是最短的，而是满足用户的偏好的路径，诸如在墙壁附近行走、在一些兴趣点旁边、以及避开障碍物并给它们留下一些分隔距离因此，似乎目标函数在搜索空间中适当地引导算法并实现其预期目的，而不会与障碍物发生碰撞。4.3. 路径跟踪模块路径跟随模块负责检查VI用户是否遵循建议的路径。一个关键的挑战是使用最少数量的传感器来确保高性能，从而为用户提供更多的便利。如今，大多数智能手机都嵌入了可用于导航的传感器。加速度计用于检测用户4.3.1. 步伐检测尽管在行走检测和步数方面进行了大量的研究和努力，但确保其在智能手机上的准确性和效率仍然具有挑战性（Kang等人， 2018年）。在本文中，一个简单的技术是只使用加速度传感器，是嵌入在大多数智能手机，这使得它很容易访问的步骤检测。它基于由（Link et al.，2011）来分割加速度计数据。这种技术最近已在（Zékány，2019）中被采用，用于步骤检测，作为针对VI人群的室内定位系统的一部分。在（Link等人， 2011），定义了五个连续采样点的窗口（W），并且利用了80%的重叠。如果在两个连续点之间存在高于阈值（p）的差然后，设置超时（t）以反映两个步骤之间经过的时间，以避免检测到错误步骤。此外，设置低通滤波器（f）以过滤重力噪声。三个参数被认为是从加速度计数据检测人的步骤。由于每个用户具有不同的行走风格，因此我们为实验设计了具有可变参数的界面，如图4所示，以便参数可以根据用户的行走风格进行调整。应该注意的是，如果用户改变步行速度，则应该修改值，使得系统可以正确地检测步数。未来的改进可能是实现自适应步检测器，自动检测步行速度或风格的变化4.3.2. 偏差检测路径跟随模块应该从路径规划模块接收作为单元格和方向的序列的规划路径，并且然后验证用户是否在正确的路径上指南针在这里用于通过将接收到的度数与某些角度进行比较来检测用户的方向。所实现的算法基于第一拟合技术（Link等人，2011），其中考虑了用于匹配路径的两种方法。存在两种模式：1）直接匹配模式，当检测到的台阶朝向与预期边缘的方向匹配并且高于某个阈值时，以及2）如果在五个连续台阶中比较边缘的预期方向和检测到的台阶朝向时存在差异，则将触发前瞻匹配模式A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7020表3ACO算法一BQ的蚂蚁数量迭代停止条件X1X2一BC0.50.50.235200.50.50.20.20.6表4在不同地图上运行ACO算法的结果。贴图大小目标函数平均值STD. 偏差路径长度（m）平均值STD. 偏差计算时间平均值STD. 偏差8x872.502.60.220.30.1420x2027213.3915.20.760.90.1430x40457.5021.10.821.10.0980x80282.501203.20.34前瞻匹配模式将进一步寻找匹配的边缘方向上的预期路线和映射检测到的步骤。实现的算法容忍三个不正确的步骤，然后启动前瞻匹配模式，在那里它将开始匹配的最后三个连续检测到的步骤与三个未来- ING预期的步骤。5. 可用性评价使用非VI用户以及VI用户评估了拟议系统的可用性评估的目的主要是评估5.1. 可用性标准（ISO 9241-11：2018）（[30]）将效率、有效性和满意度确定为可用性的主要属性。对于拟议的制度，这三项标准可界定如下：有效性旨在回答以下问题：这可以通过评估系统在检测步骤和偏差方面的准确度来评估，如下所示：准确度=准确度其中，真阴性（TN）对应于当不存在实际步骤时没有检测到步骤，真阳性（TP）对应于正确检测到的步骤，假阴性（FN）对应于当存在步骤时没有检测到步骤，并且假阳性（FP）对应于错误检测到的步骤。d效率旨在回答以下问题：“用户需要付出多大努力才能做到这一点？”这可以通过测量任务完成的时间来评估。满意度旨在回答以下问题：“用户对产品的易用性有何看法？”系统可用性量表（SUS）是一项行业标准，用于评估系统使用的舒适度和可接受性。它包括十个问题，五个回答选项，从5.2. 参与者该系统进行了测试，共有17名参与者，10名非VI志愿者和7名VI参与者。年龄在18 - 37岁之间。近50%的参与者有在户外使用导航系统但所有电池类型图标地标兴趣点空障碍门壁传奇图3.第三章。使用ACO计算路径的示例A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7021见图4。 步骤检测界面截图。VI参与者除了参与测试一些正在开发的原型之外，没有其他经验（p）和（t）的值取决于用户的行走方式。结果表明，男性受试者的平均步行速度（p）为2.6m/s，略高于女性受试者的平均步行至于视力状况，表5显示了相同性别（女性）和相同年龄范围（20至32岁）的身高匹配的4名正常和4名VI参与者测试发现，VI参与者几乎以相同的速度行走，但频率略高于视力正常的参与者。事实上，（Clark-Carter et al.， 1986年）指出，盲人在有视力的向导的陪同下，步行速度将接近有视力的步行者。然而，如果他们独立行走，他们会放慢步伐，与他们喜欢的步行速度相比。5.3. 测试程序实验使用Android设备Galaxy S6 edge型号：SM-G925 I进行，总空间为32 GB。测试分三个阶段进行：1. 对10名非虚拟仪器用户进行试点测试，主要目的是在对目标虚拟仪器用户进行测试之前评估系统的准确性。2. 与三名VI用户进行了试点测试，这些用户具有测试不同导航系统（如Tango）的经验。该试点测试旨在指出测试说明和格式的任何问题。3. 最终测试，四名VI用户没有使用经验，所有测试通过首先通过改变这两个值来调整每个用户的合适的峰值阈值（p）和时间（t）并要求用户行走一定步数来开始。当系统三次正确检测到准确的步行步数时，阈值是固定的。然后，参与者被要求执行两项任务，如表6所示。在完成要求的任务后，要求VI参与者填写系统可用性量表表，以评估用户5.4. 非VI用户的测试结果非VI用户测试的主要目的是在对目标VI用户进行测试之前评估系统的准确性。在调整阈值后，参与者被要求执行任务1。如图6所示，最低准确度为90%。美国运动医学院（Schneider，2011）认为，如果20步中的18步和22步读数之间，则步检测准确。这在准确性方面相当于90%。此外，每个参与者的平均准确率高于96%，总体平均准确率为97.65%。然后，他们被要求按照屏幕上显示的方向执行任务2。实验测试结果表明，在所有情况下，对于所有用户，系统都能正确地检测到与规划路径的任何偏差，这意味着偏差检测的准确率等于100%大多数用户确实遵循了这条路径，在10个用户中，有4个用户偏离了这条路径，需要重新规划。在遵循建议路径时，还注意到实际步数和检测到的步数之间的差异，因为与任务1相比，用户用户变得更加小心，并试图仔细按照指示。没有提示音通知正常用户成功的步骤，也没有指示作为画外音;这是在与VI用户进行测试时添加的，如下所述。5.5. VI用户测试结果在通过与非VI用户的测试评估了系统的准确性后，本节报告了与VI用户的可用性测试结果，其中根据国际标准ISO 9241-11，从有效性、效率和用户满意度方面评估了可用性。该测试分两个阶段进行：试点测试和最终测试。因此，两个组在两个不同的日期参与了该可用性评估。VI使用者是具有不同教育背景的成年女性。第一组有测试不同导航系统的经验，而第二组完全没有导航系统的经验。5.5.1. 有效性测试首先校准适当的阈值，然后执行任务1。图7和表7显示了阶跃检测的平均精度。在第二组的最终测试中，我们在成功检测到步骤时添加了蜂鸣声表6可用性评估中执行的任务。任何导航系统。表5身高匹配正常和VI参与者的结果。可用性因素普通用户（10名参与者）在准确性和任务完成虚拟仪器用户（7名参加者）有效性、效率和满意度视力正常任务1.台阶检测走20步×10次走8步×6次平均身高cm157.75 157.75平均加速度阈值（p）m/s22.0 2.1步骤之间的平均时间（t）ms356 307任务二：偏差检测按照屏幕上显示的方向走跟着指示走A. Benabid Najjar，A. Rashed Al-Issa和M. Hosny沙特国王大学学报7022百分百百分之九十百分之八十百分之七十百分之六十百分之五十百分之四十百分之三十百分之二十百分之十0%的百分比最大精度最小精确度平均准确率用户1用户2用户3用户4用户5用户6用户7用户8用户9用户10见图6。 正常用户的步数检测准确性结果。正如试点测试参与者所建议的那样，试点测试被认为改进了第二组的结果如图7所示，由于还没有添加脚步检测蜂鸣声，因此对于第二测试组（从用户4到7），最低准确度等于66%。准确性已大大提高，但根据（施耐德，2011年）仍然可以注意到，对于七个用户中的四个，达到等于100%的最大准确度，这表明当用户具有几乎稳定的行走风格时，步数检测可以特别准确。表7显示了每组记录的总体平均准确度，可以注意到，由于检测到的任何步骤都增加了蜂鸣声，第二组具有更好的准确度。然后要求参与者按照画外音的指示进行任务2。大多数虚拟仪器用户能够完成任务，系统能够检测到发生的任何偏差。与非VI用户测试结果一样，VI的实验测试结果表明，在所有情况下，系统都能正确检测到所有用户与计划路径的任何偏差，这意味着偏差检测的准确性为100%。5.5.2. 效率至于效率，记录完成任务2的时间使用女性的平均步长，大约等于66厘米（Thompson，2002年）。表8显示了每个参与者成功完成任务的步行速度 根据（Guerrero等人， 2012），没有导航支持的盲人的行走速度为0.4m/s。因此，在我们的实验中，VI参与者走得比他们应该做的要慢，可能是因为他们遵循了导航器给出的指示如表8所示，总体平均步行速度是没有任何障碍的盲人的平均步行速度的导航支持。可以注意到，第一个VI参与者能够达到通常步行速度的90%，要知道她之前参与测试了一个使用谷歌Project Tango检测障碍物的导航系统（Jafri et al. 2017年）。5.5.3. 用户满意度最后，VI参与者被要求填写系统的可用性量表表格，以评估用户的满意度。图8示出了VI用户的满意度结果，作为每个测试组的满分100分。最低分是80%，这被认为是好的，高于平均水平，根据（Zaman，2015），得分高于68%被认为高于平均水平。第二组的最低分有所改善，达到87.5%。这些结果表明，虚拟仪器用户满意并愿意使用该系统。6. 讨论和局限性总之，这项研究工作的贡献有三个方面：1. 一种ACO路径规划算法，可以找到一个优化的路线，考虑到VI用户的喜好，并避免与障碍物的人的因素，如VI用户的特殊需求已被纳入算法的每一步，以及在目标函数。2. 建议的路径规划器集成了一个路径跟踪模块，使用第一次适合技术，检测任何偏离规划的路径，并提醒VI用户，安全地