移动机器人嵌入式系统设计与路径规划算法研究

《移动机器人嵌入式系统设计与路径规划算法研究》由会员分享，可在线阅读，更多相关《移动机器人嵌入式系统设计与路径规划算法研究（47页珍藏版）》请在装配图网上搜索。

1、移动机器人嵌入式系统设计与路径规划算法研究 中国海洋大学硕士学位论文移动机器人嵌入式系统设计与路径规划算法研究姓名:朱晓荣申请学位级别:硕士专业:信号与信息处理指导教师:周东辉20040701杉动机鞘人嵌入式系统设计与婚静规划算法甜究移动机器人嵌入式系统设计与路径规划算法研究摘要随着社会的发展,工业机器人产量逐年增加,但根据最新预测,到世纪,家用机器人将成为机器人制造业的主力机种。工业机器人主要用于以工厂为代表的第二产业,而家用机器人则主要用于第三产业的服务业,在普通家庭中蕴藏着巨大的潜在市场。本文对家用移动机器人嵌入式智能规划系统进行了深入研究,在智能算法和硬件设计两方面取得了具有实际应用价

2、值的结论,实现了家用移动机器人的自主行走、实时避障、自动寻找充电器充电、不重复走遍整个房问地面等功能。为了实现上述目标,本文采用了以下路径规划策略和控制算法。工作环境的不确定性例如室内物体摆放的位置不同要求家用移动机器人具有对环境的白适应能力。遗传规划算法具有在事先不需要知道解的规模、类型和结构复杂性等情况下,解的属性可以根据问题的需要由求解过程来确定,而且基因编码长度动态可变,这些优点使得遗传规划算法特别适合用于家用移动机器人在未知环境下的路径规划。另外一方面,它的内核占用的空问少,易于用硬件实现。因此本文采用遗传规划算法来实现家用移动机器人的实时避障,采用交叉自律行走的模式实现路径不重复地

3、走遍整个房问地面。另外,为了实现移动机器人的实时避障功能,不仅要求硬件系统具有较强的数据处理能力,而且应该具有软件可移植性和硬件可扩展性。基于这些要求,本文采用了处理速度较快的可编程门阵列来实现算法,采用位单片机来实现对外围电路的控制、自动模式与人工控制模式的转换以及电机驱动等。并且该单片机具有强大的语音处理能力,可以很方便的进行语音识别,用语音来控制机器人的行为。在详细阐述遗传规划算法在机器人自适应行为进化过程的基础上,本文讨论了该算法在上实现的几个亟待解决的重要问题,包括个体的寄存器存储方法、最优化随机数在硬件上的获得途径、交叉操作的实现、以及有效的内存管理方法等。软件仿真和实验结果表明,

4、利用上述方法实现的机器人具有较快的白适应迸画的能力,能够首先沿着墙壁走一圈,然后交叉自律行走,能够自动避障,并且能通过遥控操作或语音识别进行自动行走模式和人工控制模式的转换,当检测到电压不足时,能够自动寻找充电器充电。,单片机,避障关键词:家用移动机器人,遗传规划算法,梏动机器人嵌入式系统漩计路径规划算法研究?., ?“. ,. ,., , ., ?.,. . ., . , .,“”. . .】 , ., ,.移动机器人嵌入式系统吐汁,路子州划算法研究、 ,.,. . .,.移动机器人战八系统潢汁与路径规划算法研究概述.课题背景工业机器人自问世以来很快在世界范围内得以广泛应用。目前,工业机器人

5、产量逐年增加,但据最新预测,到世纪,家用机器人将成为机器人制造业的主力机种。工业机器人主要用于以工厂为代表的第二产业,而家用机器人则主要用于第三产业的服务业,在普通家庭中蕴藏着巨大的潜在市场。但是,这种家用机器人目前尚无已完善的实例,其定义有各种说法,其技术亦各有千秋。如果要说有共同认识的话,那就是一致认为家用机器人是“在家庭中为个人服务的机器人”。在一般家庭中普及机器人的设想源于两个出发点。其一是以年轻人为中心的家庭成员的价值观的变化,即从“以工作为中一”转变为“以自我为中心”,追求生活的高质量,追求家务劳动的省力化,实现家庭自动化。这就需要借助于家用机器人的服务。其二是整个社会的老龄化。随

6、着出生率的下降,人类将呈现出长寿化,形成老年人多、年轻人少的社会。从社会福利的角度考虑,需要对许多老人配以家庭助手。但因工资、劳动条件等因素的影响,加之前述年轻人价值观的变化,在供不应求的劳动力市场上很难找到自然人作为家庭助手,故需家用机器人来补充劳动力市场。家用机器入的开发犒是今后一个时期机器人的一个重要发展方向。日本和美国都在加紧研制能够广泛用于家庭中的家用机器人,这种机器人除了能够给家庭带来娱乐外,还能够帮助家庭干一些家务,家用机器人的发展趋势将是智能化和多功能化。这种机器人运用最先进的电脑技术和通讯技术,能够与正在上班的人取得正常联系,家用机器人能够根据主人的意图完成做饭、打扫卫生、收

7、发电子邮件等许多工作。一些家用机器人还将能够取代保姆的作用,这些机器人在未来将能够替代人类的大量家庭劳动、为人类的生活带来极大的方便和乐趣。国外专家预测,在世纪,家用娱乐型机器人将大量投放市场,其消费势头将会超过彩电、电脑和汽车的消费,家用机器人产业将会成为世纪最有诱惑力的市场之一,特别是能够用于娱乐方面的家用机器人玩具将更受广大家庭消费者的欢迎。而在家用机器人中,家用移动机器人占很大一部分比例。家用移动机器人研究概况本二菱重工开发出种能照顾老人、能看门的家用机器人。这台取名“我之丸”的人形机器人身高,头顶设有鱼眼照相机,根据所摄图像,用各种传感器一边测量对象及障碍物的距离,一边使车轮式的脚在

