（信号与信息处理专业论文）自主式移动机器人进化行为研究及设计.pdf

自主式移动机器人进化行为研究及设计 自主式移动机器人进化行为研究及设计 摘要 进化机器人是嵌入了进化算法的具有较强环境适应能力的机器人，属于智能机器人研究中 比较新的领域，能够很好地解决移动机器人学习与适应能力方面的问题。 本文首先介绍了进化机器人的发展概况，结合自主式移动机器人的特点，阐述了国内外自 主式移动机器人进化行为的研究现状，简要介绍了几种常用进化算法的原理和特点。 然后，本文研究了进化算法，提出了本文使用的算法神经网络和遗传算法相结合的进 化算法。 本文重点研究了自主式移动机器人的进化行为自主避障的具体实现。设计了三轮移动 机器人，用凌阳单片机s p c e 0 6 1 a 实现神经网络控制器，神经网络的权重用遗传算法进行优化。 遗传算法由计算机软件实现，通过串口与单片机进行数据传输。然后进行了机器人进化避障的 实验。机器人在完全未知的环境下运行，通过对环境的感知和不断的学习，完善自身的适应能 力，依靠与环境不断的交互来获得知识，并通过反复调整自身的行为，最终学会在未知环境中 自主避障。 本文结合自主避障的进化实验，对进化算法的基础遗传算法的硬件化实现进行了探讨， 提出了一个能进行群体存储、适应度处理、选择、交叉和变异等操作的硬件结构，设计拟采用 x ili n x 公司的f p g a 芯片x c 2 s 2 0 0 实现，能有效地缩短运行时间，在进化机器人方面有广泛 的应用。 最后，本文对与进化机器人有关的几个问题进行了探讨，并作了总结与展望。 关键词：自主式移动机器人；进化；遗传算法；避障；f p g a ；神经网络控制器 自主式移动机器人进化行为研究及设计 t h er e s e a r c ha n dd e s j g no fe v o iu t i o n a r yb e h a v i o r f o ra u t o n o m o u sm o biier o b o t a b s t r a c t e v o l u t i o n a r yr o b o t ( e r ) i st h er o b o tu s i n ge v o l u t i o n a r ya l g o r i t h ma n dh a s t h e a b i l i t yt oa d a p tt od y n a m i ce n v i r o n m e n t i tc a ns o l v et h ea b o v ep r o b l e mw e l l t h i sp a p e rf i r s ti n t r o d u c e st h ed e v e l o p i n gh i s t o r yo fe ra n dt h er e s e a r c hs t a t u s q u oh o m e 卵da b r o a d ，a n dd e s c r i b e sp r i n c i p l ea n dc h a r a c t e r i s t i co fs e v e r a le v o l u t i o n a r y a l g o r it h m s t h e nt h ep a p e rr e s e a r c h e si n t ot h ee v o l u t io n a r ya l g o r i t h m t h ea l g o r i t h me m p l o y e d b yt h ep a p e r ( g e n e t i ca l g o r i t h mc o m b i n e db ya r t i f i c i a ln e u r a ln e t w o r k ) i sp r e s e n t e d a f t e re x p o u n d i n gt h eg e n e t i ca l g o r i t h m ( g a ) a f t e r w a r d st h ep a p e rs t u d i e st h er e a l i z a t i o no fe v o l u t i o n a r yb e h a v i o r - - o b s t a c l e a v o i d a n c e at h r c c l h e e l e dm o b i l er o b o ti sd e s i g n e d t h en e u r a lc o n t r o l l e ri sd i s c u s s e d i ne m p h a s i si nt h ep a p e r ，i ti sr e a l i z e dm a i n l yb ym c ua n dw e i g h tv a l u e sa r eo p t i m i z e d u s i n gg e n e t i ca l g o r i t h m ，w h i c hi sr e a l i z e do nt h ec o m p u t e rb e c a u s eo ft h ec o m p l e x i t y o ft h ea l g o r it h ma n dt h ed a t ac a nb et r a n s p o r t e db ys e r i a lp o r t f i n a ll yt h ee x p e r i m e n t p r o v e st h ed e s i g nc a nm a k er o b o ta v o i dt h eo b s t a c l ef r e e l y t h ep a p e rd i s c u s s e st h eh a r d w a r ei m p l e m e n t a t i o no fg e n e t i ca l g o r i t h n nah a r d w a r e a r c h i t e c t u r eb a s e do nf p g a ( f i e l dl t o g r m m a b l eg a t ea r r a y ) i sp r e s e n t e d ，w h i c hi s c a p a b l eo fp o p u l a t i o ns t o r a g e ，s e le c t i o n ，c r o s s o v e r ，m u t a t i o na n df i t n e s se v a l u a t i o n t h ed e s i g nu t i l i z e sx i l i n xf p g ax c 2 s 2 0 0 ，w h i c hs h o r t e n sp r o c e s s i n gt i m ea n dh a sb r o a d a p p l i c a t i o n f i n a l l yt h ep a p e rd i s c u s s e ss e v e r a lp r o b l e m sr e l a t e dt oe ra n ds u m m a r i z e st h ep a p e r k e yw o r d s ：a u t o n o m o u sm o b ii er o b o t ：e v o i u t i o n ：g e n e t i oa i g o r i t h m ；o b s t a o i ea v o i d a n c e f p 6 a ：n e u r a in e t w o r kc o n t t o l i e r 自主式移动机器人进化行为研究及设计 0 前言 0 1概述 近几年，随着人们对机器人服务功能需求的增加，不久的将来服务机器人有可能得到很快的 发展与应用。与工业机器入相比，服务机器人有许多不同之处：大部分是自主式移动机器人： 对于准确性的要求不再是本质的；工作的模式不是重复不变的，而是不断变化的：所处的位置 是在不断变化，而不是固定的；运动是复杂的不断变化的，整个运动经常是不确定的，没有预 先设计的叶”。所以对机器人提出了较高要求：它要自己根据环境的变化，不断修正自己的行为。 为了实现这种功能，专家们将复杂系统的自适应理论“不预先规定，由环境定论”引入机 器人的设计中，即形成了现在的进化机器人。1 9 9 3 年，“进化机器人学( e v o l u t i o n a r yr o b o t i c s , z r ) ” 这一术语首先由c l i f i e ，i - i a w e y 和h u s b a n d s 提出阻”。 进化机器人属于人工智能研究的范畴。长期以来，设计具有类似人类智能的机器一直是人 工智能、智能控制的研究目标。8 0 年代以来，各国政府相继制定了关于智能机器人的研究和发 展计划。尽管在机器人控制、计算机视觉、传感器等领域获得了大量的成果，但是由于对人类 感知、认知和计算机硬件技术缺乏正确的认识，对困难估计不足，有不少研究项目没有达到预 期目标1 5 1 。9 0 年代初，研究者们反思这l o 年来的研究历程，重新制定了更加实际、面向应用任 务的研究目标。机器人智能化主要表现在自主性和适应性两个方面，要求机器人能独立工作， 并适应环境变化。因为自主机器人与外界环境交互，其行为方式不仅决定系统能否完成任务， 还影响到后续的传感器输入。行为的长期效果和环境的不确定性使人们难以预测交互的结果。 机器入各部分的协调工作( 包括机械和控制系统) 也很复杂，而控制器的复杂程度随着系统部 件、模块之间交互的增加而增加。如何有效、简便地实现具有适应能力的自主机器人，成为研 究热点之一。进化机器人正是在这样的背景下提出的，有望成为一种合理、经济的自动化设计 方法。 进化机器人是嵌入了进化机制的具有较强环境适应能力的机器人，属于智能机器人研究中 比较新的领域。它受达尔文自然进化和优胜劣汰的思想启发，把机器人作为一个自主个体，在 与外界环境的交互中生长、发展、进化 a - s 。这个进化过程是一个类似于自然生命系统的自组织 过程，不受人为因素的干预。由于它具有简洁的结构和高度的自主能力，这一方向正受到越来 越多的国内外专家学者的重视。 自主式移动机器人的目标是在没有人的干预、无需对环境做任何规定和改变的条件下，有 目的的移动和完成相应的任务【9 】。现有移动机器人存在的主要问题是缺乏灵活性和自主性，典 型的例子是大多数机器人都是在高度结构化的环境下执行预先规定的动作，在新的环境下或遇 到意外情况时，便不能很好的完成任务。引发问题的主要原因是周围环境是非结构化的，存在 不确定性，具体体现在：关于环境的先验知识通常是不全面的，不确定和近似的；感知器得到 的信息通常是不可靠的，存在着噪声和测量误差；现实的环境通常具有复杂和不可预测的动态 自主式移动机器人进化行为研究及设计 特性，如物体的移动，环境的改变；控制作用并非完全可靠，如车轮打滑等等。为了解决上述 存在的问题，传统的解决方法是精心设计机器人的机械和传感装置，或对环境做详细的规定和 构造，或兼而有之，但带来的问题是提高了成本，降低了机器人的自主性，难以适用于任意的 环境。因此，目前移动机器人的研究重点是设计一种良好的控制结构，应具有主动学习和自适 应的能力，能克服环境的不确定性，可靠的完成复杂任务，且成本低，鲁棒性好。由进化机器 人的特点可以得知，进化机器人能够达到这一要求。 0 2 国内外自主式移动机器人进化行为研究现状 近十年来，职引起了许多研究人员的关注，其中以欧洲和日本的研究机构最为活跃，如瑞 士的l a m i ，e p f l 实验室、意大利的g p a l 研究小组、英国s u s s e x 大学进化研究中心、日本s o n y 公司等。1 9 9 3 年以来，一年一次的进化机器人学研讨会促进了该领域研究者之间的交流合作以 及e r 与生物学、神经生理学、人工生命等相关学科研究成果的融合 i o - - 】。目前，职应用研究还 只限于小规模的较为简单的问题，所采用的机器人也大多是小型的。典型的实验包括自主避障、 趋光性研究、自充电行为、模拟收集垃圾行为、视觉目标定位等。e r 研究的问题涉及系统的各 个方面，包括控制器结构、编码策略、进化操作、适应度函数的选取、个体学习、协进化、多 足机器人、硬件进化、e r 方法论等。 1 9 9 4 年前后出现了少数e r 应用实例。近年来，简单、小巧、灵活、模块化的新型机器人 的出现为进化技术应用于机器人控制器的设计提供了便利的实验条件。进化机器入学尝试着从 另一个角度来考虑全局目标和反射行为的结合问题，以提高系统的自主性和适应性。 图0 1 进化机器人研究平台k h e p e r a 图0 1 是瑞士研制的k h e p e r a ，是由两个直流电机驱动的两轮自主移动机器人，车身装有红 外线传感器，许多研究机构都购买这种机器人用来做进化行为研究的平台。德国的p e t e r n o r d i n 与w o l f g a n gb a n z h a f 使用进化方法实现了机器人避障及沿墙走。他们采用的进化算 法是遗传规划( g p ，g e n e t i co r o g r a m m i n g ) 。g p 算法实质是用广义的层次化计算机程序描述问 自主式移动机器人进化行为研究及设计 题，基本思想和遗传算法相类似，通过随机产生初始群体，然后对群体进行自然选择、交叉变 异，最终优胜劣汰，自动生成性能较好的计算机程序【1 4 】。g p 应用领域非常广，但目前的水平还 不能产生非常完善的程序。 图0 2 进化机器人研究平台 e n g h i s 图0 2 是六足g e n g h i s 机器人，由西班牙加泰罗尼亚理工大学( 简称u p c ) 研制。其中每条腿由 两个电机驱动( 水平方向和垂直方向) ，每个电机上装有压力传感器；机身装有五个摄像头、两 个触须，纵向装有倾角计；前腿和后腿装有红外接近传感器。控制器以四片m o t o r o l a 单片机 6 8 h c l l 为主。1 9 9 0 年，p a t t i em a e s 用增强学习策略( r e i n f o r c e m e n tl e a r n i n g ) 实现六足g e n g h i s 机器人的步态协调“”。这种算法基本原理为：如果某个行为策略会产生正的奖励，那么机器人 产生这个行为策略的趋势将会加强；如果某个行为策略导致环境负的奖励，那么机器人产生这 个行为策略的趋势将会减弱，最终消亡。由于强化学习不像有教学习那样有教师信号，它仅有 一个强化信号来判断动作的好坏，所以它的学习过程必定是漫长的。 图0 3 进化机器人研究平台0 c t i b t a k a s h ig o m i 又用进化的方法在图0 3 所示的八足o c7 卜l b 机器人上实现步态协调。采用 了较先进的基于生态竞争模型的遗传强化学习算法。这种算法引入子群概念，将完整种群分为 若干子群，每一子群执行自身的竞争算法( e c a ) 。e c a 根据配对个体的行为将个体间的关系分为 伙伴和对手两种。伙伴个体通过遗传交配生成新个体，这是算法中个体的先天遗传进化。对手 自主式移动机器人进化行为研究及设计 个体之间同时存在相互激活与竞争行为，结果是对手个体的表现型被动态地自适应调整，这是 个体的后天竞争学习 1 6 - 1 7 。e c a 步骤如下： s t e p1 选择伙伴个体。以代表个体为父本，再按照门当户对原则，选出一个最接近于父本的 个体作为母本，父本和母本成为一对伙伴； s t e p2 伙伴个体间进行交叉、变异等遗传操作，生成新个体： s t e p3 运用取代机制进行群体更新； s t e p4 对手个体竞争； s t e p5 子群规模调整。 这种进化算法比较先进，但是非常复杂，实现会比较困难。 自上世纪九十年代起，s w i s sf e d e r a li n s t i t u t eo ft e c h n o l o g yi nl a u s a n n e 、u n i v e r s i t y o fs u s s e xa tb r i g h t o n 、u n i v e r s i t yo fs o u t h e r nc a l i f o r n i a 等大学相继报告了自主机器人 人工进化的尝试叫l 。这些研究的成功尝试带动了欧洲、日本及美国的一大批研究者进行进化机 器人的研究。近几年，来自不同领域( 包括a t 智能、机器人、生物工程、认知科学以及社会行 为学) 的科研工作者也越来越多地投入到进化机器人的研究热潮中。 在进化机器人试验中，大多数的研究者都没有考虑机器人形体的进化( 他们都假定机器人在 进化过程中形体不变) ，而只是进化了机器人控制系统。但也有- - d 部分的研究人员同时进化了 机器人的形体和控制系统。k a r ls i m s 、j o r d a np o l l a c k 、p a o l of u n e s 就是其中的小部分人。 k a r ls i m s 在虚拟的世界中( 遵循牛顿物理定律) 进化了一个会游泳和爬行的生物，其评价函数 是当生物水平移动时就给与相应的奖励，这样奖励的结果就使生物被赋予了运动能力。j o r d a n p o l l a c k 和p a o l of u n e s 进化的不是生物，而是机构，其评价函数是机构的强度d 】。机构的强 度大，其结构遗传到下一代的可能性就大。他们把最后的仿真结果用l e g o 积木块搭建起来，证 明进化的机构比人工设计的机构强度要大得多。 国内在进化机器人方面还处于研究阶段，也已取得了一些研究成果。我国2 0 0 1 年国家自然 科学基金指南己将“机器学习与进化机器人”列为鼓励研究领域。中南大学的蔡自兴教授对自 主移动机器人的进化控制体系作了深入研究m 1 。浙江工业大学的杨东勇教授在进化算法方面取 得了研究成果呻1 。中国科技大学的杨杰教授和香港浸会大学合作进行了“分布式自主移动机器 人群体行为的智能进化”项目的开发呻1 。 进化机器人学是设计机器人的一种新方法，缺乏严格的定义和公式化描述，目前在进化自 主机器人的控制系统时，常用的研究方法有两种。一种是直接进化真实的实体机器人：另一种 是借助于仿真系统，在仿真环境里进化机器人控制系统，进而把仿真的进化结果转变成真实的 机器人。两种策略各有利弊。第一种方法无疑是耗时的；而第二种策略虽然可以加快进化的步 伐，但是仿真环境毕竟只是实际环境的简化，现实环境中的很多动力学因素很难在仿真环境里 再现，因此，有时在仿真环境里工作良好的控制器在真实环境中却是失败的。不过，这种由于 模型不匹配造成的性能下降可以在后续的进化中加以改进。近几年，有些研究人员已经成功地 4 自主式移动机器人进化行为研究及设计 证实了第二种方法的有效性。这样，大大减少了对真实机器人的进化代数，既减少了时问，又 能保证最终结果满足要求。 进化机器人的优势在于简化了控制器设计中人的工作，将机器人系统及其行为看成一个整 体，与传统机器人相比，进化机器人具有较强的环境适应性、快速性、灵活性、鲁棒性以及更 高的智能水平。作为一个新型的研究领域，进化机器人学中还有很多问题需要解决。包括：仿 真模型、进化时间、硬件保障和行为评价等。当机器人结构、环境、任务等向复杂化方向发展 时，上述问题就显得更为突出。将人工智能技术与进化计算结合起来，也许会为进化机器人方 法提供一种新的思路。随着复杂系统动力学的进展和计算机运算速度的极大提高，进化机器人 方法将会应用到环境更为复杂、智能水平要求更高的问题求解中去。 0 3 本文研究内容 本文在研究进化算法的基础上，搭建了机器人硬件平台，实现了机器入逐渐进化的避障行为。 重点实现了神经网络控制器，其中控制器主体由1 6 位单片机s p c e 0 6 1 a 实现，而神经网络的权 值优化方法遗传算法则由计算机实现。在进化实验的基础上，对进化算法的基础遗传 算法的硬件化实现做了探讨，以x i l i n x 公司的f p g a 芯片x c 2 s 2 0 0 为硬件载体，采用了自顶向 下和模块化设计的方法，用硬件设计语言v e r i l o gh d l 设计了各模块并进行了仿真，在进化机 器人方面将有广泛的应用。 本文第一章对进化算法做了研究，通过对遗传算法的详细论述，引出了本文使用的进化算法 神经网络和遗传算法相结合的算法。 第二章对自主式移动机器人的进化行为自主避障的实现做了研究，在设计机器人平台的 基础上，用微处理器实现了神经网络控制器，神经网络的权值采用遗传算法优化，使机器人慢 慢进化学会避障行为，其中遗传算法由计算机软件实现。 第三章对遗传算法的硬件实现作了探讨，对算法各模块的具体实现作了研究并进行了仿真。 第四章对现今进化机器人研究的几个问题做了分析。 自主式移动机器人进化行为研究及设计 1 进化算法研究 进化机器人的思想主要来源于进化计算。进化计算基于对自然界生物进化机制的模拟，是 以进化原理为依据，在计算机上实现的具有进化机制的算法和程序。目前，进化计算偏重于算 法的研究，因此也称之为进化算法口”。进化计算是一种通用的问题求解方法，它采用某种编码 技术来表示各种复杂的结构，并将每个编码称为一个个体。一个一定数目的编码集合，称为种 群，并通过对种群中的每个个体进行某种遗传操作( 变异、交叉、选择) 来模拟进化过程，最 终获得一些具有较高性能指标的编码。其中，变异是模拟自然界中生物遗传物质的变异，交叉 是模拟有性生殖过程中的染色体交换过程，选择则是模拟自然界的优胜劣汰过程。当前主要的 进化计算方法有3 个分支：遗传算法、进化编程、进化规划m 】【2 0 】。其中遗传算法是进化机器人 的应用基础。 1 1 进化算法的基础：遗传算法 1 1 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是近年来迅速发展起来的一种全新的随机搜索与优化 算法，其基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学说。该算法南密执安太学教授 h o l l a n d 及其学生于1 9 7 5 年创建。此后，遗传算法的研究引起了国内外学者的关注。白1 9 8 5 年 以来，国际上已召开了多次遗传算法的学术会议和研讨会，国际遗传算法学会组织召开的i c g a ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ch l g o r i t h m s ) 会议和f o g a ( w o r k s h o po i lf o u n d a t i o n o fg e n e t i ca l g o r i t h m s ) 会议，为研究和应用遗传算法提供了国际交流的机会口”。我国对于遗 传算法的研究从2 0 世纪9 0 年代以来一直处于不断上升的时期，特别是近年来，遗传算法已被成 功地应用于工业、经济管理、交通运输、工业设计等不同领域，解决了许多问题。 与传统搜索算法不同，遗传算法从一组随机产生的初始解，称为群体，开始搜索过程。群体 中的每个个体是问题的一个解，称为染色体。这些染色体在后续迭代中不断进化，称为遗传。 遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体，称为后代。 染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体，作 为下一代群体，再继续进化，这样经过若干代之后，算法收敛于最好的染色体，它很可能就是 问题的最优解或次优解。遗传算法中使用适应度这个概念来度量群体中的各个个体的在优化计 算中有可能到达最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定 义一般与具体求解问题有关。 遗传算法的处理流程如图1 1 。 遗传算法的处理流程如图1 1 。 6 自主式移动机器人进化行为研究及设计 1 1 2 编码问题 图i 1 遗传算法的处理流程 编码是遗传算法要解决的首要问题。h o l l a n d 的编码方法是二进制编码，它具有下列一些 优点：编码、解码操作简单易行、交叉、变异操作便于实现、符合最小字符集编码原则、便于 利用模式定理对算法进行理论分析。但对于许多遗传算法的应用，这种简单的编码方法很难 直接描述问题的性质，近十年来，针对特殊问题，人们提出了其它编码方法。例如： 实数编码：对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体 将会带来些不利，例如，二进制编码存在着连续函数离散化时的映射误差，同时不便于反映 所求问题的特定知识。为了克服这些缺点，人们提出实数编码方法，即个体的每个基因值用实 数表示。实数编码方法的优点如下：适合于遗传算法中表示范围较大的数：便于较大空问 的遗传搜索：提高了遗传算法的精度要求；改善了遗传算法的计算复杂性，提高了运算效 率；便于算法与经典优化方法的混合作用；便于设计专门问题的遗传算子n 4 】。 7 自主式移动机器人进化行为研究及设计 1 1 3 交叉运算 交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个 新的个体【2 0 】。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作 用，是产生新个体的主要方法。遗传算法中，在交叉运算之前还必须对群体中的个体进行配对， 目前常用的配对策略是随机配对。下面介绍几种适用于二进制编码或实数编码的交叉运算。 ( 1 ) 单点交叉又称为简单交叉，它是指在个体编码串中随机设置一个交叉点，然后在该点相 互交换两个配对个体的部分基因【2 l 】。 ( 2 ) 双点交叉它的具体操作过程是：在相互配对的两个个体编码串中随机设置两个交叉 点；交换两个交叉点之间的部分基因】。 ( 3 ) 均匀交叉它是指两个配对个体的每一位基因都以相同的概率进行交换，从而形成两个新 个体。 1 1 4 变异运算 变异运算，是指将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个 体口”。遗传算法引入变异的目的就是：一是使遗传算法具有局部的随机搜索能力。当遗传算法 通过交叉算子己接近最优解的邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优 解收敛。二是引入新的基因，使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。交 叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。下面介绍几种常 用的变异操作方法。它们适用于二进制编码和实数编码的个体。 ( 1 ) 基本位变异它是指对个体编码串以变异概率p 随机指定某一位或某几位来替换个体中每 个基因洲。 ( 2 ) 均匀变异它是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率变化2 ”。 ( 3 ) 高斯变异它是指进行变异操作时，用均值为h ，方差为o2 的正态分布的一个随机数来替 换原有基因值。具体操作过程与均匀变异类似2 ”。 1 1 5 选择运算 遗传算法使用选择运算( 或称复制运算) 来实现对群体中的个体进行优胜劣汰操作：适应 度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率 小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。下面介 绍几种选择方法。 1 ) 赌盘选择又称比例选择方法2 0 】。其基本思想是：各个个体被选中的概率与其适应度大小 自主式移动机器人进化行为研究及设计 成正比。具体操作如下： ( 1 ) 计算出群体中每个个体的适应度f ，i = 1 ，2 ，m ，m 为群体大小； 吖 ( 2 ) 计算出每个个体被遗传到下一代群体中的概率a = 只只； f = l ( 3 ) 计算出每个个体的累积概率； ( 4 ) 在 0 ，1 区间内产生一个均匀分布的伪随机数，若r a ，则选择个体1 ；否则，选择个 体屯使得：研1 ， 岛成立。 2 ) 竞争选择 竞争选择方法也是一种基于个体适应度之间大小关系的选择方法。其基本思想是每次选取n 个个体之中适应度最高的一个个体遗传到下一群体中。一般情况下n 的取值为2 。具体实现：从 群体中随机选取n 个个体进行适应度大小的比较，将其中适应度最高的个体选中参与交叉变异： 将上述过程重复m 次，就可以得到下一代群体中的m 个个体。每个个体都有被选中的概率，而且 适应度越大，个体被选中的概率就越大，符合遗传算法的思想。 1 1 6 适应度函数的设计 遗传算法使用适应度来度量群体中各个个体在优化计算中有可能达到或接近于找到最优解 的优良程度。适应度较高的个体遗传到下一代的概率就大；而适应度较低的个体遗传到下一代 的概率就相对小一些。遗传算法在进化搜索中基本不用外部信息，使用适应度函数为依据，通 过一个反复迭代过程，最终得到问题的最优解或近似解。对适应度函数的唯一要求是，针对输 入可计算出能加以比较的非负结果。 1 2 本文采用的进化算法：神经网络与遗传算法结合 近年来，神经网络已经被广泛应用于智能控制、系统优化、信号及信息处理、图像处理、模 式识别等领域 “。神经网络传统的权值获取方法一般采用基于梯度下降的方法【2 4 1 ( 如b p 算法) ， 都是采用确定的权值变化规则，在训练中逐步进行调整，最终得到交互的权值分布。这些传统 的方法对初始权向量异常敏感，不同的初始权向量值可能导致完全不同的结果，而且在具体计 算过程中，有关参数的选取只能通过实验和经验来确定，一旦取值不当，又会引起网络的振荡 而不能收敛；即使能收敛也会因为收敛速度慢而导致训练时间过长，或是陷入局部极值而得不 到最佳权值分布。 目前将遗传算法与神经网络结合起来，特别是用遗传算法优化设计神经网络的连接权重矢 量已成为神经网络研究的一个方向。利用遗传算法优化设计神经网络，能够解决上述传统的优 化方法带来的问题，能够比其他的神经网络设计方法更广泛地搜索空间，并且遗传算法能在搜 索中自动获取和积累有关搜索空间的知识，自适应地控制搜索过程，以得到适合求解问题的最 9 自主式移动机器人进化行为研究及设计 优的神经网络1 2 4 - 2 5 1 。 将遗传算法( g a ) 与神经网络( n n ) 结合，可以使神经网络( n n ) 系统扩大搜索空间、提 高计算效率以及增强n n 建模的自动化程度。这种结合不仅使神经网络具备了学习和进化性能， 表现出更强的智能，而且可以解决神经网络设计和实现中存在的一些问题，使神经网络具有更 优的性能。 g a 与n n 融和的步骤： 用染色体表示结构与参数，定义g a 的适应度函数，并初始化n n ； 训练由g a 得到的神经网络( n n ) ； 计算适应度值： 根据适应度值进行遗传算子操作，调整神经网络权重及其各参数： 在不断进化中，调整遗传算子操作方式和控制参数，以便生成更有效的基因型。 本文将上述原理应用到进化机器人中，以神经网络做进化机器人的控制器，用遗传算法对 控制器进行优化。 图1 2 为本文采用的进化方法框图。如图所示，s e n s i n g 代表机器人配置的传感器从外界环 境中得到的数据，将数据输入到神经网络，经过计算，得出机器人的动作( a c t i o n ) ，通常机 器人的动作表现为两轮电机的转速。神经网络的权值初始状态是随机的，由遗传算法慢慢优化， 最终得到最优个体，使机器人完成预定的行为，本文预定的行为是自主避障。 图1 2 设计采用的进化方法框图 1 0 自主式移动机器人进化行为研究及设计 前向神经网络是目前研究最多的一种神经网络模型，可以学会任何复杂型的映射，因此这 种神经网络应用范围很广泛【2 6 】。本文进化方法中的神经网络即采用前向神经网络。 针对前面论述的遗传算法，为了设计方便，本文进化方法中选用的各项遗传操作为： 编码方式：二进制编码。 交叉操作：单点交叉，交叉概率：0 1 。 变异操作：基本位变异，变异概率：0 6 。 选择操作：竞争选择。 群体规模：2 0 ，个体长度：1 6 。 算法过程如下： ( 1 ) 将神经网络各层的权值按顺序排列，作为一个个体的基因链； ( 2 ) 随机初始化n 个个体，形成群体第一代； ( 3 ) 对每一个个体，将其基因链解码到神经网络中，以此作为控制器，控制机器人从运动。 计算适应度值； ( 4 ) 应用选择、交叉和变异算子产生新一代，并保留上一代中最优秀的个体；重复步骤( 3 ) 、 ( 4 ) ，直到得到要求的结果。 1 3 本章小结 进化算法是研究进化机器人的基础，也是关键。本文通过对进化算法的基础遗传算法 的详细阐述，引出了采用的进化方法一神经网络和遗传算法相结合的方法，即以神经网络作 为控青0 器，采用遗传算法进行学习，它具有神经网络的各项优点，同时不会导致陷入局部极小。 此外，这种控制方案将传感器数据融合与控制合为一体，进一步简化了控制结构。 自主式移动机器人进化行为研究及设计 2 自主机器人的进化行为自主避障的具体实现 目前，进化行为的应用研究只限于小规模的较为简单的问题，所采用的机器人也大多是小 型的。典型的实验包括自主避障、趋光性研究、自充电行为、模拟收集垃圾行为、视觉目标定 位等。本章主要围绕机器人的设计，说明进化行为一自主避障的具体实现。 对移动机器人的避障已经有较多的研究，如u l r i c hn e h m z o w 采用电机神经元( a r t i f i c i a l m o t o rn e u r o n ) 控制的方法使移动机器人在障碍物回避时非常迅速可靠，s h i g e m in a g a t a 等采用 分层神经网络控制的方法使机器人达到了障碍物回避的目的1 2 7 1 。这都需要建立机器人的移动规 则。自主型移动机器人所面临的环境是动态的、未知的，如果预先建立各种机器人的移动规则， 首先很难保证这些规则在真正的运行中的有效性，况且如此多规则的查询将花费较多的时间， 也将占用较多的存储器空间。为了连续、平滑的回避障碍物，本文采用遗传算法进化神经网络 控制器的方式来实现避障。 2 1 进化机器人系统设计 图2 1 是设计的进化机器人系统结构。由图所示，系统的主体是神经网络控制器，由单片机 s p c e 0 6 1 a 实现；神经网络的权重由遗传算法进行优化，由于遗传算法的实现比较复杂，因此 专门由计算机软件完成。计算机和单片机通过串口进行数据传输。系统的实现过程为：传感器 信息模块得到的传感器数据送入神经网络控制器，得到机器人两轮的速度，从而可以控制机器 人的运动。由遗传算法优化神经网络的权重，慢慢使机器人学会自主避障。 2 2 机械结构设计 图2 1 机器人系统结构 陬i 习 i 运动i 1 _ j 图2 2 机器人机械结构 1 2 自主式移动机器人进化行为研究及设计 如图2 2 ，机器人车身呈圆形，由左、右轮及一万向轮组成。左右轮分别由直流电机驱动 可以前后任意转动。 2 3 传感器设置 1 ) 红外接近传感器 综合考虑，实验机器人采用t a 个红外接近传感器，分布情况如图2 3 所示，其中箭头所 指的方向是机器人前进的方向。传感器检测距离大约为l o c m ，输出信号随着检测距离的变化而 变化。机器人根据这些红外接近传感器感知周围障碍物的存在，将传感器的信号输入到运动控 制器中，得到两驱动轮电机的速度，从而控制机器人的动作。 a 图2 3 红外接近传感器分布图 2 ) 霍尔元件 在机器人进化过程中，适应度值的计算要求知道两轮的速度。速度是通过霉尔而件得到的。 霍尔元件是一种很好的可用于车轮转数计数的传感器。它固定安装辐戮靖豁i 每襻籍： 交 装l o 个小永磁铁，车轮每转一圈，永磁铁经过霍尔元件1 0 次即在信号端产生l o 个计量脉冲。 信号直接送单片机控制器的i o b 3 作外部中断源，在中断程序中通过处理数据会得到速度的值。 本文选用的霍尔元件型号为a 3 1 4 4 e 。图2 4 为霍尔元件的电路连接图。 。了 图2 4 霍尔元件的电路连接图 自主式移动机器人进化行为研究及设计 2 4 进化机器人控制系统设计 研究人员普遍认为在各种控制结构中，人工神经网络具有更多优势。根据进化行为类型的 不同( 简单反射式行为、简单非反射行为和动态复杂非反射行为) ，可以选用不同的神经网络结 构( 多层前馈网、递归结构等等) ，或者由进化计算来优化网络结构【2 ”。 通过综合考虑，本文采用神经网络控制器，神经网络选用两层前馈网络，且由遗传算法来 优化网络权值。其中神经网络控制器决定由单片机实现，而由于遗传算法过程比较复杂，且单 片机的速度及处理能力有限，因此决定遗传算法在计算机上仿真，仿真后的结果通过串口传给 控制器。但是遗传算法的硬件化实现也是可能的，在第三章中重点探讨了遗传算法的硬件化实 现。 2 4 1 控制系统设计思想 进化机器人控制系统的设计思想如图2 5 所示。 图2 5 进化机器人控制系统的设计思想【3 l 首先，随机生成具有不同人工染色体( 在本实验中指神经网络控制器的权重) 的初始机器 人种群( 第0 代) ，并随意放置在环境中，每一个人工染色体都编码一个机器人控制系统( 神经 网络控制器) 。每一个机器人都能够根据遗传指定的特性自由动作( 移动) ，同时，其完成动作 的性能被自动评估。性能优良的机器人允许以不同的遗传方式( 变异、交叉、复制) 繁殖下一 代。这个过程重复下去，直至产生能够很好适应环境的个体。 其中适应度函数在机器人的进化过程中起到了重要的作用，适应度函数的轻微差异可能会 导致完全不同的结果。但目前并没有一个正规的理论用于适应度函数的设计。要选择恰当的适 应度函数只能靠经验和不断的试验。这里有三点经验可遵循： 自主式移动机器人进化行为研究及设计 ( 1 ) 隐含性：适应度函数应该尽可能包含最少的变量和约束。 ( 2 ) 内在性：适应度函数的计算应尽可能利用相对于个体内部的信息。 ( 3 ) 行为性：适应度函数的设计应尽可能与机器人的行为动作相关联。 初始人工染色体种群被编码成相应的控制器，每个控制器相应的控制放置在环境中的机器 人。适应度高的控制器( 人工染色体) 可以复制下一代染色体。不断进行试验，直至产生满足要 求的染色体。 在本文中，染色体为神经网络控制器的权值。 2 4 2 控制系统具体实现 2 4 2 1 神经网络控制器结构 橇八节点 图2 6 神经网络控制器结构 图2 6 为本文采用的神经网络控制器结构图。为了便于用微处理器实现，如图所示，神经网 络采用两层前向网络结构；输入层和输出层。八个输入节点，分另n 对应8 个红外接近传感器的输 出信号；两个输出节点，分别对应两个驱动轮的电机速度。神经网络的作用函数选用比例系数 为l 的线性函数。神经网络连接权( w e i g h t i j , 声 0 ，1 ，卢 0 ，1 ，7 ) ) ，用进化算法一 一遗传算法来进行优化。 8 m = 皿一+ “ ( 2 1 ) m 三 m 7 = z r , w ；+ “ ( 2 - 2 ) i = l 其中m 7 指左轮电机速度，彬指与输出节点电机0 速度相连的权重。“是偏置权重( 3 0 ) ， 指不存在障碍物时电机前进的速度。皿指第f 个红外接近传感器的输出值。其中肘指右轮电机 速度， 指与输出节点电机l 速度相连的权重 自主式移动机器人进化行为研究及设计 2 4 2 2 适应度函数的确定 在任意一时间t ，测量出两轮的速度和红外接近传感器的值，左轮速度v t 和右轮速度u 。两 轮的平均速度v f = ( h + v r ) 2 ，两轮的速度差绝对值v = i v f - v , i ， 1 r = m a x ，崛 t 时刻的适应度函数为： z = v f ( 1 一 ) ( 1 一毋) 某段时间内适应度的和为： f = 笠z = z v t ( 1 4 了) ( 1 一崛)f = z =一v ) ( 1 一崛) ( 2 - 3 ) ( 2 _ 4 ) 适应度函数由三部分所决定：向目标行进的速度、红外传感器的输出值和两轮的速度差。 两轮速度差越大，机器人转弯越明显，适应度值就越大。 此适应度函数没有考虑h 与v ，之间的大小关系，只针对环境中存在孤立障碍物的情况，不 适应存在相邻较多障碍物的环境。 2 4 2 3 控制器硬件实现 神经网络控制器以凌阳单片机开发系统为主。采用的微处理器为s p c e 0 6 1 a ，它是一种功能 强且成本低的1 6 位微处理器。其特点如下： 体积小、集成度高、可靠性好且易于扩展：把各功能部件模块化地集成在一个芯片里，内部 采用总线结构，因而减少了各功能部件之间的连线，提高了其可靠性和抗干扰能力。另外模 块化的结构易于系统扩展，以适应不同用户的需求。 具有较强的中断处理能力：中断系统支持1 0 个中断向量及1 0 余个中断源，适合实时应用领域。 高性能价格比：片内带有高寻址能力的r o m 、静态r a m 和多功能的i o il 。另外，指令系统提 供具有较高运算速度的1 6 位1 6 位的乘法运算指令和内积运算指令，为其应用增添t d s p 功 能。使得单片机运用在复杂的数字信号处理方面既很便利，又比专用的d s p 芯片廉价。 功能强效率高的指令系统：指令格式紧凑执行迅速，并且其指令结构提供了对高级语言的支 持，这可以大大缩短产品的开发时间。 低功耗低电压：采用c m o s 制造工艺，同时增加了软件激发的弱振方式、空闲方式和掉电方式， 1 6 自主式移动机器人进化行为研究及设计 极大地降低了其功耗。另外其工作电压范围大，能在低电压供电时正常工作且能用电池供电， 这对于其在野外作业等领域中的应用具有特殊的意义。 如图2 7 的s p c e 0 6 1 a 内部结构所示，具有2 k 字的静态r a m ，内置3 2 k 的快速r o m ，3 2 位可编程 并行t o n ，通用异步全双工串行接口u a r t ，具有r s 一2 3 2 标准的发送接收波形，两个1 6 位可编 程定时器计数器。其强大的功能能够满足设计神经网络控制器的功能”1 。