基于强化学习的路径规划问题研究

哈尔滨工业大学工学硕士学位论文摘要不确定条件下的人机共生研究领域关注以机器学习为核心的环境和态势感知、动作或路径规划与决策，以及对决策结果的评价。它即包含科学理论问题，也有许多工程技术问题。研究这些科学问题和工程技术问题有明显的理论意义和实用价值。本课题主要研究未知环境下智能体路径规划的强化学习解决方案。机器人或智能体在特定环境下的路径规划是指从指定起点找到一条到达终点的路径，该路径不与障碍物发生碰撞。路径规划问题的研究由来已久，也产生了许多成熟的算法，但是这些算法多数基于已知环境模型，并结合搜索的方法。然而在很多情况下，环境的模型难以获取；另一方面，机器人执行动作时由于控制误差或环境因素导致发出的指令和执行结果产生偏差，无法按照规划好的路径去行走，甚至无法到达终点；第三，规划出的路径可能十分曲折，充满拐点，不利于机器人的实际行走。针对以上几个问题，本文利用强化学习中时间差分法来解决路径规划问题，并且针对强化学习中存在的探索利用平衡问题提出了优化的解决方法。论文主要内容如下：（1）使用强化学习中的时间差分法解决路径规划问题。相比于其他算法，优势在于不需要对环境进行建模，而且具有一定的自适应性和自学习能力，能够应对智能体运动存在不确定性的情况。利用仿真实验对算法进行了验证，结果表明时间差分法能够较快收敛，并且可以在任意位置找到到达目标的路径。（2）改进强化学习在实际应用中存在的探索与利用平衡问题。在强化学习中，探索环境与利用环境是一直存在的两个过程，过多的探索会使训练时间变长，过多的利用会使智能体收敛到不正确的解上，如何平衡探索和利用便成了一个重要的研究方向。传统方法通常随着训练时间的增加而减少探索，没有考虑环境和问题本身的复杂程度。本文基于路径规划问题，以智能体到达目标成功率为指标来衡量智能体对环境的掌握程度，从而动态调整探索因子，使智能体在对环境掌握程度较低时更多地对环境进行探索，在对环境掌握程度变大时逐渐减少探索，更多地利用环境。利用仿真实验进行了验证，结果表明改进后的探索方法能够更好地平衡探索与利用，使智能体更快到达目标点。关键词：未知环境；强化学习；路径规划；探索利用I

哈尔滨工业大学工学硕士学位论文AbstractThefieldofman-machinesymbiosisunderuncertaintyfocusesonstateawarenesswiththecoreofmachinelearning,pathplanninganddecisionmaking,ainsscientifictheoreticalissuesandengineeringortechnicalproblems,picmainlystudiesthereinfanningofrobotsoragentsinaparticularenvironmentmeansfindingacollision-freetrajectory,followingthattrajectoryandranninghasalonghistoryofresearch,alsoproducedalotofmaturealgorithms,howevermostofthesealgorithmsarebasedontheenvironmentmodel,y,inmanycasestheenvironmentmodelisverydifficulttoobtain;Secondly,duetothecontrolerrorsortheenvironmentalfactors,therobotcannotfollowtheplannedpath,resultingadeviationtotheend;third,thepathmaybeverytortuous,fullofinflectionpoint,it’oftheaboveproblems,thispaperpresentsanewsolution,thatthedilemmaofexplorationandexploitationprobleminreinforcementlearning,ncontentsofthispaperareasfollows:(1)edwithotheralgorithms,theadvantageisthatwedonotneedtomodeltheenvironment,andthemethodisadaptabilityandhastheultsshowthatthetemporaldifferencemethodcanconvergequickly,andthepathtothetargetcanbefoundatanyposition.(2)forcementlearning,therearetwoprocessesthatalwaysexist,hexplorationwillmakethetrainingtimelonger,talancetheionalmethodsusuallyreduceexplorationwiththeincreaseintrainingtime,witssertationusesthesuccessrateoftheagentreachtothetargetasastandard,andadjustexploratoryfactordynamicallybasedonthepathplanningproblem,sothatwhentheagentisnotII

哈尔滨工业大学工学硕士学位论文muchfamiliarwiththeenvironment,therhand,ultsshowthattheimprovedmethodcanexploreandexploitbetter,ds:Unknownenvironment,Reinforcementlearning,Pathplanning,

哈尔滨工业大学工学硕士学位论文目录摘要...............................................................................................................................II第1章绪论....................................................................................................................11.1课题背景及研究的目的和意义......................................................................11.2课题相关领域研究现状..................................................................................21.2.1路径规划方法研究现状.......................................................................21.2.2探索利用平衡问题研究现状..............................................................41.2.3路径规划问题的难点...........................................................................51.3论文内容及组织结构......................................................................................6第2章路径规划方法及强化学习算法.......................................................................72.1引言....................................................................................................................72.2传统路径规划算法...........................................................................................72.2.1组合式规划............................................................................................72.2.2采样式规划..........................................................................................102.3强化学习算法..................................................................................................122.3.1强化学习基本框架.............................................................................122.3.2强化学习典型方法.............................................................................142.4本章小结.........................................................................................................22第3章基于时间差分方法的路径规划.....................................................................233.1引言..................................................................................................................233.2基于时间差分的路径规划............................................................................243.2.1时间差分法基本思想.........................................................................243.2.2SARSA和273.3基于成功率的探索方法................................................................................303.3.1探索与利用平衡问题.........................................................................313.3.2动态调整探索因子.............................................................................323.4基于成功率的探索方法与时间差分法的结合...........................................333.5本章小结.........................................................................................................35第4章仿真实验及结果分析.....................................................................................36IV

哈尔滨工业大学工学硕士学位论文4.1引言.................................................................................................................364.2仿真实验说明.................................................................................................364.3实验结果及分析............................................................................................384.3.1无模型方法在路径规划中的实验....................................................384.3.2基于成功率的探索方法的Q（）-444.4本章小结.........................................................................................................50结论.............................................................................................................................51参考文献........................................................................................................................52哈尔滨工业大学学位论文原创性声明和使用权限..................................................56致谢.............................................................................................................................57V

哈尔滨工业大学工学硕士学位论文第1章绪论1.1课题背景及研究的目的和意义在我们很多人的印象里，机器人只是外表坚硬，行动笨拙的庞然大物，或者是工厂车间的机械手，代替人类做一些机械的重复性的组装工作，应用十分有限。但是近年来随着计算机技术的发展，尤其是人工智能领域的一些关键突破，使得创造出具有智慧的机器人变得可能。比如最近谷歌开发的AlphaGo[1]人工智能，已经可以在围棋上打败人类；还有在2013年的时候，谷歌大脑利用深度增强学习技术让计算机学会玩Atari游戏[2]，同样也可以在很多游戏上打败人类玩家。这些令人兴奋的成果让我们不由得想象，如果我们可以将人工智能技术应用到机器人中，是否有一天机器人可以具有人的智慧，可以像人一样思考，真正地为人类服务。这也是我们追求的一个终极目标。但是将机器人应用到现实生活中，摆在我们面前的一个重要问题就是如何能让机器人在未知环境下进行路径规划，即在最短的时间内规划出一条到达目标点无碰撞的路径[3]。这是机器人代替我们工作，为我们服务的一个重要前提，试想如果机器人无法进行路径规划，也就意味着机器人在未知环境中无法自由活动，这时要求机器人完成任务就是不可能的事情。反之，如果我们能解决机器人在未知环境下的导航问题，也将大大加快机器人应用到实际生活中的速度，将机器人用到更广阔的领域中去，比如深空探测，深海资源勘探等危险环境。综上所述，研究未知环境下的路径规划问题具有重要的研究价值与意义，本论文以黑龙江省自然科学基金项目（批准号F201012）“基于家庭机器人环境认知机理的计算模型及应用技术研究”为基础。分析了现有路径规划算法的原理和在实际应用中的问题，提出了基于强化学习的路径规划方法，将强化学习中的核心方法-时间差分法应用到路径规划中去，这种方法不需要环境模型，智能体仅仅通过不断地作出动作去试探，然后根据环境的反馈调整自己的行为，得到最优的路径，使得智能体具有良好的适应环境的能力，从而实现在未知环境中的路径规划。并且提出了改进的探索策略，更好地解决了探索利用平衡问题，帮助智能体更快找到目标点。1

哈尔滨工业大学工学硕士学位论文1.2课题相关领域研究现状1991年，e在他的著作RobotMotionPlanning中提出，机器人是通过在现实世界中自由行动来完成给定的任务[4]。这充分说明了路径规划的重要性。路径规划的目标就是从起始点找出无障碍碰撞的路径，尽快到达目标点。可以把这个问题看作是一个有限制的优化问题，优化的指标根据不同的需求会有差异，有些问题需要机器人有较强的实时性，我们需要优化算法，减少计算时间；有些问题需要机器人有较高的准确性，这时算法的精确程度成为我们优化的主要目标；有些问题机器人的能源有限，那么我们的算法就要优化出距离最短，转向次数最少的路线，这些都是不同的优化目标与评价指标。国内外的研究人员在路径规划上做了很多研究，许多成熟的算法也被应用到移动机器人上。1.2.1路径规划方法研究现状早在1959年，由荷兰计算机科学家狄克斯特拉提出的Dijkstra算法[5]，是计算单源最短路径的经典算法，也是很有代表性的算法，它应用了贪心的思想，主要思想是每次迭代选择的下一个顶点是当前标记点之外距离源点最近的点，在已知地图的情况下，这种算法仍然十分高效；1968年，A*算法被提出[6]，这种方法在Dijkstra算法的基础上，加入了启发式函数，也就是一种评估当前点到达目标的度量，用来决定下一步应该优先扩展哪个节点，这种算法在多维度规划问题上，或者是在较大规模的地图上，算法复杂度很大，因此，很多学者提出了A*算法的很多变种版本，比如1985年的IDA*算法[7]，2001年的LPA*算法[8]，2008年的BidirectionalA*算法[9]；1986年，Khatib提出了势场法[10]，这种方法的思想很简单，将规划空间看作物理学中“场”的概念，将智能体看作一个粒子，障碍物会对这个粒子产生斥力，目标会对这个粒子产生引力，两者的合力即为最后智能体运动的方向，主要的困难在与如何设计引力和斥力函数。这种方法实时性较好，同时产生的路径通常十分平滑，适合于机械臂一类的应用，缺点是在合力为0的位置智能体容易陷入局部最优解。1994年，卡内基梅隆机器人中心的Stentz提出了D*算法[11]，也称为DynamicA*算法，顾名思义，这种算法解决了A*算法无法在动态环境中进行路径规划的问题，主要思想是首先利用Dijkstra算法计算出最短路径，然后按照这个路径进行移动，一旦发现下一节点的状态发生改变，比如被障碍物堵塞，或者发2

