当前位置:首页 >> 机械/仪表 >>

基于超声波定位的机器人路径规划


中国海洋大学 硕士学位论文 基于超声波定位的机器人路径规划 姓名:孙莹莹 申请学位级别:硕士 专业:控制理论与控制工程 指导教师:张磊 201106

基于超声波定位的机器人路径规划

基于超声波定位的机器人路径规划 摘要
随着机器人技术的发展和广泛应用,移动机器人渐渐走入人们的家庭生活。 移动机器人在室内环境的运动规划成为其研究的一个重要方向。室内环境包括家 庭、敬老院、博物馆、机场、仓库、养殖场等,移动机器人想在室内运动,需要 定位系统提供自身位置信息、环境信息和路径规划。 本课题综合多项技术,面向实际应用在技术应用方法上做出了一定的创新工 作,改进了路径规划,完成了室内定位系统的研发和室内环境信息的建模。并通 过仿真和实际机器人完成了实验验证。具体工作分为以下几点: 设计和实现了超声波定位系统的硬件部分和通信协议,选择三边测量法完成 受控物体在运动空间的位姿计算。此处选受控对象为机器人,也可以是人、动物 及需要定位和获取相关信息的移动物体等。 提出建立未知环境地图的方法。机器人在位黄已知的情况下,沿工作环境边 缘行走一个封闭的曲线,对环境的大小进行一个全面的感知,建立环境的轮廓, 用栅格法表示。最后在未知环境栅格化的基础上应用深度优先算法遍历整个可行 的工作空间,搜索出所有的可行路径的同时也就知道了所有的障碍物,建立了室 内环境地图。 改进经典A木路径搜索算法,实现了机器人了从起点到终点的全局最优路径 规划。该路径搜索算法考虑了机器人在行走过程中的转向问题,节省机器人行走 时间,降低行走难度。 利用实现的超声波定位系统采集试验数据,计算移动物体位置,验证系统的 可靠性。通过仿真验证了本课题提出的未知环境的建模和改进的A木路径规划算 法的正确性。最后通过MT—R机器人完成全局路径规划实验。

关键词:移动机器人;超声波定位系统;栅格法;深度优先遍历算法;路径规 划;胁算法

Robot Path Planning Based

on

Ultrasonic Location System

Abstract With
the development and wide

application of robot technology,mobile robots

mobile robot motion planning in gradually come into people’s daily life.And indoor the indoor environment has become
an

important

direction of thdr research.Indoor

eIlvironment include house,nursing home,museums,airports,warehouses,farms

and

etc.To move around in indoor environment,the robot location information,the

envirment information and the
The

path planning needed to be getting first.

project integrated

numbers of technologies,some innovation ways have
approach,and

been made in practical

application—oriented

an improved path

planning

and real envriment experiment showed the algorithm had been proposed.Simulation

algorithm could

give



much better result.Specific works were弱following:
ultrasonic positioning were

Designed and implemented
protocols of
to

system

and communication choosing space.The

ultrasomc

network

designed

and

implemented,
sports

trilateration robot
can

in complete the pose calculation of controlled object

be selected as controlled

object,people,animals and relevant information.

other mobile

objects

which needed to be located and obtained

We proposed



modeling of an unknown

environment.When edge

in the

case

of robot

location was known,the dosed Gurve,the
establishing the

robot walked


along the

of the working

environment,a
environment,

got the

comprehensive

sense

of the working

contours

of the

environment then

the dividing it into grids.Finally,in
traversal

base of
the

an

unknown

environment using the

grid of depth—first

algorithm for

entire

feasible working spacae,the search of all

possible

paths will

know

all the

obstacles at the same time then

establishing

the indoor

environment map.


Improved

the classic A事path search

algorithm,and proposed

new path

robot.In this path search algorithm the turning of planning algorithm for the indoor mobile robot is considered.This finding time.

algorithm

greatly reduced the time of the way

基f超声波定位的机器人路径规划

We

used ultrasonic positioning system which has been achieved

to collect data,

calculate the location of moving

objects

and verify system

reliability.We
correctness

verified the

modeling of an unknown environment

and

improved the

of A木path

planning algorithm which Was proposed in this issue by simulation.Finally,the global
path planning experiment

Was completed

by

MT-R robot.
system;Grid method;

Key

Words:Mobile

robot;Ultrasonic ioacation

Depth?first traversal algorithm;Path planning;A素algorithm

Il

基于超声波定位的机器人路杼规划

1绪论
1.1课题研究的背景和意义
近几年,随着机器人技术的大力发展,人们不再满足于机器人简单的娱乐功 能,怎么能让机器人进入家居环境,帮助人类减轻家务负担成为目前机器人研究 的重点方向。经过科学家多年的研究,各国在室内环境下的机器人应用有了很大 的发展u删。 为了完成家居环境、宾馆和一些公共场合的定期清扫工作,美国iRobot公 司推出室内清洁机器人;为了使机器人可以安全行走在家居环境中实现儿童监护 功能,2005年日本推出PaPeR02005机器;为了在家居中类人机器人能够从事简 单清洁工作和家务,2008年加拿大推出完美机器人妻子Aiko;为了在无入时监 控家居环境,韩国研制出irobi机器人。 对于室内环境下的机器人应用研究,我国研究起步较晚,但是也取了一些成 果。为了护理高位截瘫病人,1995年清华大学开发了移动护理机器人,此机器 人可以完成定位,路径搜索功能;此外将移动机器人应用于室内环境的还有哈尔 滨工业大学研制的清扫机器人,迎宾机器人等。 机器人在家居环境应用,就必须知道机器人在室内的位置和室内环境信息, 在此基础上完成路径的规划。从上面可以看出,这些位置信息的确定,多是利用 机器人本体进行计算,这需要机器人本身带有繁琐的测量仪器,计算量大,获取 困难、而且定位精确度低。 而且对于同~个室内环境,每个机器人都必有自己

的定位系统,这必然增加了机器人的成本,限制了机器人在室内环境的广泛应用。 本课题从于节省成本,扩大机器人在室内环境应用的可行性方面出发,提出 了一个将机器人位置信息获取、室内环境地图建立和路径规划相融合的整体方案 来实现机器人在室内环境的应用。


本课题中利用价格低廉的超声波传感器构建室内超声波网络定位系统来获 取机器人位置信息;在确定机器人位置基础上提出基于栅格的DFS(深度优先搜 索)室内环境地图建立,为机器人提供更详细的室内环境信息;在机器人获得自 身位置信息和环境信息之后,利用改进的A木算法实现机器人的室内路径规划。 随着我国老龄化的到来,研究机器人室内环境的应用具有实际意义。本课题

摹于超声波定位的机器人路径规划

构建的机器人任室内环境的应用系统,具有简单易于实现,成本低,独讧性好的 特点。不论机器人是否带有自动定位系统,本课题都适用,推进了移动机器人在 室内环境应用的可行性。
1.2

MT-R机器人
本课题以室内环境为应用环境,以MT-Rbl智能移动机器人作为受控对象,开

展超声波定位系统、室内环境地图构建和路径规划的研究。 (1)MT-R机械系统 MT—R机器人是由上海英集斯自动化技术有限公司开发的,此移动机器人是 一款中型机器人它既能应用于室内环境又可以应用于室外环境,它的操作系统为
Windows

XP,开发环境为VC。机器人宽度为480mm,总长为490mm,高度为490mm,

重量为35KG,机器人重心离地高度为15cm左右,运行平稳。从外观上看,MT—R 机器人分为两层,底盘和控制层被外壳包容,结构力强,模块化设计,便于拆装 和调试。MT-R机器人的前面正中圆孔和左右相邻各两个圆孔供安装5个超声波 传感器,5个红外线传感器,后面正中圆孔和下方的方孔各安装一个超过声波传 感器和一个红外线传感器。箱顶上有摄像头和无线网卡。下图卜l为MT-R型机 器人的实物图。

图卜l MT—R机器人实物图

MT—R机器人为分布式系统结构,分为控制规划层、运动控制层和信息采集 与处理层,各模块之间用四根定位支撑柱连接固定。

基于超声波定位的机器人路径规划

(2)MT-R机器人运动模块 MT—R机器人提供了强大的运动控制系统。这个运动控制系统硬件部分包括
24V,70W

MAXON电机两个;运动控制卡采用DSP+CPLD结构,能够完成三路以上

的电机伺服控制。软件部分包含有MTMotion函数,它主要负责移动机器人的运 动控制模块,通过获取图像,超声信息,确定任务规划和反应性动作。对于任务 规划来说,通过路径规划模块设计任务序列,计算出机器人当前目标速度的大小 和方向,然后根据机器人的运动学模型,将目标速度分解为机器人的左轮和右轮 速度,并将此信息传给下位机,实现对左右轮的转速控制。 (3)MT-R机器人超声波 MT—R机器人本身带有超声波传感器,可以用来探测障碍物。本课题中我们 选择五个超声波传感器作为移动机器人探测障碍物的工具。本课题用于移动机器 人障碍物检测的传感器就是系统自带的5个超声波传感器,布置在机器人的前方 和左右位置,如下图1-2所示,该传感器的工作频率为40kHz,在工作模式下的 最大有效检测距离7m,这样的超声波测距系统,就是为机器人了解其前方、左 侧和右侧的环境而提供一个运动信息。


图1-2超声波传感器分布图

1-3课题相关技术
移动机器人涉及到机械、电工、自动控制、计算机测量、人工智能、传感技 术等多种技术,是多种高新技术发展成果的集成。要实现室内环境中移动机器人

基于超声波定位的机器人路径规划

安全行走,就必须知道机器人自身位置信息和室内环境的地图,然后利用路径规 划算法计算安全路径。这就需要用到室内定位技术,环境的建模方法和路径规划 算法。

1.3.1室内定位系统

移动机器人在室内环境自主移动过程中,不论是局部避障还是全局规划,都 需要精确的知道机器人的当前状态,也就是移动机器人的室内定位H1问题。目前, 移动机器人的定位系统主要有两类:相对定位系统和绝对定位系统。相对定位系

统是通过测量移动机器人相对于初始位置的距离和方向来确定智能机器人的当
前位姿;绝对定位系统通过测量移动机器人的绝对位姿来定位。 本课题的应用环境是室内环境,目前存在的室内定位系统除了超声波定位系 统以外,还有一些比较有代表性,有红外定位系统、蓝牙定位系统等。 (1)超声波定位系统 超声波定位系统∽1是由多个超声波传感器按照一定的规则组成的测距系 统,测距方式采用单向反射式测距法,通过三边定位等算法确定物体的位置。超 声波定位系统可由多个个超声波接收器和一个超声波发射器组成,主发射器放置 在被测物体上,在微机指令信号的作用下向接收网络发射超声波,接收器在收到 射超声波信号后,得到发射器与各个接收器之间的距离。当同时有3个或3个以 上不在同一直线上的接收器收到超声波时,可以根据相关计算确定出被测物体所 在的二维坐标系下的位置。 (2)红外线技术 红外线技术通过在一定的时间间隔内发射红外线信号,然后红外线接收器接 收这些红外线,按照到达时间算法或到达角度算法计算被定位物体的位置。该系 统要求被定位物体与红外线发射器之间线性可视,这就把它的应用局限到了仅室 内的范围且须保证所监测的目标是不透明的。红外线传输距离短,容易受太阳光 干扰且精确度不是很高,而且造价较高很难应用在室内定位系统中。 (3)蓝牙技术 该技术是一种短距离低功耗的无线传输技术,支持点到点、点到多点的话音 和数据业务。在室内安装适当的蓝牙局域网接入点,把网络配置成基于多用户的 基础网络连接模式,就可以获得用户的位置信息,实现利用蓝牙技术定位的目的。


