（模式识别与智能系统专业论文）基于进化势场法的足球机器人路径规划系统.pdf

摘要 路径规划是机器人技术研究领域中的核心问题之一，也是机器人学 中研究人工锶能问题的一个重要的方面。路径规划的燕要任务是在机器 人所在的玮壤中寻求一条从已知起点到己知终点豹皴抵钱徐戆无碰撞 鼹径，在莰蠢静态障褥穆存在鹣窆蠲，笼较容器我翔一条最蕊路经，当 环境中同时存在静态与动念障褥物的时候，找到一个研行豹最优路径魏 比较困难。 本论文以足球机器人系统为研究背景，主要针对系统中的路径规划 问题进行深入研究，探索行之肖效的方法来解决实际中的路径规划问 题。首先，想体介绍了足球机器入系统的体系结构殿相关技术，其中重 点讨论了决策予系统设诤，努辑薅经嫒翅在整今系绶枣豹重要莲，莠详 细论述了越球搬器久系统舔境援麓翻平台遂碰撞案l 特赢。在浚上工终蒸 础上，对入工势场法、栅格建模法、遗传算法和神缎网络这凡种典型路 径规划方法避行了深入研究，讨论它们在足球机器入系统中的应用可行 性。最后，使用遗传算法优化势场函数，设计了基于进化势场法的足球 机器人路径规划系统，该系统具有结合足球机器人平台特性的优点，包 括基础路径娥划子系统、边界路径规划子系统和禁医路径规划子系统。 透过实器魄赛擎台戆检验，证明该浚诗方法是嚣之蠢效豹。 关键词：足球机器人系统路径规划人工势场遗传算法进化势场 a b s t r a c t p a t hp l a n n i n gi sak e r n e lp r o b l e mo fr o b o tt e c h n o l o g ya r e a a n di sa l s o a l li m p o r t a n ta s d e c to f r o b o ts t u d yi na r t i f i c i a li m e l l i g e n c e t h em a i nt a s ko f p a t hp l a n n i n gi sf i g u r i n go u tac o l l i d e f r e ep a t ha tl e a s tc o s tf r o mt h ek n o w n s t a r tp o s i t i o nt ok n o w ng o a l p o s i t i o n i nt h er o b o te n v i r o n m e n t i n e n v i r o n m e n to n l yw i t hs t a t i co b s t a c l e s ，i ti se a s yt of i n da l lo p t i m i z e dp a t h , w h i l ei ne n v i r o n m e n tw i t hb o t hs t a t i co b s t a c l e sa n dd y n a m i co b s t a c l e s i ti s m o r ed i f f i c u l tt of i n daf e a s i b l eo p t i m i z e dp a t h t l i st h e s i si sb a s e do ns o c c e rr o b o ts y s t e m i tm a l n l yf o c u s e so nt h e p r o b l e mo fr o b o tp a t h p l a n n i n ga n de x p l o r e se f f e c t i v em e t h o d st os o l v et h i s p r o b l e m f i r s t l y ，t h i sp a p e rg i v e st h ea r c h i t e c t u r eo ft h es o c c e rr o b o ts y s t e m a n di t s k e yt e c h n o l o g i e s e s p e c i a l l y , i t d i s c u s s e st h ed e s i g no f d e c i s i o n - m a k i n gs u b s y s t e ma n da n a l y z e st l l ei m p o r t a n c e0 np a t h p l a n n i n g i nt h i ss y s t e m w ea l s oi n v e s t i g a t et h es y s t e mm o d e lo fr o b o ts o c c e ra n d c o l l i s i o nc h a r a e t e r i s t i c so f t i l i sp l a t f o r m 0 nt h eb a s i so f t h ea b o v ew o r k t h e a u t h o rs t u d i e st h ef o u rr e p r e s e n t a t i v em e t h o d sw h i c ha r ea r t i f i c i a lp o t e n t i a l f i e l d ，g r a d sm o d e l i n gm e t h o d ，e v o l u t i o n a r ya l g o r i t h m sa n da r t i f i c i a ln e u r a l n e t w o r k ；a n dd i s c u s s e st h e i rf e a s i b i l i t yi nr l - t i m es y s t e m f i n a l l y ，as o g c - e t r o b o tp a t h p l a n n i n gs 3 7 s t e mi sd e s i g n e db a s e do ne v o l u t i o n a r ya r t i f i c i a l p o t e n t i a lf i e l d t h es y s t e mh a st h em e r i to fc o m b i n i n gw i t hp l a t f o r ma n d i n c l u d e st h eb a s i c p a t h p l a n n i n gs u b s y s t e m b o u n d a r yp a t h p l a n n i n g s u b s y s t e ma n df o r b i d d e nz o n ep a t h p l a n n i n gs u b s y s t e m t h em e t h o di s e r i e c t i v eb yt h et e s t i m o n yo nt h er o b o ts o c c e rs i m u l a t o r k e yw o r d s ：s o c c e rr o b o ts y s t e m ，p a t h p l a n n i n g , a r t i f i c i a lp o t e n t i a l f i e l d ，e v o l u t i o n a r ya l g o r i t h m s ，e v o l u t i o n a r y a r t i f i c i a l p o t e n t i a lf i e l d i i 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，基于进化势场法的足球 机器人路经规划系统是本人在指导教师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 作者签名：金务塑掣年旦j _ l e t 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学 位论文版权使用规定”，同意长春理工大学保留并向国家有关部门或机 构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权 长春理工大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 垒磊竺2 年旦月上日 指导导师签名：翻丛地2 年皇月上日 第一章绪论 1 1 引言 几百年前，玩具商们试图设计一种以一定机械装置驱动的人偶，人 们将其称为机器人。1 9 6 2 年，美国一家公司售出第一批比较原始的工 业机器人，这是一种“搬运型”的机器人，能把物件从一个地方搬到另 一个地方，但活动范围很小。随着人类对人工智能的不断研究，各种类 型的机器人逐渐被应用到工业、农业以及人们的日常生活中。1 9 9 6 年， 深蓝战胜了当时的国际象棋冠军，被誉为是人工智能领域的一个里程 碑。机器人在许多领域得到广泛应用，如制造、航天、医学、军事、建 筑、保安、农业、娱乐等都是现在及未来机器人应用的广泛领域。机器 人在人类生活中扮演着越来越重要的角色，机器人已成为高技术领域内 具有代表性的战略目标【l l 【2 j 。 机器人技术是人工智能研究的主要阵地，是培养信息、自动化领域 科技人才的重要手段，同时，也是展示高科技水平的生动窗口和促进科 技成果转化的有效途径。机器入技术涉及到计算机、自动控制、传感和 无线通讯、精密机械以及仿生材料等众多学科领域，其研究水平能反映 出一个国家信息与自动化技术的综合实力。 机器人的发展大致经历三个阶段，第一代是可编程的示教再现型机 器人，首先由操作者通过示教盒来操作机器人的运行轨迹，作业顺序等 进行示教操作。机器人控制系统将示教指令记忆，存储，应用时再根据 再现指令顺序取出示教指令，经过编译，在一定精度范围内复现示教动 作；第二代是带有一定的传感功能，包括视觉，力觉，触觉等功能，具 有一定适应能力的机器人，这种机器人可以根据传感信息调整控制算 法；第三代则是智能机器人，这种机器人装有多种传感器，并能将多种 传感器探测到的信息进行融合，能有效地适应环境的变化，具有很强的 自适应能力，并具有自学习功能1 3 j 。 机器人路径规划是智能机器人的一个重要的课题。在静态环境和动 态环境下进行路径规划与实时避障是解决机器人应用的一个非常重要 的问题，而动态不确定环境下的机器人路径规划则是实际研究与应用的 一个重点和难点。 1 2 论题研究背景及意义 1 2 1 足球机器人系统概述 机器人足球比赛的设想首先由加拿大不列颠哥伦比亚大学的a l a n m a c k w o r t h 教授在1 9 9 2 年的报告o ns e e i n gr o b o t s ) ) 中提出的 4 1 。足 球机器人比赛是人工智能与机器人领域中极富挑战性的高技术密集项 目，同时又是多智能技术的一个理想突破点，是继计算机下象棋后出现 的人工智能发展的第二个里程碑。足球机器人融小车机械、机器人学、 机电一体化、单片机、数据融合、精密仪器、实时数字信号处理、图像 处理与图像识别、知识工程与专家系统、决策、轨迹规划、自组织与自 学习理论、多智能体协调、以及无线通讯等理论和技术于一体，它既是 一个典型的智能机器人系统，又为研究发展多智能体系统、多机器人之 问的合作与对抗提供了生动的研究模型。 足球机器人系统是机器人研究的一个分支，属于可行走智能机器人 系统。目前研究的方向有集中控制式足球机器人系统( v i s i o n b a s e d r e m o mb r a i n l e s sm u l t i r o b o ts y s t e m ) 、集中视觉型足球机器人系统 ( v i s i o n b a s e db r a i n - o n b o a r dm u l t i r o b o ts y s t e m ) 、分步控制式足球机器 人系统( r o b o t b a s e dm u l t i r o b o ts y s t e m ) 。足球机器人既有一般机器人 的共性，又有其特性。它以实现机器入足球运动员为发展目标，研究运 动分析、自动控制、人工智能、计算机视觉及其他传感器融合、无线数 字通信等学科领域。 对集中控制式足球机器人系统贡献最大的组织是国际机器人足球 协会联盟( f i r a - - f e d e r a t i o no fi n t e r n a t i o n a ir o b o ts o c c e ra s s o c i a t i o n ) f 本 文的研究就是以f i r a 平台为背景的1 。r o b o c u p ( t h er o b o tw o r l dc u p i n i t i a t i v e ) 是对分布式足球机器人系统贡献最大的组织【5 】。 1 2 2 研究足球机器人路径规划的意义 路径规划就是在一个充满障碍的环境罩给定初始位置和目标位置， 按一定的策略让机器人在运动过程中能安全、无碰撞且实时的通过所有 的障碍物到达目标位置。路径规划的目的是使机器人或其他智能体能够 按照存储在其内部的地图信息，或根据外部环境提供的引导信号( 即通 过对外部环境的实时探测所获得的信息) 规划出一条较优的避碰路径， 并能够沿着该路径在没有人工干预的情况下，移动到预定目标点。路径 规划技术的应用非常广泛，不管是关节型机器人还是移动机器人，凡是 有机器人应用的地方都有机器人路径规划技术应用的必要性或者是必 需性。 路径规划问题具有如下特点： 1 复杂性：在复杂环境尤其是动态时变环境中，机器人路径规划 非常复杂，且需要很大的计算量； 2 随机性：复杂环境的变化往往存在很多随机性和不确定因素， 动态障碍物的出现也带有随机性； 2 3 多约束：机器人的运动存在几何约束和物理约束。几何约束是 指机器人的形状制约，而物理约束是指机器人的速度和加速度； 4 多目标：机器人运动过程中路径性能要求存在多种目标，如路 径最短，时问最优，安全性能最好，能源消耗最小。但它们之间往往存 在冲突。 路径规划是足球机器人系统研究中的一个重要课题，其重要性主要 体现在： i 机器人车体造价比较高，而机器人足球比赛是一个动态竞技项 目，机器人如果没有避障行为，则会多次相撞，损坏车体； 2 好的路径规划方法可以使机器人以最短时日j 到达目的地，完成 相应动作，取得较好成绩； 3 将各种算法尤其是各种智能算法放在路径规划这样一个问题中 进行研究和检验，可以促进相关学科的发展，促进人工智能的发展； 4 足球机器人系统场上的环境是时刻变化的，其路径规划属于一 种作业环境未知且动态的路径规划及控制，在这样的平台上研究的路径 规划方法可以应用到其他机器人应用环境，完成有实用意义的任务。 如何在这样一个环境中规划出每个机器人的运动路线，让每个队员 很有策略地行动、配合，是一个研究移动机器人路径规划的很好平台， 而且在这样一个具有高度实用性和竞争性平台上研究路径规划也是个 很有挑战性的课题。 足球机器人系统环境是一个很典型的具有动态性、不确定性、实时 性的环境，这样的环境正好符合当| j 机器人路径规划的研究方向。这也 是本文选择足球机器人路径规划问题的意义所在。 1 3 足球机器人路径规划的国内外研究现状 足球机器人路径规划已经引起国内外专家和学者的关注，并做了大 量的研究工作，取得了许多研究进展和研究成果1 6 j 【7 j 哺j 。 人工势场法是国内外研究者研究与应用最多的方法。该方法具有计 算方法简单，计算量小，且在避障和轨迹规划的同时也考虑了机器人的 运动性能，因此该方法倍受人们欢迎。在国内清华大学、华中师范大学 等等院校均在足球机器人系统中使用了该方法。而且从搜集资料的过程 来看，相关文献也是比较多的，这也充分说明了人工势场方法在路径规 划中有一定的优势。 用栅格法建模进行机器人路径规划也是研究比较多的一种方法。基 于栅格法建模可以与多种方法结合使用来求得一条最优路径，例如势场 思想、进化算法、模糊逻辑等。哈尔滨工业大学薄喜柱等人用栅格法对 机器人空| 日j 建模，参照人类在人群中行走的经验对栅格地图进行进一步 规划，成功的实现了足球机器人路径规划问题。 用人工智能方法进行路径规划问题的研究也比较多，常见的方法有 遗传算法、神经网络、模糊算法等等。 遗传算法是一种人工智能方法，它基于达尔文的生物进化论的适者 生存原理，用一种基于随机搜索的进化理论求解出问题的最优解。国外 的k a z u os u g i b a r a ，j o h ns m i t h 和国内的周明，孙树栋等人均对应用遗 传算法进行路径规划进行了研究，并取得一定成果。遗传算法是一种多 点搜索算法，因而是一种求解全局最优解的较好方法。 利用神经网络解决路径规划问题同样也有许多文献提到，并具有各 自的解决方案。文献利用神经网络来描述环境约束并计算碰撞能量函 数，将迭代路径点集的碰撞能量函数和距离能量函数的和作为优化目标 函数，通过求优化目标函数的极值，确定点集的运动方程，最终使迭代 路径点集趋向于最优规划路径。 模糊理论是在美国波克莱加州大学电气工程系l a z a d e h 教授于 1 9 6 5 年创立的模糊集合理论的数学基础上发展起来的，是在线规划中 通常采用的一种规划方法。用模糊逻辑推理是通过对驾驶员的工作过程 观察研究得出的。驾驶员的避碰动作并不是对环境信息的精确计算来完 成的，而是根据比较模糊的环境信息，靠经验来决策采取什么样的操作。 该方法在移动障碍物和移动目标的环境中能有效地实现机器人避碰和 导航。广东工业大学和吉林大学等学校对模糊理论在足球机器人路径规 划中的应用进行了研究和实验。 另外还有可视图法、蚁群算法、b s p l i n g 法、动态二叉树表示环境 的a 算法等均在足球机器人这个系统中得到了研究和应用。 虽然现在研究路径规划的方法有很多，但就解决问题的性质来说， 基于静态环境下的路径规划已经比较成熟，但是动态环境下的全局最优 路径规划方法还是不太成熟，动态环境和未知环境的路径规划一直以来 都是学术界的一个难点和研究重点。 1 4 本文研究的主要内容 1 本文系统分析和研究了足球机器入系统的体系结构及相关技术， 掌握足球机器人系统运行平台的环境特性和机器人小车的性能特征，为 本文进行足球机器人路径规划研究奠定必备的基础。 2 对应用于足球机器人路径规划的各种方法进行分析，重点对人 们研究较多的几种方法进行了深入研究与分析，讨论它们在足球机器人 系统中的应用可行性，以及它们各自在路径规划上应用的优缺点。 3 根据足球机器人系统环境模型的特点，确定用人工势场法在该 系统中进行路径规划有较大的优势。本文首先使用遗传算法优化势场函 4 数，然后应用优化的势场公式，根据平台特性设计了足球机器入路径规 划系统，使机器人可以在球场的不同区域采用不同的路径规划策略，有 效地完成任务。 全文共分五章，组织结构如下： 第一章：介绍了论文的研究背景和意义，概述论文的研究内容。 第二章：总体介绍足球机器人系统。介绍了足球机器人系统的体系 结构、决策子系统和环境模型，表明了本文的研究背景，以及机器人路 径规划问题在整个系统运作中的重要性。 第三章：对几种典型的路径规划方法进行深入研究与分析。对人们 研究较多的人工势场法、栅格法、遗传算法和人工神经网络方法进行重 点研究，分析每个方法的性能特点，论述这些方法在足球机器人系统中 的应用优缺点。 第四章：研究了基于a p f g a 的机器人路径规划系统设计和实现过 程。首先设计了一套路径舰划系统，包括基础路径规划子系统、边界路 径规划子系统和禁区路径规划子系统，分别用来解决不同情况下的路径 规划任务。然后使用遗传算法优化势场函数对机器人路径进行了合理的 规划，并做出了仿真结果。 第五章：对全文进行总结和展望，指出论文中尚不完善之处及进一 步的研究方向。 第二章足球机器人系统 2 1 足球机器人系统的结构 根据实施的物理基础( 硬件) 和逻辑上的控制结构( 软件) 不同有如下 实现方案：机器人足球仿真系统，集中视觉的遥控无脑多机器人系统， 基于视觉的有脑多机器人系统，基于完全自主机器人的足球机器人系 统。一般而言，我们都是从集中视觉的遥控无脑多机器人系统入手，以 它作为实验平台进行各种技术的研究。 足球机器人是指在系统决策程序的控制下，通过自身运动( 前进、 后退、旋转、停止等) 完成比赛规则允许的传球、带球、过人、射门、 跑位等攻防技术动作的机器人球员。f i r a 足球机器人系统属于集中视 觉的足球机器人系统，计算机统一对场上信息进行分析、决策，然后控 制实际机器人运作，属于集中控制类型的系统。这种系统主要由视觉子 系统、决策子系统、通讯子系统和机器人小车子系统四部分组成。其中 小车子系统可以看作执行机构或控制对象，视觉子系统是系统的检测环 节，策略系统可以看作整个系统的控制器，而无线通讯子系统则在决策 子系统和机器人小车子系统之间起到信息交流的桥梁作用1 9 】【1 0 l 【l i j 。 1 视觉子系统 足球机器人视觉属于计算机视觉研究的范畴，而计算机视觉与模式 识别又有紧密联系。计算机视觉与模式识别是计算机科学和人工智能研 究领域的重要分支。对于基于视觉的足球机器人来说，视觉系统就是其 大脑一决策系统的唯一信息来源，因此它在整个足球机器入系统中 扮演着举足轻重的地位。在足球机器人系统中，视觉子系统由c c d 镜 头、图像采集卡等硬件设备和视觉识别软件组成a 视觉识别软件包括视 频捕获和视觉识别两个部分。 2 决策子系统 决策子系统是机器人足球比赛的核心，是人工智能等相关理论在足 球机器人系统中的集中体现。在人类足球比赛中，教练和球员的思维决 策包含形象思维和逻辑思维两部分，而机器人足球比赛中的思维决策是 借助视觉子系统或传感器获取的信息进行逻辑思维的，无法采用形象思 维进行决策。虽然他们决策方式不同，但是决策过程是类似的，是可以 进行一定程度模拟的，只是在决策表达方式上有所不同。因此决策子系 统的设计就是基于人类足球比赛的决策。 决策子系统是整个比赛的指挥机构。决策子系统根据视觉子系统传 来的场上信息，运用自己已有的经验知识，根据一定的推理决策方法， 决定每个机器人的动作。比赛的结果可以说与决策子系统的设计好坏有 6 着密切的关系。决策子系统上接视觉子系统，下接通讯子系统，是整个 智能系统的中心枢纽。每个控制周期内，决策予系统的输入是视觉子系 统传来的场上全部机器人和球的位姿信息，输出的是机器人的左右轮 速。 3 通讯子系统 m i c r o s o t 机器人足球系统的通讯模块选用的是r f ( 射频) 通信模块 ( 型号：s r f - 4 1 8 l 4 3 3 lr f ) 。通信子系统采用无线通讯，由无线数据发 射器和无线数据接收器两部分组成。无线数据发射器通过无线载波把机 器人运动控制指令数据从天线发射出去，无线数据接收器从天线接收到 信号后，经解调后获得机器人运动控制指令数据。 4 小车子系统 在整个足球机器人系统这个闭环控制系统中，机器人小车充当执行 机构的角色。所以小车性能在赛场上表现的好坏，直接反映了整个足球 机器人系统的优劣。 2 2 足球机器人系统环境模型 2 2 1 球场模型 在足球机器人系统中，其运行环境是部分已知、部分未知，含有静 态和动念障碍物的环境，且是个时刻变化的竞争性动态环境【1 2 】。如图 2 1 所示。 图2 1 足球机器人比赛球场示意图 7 其中足球机器人球场的四个边界是己知的静态障碍物，球场区域是 个矩形区，所以我们分别用四个常量来定义边界：f t o p 表示上边界， f b o t 表示下边界，f r i g h t x 表示右边界，f l e f l x 表示左边界。另外还有 双方的球门线，二者左右对称，分别用g t o p y 和g b o t y 表示球门两侧 坐标口对于这些固定的边线，机器人只要根据自己的坐杯值和边界值的 相对距离进行判断即可。 另外还有两个区域也属于己知的静态障碍物，即球场的两个禁区。 比赛规则中对禁区内双方机器人的数量有严格的限制，所以决策系统应 该根据场上形势规定禁区附近每个机器人是否可以进入禁区。对于禁区 的回避需要根据系统发出的命令来执行。 机器人和小球都属于不确定性障碍物，它们的形状确定，但位置不 确定，而且可能是静止的或者是动态的，对这些障碍物的避障是研究的 重点和难点。当这些不确定障碍物在边界附近或是在禁区附近时避障更 是个难点。 2 2 2 小车模型 1 机器人位姿定义 要对机器人的运动和动作进行研究，首先要描述其位置和姿态。在 这个坐标系内，机器人质心坐标( x ，y ) 代表机器人的位置，机器人正方 向与坐标系x 轴的央角0 表示机器人的姿态，即机器人的方向角。机 器人位姿用( x r ，y r ，0 ) 来表示，如图2 2 所示。 图2 2 机器人位置与姿态描述示意图 足球机器人的位姿函数为： v o i dp o s i t i o n ( i n tw h i c h r o b o t ，d o u b l ex ，d o u b l ey ) i md e s i r e d _ a n g l e = o ，t h e me20 ，v l ，v l ，v c 2 7 0 , 8 d o u b l ed x ，d y ，d _ e ，k a ： d o u b l ek d ； d x - - x p o s i t i o n o f h o m e r o b o t w h i c h r o b o t 0 ； 蛔- p o s i t i o n o f f t o m e r o b o t w h i c h r o b o t 1 ； d _ f s q r t ( d x + d x + d y d y ) ； i f ( d x = = 0 & & d y ：一o ) d e s i r e d _ a n g l e = 9 0 ；机器人1 0 杯点的疗向角 e l s e d e s i r e d _ a n g l e = ( i n t ) ( 1 8 0 m _ p i + a t a n 2 ( ( d o u b l e ) ( d y ) ( d o u b l e ) ( d x ) ) ) ； t h e t a _ e2d e s i r e d _ _ a n g l e - a n g l e o f h o m e r o b o t w h i c h r o b o t ；纠形 角 w h i l e ( t h e t a _ e 1 8 0 ) t h e t a _ e ；3 6 0 ；搀纠玎：角的范 秘限制在 - 18 0 、一1 8 ( j 之间 w h i l e ( t h e t a 1 8 0 1t h e t a _ e ；3 6 0 ： w h i l e ( t h e t ae 1 2 5 1v r = 1 2 5 ；书m a x p w ml i m i tf o rl e f tw h e e li nl e 1 , e r s e d i r e c t i o n * i f ( v 1 1 2 5 ) v 1 = 1 2 5 ： i f ( v r - 1 2 5 1v r = - 1 2 5 ： i f ( v l 成 力的方向背离障碍物。当p ( q ，q o b s ) 一o 时，f ( q ) 一o o ，即机器人 与障碍物相碰时，受到的斥力为无穷大。如避免机器人与障碍物相碰， 可设一个最小安全距离p 。，当p ( q ，q o b ；) 一p 。时，f ( q ) 一o o 。同时为 使f “q ) 连续，f f c p ( q ) 修改为： ( g ) = + o 。 托 ( p ( 玑q o b , ) 一p o ) 2 0 ， p ( q ，g m ) s ， 见 矾 其中p 。、p 。的大小取决于机器人的尺寸、速度及环境中障碍物的 稀疏程度等因素。 2 引力势函数的选取 目标的势函数u “q ) 同样也可以基于距离的概念。目标对机器人产 生吸引力，且距离越远，吸引作用应越大，即机器人距目标越远，所具 有的势能就越大；反之就越小。当距离为零时，机器人的势能为零，此 时机器人到达终点。这种性质是重力势能和弹性势能所具备的。但重力 势能与距离成正比；弹性势能与距离的平方成正比。故引力势函数可分 别取为： u 二( g ) = k g p ( q ，g 删) 及u 0 ( 目) = 0 5 k g p ( q ，g 删) 2 ( 3 9 ) 其中q 9 0 a i 代表目标点在运动空间的位置，p ( q ，q 9 0 a 1 ) 代表机器入q 与目标q 酬的距离，相应的引力分别是： l ( 口) = k 及匕( g ) = k g p ( q ，g 删) 它的方向指向目标点。两种势函数得到的引力是不同的， 值，一个与距离成正比。 ( 3 1 0 ) 一个是常 本文采用斥力公式( 3 8 ) 和与距离成j 下比的引力公式进行静态环境 下的路径规划实验，分别对单个障碍物和多个障碍物的情况在m a t l a b 环境下进行了仿真，实验结果如下： 图3 3 单个障碍物情况图3 4 多个障碍物情况 1 6 3 1 3 人工势场法的优缺点 1 优点 a 、结构简单，使用方便，便于底层的实时控制，这是势场法的一 个最突出特点。 b 、在进行运动规划时不仅考虑机器人的避障和轨迹规划，而且也 考虑了机器人的动态运动性能，使机器人运动更加自然和具有柔顺性， 规划出来的路径一般比较平滑并且安全。 2 缺点 a 、是一种局部寻优方法，只着眼于得到一条能够避障的可行路径， 对路径是否最优并未加以考察。 b 、对简单环境很有效，但对于复杂的多障碍物环境，不合理的势 场数学方程容易产生局部极值点，即在某点的势场合力为零，常出现的 现象是在某点停止而不能到达目标点，或者是在相近的障碍物群中不能 识别路径。 c 、势场角度不易控制，势场角度会因为机器人或者障碍物等位置 的稍微改变而发生较大变化，出现在障碍物前震荡等现象。 3 2 遗传算法 遗传算法基于自然选择的生物进化，是一种模仿生物进化过程的随 机方法，具有简单、通用、鲁棒性强和适用于并行处理的优点，广泛应 用于优化控制、图像编码、机器人最佳运动轨迹规划等领域。 3 2 1 遗传算法原理 遗传算法( 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 h n h o l l a n d 等在2 0 世纪6 0 年代末期到7 0 年代初期研究形成的一个较完整 的理论方法。它是基于达尔文的生物进化论的适者生存原理，从试图解 释自然系统中生物的复杂适应过程入手，模拟生物进化的机制柬构造人 工系统的模型。随后经过2 0 余年的发展，取得了丰硕的应用成果和理 论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能 己作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起， 使遗传算法受到广泛的关注，遗传算法作为具有系统优化、适应和学习 的高性能计算的建模方法的研究渐趋成熟。遗传算法模仿了生物的遗 传、进化原理，并引用了随机统计理论而形成。在求解过程中，算法从 一个初始变量群体开始，逐代寻找问题的最优解，直至满足收敛判据或 预先设定的迭代次数为止，属于迭代式算法。 遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟 了自然界中的生存法则，将待求解问题的每个可能解编码成一个“染色 体”，若干个染色体又构成种群，同时构造了复制、选择、交叉和变异 几种遗传操作。在遗传算法开始时，先随机产生一个种群( 即初始解) ， 并根据一定的评价函数对种群中的个体进行评价，产生相应的适应度 值。基于此适应度值，选择一部分“好的”个体用来复制下一代，然后 对这些选择出来的个体进行交叉和变异操作，产生新一代种群。新的种 群集成了上一代的一些优良特性，在性能上要优于上一代，这样使进化 逐步朝着更优解的方向i ； 进。因此，遗传算法可以看作是一个由可行解 组成的群体逐代进化的过程。 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依 据，利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选 取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一 般而言，适应度函数是由目标函数变换而成的。对目标函数值域的某种 映射变换称为适应度的尺度变化。 适应度函数的设计主要满足以下条件： 1 单值、连续、非负、最大化。这个条件是很容易理解和实现的。 2 合理、一致性。要求适应度值反应对应解的优劣程度，这个条 件的达成往往比较难以衡量。 3 计算量小。适应度函数设计应尽可能简单，这样可以减少计算 时间和空间上的复杂性，降低计算成本。 4 通用性强。适应度对某类具体问题，应尽可能通用，最好无需 使用者改变适应度函数中的参数。从目前而言，这个条件应该不属于强 要求。 使用遗传操作产生新的种群，可以保证进化始终朝着产生最优解的 方向前进，遗传算法中的遗传操作有： 1 选择( s e l e c t i o n ) ：用来确定重组或交叉个体，以及被选个体将产 生多少个子代个体。选择过程的第一步是计算适应度。在被选集中每个 个体具有一个选择概率，这个选择概率取决于种群中个体的适应度及其 分布。选择操作从群体中选择优良的个体并淘汰劣质个体，适应度大的 个体表示生存能力强，被选择的可能性比较大。反之适应度小的个体被 选择的可能则较小。 2 交叉或基因重组( c r o s s o v e r r e c o m b i n a t i o n ) ：基因重组是结合来自 父代交配种群中的信息、产生新的个体，它把两个父个体的部分结构加 以替换重组而生成新个体的操作，也称为交叉。交叉的目的是为了能够 在下一代产生新的个体，就像人类社会的婚姻过程，通过重组交叉操作， 遗传算法的搜索能力得以飞跃地提高。基因重组和交叉是遗传算法获取 新优良个体的最重要的手段。 3 变异( m u t a t i o n ) ：交叉之后是子代的变异，实际上是子代基因按 1 8 小概率扰动产生的变化。子个体变量以很小的概率或步长产生转变，变 量转变的概率或步长与维数( 即变量的个数) 成反比，与种群的大小无关。 变异本身是一种局部随机搜索，与选择交叉算子结合在一起，保证了 遗传算法的有效性，使遗传算法具有局部的随机搜索能力，同时使得遗 传算法保持种群的多样性，以防止出现非成熟收敛。在变异操作中，变 异率不能取得太大，如果变异率大于0 5 ，遗传算法就退化为随机搜索， 而遗传算法的一些重要的数学特性和搜索能力也不复存在了。 下图是遗传算法的流程图： 图3 5 遗传算法流程图 遗传算法是目前机器人路径规划研究中应用较多的一种方法，无论 是单机器人静态工作空| b j ，还是多机器人动态工作空问，遗传算法及其 派生算法都取得了良好的路径规划结果。遗传算法是一种多点搜索算 法，因而是一种求解全局最优解的较好方法。 1 9 3 2 2 利用遗传算法进行路径规划 近年来，随着智能方法的广泛应用，机器人路径规划方法也有了长 足的进展，许多研究者把目光放在了基于智能方法的路径规划研究上， 遗传算法是目前路径规划研究中应用较多的一种方法。许多学者在用遗 传算法进行路径规划时采用栅格法进行环境建模，这里对该方法进行简 要介绍“。 1 问题空间建模 建模方法同前面栅格法建模相同，用序号标注每个栅格。 2 用遗传算法进行路径规划 a 、染色体表示 用十进制栅格序号表示路径节点，用栅格序列表示一条染色体。由 于我们无法确定究竟要经过多少个栅格，所以这里的染色体采用不定长 染色体表示。 b 、初始群体生成 初始解群为随机生成的从出发点到目标点的任意一条可行路径集 合。具体产生的方法与栅格法搜索最优路径方法类似，不过我们这里不 考虑生成的路径优劣。 c 、适应值计算 f ：1 + l 撕丽d 式中，n u m 为该个体所通过的栅格数目总数： 序号间直线距离之和。 d 、遗传操作 ( 3 1 1 ) d 为该个体中相邻 选择操作：用一定的算法从当前种群中选择同样数量的新一代群 体。首先计算每个个体的适应值函数，然后用赌轮选择方法或者其他方 法选出新的种群，通常在选择时要把上一代的最优个体强制保留下来。 交叉操作：通常有单点交叉、多点交叉、均匀交叉等几种方法。随 机选择两个个体，按照一定的交叉概率选择交叉点进行交叉，用交叉后 的子代个体代替原种群中的父代个体，产生新的种群。前面提到这罩的 染色体是不等长个体，所以交叉点应该分别在要交叉的两个个体中进行 选择。 变异操作：根据路径规划的特点，这里的变异操作有多种设计方式， 可以从个体中以定的概率选择一个起点和终点之外序号作为变异点，删 除该点，或者用另个随机产生的序号代替它，或者在个体中随机选择 一个序号在变异点处插入。在仿真实验中，本文采取第二种变异方式， 并且这里选择新的路径点为自由栅格点。 在机器人的路径规划中，还需要增加一些特殊的算子，以保证所得 的路径能够避开障碍物，并达到最短的要求，常见的有插入和删除算子。 插入算子：i j 面由于交叉和变异操作可能产生不连续路径的情况， 引入插入操作的目的就是为了把间断路径用自由栅格弥补，使之成为连 续路径。具体方法是将出现断点处的两个路径点分别设为起点和终点， 然后搜索这两点间的可行路径，直到所有路径为连续路径为止。 删除算子：插入自由栅格的操作可能会使路径中出现重复节点，删 除操作的作用就是将个体中两相同序号之间的冗余序号，连同两相同序 号中的一个一并舍去，以简化路径。 3 2 3 遗传算法的优缺点 本文对应用遗传算法进行路径规划进行了一定的研究和实验，对其 性能分析如下： 1 优点 能求解出问题最优解。只要结合具体的研究背景进行有力的设计， 该算法能够得出一条可行最优路径。 2 缺点 a 、算法比较繁琐。从上面算法介绍可以看出，遗传算法不仅是个 迭代循环求解的过程，而且在每次迭代中都有很多算子，研究者不仅在 算法设计上投入比较大，而且代码实现也是一个比较庞大的工程。 b 、编码设计和适应度函数设计是个关键因素。如果这两个地方设 计不好，往往求不出问题的最优解，甚至都求不出问题的可行解。 c 、实时性难以保证。本文在实际平台中对应用该方法进行路径规 划进行了静态环境下实验，发现当算子设计比较简单，迭代次数比较少 时，遗传算法能满足实时性要求。但当环境变得复杂时，就需要增加一 些特殊的算子，这时遗传算法的实时性就不能完全保证。对于这种情况 我们采取的措施是保留每一代的最优值，当系统响应时问到了的时候， 我们只保留当i ； 求得的最优值，但是这样就不一定求得问题最优解。 3 3 栅格建模法 3 3 1 栅格法原理 栅格法( g r i d s ) 是由w e h o w d e n 在1 9 6 8 年提出的【2 2 1 。栅格法是在 静态路径规划中避障过程搜索最优路径的常见方法。将工作区域划分成 n + m 个方格，每个方格的面积比一个机器人所占的面积略大。用状态 空间法表示机器人的信息，对机器人的位置进行n 个周期的预测，将两 个相邻周期的预测位置连成直线，若直线与某方格接触，则认为覆盖了 该方格的1 2 以上面积，对应的二维数组分量置1 ，其余数组分量茕0 。 2 1 最优路径的搜索就是在空的方格内寻找连通路径。 栅格法是目前研究较广泛的路径规划方法。该方法将机器人的工作 空间解耦为多个简单的区域，一般称为栅格。若某一个栅格范围内不包 含任何障碍物，则称此栅格为自由栅格；反之，称为障碍栅格。由这些 栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅 格的路径，该路径均由自由栅格构成，用栅格的序号来表示的。最后把 栅格序号转换成机器人空日】实际坐标，令机器人按此路径运动。 已经有许多学者用栅格法对环境空问建模柬解决问题并取得了较 好的研究效果j b o r e n s t e i n 曾采用g r i d s 表示环境，用势场法决策出v f f 算法和v f h 算法，并由此将栅格法的良好性能向人们展现出来。任世 军和洪炳熔等人在机器人的位姿空间中采用基于栅格扩展的策略解决 了机器人路径规划问题。薄喜柱等人用栅格法对机器人空间建模，参照 人类在人群中行走的经验对栅格地图进行进一步规划，成功的实现了足 球机器人路径规划问题。 3 3 2 利用栅格法进行路径规划 用栅格建模法进行机器人路径规划可以分为三个主要步骤： 1 模型的建立 首先根掘机器人和目标点的位詈划定规划区域，然后将该区域用网 格表示，每个网格就是一个栅格。栅格的大小是个关键因素，栅格选得 小，环境分辨率较大，但抗干扰能力弱，环境信息存储量大，决策速度 慢；栅格选得大，抗干扰能力强，环境信息存储量小，决策速度快，但 分辨率下降，在密集障碍物环境中发现路径的能力减弱。一般栅格大小 的选取和机器人的大小相关。最后对划分好的栅格编序号，栅格序号将 代表栅格所在的位置；并给每个栅格赋以一定的初值，栅格的值将代表 有障碍物的可能性。 2 障碍物地图的生成 模型建好以后，开始检测障碍物的位置，并根据障碍物位詈找到对 应栅格地图中的序号值，并对对应的栅格值进行修改。我们这罩定义不 包含障碍物的栅格为自由栅格，包含障碍物的栅格为障碍物栅格。 3 搜索无碰撞最优路径 一 机器人路径规划就是寻找一条从出发点到目标点的连续自由栅格 序列。具体的搜索方法有很多，如基于势场法的栅格路径搜索方法，用 遗传算法进行的路径规划方法，以及基于动态二叉树的a 算法等等。 言 8 6 0 a i 1 口 ， 厂一 ( j u 觚 雄m ) 图3 6 用栅格法进行足球机器人路径规划 3 3 3 栅格法的优缺点 用栅格法进行路径规划有如下的优缺点： 1