8、室内绕道行走。它备有充电功能,如果电池电力不足,能自行充电。它能识别多达个人的容貌,掌握约万个单词的移动机器人嵌入式系统盐汁与路杼规划算注研究简单会话。能用内置的无线定位器功能,经常连接通信网络,同外出的对方保持联络及遥控操作。例如,外出的人可用手机了解家中的状态,若有大的声响,它能通知预先指定的联络对象,起到“看门作用”;又如发现独立生活的高龄老人有异常,它能立即通知远方的家属,起到“看护作用”;还能设置提醒服药的时间以及传递健康信息管理等功能。本田公司出品的版机器人能用声音控制,它有一个憨态可掬的傻瓜外形,每小时可以行走千米千米。它的身高厘米,重约多千克,体格相当于小学生。的头部配备了两部

9、照相机,可以测量与用户及周围物体之间的距离,并推算用户及物体所在的方向与移动,简单地说,这是一个能自觉地跟着主人走动的机器人。除了可以做“随从”之外,还有“认人”的本领,它能从拍摄的图像中抽取人与物体的轮廓进行识别,据说最多能认个人,同时能区分一些简单的姿势并做出回应。年日本横滨机器人大展上展示的不仅具各以上的特点,还大大增进了行进速度,搭载了不少全新技术。日本机器人开发公司近日推出一种可以通过声音和手机远程遥控的家用人形机器人,这是世界上首次被推向市场的家用步行机器人。 据日本读卖新闻日报道,这种机器人的名字叫“”,身高厘米,体重.斤,可放在手提包里携带,脚上穿着落地时可减少冲击力的机器人鞋

10、子。它有个内置发动机,可以自己掌握平衡,用两脚步行和跳舞,能做出指令要求的各种动作。人可以用声音或手机进行远程操作,还能通过手机看到机器人脸部照相机拍下的图片。公司介绍说,可以与小孩一起玩耍,成为他们的好伙伴,还可以和老人对话,让他们开心姆闷儿排解寂寞。此外,机器人的主人还可以把它单独放在家里看家。两脚步行机器人在吐界上第一一次推向市场,预示着机器人开始由产业使用向个人使用的转变。由中科院沈阳自动化研究所与中科院自动化研究所联合研制成功的一种新型特计划验种机器入?基于复合机构的非结构环境移动机器人,目前通过国家收。专家组认为这一机器人具有很强的环境适应能力,能在多种复杂、多变、恶劣的环境下完成

11、运行操作。长期以来,采用何种移动机构和移动方式,一直是移动机器人的关键技术之一。这一课题组借鉴以往的轮式、腿式、履带或滑板式等单一驱动方式,采用了先进的轮一腿履带等多种复合型装置。这些驱动装置自由组合、分西作,既可充分利用单一驱动方式在特定环境下的某种优势,又可集中发挥各种仂调装置在复杂多变环境下的综合效力。这种机器人自重不到公斤,长.米、宽.米、高 米,履带移动速度每分钟米,胶轮移动速度可达每分钟米。整机采用了“多传感器信息融合”新技术。为了弥补机器人探测“盲区”,在机器人的四周装有超声波传感器和红外线传感器,用以搜集机器人各个方向的障碍物信息;同时还装有确定目标方位的视觉传感器,用来检测机

12、器人位置的电予罗盘等。在基于神经网络与模糊算法的自主控制状态下,机器人具有自动回避障碍、寻找目标、上楼梯、跨越障碍等功能,驯使而对多种结构的复杂环境,也能应付自如,迅速做出判断,根据不同的地面状况自移动机器凡嗽入,系统设计与鸭行慨划算法研究动切换移动方式。据了解,这种特种机器人技术集机械、电子、新材判、传感器、计算机、智能控制与网络通信等多门科学于体,是最具基础性、战略性和前瞻性的高新技术。专家认为,这种机器人具有极强的环境适应能力,将为中国在太空、海洋等未知环境下的探测勘察工作提供技术保障。.移动机器人路径规划概述移动机器人路径规划是机器人学的一个最基本也是最复杂的问题,它被描述成:给定一个

13、移动机器人所处的环境环境可以通过移动机器人视觉系统或者别的途径获得,个起始点和一个期望的终止点,移动机器人蹄径规划就是根据一定的任务要求寻求一条连接起始点到终止点且能避开环境中障碍物的移动机器人的运动轨迹,即最优或次优有效路径.路径规划是移动机器人导航中最重要的任务之一。目前,移动机器人的路径规划算法主要有两种类型:一种是基于环境先验完全信息的路径规划;另一种是基于传感器信息的不确定环境的路径规划。完整的先验信息只适用于静态环境,在情况下,路径是离线规划的。在环境不确定的情况下,路径必须在线规划,其中还包含在线避障算法。近年来,国内外学者对存在固定障碍的路径进行了大量研究,提出了一些算法。其中

14、比较成功的方法主要有势场法和栅格法。.首先提出了人工势在年和年加以改进,提出了一种人工辅助全局场法,后来由.路径规划法,并进行了性能分析。用栅格法表示格予环境模型中存在障碍物的可能性的方法起源于美国大学。以后,.虽用栅格表刁一环境,但是,在更新值上与删方法不同。在每一次的超声传感器读值时,只需要很少的计算,只影响一个栅格的值,该栅格就是距离超声头为读值的栅格,它在传感器的轴上。用势场法决策出虚拟力场去控制移动机器人行驶。通过】陷阱区域; 在相近障碍物的实验研究,发现了势场法存在四方面问题:之间不能发现路径;在障碍物前振荡;在狭窄通道中摆动。.提出了一种矢量场矩形法,仍采用栅格表示环境,还采用了

