（检测技术与自动化装置专业论文）基于状态预测强化学习的移动机器人路径规划研究.pdf

山东大学硕士学位论文 摘要 随着机器人技术的发展，机器人己开始应用到未知环境，与静态已知环境下 的移动机器人路径规划研究相比较，对于动态未知环境探索应用问题，环境的未 知性和动态变化都给机器人路径规划带来了新的挑战。由于机器人不具有环境的 先验知识，移动机器人在环境探索过程中不可避免的会遇到各式各样的障碍物， 因此，研究具有灵活规划和避障功能的移动机器人及其在未知环境下的路径规划 具有重要的现实意义。本文将状态预测与强化学习算法相结合，分别对静态和动 态障碍物未知环境下移动机器人的路径规划进行了研究。 文章首先对移动机器人环境探索中路径规划的研究内容进行了综述，然后对 移动机器人环境探索下路径规划的研究现状及发展作了回顾，并对本论文的主要 结构进行了概述。 其次，详细介绍了有关移动机器人环境探索方面的知识、研究现状及存在的 问题，包括栅格地图的创建、到达目标点的代价和效用值的计算、目标点的定义 及分配策略等问题。然后，就路径规划的方法、传感器系统及多移动机器人路径 规划的冲突消解等相关内容作了详细的阐述。 第三，详细介绍了强化学习的基本概念、原理、方法、各种算法及研究现状 等问题，然后从单个机器人在静态障碍物环境中的路径规划入手，以q 强化学习 算法为基础，通过合理划分状态空间与动作空间，设计强化函数，描述了该算法 在路径规划中的具体应用。 第四，将强化学习算法与“预测”的思想相结合用于单个机器人在动态环境 下的路径规划，解决了针对规则运动障碍物和同时存在静态、动态障碍物两种环 境的避障问题。考虑到机器人前面每一步的决策对最后的成功或失败都有影响， 所以在算法中引入资格迹( e l i g i b i l i t yt r a c e ) 技术，采用改进的q 学习算法实现控 制。 第五，借用人类在动态复杂环境下确定自己下一步行动的预测机制思想，本 文将状态预测的方法与强化学习相结合，用于多移动机器人系统环境探索下的路 径规划。较以往单纯使用强化学习方法实现的路径规划，本文的方法更加合理的 实现了机器人之间的避碰，并通过预测函数降低群体强化学习空间维数、加快了 群体强化学习算法的收敛速度。 山东大学硕士学位论文 最后，对本文所作的工作和取得的成果作了总结，分析了可以进步改进的 地方，并对未来发展进行了展望。 关键词：移动机器人；环境探索；路径规划；强化学习；状态预测 i i 山东大学硕士学位论文 a b s t r a c t w i t ht 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 y ，i th a sb e g u nt ob ea p p l i e dt ou n k n o w n e n v i r o n m e n tn o w c o m p a r e dw i t l lt h er e s e a r c ho nt h ep a t hp l a n n i n gi n s t a t i ck n o w n e n v i r o n m e n t ，t h eu n k n o w ne n v i r o n m e n ta n dd y n a m i cc h a n g e sb r i n gn e wc h a l l e n g e st o t h ep a t hp l a n n i n go fe n v i r o n m e n te x p l o r a t i o nf o rm o b i l er o b o t i n e l u c t a b l y ，m o b i l e r o b o tw i l lm e e tv a r i o u so b s t a c l eb e c a u s eo fu n k n o w ne n v i r o n m e n tw h e ne x p l o r i n g t h e r e f o r e ，t h em o b i l er o b o tw h i c h c a l lo b s t a c l ea v o i d a n c ea n dv i v i dp r o g r a m m i n gi n u n k n o w ne n v i r o n m e n th a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c e i nt h i sp a p e r ，w eu s e r e i n f o r c e m e n tl e a r n i n gt os t u d yt h ep a t hp l a n n i n gf o rm o b i l er o b o tb o t hi ns t a t i ca n d d y n a m i ce n v i r o n m e n t f i r s t l y ，t h i sd i s s e r t a t i o ns u m su pt h er e s e a r c ho np a t hp l a n n i n gf o rm o b i l er o b o t e x p l o r a t i o n b a s e do nr e i n f o r c e m e n tl e a r n i n g t h e nr e v i e w st h er e s e a r c ha n d d e v e l o p m e n ta b o u tp a t hp l a n n i n go fm o b i l er o b o te n v i r o n m e n te x p l o r a t i o n t h e b a c k g r o u n da n dm a i nc o n t e n t so ft h i sd i s s e r t a t i o na r ed e s c r i b e db r i e f l y s e c o n d l y ，t h i sp a r ti n t r o d u c e st h er e l e v a n tk n o w l e d g e ，p r e s e n tc o n d i t i o na n d e x i s t e n tp r o b l e mw h i c hm o b i l er o b o te n v i r o n m e n te x p l o r a t i o ni nd e t a i l e d ，i n c l u d e e s t a b l i s h e do f 面dm a p s ，t h ec o s to fr e a c h i n gat a r g e tp o i n ta n di t su t i l i t y ，t h e d i s t r i b u t i o no ft a r g e t sf o rm u l t i p l er o b o t se t c t h e ne x p a t i a t i o nt h em e t h o do fp a t h p l a n n i n g ，s e n s es y s t e ma n d t h ec o n f l i c tr e s o l u t i o no fm u l t i m o b i l er o b o t t h et k r d p a r t i n t r o d u c e st h ec o n c e p t ，p r i n c i p l e ，m e t h o d ，a l g o r i t h ma n dt h e r e s e a r c ho fp r e s e n tc o n d i t i o na b o u tr e i n f o r c e m e n tl e a r n i n gi nd e t a i l e d t h e n ，a i m i n ga t t h es t a t i ce n v i r o n m e n te x p l o r a t i o no fs i n g l er o b o t ，t h ek e yt od e s c r i b e dt h ep a t h p l a n n i n gs t r a t e g yb a s e do nq r e i n f o r c e m e n tl e a r n i n gb yd i v i d i n gt h es t a t ea n da c t s p a c e ，s t r u c t u r i n go f r e i n f o r c e m e n tf u n c t i o ne t c t h ef o u r t hp a r tu s e st h er e i n f o r c e m e n tl e a r n i n ga n dt h et h o u g h to fp r e d i c t i o na t s i n g l er o b o tp a t hp l a n n i n gi nd y n a m i ce n v i r o n m e n t ，t h a ti no r d e r t os o l v et h ep r o b l e m o fo b s t a c l ea v o i d a n c e b e c a u s eo ft h ee a c hp r e v i o u ss t e pd e c i s i o nt ot h es u c c e s so r f a i l u r e ，o u ra p p r o a c hl e a dat e c h n i q u eo fe l i g i b i l i t yt r a c ea n du s et h ei m p r o v e m e n to f i i i 山东大学硕士学位论文 qr e i n f o r c e m e n tl e a r n i n ga l g o r i t h mt oc a r r yo u tt h ec o n t r 0 1 t h ef i f t hp a r to ft h i sd i s s e r t a t i o nl e a r n sf r o mm a n k i n dw h om a k es u r et h r o u g h t h ep r e d i c t i o n ，a n dc o m b i n e st h es t a t ep r e d i c t i o nw i t ht h er e i n f o r c e m e n tl e a r n i n gu s e s f o rm u l t i m o b i l er o b o ts y s t e mo np a t hp l a n n i n g t h ea p p r o a c hi sm o r er e a s o n a b l et h a n t h em e t h o dw h i c ho n l yu s er e i n f o r c e m e n tl e a r n i n ga l g o r i t h m ，a n dt h a tc a r r yo u tt h e r e a s o n a b l ec o l l i d ea v o i d sb e t w e e nt h er o b o t ，i no r d e rt ol o w e ras p a c es i z ea n dr a i s e c a l c u l a t i o ns p e e d f i n a l l y ，c o n c l u s i o n sa r eg i v e n 谢t l lr e c o m m e n d a t i o nf o rf u t u r ew o r k k e yw o r d s ：m o b i l er o b o t ；e n v i r o n m e n te x p l o r a t i o n ；p a t hp l a n n i n g ；r e i n f o r c e m e n t i v l e a r n i n g ；s t a t ep r e d i c t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 己在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：焦避日期：坦童：! ! ：董 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：隧导师繇弛卜日期：遨限5 山东大学硕七学倪论文 第一章绪论 1 1 引言 随着机器人技术不断向智能化方向发展，移动机器人作为控制领域中最年轻 的一代，已成为上世纪8 0 年代以来在智能控制方面的主力军。由于移动机器人具 有移动性，从而具备代替人作业的实力，不仅在工业领域被广泛应用，在繁重、 危险、恶劣、外太空等作业环境下也是不可缺少的工具，成为辅助人类在完成空 间与深海作业、精密操作，高温作业等方面的关键技术装备，具有重要的军用和 民用价值。 然而，移动机器人在环境探索过程中不可避免的会遇到各式各样的障碍物， 灵活、实时的躲开这些障碍物是衡量其性能的关键指标。因此，具有灵活规划和 避障功能的移动机器人拥有相当高的社会价值，由此产生的路径规划问题成为移 动机器人完成任务的安全保障，同时也是移动机器人智能化程度的重要标志。在 全局环境已知的路径规划研究方面，不少学者已经做了大量工作，并取得了令人 满意的效果。但是，机器人的实际工作环境往往是未知的，不确定的。在未知环 境中作业的移动机器人执行任务之前往往不能得到环境的全部信息，所以不能使 用传统的基于环境精确信息的路径规划方法，特别是在动态环境下，环境随时问 变化会导致规划跟不上实际环境信息的变化，所以目前对于机器人在局部未知的 动态环境下的路径规划问题成为一个研究热点。 随着机器人技术的迅猛发展，人们对移动机器人的研究重点已经从单个机器 人转移到多机器人系统。多机器人的研究内容和应用范围日益广泛，如多机器人 协作搬运、环境探索和地图构建，多机器人觅食，以及机器人足球赛等。与单个 机器人相比，多机器人系统以其较强的冗余型、鲁棒性、灵活性和经济性等特点 可以通过协作更可靠、更快速、更廉价地完成指定的任务。为了使机器人系统具 有适应未知环境的能力，研究人员将学习和协作进化行为相结合，使多机器人协 作成为机器人研究中最有效的方法之一。 近年来，逐步应用移动机器人的技术领域包括：环境探索、运动控制、路径 规划、定位与导航、多机器人协作、多传感器数据融合、机器人学习、高性能计 算、无线通讯和互联网技术等。以下对本论文涉及到的环境探索、路径规划、多 移动机器人协作和机器人学习等内容作概括性介绍。 山东大学硕七学位论文 1 1 1 环境探索 多数情况下机器人的工作空间信息并不是预先知道的，这就需要机器人能对 环境进行有效地探测，构造出环境地图或者边构建地图边执行任务，由此就产生 了环境探索及地图构建的问题。 最初的环境探索任务是采用单个机器人完成，其缺点是探测速度慢，感知环 境信息欠完整。随着多机器人协作在未知环境中研究的深入，自8 0 年代以来，多 移动机器人协作系统在环境探索领域的应用逐渐受到了人们的关注，并逐渐成为 机器人领域的研究热点之一。采用多机器人协作进行环境探索可以提高效率与准 确度。 从系统结构上来说，多机器人环境探索系统通常可以分为两类：集中式和分 散式。集中式系统可以得到近似最优解，但是计算量大，并且中央控制器的单点 故障会使得整个系统崩溃。分散式系统结构灵活、鲁棒性强，又分为分布式和分 层式两种。分布式系统中机器人关系平等，通过与其他机器人的信息交换，自主 进行决策。该系统具有很好的灵活性、冗余性和鲁棒性，但容易产生次优解。分 层式结构介于集中式和分布式之间，具有更强的灵活性和可扩展性，但是计算量 大，易产生冲突死锁现象。目前的多机器人协作系统常采用分布式控制结构来提 高系统的灵活性和鲁棒性，因此建立在分布式控制系统上的多机器人协作策略的 制定成为多机器人研究的一个重点和难点。 多移动机器人协作环境探索的研究，有力地推动多机器人学的发展，并且在 工业、民用和特种领域( 国防、航天、海洋等) 具有广阔的应用前景。 1 1 2 路径规划 路径规划是移动机器人的一个重要组成部分，其任务是在具有障碍物的环境 内按照一定的规则，寻找一条从起始状态( 包括位置和姿态) 到达目标状态( 包括位 置和姿态) 的无碰撞路径【l 】。未知环境下的移动机器人路径规划是传感器信息处 理过程与机器人控制过程的结合，是机器人利用传感器所反馈的信息产生控制命 令将其引导至预定目标点的过程。 一般的路径规划都会涉及到位姿空间、环境表示、规划方法和搜索方法等问 题，根据研究内容主要有以下几种分类形式： 按照环境信息的完整程度，路径规划主要包括基于己知地理信息的全局路径 2 山东大学硕士学位论文 规划和基于传感信息的局部路径规划，又分别称为静态路径规划和动态路径规 划。全局路径规划需要知道关于环境的所有消息，根据环境地图进行大范围的路 径规划。全局规划方法通常可以寻找最优解，但是需要预先知道环境的准确信息， 并且计算量很大。规划路径的精确程度取决于获取环境信息的准确程度。而局部 路径规划则只需要机器人较近的障碍物信息，让机器人具有良好的避碰能力。由 于自主式移动机器人在地面上行进，必须避开它无法通过或对其安全行驶构成威 胁的障碍物或区域，因此局部路径规划，尤其是复杂环境下的路径规划问题显得 更为重要。 根据获得环境信息的方式可分为基于模型的路径规划和基于传感器的路径 规划【2 1 。在基于模型的方法中，环境的信息被预先学习并存储下来，机器人及障 碍物用实体模型来表达。这种方法适用于己知结构化环境下的路径规划，是种 离线路径规划方法。基于传感器的路径规划是利用传感器获得环境信息，根据机 器人的任务，实时规划出机器人的运动轨迹，这种方法可以处理环境中的不确定 因素，实现在线路径规划。 根据机器人数量可分为单个机器人作业和多机器人协作。多机器人协作的路 径规划不仅要研究单个机器人的导航与避障问题，还要考虑多个机器人之间的避 碰问题。 根据环境结构化可分为静态已知环境、静态未知环境、动态不确定环境等。 1 1 3 多机器人协作 按照机器人之间相互约束的关系，习惯上将机器人之间的协作分为松散协 作、紧密协作。正确处理好单个机器人之间的协调合作关系是发挥其优势的关键。 体系结构与控制一直是多机器人系统的一个研究重点，它是多移动机器人系 统行为的基础，决定了系统的能力。在确定体系结构时，要考虑行为选择方式、 通信结构、同构还是异种机器人以及冲突消解等问题。集中式体系结构可用一个 单一的智能体来控制，分散式结构中的分布式体系结构则缺少这样一个智能体， 分布式结构中所有智能体相对于控制是平等的，另一种分散式结构分层式在 局部则是集中的。一般来说分散式结构在某些方面，如故障冗余、可靠性、开发 的自然性和可伸缩性等方面比集中式结构要好。实践中很多系统并不是单一的结 构，往往是混合式的，许多大型的分散式控制结构中包括了局部的集中控制结构。 山东大学硕士学位论文 随着多智能体系统研究的不断深入，其很多研究方法和成果在相关学科中得 到应用。尽管智能体是一个抽象的、理想化的计算实体，而多机器人系统的机器 人是一个具体、真实的物理实体，两者存在明显的差别，但多机器人协作系统具 备空间分布、功能分布、时间分布等特点，要研究的问题和多智能体系统要研究 的问题非常类似，二者有非常类似的拓扑结构、组织方式和运行机制。因此，多 机器人系统的研究也借鉴了不少多智能体系统的相关方法和技术。 多移动机器人协作系统的应用领域是很广阔的，具有潜在的巨大的技术市 场，例如：( i ) - i - 业领域：自动化生产线中，机器人群体系统可以担负起人类的作 用，完成一些复杂的工作。在危险或恶劣环境中可以代替人类自主完成复杂作 业。( 2 ) 医学领域：大量的微机器人进入肠道、胃或血管等人体内狭窄部位进行 检查、发现和修补病变；( 3 ) 军事领域：使用机器人群体进行侦察、巡逻，排雷等； ( 4 ) 航天领域：利用机器人群体进行卫星和空间站的内外维护以及星球探索等。 目前，多机器人系统协作的主要研究问题有觅食问题、多目标观测问题、未 知环境探测、地图构建、路径规划、机器人足球、群体搬运、推箱子、围捕等。 1 1 4 移动机器人的学习方法 自然界始终是人类灵感的重要来源，高等动物适应环境的能力则主要来源于 学习和进化，即根据对环境的信息感知，作出决策和行动。多机器人系统学习是 系统不断寻找或优化控制参数、适应外界环境变化的一种手段。多数研究者认为 要使机器人系统具有更大的潜能，其控制系统应具有学习能力。 现在已经提出多种学习方法，如神经网络、进化算法、强化学习以及它们的 一些组合。目前强化学习方法和进化算法已在协作机器人学中被使用，使系统具 有适应性和灵活性。然而，几乎所有的方法在所需学习的任务变得复杂时，性能 会变得很差。复杂的任务通常需要复杂的控制器，于是就需要大量的参数刻画他 们，这就引起了状态空间到动作空间映射的组合爆炸，给算法带来了繁重的任务， 极大提高了问题的难度。t h n m 等【3 】认为：对于自主机器人而言没有优化的、通 用的学习技术，学习技术需要在许多实际问题中得到协调。一般而言，一个机器 人学习体系结构通用性越强，想成功地进行某一行为的学习所需要的试验就越 多。对这些问题h a g i t 等【4 】提出了采用对机器人的学习任务进行问题分解以及结合 先验知识的方法来指导学习过程，用多种方法组合的办法来克服单个实验方法的 山东大学硕士学位论文 缺点也许是另外一条可行的道路。 在各种学习方法中，强化学习具有较强的在线自适应性和对复杂系统的自学 习能力，且能较好地符合人们解决问题的，t l , 理习惯，在机器人研究中受到了广泛 的关注。本文将强化学习的方法引入到移动机器人环境探索中的路径规划这一研 究领域，针对不同的学习环境应用一系列灵活有效的路径规划策略、避障策略和 机器人之间的避碰策略，结合强化学习算法使机器人可以实现对未知环境的快 速、精确的探索，同时使整个系统具有较高的冗余性和鲁棒性，能够适应多变的 甚至是动态的未知环境。有关强化学习的主要内容本文将在第三章详细介绍。 1 2 移动机器人路径规划的发展及研究现状 1 2 1 移动机器人环境探索的发展及研究现状 最初的多机器人环境探索是在单个机器人的基础上进行了简单的数量扩充， 机器人之间没有协调，各机器人独立工作，只有当机器人在通讯范围内时，互相 交换环境地图信息。在环境探索策略方面，移动机器人都是简单的沿墙行走【5 】 或随机行走【6 】等被动探索策略，只适用于结构化的较小环境，探索效率低。 y a m a u c h i 提出各机器人建立一个公用占有率栅格地图 7 】，并引入边界的概念【8 1 。 近几年来，随着多智能体系统( m u l t i a g e n ts y s t e m ，m a s ) 相关理论、技术和 各种智能算法的开发和发展，一些新思想、新理论，如经济学、心理学、人工免 疫学、管理学及仿生技术、遗传算法、进化计算、机器学习等被广泛运用于多机 器人协作环境探索中。基于市场法的协商机制【9 】采用完全分布的结构，具有计算 量小，通讯量少等特点。基于经济学的拍卖理论 1 0 i i ，作者将经济学中的拍卖 概念引入多机器人环境探索中，将机器人视为竞标者，将不同的目标点视为待拍 卖物品。而另一文献【1 2 】中，作者也运用了类似的思想，只是在目标点的选择过 程中，考虑了各机器人之间互相的影响，在代价计算方面做了较细致的研究。文 献【1 3 】中，在实际的空中机器人和地面机器人之间的协同问题上，作者做了研究， 并通过试验验证了其算法的有效性。而文献【1 4 懈决的是水下机器人协同探索水 下多变环境的问题。 在多移动机器人环境探索方面的主要代表性研究工作有：c a i 和p a g a c 分别 用范围传感器进行了单个机器人和多个机器人对简单环境的探测【1 5 , 1 6 】。h a n s 用 基于特征的方法产生扩展卡尔曼滤波器对机器人的定位与环境图绘制加以合成 山东大学硕士学位论文 【1 7 】。a r a u j o 和d u e k e r 分别将模糊a r t 神经网络结构及预测性轨迹过滤方法【t s , 1 9 引入了机器人的学习中，实现环境信息的更新。m o o r e h e a d 的研究中引用了 g r e e d ys e a r c ha l g o r i t h m 来搜集环境信息【2 0 l 。y a m a u c h i 利用f r o n t i e rc e l l 理论， 提出各机器人建立一个公用占有率栅格地图，并引入了边界的概念【引，每个机器 人前往离它最近的边界获得新信息。由于各机器人之间除了共享地图信息以外没 有协调，因此这种方法会出现机器人之间重复探索的情况。s i m m o n s 基于 y a m a u c h i 的边界概念，采用事件积分法提出多机器人环境探索的协调机制【2 i 】， 由中央机器人根据各机器人的投标为各机器人分配边界点，因为整个系统是一个 集中式的结构，中央机器人的单点故障会使得整个系统崩溃。v a z q u e z 提出的分 散式多机器人环境探索方法【2 2 1 。z l o t 等提出利用市场机制解决多移动机器人协作 探索的问题【9 1 ，作者采用完全分布式系统，机器人之间共享目标点信息，它们之 间的协作通过投标来实现。b u r g a r d 等在文献【1 2 】的基础上进一步提出了基于边界 的多移动机器人协作环境探索策略。 虽然近年来在多机器人环境探索研究中已经取得了卓有成效的成果，但仍存 在一些问题，比如如何能建立一种合理的探索任务描述方式来表示探索环境信 息；动态环境下目标点的选择问题；基于行为选择的决策理论在实际中的应用； 多机器人坐标间的标定以及研究方法的局限性等。 1 2 2 移动机器人路径规划的研究现状 路径规划方法是依照环境信息，给机器人规划出一条从起点到目标点的无碰 撞路径。规划路径的精确程度取决于获取环境信息的准确程度。 国内外的研究者在移动机器人路径规划方面己经做了大量的研究工作。易 展，樊晓平，罗熊等运用图论及k s t r a 算法 2 3 】，研究了由大尺度简单多边形障碍 物构成的平面场景情况下，平面移动机器人最短路径规划的几何算法，给出了详 细的算法实现。当存在有凹多边形的障碍物情况时，该算法可大大降低计算量。 文献【2 4 】利用可视图法将搜索最优路径的问题就转化为从起始点到目标点经过这 些可视直线的最短距离问题。e d r i n c 采用人工势场法进行机器入的路径规划【2 5 】， 人工势场法把移动机器人在环境中的运动视为一种在抽象的人造受力场中的运 动，目标点对移动机器人产生“引力 ，障碍物对移动机器入产生“斥力，最 后通过求合力来控制移动机器人的运动。文献【2 6 】分析了k o h o n e n 神经网络算法及 6 山东大学硕士学位论文 其识别机理，提出了k o h o n e n 神经网络和b p 神经网络结合起来进行路径规划的 方法，给出了具体的算法，探讨了在神经网络技术中引入学习机制的特点。文献 【2 刀采用栅格法表示机器人工作环境模型，用序号编码，直角坐标与序号混合应 用，采用遗传算法产生初始路径种群，并对其优化找出最短路径，然后增加删除、 插入算子达到路径规划中避障的要求，通过仿真表明遗传算法进行避障和路径规 划的有效性和可行性。p a r k 等提出了一种人工势场法和模拟退火相结合的路径规 划方法，其中人工势场法的引入增加了系统规划的鲁棒性，而模拟退火的引入又 可以跳出局部最优 2 s 】。文献 2 9 】提出一种基于模糊概念的动态环境模型，参照物 体的位置和运动信息构造二维隶属度函数，然后通过模糊综合评价对各个方向进 行综合考察，得到搜索结果。该方法在移动障碍物和移动目标的环境中能有效地 实现机器人避碰和导航。l e e 等提出一种未知环境下的高级机器人模糊导航方法， 由超声传感器来提供环境信息，然后利用基于模糊控制的导航器来计算这些信 息，规划机器人路径3 0 1 。文献提出了一种新的移动机器人路径规划方法。在 局部规划中采用基于行为和模糊规则库的方法，采用基于模糊规则的避障行为来 实时避障，当无障碍物威胁时又寻找全局路径上的最近节点回到全局路径上，饼 通过实验证明该方法节省系统计算时间，是一种简单的、较优的路径规划方法。 l e b e d e v 等提出了一种在动态环境下应用神经网络进行路径规划的方法，此神经 网络是离散的时间和动态环境，计算效率高，并且环境的信息在过程中通过神经 网络的学习而得到【3 2 】。z a f e r 等在采用离散空间进行路径规划的同时，将问题更 深入化，栅格序号采用二进制编码，统一确定其个体长度，随机产生障碍物位置 及数目，并在搜索到最优路径后，再在环境空间中随机插入障碍物，模拟环境变 化，通过仿真结果验证了算法的有效性和可行性。但是，规划空间栅格法建模还 存在缺陷，即若栅格划分过粗，则规划精度较低；若栅格划分太细，则数据量又 会太大【3 3 】。d a v i e s 等采用栅格法建模，应用遗传算法设计了一种在3 d 静态和动 态环境中路径规划的方法【3 4 】。 1 2 3 多移动机器人协作系统的发展与研究现状 有关多机器人协作的研究国外起步较早且发展很快，而国内在这方面的研究 刚刚起步。早在8 0 年代初，欧美、日本一些研究人员就开始研究移动多机器人系 统。日本名古屋大学的f u k u d a 教授提出的c e b o t 系统，每个机器人可以自主地 7 山东大学硕士学位论文 运动，没有全局的世界模型，整个系统没有集中控制，可以根据任务和环境动态 重构、可以具有学习和适应的群体智能，具有分布式的体系结构 3 5 1 。当前，在 多机器人协作系统的理论研究中，主要有基于协调的协作( c c p ) 和基于帮助的协 作协议( h c p ) ，但这两个协作协议各具有其局限性。因而，国内外科学家在该领 域展开了更深入的研究 3 6 , 3 7 , 3 8 】。欧盟在9 7 年设立了专门进行多机器人系统研究的 项目m a r t h a l a l ，即“用于搬运的多自主机器人系统”( m u l t i p l ea u t o n o m o u sr o b o t s f o rt r a n s p o r t i n ga n dh a n d i n ga p p l i c a t i o n ) 3 9 1 。除此之外，很多文献对多机器人协 作进行了深入的研究【4 0 4 1 4 2 4 3 舯 4 5 1 。 1 3 本文的主要研究工作及结构 本文以移动机器人在环境探索中的路径规划为研究背景，将强化学习方法分 别用于单个机器人在静态、动态环境和多移动机器人通过协作在不确定环境中， 解决机器人的避障和避碰问题，使移动机器人能够快速有效的找到一条最优或较 优的路径到达目标地点，同时使系统以资源和信息的最大化被利用，并通过仿真 实验验证算法的有效性。本文主要分为五个大部分，结构安排如下： 第一章为引言部分，针对本文的研究内容就移动机器人在环境探索、路径规 划、多机器人协作和机器人学习等方面内容做了概括性介绍，并对各研究内容的 发展和研究现状进行了阐述，最后介绍了本文的主要内容和结构。 第二章对多移动机器人系统协作环境探索的相关问题作了详细介绍，包括栅 格地图的创建、目标点的定义、代价和效用值的计算以及目标点的分配策略等。 然后就各种不同情况下的移动机器人路径规划进行了重点归纳。本章的最后是小 厶 ；口。 第三、四、五章是本文的重点，从内容编排上由浅入深的介绍了强化学习算 法在移动机器人路径规划方面的应用。 第三章首先详细介绍强化学习的相关问题，如强化学习的概念、原理、主要 算法及研究现状等。然后将强化学习的方法应用到单个移动机器人在静态未知环 境中的路径规划，结合一种路径规划策略，完成了学习过程中涉及的基本状态与 基本动作的划分、强化信号的设计等工作，并对相应强化学习算法进行了描述。 最后通过仿真实验验证了探索策略及状态、动作、强化信号设计的合理性，实现 了机器人的避障和路径规划。 & 山东人学硕士学位论文 第四章在上一章的基础上，我们又将强化学习的方法应用到单个移动机器人 在动态未知环境中的路径规划中，结合相应的路径规划策略，重新设置了学习过 程中的基本状态与基本动作的划分、强化信号的设计等，同时对相应强化学习算 法进行了描述。同时对算法中应用到的资格迹技术原理作了介绍。随后进行了仿 真实验验证了算法的有效性。 第五章以多移动机器人系统为研究对象，将状态预测与强化学习方法相结 合，通过机器人之间在不确定环境下的协作策略解决环境探索过程中的路径规划 问题，实现个体机器人的避障和机器人之间的冲突消解，提高到达目标点的效率。 最后进行仿真实验并给出了实验结果和分析。 最后是论文的总结及对相关工作进行了下一步展望。 9 山东大学硕士学位论文 第二章移动机器人环境探索及路径规划研究 2 1 引言 环境探索与地图构建是移动机器人研究领域里一个重要的研究方向，已经得 到许多研究人员的关注。环境探索的目的是在完全未知的环境中，机器人自主地 依靠传感器所提供的信息，用最短的时间收集到最多的环境信息，建立起作业环 境的地图，以便于机器人在未知的动态环境中自主地完成各种智能任务，如导航、 路径规划、避障策略等。 本文的研究内容是移动机器人在环境探索的研究背景下已完成目标点的分 配，从起点到目标点的移动过程中进行路径规划，在避障与避碰的同时选择最优 或较优的路径，用最短的时间，最省的能量顺利到达目标点。本章作为本文研究 内容的基础，主要包括两部分内容，一是详细介绍了多移动机器人系统协作环境 探索的相关问题，包括栅格地图的创建、目标点的定义、代价和效用值的计算和 目标点的分配策略等；二是对移动机器人的路径规划做了详细的阐述。 2 2 移动机器人环境探索 2 。2 1 环境地图的创建及表示方式 探索过程的目的是用最少的时间覆盖整个探索环境，因此各机器人必须构造 一张环境地图以便规划他们的路径、协调他们的行动，并且要求机器人之间能够 及时的相互通讯，告知已经探索过的环境区域和彼此的位置信息，以免造成重复 探索。早期的许多系统是由机器人在人工控制下采集到构建地图的数据信息，然 后通过离线的学习算法找到与数据匹配最好的地图来。但是这种方法，容易造成 人工误差，并且对于复杂的环境很难获得完整的地图信息。因此，目前采用让机 器人自动搜索来构建地图的方法，自动标示出未探测区域，通过己知信息的导航， 使用范围传感器不断探测新的未知区域，更新环境地图【7 4 6 4 7 】。 在机器人环境探索的研究中，有关环境的描述方法有很多，用于构建室内环 境的主要有两种模式 4 8 1 ：几何模式( g e o m e t r i c b a s e dm o d e l ) 和拓扑模式 ( t o p o l o g i c a lm o d e l ) 。其中几何模式主要是栅格地图，以及在栅格地图的基础上 采用的基于环境特征的表示方式。e n g e l s o n 的文章【4 9 j 中提到，采用栅格地图表示 环境的优点是计算量少，构建速度快，来自不同的传感器的信息数据容易进行融 1 0 山东大学硕士学位论文 合，而且这种方法是以概率统计学的方式将探测结果可靠的表达出来。鉴于以上 优点，本文的环境信息构建即采用了栅格地图的方法。 拓扑地图是将环境表示为一张拓扑意义中的图，图中的节点对应于环境中的 一个特征状态地点，如果节点间存在直接连接的路径则相当于图中连接节点的 弧。拓扑地图最大的优点是简洁，不需要机器人准确的位置信息，对机器人的位 置误差有更好的鲁棒性。 2 2 2 目标点的定义 本论文的环境创建都是采用的栅格地图表示方法，即每个栅格都有两种状 态：存在障碍物( f u l l ) 和不存在障碍物( e m p t y ) ，机器人通过计算每个栅格的占有 概率，得到环境信息。以下我们就b u r g a r d 等人的研究成果【5 ，详细介绍有关目 标点的定义、代价和效用值的计算，最终给出一种较合理的目标点分配策略。 机器人在探索未知的环境时，往往对“边界点或边界区域”特别感兴趣。所谓 边界点就是与机器人已经探索到的栅格相邻的、未知的、没有被探索到的栅格， 如果这些栅格连成一片区域，则称为边界区域。只要我们的方法能引导机器人向 边界位置移动，那当他们到达该区域的时候，机器人就能获得未知区域的新信息。， 因此，我们将边界定义为机器人有可能到达的目标点。当机器人完成一轮探索后， 则又会产生一系列新的边界区域。 通常一张环境地图可能会包含若干个边界点或边界区域，这样就产生了一个 问题：怎样利用边界点为每个机器人分配探索任务。同时，因为多移动机器人系 统包含多个机器人，还应考虑避免几个机器人向同一个区域移动，造成重复探索 的现象。为了解决以上问题，文献【5 l 】使用了决策理论的方法，同时考虑机器人 到达边界点的代价和该边界点的效用值，为单个机器人确定恰当的目标区域，以 实现最优的分配策略。 本文的仿真实验中，目标点通常取任意一段连续边界区域上的一点( 如中 点) 。 2 2 3 代价值计算 对于系统中的每个机器人来讲，经过一个栅格( x ，y ) 的代价k 埘) 与该栅格 的占有概率p ( o c c 。) 成正比，而且机器人到达相应目标点的代价值又与机器人到 目标点之间的距离成比例。因此，机器人到达最近目标点的代价值实际是两点之 山东大学硕士学位论文 间途经栅格代价累积最少的一条路经。为了确定机器人到达所有边界点的代价， 为下一步行走选择合适的目标点，文献【5 1 1 基于动态规划值迭代的方法，计算机 器人从当前位置到所有边界点的累积代价，选择代价值最小的一条路经作为最优 路径。最小代价值的计算为： ( 1 ) 初始化：被机器人占据的栅格赋初值0 ，其他栅格赋初值0 0 = 怪然s i s e 灿m p 0 5 i 廿 ( 2 ) ( 2 ) 循环更新：对于所有栅格( x ，y ) 都进行式( 2 2 ) 代价值的计算 k 训) = m i n 畋池y + 缈+ 缸2 + 缈2p ( o c c ，+ 却+ 缈) i 缸，妙 一1 ，0 ，1 】j ( 2 2 ) 可见，哪个位置栅格的占有概率大，机器人就向哪个方向移动，只要环境是 有界的，并且机器人行走的代价不是负值，就能保证算法的收敛性。 2 2 4 效用值的计算 因为要考虑很多因素，估计目标点的效用值是非常困难的。机器人到达边界 点的效用值一方面取决于向它移动的机器人的数目，如果已经有机器人向特定的 目标点移动，对于其他机器人来说该栅格的效用值要降低。另一方面，机器人要 考虑已分配的边界到待分配边界点的距离，以及到达已分配边界后，待分配的边 界点是否还在其传感器感知范围内。在文献 5 l 】中，根据机器人传感器可以覆盖 栅格的概率值来计算效用值。具体算法为： ( 1 ) 初始化：对所有边界赋同一个初值u ( 2 ) 计算目标点r 距离栅格d 之间的范围被机器人传感器覆盖的概率p ( d ) ： 附) ：l d 面d 觚 - j 算法属于基于行为的反应式方法，反应快，并 且允许存在一定的噪声，十分有利于自主移动机器人在较短的时间内根据传感器 的信息确定应采取的动作。从学习的角度看，探索是机器人获得知识的重要手段， 从而确定最优策略，但是单纯的探索会造成系统。- i , 工t 4 - 缶月匕v _ , 的下降。强化学习系统可以 对探索和扩张两个问题进行平衡，即在保证获得较多的知识的同时可以获得较高 的回报。因此，本文将强化学习方法应用于移动机器人环境探索下的路径规划， 使机器人顺利完成探索任务。 2 3 2 移动机器人的传感器系统 移动机器入要具备在环境中的行走能力，必须能够无碰撞的从一个起点运动 到目标点，这就需要机器人能感知环境信息并对信息进行处理。实现这一要求就 需要为机器人装备各种形式的传感器，用于各种信息的获取。 移动机器人的传感器分为外部传感器和内部传感器。 外部传感器由视觉传感器、超声波传感器、红外传感器、接触与接近传感器 、 等。视觉传感器采用高精度摄像头进行机器人的视觉导航与定位、目标识别及地 t 6 山东大学硕士学位论文 图构建等。超声波传感器用于获得机器人工作环境中障碍物的距离信息，来构建 环境地图。红外传感器采用红外接近开关探测机器人工作环境中的障碍物，以避 免与其发生碰撞。接触与接近传感器多用于机器人之间的避碰规划。 内部传感器包括编码器、里程计、陀螺仪等。编码器能够大致确定出机器人 的位置。里程计和机器人的两个后轮同轴安装，用于测量两个后轮的行走距离。 陀螺仪用于测量机器人的旋转角度，从而计算出机器人的移动方向。 2 3 3 多移动机器人在路径规划中的冲突消解 多机器人路径规划的目的是为每个机器人规划出与环境障碍物及其它机器 人都无碰撞的路径，解决机器人之间可能发生的冲突。所谓冲突消解，就是解决 机器人之间的行进冲突问题，要尽量减少这些冲突的发生，或者当冲突发生时尽 快将冲突化解【6 0 1 。机器人的运动冲突主要有：碰撞、堵塞、死锁。所谓“碰撞” 是指两个或多个移动对象同时占据同一个位置；“堵塞”是指其它机器人的运动阻 止了一个机器人以指定的速