（控制理论与控制工程专业论文）基于模拟退火q学习的移动机器人路径规划技术研究.pdf

硕士论文 基于模拟退火- q 学习的移动机器人路径规划技术研究 摘要 在各项技术研究中，导航技术是实现移动机器人智能化和自主性的一项关键技术， 也是目前的研究热点之一。而路径规划是导航技术中的基本问题，因此，研究移动机器 人路径规划技术，提高移动机器人对未知环境适应性，对实现移动机器人智能性和自主 性具有重要意义。 本文在分析了移动机器人路径规划方法的基础上，对强化学习中的q 学习算法进行 重点研究。针对基于强化学习的路径规划在奖赏函数设计、探索与利用的平衡、连续状 态和动作空间的泛化等方面存在的问题，设计了相应的解决方案，提出了未知环境下移 动机器人路径规划算法。 针对奖赏函数影响收敛速度的问题和探索与利用的平衡问题，提出了基于行为分解 奖赏函数的模拟退火q 学习的移动机器人路径规划算法。为了降低奖赏函数对收敛速 度的影响，设计了基于行为分解非均匀结构的奖赏函数；同时，为了解决探索与利用的 平衡问题，采用模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 方法进行动作选择。仿真实验表明， 该算法提高了收敛速度，有效解决了探索与利用的平衡问题，使移动机器人找到了较优 路径。 为了提高s a q 学习的收敛速度和基于动态规划的q 学习性能，提出了一种基于动 态规划的s a q 学习算法。通过动态规划对值函数进行逆序更新，加快收敛速度；采用 模拟退火动作选择策略，提高算法性能。仿真结果表明，该算法具有更快的收敛速度和 更高的性能，并且移动机器人能够找到一条无碰撞的路径。 针对复杂未知环境中连续状态和动作空间的泛化问题，提出了基于模糊推理的 s a q 学习移动机器人路径规划算法。模糊推理系统对连续的状态和动作进行泛化，并 确定系统输出动作，通过q 学习来修改模糊规则。仿真实验表明，该算法具有较强的泛 化能力，可以有效解决移动机器人在复杂环境中的路径规划问题。 关键词：机器人，路z 一 1 i ，强化学习，q 学习，模拟退火，模糊推理 a b s t r a c t 硕士论文 a b s t r a c t a m o n gt h et e c h n i c a ls t u d yo fm o b i l er o b o t ，n a v i g a t i o ni sak e yt e c h n o l o g yo f i n t e l l i g e n c ea n da u t o n o m y ，a n da l s oo n eo ft h ec u r r e n tr e s e a r c hf o c u s p a t hp l a n n i n gi st h e b a s i ci s s u eo fn a v i g a t i o n ，t h e r e f o r ei ti so fg r e a ts i g n i f i c a n c ef o ri n t e l l i g e n c ea n da u t o n o m yt o r e s e a r c ho nm o b i l er o b o tp a t hp l a n n i n ga n di m p r o v et h ea d a p t a b i l i t yo ft h eu n k n o w n e n v i r o n m e n t a f t e ra n a l y s i n gm e t h o d so fm o b i l er o b o tp a t hp l a n n i n g ，t h et h e s i sf o c u s e so nt h e r e i n f o r c e m e n tl e a r n i n go fq l e a r n i n g h o w e v e r ，t h e r ea r em a n yi s s u e si np a t hp l a n n i n gb a s e d o nr e i n f o r c e m e n tl e a r n i n g ，s u c ha sr e w a r df u n c t i o nd e s i g n i n g ，t r a d e o f fo fe x p l o r a t i o na n d e x p l o i t a t i o n ，g e n e r a l i z a t i o no fc o n t i n u o u ss t a t ea n da c t i o n ，e t c a c c o r d i n gt ot h ea b o v ei s s u e s ， s o m es o l u t i o n sa r ec o r r e s p o n d i n g l yp r e s e n t e d ，a n dt h e a l g o r i t h m f o rm o b i l er o b o tp a t h p l a n n i n gi nu n k n o w ne n v i r o n m e n ti sp r o p o s e d t h es p e c i f i cw o r ki sa sf o l l o w s ： t os o l v et h ei m p a c to nt h ec o n v e r g e n c er a t ea n dt r a d e o f fo f e x p l o r a t i o na n de x p l o i t a t i o n ， as a ql e a r n i n gb a s e do nb e h a v i o r b a s e dd e c o m p o s i t i o no fr e w a r df u n c t i o nm o b i l er o b o t p a t hp l a n n i n gm e t h o di sp r o p o s e d w h i l ea l lu n e v e nr e w a r df u n c t i o ni sd e s i g n e dt om i n i m i z e t h ei m p a c to nt h ec o n v e r g e n c er a t e ，s i m u l a t e da n n e a l i n g ( s a ) a p p r o a c hi su s e dt os e l e c ta c t i o n t os o l v et r a d e o f fo fe x p l o r a t i o na n de x p l o i t a t i o n s i m u l a t i o nr e s u l t ss h o wt h a tt h em e t h o dh a s i m p r o v e dt h ec o n v e r g e n c er a t e ，s o l v e dt r a d e o f fo fe x p l o r a t i o na n de x p l o i t a t i o n ，a n dc o u l d m a k em o b i l er o b o tf i n dt h es u b o p t i m a lp a t h a s a ql e a r n i n ga l g o r i t h mb a s e do nd y n a m i cp r o g r a m m i n gi sp r e s e n t e dt oe n h a n c et h e c o n v e r g e n c er a t eo fs a ql e a r n i n ga n di m p r o v et h ep e r f o r m a n c eo fql e a r n i n gb a s e do n d y n a m i cp r o g r a m m i n g d y n a m i cp r o g r a m m i n gi su s e dt os p e e du pt h ec o n v e r g e n c er a t e ，a n d t h ei m p r o v e m e n to fp e r f o r m a n c ei sa c h i e v e db ys a t h es i m u l a t i o nr e s u l t ss h o wt h a tt h e a l g o r i t h mh a sf a s t e rc o n v e r g e n c er a t e ，h i g h e rp e r f o r m a n c e ，a n dc o u l dm a k em o b i l er o b o tf i n d ac o l l i s i o n - f r e ep a t h f o rg e n e r a l i z a t i o no fc o n t i n u o u ss t a t ea n da c t i o n ，as a ql e a r n i n gb a s e do nf u z z y i n f e r e n c es y s t e m ( f i s ) i sp r o p o s e d f i si su s e dt og e n e r a l i z ec o n t i n u o u ss t a t ea n da c t i o na n d t od e t e r m i n et h eo u t p u to ft h es y s t e ma st h ea c t i o no fm o b i l er o b o t s i m u l a t i o nr e s u l t ss h o w t h a tt h ea l g o r i t h mh a ss t r o n ga b i l i t yo fg e n e r a l i z a t i o n ，a n dh a se f f e c t i v e l ys o l v e dt h em o b i l e r o b o tp a t h p l a n n i n gi nc o m p l e xe n v i r o n m e n t k e yw o r d s ：r o b o t ，p a t hp l a n n i n g ，r e i n f o r c e m e n tl e a r n i n g ，ql e a r n i n g ，s i m u l a t e da n n e a l i n g ， f u z z yi n f e r e n c e i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 硕士论文 基于模拟退火q 学习的移动机器人路径规划技术研究 1 绪论 1 1 研究背景和意义 机器入学是一门集计算机、机械电子、自动控制、信息与传感器、人工智能等多学 科技术于一体的系统的科学。移动机器人是机器人学研究领域的一个重要分支，广泛应 用于工业、农业、军事、医疗、服务等领域。2 0 世纪6 0 年代后期，斯坦福研究院( s r 0 的n i l sn i l s s e n 等人研制了名为s h a k e y 的自主式移动机器人，开启了移动机器人的研究 u j 。7 0 年代后期和8 0 年代中期，移动机器人的研究进入了高潮。9 0 年代以后，以实际 环境中的规划技术作为标志的移动机器人，得到了更高层次的研究【2 3 】。 目前，对移动机器人智能性和自主性的要求越来越高。移动机器人导航技术是实现 其智能性和自主性的关键，而路径规划是导航技术中的最基本问题。路径规划是指在有 障碍物的环境中，移动机器人根据一定的评价标准( 比如路线最短、时间最少、能量最 小等) ，找到一条从起始状态( 包括位置及姿态) 到达目标状态( 包括位置及姿态) 的最优或 次优的无碰撞路径【4 】。已知环境中的移动机器人路径规划已经取得了大量研究成果 5 - 8 1 ， 并且发展的比较完善。而在复杂未知环境下，移动机器人必须具有较强的自学习能力， 才能根据环境的变化实时地规划出最优的或次优的无碰撞路径。对于未知环境下的路径 规划，国内外学者也进行了一些研究，提出了若干方法，如人工势场 9 也】、模糊逻辑 1 1 j 3 】 等方法，但是这些方法远远不能满足移动机器人自主学习的要求。 强化学习作为一种重要的机器学习方法，为移动机器人智能地进行路径规划提供了 有效途径。强化学习自学习及在线学习的特点，使其能够适应变化的环境，在移动机器 人路径规划领域得到了广泛的应用，并取得了较好的效果【1 4 1 。但是强化学习在移动机器 人路径规划的实际应用中还存在着一些问题有待解决和完善，比如连续状态和动作空间 的泛化问题、探索和利用的平衡问题、奖赏函数的设计问题等。 因此，以强化学习为基础的移动机器人路径规划技术具有重要的理论研究意义和实 际应用价值。 1 2 移动机器人路径规划方法 根据移动机器人获取环境信息的多少和体系结构，移动机器人路径规划方法可以概 括为以下三种类型：基于环境模型的全局路径规划方法、基于传感器信息的局部路径规 划方法和基于行为的路径规划方法 5 , 8 , 1 3 】。对于不同的移动机器人在不同环境中，不同的 规划方法有各自的优缺点。因此，在某些情况下将不同方法进行融合可能会取得更好的 效果。 l 绪论 硕士论文 1 2 1 基于环境模型的全局路径规划方法 基于环境模型的全局路径规划方法，是在环境中障碍物的形状、大小完全已知的情 况下进行的规划方法，又称静态或离线路径规划方法。首先根据移动机器人的工作环境 进行环境建模，然后再进行路径搜索。代表性方法主要有：可视图法、栅格法、切线图 法、拓扑法、贪心算法、d i j k s t r a 算法、a j l ：算法等【6 。8 1 。 一般情况，环境已知的全局路径规划规划可以寻找到最优解，目前对其研究已经非 常成熟。通常这些方法可以较准确地进行路径规划，但是计算量非常大，而且实际环境 常常是不确定的，从而移动机器人无法根据变化的环境建立全局的环境模型，这些方法 无法满足移动机器人的智能性要求。考虑本文主要研究未知环境下的移动机器人路径规 划，在此对于已知环境的路径规划不作深入讨论。 1 2 2 基于传感器信息的局部路径规划方法 对于环境信息未知的情况，需要根据传感器获得环境中障碍物、机器人状态等信息 实时地进行路径规划。基于传感器信息的局部路径规划是一种动态规划，又称在线规划， 是当前路径规划中的研究热点，并取得了一定研究成果。常用的路径规划方法主要有： 人工势场法、神经网络算法、模糊逻辑算法、遗传算法、模拟退火算法等。其中人工势 场法属于传统的路径规划算法，其它的算法属于智能路径规划算法。下面对各种算法的 优缺点进行比较和分析。 ( 1 ) 人工势场法 k h a t i b t 9 】于1 9 8 6 年最早提出了人工势场法，并成功应用于机器人的路径规划。它是 一种虚拟力法，把目标和障碍物设想为引力场和斥力场的来源，移动机器人在引力和斥 力的合力作用下运动。该算法计算量小、结构简单、实时性好。但是容易发生死锁现象， 从而可能会使机器人陷入局部最优，而且存在丢弃障碍物分布信息的缺陷。 ( 2 ) 神经网络法 神经网络是一个并行的分布式系统，有助于解决机器人系统实时性较高的问题，并 且在机器人路径规划领域得到了广泛应用。神经网络易于表示路径规划中状态空间到动 作空间的非线性映射关系，然而该方法中的权值较难设定。 ( 3 ) 模糊逻辑法 模糊逻辑法是一种基于传感器信息的在线路径规划方法，它将输入的环境信息进行 模糊化，从规则库中获得经验知识，依据模糊推理进行路径规划。模糊逻辑法的最大优 点是根据模糊的环境信息进行计算，具有经验知识，可以克服局部极值的问题，对于未 知环境的路径规划具有极大的优越性，而且计算量小、实时性比较好。其缺点是：人的 经验知识不定是完备的，同时输入量过多会导致推理规则膨胀。 ( 4 ) 遗传算法 2 硕士论文 基于模拟退火q 学习的移动机器人路径规划技术研究 遗传算法是借鉴生物的自然选择和遗传进化机制而提出来的一种全局优化自适应 概率搜索算法。遗传算法不会陷入局部最优，具有全局收敛性，但是运算速度慢，存储 空间大。 ( 5 ) 模拟退火算法 k i r k p a t r i c k 等人于1 9 8 2 年首先将物理中固体退火思想引入组合优化研究领域，提 出了一种求解大规模组合优化问题的方法，被称为模拟退火算法( s i m u l a t e da n n e a l i n g ， s a ) 【1 5 , 1 6 】。该算法是基于邻域搜索的算法，借鉴退火过程的思想，对每个解进行邻域搜 索，并引入m e t r o p o l i s 准则判断是否接受某个邻域解作为新解。模拟退火算法是一种通 用优化算法，具有广泛的应用性。文献 1 5 将模拟退火算法应用到强化学习路径规划的 动作选择中，在开始阶段，随机地进行动作选择，随着对温度控制参数的退火降温，在 学习后期，当前策略趋于最优，几乎不存在“探索”成分，而是根据当前策略选择最优 的动作，有效解决了强化学习路径规划中探索和利用的平衡问题。 1 2 3 基于行为的路径规划方法 基于行为的路径规划方法是根据b r o o k s 提出的包容式结构建立的一种自底向上的 路径规划方法【1 7 】，它是移动机器人路径规划方法的一种新的发展趋势。它把机器人导航 的问题分解为若干个相互独立的行为单元，比如避碰、导向目标等。这些行为单元采用 的行为互不相同，它们通过相互协作完成机器人导航任务。 通常情况下，基于行为的路径规划方法可以分为以下3 种类型：反射式行为、慎思 式行为、反应式行为【5 1 。反射式行为智能性较差，一般结合其它方法一起使用；慎思式 行为适于复杂的静态环境中的路径规划；对于基于反应式行为的方法，移动机器人根据 传感器信息对每一步的动作进行实时地规划，但是因为缺乏全局的环境知识，所以不适 合复杂环境中的移动机器人路径规划 5 】。 1 3 强化学习的研究现状及其在路径规划中的应用 1 3 1 强化学习的研究现状 2 0 世纪6 0 年代，m i n s k y 首次提出了“强化”与“强化学习”等术语【1 8 】。强化学 - - j 又称作增强学习或激励学习，它的发展历史可以概括为以下两个阶段： 第一阶段2 0 世纪5 0 年代到6 0 年代是强化学习的形成阶段。其研究先后经历了试 错学习、时序差分和最优控制三条主线。 强化思想最早来源于心理学。m i n s k y 于1 9 5 4 年从计算上实现了试错学习，而时序 差分( t e m p o r a ld i f f e r e n c e ) 学 - j 是基于时间序列上对同一个量相继两个估计的差【i 9 1 。 s u t t o n 、b a r t o 及k l o p f 等把试错学习和时序差分结合在一起并且进行了深入研究。最优 控制起源于2 0 世纪5 0 年代，b e l l m a n 提出的动态规；恁l j ( d y n a m i cp r o g r a m m i n g ) 方法，它 3 1 绪论 硕士论文 是求解最优控制问题的一个有效方法，随后他又提出了马尔可夫决策过程( m a r k o v d e c i s i o np r o c e s s ，m d p ) ，1 9 6 0 年h o w a r d 提出了马尔可夫决策过程的策略迭代过程， 这些构成了现代强化学习的理论基础【1 9 , 2 0 】。 第二阶段8 0 年代以后，强化学习进入发展阶段。从6 0 年代后期至7 0 年代，强化 学习的研究进入低谷，直到8 0 年代才出现高潮。s u t t o n 于1 9 8 8 年提出瞬时差分方法， 并且证明了t d 方法的收敛条件【2 1 。1 9 8 9 年w a t k i n s 等人提出了q 学习方法并且证明了 q 学习在一定条件下的收敛性，真正把时序差分和最优控制结合在一起，同时把强化学 习中的三条主线联系在一起【2 2 】。j i n gp e n g 和w i l l i 锄s 等人提出了多步q 学习方法， w a t k i n s 与w e r b o s 等人把强化学习与动态规划和最优控制联系起来进行了理论上的研究 1 9 】 o 目前，强化学习理论的研究及其应用在国际上受到广泛重视。美国、韩国、德国、 澳大利亚等国的学者都在进行强化学习的理论及其应用的研究。在国内，1 9 9 6 年阎平凡 详细介绍了强化学习的原理、主要算法以及强化学习在智能控制中的应用 2 3 1 。近年来， 张汝波教授、郭茂祖教授和高阳教授等学者在提高强化学习的算法速度、探索和利用平 衡的问题、时间信度分配、平均奖励强化学习、强化学习在机器人中的应用等方面做了 突出贡献【1 9 】。 1 3 2 强化学习在路径规划中的应用 近年来，基于强化学习的路径规划日益成为国内外学者研究的热点，优点主要体现 在：无须建立精确的环境模型，简化了智能体的编程；无须构建环境地图，强化学习可 以把避碰、避障、路径规划、协作等问题统一解决。 m a t a r i cm e 2 4 】把强化学习应用到多机器人的协调系统中，将觅食( f o r a g i n g ) 任务的奖 赏函数表示为若干个子任务的奖赏函数的和。颜国正等 2 5 】提出了基于强化学习的协调避 障的路径规划方法，把奖赏函数设计为基于行为分解的非均匀结构，用反映各个基本行 为的奖赏函数的加权和来表示总奖赏函数，这种新的奖赏函数结构提高了学习速度，并 且证明了避碰行为和导向目标行为的相关性。陆军等 2 6 提出了基于c m a c 神经网络的 s a r s a ( 允) 学习算法，并将其应用于移动机器人的局部路径规划，实现了未知复杂环境下 的路径规划。h e e r a kb e o m 2 7 利用模糊逻辑和强化学习相结合的方法实现陆上移动机器 人的导航，完成避碰和到达指定目标点两种行为。卓睿等 2 8 】提出了基于模糊逻辑和强化 学习的移动机器人导航方法，把移动机器人导航分为避碰和寻找目标两个模块，采用模 糊逻辑推理对传感器数据进行模糊化，然后再用强化学习对避碰模块进行训练。 强化学习方法由于其自身固有的特点：适应性、反应性和自学习性，广泛应用于智 能机器人路径规划领域，尤其是未知环境中的移动机器人导航。但也存在很多问题，如 奖赏函数的设计问题、探索和利用的平衡问题、连续状态和动作空间的泛化问题、环境 4 硕士论文 基于模拟退火- q 学习的移动机器人路径规划技术研究 信息获取不完整问题等。 1 3 3 强化学习在路径规划中的关键问题 目前，强化学习在理论研究以及工程应用等各方面都得到了深入的研究，但是强化 学习在应用中还存在着一些问题，有待解决。下面讨论强化学习在移动机器人路径规划 中的几个关键问题。 ( 1 ) 奖赏函数的设计 强化学习的目的就是使累积奖赏最大，奖赏信号能够及时地准确描述强化学习的进 程，但是在实际应用中奖赏函数的设计需要考虑实际环境和具体行为，对于不同环境中 的不同行为，奖赏函数的设计不同，而且没有固定公式。奖赏函数设计得合理与否及其 准确程度，都会影响强化学习的收敛速度。因此，如何设计合适的奖赏函数已成为强化 学习的关键【3 2 。3 4 1 。 ( 2 ) 探索和利用的平衡问题 强化学习的目的是从环境状态到动作的非线性映射中，找到一个最优策略，使得智 能体获得的奖赏和最大，这就涉及到探索( e x p l o r a t i o n ) 和利用( e x p l o i t a t i o n ) 之间的平衡问 题。为了获得大的奖赏值，智能体须要倾向于采用被证明有效且获得正的奖赏的动作， 即利用；而为了发现这种动作，智能体就必须试着采用那些没有被选择的动作，即探索 【3 1 1 。探索是寻找最优策略的有效途径，但是过多地探索会影响算法的性能和收敛速度。 探索与利用平衡的问题一直是强化学习中的一个难点。目前，常用合适的动作选择方法 解决探索与利用之间的矛盾，主要的动作选择方法有占贪婪( s g r e e d y ) 动作选择策略和 软最大化( s o f l m a x ) 动作选择策略。但是这些方法解决探索和利用的平衡问题的效果不是 很明显，因此需要进一步的深入研究。 ( 3 ) 连续状态和动作空间泛化问题 一般情况下，强化学习是基于离散状态和动作空间马尔可夫决策过程的一种机器学 习方法，状态一动作对的值函数采用l o o k u p 表格进行存储和迭代地计算。而在实际环境 中状态和动作通常是连续的，如果用l o o k u p 表格对值函数进行存储，必会造成“维数灾 难”的问题，从而需要对强化学习进行离散化。为了避免“维数灾难”，实现对连续状 态或者动作空间的逼近，要求强化学习具有泛化的能力，也就是利用有限的学习经验和 记忆实现对一个大范围空间有效知识的获取和表示【2 9 1 。强化学习中的连续状态和动作空 间的泛化问题已经成为研究的重点。目前，对强化学习进行离散化的常用方法主要有神 经网络方法、模糊推理方法等。神经网络离散化方法最大的缺点就是不能保证强化学习 收敛；而模糊推理方法是移动机器人应用中较为理想的一种离散化方法 3 0 】。 5 1 绪论硕士论文 1 4 本文主要工作和内容安排 本文以未知环境中静态障碍物下的强化学习移动机器人路径规划为背景，围绕强化 学习中的q 学习算法展开研究。本文主要工作如下： ( 1 ) 为了解决奖赏函数设计和探索与利用平衡的问题，提出了基于行为分解奖赏函 数的s a q 学习移动机器人路径规划算法。 ( 2 ) 为了提高s a q 学习的收敛速度和基于动态规划的q 学习性能，提出了一种基 于动态规划的s a q 学习移动机器人路径规划算法。 ( 3 ) 针对连续状态和动作空间的泛化问题，提出了基于模糊推理的s a q 学习移动 机器人路径规划算法。 全文内容安排如下： 第一章绪论。阐述了本课题的研究背景和意义，论述了移动机器人路径规划常用方 法，详细介绍了强化学习的研究现状及其在路径规划中的应用，并讨论了强化学习路径 规划中的关键问题，最后给出了本文的结构安排； 第二章强化学习理论。首先介绍了强化学习的基本模型；然后给出了强化学习的内 部结构和各个模块的实现方法；接着对强化学习中的几种典型算法进行了分析与评述， 并重点介绍了o 学习； 第三章基于行为分解奖赏函数的s a 。q 学习移动机器人路径规划。针对奖赏函数对 具体环境和路径规划描述不准确而降低学习速度的问题，将移动机器人路径规划总的奖 赏函数表示为避碰行为奖赏函数和导向目标行为奖赏函数的加权和，从而设计了基于行 为分解的非均匀奖赏函数。同时，为了解决探索与利用的平衡问题，本文采用模拟退火 ( s a ) 进行动作选择，提出了基于行为分解奖赏函数的s a q 学习移动机器人路径规划方 法。仿真实验表明了方法的有效性； 第四章基于动态规划的s a q 学习移动机器人路径规划。本章在基于s a q 学习与 基于动态规划的q 学习的基础上，提出了一种基于动态规划的s a q 学习算法，在对当 前状态一动作对的值函数进行更新的同时，借助动态规划思想，对当前状态的前导状态 集合中的前导状态动作对的值函数进行逆序更新。仿真实验结果表明了算法不仅具有 较快的收敛速度，而且可以提高算法的性能； 第五章基于模糊推理的s a q 学习移动机器人路径规划。针对强化学习路径规划中 连续状态和动作空间的泛化问题，提出了基于模糊推理的s a q 学习移动机器人路径规 划方法。仿真实验表明了算法具有较强的泛化能力，可以有效解决移动机器人在复杂环 境中的路径规划问题。 第六章结论与展望。对本文工作进行了总结和研究展望。 6 硕士论文基于模拟退火q 学习的移动机器人路径规划技术研究 2 强化学习理论 强化学习在线学习及自学习的特点，使其成为机器学习研究领域中的重要分支，并 且广泛应用于机器人、智能控制等领域。本章首先介绍强化学习的基本模型，再详细说 明强化学习的内部结构和实现方法，最后分析了强化学习中的几种常用算法。 2 1 强化学习的基本模型 强化学习的思想来源于条件反射理论和动物学习理论，它是受到动物学习过程启发 而得到的一种仿生算法，是一种重要的机器学习方法【3 4 】。强化学习不需要经验知识，而 是通过不断与环境交互以获得策略改进，选择能达到目标的最优动作。当一个动作产生 正确的结果时，这种动作就被加强，反之就被削弱。将具有这种学习能力的机器或者各 类系统称为智能体( a g e n t ) 1 9 】。 强化学习是指智能体从环境状态到动作映射的学习，以使从环境中获得的奖赏值最 大。强化学习的基本模型如图2 1 所示： 动作a 图2 1 强化学习的基本模型 在强化学习中，智能体根据当前状态s 选择一个动作a 作用于环境，执行该动作后， 环境状态发生转移，同时产生一个奖赏值r 反馈给智能体。根据以下原则选择动作：增 大使智能体获得正奖赏值动作的概率，减少使智能体获得负奖赏值动作的概率。 强化学习的具体实现过程： ( 1 ) 设t 时刻智能体位于环境中的状态s ，s ，其中s 为状态集合； ( 2 ) 智能体在状态s 。处，按照某种策略从动作集合彳中选择一个动作a ，并执行； ( 3 ) 在动作a ，的作用下，环境由状态s ，转移到下一个新状态s s ；同时产生一个 奖赏值r ，反馈给智能体。 强化学习把学习过程看作是一个试探评价的过程。虽然智能体不能对行为进行详细 地分析与研究，但是奖赏信号可以对动作执行的好坏进行评价，改善智能体的性能。由 此可以归纳，强化学习具有适应性、反应性和自学习性的特点。 7 2 强化学习理论 硕士论文 2 2 强化学习的结构模型 2 2 1 强化学习的内部结构 由图2 1 所示的强化学习基本模型可知，强化学习由智能体( a g e n t ) 和环境( w o r l d ) 两部分组成。强化学习的内部结构如图2 2 所示 3 6 - 3 8 1 ： a s t + l a g e n t w o r l d 图2 2 强化学习结构框图 图2 2 中字母与变量表示如下： 0 为状态感知模块，把t 时刻环境状态t 映射成a g e n t 内部输入o ； r 为奖赏模块( 又称强化模块) ，根据a g e n t 执行动作的情况，环境反馈给a g e n t 一 个奖赏信号r ； p 为策略模块，根据某种策略选择一个动作a 作用于环境，同时根据奖赏信号，以 及内部感知o ，更新a g e n t 的策略知识。 图2 2 所示的强化学习可以用三元组表示，具体描述形式如式( 2 1 ) ： r s = ( 2 1 ) 其中，s = ( s 。，s ：，) 为环境的状态集合，a = ( q ，以：，) 为a g e n t 的动作集合，r 是 状态转移函数，如式( 2 2 ) ： t ：s x a s ( 2 。2 ) 同时，a g e n t n - t 用四元组描述，如式( 2 3 ) a = ( 2 3 1 其中，为a g e n t 所有内部感知的输入集合，0 是状态感知函数，把环境状态映射成a g e n t 内部输入，如式( 2 4 ) ： o ：s 专x ( 2 4 ) 奖赏函数只是一种映射关系，将状态，动作对映射为一个实数吼，如式( 2 5 ) ： r ：s aj 贸 ( 2 5 ) 策略函数p 把输入状态s ，以及奖赏信号厂映射为动作输出，这种映射关系可以表示 为： 硕士论文 基于模拟退火一q 学习的移动机器人路径规划技术研究 p ：x 吼专4 ( 2 6 ) 2 2 2 强化学习模块介绍 2 2 2 1 状态感知模块 状态感知模块的状态感知函数d 把环境状态映射为智能体的内部感知输入。对于式 ( 2 4 ) ，一般情况下，0 是恒等函数，即s = x ，此时状态是完全可观的；当s x 时， 即d 不是恒等函数时，称状态是部分可观的。连续状态空间通常是部分可观的，需要对 其进行离散化，降低输入空间的复杂度。后面将详细介绍离散化方法。 2 2 2 2 奖赏模块 奖赏模块中的奖赏信号又称强化信号，奖赏信号对产生的动作的好坏作评价，通常 是标量，例如用一个正数表示奖赏，而用负数表示惩罚。一般来说正数越大表示奖赏的 越多，负数绝对值越大表示惩罚的越多。强化学习的目的就是寻找一个最优策略，使智 能体获得的奖赏和最大。根据智能体获取最优性能的不同，奖赏函数主要有以下三种形 式【3 6 】： ( 1 ) 智能体的每个动作使将来奖赏函数值的总和最大； ( 2 ) 智能体的每个动作使将来奖赏函数值的折扣总和最大； ( 3 ) 智能体的每个动作使整个学习周期的平均奖赏函数值最大。 上述奖赏函数通常用值函数来表示，值函数的具体表示形式如式( 2 7 ) 、式( 2 8 ) 、式 ( 2 。9 ) 所示。 2 2 2 3策略模块 策略模块是强化学习的核心，强化学习的目的就是学习一个从状态集合s 到动作集 合么的最优策略，使强化学习系统获得的长期奖赏和最大。但是强化学习没有直接去搜 索这种策略，而是通过目标函数来获得最优策略。通常情况下，目标函数用状态的值函 数或者状态一动作对的值函数表示，值函数有如下三种形式【3 8 】： v 疗( 0 ) = ( 2 7 ) y 万( _ ) = 7 i + f ，0 厂l( 2 8 ) i = 0 矿庀( t ) = 1 h i - - m + o o 仁h t = 0 t t 1 ) ( 2 9 ) 其中，式( 2 7 ) 为有限非折扣累积模型；式( 2 8 ) 为无限折扣累积模型，常量是折扣因子， 它确定了将来奖赏与立即奖赏的相对比例，当7 = 0 时只考虑立即奖赏；当7 被设置为1 或接近1 的值时，未来的奖赏比立即奖赏具有更大的重要性。式( 2 9 ) 为平均奖赏模型。 是智能体从环境状态s ，到s 转移后所接受的奖赏值。如果目标函数已知，则可以根据 式( 2 1 0 ) 确定最优行为策略： 2 强化学习理论 硕士论文 万= a r g m a xv 万( s ) ，v s s( 2 1 0 ) 对于具备终结状态或者循环等问题，强化学习往往采用折扣累积奖赏值作为目标函 数。通过适当地变换，强化学习很容易应用到寻找最短路径等问题中；然而对于其它情 况，强化学习中的目标函数用平均奖赏和表示。本论文主要关注无限折扣累积奖赏值。 2 2 3 强化学习模块的实现方法 2 2 3 1 状态感知模块的实现方法 有限状态和动作空间的马尔可夫决策过程是强化学习的理论基础，而智能体的工作 状态与动作通常是连续的，需要将连续状态映射为智能体内部的状态。这涉及到连续状 态和动作空间的离散化问题，这是强化学习的一个难点。常用的离散化方法有b o x 法、 神经网络法以及模糊推理法等，下面对其进行重点介绍。 ( 1 ) b o x 法 b o x 法是由m i c h i e 提出的，其基本思想是【3 6 , 3 9 , 4 0 ：它将状态空间划分为确定数量的 非重叠区域，每个区域称为一个b o x ，每一个b o x 有一个局部精灵( 1 0 c a ld e m o n ) ，当输 入状态落入某个b o x 时，相应b o x 中的局部精灵就会被激活，该状态被置为1 ，否则为 0 。在每个时刻，最多只能有一个b o x 状态为1 。 b o x 方法没有泛化能力，如何划分状态空间也需要很多经验知识。如果划分的过细， b o x 数目太多，不利于决策；而划分的过粗时，不能准确描述环境的状态。 ( 2 ) 神经网络法 可以采用自组织神经网络来解决输入空间区域划分的问题。使用这种机制去量化输 入空间要比b o x 方法先进，但是输入样本不容易确定，同时也不能保证学习收敛。 ( 3 ) 模糊推理法 模糊推理方法是应用较广的离散化方法。它将传感器感知的环境信息通过模糊化的 方法进行离散化，用模糊语言表示实际输入，通过强化学习来调整模糊输入输出的映射 关系即模糊控制规则。例如l i o n e lj o u f f e 3 1 】采用q 学习方法学习模糊规则，并将其成功 应用于经典问题m o n t a i nc a r 中，验证了算法极强的泛化能力。 2 2 3 2 奖赏模块的实现方法 强化学习的目的就是使智能体获得的奖赏和最大。奖赏函数往往是确定的、客观的， 为策略的选择提供依据，即告诉智能体选择什么动作是好的，什么是坏的。为了提高学 习收敛速度，要求奖赏函数能够及时并且准确地对系统的学习进程进行描述。因此，如 何设计合适的奖赏函数已成为强化学习的关键 3 2 , 3 4 , 4 1 。 根据奖赏值在状态奖赏空间中的分布情况，把奖赏函数分为以下两种形式：密集 奖赏函数和稀疏奖赏函数 3 2 1 。 密集奖赏函数尺形式如式( 2 1 1 ) 所示： 1 0 硕士论文 基于模拟退火q 学习的移动机器人路径规划技术研究 r = ( t ，) ，v s ，i ( 2 1 1 ) 其中，s ，、分别为t 时刻学习系统的外界环境状态和内在感知状态。 一般情况下，稀疏奖赏函数采用式( 2 1 2 ) 的形式： f1在好状态 足= 一1在坏状态( 2 1 2 ) 10其它情况 在设计密集奖赏函数时，需要知道状态和动作空间的所有情况，所以密集奖赏函数 的设计较困难。而稀疏奖赏函数将状态动作对按完成任务的效果进行分类评价，相比 之下，稀疏函数的设计较简单，应用更广泛。 2 2 3 3 策略模块的实现方法 探索与利用的平衡问题一直是强化学习中的难点，一般通过合适的动作选择方式来 解决。常用的三种动作选择方式为：贪婪( g r e e d y ) 动作选择策略、占一贪婪( s g r e e d y ) 动 作选择策略和软最大化( s o f t r n a x ) 动作选择策略。 ( 1 ) g r e e d y 策略总是选择最优动作。g r e e d y 策略由于总是选择具有最高值函数的最 优动作，不能尽可能地探索其它动作，很有可能使学习系统陷入局部最优。 ( 2 )s g r e e d y 策略，以1 一s 概率选择最优动作，而以概率s 随机选择动作。s g r e e d y 增加了随机动作选择的概率，有利于探索新知识，但是采用固定值的占，在学习后期， 当前策略已经接近最优策略，如果依旧进行大量探索，不仅是多余的，而且会影响系统 性能。 ( 3 ) s o l 凸m a a x 策略用随机分布函数来确定各动作选择的概率，其原则是学习开始时， 随机选择动作的几率较大，随着学习次数的增多，评价值最大的动作被选中的概率也随 之增大【4 】。其中最常见的实现方法是b o l t z m a n n 分布，其表达式如下： 巧，r p ( qs ) = 而 ( 2 1 3 ) 厶k 口e 其中，k 表示状态s 或状态动作对( s ，a ，) 的值函数，p o ，is ) 表示状态s 下动作a i 被选中 的概率。z 为温度控制参数：当温度高时，所有动作概率接近相等；而当温度低时，动 作选择概率由于估计值的不同而存在很大不同；当温度趋近于0 时，s o f t m a x 动作选择 变为贪婪动作选择。s o f t m a x 动作选择策略最大的缺点就是选择最优动作的同时可能背 离最优动作。此外还有一些改进其它方法，比如郭茂祖【1 5 】等人提出的模拟退火动作选择 方法，可以随着学习进程的推移降低丁值，使得学习开始阶段侧重于“探索”，学习的 后期则侧重于“利用”策略，有效地解决了探索和利用之间的平衡问题。所以，本文采 用模拟退火动作选择方法，后续章节将重点介绍。 2 强化学习理论硕士论文 2 3 强化学习的典型算法 2 3 1 马尔可夫决策过程 在强化学习过程中，智能体通过与环境的交互来改善自己的行为。强化学习问题可 以描述为：在离散时间、有限状态和有限动作集合的环境下，使智能体获得的折扣累积 奖赏和最大，在此情况下，强化学习问题可用马尔可夫决策过程( m a r k o vd e c i s i o n p r o c e s s ，m d p ) 建模。 马尔可夫决策过程由四元组 定义【3 l 】，包含有限离散状态集合s r 、有限 离散动作集合么、奖赏函数r ：s a 一双和状态转移概率函数p ：s xa xs - 9 【0 ，1 。记 r ( 墨，a ，_ + 。) 为系统在状态j ，时执行动作a 使环境状态转移至s 州获得的立即奖赏值( 又称 瞬时奖赏值) ；记p ( 疋，a ，s t + ，) 为系统在状态s 。时执行动作a 使环境状态转移至j 州的概率。 以下分别简记为r 。，。和p 。 如果智能体在学习过程中状态转移概率尸和奖赏函数r 是已知的，无须学习模型知 识，而是直接学习最优策略，称这类方法为模型无关的方法，代表性方法有动态规划 ( d y n a m i cp r o g r a m m i n g ，d p ) 方法、s a r s a 算法等。而在实际系统中，p 和r 多数是未知 的，需要