15、两极数据减少技术和信息的三个级别表示,由算法的输出信息控制移动机器人的速度大小和方向,呈现出良好的性能。但是该方法存在环境分辨率高与环境信息存储量大的矛盾,因此,在实用上受到一定限制。针列圭见划区域中障碍物形状和分布复杂的情况,为了得到满意的路径,并且满足实酬性的要求,后来征栅格法的基础上,采用基于案例的学习方法来解决移动机器人的路径规划。基于案例的学习方法依靠过玄的经验迸彳:二学习及题求解。一个新案例可以通过修改库中与当前情况相似的的案例来获得。基于案例的学习是增量式的,学习的成功率随着案例的增加而提高,案例的匹配过程也是案例库的扩充过程。堪于案例的学习重视的是如何组织和管璀一个案例库,在需

16、要进行摊璀吲如何快速的从案例库中找到合适的匹配案例,以及是否扩充案例库。移动机器人嵌入武系统醴汁与路径规划算法硼究在基于多传感器融合的导航研究中,模糊逻辑和神经网络是采用得比较多的两种方法。这两种方法的共同点在于易于表达某些难以精确描述的规则,但也存在着各自的缺点:模糊逻辑的运算量随规则数量的增加而成几何级数增长,因而在模糊规则较多时难以付诸实施;神经网络系统受学习样本的影响很大,选择代表性强的样本集是一件分困难的事情,而让样本集覆盖整个样本空间是不现实的,因而样本设计就成为神经网络应用的一个丰要问题。由于模糊逻辑和神经网络各自的缺陷,在实际应用中,均未能取得完全满意的效果。避障控制是导航任务

17、的基本内容之一,后来又出现了将模糊逻辑、神经网络和传感器融合技术结合起来,用于移动机器人的避障控制研究。利用多个非摄像类的超声波和红外线传感器探测环境信息,采用多传感器融合技术对传感器信息进行处理,研究了模糊聚类和神经网络系统在移动机器人系统中的避障控制能力。利用遗传算法, .等人设计了一种移动机器人进化规划系统,在该系统中,路径由一个个节点组成,节点由矛坐标和位表示路径通畅与否的状态来表示,基因与路径相对应,目标函数由三个部分组成:路径长度、光滑度和距离障碍物程度,根据实际情况规定了八种遗传操作。利用改进的进化编程,并精减遗传操作,得到了很好的效果:并且可以满足不同的优化准则,得到次优路径和

18、更好效率,适应各种情况变化,具有良好的鲁棒性。目前,遗传规划算法的研究非常活跃,研究范围也涉及到神经网络、专家系统、图象处理等多个领域,在移动智能机器人研究领域,随着社会的进步和技术的发展,越来越需要机器人能够在没有人工干预的条件下自适应于环境和完成所给任务。遗传算法在这一领域已经得到了广泛地应用并取得了很好的成效。而与相比,虽然提出较晚,理论也较新,但它具有所不具备的优点,如:由于许多工程问题可以归结为对特定输入产生特定输出的计算机程序,而算法的个体表示的就是这些计算机程序,它能够很好的层次化地描述所要解决的问题;而且算法在交叉过程中是任意选择交叉点,所以它的基因编码长度是动态可变的,这就使

19、得基因所描述的系统状态可以更好地适应环境的变化;此外,对于算法的应用,事先不需要知道解的规模、类型和结构复杂性等,解的这些属性可以根据问题的需要由求解过程来确定。这些优点使得算法能够很好地应用于机器人自适应行为的演化巾。 ., .他们把遗传规划算法用于.,机器人的避障行为中,机器人采用 微控制器,实验结果表明该机器人有良好的进化行为,能够实时的避开障碍物。本文是采用遗传规划算法来实现避障的,所以下面将详细阐述一下该算法。.逮传规划算法概述遗传规划;,简称算法是由教授提出用于计算机程序的优化设计及自动生成的一种算法,其实质是用义的层次化计算机程序描述问题。它的基本思想和遗传算法 ,简称相类似,通

20、过随机移动机器人战八。戈系统设计与路径规划算法研究产生初始群体,然后对群体进行自然选择、交叉变异,最终优胜劣汰,自动生成性能较好的计算机程序。算法基于具有描述问题层次化、编码长度动态可变等特点,它被广泛地应用于人工智能、机器学习、符号处理等方面。算法使用分层结构的表达方式来表示解空间,它的叶结点是问题的原始变量,中日结点则是组合这些原始变量的函数,这种结构很类似于语言中的表数据结构。算法的个体染色体表示的是许多计算机程序的组合,根据程序表达含义和组合位置的不同,可以分为函数集和终止符集,其中函数集包括运算符号、数学函数、条件表达式等等;终止符集包括变量如描述系统的输入变量、状态变量、常数、无参

21、函数等等。函数集和终止符集必须满足两个条件:充分性利闭合性。因为算法中问题的解是函数集和终止符集的组合,所以要求预先设定的函数集和终止符集的组合空间中包含所给问题的解;同时,函数集和终止符集的组合必须满足闭合性,即任意函数所带参量和任意终止符的类型必须一致,这样才能保证遗传变换的正常进行。和遗传过程一样,算法的一般遗传过程也包括选择、交叉、变异。结构如图所示:彪手予.众幽捌形结构遗传过程结构图?堕型型塑垒坚尘:;墨堑堡生兰堕堡型型曼鲨塑壅根据基因的结构形式不同,遗传规划算法可以分为树形结构、线性结构、图形结构和其他结构形式的。线性结构能交叉操作如图所示。鱼呈量哥.盘了.圈;网圈、一圈孟圈沁护琴