哈尔滨工业大学工学硕士学位论文生移动，则利用启发函数调整当前位置的权值。这种算法主要用于机器人探路，是火星探测器采用的寻路算法，由此可见其重要性，后来也有很多学者对D*算法进行改进，比如1995年提出的FocusedD*[12]；2005年提出的D*Lite[13]；2006年提出的FieldD*等，这些改进后的算法都大大提升了D*算法的效率和应用范围。1996年和1998年，概率图法[15]和快速搜索树方法[16]被提出，以往的方法都是基于环境模型进行图搜索，这两种方法则是基于采样的规划方法，通过在规划空间中随机采样的方式，避免对整个环境进行建模，然后不断地探索，直到找到目标点为止，为路径规划提供了一种新的解决思路。近年来，由于人工智能的兴起，很多基于人工智能的路径规划方法[44]被提出，其中比较典型的方法有遗传算法[17]，神经网络法[18]，模糊逻辑法[19]等，这些方法具有一定智能性，在面对不同的场景，无论是动态的还是静态的都有不错的表现，而且具有一定泛化能力。毕盛等人[20]提出了一种基于模糊逻辑的移动机器人路径规划算法，将状态空间与动作空间关联起来，形成映射关系，解决了人工势场法中容易陷入局部极小的问题；刘传颂[21]在其博士论文中详细介绍了遗传算法在路径规划中的研究，并提出了一种基于改进染色体编码的自适应遗传算法，使得算法能够避免过早收敛的问题；[22]中提出了利用双向神经网络来解决在未知环境中进行路径规划的方法。强化学习算法是机器学习中的重要分支，起源于心理学和神经科学。人类是通过不断与环境互动，作出行为来适应环境，强化学习借鉴了这种思想，利用智能体不断尝试获取环境信息，同时设置奖励值作为反馈信号，用来引导智能体朝着累积奖励最大的方向去行动，找到最优策略。在利用强化学习解决路径规划问题方面，[46]提出利用偏好评估的强化学习技术，结合降维的方法，实现了智能体在存在移动障碍物的环境中的路径规划；[47]将深度强化学习技术与策略梯度法结合起来，解决自动驾驶中的路径规划问题，提升了路径规划问题的效率；在[48]中，作者将监督学习与强化学习相结合，为智能体提供规划好的路径，接下来智能体利用强化学习中函数近似的方法来进行泛化，实现在其它环境中的路径规划，具有较强的泛化能力。乔俊飞等人把基于BP神经网络的Q-learning应用到移动机器人，完成未知环境下的自主避障[25]；赫东锋等人提出Q-learning和模糊逻辑技术相结合的方法，用于完成移动机器人的自学习和不确定环境下的路径规划[26]；Shoichiro3

哈尔滨工业大学工学硕士学位论文Fujisawa等人利用CMACs改进的Q-learning算法，实现移动机器人的路径规划[27]。1.2.2探索利用平衡问题研究现状探索利用平衡问题本质上是关于智能体每次做决策时如何选择动作的问题，也是强化学习中固有的问题，由于在强化学习问题中，环境对于智能体是未知的，因此在一开始需要智能体随机地做出动作，探索环境，随着智能体对环境的掌握程度不断增加，智能体开始挑选那些会带来最大回报的动作去执行，也就是利用环境。过多的探索会使智能体训练时间变长，过多的利用会使智能体错过能够带来更大回报的动作，收敛到不正确的解，因此如何平衡探索和利用是强化学习中一个重要的研究课题。在强化学习中，值函数是智能体选择动作需要考虑的一个重要标准，值函数的含义简单来说即为执行此动作能给我们带来的期望回报，一个朴素的想法就是每次在智能体执行动作时都选择值函数最大的动作执行，但是由于强化学习是在线的，往往在训练的过程中，对值函数的估计是不准的，此时若盲目选择值函数大的动作往往会错过一些更好的动作，因此我们需要在利用环境的同时也保持对环境的探索，达到最好的效果。-贪心策略[42]是解决这个问题最简单的办法，即每次智能体执行动作时会有的几率随机选取一个动作执行，会有1-的几率选择带来回报最大的动作执行，但是这个方法的不足之处在于值不好设定，而且随机选择一个动作在某些情况下不是十分合理，因为有些动作要优于其他动作，但是智能体却等概率地选择它们；-贪心策略有很多改进的方法，包括-first方法[51]，基本思想是将值首先设置为1，也就是智能体一直在探索环境，经过一段训练时间之后，值设置为0，进入利用环境阶段；-decreasing是另外一种改进方法[51]，基本思想是首先将设置的很大，然后随着训练时间的增加逐渐减小值。[41]中提出了梯度算法，智能体执行某个动作的概率和其动作值函数成正比，即动作带来的期望回报越大，执行这个动作的概率越大，这种方法较-贪心策略更加合理，但是对于奖励函数的设计十分敏感；[48]利用分层强化学习方法实现了智能体内部驱动的探索方法，能够解决复杂环境下的探索问题，适合解决整体目标能够被分解成小目标的问题。[49]中提出了利用上置信空间来选择动作的方法来解决多摇臂赌博机问题，这个方法简称为UCB方法，主要思想是同时考虑了动作的值函数和对值估计的不确定性，选择动作的公式如下：4

哈尔滨工业大学工学硕士学位论文Aargmax[Q(a)calogt]N(a)(1-1)算法记录了某个动作执行的次数Nt(a)，根号项代表对值函数估计的不确定性，若次数越多，则根号项越小，不确定性越小，c代表置信区间，t代表训练循环次数。利用这个思想去在不同的动作中选择，在实际应用中取得了不错的效果；[50]中提出了ValueDifferencebasedExploration（VDBE）的方法，利用时间差分法中每次值函数更新产生的误差，作为衡量值函数估计准确性的标准，误差越大，则越不准确，利用多摇臂赌博机进行了验证。1.2.3路径规划问题的难点虽然解决路径规划问题的算法有很多，但是应用到现实生活中存在着很多问题：（1）未知环境下的路径规划。有很多算法是在建立环境模型的基础上再进行路径搜索的，但是很多时候我们无法得到环境的模型，或者需要费很大的力气才能得到环境的模型，这就使得一些基于模型的算法无法正常工作[23]。（2）在不确定环境下进行路径规划。路径规划的算法一般输出都是一条路径，也就是指令的序列。机器人在执行某条指令时由于存在着一些控制误差或者地面湿滑等环境因素，相同的执行指令可能会得到不同的执行结果，这时机器人往往会偏离设计好的路线，轻则无法到达目的地，重则与障碍物发生碰撞，造成损坏。（3）规划出平滑的路径。某些路径规划算法输出的路径可能是最优的，但是可能带有十分多的拐点，或者直观上来看存在着许多转弯处，机器人按照这种路线行进十分困难，也是十分消耗能源的。本文将着重讨论基于强化学习的路径规划方法，主要是将强化学习中的核心算法-时间差分法应用到路径规划问题的解决上去。强化学习非常有吸引力，首先，如果我们想让机器人去执行某一个任务，我们只需要设计出奖励函数，接下来让机器人自己不断尝试，而不需要具体的编程实现，这样就可以在未知环境下工作。其次，强化学习的智能体是具有自适应能力的（adaptive），可以根据从环境中得到的反馈来调整自己的行为，无需环境模型；同时还是反应的（reactive），以路径规划为例，多数方法通常会直接输出一条路径，强化学习会输出状态-动作的映射关系，这样智能体无论处于任何状态都能够作出正确的决策，这样就解决了由于控制误差或者其他因素造成机器人偏离规划路径的问5

哈尔滨工业大学工学硕士学位论文题。第三，强化学习是一个“试错”的过程，通过不断尝试来找到最优策略，这样输出的策略对于智能体来说一定是可以完成的，不会因为路径过于复杂而无法执行[24]。1.3论文内容及组织结构本文将路径规划方法分成了传统路径规划算法和智能路径规划算法，针对传统路径规划算法，本文主要介绍了组合式规划和采样式规划两大类方法，并对其中具体方法进行了介绍，包括算法流程，算法优缺点，算法适用环境等。对于智能路径规划方法主要介绍了基于强化学习的路径规划算法。本文介绍了如何将强化学习中的核心算法-时间差分法，应用到路径规划中，并取得了不错的效果。针对强化学习中探索利用平衡问题，提出了改进后的探索策略，并与传统探索策略进行对比。论文主要组织结构如下：第1章：首先介绍机器人在当今生活中各个领域的广泛应用，然后指出成功应用的前提即为机器人能在环境中进行路径规划，由此提出了路径规划问题的研究意义所在，也是本文的研究目的。接下来介绍国内外关于路径规划问题的研究现状以及路径规划问题的难点，最后介绍了本文要研究的内容。第2章：介绍了传统路径规划算法，包括组合式规划和采样式规划两大类算法，接下来介绍了几种这两类算法中的具体算法。然后介绍了强化学习算法，包括基本理论和基本组成部分，还有一些典型算法，包括动态规划方法，蒙特卡洛方法等。第3章：提出了基于成功率的探索方法，并与时间差分法相结合。首先介绍了时间差分强化学习的基本思想和典型算法，描述了用找到目标成功率来决定探索的一种标准，利用该标准动态改变探索因子，解决了强化学习中探索与利用的平衡问题，提高了智能体找到最优路径的概率。使得智能体能够更快地找到目标点。第4章：仿真实验与结果分析，利用具体的路径规划环境去验证强化学习算法，构造了格子世界作为实验环境，验证了强化学习中时间差分法这类方法在路径规划中的应用，并分析了它们收敛得到的策略和收敛速度。最后比较了基于成功率的探索方法和其它三种探索方法并列出数据，说明其优越性。6