基于超声波定位的机器人路径规划

使用蓝牙技术实现室内定位其优点是容易发现设备且信号传输不受视距的影响, 设备体积小,容易嵌入到手机等设备中,缺点是目前蓝牙器件和设备价格比较昂 贵,传播距离较短,容易受噪声干扰。 本课题采取的超声波系统定位系统,具有独立性和简单易于实现成本较低的 特点。本课题中的超声波定位系统在以后的研究中不仅适用于移动机器人定位, 而且可以应用各种物体的定位。

1.3.2室内环境建模方法

如果室内环境信息已知,那么地图的建立就变的简单易行。但是在多数情况 下,环境信息是不可知的,这时就需要机器人自带的传感器,如超声波传感器或 红外线传感器来创建当前环境的地图。本课题研究的是不知道环境信息的情况下 建立室内环境地图,所以需要借助机器人自带的超声波传感器来探测障碍物。环 境地图的建立离不开地图的表示方法,目前常用的室内环境地图表示的主要方法 为下面几种,可以根据自己的需要选取合适的表示方法。 (1)可视图法 可视图法由NilSSOn于1968年中提出∞吲。这种方法是将室内的环境信息转 化为抽象的几何特征,使用这些几何信息描述环境。可视图法视移动机器人为一 点,将机器人、目标点和多边形障碍物的各顶点进行组合连接,并保证这些直线 均不与障碍物相交,这就形成了一张图,称为可视图。这种方法缺乏灵活性,在 复杂的非规整环境下难以实现,而且对测量障碍物的传感器的精度要求较高。 (2)拓扑法

拓扑法是一种紧凑的地图环境表示方法,特别在环境大而简单时,这种方法
将环境表示为一张拓扑意义中的图。图中的节点对应于环境中的一个特征状态、 地点,拓扑图的分辨率决定于环境的复杂度。拓扑结构需要较少的存储空间,不 需要知道机器人的确切位置,适用于大规模的未知情况下的机器人导航。拓扑结 构的缺点是当环境中有两点相似时,无法判断这两点的区别。 (3)栅格法 栅格法是1968年W.E.Howden提出的,他在进行路径规划时采用了栅格表示 地图,在处理障碍物的边界时,避免了复杂的运算。该方法简单且易于实现,但 是它的缺点是存储空间要求较大,如果工作环境太大,那么栅格的数量将会增加,

基于超声波定位的机器人路径规划

在大规模的环境下路径规划的计算复杂度也很高。 以上几种环境表示方法每种都有自己的优点和缺点,可以根据具体的环境特 点选取合适的地图表示方法,本课题中将采用简单易行的栅格法表示环境。

1.3.3路径规划算法

路径规划也是本课题的重点研究对象之一。对于自由移动的机器人,路径规 划问题是在可行空间内计算一条安全无碰撞的路径。根据对环境信息了解的完整 程度,移动机器人路径规划可以分为全局路径规划和局部路径规划n洲1。全局路 径规划需要知道环境的所有的信息,根据环境地图进行路径规划;局部路径规划 是在行走过程中,根据传感器测得环境信息,在进行路径规划。目前比较常用的 路径规划算法分为传统路径搜索算法和智能搜索算法口2。1钉。 一、传统的路径搜索算法 (1)人工势场法 人工势场法最初是由Khatibn嗣提出的,基本思想是将机器人在环境中的运 动视为一种机器入在虚拟的人工受力场中的运动。障碍物对机器人产生斥力,目 标点对机器人产生引力,引力和斥力的合力作为机器人的控制力,从而控制机器 人避开障碍物而达到目标位置。该方法结构简单,便于低层的实时控制,但存在 局部最优解,容易产生死锁现象。 (2)A宰搜索算法 A术算法n钉是人工智能中一种典型的启发式搜索算法,它通过选择合适的估

计函数,来约束搜索的过程。A木算法估价函数的定义为f例髫俐砌俐;,例
是从初始结点通过结点到达目标结点的估价函数;g(n)是从初始结点到当前13

结点的实际代价;h俐是从当前结点17到目标结点最佳路径的估计代价。A木算法
的优点是在一个较小的环境下,从起点到终点搜索扩展的节点较少,实现简单直 观,非常适用于室内环境的情况。但是当环境较大而且比较复杂的时候,这种算 法会显得计算量较大,效率会降低。 (3)Dijkstra算法 Dijkstra算法n83是典型的单源最短路径算法,用于计算一个节点到其他所 有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点 为止。虽然Dijkstra算法是典型的最短路径搜索算法,依据此算法可得出最短


基于超声波定位的机器人路径规划

路径的最优解,但由于它遍历计算的结点很多,所以效率较低。
二、

智能搜索算法

(1)神经网络算法 神经网络算法随着机器人技术的广泛发展,开始大量的应用于机器人的路径 规划n螂1。其基本原理是将环境障碍等作为神经网络的输入层信息,经由神经网 络并行处理,神经网络输出层输出期望的转向角和速度等,引导机器人避障行驶, 直至到达目的地。神经网络算法的优点为它的并行处理效率较高,而且具有自主 学习功能,所以能收敛到最优路径。 (2)蚁群算法 蚁群算法由Marco Dorigo于1992年在他的博士论文中提出,是一种模拟进 化算法,初步的研究表明该算法具有许多优良的性质。机器人的路径规划问题非 常类似于蚂蚁的觅食行为,所以机器人的路径规划问题完全可以看成是从蚂蚁巢 穴出发绕过~些障碍物找到一条从巢穴到达食物源的最短路径。 (3)模糊逻辑算法 模糊数学诞生于1965年,它的创始人是美国加利福尼亚大学的自动控制专 家扎德(L.A.Zadeh),在他的第一篇论文《模糊集合》(Fuzzy Set)中,首先引 入了隶属函数(Member
ship

function)的概念。模糊逻辑方法是对传感器获得

的信息进行分析,确定机器人的行动路径,该方法该方法在部分环境未知或者是 不知的情况下,能够很好地规划机器人的路径,非常适用于局部路径,但是同时 该方法存在着“对称无法确定"的现象。 (4)遗传算法 遗传算法的概念最早是由Bagley J.D在1967年提出的,是根据生物进化思 想的启发而得出的一种全局优化算法。遗传算法在本质上是根据生物进化思想的 启发得出的一种全局优化算法,其基本实现为编码、选择、交叉和变异。遗传算 法使路径收敛到全局最优,避免了局部极小值问题,且计算量较小伍¨。但是它运 算速度不快,进化过程要占据很大的存储空间和运算时间,不利于自动处理。 本课题的应用环境为室内环境,环境简单,障碍物较少。在考虑各种路径规 划方法的基础上,选择了A木算法来完成机器人的全局路径规划。



基于超声波定位的机器人路径规划

1.4本文研究内容及组织结构
第一章在阅读了大量中外文献的基础上,先介绍了课题的研究背景和研究意

义,介绍了本课题的受控对象MT—R机器人,最后介绍了本研究课题涉及的关键
技术定位系统、环境建模方法和路径规划,并对这些关键技术做了概述和总结。 第二章详细的介绍了超声波网络定位系统的设计和实现,分为硬件组成和通 信模块。在系统实现的基础上,比较目前存在的定位计算方法,选择一种实现机 器人位置的计算。 第三章详细的介绍了环境地图建模法。提出了在由机器人测得室内环境大小 的前提下,将室内空间环境栅格化,再利用深度优先遍历室内环境,找出所有障 碍物的地图建立方法。同时,制定了机器人测量室内环境面积和深度优先全局遍 历的原则。 第四章首先介绍了经典的A木路径搜索算法,在此基础上对为算法进行了改 进,提出了一种估价函数的构建方法,和避免路径迂回行走的改进。 第五章主要是利用超声波定位系统,采取一些数据,计算出超声波发射器的 位置,证明此系统的可行性。用Visual
studio

2005仿真了用DFS遍历建立室

内环境地图,同时在地图建立好的基础上仿真了改进A木搜索算法的可行性。最 后利用MT—R移动机器人实现全局路径规划试验。 第六章主要是总结前面的章节的主要内容以及展望未来。

基于超声波定位的机器人路径规划

2超声波网络定位系统设计与实现
随着机器人技术的迅速发展,开发面向家庭的服务机器人已是必然的趋势, 其核心问题是如何获取真实有效的机器人位置信息和如何利用位置信息实现机 器人的自主运动。如果采用机器视觉、雷达探测等技术,机器人大多需携带多种 设备,不但成本高而且对计算速度和精度的要求较高,获取环境信息有限,很大 程度上限制了机器人的在室内环境中的广泛应用。超声波装置价格低廉,装置简 单,经济实用,工作稳定,所以具有一定的推广性,本课题提出在构建室内超声 波定位系统为机器人提供自身位置信息,可以使机器人免除带繁琐的设备。而且 此定位系统具有独立性,可适用于所有的机器人或者移动物体。

2.1超声波测距原理
超声波通常是指频率超过20KHz以上的声波, 具有指向性强,发射出去后

能量消耗比较缓慢,在介质中传播的距离较远的特点,所以超声波经常被应用于 距离的测量。超声波测距的方法有多种,如相位检测法、声波幅值检测法和渡边 时间差检测法等但捌1。相位检测法是通过测量返回波与发射波之间相差多少相 位,判断距离;声波幅值检测法是看回波的幅度大小,判断距离;渡越时间检测 法是通过回波的返回时延判断距离;相位检测法虽然精度高,但检测范围有限; 声波幅值检测法易受反射波的影响。


本课题采用超声测距最常用的方法时间差探测法,即在声速己知的情况下, 通过测量超声波回声所经历的时间来获得距离。超声波发射器向某一方向发射超 声波,在发射时刻的同时开始计时,超声波在空气中传播,途中碰到障碍物就立 即返回来,超声波接收器收到反射波就立即停止计时。超声波在空气中的传播速 度为340m/s,根据计时器记录的时间t,就可以计算出发射点距障碍物的距离S 即:S=340t/2。这就是所谓的时间差测距法,如图2-1所示。



基于超声波定位的机器人路径规划

酶 磷 物

图2-1超声波测距原理图 超声波在发射之后,由于介质的干扰,它的能量会降低,为了避免这种情况 的误差增大,在实现超声波测距时本课题不采用反射测距法而是采用单向测距 法,所谓单项测距法就是由被测物体发射超声波,然后由固定的超声波接收节点 接收超声波,根据测量法得到距离值。得到距离值之后,结合特定的定位算法, 可以计算出被测物体位置。

2.2系统设计与实现

2.2.1系统结构设计