22、零 圜尹辩圆圈圈圈匦圈圆圈图线形结构遗传过程结构图需要说明的是:选择、交叉、变异操作是个体依次循环进行的.也就是说下一代群体中包括部分的选择操作的个体,部分的交叉操作的个体和少部分的变异操作的个体;而不是像的遗传操作那样群体依次循环进行,这样可以使得更大几率保证好个体保留下来;由于算法的交叉操作是两个个体分别随机选取交叉点,交叉点以下的子个体长度可以不同,个体的编码长度是动态可变的,所以即使两个相同的个体,也只有当交叉点相同时才不会发生变化,因此算法的个体经遗传操作后不具有同一性,到不会使整个群体趋向最优;同样由于算法的交叉操作使得个体编码长度动态可变,所以算法不像算法那样会陷入“早熟”,变异

23、操作的作用也就相应地减弱了;算法的个体就是函数集和终符集组成的语义树,所以对个体染色体用符号型编码表示成树型结构,能够很好地体现这种组合关系,而且能很方便地进行遗传操作。个体的表示。根据个体的特点.用二叉树的树型结构和袖点结构来表示个体和个体的节点。每一二叉树都是由很多节点串起来的,可以通过访问其根节点来访问整个叉树。适应度函数的选择。常用的适应度有:原始适应度、标准适应度、归一化适应度。原始适应度是问题的自然表达,很多简单问题如蚂蚁觅食问题就可以直接用寻觅到的食物数量作为原始适应度;标准适应度是原始适应度的又一描述,它总是表现为适应度值越小越好:归一化适应度是将标准适应度进行归一化处理。如何

24、选择合适的适应度函数,还需具体问题具体分析。随机产生初始群体的方法。采用从下到上的结合法,即根据函数所带变量的个数,对终止符进行随机组合,然后组合后的于树又作为一个变量,再次和别的变量包括其他子树和终止符进行组合,这样一直组合直到达到设定的树结构深度。综上所述,可以看出,与相比,虽然提出较晚,理论也较新,但它具有所不具备的优点,如:由于许多工程问题可以归结为对特定输入产生特定输出的计算机程序,而算法的个体表示的就是这些计算机程序,它能够很好的层次化地描述所要解决的问题;而且算法在交叉过程中是任意选择交叉点,所以它的基因编码跃度是动态可变的,这就使得基因所描述的系统状态可以更好的适应环境的变化;

25、此外,对于算法的应用,事先不需要知道解的规模、类型和结构复杂性等,解的这些属性可以根据问题的需要由求解过程来确定。这些优点使得算法能够很好的用于机器人自适应行为的演化中。遗传规划中个体大小“爆炸”现象及其对策在遗传规划中存在着熟知的所谓“规模爆炸”问题,亦即作为程序个体表示的文法树的大小,包括它的深度和广度,在进化过程中不断地增大,而与此同时作为解的群体却没有任何改进。这一现象为许多研究者所发现。对于大多数的应用问题来讲,树不能太大,否则很难将它翻译为一个有意义的结果;同时,正如许多文献所指出的那样, “爆炸”现象常常伴随着优化讲程变慢的表现。.内含子的作用与危害在程序树规模变大问题中,可以观

26、察到一个十分有趣的现象,这就是“内含子”大量产生的问题,也可称之为“冗余”问题,图,是两个冗余的程序树的简单例子。在图中,因为第一个变量的值为,所以“与”运算的结果恒为,而不管第二个变量的值是什么。因此,如果有一个子树以节点为顶点的匮,那么它对程序树所代表的整个程序的最终结果没有任何影响。图中,实际计算结果是,类似的现象在符号回归问题的求解过程中是非常普遍的。为了压缩这种冗余的语句,不得不对最后的结果使用自动编辑器来消除这种现象。但是,这仅仅是在最后步所作的工作,对于在进化过程中怎样减少该现象并没有提供帮助。内含子是一个遗传学术语,指生物染色体上的某些不表达为蛋白质的基因片段,它们只足提供了有

27、意义的基因外显厂之问的问隙,文献首先将内含了的概念引入遗传算法中,在一个串中的某些基因座上放置与适应值计算无关的等位基因,移动机器、嵌入式系统设汁与蹄仟规划筒法研究或干脆认为这些位置是空的。引入内含子的意义在于,进行交叉操作时,当交叉点的位置落在内含了时,不会破坏已有的有意义的串,因此能有效地保护现有的模式。图 冗余程序树图冗余程序树模仿遗传算法的串表示,引入了线形表示的程序个体,而不是用通常的树状表示,并且在遗传规划中引进了内含子的概念,亦即“对任何适应值函数,都不影响所在程序的表现的程序块”。在实例中发现,进行了交叉操作以后,有相当的个体的适应值下降了,同时有相当的个体的适应值保持不变。经

28、过分析得知,很多个体通过增加它所包含的内含子的个数来保护自己不受交叉操作破坏作用的影响而保持适应值基本不变。的分析是基于他的程序个体的线形表示的,不完全适用于通用的遗传规划。对于如何在程序树中引入内含子的概念以及做出相应的分析,仍是一个有争议的问题。一个比较自然的定义是称个体树中的某个节点是内含子,如果该个体的适应值与顶点在这个节点的子树无关。显然,如果一个节点是内含子,则以它为顶点的了树中的任何节点都是内含子。由于动态树状表示的复杂性,对之进行理论分析是十分网难的这也是遗传规划理论研究中的主要困难所在,现有的结果也是很初步的。如前所述,内含于的出现与存在,在保护个体不受交叉操作的破坏方面是有

29、益的,似是一个程序中有过多的内含予会造成程序树过度膨胀,影响运算效率,同时也使得剥程序意义的解释变得同难。已经有多种方法来处理这种程序树的大小“爆炸”的问题,其中最简单的方法是在遗传规划的运行过程中,限制树的大小,比如。这种方法的问题是群体的多样性得不到保证。为了保证备捌的最火深度限制为在群体中有足够的遗传物质,只好使用很大的群体规模,必然大大增加计算量。更移动机器、嵌入式系统世汁与蹄杼觇划算法硼究重要的是,在多数应用刚题中,事先根本不可能确定应当如何选择树的大小才能解决问题。取得太大,没有意义,而取得太,有可能得不到正确的解。.消除冗余性的方法普遍的方法是引入类似于优化问题中“罚函数”项的简