哈尔滨工业大学工学硕士学位论文第2章路径规划方法及强化学习算法2.1引言路径规划是机器人完成各种任务的前提条件，也是机器人应用到现实生活中最重要的一环。路径规划指的是，机器人在一定范围内，从起始点找到一条到达目标点的无碰撞路径，同时尽可能最优[4]。针对路径规划问题，存在着两大类解决方法，第一类是传统路径规划算法，这类算法有两种解决思路，其一是先对地图进行建模，把环境抽象成图或者栅格，然后利用一些已有的搜索方法进行路径规划，这类解法时间复杂度高，在面临着复杂环境或者规模较大的地图时，往往会浪费很多时间建模，而且在很多情况下建立环境模型是不可能的，或者十分费时的，这就大大限制了这类方法的应用范围；第二种思路是利用随机采样的方式进行路径规划，这种方法的复杂度虽然和问题的维度，地图规模等没有关系，但是有些时候这类算法并不一定能够保证收敛，而且生成的路径十分曲折，不适合机器人实际行走，这时往往还需要对路线进行平滑操作，也很麻烦费时。传统路径规划算法研究时间较长，也有一些成功的应用，为后来的算法提供了思路。第二类是智能路径规划算法，本节着重介绍基于强化学习的路径规划算法，这类算法对先验知识有很少的依赖，只需要提供智能体一个奖励函数，智能体就会通过与环境的不断交互来改善自己的行为，实现路径规划。接下来本节将着重介绍这两大类算法。2.2传统路径规划算法虽然路径规划是在现实世界中完成，但是设计具体算法的时候，总把现实环境抽象成配置空间（configurationspace），也叫作规划空间，将环境中的障碍，机器人本身等抽象成配置空间内的元素。根据是否对环境进行建模，通常分为两大类方法，一种是组合式规划（combinatorialplanning），另外一种是采样式规划（sampling-basedplanning）。2.2.1组合式规划组合式规划方法适用于机器人对环境信息完全已知的情况，在这种情况下，机器人可以将环境中的元素都抽象出来，根据元素间的关联性，把这些元素连接起来构成一个图。然后使用搜索的方法去找到最优的路径。以下是几种7

哈尔滨工业大学工学硕士学位论文常见的组合式规划方法：（1）可视图法最古老的一种路径规划方法，基本思想就是首先把障碍物抽象成多边形，然后用线将这些多边形的顶点和起点终点连接起来，这样路径规划问题便抽象成了点到点之间最短距离的搜索问题。由于在连接点的时候需要保证两点间的连线是不经过任何障碍物的，这时把这两点称为“可视”的，该图任意两点都是“可视”的，因此得到的这个图称为可视图。得到可视图后，采用某种搜索方法比如A*算法，Dijkstra算法等，从起点找到到达终点的最短路径即可。算法整体思想如图1-1所示。但是这种方法存在很大的缺点，当环境变得复杂，构造图的复杂度会剧烈提高，或者某个障碍物有一些变换，就需要重构整个图，十分费时。图2-1可视图法基本思想（2）泰森多边形法基本思想和可视图法类似，首先把障碍物，起始点，目标点投影到一个平面中，构成一个由多边形和点组成的二维空间。然后找出一个点的集合，这个集合中的每个点距离障碍物和边界的距离相等，之所以这样可以保证机器人在按照这条线路移动时不会因为一些误差导致碰撞。这个点的集合构成一些相连的线段和抛物线，这些就构成了最后的路径。基本思想如图1-2所示。这个方法在封闭空间，低维空间中效率很高，但是对于开放的空间有时候会得到次优解。8

哈尔滨工业大学工学硕士学位论文图2-2泰森多边形法基本思想（3）精确栅格分解法基本思想首先先把障碍物等投影到一个平面当中，然后将整个平面分割成不重叠的栅格，然后开始搜索。分割时的过程是经过每一个多边形和边界的顶点，利用垂直的线段把空间分解成梯形或者其他形状，第二步再将每一个梯形内部的中心点标记出来，然后在每一个垂线放置一个标记点，将起始点和终点和这些点相连接，便构成了最后的路径，最后利用搜索算法去找到最优的那条。算法过程如图1-3所示。此方法简单易实现，但是在环境复杂时需要存储大量的信息，计算量也会大大增加，而且在障碍物或者边界是不规则图形时，无法利用顶点去分割，限制了该方法的应用范围。图2-3精确栅格分解法过程9

哈尔滨工业大学工学硕士学位论文（4）近似栅格分解法在复杂环境中，精确栅格分解法十分低效，费时，为了改善这一问题，有些学者提出了近似栅格分解法，基本思想是使用一些简单的预定义的形状去分割规划空间，这样计算的时候就可以使用相同的计算方法去迭代，降低算法运行复杂度。组合式规划方法总体上比较简单而且易于实现，首先将环境中的元素抽象成一个图，然后在图中搜索最优路线。算法具有完备性，即假如存在最优解的话，就会找到。但是当规划空间的维度提高的时候，算法将不再适用，为了解决这一问题，学者们提出了采样式规划方法。2.2.2采样式规划使用采样式规划方法时机器人不需要知道环境模型，而是去利用障碍检测算法去不断的探索环境，增量式地在规划空间中搜索最优路线，相当于在黑暗中一点一点地摸索前进。在这里我们主要讨论概率路线图方法（Probabilisticroadmaps），也叫PRM法，还有快速扫描随机树方法（Rapidlyexploringrandomtrees），也叫RRT法。（1）概率路线图方法这个算法整体分为两个阶段，第一个阶段是构造路线图，基本思想是在整个规划空间中随机采样几个点，如果这些点不在障碍物中，就标记为顶点，然后将一定范围内的顶点两两相连，在这里我们需要利用一个算法去检测两点间连线是否会穿过障碍物，如果没有，则保留这条连线，否则去掉这条连线。之后继续在规划空间中随机采样，连线，重复上述过程，我们把这些连线构成的图称为路线图，当路线图足够密集的时候且包含终止点后，停止算法，第一阶段完成。第二阶段是寻路阶段，在得到路线图之后，起始点和终止点都被连接在图中，这时我们使用某种最短路径算法，比如Dijkstra算法去找到最短路径。算法示意图如图1-4所示。这个算法的优点在于不需要建立规划空间，不需要对环境中的元素进行抽象，能够适应高维空间，也能够解决用组合式规划法解决不了的问题。但是，PRM也有一些缺点，首先算法产生的路径不一定是最优的；其次，在障碍和障碍之间空间狭窄时，这个算法便不再适用，如图1-5所示。这个算法后来也有了很多的改进版本，用一些更聪明的方法去采样或者连接这些点。10

哈尔滨工业大学工学硕士学位论文图2-4PRM算法示意图图2-5PRM不适用的情况（2）快速扫描随机树方法RRT法的基本思想是把起始点当作树的根节点，然后不断地扩展这棵树，直到包含目标点。首先生成以起始点为中心的一个圆形区域，然后在这个区域内随机采样若干点，并与起始点相连接，若连接的线段无碰撞，则保留这条线段，若有碰撞则与碰撞点相连接，就这样迭代地执行下去，同时为了保证对环境的探索，我们每迭代执行若干次之后可以重新设置根节点。RRT算法执行流程如图1-6所示。RRT方法的优点在于平衡了对环境的利用与探索，同时容易实现，易扩展。但是在某些情况下不一定保证收敛，而且对于度量标准十分敏感。11

哈尔滨工业大学工学硕士学位论文图2-6RRT算法示意图采样式规划相比于组合式规划效率更高，在实际问题中更加常用，但是并不一定总是能找到最优解，而且在高维且复杂的规划空间中仍然存在着计算复杂高的问题，同时如图1-6所示，产生的路线看起来可能是最优的，但是不够平滑，存在过多的拐点，曲折，机器人很难按照这种路径去行走。2.3强化学习算法强化学习是一门交叉学科，涉及到了心理学，神经科学，计算机科学，数学等多个领域，与监督学习，无监督学习并列，是机器学习的重要组成部分[24]。强化学习不同于监督学习，不存在监督者，只存在一个奖励信号，奖励信号有些时候立即能够给出，更多的时候是一个延迟信号，比如下棋，我们在一盘棋下完后才会知道输赢。智能体要做的就是根据这个信号来调整自己的动作，目的是获得更多的奖励。当一个动作产生正的回报时，这个动作就会被加强，下次遇到相似的状态时还会选择这个动作；反之这个动作将被削弱，通过不断与环境交互获得奖励来调整自己的策略，直到最优，将强化学习的主体称为智能体（agent）。由于智能体可以仅仅通过一个奖励信号就可以得到最优策略，也就是说环境对于智能体来说是未知的。这就是强化学习的基本思想，接下来介绍强化学习基本框架和基本方法。2.3.1强化学习基本框架马尔科夫决策过程为强化学习提供了理论框架，值函数和策略等是强化学习的基本组成部分，接下来本文将从这两个部分来介绍强化学习算法。（1）马尔科夫决策过程[28]马尔科夫决策过程（MarkovDecisionProcess，简称MDP）为强化学习提12

哈尔滨工业大学工学硕士学位论文供了一个理论框架，描述了强化学习的决策过程。马尔科夫决策过程由S,A,P,R这样的四元组来描述。其中：S：代表着状态集合A：代表智能体能够采取的动作集合aP：代表着状态转移概率矩阵，即Pss'P[St1s'|Sts,Ata]，也就是智能体在时刻t，所处状态为s时，作出动作a，在时刻t1时转移到s'的概率R：代表着奖励函数，即RsaE[Rt1|Sts,Ata]，也就是智能体在时刻t，所处状态为s时，作出动作a能够获得的期望奖励在应用强化学习算法的时候，我们得到的训练样本就会是(s1,a1,r2,s2,a2,r3,...,st)这样一个状态-动作-奖励转移序列，也就是智能体根据所处状态，作出决策，得到回报，转移到新的状态，这个过程一直持续直到到达终止状态。这个序列具有马尔科夫性质，即下一时刻的状态仅仅与当前时刻所处的状态和要采取的动作有关，与历史状态和动作无关。用公式描述为：P[St1|St,At]P[St1|S1,S2,...,St,At]。马尔科夫动态过程如图2-1所示。图2-7马尔科夫决策过程示意图（2）强化学习基本组成部分马尔科夫决策过程为强化学习问题提供了基本的理论框架，几乎所有的强化学习问题都可以由MDP去建模。除此之外，强化学习还有两个重要的组成部分，分别是值函数和策略。值函数：值函数代表着对未来回报的一个预测，即在当前状态按照某一策略行动，未来可以获得累积回报的期望值，这个值可以用来作为评价一个状态好坏的指标，然后我们根据值函数去选择动作，使得智能体转移到具有较大值函数的状态上去。表达式如下：13

