（电力电子与电力传动专业论文）机器人路径规划及编队问题的研究与仿真.pdf

西南交通大学硕士研究生学位论文第页 a b s t r a c t t h ed e v e l o p m e n to fr o b o tt e c h n o l o g yr e l c i r e s e n ut h el e v e lo fan a t i o n ss c i e n c e a n dt e c h n o l o g y i nt h ep r o c e s so fd e v e l o p m e n ti nt h er o b o tk e yt e c h n o l o g ya r e a ， s i n g l er o b o t si n t e l l i g e n c ea n dm u l t i r o b o t s c o o p e r a t i o na n dc o o r d i n a t i o nb e c o m e t h er e s e a r c hf o c u s s op a t h p l a n n i n ga n df o r m a t i o nw h i c hr e f e rt ot h er o b o t s e l f - p l a n n i n ga n dm u l t i r o b o tc o o p e r a t i o na r et h et w ok e yp o i n t so ft h er o b o t r e s e a r c h w h i c hi sc l o s e l yl i n k e dt ot h ed e s i g no ft h em o b i l er o b o ta n di n 血s t d a l r o b o t i t sv e r yw o r t h w h i l ef o rt h ei m p r o v e m e n to ft h er o b o t si n t e l l i g e n c ea n d a c c e l e r a t i n gt h er o b o tp r a c t i c a l i t yi nt h et h e o r e t i cr e s e a r c ha n da p p l i c a t i o n t h et h e s i sa n a l y z e st h eb a s i cp r o b l e m sa n da s s o c i a t e dt e c h n i q u e st ob es o l v e di n t h ep a t h - p l a n n i n g a c c o r d i n gt ot h ep a t h = p l a n n i n gp r o b l e m sc h a r a c t e r s ，s u c ha s c o m p l e x i t y , r a n d o m i c i t y , m u l t i r e s t r i c t i o na n dm u l t i o b j e c t i v e ，i tp r o p o s e sag l o b a l p l a n n i n gt h e o r y0 1 1r o b o t - o r i e n t a t i o nb a s e dt h ee x i s t i n gm e t h o d s i nt h ed e s i g n i n go f t h e s i n g l e r o b o tp a t h - p l a n n i n g ，t h ep a t h p l a n n i n gb a c k g r o u n da n db a s i cg e n e t i c a l g o r i t h m s ( g a ) a d o p t e di ns i n g l e r o b o ta r ec o m b i n e d ，t h u st h eg ab a s e do n b a c k g r o u n dt e c h n o l o g yi sf o r m e d t h ea l g o r i t h m sc h a n g e st h eo r i g i n a lc o d ea n d p o p u l a t i o ni n i t i a l i z a t i o nm e t h o d ，a c c o r d i n gt op a t h - p l a n n i n g ，an e wo p e r a t o ri s d e s i g n e d ，w h i c hi sr e a l i z e di nt h i st h e s i s ，a n ds i m u l a t i o nr e s u l t sp r o v et h ev a l i d a t i o n o ft h i sm e t h o d , a tt h es a m et i m e ，t h ei n f l u e n c eo f a l g o r i t h m i cp a r a m e t e r si sa n a l y z e d a n dr e s e a r c h e d b a s e do nt h es i n g l e - r o b o tp a t h - p l a n n i n gm e t h o d ，t h ec h a r a c t e ro fm u l t i r o b o t s p a t h - p l a n n i n gi sa n a l y z e d ，a n dc o - e v o h i t i o n i s m i s i n t r o d u c e d ，f i n a l l y ag l o b a l p a t h - p l a n n i n gw a yi sp r o p o s e di nt h et h e s i s t l l i sm e t h o df u l l ye x e r t st h ee s s e n c e p a r a l l e l o ft h eg a0 dt h et h e o r yo fc o e v o l u t i o n ，t h e r e f o r er e a l i z e s g l o b a l p a t h - p l a n n i n go fm u l t i - r o b o t sb yt h ec o o p e r a t i o no fp o p u l a t i o nc l a s s i f i c a t i o na n d i n f o r m a t i o ne x c h a n g e h 1t h er e s e a r c ho fm u l t i r o b o t sf o r m a t i o n t h i st h e s i sa n a l y z e st h ef o r r n a 土i o na n d c o n t r o lo fr o b o t s t e a m i tr e a l i z e sac o o r d i n a t i o nc o n t r o lm e t h o dd u r i n gt h e e x e c u t i n go ft h ec o l l a b o r a t i o nt a s k i ta d o p t sat e a mc o n t r o ls t r a t e g yw h i c hi sb a s e d o nt h ee o m b i n a t i o no ft h e “l e a d e r c o n t r o lm e t h o da n dt e a md y n a m i ca d i u s t r n e n t ， 西南交通大学硕士研究生学位论文第1 il 页 t h u si tc a ni m p r o v et h ec a p a b i l i t yh o wt h em u l t i - r o b o tt e a md e a lw i t ht h ee m e r g e n c y o nt h eb a s eo ft h i sm e 也o d a n da d d i t i o n a l l yb yc o m b i n a t i o no fr o b o t sr o l e c o n v e r s i o n ，m u l t i r o b o t sc a na c c o m p l i s ht h ec o o p e r a t i n gt a s km u c h w e l l t h et h e s i sa n a l y z e st h ef u n c t i o ns t r u c t u r eo ft h ei n t e l l i g e n tr o b o ts i m u l a t i o n s y s t e m d e s i g n st h es i m u l a t i o ns o f t w a r ew h i c hp r o v i d e st h eu s e rm u t u a l i n t e r f a c ea n d f u n c t i o nm o d e l sf o rp a t h - p l a n m n ga n df o r m a t i o nr e s e a r c h ，m o r eo v e rp r o v e st h e m e t h o d so fp a t h p l a n n i n ga n df o r i i l a t i o nb ys i m u l a t i o n k e yw o r d s ：i n t e l l i g e n tr o b o t ；p a t h - p l a n n i n g ；f o r m a t i o n ；g a ；c o o r d i n a t i o na n d c o o p e r a t i o n 西南交通大学硕士研究生学位论文第，页 1 1 机器人技术综述 1 i i 机器人发展简史 第1 章绪论 随着计算技术、电子技术、控制理论、人工智能理论、传感器技术等不断 成熟和发展，机器人概念及定义也在不断充实和创新，所涵盖的内容越来越丰 富。机器人发展沿袭两条迥异的技术路线：一是结合工业发展的需求，开发出一 系列特定应用的工业机器人( i n d u s t r i a lr o b o t ) ：另一是把机器人作为人工智能的 载体，研究机器智能( m a c h i n ei n t e l l i g e n t ) 和智能机器( i n t e l l i g e n tm a c h i n e ) 。 机器人的发展历程及学科领域建立如图i 1 所示【】。 图卜1机器人发展历程图 由于移动机器人( m o b i l er o b o t ) 在救灾，服务、医疗、娱乐、军事侦察、 扫雷排险、防核化污染等危险与恶劣环境以及民用中的物料搬运上具有广阔的 应用前景，使得世界各国自上世纪7 0 年代开始展开对它的研究1 4 1 1 5 1 移动机器 人是一个集合环境感知、动态决策与规划、行为控制与执行等多种功能的综合 系统，涵盖机械、电子、计算机、传感测控等多项技术，是多学科互相结合、 互相渗透的产物。 随着电子技术的进步，移动机器人为提高处理复杂任务和适应变化的环境 的能力，必须提高机器入的智能指标：自主性、适应性和交互性。在机器人向 西南交通大学硕士研究生学位论文第2 页 智能化的发展中，以模拟、延伸、扩展人的思维、感知、行为智能的人工智能 理论、方法与技术被引入机器人领域，9 0 年代初，智能主体研究热点与移动机 器人提高智能需求紧密结合，大范围、多层次、多方位的合作促使智能机器人 ( i n t e l l i g e n t r o b o t ) 出现。智能机器人包括反映了个体智能的单机器人系统与反 映了群体智能的多机器人系统，是对人类社会生产活动的想象和探索，在今天 的理论、技术研究中成为热点 6 - - ”j 。 1 i 2 智能机器人关键技术 智能机器人需要根据工作任务和周围环境，自主确定工作步骤和方式；具 有适应复杂工作环境的能力( 主要通过学习) ，理解周围环境和所要执行任务的 能力，做出正确的判断及操作和移动等能力；与环境、其他机器人、人类之间 获取、处理和理解信息的交互能力。因此涉及的关键技术如下 3 - - 5 1 ： ( 1 ) 机械结构：机器人适应不同作业环境的各种移动机构的设计与选型； ( 2 ) 体系结构：研究内容分别针对单机器人和多机器人，对于单机器人的 主要热点是如何融合意识行为与反射行为达到统一；对于多机器人系统主要是 研究逻辑上和物理上的信息关系和控制关系，以及问题求解能力的分布模式； ( 3 ) 导航与定位：包括机器人定位和路径规划，是机器人研究的重点； ( 4 ) 感知问题：包括环境监测与建模的传感器信息融合，是智能行动的基 础： ( 5 ) 运动控制：研究机器人现实环境下的动作控制策略与方法； ( 6 ) 交互技术：包括人机接口、机器人开发语言和机器人互联通讯技术； ( 7 ) 智能技术：是用机器人模拟人的外在认识与思维行为的技术总称，目 前热点是自动规划技术、基于传感器的智能研究、多机器人的协调与协作等； ( 8 ) 实验研究与系统软件平台开发：研制具有高度开放性、通用性、机器 人平台无关性和可扩展性的系统软件平台，对现有的零散技术成果进行系统集 成，同时为规范系统软件的设计框架提供标准。 目前国际上的研究趋势主要集中在利用传感器建立高完整性的机器人、主 动环境概念与机器人交互能力融合、多机器人系统、智能技术几个方面。本文 从机器人的导航问题出发，探索多机器人系统的协调策略，研究其中智能技术 的应用。 西南交通大学硕士研究生学位论文第3 页 1 2 机器人路径规划及编队问题 1 2 i 路径规划 作为现实环境中驻留的智能体，机器人与外界环境交互能力的提高需要解 决：在哪里? 应该去哪里? 如何到达那里? 对于此类问题的研究称为导航技术， 而最后一个问题涉及机器人的路径规划，它是导航研究的一个重要环节和课题 【1 】【j l 】f i 2 】。 所谓路径规划是指移动机器人按照某一性能指标( 如距离、时间、能量、安 全等) ，从环境中搜索一条从起始状态到目标状态的最优或次优路径。路径规划 具有如下特点： 复杂性：动态时变环境下的规划非常复杂且计算量庞大； 随机性：复杂环境下的不确定因素使得环境充满随机性； 多约束：机器人存在形状、速度、加速度等约束； 多目标：多个机器人均需路径最短、安全无碰，在同一环境下存在冲突。 路经规划是移动机器人完成任务的安全保障，同时也是移动机器人智能化 程度的重要标志。在当前机器人硬件系统精度短期内无法提高的情况下。对于 路径规划算法的研究显得尤为重要 1 2 2 编队问题 在自然界中，鱼类、鸟类运动时普遍保持编队行为，即形成某一几何形状 或者运动过程中保持一种相对不变的位置关系，从而使这些动物能联合起来更 加有效地发现、围捕猎物以及抵御捕食者自然现象启示我们：机器入团队在 执行任务中若保持队形，同样可以发挥较大作用，因此提出多机器人编队问题 的研究【1 6 1 。 多动机器人移动过程保持一定的队形具有以下优点： 充分获取当前环境信息； 增加抵抗外界入侵的能力； 提高工作效率： 提高系统的鲁棒性。 所谓编队问题是指多个机器人在到达目的地的过程中，保持某种队形，同 西南交通大学硕士研究生学位论文第4 页 时又要适应环境约束( 例如存在障碍物或者空间的物理限制) 的控制技术。队 形问题是一个具有典型性和通用性的多机器人协调与协作问题。编队问题包括 队形形成和队形控制两部分。 队形形成主要是研究如何使机器人系统从一个杂乱无章的状态最终形成一 个具有规律性的整体或符合设计者要求的稳定状态，这为群机器人根据所要保 卫的区域的几何形状有序分布以建立一个屏障或者包围一个特定目标等任务提 供了技术支持。队形控制主要是研究在机器人系统在向目的地行进过程中，既 要遵守一定的队形约束，又要适应当前工作环境的约束的控制技术这两项研 究既可以独立展开，也可以联合起来。 1 2 3 国内外研究现状 机器人路径规划研究起始于上世纪7 0 年代，目前针对这一问题研究十分活 跃，自动化、机器人、人工智能等领域的许多学者做了大量颇有成效的研究工 作，主要研究内容按不同分类标准大概分为以下几个方面 n - i 5 】：按规划方式划 分的全局规划与局部规划；按工作环境划分的静态环境规划与动态环境规划。 本文从基础理论应用角度，将现有的规划方法分为传统规划方法和智能规 划方法。传统方法基于几何学与图论的理论，包括自由空间法、图搜索法、栅 格解耦法、人工势场法，大部分机器人路径规划中的全局规划都是基于上述几 种方法。伴随传统方法的搜索技术包括：图搜索方法( 梯度法、a 法) ，枚举法， 随机搜索法等。但是以上这些传统方法在路径搜索效率及路径优化方面尚有待 于进一步改善。 近年来，随着人工智能方法的广泛应用，许多研究者把目光放在了基于 智能方法的路径规划研究上。对于智能技术的研究主要分为两大派：间接进化 和直接进化。前者主要以符号主义的人工智能为代表；后者以计算智能技术为 代表，包括神经网络技术、模糊技术、进化计算( 遗传算法、进化策略、进化 规划等) 和基于个体的复杂系统的研究。目前已有的方法有： ( 1 ) 基于模糊逻辑的路径规划 基于模糊逻辑的路径规划是根据驾驶员的工作过程观察研究得出，驾驶员 的避碰动作并非是对环境信息精确计算实现，而是根据模糊的环境信息，通过 查表得到规划出的信息，完成局部路径规划。在线规划中通常采用此法，对处 理未知环境下的规划问题显示出很大优越性，但也有其固有缺陷：复杂的未知 动态环境中，模糊规则很难提取；人的经验不一定完备，当输入量增多时推理 西南交通大学硕士研究生学位论文第5 页 规则或模糊表急剧膨胀，使得导航效率降低： ( 2 ) 基于神经网络的路径规划 路径规划是感知空间到行为空间的一种映射，映射关系可用不同方法实现， 但很难用精确的数学方程表示。采用神经网络易于将传感器数据作为网络输入， 期望运动方向的角增量作为网络输出，由多个选定位姿下的一组数据构成原始 样本集，经过剔除重复或冲突样本等加工处理，得到最终样本集。不过神经网 络应用往往局限在环境的建模和认知上，由于目前在导航过程中主要采用前馈 网络，需要教师信号进行训练，因此难于实现在线应用； ( 3 ) 基于遗传算法的路径规划 遗传算法以自然遗传机制和自然选择等生物进化理论为基础，构造了一类 随机化搜索算法，是目前机器人路径规划研究中应用较多的一种方法。但是遗 传算法运算速度较慢，进化众多的规划要占据较大存储空间和运算时间。因此 在此基础上，根据不同的对象与环境的应用需求，遗传算法派生出众多种类。 ( 4 ) 基于混合方法的路径规划方法 为弥补单一算法的不足，许多研究混合了不同的智能算法，如神经网络和 模糊数学结合可实现移动机器人局部路径规划，提高机器人学习能力；模糊神 经网络和遗传算法的融合，可提高机器人自适应控制方法，将规划过程分为离 线学习和在线学习等等。 随着移动机器人应用范围的扩大，对于规划技术的要求也越来越高，新的 发展趋向于将多种方法相结合：基于反应式行为规划与基于慎思行为规划的结 合，全局路径规划与局部路径规划的结合，传统规划方法与新的智能方法的结 合，因此在移动机器人导航中，智能方法有极大的发展空间。 2 0 世纪8 0 年代中期到9 0 年代，分布式人工智能、复杂系统和多智能体系 统理论的研究逐渐展开，一些学者将多机器人系统作为试验平台进行相关理论 的研究和仿真，提出多智能体机器人系统( m u l t i - a g e n tr o b o t i cs y s t e m s ，m a r s ) 理论。队形问题的本质属于m a j 玛研究中的协调与协作问题。 目前国外开展的研究有【1 7 “2 3 ：欧盟的用于搬运工作的多自主机器人系统 ( m a r t h a ) 课题，日本的a c r r e s s 系统和c e b o t 系统，美国d a r p a 的 战术移动机器人计划，m d a 】媳项目，美国学者k 珈和g b e n i 等研究的s w 根m 系统等。比较有代表性的典型系统包括：自重构机器人系统( s e l f - r e c o n f i g u r a b l e r o b o t i cs y s t e m s ) 、群智能机器人系统( s w a r mr o b o t i cs y s t e m s ) 、足球机器人系 西南交通大学硕士研究生学位论文第6 页 统( s o c c e r r o b o t s ) 等。国内的上海交通大学、中国科学院沈阳自动化研究所、 哈尔滨工业大学机器人研究所、东北大学等已先后开发出各种形式的多机器人 系统。 国内外在多机器人队形问题方面开展了大量的工作【1 田1 倒，其中包括： ( i ) t h er o b o t i c sa n da u t o m a t i o nl a b o r a t o r y ( m i c h i g a ns t a t eu n i v e r s i t y ) 的f o r m a t i o nc o n t r o lo f m u l 如1 ea u t o n o m o u sa g e n t s 项目，通过设计有效的控制 器使得多智能体保持所需队形，并能应对环境的突变； ( 2 ) g e n e r a lr o b o t i c s ，a u t o m a t i o n ，s e n s i n g ，a n dp e r c e p t i o nl a b o r a t o r y ( u n i v e r s i t yo f p e n n s y l v a n i a ) 的c o o p e r a t i v ec o n t r o la n dl o c a l i z a t i o no f m u l t i p l e r o b o t s 项目研究多机器人协调队形控制； 、 ( 3 ) i n t e l l i g e n ts y s t e m sa n d r o b o t i c sc e n t e r ( s a n d i a n a t i o n a ll a b o r a t o r y ) 的 p e r i m e t e rd e t e c t i o n 项目，目标是开发机器人警戒系统，采用多个小型野外机器 人共同承担单兵安全警戒任务，可大大降低单兵的生存负担，提高作战能力。 其中一项研究是开发一个简单的用户界面使单兵可以指导多个机器人的运动。 多机器人协调编队运动便于单兵指挥，是完成任务的一种有效方式； ( 4 ) m o b i l er o b o tl a b o r a t o r y ( g e o r g i ai n s t i t u t eo f t e c h n o l o g y ) 的r e a c t i v e c o n t r o lf o rm u l t i - a g e n tr o b o t i cs y s t e m si nh o s t i l ee n v i r o m e n t s 项目和 m u l t i a g e n tr o b o t i cs y s t 锄s 项目，将队形控制研究成果应用于无入地面车中； ( 5 ) i n t e r a c t i o n l a b ( u n i v e r s i t y o f s o u t h e r n c a l i f o r n i a ) 的r o b o t f o r m a t i o n s u s i n go n l yl o c a ls e n s i n ga n dc o n t r o l 项目，研究基于局部传感和控制的队形实 现。 虽然目前这些工作还都处于实验室研究阶段，同时所处理的任务的复杂度 还不够高，但通过这些研究，探索多机器人系统从任务分配、规划到控制层次 协调的普遍模式和包括通信、传感检测等具体的实现方法，对于将来在非结构 化环境下完成复杂任务的智能机器人系统的应用具有重要意义。 1 3 课题研究目的与意义 机器人技术的发展彰显一个国家科学技术水平的高低。在机器人关键技术 的研究中，导航技术是其核心，而路径规划是导航研究的一个重要课题，无论 是工业机器人还是移动机器人的设计都与此息息相关提高机器人的自主规划 能力，是机器人智能化指标之自主性的必要条件。与此同时，机器人技 术发展的必然趋势是进行多机器人协作任务的研究，这将对机器人技术的发展 西南交通大学硕士研究生学位论文第7 页 起着重要作用。多机器入之间的协调与协作将大大提高机器人行为的智麓化程 度，完成很多单机器人无法完成的工作，进一步将人类从危险和繁重的工作中 解放出来。多机器人系统的研究对提高机器人的智能化水平及加快机器人的实 用化进程具有重要的理论研究意义和实用价值。 本论文的目的是根据机器人路径规划的任务，引入人工智能的理论，进行 算法和策略研究，并分别针对单机器人、多机器人进行仿真试验；进一步结合 多机器人运动过程的编队任务，进行多机器人协调与协作策略的研究和仿真。 本课题的研究涉及机器人路径规划，多机器人队形形成、队形控制，多机 器人系统体系结构分析，v i s u a lc + + 环境下基于m f c 的软件编写等多方面知识， 对全面掌握移动机器人控制和多机器人协调协作具有十分重要的意义。 1 4 论文主要工作 本文结构共分为6 章，主要工作内容分述如下： 第l 章为绪论，首先介绍机器人的发展及关键技术，阐述路径规划及多机 器人系统编队问题的定义和特点，总结目前韵研究方法和国内外的研究状况。 其次阐述了本文的目的与意义，并进一步介绍论文主要工作及文章结构安排。 第2 章进一步分析机器人路径规翔闯题，选择环境建模和规划方法，建立 了算法实现的数学模型在分析遗传算法的基础上，根据机器人特点，选择加 以改进的遗传算法作为搜索技术。本章介绍了2 种改进的策略，为下文设计提 供框架。 第3 章根据上文所述策略，设计并编程实现用于单人规划的基于知识的遗 传算法，通过仿真软件的验证，证明算法的有效性。针对多机器人的规划特点， 在单机器人规划基础上，将算法设计推进一步，实现多机器人之间的协调规划， 同样通过仿真试验，证明策略可行 第4 章介绍多机器编队问题的研究方法，采用基于i , e a d 口- 的队形控制方法， 针对该方法的不足，采用基于l c a d f f l 的队形控制算法与队形动态调整相结合的 策略，增强多机器人队列处理突发事件的能力，在该算法的基础上，又结合了 机器人角色转换方法，更好地完成协作任务。仿真试验验证了算法的有效性。 第5 章分析了智能机器人仿真系统的功能结构，设计用户交互界面和功能 模块，开发了用于路径规划、编队问题研究的机器人仿真软件，并对本文中提 出的路径规划中的算法和队列控制算法进行了仿真验证。 最后是对本文工作的总结，以及对下一步工作的展望。 西南交通大学硕士研究生学位论文第8 页 1 5 本章小节 本节简单介绍机器人的发展，点明论文研究的2 个问题。总结国内外的研 究现状和发展趋势，随后阐述论文的目的与意义，对文章框架和工作重点进行 逐章的安排与归纳。 西南交通大学硕士研究生学位论文第9 页 第2 章机器人路径规划与算法分析 2 1 路径规划问题 机器人路径规划的研究涉及三个问题，分别是：对客观环境的抽象表示、 路径规划方法的理论基础和路径搜索策略的算法设计。下面逐一进行分析研究。 2 1 1 环境表示 合理的环境表示有利于建立规划方法和选择合适的搜索算法，最终实现较 少的时间开销而规划出较为满意的路径。不同的路径规划方法正是基于不同的 环境建模，栅格解耦法是目前研究最广泛的路径规划方法【2 3 1 。该方法将机器人 的工作空间解耦为多个简单的区域，一般称为栅格。栅格解耦法包括确切的和 不确切的两种。如图2 1 所示，( a ) 表示机器人原始工作环境。 ( a ) 原始工作环境( b ) 确切解耦( c ) 不确切解耦 图2 1 环境表示方法图例 图2 1 ( b ) 将移动机器人工作环境分解成一系列具有二值信息的网格单元， 环境被量化成具有一定分辨率的栅格，即确切解耦表示环境，栅格的几何单元 确定取决于求解问题的精度；不确切解耦方法是将整个图被分割成多个较大的 矩形，如果大矩形内部包含障碍物或者边界，则又被分割成4 个小矩形，对所 有较大的栅格都进行这种划分，然后在划分的最后界限内形成的小栅格间重复 执行程序，直到达到解的界限为止，这种解耦的结构称为四叉树，如图2 1 ( c ) 所示 本文重点是研究机器人路径规划中的智能方法，提高机器人智能程度，因 西南交通大学硕士研究生学位论文第1 0 页 此希望环境建模简单通用，特选用确切栅格法作为环境的建模方法。 2 1 2 规划方法 当论文确定采用栅格解耦法表示环境后，这些栅格构成了一个连通图，本 文借鉴几何法、单元分解法和数学分析法的思想，对机器人的路径规划方法作 如下表述： 在连通图上寻找一条从起始栅格到目标栅格的路径，这条路径是由多个自 由单元( 即可行的空间) 组合而成，即从起点到终点之间的一条无碰路径，由 于组合众多且良莠不齐，因此需要搜索其中最优的一条，从而把避障路径规划 问题转换为带约束的路径搜索问题。 2 1 3 搜索算法 避障路径的搜索技术分为两大类：一类是经典算法，如枚举法、动态规划 方法、梯度法，a 、d + 最优算法等方法；另一类是智能计算方法，本文在绪论 中已经详细介绍。进化算法模拟智能产生过程，成为近年来机器人智能化研究 的热点。作为进化计算的主要分支之一，遗传算法以其有指导的随机搜索技术 在机器人研究领域得到关注。 通过环境建模和规划方法选择，路径规划问题被转化为路径搜索问题。本 文选择遗传算法作为搜索方法，在分析遗传算法基本原理的基础上，从机器人 应用角度提出改进，以提高算法的效率 2 ，2 遗传算法分析 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是一种仿生优化算法，由美国m i c h i g a n 大学的j o l l nh o u a n d 教授于1 9 7 5 年在著作( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a l s y s t e m s 中提出，后经同事与学生等归纳完善形成进化计算的一种，定名为遗 传算法【2 ”9 】。 2 2 1 遗传算法原理与特点 遗传算法基于进化论和遗传学理论，利用简单的编码技术和繁殖机制来表 现复杂的现象，在群体中各个体之间进行信息交换，完成种群的更新和迭代， 西南交通大学硕士研究生学位论文第1 1 页 采取群体搜索策略来搜索全局最优解。 遗传算法优化问题的基本原理口】如图2 - 2 所示：分析问题的本质，建立原 问题的优化模型确定基因，通过简单的编码，形成个体( 表示问题的一个解) 和种群( 表示问题的潜在最优解的搜索空间) 初始种群产生之后，按照适者生 存和优胜劣汰的原理，选择个体进行组合交叉和变异，产生出代表新解集的种 群。逐代进化产生越来越好的近似解。末代种群中的最优个体经过解码，可以 作为问题近似最优解。 图2 - 2 遗传算法原理图解 遗传算法与传统的优化算法相比，主要有以下特点： ( 1 ) 智能性：算法在搜索过程中体现的自组织、自适应与内在学习特征， 使其求解过程体现了智能性； ( 2 ) 本质并行性：一是内在并行性，算法可在多台计算机上独立进行种群 的进化，并通过通信选取最优个体：二是内含并行性，算法同时搜索解空间的 多个区域，并相互交流信息，利用较少的计算获得较大的收益； ( 3 ) 过程性：算法模拟的是一个过程，算法本身无法判定个体处在解空间 的位置，因此需要人为干预( 即事先确定终止准则) 才能终止； ( 4 ) 不确定性与多解性：在进化过程中，算法的主要步骤含有随机因素， 事件发生与否带来的不确定性和基因结构调整重组形成多个近似解； 西南交通大学硕士研究生学位论文第12 页 ( 5 ) 鲁棒性与全局优化：算法利用个体适应度值推动群体的进化，求解不 同问题时，只需要设计相应的适应性评价函数，而无需修改算法的其它部分。 同时，算法在解空间的多点并行搜索，使得结果具有全局优化的特点。 遗传算法的特点使其在计算数学、航空航天、交通、通信、自动控制、机 器人学、人工生命和机器学习等方面获得了广泛的运用。 2 2 2 基本遗传算法的组成 基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ，s g a ) 只使用选择算子、交叉算 子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，各种改进的遗 传算法，均以其为基础。可将s g a 的组成定义为一个6 元组，见下式： s g a = ( c ，昂f i t n e s s ，o p e r a t o r s ，e n d ，c o n f i g ) ( 2 - 1 ) 式中c ：个体编码方法，s g a 为2 进制，固定长度符号串表示群体中的个体； 只：初始群体及产生方法( 随机法) ； f i t n e 3 a ：个体适应度评价函数，是遗传算法与问题的接口； o p e r a t o r s ：遗传算子，分别表示选择、交叉、变异操作； e n d ：遗传算法的终止条件； c o n f i g ：算法参数设置，包括编码长度，种群规模、变异概率己、杂交概 率只，进化代数r 等 s g a 提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具 体领域，对问题的种类具有很强的鲁棒性，图2 - 3 是s g a 流程图。 西南交通大学硕士研究生学位论文第1 3 页 图2 - 3s g a 流程图 2 。3 遗传算法在路径规划中的应用 2 3 1 问题预处理 本文采用基于s g a 的改进算法进行全局路径规划。机器人根据环境中给定 的起点和目标点位置，规划其行动路线，要求所得路径不与任何障碍物发生冲 突，长度应尽可能短，尽可能方便机器人的运动控制。本文重点在于算法的分 析、设计与实现，因此作如下设定：机器人运动环境为二维平面空间，且机器 人运行速度恒定：根据机器人的大小尺寸适当地扩大环境中的障碍物的大小， 从而在规划路径时把机器人视作一个质点，即忽略机器人的尺寸。 2 3 2 环境建模的实现 2 3 2 1 建模步骤分析 实际环境按照栅格法及问题预处理的设定，环境模型的建立具体步骤如图 西南交通大学硕士研究生学位论文第1 4 页 2 - 4 所示。 图2 - 4 建模步骤示惹图5 利用绘图软件绘制实际环境地图并保存为位图文件，位图为矩形的黑自二 色图案，其中黑色区域表示障碍区域，而白色区域表示可自由通行的区域。不 限制障碍物的形状、大小、数量，以尽可能与实际环境相符。利用m a t l a b 软 件将此位图文件转换为一个2 值矩阵：值为0 的元素显示为黑色，值为l 的元 素显示为白色。此时地图数据为建立环境的数学模型和编写算法的程序提供基 础。 离散化下的空问单元分属自由空间、障碍空间、混合空间( 即一部分是自 由空间另一部分是障碍物) 三种。对于后者依据其自由空间和障碍物占有空间 的比例，将其归属于自由或障碍。机器人路径即通过搜索这张栅格图得到。 同时，仿真数据显示是研究问题必不可少的手段，对于环境及路径的显示， 本文自行编写软件显示。整个显示场景由环境模型和机器人路径组成。场景的 背景为白色，静态障碍为黑色。本文为进行算法的仿真，建立了从简单到复杂， 障碍物密度各异的多个环境模型。 2 3 2 2 环境的数学模型 设机器人运行物理环境e ( 2 维) 的几何尺寸为：长度为工，宽度为形； 设定离散化网格尺寸为( 4 口) ，则机器人工作环境确切解耦参数为( 幺) ， 因此环境e 由众多网格函构成，其数学模型如式2 2 所示： e = g fi g r = o 1 , i o , j o j ( 2 2 ) 其中岛：o 表示环境自由，可行；岛= 1 表示环境障碍，禁行。 栅格法建模虽然直观、简易和快捷，但是构成的搜索空间很大，因为一个 西南交通大学硕士研究生学位论文第1 5 页 几何参数描述的障碍被分离成很多离散的数值参数描述形式，需要联系实际环 境几何规格，慎重选择网格尺寸的合适大小，本文根据算法需要，设计了解耦 参数( 1 0 x 1 0 ) 。 2 3 3 单目标优化与多目标优化 从数学角度分析，机器人路径规划问题可以表达为求解带约束的某个( 或 某些) 目标函数极值问题。解决实际优化问题时，如果仅考虑一个目标，则称 为单目标优化问题，如果存在的目标超过一个并需要同时处理，则称为多目标 优化问题【2 1 单目标优化问题的数学模型如下： m 瓢，( 工) = ，( 力 ，。 j j g f ( s 0 ，i = l ，2 ，m 式中：工r 。是带有一个参数( 决策变量) 的向量，( d 为且标函数，f ( 曲为 评判函数，g f ( 功是非线性约束条件，研表示约束不等式的个数，由它们形成了 可行解区域。通常在决策空间中用s 来表示可行区域： s = 石e r 。j 岛( 力o , i = 1 , 2 ，拼，毒0 ， ( 2 - 2 ) 同理，多目标优化问题数学模型如下： m 积，( - 阢，厶，a ( x ) l ( 2 - 3 ) & f g j ( 善) 0 , i = 1 , 2 ，埘 s 用来表示决策空间中的可行区域，z 用来表示目标空间： z = z r l 毛= 五破：2 = 五( 破，2 k = 五( d ，j 毋( 2 - 4 ) 其中，z r 是带有k 个目标函数的向量。换句话说，z 是s 中所有点的原象 的集合。 多目标优化问题与单一目标优化问题的差异非常大，在单一目标时，人们 寻找最优解。在多个目标时，由于存在目标之间的无法比较和冲突现象，不一 定在所有目标下都是最优的解，参见图2 - 5 中，算法的结果通常是一个集合力， 而不是一个具体的值 西南交通大学硕士研究生学位论文第16 页 f 图2 - 5 多目标优化问题的解 遗传算法的内在特征说明了进化算法适用于多目标优化的原因：一方面算 法基于种群的搜索方式实现了搜索的多向性和全局性，使得它非常适合于求解 多目标优化：另一方面，算法不需要许多数学上的必备条件，可以处理所有类 型的目标函数和约束 对于路径规划问题的重点路径搜索，本文根据单机器人和多机器人的 差异而采用不同的处理方法：对于单个机器人的规划，其目标函数就是所规划 路径的运行成本( 长度) 最低，约束条件是避免与障碍物相碰撞：多机器人规 划，目标函数是每个机器人主观上的路径最短，同时要避免在运行过程中与其 他机器人的碰撞。对于遗传算法在路径规划中应用，需要根据式( 2 1 ) 、( 2 3 ) 分别设计算法的适应度评判函数，分别设计改进的遗传算法 2 3 4 遗传算法的应用策略分析 遗传算法在路径规划中的作用是搜索和优化最终的结果，s g a 虽然对于问 题具有普遍适应性，但是在算法的收敛性和效率等方面都有缺陷，因此本文在 采用遗传算法作为搜索技术的应用中，针对单个机器人和多个机器人分别进行 应用策略的分析。 2 3 4 1基于知识的算法改进应用 遗传算法具有的编码性使其对于问题具有适应性和鲁棒性，针对路径规划 豹算法应用，既要满足研究规划的要求，也要提高算法的效率。为发挥遗传算 法自身的智能性，充分利用进化信息，本文将路径规划问题的领域知识引入初 始种群，改进s g a 的部分设计，可以克服s g a 的收敛缓慢的问题，提高遗传 算法的效率 2 4 1 3 4 - 3 6 。算法的改进需要解决以下问题： 西南交通大学硕士研究生学位论文第1 7 页 个体的编码方法设计； 初始种群的产生方法与处理： 适应度函数的设计： 遗传算子的设计。 2 3 4 2 基于共生机制的协同进化算法 多机器人在同一环境下工作的特点是竞争与协作并存，使得优化约束进入 多目标、多态的境况中s g a 只考虑生物之间的竞争，没有考虑生物之闯协作 的可能性。真实情况是竞争与协作并存，即所谓的协同进化，考虑种群与环境 之间、种群与种群之间在迸化过程中的协调 2 7 1 3 2 l 。 本文引入协同进化算法中的共生机制，在基于知识的遗传算法基础上，提 出一种新的适应多机器人规划应用的基于共生机制的遗传算法。 这种策略模拟生物进化中的共生现象，把种群看作是若干个物种( 子种群) 的共生，各个物种的进化独立地实现，然后在适当的时候，以适当的方式交换 信息，以相互促进、相互进化本质上是从个体表现型层次实现算法的并行规 划。 算法将多机器人规划问题划分为若干子问题，即各个机器人拥有自己的进 化种群( 可行解搜索空间) ，单独进化。每一个进化个体只对应问题的部分解， 由不同种群个体构成的一个共生体对应问题的一个完整解。算法框图见图2 - 6 ， 各个机器人独立进化，综合评判，为使最终解的组合满足多目标约束，需要解 决以下问题： 子种群的划分方式； 子种群进化算法； 子种群适应度评价函数设计：