30、约压力项,对于。个最小化问题,这就相当于将一个与树的大小有关的项加到原始的适应值函数上以产生新的适应值函数,剐这里表示一个个体,为的原始适应值,给出了的树状表示的复杂度,如树的深度,节点的个数等,为简约压力因子,为新的适应值函数.这种方法的困难在于如何权衡简约压力因子的大小。如果太小,则对于减少内含子数目的效果并不理想;而太大,遗传规划倾向于选择短的解,即使短解的原始适应值较差,这就会导致收敛到错误的解。由于事先无法估计最优解的规模,的确定当然是以自适应选择为佳,亦即在进化过程中自动地调整的大小。在实践中发现,上述方法有其适用的具体问题。但如何找出问题的特征以便事先就能判断使用哪一种方法更合适

31、,仍是一一个没有解决的问题。.论文结构家用移动机器人的开发将是今舌一个时期机器人的个重要发展方向,这种机器人除了能够给家庭带来娱乐外,还能够帮助家庭干一些家务,家庭机器人的发展趋势:悔是智能化和多功能化。家用移动机器人的关键技术是嵌入式智能规划系统。规划系统包括传感器及其信息融合、机器人的定位定向和自主规划及其硬件实现等。本课题研究的主要内容有家用移动机器人路径规划算法?遗传规划算法、传感器及信息融合技术以及基于嵌入式芯片的智能规划硬件系统的设计实现。本课题交现的基本功能有遇障碍可自动回避、可沿障碍边界移动、自学习进化算澎、实现行走慕本无重复路径以尽快的走遍整个房闻地丽;多种传感器检测周围一作

32、环境,全过程安全可靠,操作自动化:当检测到电压不足时,可以自动寻找充电器进行充电,充电一次工作分钟:可以进行语音识别署遥控操作来切换机器人的行走模式?自辛彳丁走和人工控制行走模式。第 章,遗传规划用于机器人避障的实现。首先说明了本文移动机器人采片的.【径规划算法;然后详细刳述了遗传规划算法用于机器人避障的实现,包括个体的表示、遗传操作、适应度函数以及算法进化的详细过程。仿真结果表明,该遗传规移动机器人嵌入式系统吐与路径规划算法研究划算法学习的速度较快.有较高的处理速度,提高了移动机器人的避障实时特性简化了系统设计。这一章是本文的重点。第二章,家用移动机器人智能控制系统的硬件设计。根据算法实现地

33、经济性和简单可行性以及硬件的可扩展性,选取可编程门阵到芯片作为遗传算法实现的载体;选用位单片机作为智能控制芯片,以控制电机以及外围电路。这是本文的另一重点。第章,详细阐述了遗传规划算法在硬件上实现的几个重要问题及解决方法,包括个体的寄存器存储方法、最优化随机数在硬件上的获得途径、交叉操作的实现、以及有效的内存管理方法等。第四章,沦文总结。概括本论文研究的主要内容,并说明了本课题研究的重点内容和方向。鸦功机器几嵌入式系统慢汁与鸭行况划贯:研究遗传规划算法用于机器人避障的实现本文所采用的路径规划算法本课题要实现的基本指标有:自学习进化算法实现逞障碍可自动回避;行走基本无重复路径以尽快的走遍整个面积

34、;多个传感器检测周围工作环境,全过程安全可靠,操作自动化;当检测到电压不足时,可以自动寻找充电器进行充电,充电一次可工作分钟;可以进行语音识别和遥控操作来切换机器人的行走模式?自主行走和人工控制模式。根据要实现的基本指标,使机器人采用交叉独立自律行走的模式。图为交叉行走模式不意图。首先,通过测距传感器检测房间的墙壁,控制机器人沿墙角行走。在沿墙角行走时,当检测到标志时,确认走遍周边墙角使机器人返回原位。周边墙角走完后,转向房间中部行走,从房间一侧行至对侧后,转动。返回,如此反复行走,如前方有障碍物则返回。这种往复行走在交叉。的纵横两个方向进行,即可将仝窜走遍。外走缄向往葭行走行盘瓤盗横向往复行

35、走图交叉行走模式图移动机器凡嵌入式系统设计与踹杆觇划骨限研究为了实现以上这些动作,需按以下的基本规则进行控制。第,障碍物回避规则。根据算法硬件实现的可行性、方便性和经济性,用遗传规划算法来实现机器人的避障行为。在吸尘机器人周围设置六个红外线测距传感嚣,把这些传感器的数值输入到智能控制器里,利【;遗传规划算法得到机器人的两轮电机的速度,从而控制行走电动机的动作。这样,目使遇到各种各样材质和形状的障碍物,也不会冲撞,保证吸尘机器人高效准确地在墙角环行和在房问中部往复行走。笫二,姿势控制规则。首先,通过测距传感器检测房间的墙壁,控制机器人沿墙角行走一周。然后纵横两方向往复行走,通过旋转传感器进行控制

36、,使机器人保持直行,前方遇到障碍物进行。的转向控制。但只用这种控制在有地毯的房间或地面不太平的房间,保持直行有困难。比如地毯的毛有一定的倾向,机器人即使向前直行,由于倾斜毛的影响,也会使本体改变前进方向。因此使用可检测万向轮方向的横向传感器,根据此传感器的信息可知道横向偏移,从而修正控制机器人保持直行。由于本机器人是自动操作,通常用户是不在旁边的。如运转中出现故障,不仅不能作,还可能发生不安全情况。因此需要采取一些措施来避免出现这些问题,在本机上设置检测本机至地面距离的高度传感器,工作前预先检测前方的地面高度,如遇到台阶等物体,可使机器人回避。设置报警传感器,在车轮遇到障碍物产生渭够,当孩子不