课题设计的超声波定位系统防矧包括超声波接收器、超声波发射器,RF信号 发射器、主控节点和控制中心。超声波接收器和主控节点以一定的间隔被固定在 室内的天花板上。超声波发射器和RF信号发射器都固定在移动机器人身上。移 动机器和控制中心采用无线网络通信,超声波接收节点和主控节点通过485总线 与控制中心进行数据的传输。 控制中心发射启动命令,固定在天花板上的主控节点和超声波接收器接收到 命令后,主控节点向固定在移动机器人身上的RF信号接收器发出一定宽度的射 频信号,超声波接受器则启动自带的定时器。RF信号接收器接收到主控节点的 信号后启动移动机器人身上的超声波发射器发出超声波,超声波接收器接收到超 声波后其内部的定时器就会停止计时。最后,通过遍历询问,超声波接收器内的 定时器将记录的时间数据通过RS485总线传给控制中心存储。利用这些储存的时 间数据,通过一定的算法计算出移动机器人的位置。超声波定位系统模型结构图 如图2-2所示。

i0

基于超声波定位的机器人路径规划

图2-2超声波定位系统结构图

2.2.2系统硬件组成

超声波定位系统的硬件由超声波发射结点,超声波接收结点,控制节点和作 为控制中心的Pc机组成。Pc机发出命令,控制节点发射射频,超声波接收器内 的定时器开始计时,固定在移动终端的射频接收器接收到控制节点发射的射频后 启动超声波发射结点发射超声波,超声波接收节点接到超声波后定时器停止计 时,并将时间数据传给Pc机进行数据处理,来计算移动终端的位置。超声波定 位系统硬件组成如下图所示:

图2-3超声波定位系统的硬件组成图

基于超声波定位的机器人路径规划

Pc机(控制中心)主要完成两个功能:①通过RS232和RS485总线与主控节

点、超声波接收节点进行通讯;②负责定位坐标的计算: 主控节点的主要完成两个功能:①接受来自控制中心的启动命令;②主控
节点接收到启动命令后通过射频模块向固定在移动终端上的射频接收器发送射 频。

超声波接收节点主要完成三个功能:①接受来自控制中心的启动命令,启

动MCU里边的定时器开始计时;⑦接收超声波发射器发送的超声波,并在检测
到超声波发射器发来的超声波时停止计时;③控制中心遍历节点,把所得时间
数据回传给控制中心存储。 移动机器人需要带有接收主控节点发射射频的射频接收器,MCU,超声波发 送器等。对于组成超声波定位系统的器件选择的具体情况如表2-I所示:


RS485驱动
McU

表2—1超声波定位系统的硬件组成

主控节点 采用MA)【487芯 片
采用ATMEL公司 的Atmega48

超声波接收节点

移动机器人

采用MAX487芯片 采用ATMEL公司的 采用ATMEL公司的Atmega48
Atmega48

型号F05R,载 射频发射模块 频频率
315/433M

射频接收模块 超声波发射器

型号J04V,载频频率315/433M 型号NU40CIOT,频率40KC,发射 角80度,驱动电压可达40伏 由交流AC/DC适 由交"KU~C/DC适配器 由交流AC/DC适配器统一供电,24 伏

电源

配器统一供电, 统一供电,12伏
12伏

射频接收器我们采用安阳市新世纪公司的J04V微型射频发射模块,载频频 率315/433M,其优点是输出无噪声干扰、极低功耗和特小体积,不需外接天线,

12

基于超声波定位的机器人路径规划

射频调制及解调都有MCU完成,MCU采用ATMEL公司的Atmega48,如图2—4中的 a;射频发射和超声波接受模块采用如图2—4中的b;超声波发射器我们采用深 圳金瓷公司的NU40CIOT,其频率40KC,发射角80度,驱动电压可达40伏,如 图2-4中的c。







图2-4定位系统硬件芯片

2.2.3系统通信模块设计

一、串口通信 串口通信应用于主控节点和超声波接收节点上,实现其与控制中心通信的功 能。既通过串口通信可达到控制中心向主控节点和超声波接受结点发送命令及接 收数据的功能。 串行通信端口RS232是Pc机上的标准配置。在通信速率低于20kb/s时, RS一232C所直接连接的最大物理距离为15m(50英尺)。RS-485总线,在要求 通信距离为几十米到上千米时,广泛采用RS一485串行总线,而且RS一485用于 多点互连时非常方便,并可以联网构成分布式系统,所以在本系统中用RS485 总线进行各节点之间的连接。而由于RS232和RS485之间的电气特性不同,故需

要一台RS232—485转换器。下图是RS232/RS485转换器:

基于超声波定位的机器人路径规划

图2-5

RS232/RS485转换器

将转换器的两端分别连接RS232/RS485的各串口端,RS485总线各子端连接 到主控节点及接收节点的J4口。 二、通信协议的制定 超声波定位系统中,控制中心(PC机)与主控节点、超声波接收器等都要 进行通信,这就需要制定串口通信协议。超声波定位系统中的通信主要分为:控 制中心发射命令启动主控节点和超声波接收器中的定时器;控制中心通过遍历所 有的超声波接收器将定时器内的数据传回控制中心。 (1)控制中心发射命令启动主控节点和定时器 开串口,串口初始化,发送启动命令,协议格式如下所示:
FFH

I√um



ol



由控制中心(PC)机向主控节点和超声波接收节点发启动命令,各节点接收

到命令后做各自的需要完成的任务。各超声波接收节点接收到FFH从H码后就启 动定时器开始计时,0l码对超声波定接收器无效;主控节点接收到FFH从H 01码
后启动某移动终端发超声(由于定位系统可以定位多个移动终端所以01代表编 号为l的移动终端)。通过上面可以知道对超声波接收节点而言第三个字节参数 无效,即接收到第二个字节时,定时器启动;而对主控节点第三个字节则作为移 动终端地址码。 当移动终端接收到主控节点发出的射频以后,固定在移动终端上的超声波发

14

基于超声波定位的机器人路径规划

射器就向超声波接收器发射超声波,接收到超声波信号的超声波接收节点产生外 部中断,定时器停止计时。没有接到超声波信号的接收器则定时器溢出归零。 (2)定时器内的数据信息获取 超声波接收器内的定时器接收到超声波信号后停止计时,需要将这些定时器 内的时间数据传回PC机(控制中心)。在本课题中我们采用了各节点遍历的方式, 挨个询问超声波定时器,如果定时器内有数据则把数据传回,如果没有数据则放 弃,不用传回,接着询问下一个,直到遍历所有的接收节点。在遍历过程中需要 PC机发送一个命令让哪个接收节点内的数据传回,接收节点在接到传回命令后 将自己的定时器数据传回,这些命令的格式下面将介绍。 请求式命令:PC机访问某单独接收节点, 请求该接收节点返回超声波定时

回传式命令:某接收节点向PC机返回超声波定时内的时延参数,共有四个 字节组成(超声时延值码需二个字节):



Il

FFH

55H

定时器内数据



Pc机发送呼叫帧(即Pc机向某接收节点发送取数据命令)后,等待一段时 间后如果没有收到接收节点的应答帧(即接收节点向Pc机发的回传数据)i则 PC机认为帧丢失并重新发送呼叫帧。若呼叫三次仍无应答,则系统认为接收节 点处于关机状态(或者已经坏了),转而呼叫下一节点。

23定位算法
如果想要实现移动机器人的自主运动,必须首先解决机器人的定位问题,让 机器人知道自己在哪里,明确自己所在环境的具体方位。只有这个问题解决了, 通过机器人遍历室内环境建立地图和路径规划才能有意义。所以在超声波定位系 统中选取合适的计算方法计算机器人的位置很重要,如果选取的计算方法合适可 以节省计算量。本课题选取了三边测量法计算机器人的位置。

2.3.1常见的超声波网络定位算法

目前常用的节点定位算法以定位的方式可以分为两大类:基于测距算法和

基于超声波定位的机器人路径规划

无需测距算法。基二F测距算法是通过测量节点间的距离或角度信息,使用三边测 量、三角测量或最大似然估计定位方法计算节点位置;无需测距定位算法不需要 距离和角度信息,而是根据网络连通性等信息来实现节点定位。现有的基于非测 距的算法有:质心法、基于距离矢量计算跳数算法、无定形的算法及三角形内点 的点近似定位算法、基于方向的节点定位算法等睁3¨。 目前有多种算法可以实现在超声波网络定位系统中的定位计算,主要为三边 测量法、三角测量法、极大似然估计法。下面将详细的介绍每一种定位算法的具 体应用。 (1)三边测量法

三边测量法如图2-6所示,已知A、B、C三个节点的坐标分别为阢川,伍 州,
伍yo),它们到未知节点D的距离为以,以、
吐,设D的坐标为(X,Y)。

那么,可以获得一个非线性方程组,如公式(2—1)所示:

正i丁而=丸
瓜二了瓦j了=d。
瓜=了瓦j了=d。

(2一1)

通过解这个线性方程组,我们可以的到D点的坐标(x,y)为:
d x4一xc+4一yc+c_o 屯2一瓦2+42一儿2+12_dY d。2



2(丘一x。)-2(y。-y。) 2(xb—xA一2(y6一Y。)

(2.2)
一xc+yh—c七c—h Xb2一t2+y62Yc2+dc2d62

16

基f超声波定位的机器人路i÷规划

I~kxo,一x。)2+(yol-y。)2=‘
{4(Xo,一Xc)2+(蜘l一儿)2=^
(2.3)

l(x。一t)2+(y。一y。)2=2‘2(1一COS0r)

基f超声波定位的机器人路径规划

图2—7三角测量法 (3)极大似然估计法

已知1、2、3等n个节点的坐标分别为阮∥,阢∥,阢∥,…一… 阢yo),以及它们到未知节点D的距离分别为以如西…….砌,设定D的坐标
为(X,Y)。应用最大似然估计法会有下面的公式: (xI—x)2+(yl-y)2=d12
……



(2-4)

(‘一x)2+(y。-y)2=以2 J

五2一_2—2(xl一矗)x+y12一儿2—2(yl一儿)y=42一dn2
……. X2n_I—xH2—2(.h—l—Xn)x+y2。一l—Y2。一2(y。一l一儿)y=d2。-l—d2^ 上面公式(2-5)的线性方程为AX:b,其中: 2(xl一矗)一2(yl—Y。)
A=

(2—5)

2(x。一l—b)一20,。一I一儿) IXd一2以+n儿%
b=

一xn+y、一yn七dn一、 12

x2月一l—x月2+y2月一l一儿2+以2一d2H—l

Ⅳ=圈

18

基f超声波定位的机器人路径规划



用最小均方差估计可以得到节点D的坐标(x,Y)为X=(Ar彳).1

Arb

以上共介绍了三种定位的方法,这三种方法均可以应用于超声波定位中, 在本文中的超声波定位中,我们选择简单计算的三边测量定位法。

2.3.2具体位置计算

本文我们采用三边测量算法进行定位系统中的被定位物体的位置计算口2剖。 适当调整接超声波接收网络中超声波接收器之间的配置距离间隔d,就能保证接 超声波接收网络中至少有三个超声波接收器接收到从机器人身上的超声波发射 器T(玉.,Y.)发出的超声波。我们从接收到超声波的超声波接收器中选出不在 一条直线上的三个超声波接收器分别表示为R1,R2,R3,由于超声波网络是设 定好的,因此这些超声波接收器的位置是已知的。选定的三个超声波接收器的位 置是已知的,它们的坐标值分别为R。(x儿Yn,H)
Rf3

,Ri:bn,Y加H)’,

k3,虼,1-1)

(图2—8)。

