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

马朋委 潘地林 汪立冬

摘要：为解决随机环境下的智能体的路径规划问题，借助强化学习算法的自学习和和自适应的特点，引入Q学习算法处理随机环境下的路径规划问题。实验结果表明，该算法在解决随机环境中路径规划的有效性。

关键词：强化学习；Q_learning；路径规划；随机环境

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）31-0148-02

Reinforcement Learning based Agent Path Planning in Random 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 概述

路径规划[1]是一个重要的研究课题，在机器人导航和游戏智能体中都有着很大的研究价值。在确定环境下（比如只有静止障碍物的寻路过程）可以很有效地解决此类问题。但在随机环境下，这种随机性就破坏了A*算法的要求。随机环境相对于确定环境（固定顺序的一系列操作一定会得到相同的结果）而言的，因为每一步的操作的结果都是随机的，即使相同的操作序列也会得到不同的结果。此时如果强行应用的话，最好的情形也需要做很多修改工作，最差的情形是A*会给出错误的答案。在此我们引入一个解决随机条件下的多步决策问题，强化学习（Reforcement Learning）。

强化学习是一种在线的、无导师的机器学习方法，主要表现在由环境提供的强化信号对智能体所产生动作的好坏作一种评价，而不是告诉智能体如何产生正确的动作，智能体依靠自身与环境的交互进行学习，在行动和评价的环境中获得知识，对行动方案进行改进适应环境，已达到获得最优动作。20世纪90年代，强化学习通过与运筹学、控制理论的交叉结合，在理论和算法方面取得了突破性的研究成果，奠定了强化学习的理论基础，并在机器人控制领域、优化调度等序贯决策中取得了成功的应用[2]。

2 强化学习

强化学习是一个能够感知环境的自治智能体如何通过学习选择能够达到目标的最优动作，即强化学习的任务就是学习从环境到动作的映射[3]。强化学习的学习过程类似于人，从来不是静止被动地等待，而是主动地对环境试探交互，从环境给予的反馈信号来学习知识，改进行动方案，已达到预期的目的，这也符合强化学习的特征[4]。强化学习大部分都是以马尔科夫决策过程（Markov Decision Process）为基础。马尔科夫决策过程借助四元组来描述。S为环境状态空间，[A]为动作空间，[P]为状态转移概率，[r]为立即回报函数。强化学习的模型如图1：

图1 强化学习框架

在马尔科夫决策过程中，Agent是通过一个决策函数（即策略）来选择动作的，常用π表示策略。在定义了策略后对应状态-动作值函数为[Qπ（s，a）]，[Qπ（s，a）]表示在状态s下根据策略π执行动作a的期望值如式（1）：

[Qπ（s，a）=Eπt=0∞γtrt+1|st=s，at=a] （1）

最优动作值函数的定义为式（2）：

[Qπ（s，a）=maxπQπ（s，a）=s'∈SP（s，a，s'）r+γmaxa'∈AQ*（s'，a'）] （2）

最优策略是使得Agent在每一个状态下均能获得最大值的策略如式（3）：

[π*（s）=arg maxaQ*（s，a）] （3）

其中[arg maxaQ*（s，a）]是状态[S]的一个函数，其值为使[Q*（s，a）]最大的动作[a]。一些强化学习算法已经在理论和应用方面取得了重大的成功[Q]_learning[5]，TD（λ）[6]， SARSA[7]。本文选取[Q]_learning算法，[Q]_learning是一种有效的模型无关强化学习算法。

3 [Q]_learning算法

[Q]_learning算法是Watkins最早于1989提出来的[8]，又称离策略TD学习。它采用[Q（s，a）]状态动作对的值做估计函数。在[Q]学习中智能体维护一个查找表[Q（s，a）]，其中[Q]和[S]分别是状态和行为的集合智能体借助时间差分的思想来更新查找表。智能体在每一次学习迭代时都需要考察每一个行为，如果每个状态-动作对被无限频繁的访问，且学习率合适，算发最终会收敛，其收敛性已得到证明。常见的动作选择策略有[ε-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）+α[rt+γmaxaQ（st+1，a）-Q（st，at）]]

[st←st+1]

直到[st]是终止状态

直到所有的[Q（s，a）]收敛

输出最终策略。

[Q]学习算法在强化学习算法中最为基本，实际应用也很广泛。只要在任意的状态智能体尝试一个行为的次数不受限制（即智能体在一个状态不会总是执行相同的行动子集），则不管智能体真正依据的策略是哪个，[Q]学习都学习一个最优的策略。

4 实验结果与分析

为了验证算法的有效性，本文选取一个15X10的迷宫如图2，S为迷宫的开始节点，G为终点，棕色块相当于墙壁或障碍物，灰色块为可行区域，红色块代表陷阱，绿色块为算法的最终的规划路径。

图2

本文选取[ε]为0.2，，折扣率[γ]为0.9，步长[α]为0.1，回报函数r定义如式（5）：

[r=5 终点，随机选取一个点开始-5陷阱-1撞到墙壁或障碍物，待在原地0其他情况] （5）

智能体刚开始从[S]位置出发，目标是终点[G]的位置。执行动作[a]时有一定的概率会向两侧移动（假如0.8概率向右移动时，会有0.1的概率向上移动，0.1的概率向下移动）强化学习凭借自身自学习的特性，不断的与环境交互，获得反馈信号（奖赏值），更新该位置的[Q]查找表，直到程序迭代结束，强化学习能够很好的从环境中获得该知识，得到一个最优策略。图2的运行结果表明算法有很好的效果，表明强化学习的在线学习特点在随机环境中的优势，验证了算法的可行性。

5 结束语

虽然强化学习在随机环境地图规划中能够较好的应用，但它也存在着学习知识较慢，算法需要多次迭代才能收敛，在执行选取动作的策略时也存在着探索与利用的平衡问题。如何加快算法的收敛速度，提升在环境中学习知识的能力，一直是强化学习研究的重点。

参考文献：

[1] 陈卫东，李宝霞，朱奇光.模糊控制在移动机器人路径规划中的应用[J].计算机工程与应用，2009，45（31）：221-223.

[2] 史忠植.智能科学[M].北京：清华大学出版社，2006：30-35.

[3] Mitchell T M.机器学习[M].曾华军，译.北京：机械工业出版社，2008：21-26.

[4] 谭民，王硕，曹志强.多机器人系统[M].北京：清华大学出版社，2005：65-72.

[5] L.P. Kael bling， M.L. Littman， and A.W.Moore，reinforcementlearning：Asurvey[R].Arxivpreprintcs/9605103， pp.237-285，1996.

[6] L.Tang B. AnandD.Cheng，An agent reinforcement learning model based on neural networks[C].Bio-Inspired Computational Intelligence and Applications，pp.117-127，2007.

[7] Jinsong，Leng， LakhmiJain，Colin Fyfe.Convergence Analysis on Approximate Reinforcement Learning[C]，Z.Zhang andSiekmann （Eds）：KSEM 2007，LNAI 4798，pp.85-91.

[8] SUTTON R S， BARTO A G.Reinforcement learning：an introduction [M]. Cambridge： MIT， 1998：150-185.