全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 西华i 型足球机器人系统的路径规划研究 机械电子工程专业 研究生张华指导教师王进戈 随着科学技术的进步以及机器人学的发展,智能机器人已成为计算机应用和 人工智能发展的一个主要方向。移动机器人的研究和开发近年来受到了人们的高 度重视。机器人足球比赛是近几年国际上开展起来的一种高科技对抗活动,由于 它集高新技术、娱乐、比赛于一体,所以引起了社会的广泛关注和极大兴趣。而 路径规划是移动机器人系统中的一个重要内容,因为他的好坏直接影响到机器人 完成任务的质量。比赛中要求机器人在运动过程中能根据周围环境的变化而自主 地采取相应措施的能力也越来越强。因而,路经规划作为机器人! 智能”的因素 就显得尤为重要,成为机器人研究领路的一个热点。 移动机器人的路径规划是一个很复杂的问题,不仅要寻求一条无碰撞的最短 路径,而且还要求该路径尽可能平滑并满足一定的安全性。本论文以f i r a 半自主 型机器人足球系统为研究平台,介绍了足球机器人系统的体系结构及相关技术, 其中重点讨论了决策子系统设计,分析路径规划在整个系统中的重要性,并详细 论述了足球机器人系统环境模型和平台避碰控制特点。在以上工作的基础上分析 了目前各种路径规划方法优缺点的基础上,讨论它们在足球机器人系统中的应用 可行性。最后选择遗传算法来解决静态和动态环境下移动机器入的路径规划问 题。 本文主要针对当前路径规划中存在的诸多问题,提出了一种基于遗传神经网 络的机器人避开多随机障碍物的路径规划方法。该方法首先提出障碍物环境的神 经网络模型并利用该模型建立机器人动态避碰路径与神经网络输入输出的关 系,然后用遗传算法对神经网络的参数进行训练,得到比较满意的权值和阈值的 输出。这种方法融合了遗传算法和神经网络方法的优点,先利用遗传算法的全局 捅要 搜索,找到一个局部范围,然后由神经网络算法实现局部的搜索,这样可以很好 的避免神经网络搜索易陷入局部最小的缺点,是一种比较高效快速的路径搜索算 法。 最后用m a t l a b 编写仿真程序。仿真结果表明,该算法能够成功地在各种 复杂程度不同的环境里规划出一条近似最优的路径,证明了算法的有效性。 关键词机器人足球;决策子系统;路经规划:神经网络:遗传算法 i i 摘要 i 冱s e a r c ho fr o b o ts o c c e rs y s t e m s p a t hp l a n n i n gf o rx i h u ait y p e s p e c i a l t y :m e c h a n i c a le l e c t r o n i c se n g i n e e r i n g p o s t g r a d u a t e :z h a n gh u as u p e r v i s o r :p m f w a n gj i n g e a st h ed e v e l o p m e n to fs c i e n c ea n dr o b o t i c s ,i n t e l l i g e n tr o b o tc o m e st ob e t h em a i nd i r e c t i o no f c o m p u t e ra p p l i c a t i o n a n da r t i f i c i a l i n t e l l i g e n c e d e v e l o p m e n t p e o p l ed e v o t em u c ha t t e n t i o nt ot h es t u d yo fm o b i l er o b o t sn o w s o c c e rr o b o tc o m p e t i t i o ni sa h i g h - t e c ha n t a g o n i s ma c t i v i t yw h i c hh o l di n i n t e r n a t i o n a ln a t i o n s p a t hp l a n n i n gi sa ni m p o r t a n ta s p e c to fm o b i l er o b o t s y s t e m ,a si t sg o o do rn o td i r e c t l yi m p a i rt h eq u a l i t yo fa c c o m p l i s h i n gr o b o t s m i s s i o n i nt h ec o m p e t i t i o n ,r o b o t sc a p a c i t yt ot a k e a p p r o p r i a t em e a s u r e s a c c o r d i n gt om o v e m e n tc i r c u m s t a n c e sm u s tb em o r es t r o n g e r t h e r e f o r e ,p a t h p l a n n i n g ,a sai n t e l l i g e n tf a c t o ro fr o b o t ,p r o v e st ob eah o ts p o to fr o b o t r e s e a r c hf i e l d p a t hp l a n n i n gf o rm o b i l er o b o t si sac o m p l e xp r o b l e mt h a tn o to n l y g u a r a n t e e s ac o l l i s i o n f l e ep a t hw i t hm i n i m u mt r a v e l i n gd i s t a n c e b u ta l s o r e q u i r e s s m o o t h n e s sa n dc l e a r a n c e s t h i sd i s s e r t a t i o n p r e s e n t s ag e n e t i c a l g o r i t h m sa p p r o a c hf o rs o l v i n gt h ep a t h p l a n n i n gp r o b l e mi ns t a t i ca n dd y n a m i c m o b i l er o b o te n v i r o n m e n t s a c c o r d i n g t ot h ec h a r a c t e r i s t i co f p a t hp l a n n i n gp r o b l e m ,e v e r y c o m p o n e n to ft h ea l g o r i t h m sa l ea n a l y z e dc a r e f u l l y ,i n c l u d i n ge n v i r o n m e n t r e p r e s e n t a t i o n , c h r o m o s o m er e p r e s e n t a t i o n ,p a t h e v a l u a t i o n , g e n e t i c o p e r a t o r sd e s i g n a n dg ap a r a m e t e r ss e l e c t i o n an e wh y b r i d g e n e t i c a l g o r i t h mi sp r e s e n t e db yu s eo fg e n e t i ca l g o r i t h mt oo p t i m i z et h ev a l i dp a t h 摘要 g e n e r a t e db yn u m e r i c a lp o t e n t i a lm e t h o d u s i n gt h ec o n c e p to fa u t oc o n t r o l ,a m e t h o da d o p t i n gl o c a t i o nf o e d b a c k ,d i r e c t i o np r e d i c t i v ea n dp a t hr e p l a n n i n gi s u s e dt od e a lw i t ht h ep r o b l e mi nd y n a m i ce n v i r o n m e n t s t h i sa l g o r i t h mh a st ob et e s t e da g a i n s tv a r i e t ys t a t i co rd y n a m i ce n v i r o n m e n t s an e wa p p r o a c ho fp a t hp l a n n i n gb yc o m b i n i n gg e n e t i c a l g o r i t h m ,n e u r a l n e t w o r ki s p r e s e n t e d , t oa v o i dt h es h o r t c o m i n gt h a tt h er e s u l to ft h en e u r a ln e t w o r k m a yb et h el o c a lm i n i m u m t h eg e n e t i ca l g o r i t h mi su s e dt os e a r c hh o l i s t i c a l l yf o rt h e i n i t i a ln e t w o r k w e i g h t s 1 1 1 en e u r a ln e t w o r k i su s e dt os e a r c h p a r t l y f o rt h e o p t i m i z a t i o no u t p u tw h i c hi sd i s t i l l e dt h er u l e st op l a nt h ep a t h t h es i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mi sa b l et of i n dab e t t e r p a t hr a p i d l yi na n yc o m p l e xe n v i r o n m e n to n l yi ft h ep a t he x i s t sa n dv a l i d a t e d t h ee f f e c t i v e n e s so ft h ep r o p o s e da p p r o a c h k e y w o r d s : r o b o ts o c c e r , m o d e l i n g ,p a t hp l a n n i n g ,n n ( n e u r a ln e t w o r k ) , g a ( g e n e t i ca l g o r i t h m s ) v 两华大学硕十学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。除了文中特别加以标注和致谢的地方外,论文不包含其他人已 经发表或撰写过的研究成果,也不包含为获得西华大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同学对本研究所作的任何贡献均 已在论文中作了明确地说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的,论文 成果归西华大学所有,特此声明。 作者签名:方乐华 翩繇碱 扣7 年t 月,日 f 劢p 年广月f 口日 f 两华人学硕十学位论文 1 1 课题来源 1 引言 本课题是:四川省应用基础研究资助项目,项目编号:0 3 2 2 1 2 9 四川省重点学科资助项目,项目编号:z0 2 2 4 5 。 机器人是人类二十世纪最伟大的发明。移动机器人的研究是近年来发展迅 猛的一个领域,已经越来越广泛的应用于工业、农业、军事、教育等人类社会的 各个方面。足球机器人给机器人技术研究提供了一个良好平台,它综合了多学科 的发展成果,集人工智能、智能控制、信息处理、图像处理、检测与转换等专业 技术为一体,跨计算机、自动控制、机械、电子等多学科,代表高技术的发展前 沿,成为当前智能机器人研究的热点之一。它既是一个典型的智能机器人系统, 又为研究发展多智能体系统、多机器人之间的合作与对抗提供了生动的研究模 型。 目前的足球机器人比赛类型可分为半自主式、全自主式、类入型以及足球机 器人仿真程序比赛。 机器人是在没有人干预、无需对环境作任何规定和改变的条件下,有目的地 移动和完成相应的任务。在足球机器人系统中,多个机器人活动在一个实时、噪 声以及对抗性的复杂环境下,通过协作、配合完成进球的共同目标。 1 2 课题背景 1 2 1 机器人决策子系统简介 足球机器人系统由视觉子系统、决策子系统、通信子系统和小车子系统四部 分组成。只有当四个子系统紧密配合、快速准确地工作时,我们的西华队才能取 得一场又一场比赛的胜利。决策子系统相当于机器人的大脑,在整个系统中起着 重要的作用。 比赛时,视觉子系统每4 0 m s 左右将球场上各机器人的位姿和球的信息传入 西华_ 人学硕十学位论文 计算机,决策子系统根据传入的视觉信息分析球场上的情况,做出相应的决策, 转化为每个机器人的左右轮速,通过通信予系统发送给每个机器人,去完成比赛 任务:决策软件负责通过位姿判断场地态势产生策略,并确定本方机器人的速度 设定,写到主机的串口。这个部分很重要的一个要求就是要保证实时性,因为足 球机器人系统的机器人和球的运动速度非常快,场上信息瞬间万变,而且前一个 部分的工作已经有一定的滞后,就要求决策软件必须尽快完成分析决策过程并发 送机器人速度设定。而要对场上的机器人快速的做出正确的决策控制,使之能够 在场上安全最优的到达目的地执行任务,就必须对机器人的路径做出最优化的规 划。由此可见,机器人路径规划是智能机器人的一个重要研究课题。机器人足球 系统环境是一个具有动态性、不确定性、实时性的环境,在这样一个具有高度实 时性和竞争性平台上研究路径规划也是一个很有挑战性的课题。目前用于路径规 划的方法很多,如人工势场法,栅格法、可视图法及各种人工智能方法如遗传算 法,神经网络等等。但这些方法在高度动态性和实时性环境中的研究还不太完善, 有待进步改进。 策略决策系统结构如图卜l 所示。 口匿圃 f i g t u e 1 1 t h es t m c 嘛o f r o b o ts w a t e g ys d 搭”t e m 图1 - 1 机器人决策予系统结构 2 两华人导! 硕十学位论文 在我们的足球机器人系统中,决策类是受视觉调用的。当决策子系统收到视 觉输入信息后,对其进行预处理,根据球和本方机器人的位置对场上攻防形势进 行分析,并将所作的决策分解为各个任务这是决策的第一层。根据分解完的 任务从队形库中为本方机器人确定一个队形这是决策的第二层。根据队形所 需的角色以及我方机器人的位置,将每个角色分配给具体的机器人这是决策 的第三层。之后通过机器人管理函数将左右轮速发送给对应的每个机器人。 1 2 2 足球机器 路径规划研究内客 所谓的路径规划就是在一定的环境中给定初始位置和目标位置,按一定的策 略使运动物体从初始位置无碰撞地到达目标位置,并满足一些约束条件。路径规 划技术的应用非常广泛,不管是关节型机器人还是移动机器人,凡是有机器人应 用的地方都有机器人路径规划技术应用的必要性或者是必需性。本文以移动机器 人的路径规划为重点开展研究工作。 由移动机器人的发展可知,移动机器人中最主要的一个研究方向就是路径规 划。因为路径规划结果的好坏直接影响机器人完成任务的质量,所以很多研究者 致力于研究开发新的、高效的机器人路径规划的方法。路径规划也是足球机器人 系统研究中的一个重要课题,其重要性主要体现在: ( 1 ) 机器人车体造价比较高,而机器人足球比赛是一个动态竞技项目,机器人 如果没有避障行为,则会多次相撞,损坏车体; ( 2 ) 好的路径规划方法可以使机器人以最短时间到达目的地,完成相应动作, 取得较好成绩: ( 3 ) 将各种算法尤其是各种智能算法放在路径规划这样一个问题中进行研究 和检验,可以促进相关学科的发展,促进人工智能的发展: ( 4 ) 足球机器人系统场上的环境是时刻变化的,其路径规划属于一种作业环境 未知且动态的路径规划及控制,在这样的平台上研究的路径规划方法可以应用到 其他机器人应用环境,完成有实用意义的任务。 如何在这样一个环境中规划出每个机器人的运动路线,让每个队员很有策略 地行动、配合,是一个研究移动机器人路径规划的很好平台,而且在这样一个具 有高度实时性和竞争性平台上研究路径规划也是个很有挑战性和竞争性平台上 研究路径规划也是个很有挑战性的课题。 机器人路径规划是个研究时间比较长的课题,随着科技的发展和人类探索领 域的不断拓宽,对机器人的要求也不断地提高。现在动态环境和未知环境中的机 3 两华大学硕十学位论文 器人路径规划、高度实时性环境中的机器人路径规划及智能方法在路径规划中的 要求越来越多,对研究者的任务要求也越来越高,研究难度不断提高。足球机器 入系统环境是一个很典型的具有动态性、不确定性、实时性的环境,这样的环境 正好符合当前机器人路径规划的研究方向。这也是本文选择足球机器人路径规划 问题的意义所在。 1 3 课题的研究意义 本课题根据我校四川省应用基础研究资助项目和四川省重点学科资助项目 的研究,提出了足球机器人路径规划方法研究,对移动机器人的研究与开发具有 重要意义。 由足球机器人的发展可知,足球机器人中最主要的一个研究方向就是路径规 划。因为路径规划结果的好坏直接影响机器人完成任务的质量,所以很多研究者 致力于研究开发新的、高效的机器人路径规划的方法。 遗传算法是以自然遗传机制和自然选择等生物进化理论为基础,构造的一类 随机化搜索算法它具有运算简单、收敛速度快等优点,并且在全局寻优方面具有 高效性和隐含并行性。用神经网络处理非数值计算的形象思维等信息具有比传统 处理方式好的多的效果。 这两种算法虽然在原理上差异巨大,但在算法结构上却很相似,具有很强的 兼容性,把这两个算法结合可以构成改进的遗传算法,它兼备了很强的全局和局 部的搜索能力的优点,在变量数目较大时尤其突出。 本课题具有重要的理论和应用价值,其意义在于遗传算法和神经网络是人工 智能领域中新的研究热点,具有很高的研究价值;遗传算法和神经网络相结合,可 以有效地弥补遗传算法搜索空间大、易出现冗余解等缺陷,同样具有深远的研究 前景和广阔的发展空间:基于遗传算法和神经网络的杌器人路径规划方法,较传统 的路径规划方法在速度和避障精度会有很大提高,对机器人的普及和应用具有深 远的现实意义。 1 4 国内外研究现状 足球机器人路径规划已经引起国内外专家和学者一致的关注,并做了大量的 4 西华大学硕士学位论文 研究工作,取得了许多研究进展和研究成果。 人工势场法是国内外研究者研究与应用最多的方法。势场法是一种在线避障 的方法,机器入在势能函数导出的力域中运动。障碍物用排斥力代表,目标则用 吸引力代表,根据这些势场能产生的合力,机器人到达且标并避开了障碍物。由 于势场能公式不能消除局部最小点的产生。机器人可能在到达目标之前,停在局 部最小点上。该方法具有计算方法简单,计算量小,且在避障和轨迹规划的同时 也考虑了机器人的运动性能,因此该方法倍受人们欢迎。在国内清华大学、华中 师范大学等等院校均在足球机器人系统中使用了该方法。而且从搜集资料的过程 来看。相关文献也是比较多的,这也充分说明了人工势场方法在路径规划中有一 定的优势。 用栅格法进行机器人路径规划也是研究比较多的一种方法。该方法将机器 人的工作空间分解为多个简单的区域,一般称为栅格,由这些栅格构成了一个连 通图,在这个连通图上搜索一条从起始栅格到目标栅格的路径。基于栅格法建模 可以与多种方法结合使用来求得一条最优路径,例如势场法、进化算法、模糊逻 辑等。栅格法没有解决栅格法存在着的坏境分辨率与环境信息存储量大的矛盾, 因此在应用上受到一定的限制。 用人工智能方法进行路径规划问题的研究也比较多,常见的方法有遗传算法 、神经网络嘲、模糊算法等等。 遗传算法是一种人工智能方法,它基于达尔文的生物进化论的适者生存原理, 用一种基于随机搜索的进化理论求解出问题的最优解。国外的k a z l l os u 鲫n a r a , j o l ls m i t h 等和国内的周明,孙树栋等人均对应用遗传算法进行路径规划进行了 研究,并取得一定成果。遗传算法是一种多点搜索算法,因而是一种求解全局最 优解的较好方法。 利用神经网络解决路径规划问题同样也有许多文献提到,并具有各自的解决 方案,利用神经网络来描述环境约束并计算碰撞能量函数。将迭代路径点集的碰 撞能量函数和距离函数的和作为优化目标函数,通过求优化目标函数的极值。确 定点集的运动方程,最终使迭代路径点集趋向于最优规划路径。 模糊理论是在美国波克莱加州大学电气工程系l a z a d c h 教授于1 9 5 5 年创 立的模颧集合理论的数学基础上发展起来的,是在线规划中通常采用的一种规划 方法,包括建模和局部规划。用模糊逻辑推理是通过对驾驶员的工作过程观察研 究得出的。驾驶员的避碰动作并不是对环境信息的精确计算来完成的,而是根据 比较模糊的环境信息,靠经验来决策采取什么样的操作。该方法在移动障碍物和 两华大学硕士学位论文 移动目标的环境中能有效地实现机器人避碰。该方法在环境未知或发生变化的情 况下就能够快速而准确地规划机器人路径,对于要求有较少路径规划时间的机器 入是一种很好导航方法。机器入的定位精度敏感、对环境信息依赖性强等缺点, 使移动机器人的行为表现出很好的一致性、连续性和稳定性。但是其缺点是当障 碍物数目增加时该方法的计算量会很大,影响规划结果。 另外还有可视图法、b s p l i n g 法、动态二叉树表示环境的a 算法等均在足球机 器人这个系统中得到了研究和应用。 虽然现在研究路径规划的方法有很多,但就解决问题的性质来说,基于静态 环境下的路径规划已经比较成熟,但是动态环境下的全局最优路径规划方法还足 不太成熟,动态环境和未知环境的路径规划一直以来都是学术界的一个难题和研 究重点。 1 5 本文内容及结构 本文的主要内容有以下几个方面: 1 足球机器人路径规划的几种常用方法综述。 2 神经网络方法的详细介绍。 3 遗传算法的详细介绍 4 改进的遗传神经网络方法进行机器人的路径规划。 本文的结构如下: 本文以微型足球机器人为主要研究对象对足球机器人路径规划的各种方法 进行论述,最终提出一种高效的综合方法,并进行详细的设计。 第一章为绪论部分。 第二章为基础知识部分。介绍了几种常见的路径规划方法。 第三章首先介绍了神经网络模型,通过建模,对机器人路径规划并分析了 神经网络方法的优缺点。 第四章详细介绍了遗传算法,并对遗传算法的各种操作方法进行综述,最 后介绍了遗传算法的设计。 第五章介绍了用一种改进的遗传神经网络方法进行路径规划,经过实验,表 明这种方法是正确有效的,并且这种方法应用于西华大学的足球机器人系统以 后,取得了较好的成绩。 6 两华大学硕十学馋论文 2 足球机器人路径规划技术 2 1 路径规划概述 规划技术是机器人研究领域中的一个重要分支,而且成为移动机器人领域的 一个研究热点。所谓机器人的最优路径规划阀题,就是依据某个或某些优化准则 ( 如工作代价最小,行走路线最短,行走时间最短等) ,在其工作空间中找到一条 从起始状态到目标状态的能避开障碍物的最优路径。机器人的路径规划方法可分 为两类:基于环境先验信息的全局路径规划,又称静态规划;另一种是基于传感器 信息的局部路径规划,又称动态规划,后者环境是未知或部分未知的。 2 1 1 路径规划问题描述 路径规划问题在理论上主要存在三个子问题: ( 1 ) 环境表示问题:指环境中障碍物的表示和自由空间的表示。环境建模就是 对机器人活动空间的有效描述。机器人在规划前首先要做的就是将环境的描述由 外部的原始形式通过一系列处理转化为适合规划的内部的世界模型,这个过程我 们称为环境建模,其中主要是障碍物的表示方法。合理的环境表示才能有利于规 划中搜索量的减少,才能有利于时空开销的减少。不同的规划方法是基于各种不 同的环境建模来进行的。 ( 2 ) 搜寻空间问题:在某个指定区域r 中,确定物体a 的安全位置,使它不与 已有的其它物体b ( j - l 2 ,1 1 1 ) 相碰。 ( 3 ) 搜寻路径问题:在某个指定区域r 中,确定物体a 从初始位置移动到目标 位置的安全路径,使得移动过程中不发生a 与b i 的碰撞。一系列安全位置就可 以构成安全路径。 解决路径规划问题的关键在于设计一种恰当的环境模型表示方法,即一种数 据结构。该结构能反映出机器人在某位置上发生碰撞的可能性。然后,按照模型 中的连通性构造与之对应的可连通图。该连通图仅抽取环境模型的连通性,忽略 掉与路径规划不相干的信息,避免了因无关信息的引入使规划复杂化,这种连通 图构成了问题状态空间。在该状态空间内利用搜索技术进行搜索,便求解出一条 通路。将通路上的节点转化为实际模型中的表示形式( 如坐标点的序列) ,便得到 7 西华入宁硕十学位论文 了机器人的无碰路径。 路径规划问题具有如下特点: ( 1 ) 复杂性:在复杂环境尤其是动态时变环境中,机器人路径规划非常复杂, 且需要很大的计算量。 f 2 ) 随机性:复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物 的出现也带有随机性。 ( 3 1 多约束:机器人的运动存在几何约束和物理约束。几何约束是指机器人的 形状制约,而物理约束是指机器人的速度和能量等。 “) 多目标:机器人运动过程中路径性能要求存在多种目标,如路径最短,时 自j 最优,安全性能最好,能源消耗最小。但这些目标之间往往存在冲突。 大部分的足球机器人应用中都需要足球机器人沿一条特殊路径到达目的地 而圆满地完成任务,并且要求避免与工作空间中的障碍物相碰撞。足球机器人的 运动能力,包括前进、后退、转动等,是整个机器人足球比赛系统执行指令能力 的反映。如果足球机器人运动能力很差,即使系统的策略很好,也不可能在比赛 中体现出良好的效果。对于足球机器人来说,无论是执行简单的跑位等动作,还 是执行复杂的进攻、防守等任务,都需要有一个路径规划的过程。尤其是多个足 球机器人协作的任务对实时性要求较高,此时路径规划尤为重要。路径规划不仅 要求足球机器人能够按照某一指标到达目的地,而且还要求每个足球机器人能够 避免与工作空间中的障碍物相碰撞,其中的障碍物包括静止的障碍物和移动的障 碍物,亦即工作空间中的机器人和边界。路径规划的好坏直接影响足球机器人执 行任务的质量,所以,找到一种既快又好的规划方法尤为重要。 目前应用于足球机器人路径规划问题己有的研究方法可以分为全局型方法、 局部型方法以及混合型方法三种。 全局规划方法依照己获取的环境信息,给机器人规划出一条路径。规划路径 的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解,但 是需要预先知道环境的准确信息,并且计算量很大。 局部规划方法侧重于考虑机器人当前的局部环境信息,让机器人具有良好的 避碰能力。很多机器人导航方法通常是局部的方法,因为它的信息获取仅仅依靠 传感器系统获取的信息,并且随着环境的变化实时的发生变化。和全局规划方法 向比较,局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息,有时 两华大学硕士学位论文 会产生局部极点,无法保证机器人能顺利到达目的地。 混合型方法试图结合全局和局部的优点,将全局规划的“粗”路径作为局部 规划的子目标。从而引导机器人最终找到目标点。 2 1 3 足球机器人路径规划方法的发展方向 上边介绍的基本的全局和局部路径规划方法,每种方法都有各自的优点和不 足之处及一定的适用范围。目前,足球机器人领域的研究者们又在探讨新的规划 方法。 总体来讲,目前混合型方法正成为路径规划方法研究的新方向。即现在的研 究向着互相结合,取长补短的前进方向发展,向着两种或多种己有算法的有机结 合的方向发展。现在,随着足球机器人的路径规划环境趋于复杂,对其规划速度 的要求越来越高,并且由于要求机器入完成任务的不同,规划时的性能指标要求 趋于多变和复杂,国内外的研究由以前的二维、已知、静态环境中的规划转向三 维、部分己知或未知、变化、有多种因素制约的环境中的路径规划,并借鉴和结 合各学科( 如仿生学、机械学、生命科学、物理学、经济学等) 中的优化方法、智 能决策等技术来设计路径规划算法。主要的研究进展有以下几个方面: ( 1 ) 将上节所介绍的几种路径规划方法相结合,又产生了几种新的路径规划 方法。例如,将栅格法和单元树法相结合用于解决二维和三维空间的路径规划问 题;将八叉树法和人工势场法相结合来解决动态环境下三维空间的路径规划问 题;以及对人工势场法进行改进等等。 ( 2 ) 遗传算法由于其具有优良的全局寻优能力和隐含的并行计算特性,所以 越来越受到重视。将遗传算法与已有的其它的路径规划方法相结合来解决路径规 划问题,取二者之所长,提高了路径规划问题的求解质量和求解效率。例如,遗 传算法与栅格法相结合,采用栅格法对机器人工作空间进行划分,用序号表示栅 格,并以此序号作为机器人路径规划参数编码,用遗传算法对机器人路径规划进 行研究;遗传算法与凸区法的结合,先用凸区法进行粗路径的搜索,再用遗传算法 进行路径节点的调整,从面规划出机器人的行走路线;以及遗传算法与人工势场法 的结合等。 但是,遗传算法虽然能从概率的意义上以随机的方式寻求到全局最优解,但 它在实际应用过程中也可能会产生一些问题。这些问题最主要的是早熟现象、局 部寻优能力差等。它们在路径规划中的典型表现是:得到的路径虽然总体上是较好 9 两华大学硕十学位论文 的,但存在着个别不必要的尖峰( 遗传算法使得高于群平均的模式在下一代中获得 较多的取样,这样不断进行,一旦某些模式取样在群中占有优势,遗传算法就会 强化这种优势,从而使搜索范围迅速变窄,表现为群收敛向一些相同的串】,在局 部上的爬山能力较差。 ( 3 ) 神经网络和模糊逻辑在路径规划中的应用也得n - f 广泛的重视,关于这方 面的文章也很多。例如k i l n i n op u l a k k a 和v e i lk u 3 a n p a a 利用s o f m 神经网络来 进行路径规划的方法等。 ( 4 ) 多数情况下,局部路径规划的目的是要快速避开先前未知的障碍物,在这 方面,比较典型和有效的办法是人工势场法及从它衍生的雷达法等。很多研究人 员都把各种含有学习的算法引入局部路径规划。如:模糊理论、人工神经网络、动 态二叉树法、遗传算法、强化学习等。从某种角度看,蚁群算法也是一个具有学 习特性的算法。但带有学习性质的算法有些收敛速度慢,有些需进行多次训练才 能较好地解决路径规划问题。 2 2 典型足球机器人路径规划方法 移动机器人路径规划是移动机器人技术的主要研究内容之己经有近四十 年的研究工作。即从不同的环境建模,针对不同的应用领域等提出了很多路径规 划的方法,几何法、单元分解法、人工势场法和数学分析法就是路径规划中比较 基本的方法。随着路径规划问题的越来越复杂,遗传算法、神经网络等人工智能 的方法也因此被引入到路径规划问题当中来。多种方法不是互相排斥的,常常是 几种方法结合起来,互相取长补短,共同地实现路径规划任务。下面就由浅入深 地介绍一下路径规划的几种方法。全局路径规划目前比较成熟,它首先对环境建 模,然后进行路径搜索。环境建模的主要方法有:位姿空间法和图搜索法等。而局 部路径规划算法由人工势场法、遗传算法( g a ) 和模糊逻辑算法等。 2 2 1 位姿空间法 位姿空间法是目前研究移动机器人路径规划的一个基本工具,其基本思想是 用位姿空间中的一个点来表征机器入的位置和方向。位姿空间法由w e h o w d e n 、 s u d u p a 、,t l o z a n o _ p e r e z 和m a w e s l e y 、i l a b o o k s 等人发展的一种无碰路径 0 西华大学硕十学位论文 规划算法。其实质是根据运动物体的大小和姿态,把周围的障碍物向外扩展一定 的距离,即相应的“膨胀”,变成扩展障碍。与此同时,运动物体缩小为一个点( 运 动物体位姿的描述简化为位姿空问的一个点) ,于是得到了一个新的空间,成为位 姿空间。由于环境中障碍物的存在,运动物体在位姿中相应的有一个障碍区。这 样把原来在物理空间中求运动物体的无碰撞问题,变换成位姿空间中求一个质点 的运动路径。这实际上是构造了一个虚拟的数据结构,把运动物体、障碍物及几 何约束关系作了等效变换,简化了问题的求解。位姿空间法把原来求一般物体无 碰撞路径问题。转化为求质点在位姿空间的安全问题,使问题得到简化,因此得 到了广泛的应用。 目前,最常用的方法是可视图法,即在一个无向图中,将机器人的起始点和 终止点以及轨迹中的各点表证为点的形式,从而机器人的有效路径就是这些点与 障碍物不相交的相互连接的线段。如果机器人的尺寸大小忽略不计,很有可能使 得机器人通过障碍物顶点时离障碍物太近甚至接触,而且该算法在障碍物比较密 集的环境搜索时间长。因此,可视图法虽然可以求得最短路径,但缺乏灵活性, 且存在组合爆炸问题。后有v o m n o id i a g r a m s 法和t a n g e n tg r a p h ( z a ) 法对可视图 法进行了改进。 几何法在二维工作空间下的性能很好,但扩展至三维工作空间后,其复杂性 和计算时间都会大为增加。 2 。2 。2 图搜索法 图搜索法采用预先定义的基本形状构造自由空间,把自由空问切分为一个个 的单元。若全部包含障碍物,称为障碍物单元:若不包含障碍物则称为自由单元; 若部分包含障碍物,则称为混合单元。该算法将这些基本单元及它们之间的联系 组成一个连通图,然后运用一定的搜索方法进行路径的搜索。其中主要方法有: 自由空间法和栅格法。 自由空间法采用预先定义的如凸区法、三角形法、广义锥法,等基本形状构 造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。该 方法比较灵活,起始点和目标点的改变不会造成连通图的重构,但算法的复杂程 度与障碍物的多少成正比,且不是任何情况下都能获得最短路径。为了提高表示 的效率,人们采用层次结构表示。自由空间法的另外一个缺点就是只在二维空间 下性能好,很难扩展到三维的工作环境,一旦扩展到三维的工作环境,其复杂度 和计算时间都会大为增加。 西华大学硕士学位论文 栅格法将机器人工作环境分成一系列具有二值信息的网格单无,多采用四叉 树或八叉树表示工作环境,并通过优化算法完成路径搜索。该法以栅格为单位记 录环境信息,环境被量化成具有一定分辨率的栅格。栅格的大小直接影响着环境 信息存储量的大小和规划时间的长短。栅格划分大了,环境信息存储量小,规划 时间短,但分辨率下降,在密集环境下发现路径的能力减弱;反之,环境的分辨率 高。在密集环境下发现路径的能力强,但环境信息、存储量大,规划时间长。所 以该算法的缺点是表示效率不高,存在着时空开销与求解精度之间的矛盾。后来 为了提高表示的效率,人们采用层次结构表示。s u b b a r a ok a m b h a m p a f i 采用不完 全四叉树表示工作空间,将叶节点连接成一张拓扑图,规划出满足性能的指标路 径。路径的搜索策略主要有:a 算法,d s 最优搜索算法等。从严格意义上看,位 姿空间法也属于图搜索方法的一种。 2 2 3 人工势场法 人工势场法最初是由k h a t i b 提出的一种虚拟力法。其基本思想是将机器人 在环境中的运动视为一种虚拟的人工受力场中的运动,障碍物对机器人产生斥 力,目标点对机器人产生引力,引力和斥力合力作为机器人的加速力,来控制机 器人的运动方向。该法简单,便于低层的实时控制,在实时避障和平滑的轨迹控 制方面得到了广泛的应用,但对存在局部最优解的问题,容易产生死锁现象( d e a d l o c k ) ,因而可能使机器人在到达目标点之前就停留在局部最优点。 人工势场法由于其算法的简单和易扩展而引起了越来越多的重视,其基本 思想是通过寻找路径点的能量函数( 势函数) 的极小值点而使路径避开障碍物。通 常情况下,其势函数是一个关于距离的标量,在寻找路径点时,若考虑障碍的边 界形状,难以用解析式计算而不得不用离散方法搜索此函数的最快下降方向,从 而带来了离散精度和计算量的矛盾,若仅把障碍近似为圆形物体,又难以区别不 同边界障碍的作用。而且传统的人工势场法由于没有引入优化过程而容易陷入局 部极小区域且不易调节,因而不适于寻求最短路径。在考虑到机器人的动力学约 束时,机器人如何跟踪规划出的路径也是一个问题。 文献 6 】提出移动机器人最优路径规划新算法,解决了最优路径规划的初始 点选择问题,大大提高了算法运算速度,实现了机器人在运动障碍环境中韵实时 路径规划。 1 2 撕华人学硕士学位论文 2 2 4 模糊逻辑算法 当环境信息完全己知时,移动机器人路径规划问题的研究己涌现了大量有效 的方法。近年来,人们更多地重视动态环境下和存在不确定障碍的路径规划问题。 在实际运用中,障碍物的移动往往是随机的,不确定环境中作业的移动机器人在 执行任务前通常不能得到环境的全部障碍信息,故无法使用传统的基于精确信息 的路径规划方法。特别是动态环境下,虽然可以频繁地进行重复规划,但由于全 局规划的计算负担很重,导致规划跟不上实际障碍信息的变化。 现在一种比较有效的方法是不寻求建立机器人工作环境的精确模型,而直接 将传感器得到的有限环境障碍信息送给机器人。机器人直接由这些信息根据预先 建立的一些规则做出反应。这种方法的出发点是模拟一些低等动物的行为,遵循 刺激反应这样简单的行为规律,而不必直接试图让机器人有人那样高的智 能。应用表明,用这种方法实现的自主机器人虽然智能程度较低,但具有很大的 实用性,工程可实现性也较强。规则的建立较多地采用了专家系统、模糊控制的 方法。 基于环境反应的方法不需要环境的数学模型来处理各种情况。该方法最大的 特点是参考人的驾驶经验,计算量不大,易做到边运动边规划,能够满足实时性 要求,克服势场法易产生的局部极点问题,效果比较理想。但该方法在复杂环境 中难构造出比较全面的规则库,且环境变化较大时,需要花费大量时间来调整和 修改己构成的规则库,不具备适应能力。 2 2 5 具有自学习能力的算法 具有自学习能力的算法是能够使机器人具有自学习能力,使机器人在运行 中通过与环境的交互或者是人的指导,逐步提高对环境的适应能力的方法。“学 习”这一术语指的是机器人通过试验、观察和推测来更新知识的能力。枫器人只 有通过不断的学习,才能完善自身的适应能力;依靠与环境不断的交互来获得知 识。 2 3小结 就研究现状来看,比较有前途的几种方法是用人工神经元网络、遗传算法、 西华大学硕七学倥论文 强化学习或者是这几种方法相结合的研究方法。j h o l l a n d 在上世纪6 0 年代初提 出了遗传算法,以自然遗传机制和自然选择等生物进化理论为基础,构造了一类 随机化搜索算法。它利用选择、交叉和变异等遗传操作来培养控制机构的计算程 序,在某种程度上对生物进化过程做数学方式的模拟。它不要求适应度函数是可 导或连续的,而只要求适应度函数为正,同时作为并行算法,它的隐并行性适用 与全局搜索。多数优化算法都是单点搜索算法,很容易陷入局部最优,而遗传算 法却是一种多点搜索算法,因此更有可能搜索到全局最优点。由于遗传算法的整 体搜索策略和优化计算不依赖于梯度信息,所以解决了一些其它优化算法无法解 决的问题。但遗传算法的运行速度不快,进化众多的规划要占据较大的存储空间 和运算时间。 1 4 两华大学硕士学位论文 3 神经网络算法 神经网络是由许多并行运算的功能简单的单元组成,这些单元类似于生物神 经系统的单元。神经网络是一个非线性动力学系统,其特色在于信息的分布式存 储和并行协同处理。虽然单个神经元的结构极其简单,功能有限,但大量神经元 构成的网络系统所能实现的行为却是丰富多彩的。和数字计算机相比,神经网络 系统具有集体计算的能力和自适应的学习能力。此外,它还具有很强的容错性和 鲁棒性,善于联想、综合和推广。神经网络是模拟人类生理上的神经机制的计算 模型,也是一种常用的学习方法,从功能上讲神经网络是一个高度复杂的非线性 动力学系统,它除了具有一般非线性系统的麸性之外,还有自己的特点,如高维 性、神经元之间的广泛互连性以及自适应性和自组织性等。机器人控制是人工神 经网络广泛应用的研究领域,其中机器人路径规划是其重要的研究内容。 一般而言,神经网络是一个并行和分布式的信息处理网络结构,它一般由许 多个神经元组成,每个神经元只有一个输出,它可以连接到很多其他的神经元, 每个神经元输入有多个连接通路,每个连接通路对应于一个连接权系数。 严格地说,神经网络是一个具有下列性质的有向图: 每个节点有一个状态变量x i ; 节点i 到节点j 有一个连接权系数; 每个节点有一个阐值毋; 每个节点定义一个变换函数【x j ,瞑( i j ) ,常见的情形为 坟x j 一只) 神经网络可以分为四种类型,即前馈型、反馈型、随机型和自组织竞争型。 前馈型网络是诸多网络中广为应用的一种网络,它是一种通过改变神经元非线性 变换函数的参数以实现非线性映射,其代表性的模型是多层映射b p 网络、径向 基网络( r b f 网络) 。h o p f i e l d 神经网络是反馈型网络的代表,它是一个非线性动 力学系统,已在联想记忆和优化计算中得到成功应用。模拟退火( s a ) 算法和 b o l t z m a n n 机是随机型网络。自组织竞争型网络的特点是能识别环境的特征,并 两华大学
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 七年级科学《建构原子模型》教学设计
- 四年级英语教案:Unit 4 Going shopping 词汇与重点难点
- 高二语文《苏武传》教学设计:以史传为径构建深度阅读与批判思维
- 八年级英语教学设计:Unit 4 Section B 3a-4d 阅读写作融合课
- 小学四年级道德与法治教学设计:走进多姿多彩的民间艺术
- 初中化学中考盐与化肥专题复习教学设计
- 我身上的“红绿灯”心理健康教案设计-小学三年级生活规则意识培养
- 小学四年级综合实践活动教学设计:家务劳动我能行
- 初中八年级数学“三角形的外角”创新教学设计
- 高中历史必修纲要上册第三单元辽宋夏金元教学设计
- 中煤电力社会招录笔试试题2026
- 2026年溶剂油行业洞察报告及未来五至十年发展趋势报告
- 2026年初级会计资格考试《初级会计实务》真题+答案解析
- 高校外籍留学生管理安全培训
- 高三思想政治教学设计:必修四哲学原理举例说明的情境关联词教学实践
- T/QLMZ 19-2024化妆品用原料 海藻酸钠
- 幼儿同伴交往能力评估量表(PAS)实施规范
- 2026年退管人员测试题及答案
- 商会招聘笔试题及答案
- 癫痫诊疗指南(2025年版)
- 年中小学教师正高级职称评聘答辩试题附答案
评论
0/150
提交评论