图2-8超声波定位示意图 超声波接收器R1,R2,R3是预先配置在天花板上的,因此它们的坐标值已 经知道。根据三边测量原理,固定在移动机器人身上的超声波发射器T的坐标值
(■.,Y1)为

19

基于超声波定位的机器人路径规划

Xi,)2+◇。 y∥+H2=t12 ‘:)2+“ 咒2)2+日2df22 ‘,)2+(y。 Yi3)2+H2=叱2

(2-6)

上式中H=天花板到固定在移动机器人上的超声波传发射器的垂直距离; dn,dmd;,是固定在移动机器人身上的超声波发射器到选定的超声波接收器的距 离,由超声波测距求的。由上式(2-6)可以求得移动机器人身上的超声波发射 器位置坐标T(而.,Y。)。在理想情况下,联立方程组(2-6)的解是唯一的,即在水 平面上三个圆相交于同一点T(xL,Y。)(图2—8)。当有误差存在时,图2-8中的三 个圆并不交于一点。在本文中,我们暂时假设系统不存在误差,三个圆交于一点。 移动物体的定位不仅仅是二维坐标的计算,还包括方位(旋转角度)计算, 本章设计实现的超声波定位系统也可以计算出移动物体的方位。我们在移动机器 人前面和后面安装两个超声波发射器T1(‘,,Y1,0),T2(x2,Y2,0),这两个超声 波发射器的位置Tl,T2都带入上面的公式(2-6)求解后,我们就可以利用下面 的公式(2-7)求的移动机器的方位p,选取T1,T2坐标的中间值作为机器人的 二维平面坐标T(x,Y)(公式2—8)。

0:删an(丛生)
西一x2


(2—7)

lI

,● ●J、 ●【





一一2一一2

(2—8)

选取合适的时间数据,采用上面的算法就可以计算出机器人的位姿 T(X,Y,秒)。

2.4本章小结
本章介绍了了超声波网络定位系统的计算原理,完成超声波网络定位系统的 设计与实现,包括构建超声波定位系统的芯片的选取和通信协议的制定。在此基 础上分析常见定位算法,选择三边测量法完成了被测物体的位置计算。

基卡超声波定位的机器人路径规划

3基于栅格的DFS室内地图建立
移动机器人随着科学技术的发展作为家务和办公室助手正逐渐走进办公室、 超级市场、家庭居室等室内环境。要使移动机器人能够在室内环境中自由安全的 移动,就必须知道室内环境的障碍物位置,这就牵扯到室内地图的建立。本课题 中的室内地图建立就是利用机器人自身传感器搜索出环境大小后,将整个环境用 栅格法表示。在未知障碍物的栅格地图上给机器人设定一个起点和不可到达点, 采用深度优先(DFS)全局遍历搜索,得出栅格地图上所有的障碍物信息。这样 整个环境地图就建立,为机器人的路径规划提供足够的环境信息。

3.1栅格法
本课题的应用环境为实验室空间,室内面积较小,室内结构简单。在考虑目 前存在的环境表示方法优劣后,本课题采用了栅格法表示室内环境。


3.1.1栅格法

栅格法将机器人工作环境分解成一系列网格单元,就是将室内环境用大小相 等的方格表示,环境中的障碍物不论形状如何都占用不等的方格。并且在机器人 运动过程中,栅格的位置和大小不发生变化。从机器人运动安全性考虑,栅格的 大小多以机器人自身的尺寸为准降驯。栅格法具有简单、实用、操作方便的特点, 具体为: (1)不论障碍物为规则障碍物还是不规则障碍物,都无需知道障碍物形状和大小。 (2)不需要考虑运动对象的运动轨迹、数目及形状。 (3)算法实现简单,在很多场合都适用。 (4)只要起始点与终点之间存在路径,栅格法就一定能找到一条合适路径。 栅格法作为一种环境建模的方法,在拥有优点的同时,也具有其缺点: (1)当搜索的空间大时,需要的存储空间增大。 (2)搜索路径的精确度与栅格粒的大小有关系。 (3)栅格搜索出的路径是曲折的不够平滑,增加了机器人行走时转弯的难度和机 器人路径行走的时间。. 栅格法应用于机器人工作空间的规划目的是建立机器人工作环境的数字地
2l

基十超声波定住的机器人路径规划

图,在地图中存贮移动机器人的运动轨迹和空ll】J内的障碍物信息。所以,栅格法 主要包括两部分地图建模和信息编码。地图建模就是将一块实际的场地划分成等 面积的小方块,每个小方块称为一个栅格,栅格的大小一般由移动机器人大小来 决定。移动机器人在栅格化的场地中运动时,可以通过传感器获取工作空间的障 碍物信息,并将障碍物的信息转化为栅格属性,构成基本的地图信息。信息编码 是对地图进行数字化编码。栅格法中的编码方法是对每个栅格的障碍物信息用一 个二迸制数表示,有障碍物时表示为“1”,无障碍物时表示为“0”。一个空间 在完成建模和信息编码后,如图3一l所示,其中黑色方格为有障碍物的栅格用1 表示,白色方格为自由空间用0表示。

?j

fl

fI

:I

fl

f{

fl

¨

it

fI

i}

(;

fI

fl

《}

7}

《}

,}

《i



f{

(‘

e『

?}

≤l

fI

,l



{l

f{

e}

’;

f}

(1

、j

(}

《}

f.

,}

,,

,{

(I

jl

,,
’J

《}

iI

{{

l}

《I

:{

《‘

!{

(j

fI

:}

<l

{}

:l

一}

《:

,I

(I

(4

-‘l

,I

!}

基于超声波定位的机器人路径规划

我们首先设每个栅格的中心坐标为栅格的直角坐标,则每个栅格编号都与其 直角坐标一一对应。地图中的任意一点(X,Y)-q栅格编号N的映射关系如下面的 公式所示:

Ⅳ=叫忐]+等×吐老)
INT函数表示取整操作。

伊-,

公式(3一1)中,x删表示栅格的坐标取值范围;G妇表示所选取的栅格粒的大小;

同样,从序号法也可以求出栅格粒的中心坐标,则栅格中心坐标GG砌,y制)
与栅格编号N之间的映射关系如下所示:

XGrid=@%1|11)xG龇々导(3-2)
Yo,百a=INl

tN/M)xG‰七可G¥/ze(3-3)
Us魄

公式(3—2)和(3—3)中,M__len毋,h,符号%表示取余操作。
栅格编号和坐标关系如图3-2所示,x,y的范围xtengat、y蚴均设为10,
栅格粒的尺寸大小设为1,栅格粒中心的数值就是栅格粒的编号。图中共有100 个栅格,其中第一个栅格的编号为0,是为了配合VC++中数细编号的习惯。

基于超声波定位的机器人路径规划

,r

《I





:{













l《}

】l

i2

l:王

l毒

15

l翁

17

18

19

銎J

2l

22

23

2毒

25

26

27

28

29

:;《'

3l







25

30

37



39

40

违t


毒2



44

,毒器

46

毒7



49

融j

5l





5毒

5器



5彳








6l

蘸2

63

64

8嚣



87

68


_g

7l

72

73

7奄

7S

7鑫

77

豫 鹅
g毫

黝 酶

8l

8皇

83

84





96

87



《Il



售3

§亳

97

l驹



图3-2序号法与坐标法对应关系

3.1.3室内环境栅格法建模步骤

栅格法作为环境建模方法易于实现,具有一致性、规范性和简单性的特点。 室内环境相对固定,范围小,避免了栅格法中由于空间范围大导致的信息量大的 缺点,所以本文选用栅格法作为移动机器人室内工作环境的建模方法。用栅格建 模法在室内环境可以分为三个主要步骤: (1)栅格粒大小的选取 首先室内空间(地面的大小)用网格表示,每个网格就是一个栅格。栅格的大 小是个关键因素,栅格选得小,环境分辨率较大,但抗干扰能力弱,环境信息存 储量大,决策速度慢;栅格选得大,抗干扰能力强,环境信息存储量小,决策速 度快,但分辨率下降,在密集障碍物环境中发现路径的能力减弱。从机器人行走 安全性考虑,一般栅格大小以机器人的大小为准。本课题的受控对象为MT—R机 器人,其宽度为480ram,长为490ram,所以栅格粒的大小选择为480mm*490mm。

在实际应用中是地板砖的大小,这样也更利于实际室内环境栅格地图的建立。

基于超声波定位的机器人路径规划

(2)障碍物栅格确定

当机器人新进入一个环境时,它是不知道室内的障碍物信息的,这就需要机
器人能够遍历整个环境,检测障碍物的位置,并根据障碍物位置找到对应栅格地 图中的序号值,并对对应的栅格值进行修改。自由栅格为不包含障碍物的栅格赋 值0,障碍物栅格为包含障碍物的栅格赋值l。 (3)特殊障碍物栅格的处理 机器人在探测障碍物过程中,会遇到一些特殊的障碍物栅格,比如室内的书

桌,餐桌等凹形障碍物。当机器人进入到桌子底部时(不考虑机器人高度),机 器人会检测到其前方和左右方都有障碍物,也就是一个凹障碍物,这时可以把桌
子所覆盖的面积都当成障碍物处理。如果障碍物为中空的,例如一个四只脚的桌 子,这时机器人可以从桌子底下钻过去,这种情况下可以把桌子底下没有障碍物 的地方划为自由栅格,桌脚部分设为障碍物栅格。也就是图3-3中(a)情况处 理成(b)情况。凹形障碍物将凹进去的部分当做障碍物处理,作为障碍物栅格; 对于四只脚的桌子(桌子底部机器人可以通过),桌子底部处理成可行的区域, 设为自由栅格。

基于超声波定位的机器人路伶规划

基于超声波定位的机器人路径规划

掉一部分重复的节点,从而提高了搜索效率。这两种算法每次都扩展一个节点的 所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的 一个,而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提 高效率,所以采用了不同的数据结构。广度度优先算法的流程图如下:

图3-4广度优先算法搜索流程图 深度优先算法的流程图大致~样,只是相应的队列改为栈即可。由于广度优 先搜索的下一个搜索扩展点是当前搜索点的兄弟节点,所以搜索过程中需要多次 重新设置搜索的起点,不利于实际操作,而深度度优先的搜索算法的下一个搜索 扩展点是本次扩展出来的子节点中的一个,通过回溯可以方便的找到下一个扩展 点,利于实际操作。

一一一=一瑚度优先搜索是一种在开发爬虫早期使用较多的方法,它的目的是要达到被
搜索结构的叶结点。在一个路径中,当一条路径被选择后,被选择的路径将执行
27

基于超声波定位的机器人路径规划

深度优先搜索,即在搜索其余的路径结果之前必须先完整地搜索单独的一条路 径。深度优先搜索沿着路径上的节点走到不能再深入为止,然后返回到某一个路 口,再继续选择该路口中的其他路径。当不再有其他路口可选择时,说明搜索已
经结束。

本文的实验环境为室内的家居环境,因此时间复杂度不太大,可以采用深度 优先算法遍历整个室内环境,建立未知环境下的栅格地图。采用这种方法能够较 快的完成所有的路径的搜索,节省搜索时间。

3.2.2基于DFS遍历的室内栅格地图建立