哈尔滨工业大学工学硕士学位论文v(s)E[Rt1Rt22Rt3...|Sts](2-1)我们对上式进行一些调整后得到式2-2：(2-2)这就是贝尔曼方程中的一种形式，贝尔曼方程说明当前值函数可以由立即回报加上下一个状态的值函数乘以折扣因子表示，这种关系为求解值函数打下了基础。其中代表折扣因子，是一个0到1之间的数，用来平衡未来回报与立即回报，如果折扣因子接近0，就代表智能体是“近视”的，更多地根据立即回报的多少去决策；若折扣因子接近1，则表示智能体是“远视”的，能够根据未来会获得的累积奖励来作出决策。值函数还有另外一类，被称为动作值函数，也叫做Q值函数，指的是智能体在当前状态，执行动作a后，再按照某一策略行动未来可以获得累积回报的期望值，表达式如下：q(s)E[Rt1Rt22Rt3...|Sts,Ata]v(s)Rt1v(s')(2-3)有了动作值函数的定义之后，我们对式2-3做一些调整可以得到下式：q(s,a)Raspss'((s))v(s')s'(2-4)其中，(s)代表智能体在当前策略下，处于状态s可以执行动作的集合，式2-4考虑了随机环境下的Q值表示，即在状态s执行动作a，有可能会转移到多个状态，转移到每个状态都有一个特定的概率。策略：策略指导着智能体行为，是强化学习问题的最终输出。形式就是一个状态到动作的映射关系，这样智能体就算在执行动作过程中出现偏差，没有按照原定路线行进，那么根据策略和当前所处的状态也会找到合适的动作去执行。策略分为两种，分别是确定性策略和随机性策略。确定性策略会根据具体状态输出一个动作，而随机性策略则会根据状态输出选择每个动作的概率，输出值为P[Ata|Sts]。2.3.2强化学习典型方法值函数估计方法[29]是强化学习中最基础的一类方法。也就是通过估计值函数来求解最优策略，因为如果能够得到值函数，一般是动作值函数，我们根据以下表达式可以求解最优策略。*(s)argmaxq*(s,a)aA(2-5)14

哈尔滨工业大学工学硕士学位论文其中，q*(s,a)maxq(s,a)。或者我们也可以通过估计状态值函数的值来得到最优策略，同理，首先得到最优状态值函数，v*(s)maxv(s)，然后利用最优状态值函数得到最优策略，如下式所示：*(s)argmaxpsa(s')v*(s')aAs'S(2-6)可以看出，如果我们已有最优状态值函数，要想求解最优策略还需要知道状态转移函数，在无模型的环境下是无法得到最优策略的。如果我们已有最优动作值函数，那么我们可以直接通过一个最大化的操作求解最佳策略。所以，对动作值函数的估计在强化学习中应用更加广泛，直接估计动作值函数也是得出最优策略的最佳方式。求解最优动作值函数是一个非线性问题，通常利用迭代的方式求解。常见的强化学习方法有三大类，分别是有模型的强化学习算法和无模型的强化学习算法，还有有模型无模型结合的方法。（1）有模型强化学习算法针对环境模型完全已知，即状态转移函数和奖励函数已知的情况，这时我们可以利用贝尔曼方程来直接求解值函数。这种问题具有优化子结构，即整个问题可以被分解成子问题，子问题的最优解组合起来也是原问题的最优解，符合动态规划的特征，因此这类有模型强化学习算法也被称为动态规划法。这里有两种典型方法，分别是值函数迭代和策略迭代。值迭代算法通过不断迭代Q值，最后所有Q值会收敛到最优。算法描述如下：算法2.1：值迭代算法输入：策略，转移函数f，初始动作值函数q(s,a)，奖励函数r，最大迭代次数n，折扣因子输出：策略动作值函数q*(s,a)=1:n：2.3.4.5.6.qqnFor(s,a)：q(s,a)rsamaxq(f(s,a),a')a'Endforqn1q15

哈尔滨工业大学工学硕士学位论文7.q*qn策略迭代算法[29]通常由策略评估和策略改进两部分构成。在策略评估中，根据当前策略计算值函数；在策略改进中，通过对值函数最大化，改进策略，重复这两个过程，直到收敛到最优策略。算法整体流程如图2-2所示。图2-8策略迭代算法首先初始化一个随机策略，然后对这个策略进行评估，也就是计算策略的状态值函数，然后利用贪心的思想对策略进行改进。算法整理流程如下：算法2.2：策略迭代算法输入：初始策略0，最大迭代次数n输出：策略动作值函数q*(s,a)，最优策略*=1:n：2.3利用值函数迭代计算i的Q-值函数qni1(s)argmaxq(s,a)ai4.q*qn，*n在策略评估过程中，往往需要等到值函数收敛之后才能进行策略改进，这其实是没有必要的，并不一定要等到值函数收敛再进行策略改进，可以在进行一次策略评估之后便开始策略改进，如此循环往复执行这两个过程，最终会收敛到最优值函数和最优策略，这便是广义策略迭代[40]的思想，很多强化学习方法都用到了这种思想。以上就是有模型强化学习算法的介绍，两种算法都需要对环境具有完整的16

哈尔滨工业大学工学硕士学位论文先验知识，能够求解有限动作集合和有限状态集合MDP问题。在策略迭代算法的两部分中，策略评估侧重于给定一个策略然后通过迭代的方式去计算出值函数；策略提升侧重于给出一个策略的值函数之后，得到一个改进后的策略。策略迭代和值函数迭代，是动态规划法的核心。（2）无模型强化学习算法强化学习较其他路径规划算法一个重要的优势在于强化学习可以在无模型环境中工作，只需要给出奖励信号，智能体就可以通过与环境不断地交互找出最优策略。通常无模型方法按照用途可以分为两大类，一类称为预测问题，也就是prediction，用来评估给定策略的价值函数，另外一类称为控制问题，也就是control，用来得到针对某一问题的最优策略。本文接下来针对控制问题介绍几种无模型强化学习方法。第一种，蒙特卡罗算法（MonteCarloMethods，又称MC算法）[30,31]，这种方法不需要环境模型，仅仅需要和环境交互生成的状态-动作-奖励序列，基本思想是对样本回报求平均。MC方法可以直接从这种序列中学习出最优策略。MC方法适用于那些有终止状态的任务，每次当一个序列结束，也就是到达终止状态后，MC方法对值函数和策略进行一次更新。MC也利用了策略迭代的思想，首先对初始策略进行评估，然后利用贪心的方法进行策略更新。策略评估方法十分简单，现在我们已经有了状态-动作-奖励序列，只需要对每一个状态-动作对得到的累积奖励求平均即可。算法如下：算法2.3：蒙特卡洛估计算法输入：被估计的策略(s)，初始动作值函数q(s,a)，累积回报returns(s,a)，最大迭代次数n，折扣因子输出：策略动作值函数q(s,a)=1:n：2.3.4.5.6.任意选择s0S，以策略产生一个序列对于出现在序列中的每一对s,a：计算出之后的累积奖励和G把G加入到returns(s,a)q(s,a)=average(returns(s,a))计算出累积回报G指的是在出现（s,a）对之后，利用动作值函数公式2-3来计算出累积折扣回报，average指的是对所有的累积折扣回报求平均，得出q(s,a)。这样我们就可以得到每一个状态-动作对在策略下的值函数。有了值17

哈尔滨工业大学工学硕士学位论文函数之后，接下来利用策略迭代中同样的思想，可以通过贪心的方式来改进策略，同时，由于MC方法若想要收敛，需要保证每一个状态-动作对都能够被访问尽可能多的次数，因此在这里采用的启发式探索开始的方式，也就是每次训练序列开始的时候，都随机地选择状态和动作，这样就尽最大可能去保证每一个状态-动作对都能被访问，保证算法的收敛性。融合了策略评估和改进的MC算法如下所示：算法2.4：蒙特卡洛算法输入：初始策略(s)，初始动作值函数q(s,a)，累积回报returns(s,a)，最大迭代次数n，折扣因子输出：策略动作值函数q*(s,a)和最优策略*(s)=1:n：2.3.4.5.6.7.8.9.任意选择s0S,a0A，所有的状态-动作对都要有可能被选中从(s0,a0)开始，以策略产生一个序列对于出现在序列中的每一对s,a：计算出之后的累积奖励和G把G加入到returns(s,a)q(s,a)=average(returns(s,a))对于序列中的每一个状态s：(s)argmaxq(s,a)a以上就是完整的MC方法。[32,33]第二种，时间差分方法（TemporalDifferenceMethod，又称TD方法），这是强化学习中最核心的方法。TD方法结合了蒙特卡洛方法和动态规划法两种方法的优点，首先，TD方法不需要环境模型，可以直接从智能体与环境产生的序列中学习出策略，这点和蒙特卡洛方法十分类似，第二，TD方法又与蒙特卡洛方法不同，无需等待一个序列到达终止状态才能更新策略与值函数，智能体每作出一个动作，获得一个奖励，到达一个新的状态，这时我们就可以对值函数和策略进行更新，更新的方式也是自展的（bootstrapping），即利用一个状态的估计值去更新另外一个状态的估计值，这种思想和动态规划法又很类似。下面介绍时间差分方法。首先介绍策略评估，和蒙特卡洛方法一样，TD算法也是从产生的序列中直接学习值函数，利用的公式如下：v(st)v(st)[Rt1v(st1)v(st1)]18(2-7)

哈尔滨工业大学工学硕士学位论文其中我们把Rt1v(st1)称为TD目标。这个值可以通过在状态st时执行一个动作，得到奖励函数，然后转移到新的状态获得。下面详细介绍TD算法：算法2.5：时间差分算法输入：待评估策略(s)，初始值函数v(s)，最大迭代次数n，折扣因子输出：策略动作值函数q*(s,a)和最优策略*(s)=1:n：2.3.4.5.6.7.8.初始化状态sFor序列中的每一步：由策略(s)得出动作A执行动作，获得回报R，转移到新的状态s'v(s)v(s)[Rt1v(s')v(s)]ss'直到s为终止状态在训练中，把一个从起始状态开始到达终止状态这样一个动作-状态-奖励序列称为一个训练循环（episode），在一个episode中每一次执行动作称为一个步骤（step）。TD算法利用对一个状态值的估计去估计另外一个状态的值，这种方法称为bootstrapping。TD算法相比于动态规划方法的好处是它不需要环境的模型；TD算法相比于蒙特卡洛算法的好处在于，它是在线的，增量式学习算法，不需要像蒙特卡洛那样，等到终止状态才开始更新，智能体每执行一步都可以更新，这样对于一些状态序列非常长的任务来说就十分适用。有了TD策略评估算法之后，本文接下来讨论TD策略改进算法，同蒙特卡罗算法和动态规划算法一样，这里我们可以利用贪心的思想去更新策略，但是在这里，更新的对象由值函数变成了动作值函数，和值函数更新类似，只是更新公式有些变化，如下：(2-8)不断地估计某一个策略的动作值函数，然后利用贪心算法去改变，使其能够朝着最优策略的方向更新。具体算法如下：算法2.6：时间差分控制算法输入：初始化策略(s)，动作值函数q(s,a),sS,aA，最大迭代次数n，折扣因子输出：策略动作值函数q*(s,a)=1:n：19q(st,at)q(st,at)[Rt1q(st1,at1)q(st,at)]

