随机环境中基于强化学习的智能体路径规划

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 随机环境中基于强化学习的智能体 路径规划 摘要：为解决随机环境下的智能 体的路径规划问题，借助强化学习算法 的自学习和和自适应的特点，引入 Q 学 习算法处理随机环境下的路径规划问题。 实验结果表明，该算法在解决随机环境 中路径规划的有效性。 中国论文网 /8/view-12746366.htm 关键词：强化学习； Q_learning；路径规划；随机环境 中图分类号：TP18 文献标识码： A 文章编号： 1009-3044（2015）31- 0148-02 Reinforcement Learning based Agent Path Planning in Random -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 Environment MA Peng-wei， PAN Di-lin， WANG Li-dong （Anhui University of Science and Technology， Computer Science and Engineering， Huainan 232001，China） Abstract： In order to solve the problem of path planning on agent in random environment， with the help of reinforcement learning algorithm of self learning and adaptive characteristics of the introduction of Q_learning algorithm to deal with the path planning problem of random environment. The experimental results show that the algorithm in solving path planning in random environment is effective. Key words：reinforcement learning； Q_learning； path planning； random environment 1 概述 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 路径规划1是一个重要的研究课 题，在机器人导航和游戏智能体中都有 着很大的研究价值。在确定环境下（比 如只有静止障碍物的寻路过程）可以很 有效地解决此类问题。但在随机环境下， 这种随机性就破坏了 A*算法的要求。 随机环境相对于确定环境（固定顺序的 一系列操作一定会得到相同的结果）而 言的，因为每一步的操作的结果都是随 机的，即使相同的操作序列也会得到不 同的结果。此时如果强行应用的话，最 好的情形也需要做很多修改工作，最差 的情形是 A*会给出错误的答案。在此 我们引入一个解决随机条件下的多步决 策问题，强化学习（Reforcement Learning） 。 强化学习是一种在线的、无导师 的机器学习方法，主要表现在由环境提 供的强化信号对智能体所产生动作的好 坏作一种评价，而不是告诉智能体如何 产生正确的动作，智能体依靠自身与环 境的交互进行学习，在行动和评价的环 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 境中获得知识，对行动方案进行改进适 应环境，已达到获得最优动作。20 世纪 90 年代，强化学习通过与运筹学、控制 理论的交叉结合，在理论和算法方面取 得了突破性的研究成果，奠定了强化学 习的理论基础，并在机器人控制领域、 优化调度等序贯决策中取得了成功的应 用2。 2 强化学习 强化学习是一个能够感知环境的 自治智能体如何通过学习选择能够达到 目标的最优动作，即强化学习的任务就 是学习从环境到动作的映射3。强化学 习的学习过程类似于人，从来不是静止 被动地等待，而是主动地对环境试探交 互，从环境给予的反馈信号来学习知识， 改进行动方案，已达到预期的目的，这 也符合强化学习的特征4。强化学习大 部分都是以马尔科夫决策过程（Markov Decision Process）为基础。马尔科夫决 策过程借助四元组来描述。S 为环境状 态空间，A 为动作空间， P为状态转 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 移概率，r为立即回报函数。强化学习 的模型如图 1： 图 1 强化学习框架 在马尔科夫决策过程中，Agent 是通过一个决策函数（即策略）来选择 动作的，常用 表示策略。在定义了策 略后对应状态-动作值函数为 Q（s ，a），Q（s，a）表示在状 态 s 下根据策略 执行动作 a 的期望值 如式（1）： Q（ s，a ） =Et=0trt+1|st=s，at=a （1） 最优动作值函数的定义为式 （2）： Q（ s，a ）=maxQ （s，a ） =sSP（s ， a，s）r+maxa AQ*（s，a） （2） 最优策略是使得 Agent 在每一个 状态下均能获得最大值的策略如式 （3）： -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 *（ s）=arg maxaQ*（s，a） （3） 其中arg maxaQ*（s，a） 是状 态S的一个函数，其值为使 Q*（s，a） 最大的动作 a。一些强化 学习算法已经在理论和应用方面取得了 重大的成功Q_learning5 ，TD（）6， SARSA7。本文选取 Q_learning 算 法，Q_learning 是一种有效的模型无 关强化学习算法。 3 Q_learning 算法 Q_learning 算法是 Watkins 最早 于 1989 提出来的8，又称离策略 TD 学习。它采用Q（s，a ） 状态动作对的 值做估计函数。在Q 学习中智能体维 护一个查找表Q（s，a ） ，其中Q 和 S分别是状态和行为的集合智能体借助 时间差分的思想来更新查找表。智能体 在每一次学习迭代时都需要考察每一个 行为，如果每个状态-动作对被无限频 繁的访问，且学习率合适，算发最终会 收敛，其收敛性已得到证明。常见的动 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 作选择策略有-greedy 和 Boltzmann 分 布，本文采用的是-greedy算法，指的 是多数情况下选择具有最大 Q 值的动作， 但以概率选择其它动作。Q_learning 的迭代公式如（4）： Q（ st，at） Q（st ，at ） +rt+maxaQ（st+1，a ） -Q（st，at ） （4） 其中为学习率（步长） ， （0，1，为折扣因子， （0，1 其学习过程如下： Step 1：初始化：Qs，a为任意 值（为方便计算，通常初始化为 0） ，设 置步长，折扣因子 。 Step 2：Repeat 给定起始状态S2 Repeat（对于一幕的每一步） 根据-greedy 的策略选择动作at ， 得到立即回报rt和下一个状态 st+1 更新Q（st，at ）Q（st，at） -精选财经经济类资料- -最新财经经济资料-感谢阅读- 8 +rt+maxaQ（st+1，a ） -Q（st，at ） stst+1 直到st是终止状态 直到所有的Q（s，a）收敛 输出最终策略。 Q学习算法在强化学习算法中 最为基本，实际应用也很广泛。只要在 任意的状态智能体尝试一个行为的次数 不受限制（即智能体在一个状态不会总 是执行相同的行动子集） ，则不管智能 体真正依据的策略是哪个，Q学习都 学习一个最优的策略。 4 实验结果与分析 为了验证算法的有效性，本文选 取一个 15X10 的迷宫如图 2，S 为迷宫 的开始节点，G 为终点，棕色块相当于 墙壁或障碍物，灰色块为可行区域，红 色块代表陷阱，绿色块为算法的最终的 规划路径。 图 2 本文选取为 0.2， ，折扣率 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 9 为 0.9，步长为 0.1，回报函数 r 定义 如式（5）： r=5 终点，随机选取一个点开始 -5 陷阱 -1 撞到墙壁或障碍物，待在原地 0 其他情况 （5） 智能体刚开始从S位置出发，目 标是终点G 的位置。执行动作 a时有 一定的概率会向两侧移动（假如 0.8 概 率向右移动时，会有 0.1 的概率向上移 动，0.1 的概率向下移动）强化学习凭 借自身自学习的特性，不断的与环境交 互，获得反馈信号（奖赏值） ，更新该 位置的Q查找表，直到程序迭代结束， 强化学习能够很好的从环境中获得该知 识，得到一个最优策略。图 2 的运行结 果表明算法有很好的效果，表明强