本课题中受控对象是前面介绍过的MT—R机器人,此机器人前后左右都带有 超声波传感器,用来探测机器人行走过程中遇到的障碍物。制订一些机器人行走 规则,就可以知道整个房间的情况,从而建立室内环境地图H2喵1。 首先建立地图应该知道整个环境的轮廓,本课题中采用实验室房间作为实验 对象,实验室是个规则的长方形,所以可以让机器人比较容易的得到整个房间的 轮廓。假设图3-5为机器人的工作环境,让机器人沿墙角的一点出发,(保持机 器人两轮的速度相同让机器人可以沿直线运动)保持机器人的左侧传感器始终探

测到障碍物,当机器人的前方传感器探测到障碍物时,使机器人能够右转,遵循
这个规则让机器在封闭的空间内运动。正由于机器人运动空间是封闭的,所以机 器人最终会回到原来的出发点,这样整个房间的轮廓就可以得出来了,也就建立 了地图的轮廓,如图3-6所示,墙壁是不可行走的,在地图中可以把墙壁当做障 碍物处理。机器人认为墙壁以外的空间是不可行的,墙壁以内的空间为可行的。
■一●■■一一●■●■一●一一■■■●l 一 ■ _ ● ● l ■ ● ■ ■ ■■■一 ■■ ■ 一 一■ 一一一一一一 .一一 ■ 一 ■。一 一 一 ■ ■■ ■ ■ ■ r■麓一 ● 一 一 ●■ 一 一 一 一■ 一 一 ● ■■一■一 一 ● ● ■ l ■ ●● _ ●●●●一 一 _ 一■一一一 ● ●



图3—5室内环境

图3-6探测的环境轮廓

知道了地图的轮廓大小以后,就把室内的空间栅格化,这样就把DFS全局遍

基f超声波定位的机器人路行规划

历搜索变成了在一个不知道障碍物的栅格地图内搜索所有自由栅格问题。建立了 如图3—6的栅格地图后,就可以利用深度优先算法搜索室内的障碍物。首先给机 器人设定一个搜索的起点和不可到达终点,然后让机器人按照深度优先搜索算法 遍历室内所有的自由栅格,室内所有的可自由栅格知道后,不可到达的栅格被定 义为障碍物栅格,这样整个房间的地图就建立了。在这里为了保证机器人可以遍 历地图中所有可行路径,我们通常把终点设置为一个不能到达的点,因为如果终 点可达到,机器人会在没有全部遍历室内环境的情况下停止搜索。由于本课题中 的地图坐标都为正,所以本文中终点设置为(一1,一1),这是一个在墙外的点, 不可到达。同时机器人在寻路过程中遵循“下右上左”的原则,既机器人先向下 行走;当机器人前方遇到障碍物时,机器人转向右走;当右边也遇到障碍物时, 机器人退回到上一个栅格,由于这个栅格的下面已经走过了所以不再走,这时根 据下右上左的原则,机器人向右边的栅格前进。遵循这样的规则,机器人最终可

以搜索出所有的可行路径,并且机器人最终将返回起始点,此种方式不需要人工
干预,非常适合于机器人的非实时寻路。 在如图3-6这样的栅格地图上,用深度优先算法出的障碍物都是基于这么一 条原则的:障碍物的大小永远等于n个栅格的大小,不会出现半个栅格这样的情 况。

3.3本章小结
本章在阅读大量文献的基础上,考虑本课题的应用环境,利用栅格法和深度 优先搜索算法,提出了适合本课题的室内环境地图建模法。机器人先测得室内环 境大小,将室内环境先栅格化,然后采用设定不可到达终点的深度优先遍历,获 知室内的所有信息,建立了室内环境地图。本章节为下面章节的机器人路径规划 准备了必要的地图。

基于超声波定位的机器人路径规划

4基于A央算法的全局路径规划
4.1

A女算法的改进
A木算法是人工智能中一种典型的启发式搜索算法,它通过选择合适的估计

函数来约束搜索的过程,达到提高搜索效率的目的。由于A木算法的简单易行使 得它在机器的全局静态路径规划中应用的比较广泛。

4.1.1

A牛算法

胁算法m1是到目前为止最快的一种计算最短路径的算法,它是一种‘较优’ 算法,即它一般只能找到较优解,而非最优解,但由于其高效性,使其在实时系 统、人工智能等方面应用极其广泛。 A术算法是一种启发式的搜索算法,它能在有限步内终止,与DFS和BFS这类 盲目型搜索最大的不同,就在于当前搜索结点往下选择下一步结点时,可以通过 一个启发函数来进行选择,选择代价最少的结点作为下一步搜索结点而跳转其 上。也就是说A木算法最为核心的部分,就在于它的一个估值函数的设计上:
只n》=|g《n)+lltn)

g(n)表示从给定起始节点到当前节点n的实际代价,而h(13)则是从当前节 点n到目标节点的估计值。 如果需要A术给出最优的路径,那么启发式函数值就应该是从起点位置到终 点实际代价的一个低估值,但如果启发函数值过低,则启发式给胁搜索算法的 信息就太少,并始终告诉A木搜索算法还存在更好的路径,则会导致搜索时间明 显增加。因此A木算法中启发函数的选取十分重要。 A木算法是一种较优算法,并不能找到最优解,但是具有估价函数

f纠髫纠砀纠的A木算法需要满足如下条件则肯定能找到最优解: ①搜索树上存在着从起始点到终了点的最优路径。 ②问题域是有限的。
③所有结点的子结点的搜索代价值>o。

基干超声波定位的机器人路径规划

④h俐=秭书俐阳事例为实际问题的代价值)。
4.1.2

A章算法改进点

本章在利用了传统的A木搜索算法的同时,根据根据实际运用情况,做了改 进。

第一点是对估价函数,国的改进。A:Ic算法最为核心的部分,就在于它的一

个估值函数的设计上?,例髫例舶纠。其中,例提供的是起始点到达目标点
的最低代价,它有两部分组成:一部分是g俐,它表示从起始点到当前点的代
价;另一部分h(n),是启发式搜索中最为重要的一部分,即当前点到终点的估

计值,h纠设计的好坏,直接影响着具有此种启发式函数的好坏。好的启发式函
数可以产生好的路径,而一个较差的启发式会减慢胁算法,导致产生不好的路
径。

一般情况下,俐的选取都是以路径的长短作为评价标准的,路径最短的为
最优路径,但是本课题的应用对象为机器人,这就牵扯到机器人的转向问题,在 路径大小相同的情况下,如果机器人转向较少,这会减少机器人的路径搜索时间, 提高运行效率。如果转向太多则会使路径变得相对复杂。再考虑了机器人行走路

径长短和转向问题后,我们提出了这样一种新的,例的构建方法:对于路径长
度部分采用经典曼哈顿计算方法,对于机器人转向代价的标准则采用当前节点中 机器人的方位口(旋转角度)(第二章中计算的)与相邻节点方向的角度差。则得 出一个新的


,向)髫例铂俐,g俐采用曼哈顿法计算,既从起始栅格到当前栅格时, 已经走过的栅格数乘以10,以后每走一个栅格g(n)就加上10:乃俐只是一个对
剩余路径代价的估算,分为两个部分,路径长度估计和机器人转向代价估计。路 径长短部分使用Manhattan方法,即从当前栅格开始,水平、垂直移动到目标栅 格的总的栅格数(包括障碍物栅格)乘以10;机器人转向代价估计采用机器人方 位角矽与相邻节点方向的角度差。 曼哈顿法是一种距离计算方法,它计算从当前格到目的格之间水平和垂直的 方格的数量总和,忽略对角线方向,然后把结果乘以lO。这被称为曼哈顿方法

基于超声波定位的机器人路径规划

是因为它看起来像计算城市中从一个地方到另外一个地方的街区数。 第二点对A木算法流程的改进,传统的胁算法流程如下: 步骤I:初始化,建立一个OPEN列表和一个CLOSED列表。 步骤2:把起点S加入到OPEN列表中去。 步骤3:如果OPEN列表是空,搜索路径失败,返回,否则进行步骤4。 步骤4:遍历OPEN列表,查找,值最小的点,将该点作为bestnode移入CLOSED 列表,并把它作为当前点。 步骤5:判断当前点bestnode是否为目标点,若是,则规划结束,输出路径, 否则把当前点bestnode的四个相邻点投入OPEN列表,进行步骤3。 步骤6:保存并输出CLOSED列表中的路径节点。 这里我们主要对A木算法流程中的步骤5进行改进。从经典的胁算法流程可 以看出在步骤5中的当前节点四个相邻节点处理上存在缺陷。这个计算会重复计 算那些已经走过的节点,也就是在CLOSED列表中存在的节点,这样会导致在搜 获路径时出现路径的重复行走,浪费时间,针对这种情况我们对步骤5进行了下 面的改进。 改进的步骤5:判断当前点bestnode是否为目标点,若是,则规划结束, 输出路径;否则把当前点bestnode的四个相邻点投入OPEN列表,如果这些相邻 节点不属于OPEN表也不属于CLOSE表,将该结点放人OPEN表,并根据结点f值 对OPEN表进行排序,进行步骤3:如果这些节点属于CLosE表,略过不处理, 进行步骤3。 经过改进以后,一些重复行走过的点被剔除,提高了算法的执行效率,避免 了行走过程中的迂回行走现象。

4.2基于A音算法改进的全局寻路
4.2.1估价函数的选取

A木算法作为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些 策略设计的问题中。在此算法中,一个经过仔细设计的启发函数,往往在很快的 时间内就可得到一个搜索路径的最优解。 在栅格地图中设定一个起点和一个终点,采用A木搜索算法避开障碍物,找
32

基于超声波定位的机器人路径规划

N-一条安全的路径。给机器人一个起点栅格,当前栅格周围有四个栅格可以行走, 也就是机器人有四个前进方向:左、右、前、后,如图4一l。

,,.

H’
友+

弋/
÷


/,L、

—在

图4-1机器人运动方向 四个相邻的栅格中,选取哪栅格个作为机器人行走的下一个节点就利用到了

我们提出的估价函数,纠的构建方法。具体选取方法如下:
在下图4-2中,我们假设图中的黑色方块为一个正中移动的机器人,此时它 的运动方向与Y轴平齐,也就是朝着前方运动。此时在它周围有四个可以行走的 栅格,经过路径长度的计算后发现机器人向前方栅格行走和向右方栅格行走到达 目标点的路径长度代价是一样的。由于此时机器人此时的方位为90度,如果朝 前行走,机器人方位与将要行走方向的夹角为0度,机器人无需转向,继续行走 即可;但是如果朝右行走机器人方位与将要行走方向的夹角为90度,也就是机 器人需要原地右转90度才能行走,这大大等价了机器人行走的时间和难度。所 以综上所示,可以选择向前行走。







-_lI

L^
,r们





图4-2栅格选取

基于超声波定位的机器人路径规划

4.2.2全局寻路算法流程

要完成A术搜索算法,首先要设计一个函数,在这个函数中实现了全局寻路 路径的具体算法,设计程序流程图如下:



图4-3全局寻路的具体流程图 其中图4-3中相第四步相邻点处理主要是处理当前栅格周围四个栅格的处 理,具体处理方法如下:

U如果该栅格不可通过或者已经在close列表中,略过它。反之如下。 ∽如果该栅格不在open列表中,把它添加进去。把当前栅格作为这一格的父节
点。更新当前栅格的gCn)和h白夕的值。