37、注意压碰本机等,在机器人工作难以继续进行时,使机器人停止运转。系统的构成整个系统的构成如图所示,外部传感器得到的信息经过单片机处理后得到距离数据传给控制器,由固化在的算法来处理这些数据,从而得到机器人的动作信息,以驱动机器人动作。动作评价适应度计算移动机器人与传感控制器惫度器单片机?一距离等信息记忆与处理图系统整体框图移动机器凡嵌入式系统设十与蹄栉贱臂琏研究.实验环境如图所求,机器人为二轮小车,采用芯片作为微控制器,同时采用存储器用于存储的电路配置信息。片运动控制芯片可实现机器人左、右轮速度伺服控制,电机为自带光电编码盘和减速器的直流电机,单片机为台湾凌阳公司的位单片机,传感器是分布在小车周围

38、的六个红外接近传感器,能检测的距离大约为如图。图 二轮小车移动机器人嵌入式系统畦汁与路径规划算法研究图 红外接近传感器分布图.机器人运动模型图所示为三轮机构原理图。它是由独立驱动的两个后轮和小脚轮构成的辅助轮组合而成。设转向角为中、点的坐标为,、车体相对于坐标轴的偏斜角为,、。为两轮的速度,那么车体的运动可用表达式来表示:,淞图小车机构原理倒.遗传规划算法和机器代码在第一一章已经讲述过,等人利用遗传规划算法来进化机器人的行为得移动机器人嵌八式系统设计与路径舭划算注研究到很好的效果,本文是在他们研究方法的基础上,提出三点改进:一是个体是用一组位的寄存器组来存放;二是算法在上实现的,而不是在单片机

39、上来实现;三是群体的初始化时,随机数获得的方法不一样。通过这三点改进,机器人进化的速度加快,而且遇到障碍物时自动避障的灵敏度提高了。遗传规划是用于计算机程序的优化设计及自动生成的一种算法,其实质是用义的层次化计算机程序描述问题。它的基本思想和遗传算法相类似,通过随机产生初始群体,然后对群体进行自然选择、交叉变异,最终优胜劣汰,自动生成性能较好的计算机程序。算法基于具有描述问题层次化、编码长度动态可变等特点,它被广泛地应用于人工智能、机器学习、符合处理等方面。许多工程问题可以归结为对特定输入产生特定输出的计算机程序,而算法的个体表示的就是这些计算机程序,它能够很好的层次化地描述所要解决的问题;而

40、且算法在交叉过程中是任意选择交叉点,所以它的基因编码长度是动态可变的,这就使得基因所描述的系统状态可以更好的适应环境的变化;此外,对于算法的应用,事先不需要知道解的规模、类型和结构复杂性等,解的这些属性可以根据问题的需要由求解过程来确定。这些优点使得算法能够很好的用于机器人自适应行为的演化中。所渭路径规划就是在给定的障碍环境结构下,机器人从初始点出发,能够避开障碍物而到达目标点。这包含两层意思,一是如何避障,二是避开障碍物后向哪个方向走才能最优的到达目标点。基于上述遗传规划算法的优点,本文首先利用该算法实现避障,然后根据交叉独立行走的模式走遍整个房间的面积。.个体的表示在本系统中,采用线性基因

41、的形式,并把构成群体的个体以二进制代码的形式进行存储。这就使得系统的执行速度提高了很多倍,同时节省了存储空间,内核只需要的存储空间。这些特性可以使算法运行在低端处理器上如一块芯片进行理想的实时控制,从而达到了能进行独立的控制,而不需要构成主从式结构。这里采用的进化算法是一种高级的,即每个个体都是由不同长度的位的指令序列集类似标准语言函数的机器代码序列组成的。每条位的指令代表简单的算术操作如“”或者“”,可以包招最大长度为位的常数,它的结构如图,它包括四部分:头部分、返同部分、函数体和缓冲区。头部分存放常量和个体初始化的内容,不能对这部分代码进行交叉或变异操作;返回部分使系统在函数调.后返回到主

42、进程中;函数体是由代表个体的实际程序组成的,遗传操作存这哩发牛;在每个个体的末尾都保留了一部分缓冲区空间,这保证了个体的长度是叮以变化的,为交叉操作提供了空间。移动机器凡嵌入式系统设计与路径蜘划算法研究.一?斗?十斗竺五裂图个体的结构.遗传操作在本系统中,利用两点字符串交叉,节点是基本的交叉单位,可以在节点的一侧或两侧进行交叉操作,但不能在节点内部,图例示了本文中采用的交叉方法。变异发生在节点内部,变异算子保证变异后的指令在有效的指令集范围内。所有的遗传操作都要保证进化中的封闭性。在该实验中,采用的是低级机器代码指令,函数集由算术操作、,移位操作、和逻辑操作,和组成的。恕引创 ,誉尚忑只图 交

43、叉操作移动机器人嵌入,系统醴计与路径舰划算法研究.适应度函数在本文中,每个个体都是由简单的指令集程序行组成的,这些指令表示了变量、输入和输出参数之间的关系。输入是六个红外接近传感器的距离值,运行后的结果输出是两轮驱动电机的速度, 用函数可以表示为:,:,。,。,。,其中,?是外界传感器的数值,。,:是两轮驱动电机的速度。但为了更好的表达个体进化与外界环境的关系,我们把上述函数表示成下式:., ,:,个体根据适应度函数值的大小来调节参数,从而使个体能更好的适应环境。适应值函数的大小表示了个体的优劣,它由“惩”和“罚”两部分组成。对函数值有负贡献的部分,即“罚”,它是所有红外传感器数值的和。越接近

