购物体验中的无障碍路径规划算法

沙特国王大学学报一种新的视障者Durgesh Nandini，K.R.塞哈Indira Gandhi Delhi Technical University for Women，Kashmere Gate，Delhi 110006，India阿提奇莱因福奥文章历史记录：2016年12月4日收到2017年3月14日修订2017年3月23日接受2017年3月25日在线发布保留字：最短路径算法无障碍路径A B S T R A C T视力受损的人需要不断的帮助来从一个位置导航到另一个位置。在超市实现自主购物体验对他们来说是一个真正的挑战本文提出了一种贪婪路径规划算法，为视障者在超市走廊中提供无障碍最优路径。所提出的路径规划算法的新颖性在于转弯的数量随着距离的最小化，因为视觉受损的人更喜欢通过没有任何转弯的直线路径移动。所提出的算法可以被纳入任何现有的购物辅助系统在市场上提供的障碍物检测设施在it.The算法还重新路由的情况下，在路径中检测到的障碍物的用户©2017作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍导航是每个人的基本需求。当人们从一个地方到另一个地方时，人们有自己明确的选择路径的标准。对于学生或例如，上班族上学或上班快迟到时，最重要的可能是最短的路;喜欢健身或注重健康的人可能会选择较长的路;长者可能会选择光线充足、障碍较少的路等;但视障人士在由一处前往另一处时，却没有自主选择的权利。他们通常试图记住他们所访问的每个环境的路线，这除了是一项乏味的任务之外，在建筑物的架构改变、在建道路或存在动态或静态障碍物的情况下也可能成为问题，这些障碍物可能与他先前的经历不同。视力受损的人甚至不能尝试一条新的路线，因为他们缺乏对周围环境的信息，并且容易受到各种风险的影响。同样，他们也需要不断的帮助，通过超市导航和选择他们想要的产品。沙特国王大学负责同行审查制作和主办：Elsevier*通讯作者。电子邮件地址：Durgeshn4@gmail.com（D.Nandini）、krseeja@gmail.com、seeja@igdtuw.ac.in（K.R. Seeja）。障碍物检测成为一个关键点，而处理与视觉障碍的人。在超市场景中，视障人士可能会遇到各种类型的障碍物。它可能是静态障碍物，如入口或出口门，货架等。或动态障碍物，如湿地板、手推车、人等。在现有系统的帮助下，他们也许可以在最短的路径上移动到他们选择的超市区域。一些可用的辅助系统甚至包括，考虑在引导路径中存在障碍物的可能性，并在建议路径中检测到障碍物时发出蜂鸣器。但主要问题当前可用的系统的缺点是，一旦在建议路径中检测到障碍物，它们就不能将用户从其当前位置重新路由到其期望目的地。2. 文献综述为视障人士开发导航系统已经做了大量的工作，这样他们就可以独立地在超市购物，没有任何帮助。但现有系统的主要局限性是它们不能作为一个整体工作。现有的系统利用各种技术，如超声波传感器、全球定位系统（GPS）、条形码和射频识别（RFID）（Joseph等人，2014;Kanwal等人，2015年），以引导盲人用户在超市中从一个位置到另一个位置。许多可穿戴产品和引导棒（Saraf等人，2014;Gurubaran等人，2014）也是这一领域研究的成果。这些研究的目标大多是提供硬件解决方案。在文献中没有太多的工作在开发路由算法，特别是为视障人士。现有的导航系统使用知情或http://dx.doi.org/10.1016/j.jksuci.2017.03.0051319-1578/©2017作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com386D. Nandini，K.R.Seeja/ Journal of King Saud University⁄1MW用于路由的无信息路径查找算法所有这些算法的目标是减少从一个位置到另一个位置的成本或距离。在一项研究（Golledge，1995）中，对普通人的路径或路线选择标准进行了研究，对从一条路径移动到另一条路径时选择路线的不同标准进行了排名最高的标准是最短的距离，最少的时间和最少的转弯。在机器人运动的背景下也已经研究了路径规划（Minguez等人，2005; Yared 等 人 ，2007; Khatib ， 1986; Barraquand 等 人 ，1996），其中机器人研究环境并绘制到达其目的地的路径，同时避开环境中任何可能的障碍物。基于网格的路径规划是实现机器人自由布线的最常用技术之一。使用元启发式技术如遗传算法的网格中的路径规划（Alajilan等人， 2013）、和声搜索（Yang，2009）和四元和声搜索（Koceski等人，2014年）也提出了。所有这些算法的目的是提供一个无障碍路径的机器人，同时减少算法的计算时间。然而，在机器人运动中，机器人的形状和运动角度是规划无碰撞路径的主要约束条件，这对于视力受损的人来说并非如此基本的深度优先搜索（DFS）和广度优先搜索（BFS）在搜索时间、存储器需求以及路径成本方面不是有效的。本文提出了一种深度优先的迭代深化算法（IDDFS）（Korf，1985a，b），用于国际象棋程序的最优搜索。它结合了DFS的空间效率和BFS的然而，底层图的大小是有限的。Dijkstra在该算法中，使用距离准则来找到从一个位置到另一个位置的最短路径称为边界迭代深化深度优先搜索（BIDDFS）的算法（Lim等人，2015），以减少Dijkstra算法的内存需求和IDDFS算法的局限性。 作者结合双向搜索和并行实现，提出了两种BIDDFS方案. Hart等人， 196 8）算法是所有信息搜索技术的标准。 ID A/（Korf，1985 a，b）是A/的一个有效率的变体，如果搜索图中有圈，它可能会被捕获。后来的条纹算法（Björnsson等人，200 5）已被提出，以消除这一缺陷的ID A/。 深度方向A/算法（Khantana poka等人， 200 9）使用图论概念以及A/算法已经被提出用于在2D和3D游戏中为动画角色的移动寻找最短路径。AParallelNewBidirecti onalA/algorithm（Rios et al.， 2011年），提出了利用双向搜索和并行实现。在最近的一项研究中（Lim等人，2016年），作者提出了一个优化的BIDDFS通过减少内存读取和写入周期。提出了一种新的路径规划算法为视障人士提供无障碍、最短和最少转弯的路径。3. 材料和方法该算法的目的是引导视障人士通过超市的各个通道，从他们的当前位置到他们选择的目的地，使他们能够进行援助免费和独立的超市购物。该算法假设一个单层超市的布局，货架在路径的两侧，所提出的算法计算从用户的当前位置的最佳路径选择的目的地。如果在通过建议路径的导航期间识别到障碍物，则算法通过新的最佳路径将用户重新路由到他的目的地。路径查找算法的输入由对应于超市布局、用户的当前位置、用户选择的目的地和障碍物列表的图形组成。最后输出从用户当前位置到超市中所选目的地的无障碍最优路径3.1. 图构建为了实现所提出的算法的超级市场，它需要得到超市的设计布局，并将其转换为相应的无向加权图。超级市场图的构造遵循以下规则：a) 超市中的每个部分都由一个节点表示b) 根据两个节点之间的距离，c) 单个节点用于表示路径相对两侧的部分。3.2. 拟议方法拟议方法中的各个步骤是1. 获取超市设计布局。2. 将超市布局转换为无向加权图。3. 通过将权重矩阵（W）除以所有边权重的最大值来归一化权重矩阵（W），使得所有权重值在范围[0，1]内。4. 为每个回合分配0.5的权重，因为0.5是范围[0，1]的中位数。5. 最佳距离=行驶距离+转弯0.5.6. 调用OPTIPATH（），这是一个贪婪算法，用于找到从源到目的地的最佳路径。7. 穿过路径，检查障碍物。8. 如果找到Obstacle，则从图中删除相应的边，并以当前节点作为新源调用OPTIPATH（）。9. 继续前进，直到到达目的地。描述所提出的方法的流程图如图所示。1.一、3.3. 拟议汇总表该算法使用四个不同的矩阵这些矩阵定义如下：3.3.1. 权重矩阵设W是对应于图的权重矩阵，其中W½i;j] /4从节点i到节点j的距离1;如果i;j不是图中的边，或者i j3.3.2. 归一化权矩阵在建议的重量比较公式中，Dijkstra公式为此，通过将权重矩阵中的所有权重值除以最大权重值来归一化权重矩阵，使得所有权重值在范围[0，1]内令NW为归一化权重矩阵，并定义为：NW ½i;j] <$W½i;j]D. Nandini，K.R.Seeja/ Journal of King Saud University3871Fig. 1. 流程图。其中mw是W中的权重值之外3.3.3. 转弯矩阵定义了一个称为转弯矩阵的矩阵来合并分配给转弯的权重。每个回合都被赋予一个权重，0.5是权重范围[0，1]的中位数设T为转弯矩阵，定义为《古兰经》0：5;如果路上有个转弯的话！ X！其中x是单个中间节点：0;否则3.3.4. 障碍矩阵定义了一个称为障碍物矩阵的矩阵来记录路径中障碍物的存在。障碍物检测技术可以在相应路径中检测到障碍物时在障碍物矩阵中设置相应的条目。设O为障碍物矩阵，定义为：O ½i;j] ¼1;如果路径i中存在障碍物，J0;否则3.4. 重量比较公式用户当前位置到其期望目的地之间的最短距离路线可以使用Dijkstra算法来计算。但视障人士的最佳路线不仅是从源到目的地的最短距离路线，但也是转弯最少的路线。因此，本研究提出一个新的权重比较公式，其中包含最小距离和最小转弯准则。设d[v]为顶点v到源s的最佳距离（通过添加路径中边和转弯的权重）。建议的权重比较公式如下，3.5. 伪代码算法OPTIPATH（）返回从源到目的地的最佳路径。它使用以下数组●visited ½i] ¼1;如果找到了从s到i的最佳路径0;否则● d[i]表示从“s”到“i”的最佳距离● parent[i]表示最优路径中节点“i”的父节点388D. Nandini，K.R.Seeja/ Journal of King Saud University图二. 超市布局。图三. 等价图3.6. 最坏情况复杂度设“n”为图中的顶点数。最坏的情况下，OPTIPATH（）的运行时间是O（n2）。的外部while循环ObstacleFreeOptiPath（）迭代最多'n'次，如果图是完全连接的，这在超市场景中是罕见的情况。因此ObstacleFreeOptiPath（）的总复杂度是O（n3）。D. Nandini，K.R.Seeja/ Journal of King Saud University3894. 实验该算法已在C++中实现。通过取图1所示的超市样品进行了各种实验。 二、 等效图如图11所示。3.第三章。OPTIPATH（）旨在为视障用户规划最安全、最短和最小转弯路径，并在用户被困在超市的任何区域假设一位视障顾客X进入超级市场，并希望从超市的乳制品区购买一些牛奶和面包。然后，用户“X”提供目的地作为输入，即乳制品区，其是 所 提 出 的 算 法 的输 入 之 一 。 另 一 个 输 入 是 用 户 所 提出 的 算 法OPTIPATH（）为用户找到OPTIPATH（）还将用户从表1从源节点0到目的节点51的可能路由。如果在建议路径中检测到障碍物，则将其当前位置移动到其选择的目的地（参见图4）。考虑图3所示的图表。假设节点0是用户的当前位置，并且他希望转到节点51。到达目的地的方法不止一种，如表1所示。所提出的算法必须从几个可能的路径中选择最优路径。该算法中选择最优路径的第一个准则是源点和目的点之间的最小转弯数。与此同时，也注意尽量缩短距离。在该示例中，所提出的算法选择从节点0-1-2-3-4-5-17-15-14-13-42-43- 51开始的路径作为视觉障碍者的最佳可能路线因为它只包括一个转折点，并且与目的地节点可用的其他可能路线相比，在距离方面没有太大差异最初，假设在到目的地的路径中没有障碍物来建议路线，因为用户不知道任何障碍物。在路由识别之后，通过检查遍历所识别的路径的障 碍 。 如 果 在 路 径 中 识 别 出 障 碍 物 ， 则 删 除 相 应 的 边 ， 并 调 用OPTIPATH（）计算从用户的当前位置开始的新路线（假设当前位置作为开始节点）到目的地以重新路由用户。考虑一个如图4所示的带有障碍物的图。这里，在最佳路径从0到51，当用户到达节点17时。现在删除见图4。 试验结果路线距离匝0-1-27-26-28-29-24-23-40-98-41-43-5111950-1-2-3-4-5-17-15-14-13-42-43-5112910-1-2-3-20-21-22-23-40-38-41-43-5112930-1-27-26-28-29-32-33-39-38-41-43-511203390D. Nandini，K.R.Seeja/ Journal of King Saud University⁄表2性能比较无障碍。S. 无来源/目的地路线建议距离转弯次数DijkstraOptipathDijkstraOptipathDijkstraOptipath1 0140-1-27-26-25-21-18-15-140-1-2-3-4-5-17-15-147178312 0210-1-27-26-25-210-1-2-3-20-214953213 0120-1-27-26-25-21-18-15-14-13-120-1-2-3-4-5-17-15-14-13-1295102424 0510-1-27-26-28-29-24-23-40-38-41-43-510-1-2-3-4-5-17-15-14-13-42-43-51119129515 0370-1-27-26-28-29-24-23-40-38-370-1-2-3-20-21-22-23-40-38-37101111316 442644-43-41-38-40-23-24-29-28-2644-43-41-38-39-33-32-29-28-266970317 39439-38-40-23-22-21-18-15-17-5-439-38-41-43-42-13-14-15-17-5-48996428 204920-21-18-15-16-9-10-11-45-46-47-48-4920-21-22-23-40-38-37-36-52-50-49100102319 3493-20-21-18-15-16-9-10-11-45-46-47-48-493-20-21-22-23-40-38-37-36-52-50-491101123110 4534-5-17-15-18-21-22-23-40-38-37-36-534-3-2-1-27-26-28-29-32-33-34-35-5310611142表3与障碍物的性能比较。S.No.源目的地障碍OPTIPATH（）在检测障碍物检测后建议的路径（重新路由）101415-140-1-2-3-4-5-17-15-检测到障碍物15-18-21-22-23-19-13-1426488-96-7-8-检测到8-7-6-5-17-15-14-13-42-43-51-50-49-48301215-140-1-2-3-4-5-17-15-检测到障碍物15-16-9-10-11-12404645-460-1-2-3-4-5-6-7-8-9-10-11-45-障碍物检测45-11-12-13-42-43-44-46503723-400-1-2-3-20-21-22-23-检测到障碍物23-24-29-32-33-34-35-53-36-37603332-330-1-27-26-28-29-32-检测到32-29-24-23-40-38-39-337183121-2518-21-检测到21-22-23-24-29-30-318185240-3818-21-22-23-40-检测到40-23-24-29-32-33-34-35-53-36-529183425-2618-21-25-检测到25-21-22-23-40-38-39-33-341018479-1018-15-16-9-检测到9-16-15-14-13-42-43-44-46-4711481716-1548-47-46-45-11-10-9-16-检测到16-9-8-7-6-5-1712442628-2644-43-41-38-39-33-32-29-28-检测到障碍物28-29-24-23-22-21-25-261393846-449-10-11-45-46-检测到46-47-48-49-50-52-36-37-381455042-435-17-15-14-13-42-检测到42-13-12-11-45-46-47-48-49-501563415-176-5-17-检测到17-5-4-3-2-1-27-26-28-29-32-33-3416204920-2120-检测到20-3-4-5-17-15-14-13-42-43-51-50-491734920-213-20-检测到20-3-4-5-17-15-14-13-42-43-51-50-491841417-154-5-17-检测到17-5-4-3-20-21-18-15-14边（17，15），并再次调用OPTIPATH（）以找到从节点17到节点51的新路径。因此，所提出的算法通过新路径17-5-4-3-20-21-22-23-40-38-41-43-51重新路由用户5. 结果和讨论在有障碍物和无障碍物的图上对不同的源节点和目的节点5.1. 实验1在该实验中，考虑如图3OPTIPATH（）计算的路径与Dijkstra（）计算的路径一致，结果如表2所示。结果表明，该算法所提供的路径的转弯数小于或等于Dijkstra算法的转弯数5.2. 实验2在该实验中，考虑了如图4所示的在不同顶点之间放置障碍物的图所提出的算法在检测到障碍物时重新路由人，因此由所提出的算法返回的路径没有任何障碍物，如表3所示。同时，该算法还使成本和匝数最小化。6. 结论提出了一种新的视障者路径规划算法所提出的算法可以并入现有的导航辅助设备，如视障人士使用的电子白色该算法的主要特征是转弯次数的最小化，这是视障人士的偏好之一，以及在超市导航时需要行驶的距离。该算法可以与任何障碍物检测技术（如超声波传感器）一起使用，以在障碍物的情况下通过最佳路径重新路由用户该算法的性能进行了比较，Dijkstra的最短路径算法，它被发现，该算法找到了一个更好的路径，根据视障人士，通过减少转弯的路径和重路由的情况下，障碍物的引用Alajilan ， Maram ， Anis Koubaa ， Imen Chaari ， Hachemi Bennaceur ， AdelAmmar，2013.基于遗传算法的大规模网格环境中移动机器人全局路径规划。在机器人的个人和集体行为（ICBR），2013年国际会议上，pp。1-8. 美国电气与电子工程师协会。Barraquand ， Jérôme ， Kavraki ， Lydia ， Motwani ， Rajeev ， Latombe ， Jean-Claude，Li，Tsai-Yen，Raghavan，Prabhakar，1996年。路径规划的随机抽样方案。在：机器人研究.Springer，London，pp. 249-264。Björnsson，Yngvi，Enzenberger ，Markus，Holte，Robert C. ，Schaeffer，Jonathan ，2005.边缘搜索：在游戏地图上寻找路径时击败A。 CIG 5，125-132.Dijkstra，Edsger W.，一九五九年关于图中两个问题的注记数字。Math.1（1），269-271.D. Nandini，K.R.Seeja/ Journal of King Saud University391⁄⁄Golledge，Reginald G.，1995.人类导航中的路径选择和路线偏好：进展报告。在：在空间信息理论国际会议。施普林格，柏林海德堡，pp. 207- 222Gurubaran，Gowrishankar Kasilingam，Mritha Ramalingam，2014.视障者语音辅助电子棒Hart，Peter E.，Nilsson，Nils J.，拉斐尔，伯特伦，1968年。启发式确定最小费用路径的形式基础。IEEE Trans. Syst. Sci.赛博恩 4（2），100-107.约瑟夫，理查德F.，Godbole，Anand A.，2014.一种视障行人智能旅伴。在电路，系统，通信和信息技术应用（CSCITA），2014年国际会议上，pp。283-288. 美国电气与电子工程师协会。Kanwal，Nadia，Bostanci，Erkan，Currie，Keith，Clark，Adrian F.，2015.视觉障碍者导航系统：视觉与深度传感器的融合。Appl. Bionics Biomech。 2015年。Khantanapoka，Khammapun，Krisana Chinnasarn，2009.具有深度方向的2D 3D游戏实时寻路算法。自然语言处理，2009年。SNLP'09。第八届国际研讨会。美国电气与电子工程师协会。Khatib，Oussama，1986年。机械手和移动机器人的实时避障。自主机器人车辆。施普林格，纽约，pp.396- 404Koceski，Saso，Panov，Stojanche，Koceska，Natasa，Zobel，Pierluigi Beomonte，Durante，Francesco，2014.一种新的基于网格的四次和声搜索路径搜索算法。Int. J.Adv. 机器人系统 11（9），144.Korf，Richard E.，1985年a。深度优先迭代深化：最优容许树搜索。第内特尔27（1），97-109。Korf，Richard E.，1985年b。迭代-深化-A：最优容许树搜索。见：第9届人工智能国际联合会议论文集，第2卷。摩根·考夫曼出版公司，pp. 1034- 1036Lim，Kai Li，Seng，Kah Phooi，Yeong，Lee Seng，Ang，Li-Minn，Ch'ng，SueInn，2015. 不知情寻路：一种新方法。专家系统应用42（5），2722-2730。Lim，KaiLi，Seng，Kah Phooi，Yeong，Lee Seng，Ang，Li-Minn，Ch'ng，Sue Inn，2016.为视障人士提供导航。Int. J. Comput.复杂.内特尔阿尔戈1（1），99-114。Minguez，Javier，Montano，Luis，2005.未知、动态和复杂场景下基于传感器的机器人运动生成。机器人奥顿系统 52（4），290- 311。Rios，Luis Henrique Oliveira，Luiz Chaimowicz，2011.PNBA：一种并行双向启发式搜索算法。In：Proceedings of the XXXI Congressa da Sociedade Brasileirade Computaçao.Saraf，Mohit，Shehzad，Mohd，Jadhav，Neeraj，2014.一种基于IVR的盲人智能导盲棒。Int. J. Curr. Eng. 技术人员：一七一九至一七二三年Yang，Xin-She，2009. 和声搜索作为一种元启发式算法。音乐启发和声搜索算法。施普林格，柏林海德堡，pp. 1-14号。Yared ， Rami ， Xavier Défago ， 2007 年 。 Julien Iguchi-Cartigny 和 MatthiasWiesmann。动态群异步协作移动机器人碰撞预防平台。