哈尔滨工业大学工学硕士学位论文2.3.4.5.6.7.8.9.10.初始化状态s根据策略(s)和当前状态选择出动作aFor序列中的每一步：执行动作a，获得回报r，转移到新的状态s'根据策略(s)和s'选择出动作a'q(s,a)q(s,a)[rq(s',a')q(s,a)](s)argmaxq(s,a)ass';aa'直到s为终止状态上述算法由于每次利用(s,a,r,s',a')五元组进行更新，因此也称为SARSA算法，这个算法在运行足够长的时间之后能够以100%概率收敛到最优动作值函数和最优策略。关于无模型强化学习算法，本文就介绍两类主要的算法，蒙特卡洛算法主要利用采样求平均的思想去学习值函数，它利用智能体与环境直接交互得到的样本去学习，主要的优点在于对值函数的估计是无偏的，而且不是十分依赖于环境的马尔科夫性质；时间差分方法结合了动态规划方法和蒙特卡洛方法两者的优点，不需要环境的模型同时可以以一种增量式的方法进行更新，而且保证收敛到最优策略，实际中应用广泛。（3）有模型无模型相结合方法这类方法，把有模型强化学习算法和无模型强化学习算法的思想结合起来。在解决有模型强化学习问题时，我们把这个过程称为规划（planning），智能体无需实际去执行某个动作，就能够知道这个动作会有什么后果，会转移到什么状态，因此在这种环境下只需要在状态空间进行搜索找到最优策略即可，所以称为规划问题；在解决无模型强化学习问题时，我们把这个过程成为学习（learning），也就是从直接与环境产生的实际样本或者是仿真出来的样本中学习出一个最优策略。下面介绍一下dyna框架[34]，融合了规划和学习，是这类方法的典型框架。在无模型强化学习中，智能体从与环境交互产生的样本序列中直接学习到值函数或者策略；在有模型强化学习中，利用虚拟产生的样本规划出值函数或者策略；在dyna中，智能体利用与环境交互产生的样本序列来学习一个模型，然后利用模型生成虚拟样本，利用实际的样本和虚拟的样本共同去学习和规划出值函数或者策略。学习模型主要指的是学习转移函数和奖励函数，学习转移20

哈尔滨工业大学工学硕士学位论文函数本质上是一个密度估计问题，学习奖励函数本质上是一个回归问题，两者都可以利用监督学习的方法解决。dyna整体框架如图2-3所示。图2-9dyna框架有了dyna整体框架，下面给出具体算法：算法2.7：dyna算法输入：折扣因子，q(s,a)和Model(s,a)，最大迭代次数n输出：最优动作值函数q*(s,a)=1:n：2.3.4.5.6.7.8.9.10.11.初始化状态s利用贪心策略选择动作a执行a，得到立即回报r，转移到新的状态s'q(s,a)q(s,a)[rmaxq(s',a')q(s,a)]a'利用r，s'更新Model(s,a)重复k次：从之前观测的状态集合中选出一个状态s从之前在状态s时执行的动作中随机选择一个动作a利用Model(s,a)计算得到r，s'q(s,a)q(s,a)[rmaxq(s',a')q(s,a)]a'以上就是dyna算法基本流程，外层循环直接利用实际的样本去学习环境模型，更新值函数，内层循环利用学习到的模型去生成样本，更新值函数，相对于单纯的规划或者学习方式，dyna算法具有更高的效率。21

哈尔滨工业大学工学硕士学位论文2.4本章小结本章介绍了传统路径规划算法，包括采样规划方法和组合式规划方法，这些方法都十分成熟，也为后来发展的路径规划方法奠定了基础。在接下来的内容中本文介绍了一种新的思想，利用强化学习去解决路径规划问题，并在2.3中首先介绍了强化学习的思想和基本组成部分，接下来将强化学习的基本算法分为三类，分别是有模型强化学习算法，无模型强化学习算法，和两者结合的强化学习算法，并在每一类算法中介绍了典型的算法，分别是动态规划法，蒙特卡洛法，时间差分法和dyna算法，这些方法有些可能由于时间复杂度不会应用到实际生活中，但是为后续的算法提供了理论基础，其余的算法都是基于这些算法演变而来。22

哈尔滨工业大学工学硕士学位论文第3章基于时间差分方法的路径规划3.1引言TemporalDifference（TD）这个名词首先由Sutton在1988年提出，Sutton受俄罗斯生物学家巴普洛夫的经典条件反射实验[35]的启发，提出了时间差分思想的框架。在巴普洛夫的实验中，首先找来一只兔子，然后对着兔子的眼睛吹气，这时由于生物的自我保护意识，兔子就会闭眼，接下来，在吹气之前亮起红灯，然后再吹气，这样重复一段时间后，兔子在亮起红灯的时候，此时还并没有吹气，就会由于保护意识闭眼，产生了一种反射。如图3-1。类似的实验还有很多，比如在给宠物喂食的时候，通常都会先摇铃提醒动物，然后喂食，经过一段时间后，动物们一旦听到摇铃声，就会马上凑过来等待吃食物[35]。这种反射在人类或者其他生物之中十分常见，本质上是一种生物适应环境的能力，也正是这种适应环境的能力才使得人类和其他生物存活到现在。图3-1兔子的眨眼反射实验Sutton从这个实验中受到了启发，提出了时间差分的思想，在兔子的眨眼反射实验中，兔子根据红灯亮起能够预测出接下来要发生的事情，在这里，红灯闪烁是一个刺激信号，在强化学习中也就是反馈信号（奖励函数），而吹气就是目标，最终的目的是使得兔子能够根据这个信号来作出正确的行为（提前闭眼）。在时间差分思想也是如此，目的是使智能体在某一个时间点根据回馈信号，预测未来将要发生的事，然后作出正确的行为。本章提出了基于成功率的时间差分强化学习路径规划的方法，记录智能体成功找到目标的次数和总的探索次数，以两者的比值即为成功率作为标准衡量智能体对环境的熟悉程度，利用成功率来动态地改变探索因子，使得智能体在训练过程中能合理地对环境进行探索与利用，比较好地解决了路径规划问题。除此之外，将详细介绍TD算法基本思想，和其他强化学习方法一样，TD23

哈尔滨工业大学工学硕士学位论文算法也分为策略评估问题和策略控制问题两大主要部分，在策略评估问题中，TD算法主要用来评估某个策略的值函数，也就是评价策略的好坏；在策略控制问题中，主要利用贪心的思想改进一个策略，这时需要借助Q值函数，然后再评估策略，两个过程迭代进行，直至收敛。本文将主要介绍两个时间差分控制方法，Q-learning[36,37]和SARSA[38]，这两种方法都基于时间差分的思想，可以进行增量式更新，同时简单易实现，因此应用广泛。3.2基于时间差分的路径规划3.2.1时间差分法基本思想时间差分方法（TemporalDifference，简称TD算法）在强化学习中有着重要的地位，最新的一些强化学习取得的成果都基于TD算法的思想，包括深度强化学习，深度Q值网络等。核心的更新公式如下：newEstimateOldEstimate+StepSize[target-OldEstimate](3-1)其中[target-OldEstimate]这一项被称为误差，随着智能体不断地学习，这一项将会越来越小。StepSize被称为学习率，是一个0到1之间的数，若学习率为0，代表智能体没有学习；若为1，则代表智能体在学习时仅仅利用最近一步的信息，在一些应用中，学习率这一项是变化的，通常随着学习时间的增长，学习率不断降低。TD算法学习的过程是自展的（bootstrapping），也就是利用对一个状态的估计值去估计另外一个状态的值。这种更新方式使得智能体在每一次作出决策都会对值函数产生更新，大大提高了效率。在算法的一开始，我们都是利用随机初始化的值去进行更新，往往是不准确的，但是当我们一旦第一次遇到了终止状态，这时，时间差分方法和蒙特卡洛估计算法得到了累积回报是一致的，无偏的，这时算法得到了一个精确的回报，然后不断迭代，时间差分方法最终会收敛到真实值。下面给出时间差分法的基本流程：算法3.1：时间差分法输入：要评估的策略，状态值函数v(s),sS，可以为任意值。初始化学习速率，折扣因子输出：策略的状态值函数v(s),s=1:n：2.初始化状态s24