44、一个物体,“罚”的值越大,为了防止机器人原定不动或打转,给适应度函数值一个正的部分,即“奖”,机器人走得越快,“奖”值就越大。,的取值范围为?,值越大越接近物体。、。取值为?,是个体执行的结果,为左右轮的速度。根据以上原则,适应度函数值可表示为:,一、一,一。.进化算法在本系统中,进化训练中选用的参数如表所示表函数集: ,“奖”减去“罚”的部分适应度函数:群体规模:%交叉率:%变异率:联赛选择选择:移动机器人嵌入武系统醯计与路径规划算法研究图控制结构图控制结构框图如图所示,算法具体的实现步骤如下从群体中任意选择个个体;对联赛选择中的个个体,都做如下几步:从外界读入六个传感器的数值,并把这些值传

45、给该个体。执行个体得到两轮驱动电机的速度。把电机速度传给机器人。休眠等待机器人的动作结果。再次读入传感器的数值并计算适应度函数的值。根据适应度函数的值,用最好的两个个体的子代来代替最差的两个个体。对子代进行交叉和变异。转到步骤,重复以上步骤,直到选出最优的个体。算法实现的流程如图。.该算法的仿真结果开始时行为是杂乱无章的。在头几分钊,内,机器人不断的垮物体碰撞,但随着时间的推移,碰撞次数越来越少,第一个智能行为经常表现为遇到障碍物时向后退,然后逐渐的学会拐弯以避开障碍物。移动机器人嵌入式系统世计与路径规划算法训究移动机器人嵌入式系统设计与路径规划算法研究进化过程中个体适应度值和性能的变化可以从

46、图,中看出,在进化中的第代内,平均适应度值和最好个体的适应度值都得到提高图和。从图可以看出,从第代开始,最好的个体的适应度函数值就达到了进化后最后个体的适应度函数值,但是波动很大。虽然在每代中最好的个体都保留下来,但在训练中相同的个体却表现为不同的适应度函数值,这是由于适应度的取值依赖于其性能即表现结果,而不是控制程序结构本身。从图可以看出,在代内,是稳定增加的,但平均碰撞次数平均采样数却没有明显的变化,这说明了随着进化的进行,达到了避障的效果。图每代最好个体的适应度值图每代平均适应度值图采样数和碰撞次数的变化结果讨论由以上讨论可以看出,该遗传规划算法学习的速度较快,有较高的处理速度、较低的内

47、存需求,提高了移动机器人的避障实时特性、简化了系统设计。堡垫丝堡垒堂垒壅至堕堡堕堡塑型生燮一一?移动机器人智能控制系统的硬件设计一?算法的硬件实现甫隶奎翥柔鲁霪磊孥裂蒌霉言裳警罂凳金譬錾耋唑茎哭擎鬈并瑟螽皇篆墓翥鬈霹器八日眵哭州雌早;兰耄粪銎銮焉萋譬獬南翥譬篡塞焱,。嬲磊鬻翼豁一是容量足够大,能容得下算法的实现;二是处理谜度快,便一是硬件具有“扩展性、软件具有可移植性、可集成。刘。篙鬈篡乎蠢翟麓戮襄嚣差嚣禚筹器瑟瓣篙篙未簸鼗蓑算/算善安现的载体:选用位单片机作为智能控制心片,吼控市毡屯“队删。路。幽为整个硬件系统的连接框图。实现算法六个红外接近传感器电机驱动电路红外接收装置霍尔元件检测语言录放

48、电路单片机轮予转数用来计算速度语言识别控制遥控电路电路图整个硬件系统框图?堡塑璺堡垒茎墨竺堡。兰堕堡塑型墨鲨窒?现场可编程门阵列.可编程逻辑器件当今社会是数字化的社会,是数字集成电路广泛应用的社会。数字集成电路在小断的进行更新换代。由早期的电子管、晶体管、小中规模的集成电路、发展到大规模和超大规模的集成电路,几万门以上,还有许多具有特定功能的专用集成电路。而随着微电子技术的发展,设计与制造集成电路的任务已经不完全由半导体商来独立承担。系统设计师们更希望能按照自己的意愿设计出符合自己要求的专用集成电路芯片即,且希望设计周期尽可能的短,希望在实验室里就能完成芯片设计工作,并且可以立即投入使用。就出

49、现了可编程逻辑器件。可编程逻辑器件能完成任何数字器件的功能,上至高性能,下至简单的电路,都可以用来实现。如同一张白纸或是一堆积木,工程师可以通过传统的原理图输入法,或是波形输入及硬件描述语言一般为语言或语言自由的设计一个数字系统。通过软件仿真,我们可以事先验证设计的正确性。在完成以后,还可以利用的在线修改能力,随时修改设计而不必改动硬件电路。使用来开发数字电路,可以大大缩短设计时间,减少面积,提高系统的可靠性。的这些优点使得技术在年代以后得到飞速的发展,同时也大大推动了软件和硬件描述语言的进步。一现场可编程门阵列和目前使用较多的器件为 。不同的,一家对自己的产品分类和叫法不尽相同。通常是按照结

50、构的不同来划分和的。采用的是基于乘积项的结构。而是采用的查找表? 结构。查找表简称为,本质上就是一个,目前的中多使用输入的,所以每个可以看成一个有位地址线的.的。当用户通过语言或其他方式描述厂一个逻辑电路以后,开发软件会自动计算逻辑电路的所有可能的结果,并把结果实现写入,这样,每输入一个信号进行逻辑运算就相当于输入一个地址进行叠表,然后把查找的结果输出。这种基于工艺的器件,掉电后,其上的所有数据就会丢失。因而需要一个外部的器件一般为一个或者同过机的并口,在上电时写数据到器件中,之后器件才能执行各种操作。因而不便于加密,中的数据容易破改,不利于数据的保密,对保密性要求较高的场合不适用。移力机器几