U如果它已经在open列表中,用当前g

Cn)值为参考检查新的路径是否更好。

更低的gCn)值意味着更好的路径。如果是这样,就把这一格的父节点改成当前

格,并且重新计算这一格的g向)和厅例值,具体流程图如下:

基f超声波定位的机器人路径规划









图4-4相邻点处理的具体流程图

4.3本章小结
本章首先简单的介绍了经典A牢算法的定义和实现的步骤。在考虑了实际情 况下,对经典的胁算法采取了两点改进。第一将曼哈顿法基础上加入了机器人 转向问题,选取了合适的估价函数,设计了路径搜索算法的仿真程序设计步骤; 第二在流程处理上提出了走过的节点的处理方法,节省了搜索时间,避免了栅格

的重复行走。

35

基于超声波定位的机器人路径规划

5超声波定位实验与路径规划仿真
在利用超声波定位系统测得机器人位置后,可以让机器人遍历室内环境构建 地图,地图建立以后可以实现机器人的路径规划。本章是在前面章节完成的基础 E,利用超声波系统采取数据,完成定位计算;用Visual studi02005仿真室内 环境地图的建立和在已知地图基础上的机器人全局路径规划。由于本课题的受控 对象MT—R机器人,可以当做PC机(一台电脑)来用,所以本课题的超声波定位 技术和地图仿真,以及路径规划都在MT—R机器人上完成。

5.1超声波网络定位系统实验
超声波接收网络是由多个安装在室内天花板上的超声波接收节点按照等间 隔距离组成的,其节点间距在很大程度上影响定位精度。室内面积和节点到地面

的垂直距离一定的条件下,网络节点越密集,定位精度越高,但是相应的成本也
会越高。 本论文中选取房间的面积为2.5×3m2,每个超声波接收接收器之间的距离 为0.5米,所采用的超声波发射器的发射角度为800,在选取的实验空间内,天 花板上的超声波发射器共有42个。(如表5-1) 表5-1定位网络配置
实验房间面积
(m 2)
25×3

接收器之间的 距离(小)
O.5

地面到天花板
的距离(m) 2/2.5

波发射器发射 角度(O)
80


接收器的数量
(个)
42

超声波接收器按照一定的间距固定在铁架子上(如图5-1a),然后将悬挂在 天花板上,构成超声波网络定位系统(如图5一l b)。

(a)

(b)

图5-1超声波网络定位系统

基于超声波定位的机器人路行规划

在实验过程中,我们选取超声波发射器到天花板上的超声波接收器之间的距 离H分别为2米和2.5米,对每个超声波接收节点进行编号,主控节点的编号为 0l。由于超声波接受器是事先安装在天花板上的,所以可以预先测得超声波接受 器的坐标。首先控制中心发出启动命令FFH
AAH

01,主控节点和超声波接收器

接收到启动命令码后开始工作:主控节点向在移动机器人上的RF接受器发射RF 信号启动移动机器人身上的超声波发射器发射超声波(参数为第三个字节0l, 既主控节点的编号)。对于超声波接收节点第三个字节参数无效,接收到第二个 字节时,超声波接收器内的定时器启动。超声波接收器接收到超声波后,计时器 停止计时,这时要取出所有计时器内的数据。由于超声波发射器的发射角度为 80度,必然有一部分超声波接收器接收不到超声波,所以其内的定时器没有数 据,这一部分数据不需要传给控制中心。当取回数据以后,从这些数据中任取3 个数据,应用三边测量法就可以计算出超声波发射器的位置。取遍所有的定时器 有效数据进行计算,然后计算平均值,实验结果如表5—2所示。 表5-2超声波定位结果
移动机器人实际位置(米)
H=2 (1.0,1.O) (1.0,1.5) (2.0,1.0) H=2.5 (1.0,1.O) (1.0,1.5) (2.0,1.0))

移动机器人的测量位置(米)
H=2 H=2.5

绝对误差
H=2
H=2.5

响应 速度

(1.0619,0.9437) (1.0303,1.5208) (2.0070,0.9159)

(1.0330,1.0289) (1.0631,1.5044)
6% 6% 103ms

(2.0575,0.9937) (2.0450,1.4644)

(2.0。1.5)

(2.0,1.5)

(2.0453,1.5046)

从上面的结果可以得出,真实的位置和测量值之间存在的绝对误差H力为6%。 因为本定位系统是应用于移动机器人的,考虑到机器人本身的大小,我们要求定 位误差为10cm,从实验结果分析这是符合要求的。

5.2基于DFS的栅格地图仿真
在第三章,我们提出了在未知环境下的室内环境地图的建立方法。在未知环 境下,先利用机器入自带的传感器得知房间的整体轮廓,然后将其栅格化,在这 个不知道障碍物位置的栅格地图上用深度优先算遍历所有可行区域的,找出障碍 物的具体位置。深度优先算法的具体流程图如下图所示:

37

基于超声波定位的机器人路径规划

图5—2深度优先算法流程图 我们用Visual
Studio

2005仿真深度优先全局遍历室内环境建立地图。如

下图5—3所示,在一个不知道障碍物在哪的室内环境下,先建立一个环境轮廓, 将其划分为20*20的栅格,周围为墙壁,墙壁内哪个栅格是障碍物栅格还是自由 栅格是不知道的。然后,给机器人设定一个起始点和一个不可到达的终点,这个 终点设定在墙壁上。给机器人设定不可到达的终点的目的是让机器人在没有遍历 完所有的可行区域时是不能停止搜索的。最终机器人会搜完所有的自由栅格,并 将障碍物栅格标出。 DFS遍历不需要人工干预,非常适合于机器人的非实时寻路。程序中实现DFS 算法的函数为DFS—Search,该函数是CAstarWindowView类的成员函数,程序采用 递归调的方式实现,其中传入参数row,c01分别代表遍历入口点栅格坐标。 机器人用深度优先算法探索从起点到终点的所有可行路径,这样就可以搜索 出所有的障碍物并在地图上进行标记。具体的仿真过程如下图5-3所示,设定好 机器人的起点和终点后,点击图中的确定,就可以让机器人从起始点开始搜索所 有的到终点的路径,同时障碍物的位置也标记了出来,如图5-4所示。

基于超声波定位的机器人路径规划

■●一一●●■一■●●●■一一●一一●● ● ● ■ 一 ● ● ● ■




终氨昌 终愚‘■
一 一 ■ ● ● 一 一

■ ●
一 ●






量一起点一
一 一


一 一

■—一■■一—■一童■■朋■●一—一■

图5-3深度优先算法



图5—4深度优先算法结果 从仿真的结果图5-4看出,利用深度优先算法来实现室内环境的遍历绘制出 室内环境地图是可行的,机器人在搜索可行路径的同时将障碍物都标记了出来。
5-3

A★改进算法全局路径规划仿真
第三章通过栅格法和DFS全局遍历结合,为室内环境建立了栅格地图。在此

基础上采用第四章A木改进的搜索算法完成机器人的全局静态路径规划仿真。

为了方便操作,程序中并没有显示设置估价函数f(n),程序中为每个栅格
设定两个参数h_value和g_value分别代表当前栅格到目标栅格的代价和起始栅 格到当前栅格的代价。在具体的代码中,类Rect是栅格类,代表地图中的一个 个单位面积的栅格,类成员变量h_value和g_value是响应的估价值,当相应栅 格被加入openl i st时,栅格相应的h—value和g_value分别代表当前栅格到目 标栅格的代价和起始栅格到当前栅格的代价。
39

堆于超声波定位的机器人路径规划

L JasS

Itect


publiC: int map—X: int map—Y: int int Rect*pre:

h—value://当前栅格到目标栅格的代价 g_value://起始栅格到当前栅格的代价

)://栅格类 在选取第三章改进的估价函数f(n)后,就可以进行相应的A术算法仿真设计, 本程序采用面向对象的方式,建立相应的搜索器类AStart,其中Find()函数 为AStart函数的搜索函数,open—list开放列表存放所有已探知的但未搜索过 点的优先队列。close—list关闭列表存放搜索过的点的数组,提取最优路径时
有用。

仿真中把机器人设为一个栅格的大小,室内地图选择栅格的大小为IcmX lcm,地图的大小为20cmX20cm,用Visual Sdudi02005仿真划分后的移动机器 人工作空间如图5-5所示。

一一■一一●■●■■●■●●■■■●一■ ■ 一 ●





自由栅格∥暑

一 一■一一● ■■ ■ 一一 ●一一一■■ ■6口}■ ■一 一 ●≥窜息+● ■■ ■ ■一■ ■ 一■ 一一 一 一 一一■ 一 一■ 一 ■■一 ■ 一 ■■ 一 ●■■ 一 一 ■■ 一—●■——一一 ●■一一一一 ■——、—一、▲..

■起点一■■●一■■一

霎翟|.

■舞.

■ ■ ● ■ ■ ■■■■一一一■●■一●一一一■■一■■

……~ 暑霞;黝.J

■……■■●一■

● 一■ ■ 一 ■ ■●一一■■一■一一■一一 ■ ■ 一 ■ ■ 一 ■一●一 ■ ■ ● 一■■一 ■ 一 ■ ■ ■■一 ■一“。■ ■一■ ■■ ● 一 ■●● ●一 ■ ●一■ 一一 ■■■■■■■■ 一一 一 一一一 一一 一 一 ■ ■ ■一 ■ ■一■■■一一一羹 ■一 ■■■■奠一■■■■j 一 ■■■■■ ■■ 一 一

¨■■一

■ ■ ■ ■● 一 ■ 一●■ ■ ■一 ■ ■ ■ 一■■●■一■●■■■■一

一■

图5—5栅格化地图

图5—6搜索路径

在仿真地图中,我们给机器人设定一个起点和一个终点,如图5-5中所示,
则经过A木搜索算法以后,机器人可以找到一条从起点到终点的路径,如图5—6 所示。当起点到终点路径不可到达时,仿真中给出提示信息,如图5—7所示。

基于超声波定位的机器人路径规划

●■■●■■一一●一一一一一一一一■ ■ 一 一 ● 一 ■ 一 ●■■一 ●■ 一一 ■ 一■■■■一 一一 一一 ■ ■ ●一 一 ● 一一 ● ■■ ■■ ■ 一一 一 一■ ■ 一一 ■ ■■ ■ 一一 ● ● ■ ■ 一 ●一一●■一 一 一一 一 ●●■一■ ■一 一 一■■●● 一 ■■■一一一●■■■一一一一■一●■

图5-7目标点不可到达 在第四章我们也说过,经典的A木算法可以找到较优解,而可能不是最优解。 这种情况是存在的,在5—8(a)中设定一个起点和终点,终点是可到达的,经 过A木算法的到从起点到终点的路径如5-8(b)所示。
啊 帽

_N鲡|INNRNNINNiNNI|
■■■一■■■

I●

瞳 囊 }一
:一

一■明■一一


曩 啊 啊 ■
一 一■

● 一 ● ● ■ 一 ■ 一 ● 一 ■

I暑f

■■■■■■■■ 翻■ ■■绷■ ■一

~∽

■ 一 ■ ■■ ■■ ■一■●一■■■

(b)

最优路径

(c)