哈尔滨工业大学工学硕士学位论文序列中的每一步：利用策略选择动作a执行a，得到立即回报r，转移到新的状态s'v(s)v(s)[rv(s')v(s)]，ss'直到s为终止状态将上述算法应用到路径规划问题也同样可行，输入我们要评估的策略，即状态-动作的映射关系，我们要为每个状态指定一个动作。我们把智能体所处的位置当成状态，这样智能体在任意位置都可以得到要采取的动作。接下来开始训练，初始化智能体的位置，这个位置是任意的，只要不超过地图范围即可，接下来得到要采取的动作，执行，智能体转移到新的位置，也就是到达新的状态，并且根据环境会获得一个奖励值，通常为撞到障碍物设置一个负的奖励，到达目标点设置正的奖励。接下来根据上述算法中步骤4来更新值函数，就这样不断地按照这个策略去行走，更新值函数，一旦到达终止状态，则结束一次训练循环，重置智能体，再一次开始训练，对于路径规划问题来说，终止状态指的是到达目标点，或者到达有障碍物的位置，这都会被认为是到达了终止状态。由TD算法可知，应用TD（0）算法意味着每次只更新一个状态的值函数，事实上这是不合理的。以路径规划为例，假如智能体经历了若干次状态转移之后到达目标点，此时不仅仅到达目标点前一个状态的值函数需要被更新，之前的一系列状态转移都对最终到达目标点有贡献，如何衡量这些贡献，这就是TD（）算法。为了解决TD（0）算法没有考虑到更新之前状态的问题，TD（）提出了一种记忆机制，能够记录在过去几步其他状态被访问的次数，然后利用这个机制在更新前一时刻的状态值函数时，也能对之前的状态值函数进行更新，经过实验证明，这种方法可以加速值函数的学习。我们定义“迹”来记录访问某一状态的次数，“迹”的定义如下：et1(s)sstet(s)(3-2)e(s)1sstt1在这里，是折扣因子，[0,1]表示迹衰减因子，定义了每一个状态的迹权重，若=0则此时为TD（0）算法，表明只有当前状态的前一状态会得到更新，若=1，此时为TD（1）算法，表明之前的所有状态都会得到更新，也就是蒙特卡洛算法在时间差分算法框架下的解释。图3-2以状态s1为例，用图的形式展示了s1状态随着状态转移，迹的变化情况。25

哈尔滨工业大学工学硕士学位论文s0s1s2s1s2s3s4s5图3-2s1状态迹的变化过程图3-2描述了状态序列s0s1s2s1s2s3s4s5在一开始，状态s1的迹的值始终为0，当第一次访问状态s1后，迹变为1，接下来在的作用下不断衰减，第二次访问s1后，s1的迹加1，此后由于再没有访问到状态s1，因此迹不断衰减。接下来本文讨论TD（）算法是如何更新状态值函数的。在TD（0）算法中，我们完全忽略了之前的状态，在TD（）算法中，之前的状态可以依据迹的值来进行更新，如果这个状态的迹比较小，那么这个状态的值函数也仅仅会产生一些微小的变化，反之如果这个状态的迹比较大，那么这个状态的值函数将会产生明显的变化。接下来给出TD（）算法的更新公式，首先给出误差的更新公式，如下：trt1v(st1)v(st)接下来利用如下公式更新每一个状态的值函数：v(st)v(st)tet(s)sS(3-3)(3-4)完整的TD（）算法如下：算法3.2：TD（）输入：要评估的策略，状态值函数v(s),sS，可以为任意值。初始化学习速率，折扣因子，迹衰减因子输出：策略的状态值函数v(s),s=1:n：2.3.3.4.5.6.初始化状态sFor序列中的每一步：利用策略选择动作a执行a，得到立即回报r，转移到新的状态s'计算误差rv(s')v(s)更新上一时刻状态的迹e(s)e(s)126

哈尔滨工业大学工学硕士学位论文7.8.9.10.衰减其它状态的迹e(s)e(s)更新值函数v(st)v(st)e(s)ss'sS直到s为终止状态利用TD（）算法最大的好处就是可以加快算法的收敛速度，尤其当环境奖励十分稀疏的时候，TD（）可以将得到的回馈反向传播给之前所有的状态，使学习效率更高。有了时间差分算法的基本思想之后，我们能够对特定的策略进行评估，利用广义迭代策略思想，要想得到最优策略和最优值函数，接下来要对现有策略进行改进，然后再次评估策略，两者交替进行，直至收敛。这种融合了评估策略过程和提升策略过程的方法也被称为控制算法，应用了时间差分法的控制算法主要有SARSA和Q-learning两种。3.2.2SARSA和Q-learning策略控制在策略评估的基础上加入了策略提升，也就是利用策略预测算法得到的值函数，贪心地更新当前策略，然后再一次对更新后的策略进行策略预测，这两个过程交替进行，一个结束另外一个开始，这两个过程最终的结果是一致的，预测过程收敛到最优值函数，提升过程收敛到最优策略，这两部分共同构成了策略控制算法。接下来本文将策略控制算法分为两大类，on-policy和off-policy，分别进行介绍。（1）SARSA：on-policy控制算法算法第一步首先是给出一个策略，然后对于每一个状态-动作对估计出动作值函数。这和TD（0）算法估计状态值函数是一样的过程，更新公式如下：(3-5)由上式可知，和TD（0）算法唯一的区别就是把状态值函数替换成了动作值函数。接下来给出SARSA的算法流程：算法3.3：SARSA输入：要评估的策略，动作值函数q(s,a),sS,aA，可以为任意值。初始化学习速率，折扣因子，最大迭代次数n输出：最优策略=1:n：27q(st,at)q(st,at)[rt1q(st1,at1)q(st,at)]

哈尔滨工业大学工学硕士学位论文2.3.3.4.5.6.7.8.初始化状态sFor序列中的每一步：利用策略选择动作a执行a，得到立即回报r，转移到新的状态s'更新值函数q(s,a)q(s,a)[rq(s',a')q(s,a)]利用贪心的思想更新当前策略(s)argmaxq(s,a)ass'直到s为终止状态算法第一步智能体从策略中根据所处位置选择要执行的动作，然后执行，第二步得到回报，移动到新的位置，也就是到达新的状态st1，然后得到新状态关联的动作(st1)，第三步利用公式更新动作值函数，第四步使用和蒙特卡洛控制方法中相同的机制去提升策略，策略选择在当前状态下，能使动作值函数最大对应的动作。智能体不断重复这个过程，直到收敛。由算法可知，SARSA生成训练样本，即s,a,r,s',a'的策略，对应着第一步和第二步，和我们要评估改进的策略是相同的策略，对应着第三步和第四步，因此SARSA被称为on-policy算法。SARSA和TD（0）算法面临着同样的问题，即我们每次只更新一个状态-动作对的值函数，使得效率十分低下。那么我们可不可以把TD（）的思想也用到SARSA中呢？答案是肯定的。在TD（）中，我们记录的是状态迹，一旦状态被访问，迹就增加，反之衰减，在SARSA中，我们只需要把状态迹改为状态-动作迹即可。迹的更新公式如下：et1(s,a)1sst,aatet(s,a)(3-6)e(s,a)t1同样这里的代表着衰减因子。有了状态-动作迹的定义，动作值函数的更新公式如下：q(s,a)q(s,a)e(s,a)(3-7)这样我们便得到了SARSA（）算法。（2）Q-learning：off-policy控制算法在on-policy算法中，智能体利用给出的初始策略去生成训练样本，然后利用这些样本去更新策略，相当于智能体自己不断与环境进行交互，然后改进自己的方法。还有另外一种方法和on-policy算法相对应，也可以学习到最优策略，也就是off-policy，在off-policy中，智能体利用策略来生成训练28