51、嵌八,系统设计瞎衽帆划算法研究. 系列器件本实验选用的是公司生产的 系列芯;。,型号为:这里考虑到以后拶展设计的需要,选用一个门数较多的芯片。可配置逻辑系列芯片内部由块,输入输出块和高效分层的通用布线通道部分构成。每个包括个,每个又由两个,两个触发器和相关逻辑构成。般把看成是最小的单元。采用.伏的低电压供电。采用新的先进的./.的工艺技术制造。具有高于器件的性能。和系列器件相似。集成度低于系列器件两者的集成范围较少有重叠,比器件密度要高。有个和与器件一样容量的块。不具有类似的差分输入输出标准。系列器件具有较高的集成度,因而拓宽了它的应用范围;内部大量的短的可连线保证了快速的布局布线时间。全局时

52、钟布线资源:有个专用的全局低斜率的时钟缓冲器。他们有专用的输脚,其中个位于中上部,另外个位于中下部。有附加的公共资源,这些资源是用来分配低斜率/高扇出控制信号的,如附加的时钟、时钟使能、三态控制和复位。控制信号在器件内的分配在内即可完成。在片时钟分配:时钟在片内分配会带来延时,大的芯片时钟延时就较大。:用来调整时钟信号使得输入和时钟同步。个,一 ?是通过在时钟网络中插入延迟直到时钟输入的上升沿和时钟反馈的上升汾一致为止来产生作用的。这就要求一个好的时钟分配网络,以便丁可以保证时钟的沿同步的到达各个部分。可以方便的和其他器件接。图是典型的电路连接方式。系列器件的多种特性,使得我们町以方便可靠的实

53、现各种应用电路。移动机册人嵌入,系统设训与路秤规划算法研究.心殴产、. . :图 典型的电路连接图工具:本设计中使用的设计输入、综合及布局布线工具是的版,仿真工具使用的是公司的 .版本。基本开发流程;设计仿真;基本开发流程主要包括设计输入设计综合;布局布线&;配置/五个主要步骤。设计输入主要有原理图输入和输入两种方式,一般开发商都同时支持两种输入方式。有些熟悉硬件设计的工程师开始喜欢利用原理图进行设计,这种方法非设常直观,但基于可移植性和规范化方面的考虑,绝大部分深入设计和计的:程师最终都将统一到 平台上来。砹训仍真包含功能仿真利时序仿真两项主要内容,功能仿真忽略了综合和布局布线导致的时延等因

54、素,仅仅从逻辑上进行仿真,这对设计思路的验证足有帮助的,;须通过口寸序仿真作进一步验证,发现并修正时序问题。发叫综合将语言生成用于布局布线的网表利相应的约束。综合效果直接导敛发计的性能利逻辑门的利用效率,凶此,许多可编程逻辑器件开发商都支持第三力综合矛仿真上具,著名的有:、和等。壁塑坐鲨垒壁垒查墨堕堡生兰堕堡塑型兰鲨婴塑?一布局布线工具利用综合生成的网表,在内部进行布局布线,并牛成用丁配置的比特流文件。布局布线工具与可编程逻辑器件工艺及其布线资源密切相关,一般由可编程逻辑器件开发商直接提供。幻中能从狮科的其斌怄尉励蹄有吨蜘删叫驷揽据载骄靳札罐黼耗一一一一虢一一一一一一一一一一一一一一一一一一一

55、一. 及其外围电路连接框图由于器件采用的是工艺,在断电的情况下内的配善数塑搏叁量描?。中的配置数据装载八粪瓣在詈罐勰霖箬嚣蒹系统嬲淼爨妻慧塑嚣繁中,上电时由控制电路控制将兼容的本文采用的是,连接如图所示。二极管状态.按键开关直流电源指示灯。稳压器.稳压器?并口万门端口/缓厅面程序控冲一器 制转换开关扩展端口图 及其外围电路连接框图移动机器人嵌入,系统设计与路径规划算法训究及其外围电路连接的电路图图图 及其外围电路连接的电路图一圃根寄尝琳骚曩堪渚竹魁崭嘶韬摧、咚嚣需漤移动机器凡溢入系统设计与路杼坍划算法研究位单片机控制器及其外围电路的设计自上述可以看出,传感器得到的外界环境信息,传给进化芯片,由

56、芯片里的遗传规划算法运行得出两轮电机的速度,然后由单片机控制电机的动作。机器人是如何不重复的走遍整个房间地面,是由运行在单片机的交叉自律行走的算法控制的。本文采用凌阳公司的位单片机作为控制芯片。. 位单片机随着单片机功能集成化的发展,其应用领域也逐渐地由传统的控制,扩展为控制处理数据处理以及数字信号处理 等领域。凌阳的位单片机就是为适应这种发展而设计的。它的内核采用凌阳最新推出的 位微处理器芯片以下简称“。围绕“所形成的位系列单片机以下简称“家族采用的是模块式集成结构,它以内核为中心集成不同规模的、和功能丰富的各种外设接口部件如图所示。图 ”家族的模块式结构在.工作电压范围内的工作速度范围为.

57、,较高的工作速度使其应用领域更加拓宽。字字仅占一页存储卒间,埘位可编程的多功能/端:两个位定时器/计数器;实叫时钟:低电压复位/监测功能:通道位模一数转换输入功能并具有内置自动增益控制功能的麦克风输入方式:双通道位方式的音频输出功能等。是适用于数字声音和语音识别产品的一种最经济的选择。 共有个引脚封装形式为,它的排列如图所示。引脚排列图的结构图.在本文中单片机及外围电路连接图图所示为单片机及外围电路系统,包括单片机最小系统部分、电机驱动部分、录放音驱动部分、自动寻找充电器电路部分以及电源部分。下面将详细介绍一一下自动寻找充电器电路部分。龆:出一;凸?一一一;曲碳摩燃竦囊留婶士魁轿峨懈高缔罨需绺?一一:;土;、一移巩帆:琳、隈入,二系统.训路径觇划贸研究.移动机器人自动寻