图5-8路径对比图 我们可以看出,在5—8图(b)中路径转弯较大,这会增加机器人的行走难度 和路径行走时间,因为机器人转弯也是需要时间的。我们采用第四章设计的估价

4l

基干超声波定位的机器人路径规划

函数f(n)代替单纯的以路径长度为标准的评估函数。新的评估函数f(FI)考 虑了机器人的转弯代价,所以可以找到一条比5—8(b)更优的路径,如图5—8 所示的另一条路径。从5—8(b)和5—8(C)的结果对比可以看出,虽然两者行 走路径长度一样,但是5—8(b)中明显的转弯次数增多,5—8(C)中路径较为 平滑,因此可以证明我们设计的估价函数是可行有效的。
5.4

MT-R机器人实验
A术算法仿真得到的安全路径最终将应用于机器人,这里我们的实体受控对象

采用MT—R机器人,下面将详细的介绍路径仿真结果应用于实体机器人的可行 性。 一、MT-R机器人跟随实验 MT—R机器人两个主动轮安装在底箱前部,差速驱动。试验中需要机器人转 向90度,设一个地板砖的大小为一个栅格,即机器人的一个步长。首先用VC 设计一个界面,测出移动机器人行走一个步长和旋转90度时所需要的时间。测 试界面如下图所示:

前进持续时问

后退持续时间 左转持续时间 右转持续时间

~瑚~一撇||
∞.|8一∞二∞}| 垂毫~一猢一

左轮速度型[:j蚕口
右轮速度
|0.2

一一一一

t000 2000 1000
1000

颈定义路径
l行号

囹童目宙蠲国匿麴圈髓囱一 囹重日雹囫日幽衄髓蕊一~
3 4

左轮速度

右轮速度j持续时间

0 150000



0 0 0

165000

200000

210000 165000 110000 10.

5 6


0 150000 0 100000 0 100000

;=;,、.……。………,、

—0

3600
、,

图5-9测试界面

42

基于超声波定位的机器入路径规划

经过测试,可以得出以下测试结果: 前进时:左轮速度------0.2m/s;

右轮速度一0.25m/s;
右轮速度一-0.3m/s; 右轮速度------0.2m/s;

时间:1600ms:

左转90度:左轮速度------0.2m/s;

时间:400ms: 时间:400ms;

右转90度:左轮速度…0.3m/s;

完成机器人前进和转弯的单步测试后,我们设计一个机器人的连贯动作,看 机器人能否实现连续的运动。由于机器人在前进和转弯时的左右轮速度是设定好 的,所以我们可以把机器人的连续运动命令简化为机器人运动的时间表。机器人 读取这些时间,就可以实现连续的运动。我们设置一个3*3的栅格,中间黑色栅 格为障碍物,S为起始栅格,E为终点栅格,假设机器人为一个点,让机器人从 起始点开始安全绕过障碍物区。利用A木算法的到的安全路径为栅格格6,3,

0,l,2,示意图如5-10,将这些栅格转化为机器人可以读取的时间文件,转化
关系如表5-3: 表5-3
动作
时间ms

6前进
1600

3前进
1600

0前进
1600

右转
400

1前进
1600

2前进
1600

将表5-3转化的时间存储为机器人可读的文件,然后再机器人运动的时候
读取这些文件,就可以实现机器人连续运动和跟随。MT—R机器人按照上述方法

安全行走路径如图5—11所示。



2-E+

●仉 ●
3.

1..

_蛔冒围
)√


S‘?6} 7— 8.j

图5-10路径示意图

43

基于超声波定位的机器人路径规划

图5—1l机器人连续动作图 二、全局路径规划实验 在进行以MT—R机器人为实验对象的机器人全局路径规划之前,我们首先要 利用前面介绍的A:I:搜索算法来规划出机器人从起始点到目标点的最优路径,然 后再让MT—R机器人进行实验。图5—12中,在栅格地图上设定机器人起点第4 个栅格和终点第45个栅格,栅格23,24,33,34,43,44为障碍物栅格,应用 A术算法得出最优路径。这个最优路径为栅格4,14,15,25,35,45,55,54。

基于超声波定位的机器人路径规划




