第３Ｏ卷第２期 计算机仿真 ２０１３年２月 文章编号：１００６—９３４８（２０１３）０２—０２８２—０４ 基于双目视觉的移动机器人避障算法仿真研究 何赕，张翼飞 （河南城建学院，河南平顶山４６７０３６） 摘要：针对当前超声波定位的机器人避障技术中，只能感知外围的单一信息，在多机器人通信或者外围存在信号串扰的前提 下，信息转化测距结果存在较大误差，存在避障盲区的问题，提出一种视觉多图像信息融合的机器人避障算法，通过双目立 体视觉采集机器人的实际图像信息，运用像素自适应融合方法最大程度的采集视觉信息，归一化后的视觉信息带人Ａ 算 法进行最优路径的选择，克服单一信息选择中路径计算的弊端，建立多信息约束的路径搜索模型，最大化的解决视觉避障中 的干扰问题。后期的计算机仿真结果表明，与传统的测距避障算法相比，有效提高了算法的抗噪性能和避障准确性，为移动 机器人避障优化提供了依据。 关键词：超声波定位；机器人避障；视觉信息 中图分类号：ＴＰ３９８．９ 文献标识码：Ｂ Ｂａｓｅｄ ｏｎ Ｂｉｎｏｃｕｌａｒ Ｖｉｓｉｏｎ ｏｆ Ｍｏｂｉｌｅ Ｒｏｂｏｔ Ｏｂｓｔａｃｌｅ Ａｖｏｉｄａｎｃｅ Ａｌｇｏｒｉｔｈｍ Ｓｉｍｕｌａｔｉｏｎ ＨＥ Ｙｉ．ＺＨＡＮＧ Ｙｉ—ｆｅｉ （Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｕｒｂａｎ Ｃｏｎｓｔｒｕｃｔｉｏｎ，Ｐｉｎｇｄｉｎｇｓｈａｎ Ｈｅｎａｎ ４６７０３６，Ｃｈｉｎａ） ＡＢＳＴＲＡＣＴ：Ｉｎ ｖｉｅｗ ｏｆ ｔｈｅ ｃｕｒｒｅｎｔ ｂａｓｅｄ ｏｎ ｕｌｔｒａｓｏｎｉｃ ｐｏｓｉｔｉｏｎｉｎｇ ｏｆ ｔｈｅ ｒｏｂｏｔ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｍｅｔｈｏｄ，ｃａｎ ｏｎｌｙ ｐｅｒｃｅｐｔｉｏｎ ｐｅｒｉｐｈｅｒａｌ ｓｉｎｇｌｅ ｉｎｆｏｒｍａｔｉｏｎ，ｉｎ ｍｕｈｉ—ｒｏｂｏｔ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｏｒ ｐｅｒｉｐｈｅｒａｌ ｅｘｉｓｔｉｎｇ ｓｉｇｎａｌ ｅｒｏｓｓｔｌａｋ，ｕｎｄｅｒ ｔｈｅ ｐｒｅｃｏｎｄｉｔｉｏｎ ｏｆ ｉｆｎｏｒｍａｔｉｏｎ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｒａｎｇｉｎｇ ｒｅｓｕｌｔｓ ｔｈｅｒｅ ｉｓ Ａ ｂｉｇ ｅｌｉ＇ｏｒ，ｔｈｅｒｅ ｅｘｉｓｔｓ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｂｌｉｎｄ ａｒｅａ ｏｆ ｔｈｅ ｐｒｏｂｌｅｍｓ，ｔｈｅ ａｒｔｉｃｌｅ ｐｒｏｐｏｓｅｓ Ａ ｋｉｎｄ ｏｆ ｍｕｌｉｔｐｌｅ ｉｍａｇｅ ｂａｓｅｄ ｏｎ ｖｉｓｕａｌ ｉｎｆｏｒｍａｔｉｏｎ ｆｕｓｉｏｎ ｒｏｂｏｔ ｏｂ－ ｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ａｌｇｏｒｉｔｈｍ，ｔｈｒｏｕｇｈ ｔｈｅ ｂｉｎｏｃｕｌａｒ ｓｔｅｒｅｏ ｖｉｓｉｏｎ ａｃｑｕｉｓｉｔｉｏｎ ｒｏｂｏｔ ａｃｔｕａｌ ｉｍａｇｅ ｉｎｆｏｒｍａｔｉｏｎ，ｔｈｅ ｕｓｅ ｏｆ ｐｉｘｅｌ ａｄａｐｔｉｖｅ ｆｕｓｉｏｎ ｍｅｔｈｏｄ ｍａｘｉｍｕｍ ａｃｑｕｉｓｉｔｉｏｎ ｖｉｓｕａｌ ｉｆｎｏｒｍａｔｉｏｎ，ｎｏｒｍａｌｉｚａｔｉｏｎ ｏｆ ｖｉｓｕａｌ ｉｎｆｏｒｍａｔｉｏｎ ｉｎｔｏ ｔｈｅ Ａ 水ａｌｇｏｒｉｔｈｍ ｉｓ ｏｐｔｉｍａｌ ｐａｔｈ ｃｈｏｉｃｅ。ｏｖｅｒｃｏｍｅ Ａ ｓｉｎｇｌｅ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ｔｈｅ ｃｈｏｉｃｅ ｏｆ ｈｔｅ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｐａｔｈ ｉｓ ｃａｌ－ ｃｕｌａｔｅｄ ａｎｄ ｅｓｔａｂｌｉｓｈ ｔｈｅ ｍｕｌｔｉｐｌｅ ｉｎｆｏｒｍａｔｉｏｎ ｃｏｎｓｔｒａｉｎｔ ｐａｔｈ ｓｅａｒｃｈ ｍｏｄｅｌ，ｔｏ ｓｏｌｖｅ ｔｈｅ ｍａｘｉｍｕｍ ｖｉｓｕａｌ ｏｂｓｔａｃｌｅ ａ． ｖｏｉｄａｎｃｅ ｏｆ ｉｎｔｅｒｆｅｒｅｎｃｅ ｐｒｏｂｌｅｍ．Ｌａｔｅｒ ｔｈｅ ｃｏｍｐｕｔｅｒ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔｓ ｔｏ ｐｒｏｖｅ ａｎｄ ｔｒａｄｉｔｉｏｎａｌ ｒａｎｇｉｎｇ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｍｐｒｏｖｅ ｔｈｅ ａｎｔｉｎｏｉｓｅ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ａｃｃｕｒａｃｙ，ｉｍｐｒｏｖｅｍｅｎｔ ｅｆｆｅｃｔ ｉｓ ｏｂｖｉｏｕｓ．． ＫＥＹＷＯＲＤＳ：Ｕｌｒｔｓａｏｎｉｃ ｐｏｓｉｔｉｏｎｉｎｇ；Ｒｏｂｏｔ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ；Ｖｉｓｕａｌ ｉｎｆｏｒｍａｔｉｏｎ 器人的实际运行环境具有复杂性、多样性和随机性的特征， １ 引言 机器人需要具备较高的环境辨识、路径规划和躲避障碍的能 随着科学技术和社会经济的发展，学者研究出了大量的 力…，才能准确完成预期任务。因此，对移动机器人路径中 机器人替代人类完成繁琐和危险的工作，不仅确保了人们的 的避障研究是学者分析的重点问题。机器人避障就是机器 安全，而且提高了工作效率促进经济的发展。移动机器人是 人在从出发点到目标点时，利用控制方法准确避开相关障碍 一个集环境感知、动态规划、行为控制等功能为一体，具有定 的过程。自主避障技术是评价移动机器人智能化程度的重 位导航和自主避障功能的综合控制系统。其广泛应用于工 要指标。在动态复杂的环境中，智能机器人能够依据系统预 业、医疗、军事、空间拓展等领域，具有重要的使用价值。机 设的任务以及规划路径，再结合自身传感器感知的周围环境 的信息，寻找最优路径，避免发展碰撞。超声测距和超声传 收稿日期：２０１２—１１—０３ 感器技术的环境适应性和抵御干扰性都较强，为智能机器人 －－－——２８２－－－—— 避障系统提供了重要的技术基础 “ 。随着人工智能技术 ２．２盲区和信息串扰影响 的发展，产生了大量的基于智能优化系统的机器人避障 方法。 超声波传感器在探测障碍物时存在一定的盲区，产生盲 区的原因较多，如最初硬件设计时只规定了一个单元的延迟 机器人避障规划中的超声波定位技术使用现代人工智 时间，当接收到大于预定阀值的信号时会引起测量时间出现 误差盲区。机器人感应系统中的多种传感器能采集大量的 信息，但过多的信息会产生噪声干扰 Ｊ－，出现多传感器信 号串扰问题。信号串扰会导致当前传感器的发送信号被其 它传感器接收，影响信号的准确传递。 能算法，具有超强的并行计算能力，定位搜索时不会依赖与 严格的数学模型与梯度信息，所以在机器人路径规划与避障 中广泛被采用，但是当前的基于超声波定位的机器人避障方 法中，只能感知外围的单一信息，在多机器人通信或者外围 存在信号串扰的前提下，信息转化测距结果存在较大误差， 存在避障盲区的问题。另外，在一些环境复杂的凹形区域， 机器人的路径常常会遇到需要迂回的步骤，这种情况下传统 的方法中机器人无法有效迂回避障，造成避障失败。 本文提出一种基于视觉多图像信息融合的机器人避障 算法，通过双目立体视觉采集机器人的实际图像信息，运用 像素自适应融合方法最大程度的采集视觉信息 Ｊ，归一化 后的视觉信息带入Ａ 算法进行最优路径的选择，克服单一 信息选择中路径计算的弊端，建立多信息约束的路径搜索模 型，最大化的解决视觉避障中的干扰问题。 ２机器人避障原理 ２．１超声波机器人避障表达式 当前智能机器人路径分析常用的技术是基于超声波传 感器信息探测的机器人避障技术。超声波传感器的优点是： 抗干扰能力强；体积小、使用便捷；实用性强。智能机器人的 超声波传感器安放在机器人的感应系统中，如图１所示。 波传感器 图１机器人超声波传感器的安放 使用超声波传感器进行避障和路径规划时使用渡越时 间法可测量传播距离。超声波发生器运行时开始计时，传播 时遇到障碍物会发生反射形成回波传递到接收端，停止运行 并记录时间。最终超声波传感器依据记录的时间以及路径， 运算出障碍物的距离，确保及时避障，相应的运算公式，如式 （１）所示。 Ｚ＝ｖｔ／２ （１） 其中， ，ｔ分别表示超声波的传播速度和时间，通常设置超声 波的传播速度为３５５（ｍ／ｓ）。传感器与反射点间的距离是： ｚｚ： 辩√ 一（寺） ∞ （２） 图２信号串扰发生示意图 本文设计的机器人各个模块能够消除盲区和信号串扰 问题。 ３机器人避障算法 ３．１视觉避障中的障碍特征提取 本文设置机器人视觉边界为直线模型，通过Ｈｏｕｇｈ变换 方法提取障碍特征。使用角度约束关系 和消失点判断两 种方法提高提取障碍特征的有效率。 １）构建角度约束关系 Ｈｏｕｇｈ变换方法依据障碍物特征分布的范围进行检测。 该方法在查询特征范围内的最大值时，要求特征的邻近边界 满足式（３）的角度约束关系： ｆＬ ￣＇Ｌ胁ｍｉｉ．＜ ＜ １ ｎ＜ ｍ￡＜ 胁 。 （３） 其中 枷，Ｏ＇￣ｇｈ 分别表示特征左右边界的角度，使用式（３）能 够剔除无效特征。 ２）障碍区边界特征提取 通过消失点分析ｈｏｕｇｈ检测的结果，可以避免Ｈｏｕｇｈ变 换的检测结果出现“虚峰”以及“漏检”现象。消失点是指检 测出来的障碍特征左右边界的交点。 边界提取方法的主要过程是： １）使用包含角度约束的ｈｏｕｇｈ变换在图像左右边界范 围内，获取Ｐ组可能边界线； ２）获取Ｐ×Ｐ个左右边界线的交点，即消失点的坐标； ３）通过消失点的位置信息分析交点位置，最终得到符 合消失点约束的障碍边界线，减少虚峰和漏检现象的发生。 原理用图３描述。 ３．２ Ａ 算法中最优路径的求解 对上述获取的障碍特征进行约束条件的变换，融入Ａ术． 算法获取最优路径。Ａ 算法基于Ｄｉｊｋｓｔｒａ算法的基础上融 入了估计函数，通过估计值的大小选择局部最优的节点作为 ．．．——２８３，．．—— 机器人 图３机器人避障的视窗分割图 最优路径预备节点，能够简化预备节点集，提高算法效率。Ａ 算法的估计函数为： ｆ（ｐ）＝ｇ（ｐ）＋ｈ（ｐ） （４） 其中，ｇ（Ｐ）表示原始点到当前点Ｐ的消耗代价；ｈ（Ｐ）表示预 备节点到期望节点的估计代价；Ａ 算法选择极大或极小节 点作为最优路径的下级节点。ｈ（Ｐ）表示觉悟函数，设计合理 的觉悟函数能够提高算法的性能。 Ａ 算法的运算过程为： １）构建ＯＰＥＮ和ＣＬＯＳＥＤ表，其中ＯＰＥＮ表保存未估价 的节点，ＣＬＯＳＥＤ表保存完成估价的节点。 ２）基于广度优先搜索理论，设置起点为初始路径节点， 并保存于ＯＰＥＮ表中。 ３）将ＯＰＥＮ表中的首节点，保存在ＣＬＯＳＥＤ表中，并运 算该节点的估计值，并在状态区域内查询与该节点有关的全 部节点作为预备节点，保存于ＯＰＥＮ表中，同时将表中节点 按估价值的升序进行排列。 ４）重复进行步骤３，直至获取预期节点。 ３．３ 多机器人的视觉碰撞问题 机器人视觉蔽障算法通过主对协调调控机制，控制机器 人运行路径，避免发生碰撞。如果机器人位于干扰范围内 时，多个机器人同时运行时容易出现碰撞，因此对碰撞的准 确检测是机器人主对协调控制的重要问题。需要考虑如何 减少机器人与障碍物发生碰撞的概率，提高机器人的控制 率。分析两个物体之间的距离，可以判断两个物体是否发生 碰撞。三维空间中，任意两点的Ｅｕｃｌｉｄｅａｎ长度可由式（５） 描述： 『 ｉ２＋ＷＩｆ＝，／（ｗ２ｙ＋ ） 一（ｗ２ｘ ） 一（ｗ２ｚ＋ ） （５） 将任意两条线段Ｅ和Ｆ的邻居点带入式（６）可得两条 线段之间的距离： ｗ（Ｆ 、Ｅ ）＝ｍｉｎ｛ ），１ｌ：ｙ∈Ｅｏ， ∈Ｆ ） （６） 依据主体中心线距离可以分析是否存在碰撞现象。式 （６）只研究了简单的几何物体，当Ｅ、Ｆ都由多个物体组成， 通过计算各物体间的距离，可以获取Ｅ和Ｆ间的距离。如果 已知Ｅ、Ｆ的中心线间的距离，则以Ｗ为半径的范围物体可 ．．．——２８４．．．—— 以表示成： Ｇ ＝｛ ：ｌＩｙ。＋ ｌＩ≥Ｗ ， ∈ ）， ≤０，ｐ＝Ｅ、Ｆ（７） 则两个主体面间的距离为： Ｇ ，ＧＦ）＝，（ ， ）＋Ｗ ＋ ， （８） 如果两个主体中心线距离比半径总和大，说明未发生碰 撞；否则，发生碰撞。如果划分的路线存在碰撞范围，则机器 人会发生碰撞。如果存在碰撞区域，通过协调系统进行控 制，方法是：１．再次规划路径，直至机器人运行安全；２．机器 人先按自身规划路径运行，再依据其它设计路径运行。或者 机器人先依据其它规划路径运行，再依据自身规划路径运 行。举例两个机器人间的运行轨迹图如图４所示。 ●机器人１ ●机器人２ 图４机器人视觉蔽障轨迹分析 分析图４可得，两机器人的规划路径存在碰撞区域。此 时，通常规划与原路径相反的路线，使机器人依据新路径再 次运行一遍。虽然图中机器人的运行路径存在碰撞区域，但 两个机器人不一定会发生碰撞。原因是不同的机器人具有 自身特有的运行路径和速度，当一个机器人超过碰撞区域， 另一个机器人可能还未到达碰撞区域，此时两个机器人不会 碰撞。使用优化方法可分析不同的机器人是否发生碰撞。 若已知两机器人的运行路径，当两个机器人同时运行时，可 得如下结果： １）如果两条路径不存在碰撞区域，说明两个机器人可各 自运行，互不干扰； ２）如果两个机器人的运行路径存在碰撞区域，且有 Ｓ（ＧＰ）／ｔｌ— （ＰＪ ）／￡１≥ｚ（Ｇ Ｐ ）／ｔ２ｋ 或 ｚ（Ｇ Ｐ ）／ｔ２一 （Ｐ Ｊ Ｖ ）Ｉｔ２≥ （ＧＰ）／ｔ１ 则两个机器人可各自运行，互不干扰；否则，将会出现碰撞现 象，影响机器人的正常运行。 ４仿真与结果 ４．１实验环境的选择 实验使用Ｗｉｎｄｏｗｓ操作系统，通过ｃ＋＋语言编写仿真 程序，硬件平台是ＩＢＭ ＴｈｉｎｋＣｅｎｔｒｅ系列，ＣＰＵ主频是３ＧＨｚ。 仿真设置起点坐标、终点坐标、节点数等仿真数据，依据这些 数据生成路径图的拓扑结构，设置觉悟信息的比重因子取值 区间，程序随机产生各节点的比重因子。不断改变节点的总 都得到了提高。 数，分析不同搜索算法在不同节点数情况下的运算效率和 表１算法仿真对比结果 性能。 ４．２实验结果仿真分析 在Ａ 算法中融入计算机视觉特征后，能够确保机器人 向预期节点方向运行，并且对机器人运行特征进行约束融 合，避免发生“死循环”现象。Ａ 算法依据多核处理器以及 ＭＰＩ并行编程技术，进行路径的搜索和优化，相比传统算法 的优点是：运算效率高、耗能量少、有效率高等。分别使用传 统超声波避障方法以及本文算法对相同的复杂路径进行避 障测试，获取的结果分别用图５和图６描述。 ５总结与展望 本文提出一种基于视觉多图像信息融合的机器人避障 算法，通过双目立体视觉采集机器人的实际图像信息，运用 像素自适应融合方法最大程度的采集视觉信息，归一化后的 视觉信息带入Ａ 算法进行最优路径的选择，克服单一信息 选择中路径计算的弊端，建立多信息约束的路径搜索模型， 最大化的解决视觉避障中的干扰问题。通过对机器人实际 的不同路状下的避障实验证明该方法具有很好的鲁棒性与 有效性。 参考文献： ［１］李群明，熊蓉，褚健．室内自主移动机器人定位方法研究综述． ［Ｊ］．机器人，２００３，２５（６）：５６０—５６７． ［２］赵ＩｂＪｌＩ，刘子峰，杨立辉．特种机器人运动轨迹规划及其实现 ［Ｊ］．计算机应用研究，２０１１，（８）：２００７—２００８． ［３］胡萍．超声波测距仪的研究［Ｊ］．计算机与现代化，２００３， （１０）：５４—５６． ［４］ 陈华华，杜歆，顾伟康．基于神经网络和遗传算法的机器人动 态避障路径规划［Ｊ］．传感技术学报，２００４，（４）：５５１—５５５． ［５］Ｅ Ｄｉｊｋｓｔｒａ．Ａ ｎｏｔｅ ｏｉｌ ｔｗｏ ｐｒｏｂｌｅｍｓ ｉｎ ｃｏｎｎａｔｉｏｎ ｗｉｔｈ ｇｒａｐｈｓ［Ｊ］． Ｎｕｍｅｒｉｓｅｈｅ Ｍａｔｈｅｍａｔｉｋ，１９５９，１：２６９—２７１． ［６］漆阳华，杨战平，黄清华．Ａ 的改进路径规划算法［Ｊ］．信息 与电子工程，２００９—８：３２６—３２７． ［７］Ｈａｎｓ Ｗ Ｇｕｅｓｇｅｎ，Ｄｅｂａｓｉｓ Ｍｉｔｒａ．Ａ Ｍｕｌｔｉｐｌｅ Ｐｌａｔｆｏｒｍ Ｄｅｅｅｎ￣ａｌ－ ｉｚｅｄ Ｒｏｕｔｅ Ｆｉｎｄｉｎｇ Ｓｙｓｔｅｍ［Ｊ］．１ＥＡ／ＡＩＥ９９，ＬＮＡＩ １６１１，２００１： 图６本文的Ａ｛算法仿真结果 ７０７—７１３． ［８］ Ｆｕ Ｍｅｎｇｙｉｎ，Ｂｉｎ Ｘａｅ．Ａ Ｐａｔｈ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｄｙｎａｍｉｃ Ｎｅｔ－ 通过对图５和图６的对比看出，本文算法在所有的路径 ｗｏｒｋｓ ａｎｄ Ｒｅｓｔｒｉｃｔｅｄ Ｓｅａｒｃｈｉｎｇ Ａｒｅａ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ ＩＥＥＥ 都没出现避障失败问题，而传统的超声波算法在第１、３、１１ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｏｒｅｎｅｅ ｏｎ Ａｕｔｏｍａｔｉｏｎ ａｎｄ Ｌｏｇｉｓｔｉｃｓ，２００７：１ １９３ 号路线上都出现了避障失败的现象。可见本文算法更加 —１１９６． 优秀。 ［９］ 王菁华，崔世钢．应用几何理论的智能机器人路径规划仿真 算法性能测试得到的对比结果如表１所示。 、［Ｊ］．计算机仿真，２０１０—５：１５—１７． 由仿真结果对比可知，在小规模路径图的搜索中，传统 ［作者简介］ 算法与本文算法的运行时间相当，但由于传统算法不考虑多 何 皴（１９７７一）男（汉族），河南周口人，硕士研究 目标的情况，得到的路径随机性较大；在中规模路径图中，传 生，讲师，主要研究方向为计算机软件与理论、网络 统算法陷入盲区；在大规模路径图中，本文算法的搜索时间 安全、人工智能等。 比传统算法节省了一半左右。以上的仿真结果充分说明本 张翼飞（１９７９一），男（汉族），河南鲁山人，硕士，讲 文算法利用硬件资源和算法优化，使路径规划的性能和效率 师，主要研究方向为信息安全。 ．－－——２８５—－－——