强化学习模型及其在避障中的应用

孙　魁,吴成东（.沈阳建筑大学信息学院;　.沈阳建筑大学,沈阳　006）



强化学习模型及其在避障中的应用

孙魁1,吴成东2
（1.沈阳建筑大学信息学院;2.沈阳建筑大学,沈阳110016）

摘 要：强化学习是机器学习的一个重要分支，其优点是不需要先验知识，通过与环境的交互进行试错学习。与有导师学习不同，强化学习没有得到确定的目标值而是一个奖赏值。本文介绍了强化学习的模型和一些常用算法，并将强化学习的方法应用在避障问题上。

关键词：强化学习；马尔科夫决策；避障

1　概述

强化学习(Reinforcement Learning，RL)是近几年来人工智能和机器学习研究的热点。不同于监督学习，强化学习强调与环境的交互并在其中进行学习，用极大化的从环境获得的评价性反馈信号为学习目标，所以强化学习在求解那种无法获得教师信号的复杂优化决策问题中具有广泛的应用[1][2]。

强化学习是机器学习的一个重要分支。强化学习通过对环境的反复试探，从中学习环境到可执行动作的最优反应式策略，以期获得最大回报。相比于其它学习策略，强化学习的明显优势在于它对先验知识的是否完备几乎没有要求，即使在信息完全未知的情况下，强化学习仍然具有较好的自适应性和鲁棒性[3]。

传统的强化学习方法主要针对的是离散状态和行为空间的马尔科夫决策过程，也就是状态的值函数或行为的值函数采用了表格的形式来进行存储和迭代计算。但是实际工程应用中的许多优化决策问题是具有大规模或连续的状态或行为空间的情况，所以表格型强化学习算法也同动态规划法一样存在维数灾难。为了克服维数灾难，以实现对连续性状态或行为空间的马尔科夫决策过程的最优值函数和最优策略的逼近，我们就必须研究强化学习的泛化问题或推广问题，也就是利用有限的学习经验和记忆以实现对一个大范围空间的有效知识获取和表示的方法。

2　强化学习模型和马尔科夫决策过程（Markov decision process, MDPs）

2.1强化学习模型

强化学习系统的基本要素包括：状态集合S、控制行为集合A、控制策略p、强化信号R和状态评价函数V（s）[4]。

强化学习要研究解决的问题是：一个能够感知外部环境的自治智能体(Agent),通过学习选择能够到达目标任务的最优动作，即强化学习Agent的任务就是学习从环境到动作的映射[26]。强化学习跟连接主义学习中的监督学习的区别主要表现在不存在教师信号上，强化学习中的由环境提供的强化信号是对Agent所产生动作的好坏作出一种评价(通常为标量信号)，而不是直接告诉Agent如何去产生确定性的动作。由于外部环境提供了很少的信息，Agent必须靠自身的探索进行学习，通过这种方式Agent在行动-评价的环境中获得知识、改进行动方案以适应环境。

强化学习具有以下特征：

Agent不是静止的、被动的等待，而是主动对环境做出试探；环境对试探动作反馈的信息是评价性的(好或者坏)；

Agent在行动-评价的环境中获得知识，改进行动方案以适应环境，达到预期目的。

标准的Agent强化学习框架如图1所示，Agent通过感知和动作与环境交互。在Agent 与环境每一次的交互过程中，强化学习Agent接收环境状态的输入s,根据内部的运算机制，输出相应的行为动作a。环境在动作a的作用下，转移到新的状态s’，与此同时产生一个强化信号(立即回报)r(奖励或惩罚)返回给Agent，Agent根据环境状态和强化信号选择下一个动作，选择的原则是使Agent获得最大的回报值。选择的动作不仅影响立即回报值，而且影响下一时刻的状态及最终时刻的强化值。在学习过程中，强化学习技术的基本原理是：如果系统的某个动作导致环境正的回报，那么系统以后产生这个动作的趋势就会加强，反之系统产生这个动作的趋势便会减弱。这和生理学中的条件反射原理是接近的。

2.2马尔科夫决策过程（Markov decision process, MDPs）

大多数关于强化学习方法的研究都是建立在马尔科夫决策过程理论框架之上的，尽管强化学习方法并不局限于马尔科夫决策过程，但离散的、有限状态的Markov决策过程框架是强化学习算法的基础。

马尔科夫决策过程起源于随机优化控制，是一个离散时间的随机过程，由六元组{S,A,D,P,r,J}来描述。六元组中，S为有限的环境状态空间；A为有限的系统动作空间；D为初始状态概率分布，当初始状态是确定的，D在该初始状态下的概率为1，当初始状态是以相等的概率从所有状态中选择时，则D可以忽略；为状态转移概率，表在状态s下选择动作a后使环境状态转移到s’的概率；为学习系统从状态s执行动作a转移到状态s’后获得的立即回报(奖赏)，是一种“近视”的表达信号；J为决策优化目标函数。马氏决策过程的特点是目前状态s向下一个状态s’转移的概率和回报只取决于当前状态s和选择的动作a，而与历史状态无关，因此MDP的转移概率P和立即回报r也只取决于当前状态和选择的动作，与历史状态和历史动作无关。若转移概率函数P(s , a , s ')和回报函数r(s , a , s ')与决策时间t无关，即不随时间t的变化而变化，则MDP称为平稳MDP。

2.3累积奖赏模型（3种）

MDP的决策优化目标函数J一般分为3种类型，即有限阶段总回报目标、无限折扣总回报目标和平均回报目标。

有限阶段总回报目标为

式中，tr为t时刻得到的立即回报；N表示智能体的生命长度，即马尔科夫链的长度。在多数情况下，智能体学习的生命长度是未知的，且当N®¥时，函数可能会发散。因此，有限阶段总回报目标很少考虑。

无限折扣总回报目标为

平均回报目标为

3　强化学习基本算法

强化学习主要算法有动态规划法(Dynamic Programming, DP),蒙特卡洛法(Monte Carlo, MC)和时序差分法(Temporal Difference, TD)和Q学习（Q-learning）等。

3.1动态规划法

动态规划法是一种基于模型的策略寻优方法。这种方法将动态系统的状态和值函数的概念用于定义函数方程(现在通常称为Bellman方程)。这类通过求解Bellman方程来解决最优控制问题的方法被称为动态规划。

动态规划在过去的几十年中已经取得了极大的发展，被广泛地认为是求解一般随机最优控制问题的唯一切实可行的方法。但是，动态规划存在所谓的维数灾难问题，也就是说，动态规划的计算量需求随着状态变量数目的增加而呈指数级增长。但是相比于其他方法，动态规划仍然是一个非常有效且应用广泛的方法。动态规划与强化学习密切相关，对于马尔科夫决策问题，前者主要解决环境的状态转移概率和回报函数已知的决策问题，而后者主要处理状态转移概率和回报函数未知的情形。

3.2蒙特卡罗法

在概率和统计理论中，蒙特卡罗（Monte carlo, MC）方法是一种用部分估计整体利用随机数来解决问题的方法，通过统计模拟或抽样方式以获得问题的近似解。将MC引入强化学习中，就得到一种无模型的学习方法。此方法不需环境的先验模型，只需要通过与环境的交互来获得的实际或模拟样本数据（状态、动作、奖赏）序列，从而去发现最优策略。MC方法与策略迭代原理类似，分为MC策略评估和MC策略控制两部分，MC方法主要用在策略评估中。

本质上讲，MC方法就是基于平均化样本回报值来求解值函数的方法，从而解决强化学习问题。为了确保良好的定义回报值，MC算法定义为完全抽样的即所有的抽样点必须最终终止只有当一个抽样点结束，估计值和策略才会改变。因此该方法只适合于场景式任务，即任务存在终止状态，任何策略都在有限步内以概率1到达终止状态。

3.3时序差分法

1988年，Sutton等人提出了一种用于解决时间信度分配问题的方法：时间差分方法TD，而强化学习中所用的主要方法都是基于TD的。TD学习方法结合了蒙特卡罗和动态规划两种方法的思想，不需要系统模型，这样能够直接从学习者的原始经验开始。与动态规划方法一样，TD方法通过预测每个动作的长期结果来给先前的动作赋予奖励或惩罚，即依赖于后续状态的值函数来更新先前状态值函数，主要应用于预测问题。

3.4Q-学习

Q-学习是由Watkins提出的一种模型无关的强化学习算法。Q-学习在迭代时采用状态-动作对的奖赏值和Q*(s,a)作为估计函数，而不是TD算法中的状态奖赏和V（s），因此在每一次学习迭代过程中都需要考察每一个行为，可确保学习过程收敛。

Q函数定义及Q值的调整方法如下：

4　基于Q学习的避障应用

良好的学习性能使得强化学习在实际中获得越来越广泛的应用，应用领域有各种任务调度、机器人控制和游戏等等。本文简单介绍基于Q学习的避障应用。

避障环境采用20X20栅格，模拟Agent从左下角出发点出发，通过基于Q学习算法的动作选择到达目标点设定在（19，15），在过程中要避开随机放置的障碍物，并且动作过程中不能离开栅格边界。模型将Agent的坐标作为Q学习中的状态参数，在每一个栅格，Agent只有上、下、左、右四个动作空间。回报函数如下：

Q初始值设为0。

MATLAB仿真结果如图2。

仿真结果表明Q学习算法能够收敛并成功实现避障达到目标点。

5　结束语

强化学习是一种很有前途的学习方法，已经引起越来越多学者的研究兴趣。近年来呈现了大量的研究成果，但是仍然有许多亟待解决的问题，例如算法的收敛速度问题与维度灾难问题。尽管强化学习发展道路上充满困难与挑战，但是其前景广阔，是未来的趋势。

参考文献：

[1]Leslie Pack Kaelbling, Michael L. Littman, Andrew W. Moore. Reinforcement Learning：A Survey. Journal of Artificial Intelligence Research 4 (1996) 237-285.

[2]Richard S. Sutton , Andrew G. Barto , Reinforcement Learning : An Introduction , MIT Press, MA, 1998.

[3]R. S. Sutton，A. G. Barto．Reinforcement learning: An Introduction[M]．MIT Press，Cambridge， MA，2006，72-77．H

[4]P van Hasselt. Insight in Reinforcement Learning: formalanalysis and empirical evaluation of difference learning algorithms. SIKS dissertation series,2011.

[5]John Holand．Reinforcement learning: A survey[J]．Machine learning，1988，3(1):9-14.

[6]Wang X L，Wang L．Research of distinguish matrix dealing with unconformity problems in rough sets[J]．Microcomputer Development，2008，13(6):119-120．

[7]D. Michie，R. A. Chambers．Box: An experiment in adaptive control[M]．Machine intelligent，2010，137-152．

[8]J. C. Q-learning[J]．Machine Learning，1992，8:279-292．rough sets theory[M]．Kluwer Academic Publishers，Norwell，MA，1992．

[9]Markov．Algorithm for attribute reduction based on reinforcement learning on improved discernibility matrix[J] ．Computer Engineering and Application，1997，43(32):83-85．

[10]Wu C D，Zhang Y ，Li M X ．A rough set GA-based hybrid method for mobile

robot[J]．International Journal of automation and computing 2006，3(1):29-34．

[11]R. Slowinski．Intelligent decision support: handbook of applications and advances of the47

[12]陈锋,胡社教,陈宗海.未知环境下自主移动机器人的行为学习研究[J].模式识别与人工智能,2006,15(04):498-501．

[13]张汝波,顾国昌,刘照德.Q学习理论、算法及应用[J].控制理论及应用,2007,17(05):637-642．

[14]阎平凡．再励学习算法及其在智能控制中的应用[J]．信息与控制，2006,25(01):28-34．

[15]张汝波.滚动式窗口算法及应用[M].哈尔滨:哈尔滨工程大学出版社,2006:134-139．

[16]陈学松,杨宜民.强化学习研究综述[J].计算机应用研究,2010.

DOI :10.16640/j.cnki.37-1222/t.2016.01.234