哈尔滨工业大学工学硕士学位论文样本，然后利用这些样本去更新策略。相比于on-policy，off-policy方式有更多的优点。由于产生样本的策略和要更新的策略不同，因此在off-policy中，智能体不一定要自己亲自去产生样本，可以利用其他智能体产生的样本去学习出最优的策略。第二，我们可以重新利用以前由旧策略产生的旧样本来更新当前的策略，这种方式被称为经验回放，也是深度Q网络的核心思想之一。off-policy中最著名的算法就是Q-learning，由Watkins在1989年提出，其影响深远，一些最新的研究成果都以Q-learning为基础。下面给出Q-learning的更新公式：q(st,at)q(st,at)[rt1maxq(st1,a')q(st,at)]a'(3-8)由上式可知，Q-learning和SARSA主要的区别在于目标值的计算，在SARSA中目标值为rt1q(st1,at1)，在Q-learning中，目标值为rt1maxq(st1,a')。SARSA利用了广义策略迭代的思想，对目标值的估计基a'于q(st1,at1)，at1也就是策略根据状态st1给出的动作，提升策略意味着根据q(st1,at1)来提升。在Q-learning中，我们使用两个策略和，利用策略来产生训练样本，而q(st1,at1)中的at1并不是由给出，是由策略给出，也是我们要更新的策略。下面给出Q-learning的算法流程：算法3.4：Q-learning输入：要评估的策略，采样策略，动作值函数q(s,a),sS,aA，可以为任意值。初始化学习速率，折扣因子，最大迭代次数n输出：最优策略=1:n：2.3.3.4.5.6.7.8.初始化状态sFor序列中的每一步：利用策略选择动作a执行a，得到立即回报r，转移到新的状态s'根据式3-5更新策略动作值函数利用贪心的思想更新当前策略(s)argmaxq(s,a)ass'直到s为终止状态通过与SARSA对比，可以发现在Q-learning中得到要采取的动作使用的策略和要更新的策略不是一个策略，在SARSA中我们利用策略得到要采取29

哈尔滨工业大学工学硕士学位论文的动作，然后改进的策略也是，这也就是Q-learning和SARSA最大的区别所在。和TD（），SARSA（）一样，在Q-learning中也可以引入迹的思想。更新公式如下：et1(s,a)qt1(st,at)maxqt1(st,a)aet(s,a)IsstIaat(3-9)0otherwise其中Isst和Iaat为指示函数，若sst则值为1，反之为0。动作值函数更新和SARSA（）类似，首先得到误差项，公式如下：rt1maxqt(st1,a)qt(st,at)ta(3-10)有了误差项之后，为所有的状态更新动作值：qt1(s,a)qt(s,a)tet(s,a)(3-11)这样我们便得到了Q（）算法。3.3基于成功率的探索方法在我们的日常生活中，时刻要面临着选择，比如当我们要出去吃饭的时候，究竟是去我们经常去的那家饭店，还是尝试一家新的饭店。这就是探索-利用问题，去一家新的饭店，意味着这家饭店可能更好吃，也可能很难吃，这就是在探索，去一家我们常去的饭店，没有任何风险，因为我们已经探索过了，这是在利用我们探索的结果，即为利用环境，我们不能一直探索，也不能一直利用。在强化学习中也是如此，每次作出决策的时候，什么时候去探索未尝试过的动作，什么时候去从已经探索过的动作中选择最好的那个，是一个问题，若智能体一直在尝试新的动作，可能永远都无法找到问题的解，若智能体一直在利用环境，可能会错过一些更好的解，这也就是探索-利用平衡问题[41]。一种很直观的解决方法就是当智能体对环境还不是很熟悉的时候，应该更多的探索环境，一旦智能体对环境已经完全掌握，此时应该更多地利用环境，就像我们去饭店吃饭，当我们一家没去过或者仅仅去过几家的时候，我们应该随机地去选择，当我们把附近的饭店都吃遍之后，就应该挑选那些我们觉得好吃的饭店。那么如何衡量智能体对环境的熟悉程度呢？传统方法通常随着训练时间的变长而减少对环境的探索，用训练时间来衡量对环境的熟悉程度，这种方法很直观，但是有时不够准确，本文提出了利用探索成功率和找到不同可行解的数量这两个因素共同衡量智能体对环境的熟悉程度，提出了一种新的探索30

哈尔滨工业大学工学硕士学位论文方法。3.3.1探索与利用平衡问题平衡探索-利用有很多方法，其中最为普遍的是-贪心策略[42]，也就是上文提到的Q-learning和SARSA算法中采用的探索策略。-贪心策略使得智能体每次在作出决策的时候，会有比较小的几率选择一个随机的动作，即为探索环境，有比较大的几率选择动作值函数最大的动作，也就是利用环境，选择动作的公式如下：argmaxq(s,a)a(s)a~A(s)(3-12)也是0~1是算法在每一步中生成的0~1之间的随机数，即为探索因子，之间的数，若比较大，则智能体偏向于尝试随机的动作，即探索环境，如果智能体每次都偏向于采用随机的动作，这样不利于智能体找到目标[43]；若比较小，则每次智能体偏向于去选择那些已知动作值函数最大的那些动作，即利用环境，如果智能体每次都偏向于利用环境，在值函数没有收敛的时候，会盲目地利用环境，往往不会得到最优解，甚至无法得到解。因此，的值影响着智能体的探索策略，如何调整的值十分关键。传统方法通常为了保证收敛速度，随着训练时间的增加而减小探索因子，即更多地利用环境，快速收敛到对应的解之中，但是这种方法的弊端在于智能体有些时候会在智能体还未能完全探索环境时使得探索因子变小，收敛到次优解甚至收敛到一个普通的解，如图3-3所示，这里利用一个简单的例子说明这个问题。图3-3次优策略示意在图3-3中，右上角五角星位置为目标，到达目标点会获得100的奖励，31

哈尔滨工业大学工学硕士学位论文假设我们的起始点在右下角，假设折扣因子为0.9，图中标红色的箭头为已经收敛的策略，只剩下右下角的状态没有得到最优策略。首先左上角向右这个动作值函数即为100，左下角向上的动作值函数为100*0.9，即90，现在考虑右下角状态的动作，此时由于初始化的原因，右下角向上和向左的动作值函数均为0，但是由于左下角向上的值函数为90，也就是说到达左下角的状态会得到90的期望奖励，那么此时右下角状态就会倾向于向左下角移动，而不是向上去尝试，这样一旦当智能体在右下角向左移动后，右下角向左的动作值函数会变成90*0.9，即81，远大于右下角向上移动的值函数0。加之在后续的训练中，探索因子逐渐变小，智能体可能永远不会在处于右下角状态时尝试向上的动作，因此只能收敛到图3-4路径。对于图3-4这种简单问题来说，发生这种情况的可能性并不是很大，但是在实际问题中，由于问题的复杂性，有很大可能出现这种情况。图3-4收敛路径这是我们不愿意看到的结果，因为显然在右下角存在着更好的策略，即向上，由于探索因子选取不当，导致我们没有在更多的状态中探索更多的动作，进而导致无法得到最优解。在面对更加复杂的问题时，就更难得到最优解。3.3.2动态调整探索因子为了打破这种局面，本文将动态调整-贪心策略中的探索因子，适时增大探索因子鼓励探索，使得智能体能够尝试更多的动作，找到更多的解，同时在对环境探索基本完成之后逐渐减小探索因子，加快收敛。那么何时增大探索因子，何时减小探索因子呢？这里以智能体的成功率和找到不同可行解的数量来作为依据，这里的成功率指的是智能体成功找到到达目标点的概率，当智能体找到一条到达目标点的路径，成功次数加1，当智能体撞到障碍或者一次训32

哈尔滨工业大学工学硕士学位论文练步数超过设定的步数，失败次数加1。在训练初期，由于智能体对环境不够了解，开始的几次尝试可能都会以撞到障碍结束，成功率会很低，这时保持探索因子不变，随着智能体对环境探索地深入，智能体会找到到达目标点的路径，并得到正的奖励，因此在以后的尝试过程中，智能体会更多地沿着这条路径行走，这条路径上的状态值函数变大，成功率变高，此时引入另外一个评价标准，即找到不同解的数量，对于路径规划问题来说，即为找到到达目标点路径的数量，若这个数量一直保持在一个比较小的数字并且不变，则说明智能体一直在重复旧的路线，此时产生的样本不具有代表性，我们此时应该增大探索因子，鼓励智能体去找到其他的路径。在这里，成功率反应了智能体的一种稳定程度，若成功率变高，则说明智能体陷入了一种稳定的状态，不断地找到问题的解，但是我们不能判断出这个解是否是最好的，一直在重复相同的解也会使成功率变高，但是这并不是我们希望看到的结果，因此这里同时引入找到不同解的数量这一标准，找到不同解的数量反应了智能体对环境的掌握程度，找出不同的解越多，则说明智能体对环境掌握程度越高，但是仅仅依据找到不同解的数量来调整探索因子也是不对的，比如当找到解的数量保持不变时，一方面可能是智能体基本找到了所有解，可以停止算法，也有可能是智能体陷入了原来的解当中，未能发现新的解；这时就需要成功率来作为另外一个因素来帮助我们去调整，若成功率较高但是解的数量较少，则说明很有可能是第二种情况，此时应该增大探索因子，探索新的解；若找到不同解的数量较大，且成功率也较高，则说明此时智能体很有可能已经找到所有解，可以缓慢减小探索因子，继续观察。因此这两个标准要一起考虑，才能更好地调整探索因子。总结起来，即在智能体成功率变高，同时解的数量在一个较低的数目保持不变时，此时按照一定步长缓慢增加探索因子；若解的数量仍然保持不变或者先增加再不变，则说明问题很可能已经收敛；此时缓慢减小探索因子，直到0。传统的方法通常随着训练循环数目的增加来调整探索因子，与传统方法相比，本文提出的方法考虑了更多的因素，符合算法运行规律，具有更强的适应能力和更好的效果。3.4基于成功率的探索方法与时间差分法的结合本小节将3.2中介绍的Q（）-learning和3.3中介绍的探索方法结合起来来解决路径规划问题。具体算法如下：算法3.5：基于成功率的时间差分算法33

哈尔滨工业大学工学硕士学位论文输入：初始策略，初始动作值函数q(s,a)，最大迭代次数n，每次迭代最大尝试步数k，初始化探索因子，折扣因子，最大成功率srate，最低可行解数量pathnum1，最多可行解数量pathnum2，探索因子变化步长stepsize，探索因子改变周期round输出：策略和动作值函数q(s,a)=1:n:2.清空templiststepsize*(pathnum1num)(x/i)srate,numpathnum13.stepsize*(i/round)(x/i)srate,numpathnum24.得到初始状态=1:k:生成0，1之间随机数，若大于，执行(s)，反之随机挑选一个动作执行。假设这步选择的动作为a执行动作a，得到奖励r，转移到新的状态s'Ifs'为终止状态：若s'为目标状态，xx1，判断templist是否在list中，若不在则加入list，同时numnum1。跳出循环Else:计算误差：rmaxq(s',a')q(s,a)a'更新动作状态迹：e(s,a)e(s,a)1更新其他动作状态迹：e(s,a)e(s,a)更新动作值函数：q(s,a)q(s,a)e(s,a)s'添加到templist中ss'templist用来保存一次探索的路径，pathlist用来存储找到的所有路径，num用来保存找到解的数量，x用来保存成功找到目标的次数。在路径规划问题中，算法将智能体位置作为状态。算法与传统Q（）-learning不同的地方如下：第3步动态改变探索因子，这里利用了成功率和找到解的数量。需要注意的是，改变探索因子的时候，需要连续多次迭代都满足相应条件才改变。第8步到第11步用来记录智能体探索成功次数，一旦找到目标点，则成功次数加1，然后判断这条路径是否和之前的成功路径重复，如果不重复，则加入到路径集合中。34

哈尔滨工业大学工学硕士学位论文第16步保存智能体每次迭代的状态转移序列，在路径规划问题中，状态转移即为路径。3.5本章小结本章主要提出了基于成功率的探索方法，介绍了强化学习中存在的探索利用平衡问题，并且针对传统探索方法中收敛过早，往往得不到最优解的问题，本文分析了强化学习算法的运行规律，提出了优化的探索方法，即以成功率作为标准衡量智能体对环境的熟悉程度，根据这个标准来指导智能体进行探索，可以在合适的时候鼓励智能体进行探索，使得智能体找到最优路径。并与Q（）-learning相结合，描述了具体的算法。除此之外，介绍了强化学习中最核心的算法，时间差分方法，首先介绍了时间差分预测算法，也就是如何利用时间差分方法去评估一个策略，介绍了TD（0）算法，针对TD（0）算法每次只能更新一个状态的值函数，收敛速度慢的问题，提出了改进的TD（）算法，TD（）引入了迹的概念，记录了之前状态被访问的频率，作为更新的权重，这样每次更新的时候，所有状态都会得到更新。第二部分本文介绍了时间差分控制算法，也就是如何输出最优策略，介绍了SARSA算法和Q-learning算法，这两个算法都以估计动作值函数为基础，只是SARSA采样和改进利用的是相同的策略，相当于智能体自己去尝试，然后改进，因此称为on-policy；而Q-learning算法中采样和改进的策略是不同的，相当于看着别人如何做，然后改进自己的策略，因此称为off-policy。采用和TD（）相同的思想，介绍了SARSA（）和Q（）-learning。35

哈尔滨工业大学工学硕士学位论文第4章仿真实验及结果分析4.1引言本章将把强化学习中的时间差分法方法与路径规划问题结合起来，并分析实验结果。随后将本文提出的探索方法和Q（）-learning相结合，与传统探索方法进行了比较。实验平台为VISUALSTUDIO2012。4.2仿真实验说明（1）环境模型本章节使用“栅格”法表示的地图，地图尺寸分别是10*10，20*20，即地图长宽分别为10个单位长度，如图4-1所示。其中黑色方格代表障碍，左下角代表的是智能体，右上角红色五角星代表的是导航终点，在程序中地图使用文件进行存储，起始点用数字0表示，障碍物用-1表示，空白栅格用1表示，目标点用2表示，这样就可以用一个10*10的矩阵来表示一个尺寸为10x10的地图。图中标注的数字即为状态，每一个栅格代表一个状态，智能体在栅格间移动。实验的目的是从地图中任意一点，终点，障碍物点除外，都能找到一条到达目标点移动步数最少的路线。图4-1实验场景（2）MDP四元组强化学习问题都可以用马尔科夫决策过程来进行建模，在本问题中，马尔36

哈尔滨工业大学工学硕士学位论文科夫四元组定义如下：动作集合：上下左右四个动作，智能体将沿着栅格运动，从一个栅格移动到相邻的四个栅格中，不可以沿对角线移动，不可以跨格移动。在程序中利用一个枚举变量来表示这些动作。状态集合：每个格子代表一个状态，在图4-1中已经标出，分别用1-100表示这些状态，左上角的格子为状态1，右下角的格子为状态100，目标状态和中间的障碍物，为终止状态。一旦智能体移动到终止状态，一个训练循环（episode）结束，智能体重新选择初始位置，进行下一次训练。转移概率矩阵：本例假设状态转移成功率为80%，即执行动作有一定偏差，智能体执行动作后会有80%的几率移动到相应位置，有20%的几率偏移到其它位置。奖励函数：也叫强化信号。到达右上角目标状态，即状态10，会得到1的奖励，若到达中间的障碍物状态，状态32，33等，则得到-1的奖励，即表示惩罚，到达其余状态，会获得-0.04的惩罚，代表智能体电量的损耗，这样可以使智能体尽快到达目的地。（3）程序相关数据结构定义程序中涉及许多要存储的变量，假设栅格地图的尺寸为10*10，也就是有100个状态，由于动作有4种，那么Q值表即为4*100维的矩阵，全部初始化为0。与Q值表相关的就是迹，迹存储的是每个状态-动作对访问的频率，因此大小也为4*100维。（4）参数初始化情况强化学习中有几个重要的参数会决定强化学习算法收敛的速度，首先是奖励折扣因子，取值在0，1之间，这个因子决定了智能体是“远视”的还是“近视”的，如果这个因子接近于0，那么智能体就会更看重立即回报，反之若接近1，那么智能体就会同样看重未来的期望回报。由于本实验是路径规划问题，环境不确定性程度较低，而且总会遇到终止状态，因此未来回报和立即回报的比重是接近的，实验将折扣因子初始化为0.8。第二个重要的参数即学习速率的设置，同样为0，1之间的实数，如果过小，那么学习速度就很慢，算法迟迟不能收敛，若过大，有些时候会使算法收敛到不正确的值。这里根据经验，将学习速率设置为0.01。第三个重要的参数即的值，由于在实验中，使用了-贪心策略来控制探索-利用的平衡，同时保证算法的收敛性，因此需要设置的值，同样为0，1之间的实数，若接近于0，那么代表智能体利用环境更多一些，就会导致37

哈尔滨工业大学工学硕士学位论文错过一些比已知最优动作更好的动作，反之若接近于1，则表示智能体探索环境多一些，而过多的探索会导致算法运行时间过长。本节将根据不同算法为设置不同的初始值。每次训练循环最大探索步数设置为300，即每个训练循环最多允许智能体作出300次决策，如果行动步数超过300智能体没有到达终止状态，则说明此次使用的策略是很失败的策略，没有必要继续执行动作，此时终止训练，重置智能体，进入下一轮学习。每次训练循环最大探索步数的设置和具体的问题相关，若问题较简单，则这个值较小，若问题比较复杂，不容易得到最优策略，则需要更多的探索步数。由于强化学习算法大多使用的都是迭代的思想去计算，因此要设置算法的终止条件，若对于任意一个状态，相邻两次迭代值函数变化的差值小于一个阈值，则认为算法已经收敛，这里的阈值设置为1e-6。（5）算法输入和输出在无模型方法中，算法无需任何输入，只需要在智能体运动到相应状态给出奖励信号即可。算法最终的输出都是相同的，即最优动作值函数和最优策略。4.3实验结果及分析本小节将强化学习方法应用到路径规划中，比较这些方法的优劣。分成两大部分，第一部分是时间差分法在路径规划中的应用，第二部分将本文提出的探索策略和传统的探索策略分别与Q（）-learning相结合，比较几种探索算法的收敛策略。4.3.1无模型方法在路径规划中的实验本小节将介绍无模型方法在路径规划中的应用，主要介绍时间差分法，其中包括两种典型的方法，Q-learning和SARSA，以及它们的改进方法Q（）-learning和SARSA（）。本节将分别使用10x10格子世界和20x20格子世界进行验证，将转移概率不确定性表示成如下矩阵：0.80.100.10.10.80.1000.10.80.10.100.10.8即每次智能体向上移动，会有0.8概率向上移动，有0.1的概率向右移动，有0.1的概率向左移动。同理，每次智能体向右移动，有0.8的概率向右移动，38

哈尔滨工业大学工学硕士学位论文有0.1的概率向上移动，0.1的概率向下移动。这样就模拟了实际环境下智能体移动的不确定性。首先本节将使用SARSA算法解决上述问题，SARSA方法是一种典型的on-policy方法，首先定义一个随机策略，在实验中设置的是无论处于什么状态均采用向左的动作。然后智能体通过与环境不断进行交互去改进这个随机策略，最终经过多次迭代之后，算法将会收敛到最优策略。接下来使用Q-learning算法来解决同样的问题，Q-learning和SARSA不同的是它是off-policy方法，产生样本的策略和算法要改进的策略是不同的策略。两种算法的执行结果如图4-2所示。图4-2SARSA（左）和Q-learning（右）运行结果由图4-2可知，SARSA和Q-learning针对同样的问题产生的策略基本一致，直观上来看两种策略在多数状态下产生的是最优策略。下面分析两者的收敛速度，如图4-3和图4-4所示。39

哈尔滨工业大学工学硕士学位论文图4-3SARSA算法收敛情况图4-4Q-learning算法收敛情况图4-3和图4-4的横轴为训练循环次数，纵轴为每次更新所有状态的误差和，形式如下：rt1maxqt(st1,a)qt(st,at)Qlearningat(4-1)rq(s,a')q(s,a)SARSAtt1tttt1在一次训练循环中，这个差值反应了同样的状态-动作对值函数，上一次训练与本次训练的差异，也就是值的改变情况，每个访问到的状态-动作对都会产生这样的误差，把一次训练循环中产生的误差累加起来作为纵轴，这样就可以反应出每个训练循环中状态-动作值的改变情况，一旦改变趋近于0，那40

哈尔滨工业大学工学硕士学位论文么就说明每一次训练中的策略不再改变，进而说明动作值函数不变。即策略先收敛，然后值函数收敛，策略收敛定义为近500次训练策略都保持不变，这时停止训练。由图4-3和图4-4可知，两种算法的收敛速度也基本相同，均在40000次训练后收敛，最终这个差值在0上下波动，只是SARSA算法在收敛之后的波动值要大于Q-learning。两者并无优劣之分，但是在很多情况下Q-learning由于它的off-policy性质，应用更加广泛。下面将Q-learning和SARSA算法的两种改进算法Q（）-learning和SARSA（）应用到相同的问题中，为了解决Q-learning和SARSA每次只会更新一个动作值函数的问题，Q（）-learning和SARSA（）提出了迹的概念，更新公式如下：e(s,a)1sst,aatet(s,a)t1et1(s,a)在这里将迹衰减因子设置为0.5。实验结果如图4-5所示。(4-2)图4-5SARSA（）和Q（）-learning得到的最优策略由上图可知，在某些状态，Q（）-learning会得到次优策略，比如右下角目标的左上方的位置，Q（）-learning给出的策略是向上，但实际这样会多走两步才能到达目标点，最优的策略应该是向右或者向下，这是由于Q（）-learning总是根据其它的策略产生的样本去学习，也就是说学习别人，所以一旦产生样本的策略不够好，就会造成次优策略。而SARSA（）表现一般比较稳定，产生的策略一般都是接近最优的策略。Q（）和SARSA（）无法在每一个状态都得到最优策略的原因在于探索与利用的平衡不好控制，一旦智能体找到了一条到达终点的最优策略，那么接下来就有很大的可能性沿着这条41

哈尔滨工业大学工学硕士学位论文路径走下去，尽管有些时候这条路径不是最优的，但是智能体已经对其产生了依赖性，尽管有时会探索其他的动作，但是马上就会再次回到原来的路径上，这也是强化学习中一个固有的问题。下面比较SARSA（）和Q（）-learning的收敛速度。如图4-6和图4-7所示。图中横轴为迭代次数，纵轴为误差和。由图可知，SARSA（）算法收敛较快，但是存在着较大波动，也就是说动作值函数还在发生着变化，而Q（）-learning算法收敛较慢，但是收敛之后，值函数基本不会产生较大变化，两者的收敛速度要快于SARSA和Q-learning，说明加入迹之后，会加快算法收敛速度。在这里需要注意一点，由于存在着动作不确定性，这里是无法使得误差项收敛到0，通常会在0附近波动。图4-6SARSA（）算法收敛情况42

哈尔滨工业大学工学硕士学位论文图4-7Q（）-learning算法收敛情况接下来，本文将使用更加复杂的环境，如图4-8所示，这次使用20x20的格子世界作为规划地图，并添加了更多障碍，增加了实验的复杂度，在这个环境中，状态数量由原来的100个增加到了400个，其余条件不变。图4-8导航环境使用SARSA（）进行实验，收敛的策略如图4-9所示，收敛情况如图4-10所示，由图4-10可知，图中横轴为迭代次数，纵轴为误差和。随着状态数目的增加，波动值的范围也在增加。算法在经过了180000次训练之后策略和动作值函数才收敛，在10x10格子世界中，SARSA（）收敛次数是30000，43

哈尔滨工业大学工学硕士学位论文这也验证了SARSA（）算法的时间复杂度为(n2)，n代表状态数目。图4-9SARSA（）算法策略图4-10SARSA（）算法收敛情况4.3.2基于成功率的探索方法的Q（）-learning本小节将本文提出基于成功率探索方法与强化学习中典型的探索利用平衡方法进行比较，分别是-decreasing方法，-first方法和Upper-Confidence-Bound（UCB）方法，分析实验效果。下面分别简述上述方法。44