;{

:H

i¨

J‘l H



_J

,P1 —

2n

!-

+。i:

。●‘

’:』

!j

一r●

?,一 ’jl

:jH

:{0

4i

{{

;』

l蔓

j?f

毒-

{J{

;0

烈j

5】

五2

五‘{

j;



-_ ”】f

1h



59

i,i}

;,:

,■

+'::

f;{

n‘

÷;“

h0

_《l

_】

:’2

7{

--

。1

了;}



7R

?0

珂《}

蚪j

H:

“’{

辩4

H5

M÷'

H了

8H

R9

何{

|{l

0=

0‘{

~{

~-。l

铷t

勺_

甜H

】tJ(}



45

55

左转
900

54

前进
时间
mS

前进
1600

前进
1600

1600

1600

400

1600

400

1600

1600

1600

400

基十超声波定位的机器人路径规划

艘沁豳 溅~鹧龋f嗣捌

摭爨“攘搠豢鹬。
5一13全局路径规划实验 图5—13中的(a)机器人位于初始S(黄色),图(b)移动机器人向着障碍物前 进,图(c)中机器人以90度绕过障碍物板凳,然后按照仿真所得的最优路径安全 到达设定的终点(蓝色)。

5.5本章小结
本章应用超声波定位系统采集了一些实验数据,利用三边测量法计算出了定 位信息,分析了定位的准确性;应用仿真,实现在未知环境的栅格地图中用深度

优先(DFS)全局遍历得到障碍物,绘制地图;在斛路径搜索算法仿真平台上,
验证了新提出的估价函数的可行性,并将未改进的和改进的做了仿真对比。最后 用MT—R机器人完成了机器人的全局路径规划实验,证明了本课题的研究成果可 以应用于实际的机器人。

基于超声波定位的机器人路径规划

6总结与展望
自主移动机器人在室内环境的广泛应用离不开定位系统,室内环境信息和路 径规划。定位系统可以让机器人知道自己在哪里;室内环境信息,可以让机器建 立对工作环境的印象,明确障碍物的位置,为路径规划提供信息前提;路径规划 系统可以是机器人在运动过程中避开障碍物,找到安全最好的路径完成任务。本 课题在综合各种技术的基础上,完成了定位系统的设计和实现,未知环境的地图 建立和路径规划。主要工作分为四大块: 一、在收集和阅读大量国内外文献的基础上,完成了超声波定位系统的设计 与实现,通过三边测量算法计算出机器人的位姿,让机器人知道自己目前所处的 位置,为机器人的环境地图建立和路径规划提供了必要的基础。 二、本文首先针对室内移动机器人,提出了一种机器人工作环境地图的测绘 方法,该方法基于栅格地图表示环境,通过深度优先遍历室内的所有可行区域对 机器人探测环境的路线进行导航。仿真表明基于栅格表示环境,用深度优先算法 遍历建立环境地图的可行性。 三、课题着重研究了静态环境下的机器人避障问题,由于本课题的应用环境 为室内实验室,环境简单,选择了简单易行的A术搜索算法,并对经典的A木算法 进行了改进,完成了算法中新的估价函数的选取,避免了路径重复搜索问题,最 后用仿真证明了改进的正确性。 四、应用构建的超声波定位系统平台,采集试验数据,利用三边定位法测得 物体的坐标;利用自行设计的仿真验证本课题提出的地图构建法和改进的路径搜 索算法的可行性。最后利用婀一R机器人实验平台实现机器人的全局路径规划, 取得了良好的效果。 本课题将超声波定位系统,环境地图的构建和机器人的路径规划综合运用, 形成了一个完整的应用系统,但是仍旧有许多不足之处: 一、课题研究的地图建立方法是针对室内机器人这一特殊对象的工作环境, 研究的是在封闭环境下的地图绘制和全局遍历方法,其不足之处主要是应用范围 比较窄,不具有更广泛的通用性。而且,考虑的外界因素过少,没有考虑存在动 态障碍物时该怎么解决地图绘制问题。 二、课题主要研究了环境信息都测得的情况下的静态路径规划,并没有考虑
47

基于超声波定位的机器人路径规划

在动态障碍物的情况下的路径规划。并且本课题的实验环境室内,环境简单,未 考虑在室外复杂环境下的路径规划问题。 随着移动机器人的广泛应用,会有更多的问题需要去探索研究。本课题可以 以后从以下几个方面进行进一步的研究: 一、由于本课题的很多实验都是在仿真平台上进行的,仿真环境是在Visual
studio

2005环境下开发的,可以在以后的研究中将本课题中的部分理论应用于

实际机器人。 二、本课题中通过传感器测量静态的障碍物,没有考虑动态障碍物的信息获 取,在以后的研究中可以通过机器人的视觉传感器对环境中的动态物进行探测得 到障碍物的三维信息,实现在动态环境下识别障碍物。 三、从路径规划算法来说,本课题考虑的是同全局的角度的路径规划,今后 的工作中可以扩展到基于部分环境己知的情况的规划或者动态的路径规划,同时 也可以考虑多个机器人的路径规划问题。

基于超声波定位的机器人路径规划

参考文献
【l】李磊,叶涛,谭民,陈细军.移动机器人技术研究现状与未来【J】.机器人,2002,24(5):457-480 【2】刘宝平,张红梅.移动机器人研究现状和未来发展的分析【J】.科技信息,2009,29:65. 【3】研究型智能机器人MT-R用户手册,2007. 【4】4 李群明,熊蓉,褚健.室内自主移动机器人定位方法研究综述【J】.机器人,2003,25(6):560.567

[5】郑静,张吉力,华泽钊,徐根林.室内超声波定位系统的构建与测试忉.上海理工大学学 报,2007,29(6):55 1.556. 【6】寇海洲,庄毅.无线传感器网络超声波定位算法的研究【J】.航空计算技术2008, 38{4}:125-128. [7】俞竹青,那须康雄.室内移动机器人超声波传感器导航网络分布研究[J】.传感器技 术,2003,22(11):12-15 [8】Nilsson NJ.A mobile
automaton:an application ofartificial intelligence

techniques【C】.Proe.

1st Int.Joint Conf.on Artificial Intelligence,Washington D.C.,1969:509--520.

[9】Nilsson N.J.A mobile

automation:an application ofartificial intelligence

techniq—ucs[D].in

Proc.First Znt.Joint Conf.Artificial.ZnteU,1969.

【10】彭艳.智能水下机器人全局及局部路径规划技术研究.【硕士学位论文】.哈尔滨工程大
学,2003.

【1l】王会丽.自动导向小车路径规划算法的研究及仿真.【硕士论文】.西安理工大学,2002.
【1 2】Bohlin,&Robot
Path

Planning.DoKTORSA、mANDL玳GAR-C地地MERS

TEKNISKA

HoGSKOLA,2002,(1 850):a11. [13】王艳平.移动机器人路径规划方法研究【J】.科学探讨科学应用技术与研究,电脑与电信, 2009,(1):6乒—68. 【14】曲道奎,杜振军,徐殿国,徐方.移动机器人路径规划方法研究,机器人[J]2008, 30(2):91-101,106. 【15】黎红.自主移动机器人路径规划中的主要方法【J】.中国电力教育,2010:814._81 6.

【16】Qussama

Khatib.Real-Time Obstacle Avoidance For maniPulators and Mobile

Robots【J】J.Proc of IEEE,1 994. [17】Kala.Rahul,Shukla.Anupam,Tiwaft.Ritu.Fusion ofprobabilistic A?flgofithm
inference system for robotic path planning.ARTIFICIALⅡ呵TELLIGENCE
and fuzzy

REVIEW,20 1 0,33(4):307.327 【18】Lozano-Pbre T.Z,Automatic planning
ofmanipulator transfer

movement【J】.IEEE

Trans.Syst.Man.Cybern,1 98 1,1 1:68 1-698.

49

基于超声波定位的机器人路径规划

【19】禹建丽,V.Kroumov,孙增忻,成久洋之.一种快速神经网络路径规划算法.机器人,ROBOT, 2001,23(3):201-205. 【20】Danica
Janglova.Nepal Networks in Mobile Robot Motion.International Journal of

Advanced Robotic Systems,Volume 1 Number l(2004),PP.1 5?22

【21】李少远,王景成等.智能控制【M],机械工业出版社,2008:156-167 【22】康乐俊,黎敏,阳建宏,刘剑,董云飞.基于超声波和TDOA的无线传感器网络高精度定位 方法【J】.微计算机信息,20 1 0,26(4):79.8 1 【23】闫鹰.自动导航小车超声波定位方法的研究.【硕士论文】.西安理工大学,2005.
【24】Minami.Masateru,Morikawa.Hiroyuki,Aoyama.Tomonori.Design
fully
and implementation of


distributed ultrasonic positioning

system.ELECTRONICS AND COMMUNICATIONS

IN JAPART 3 FUNDAMENTAL ELECTRONIC SCIENCE,2007,90(6):1 7—26

【25】Schweinzer.HF,Spitzer.GE

3D Ultrasonic Positioning

System诵Ⅱl High Accuracy for

Indoor Application.Key Engineering Materials,20 1 0,437:263—270.

【26】Yi.Soo?Yeong.Sensing-Global
Robot.正ICE Transactions
on

Ultrasonic System for Self-Localization of Mobile

Communication,2003,86(7):2 1 71-2 1 77.

【27】Qrussama

Khatib.Real-Trine Obstacle Avoidance For manipulators and Mobile ofIEEE,1994.

Robots[J】.Proe

【28】寇海洲.基于超声波的定位系统研究与实现【J】.数据通信,2008,3:49—51. 【29】孙明明.超声导航移动机器人关键技术的研究:[硕士学位论文】.浙江大学,2005.传感技 术学报,2010,23(3):348.350. 【30】宋玉梅.无线传感网络节点定位技术研究与实现:【硕士学位论文】.电子科技大学,2005. 【3 1】Zhou.H,Sakane.S.Sensor
Using


Planning for Mobile Robot Loealization--A Hierarchical Approach


Bayesian Network and

Particle Filter.IEEE Transactions

on

Robotics,

2008,22(2):48 1-487. 【32】Writtenberg.D,Ruppel.U.Ultrasonic system【J】.WOI也DCQ让一DORKING FARNHAM,2002:43-46. 【33】Panich.Surachai.Positon calculation
for mobile

THEN

robot谢m ultrasonic

s)rstem.Far East Journal

ofMathematical Sciences—FJMS,2010(46):15-22.

【34】俞竹青,那须康雄.超声网络导航中移动机器人的位置计算【J】.机器人应用技术与应 用,2002(3):36-39. 【35】任世军,黄德海.一种基于栅格扩展的机器人路径规划方法.哈尔滨工业大学学 报,2001,33(1):68.72 【36】雷艳敏,冯志彬.改进的势场栅格法在机器人路径规划中的应用【J】长春大学学报2009, 19(1):38-42. 【37]肖南峰编著.智能机器人【M】.广州:华南理工大学出版社,2007.158.

基于超声波定位的机器人路径规划

【38】徐邵敏.移动式机器人自主测绘环境地图的方法研究.【硕士学位论文】.北京工业大 学,2007. 【39】武传宇,沈卫平,胡旭东.未知环境中移动机器人基于行为的自主导航与环境构建【J】.机电 工程,2003,20(5)'1 15-117. 【40】迟健男,徐心和.移动机器人既时定位与地图创建问题研究【J】.机器人,2004,26(1):92.95. [41】Wofl.Denis F'Sukhatme.Gaurav S.Mobile
Robot Simultaneous Loeatization and Mapping in

Dynamic Enviroments.Automous Robots,2005,19(1):53—66.

[42】Hahnel.D,Triebel.心Burgard.W.Map Building诵tll Mobile Robots in Dynamie
Environments.IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND

AUToMATION,2003,2:1 557.

【43】陈花,张远平,林强.受限移动机器人构建地图的最优探测法明.计算机工程与设计,2009,
30(6):3823.3825.

【“】何慧娟.超声在移动机器人障碍物检测中的应用研究[J】.工业控制计算 机.2010,23(7):4l_42. 【45】祝尚臻,于宏涛,李丽霞.迷宫相器人硇回溯深度优先簧法应用【刀.高校理科研究:84.86. [46】Tian,L.A^宰Search Arithmetic
Based
on

Dynamic Coordinate in Assembly Path Plan.

COMPUTER INTEGRATED MANUFf~CTURING SYSTEMS-BEUING-.2002,8:316.319.

【47】朱运力.超声波定位系统的参数研究【J】.机电产品开发与创新,2006,19(2):128.130

51

基于超声波定位的机器人路径规划

致谢
值此论文完成之际,首先要向我的导师张磊老师致以衷心的感谢!张磊老师 为我提供了宝贵的学习机会,在学习与科研上经常与我进行交流并指导,在我三 年的研究生期间,无论是在学术理论学习、课题研究方面还是生活方面,我都得 到了张磊老师的悉心教诲!张磊老师是一位有着严谨的学术态度,一丝不苟的科 研工作精神、踏实的工作作风的严师,张磊老师这些优良的作风,都鞭策着我在 以后的工作中认真努力。张老师不仅在学业上给了我很大的帮助,而且教给了我 一种积极的人生态度和做人的准则。 本论文的完成也离不开的系了很多老师的指导和关怀。在此要感谢褚东升教 授,王建国教授、谢则晓教授、刘滨教授、李庆忠教授的指导和帮助,他们不仅 是学术上严格的老师,也是生活中和蔼的长辈。 本论文的顺利完成也离不开实验室很多同学的帮助,他们是师妹石绍丽,师 弟田阳以及同班同学的李坤,李艳丽等,在此一并感谢!和大家相处的三年快乐 时光,我会永远珍藏。特别感谢我的父母和家人,我能够顺利的完成学业,离不 开他们始终如一地无私的爱和关怀。在此,我向他们表示最深挚的感谢。 另外,各位审稿和答辩老师给我在完成论文中的建议也是对我学习的指导和 今后的工作是莫大的帮助

52

基于超声波定位的机器人路径规划

个人简历
1986年2月26日出生于山东省临沂费县。 2004年9月考入青岛理工大学工程学院自动化专业,2008年7月本科毕业并获 得工学学士学位。 2008年9月考入中国海洋大学工程学院控制理论与控制工程专业攻读硕士学位
卒久、 土—7


基于超声波定位的机器人路径规划

发表的学术论文

发表的学术论文 (1)基于超声波定位系统的机器人全局路径规划.计算机应用,2010.
(2)Robot
global path planning based
Oil

ultrasonic net location system.

2011年第三届IEEE计算机与网络技术国际会议

基于超声波定位的机器人路径规划
作者: 学位授予单位: 孙莹莹 中国海洋大学

本文读者也读过(10条) 1. 陆蔺 超声波三维定位与跟踪系统的设计与实现[学位论文]2010 2. 孙德华 RoBUT-Ⅰ机器人的研制及其视觉研究[学位论文]2010 3. 范志斌 基于图像局部不变性特征的机器人目标识别与定位[学位论文]2011 4. 王军柱 室内轮式机器人走行控制的研究[学位论文]2011 5. 刘玉东 室内环境下的机器人自主导航研究[学位论文]2011 6. 苑宝玉 超声波室内定位系统[学位论文]2010 7. 方兴.郑小林.彭承琳.侯文生.吴旭东.梁学领.Fang Xing.Zheng Xiaolin.Peng Chenglin.Hou Wensheng.Wu Xudong.Liang Xueling 消化道应用微磁囊定位系统抗地磁干扰的补偿方法[期刊论文]-生物医学工程学杂志 2008,25(6) 8. 梁欣 基于FPGA的OFDM水声通信系统设计与开发[学位论文]2011 9. 李艳丽 基于遗传算法的多足球机器人路径规划[学位论文]2011 10. 王志燕 基于DEA方法的环渤海地区机场效率研究[学位论文]2011

本文链接:http://d.wanfangdata.com.cn/Thesis_Y1927234.aspx


相关文章:
电子设计大赛—超声波定位系统
而设计研制箱涵排水疏通移动机器人的 自动控制系统,保证机器人在箱涵中自由排污...Ⅰ.3 本设计研究与实现方法超声波定位系统主要基于研究超声波的测距方法,然后...
超声波定位
系统由一个主测距器和若干个电子标签组 成,主测距器可放置于移动机器人本体上...目前, 比较流行的基于超声波室内定位的技术还有下面两种: 一种为将超声波与射频...
智能仪器完结-基于超声波定位原理的停车辅助系统
智能仪器完结-基于超声波定位原理的停车辅助系统_信息与通信_工程科技_专业资料。...1.2 国内应用现状近年来,由于导航系统、工业机器人的自动测距、机械加工自动化...
基于RFID的室内超声波定位系统
基于RFID的室内超声波定位系统_电脑基础知识_IT/计算机_专业资料。龙源期刊网 ...【关键词】 RFID 超声波测距 二维坐标 单片机 1 引言 小到室内机器人的跟踪...
【最新修订版】基于CDMA室内超声波三维定位系统设计毕...
如井下人员的精确定位、医疗监护、远动捕获以及室内无 人机和机器人的航迹规划等...从 Bat 标签到传感器,如果超声脉冲是经过反射,而不是 沿直线路径传输, 将产生...
机器人定位技术
个问题是其导航系统总的定位及其跟踪问题,第二、三个是导航 系统的路径规划问题...摄像头、激光雷达 等和基于机器人外部所用的传感器,如摄像头、激光雷达,超声波...
基于超声波的盲人导航系统设计文献综述(毕设)
3.2 超声波的定位 定位是确定移动机器人在二维工作环境中相对于全局坐标的位置...对定位技术的基本思路都是基于测量值的积累,因而无法避免时间漂移问题,随着 路径...
超声波的移动机器人导航的设计原理
超声波的移动机器人导航的设计原理时间:2012-05-14 13:07:00 来源: 作者: 1 引言 在项目开发中采用从英国进口的 SRF05 超声波传感器,它的回波反馈与测距方式...
基于超声波的液位测距系统设计
基于超声波的液位测距系统设计 隐藏>> 摘 要 本文是利用超声波测距的原理而设计...实现对工业生产线上的物料传送定位、电梯的运行监测、移 动机器人的测距定位等...
基于RFID定位技术的AGV机器人网络路线引导方法
物流系统等,同时对 AGV 机器人路径规划、群体合作、智能调度提出了一些新的...目前国内外对 AGV 定位方法的研 究主要包括:视觉定位、超声波定位、红外定位等...
更多相关标签: