计算机研究与发展
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999年 第36卷 第12期 Vol.36 No.12 1999



Q-学习及其在智能机器人局部路径
规划中的应用研究
张汝波　杨广铭　顾国昌　张国印
摘　要　强化学习一词来自于行为心理学，这门学科把行为学习看成反复试验的过程，从而把环境状态映射成相应的动作.在设计智能机器人过程中，如何来实现行为主义的思想、在与环境的交互中学习行为动作？文中把机器人在未知环境中为躲避障碍所采取的动作看作一种行为，采用强化学习方法来实现智能机器人避碰行为学习.Q-学习算法是类似于动态规划的一种强化学习方法，文中在介绍了Q-学习的基本算法之后，提出了具有竞争思想和自组织机制的Q-学习神经网络学习算法；然后研究了该算法在智能机器人局部路径规划中的应用，在文中的最后给出了详细的仿真结果.
关键词　Q-学习，神经网络，智能机器人，局部路径规划
中图法分类号　TP242.6
Q-LEARNING AND ITS APPLICATION IN LOCAL PATH
PLANNING OF INTELLIGENT ROBOTS
ZHANG Ru-Bo, YANG Guang-Ming, GU Guo-Chang, and ZHANG Guo-Yin
(Department of Computer and Information Science,
Harbin Engineering University, Harbin 150001)
Abstract　The concept of reinforcement learning comes from behavior psychology that takes behavior learning as trial and error, by which the states of environment are mapped into corresponding actions. There's a question of how the behaviorism can be used to learn the actions in interaction with the environment in designing intelligent robots. In this paper, the actions that a robot takes to avoid obstacles are taken as one class of behaviors and the reinforcement learning is used to realize behavior learning of obstacle avoidance. Q-learning is one kind of reinforcement learning method that is similar to dynamic programming. After basic ideas of Q-learning are introduced, a neural network learning algorithm of Q-learning with concepts of competition and self-organization is presented. Its application in local path planning of intelligent robots is also introduced. Finally, the detailed simulation results are presented.
Key words　Q-learning, neural network, intelligent robot, local path plan
1　引　　言
　　在连接主义学习中，学习算法基本上可以分为3种类型，非监督学习(unsupervised learning)、监督学习(supervised learning)和强化学习(reinforcement learning).
　　非监督学习规则在生理学上就是Pavlov的条件反射原理，当用一个毫无意义的刺激信号（如铃的响声）同时伴有另一个刺激信号（如食物）反复加给动物的时候，经过一段时间的训练后，动物就会建立一种联想.当再接受到刺激信号时，动物就会产生条件反射.这种类型的学习完全是开环的，在神经网络学习中，称之为相关规则，即神经网络中的Hebb学习规则.
　　监督学习规则是一种反馈学习规则，当输入信号作用于系统后，观察其输出，由教师提供理想的输出信号，所产生的误差信号反馈给系统来指导学习，在神经网络学习中，称之为最小误差学习规则或称之为δ规则［1］.
　　观察生物（特别是人）为适应环境的学习过程可以发现它有两个特点，一是人从来不是静止地被动等待而是主动对环境作试探，二是从环境对试探动作通过的反馈信号看，多数情况下是评价性（奖或罚）的，而不是像监督学习那样给出正确答案.生物在行动－－评价的环境中获得知识，改进行动方案以适应环境达到预想的目的.具有上述特点的学习就是强化学习（或称再励学习，评价学习，简记为RL）［2］.
　　Q-学习算法是由Watkins在1989年提出的类似于动态规划算法的一种强化学习方法.它提供智能系统在马尔科夫环境中利用经历的动作序列选择最优动作的一种学习能力，并且不需要建立环境模型.Q-学习算法实际是MDP（Markov decision processes）的一种变化形式.Watkins采用lookup表来表示输入状态，证明了Q-学习的收敛性［3］.Szepesvári在一定条件下证明了Q-学习的收敛速度［4］.Williams等人采用Q-学习算法对倒摆系统进行实验研究，并与Anderson等人采用AHC方法进行了比较分析［5］.由于自身的特性，强化学习被广泛地应用在智能控制领域，许多学者都取得了令人满意的成果.Beom利用模糊逻辑和强化学习实现了陆上移动机器人导航系统，机器人通过学习能够在未知的环境中运动，可以完成避碰和到达指定目标点两种行为［6］. Winfried采用强化学习来使昆虫机器人学会6条腿的协调动作［7］.Carnegie Mellon大学的Sebastian采用神经网络结合强化学习方式使机器人通过学习能够到达室内环境中的目标［1］.
　　本文在介绍了Q-学习的基本算法之后，提出了具有竞争思想和自组织机制的Q-学习神经网络学习算法；然后研究了该算法在智能机器人局部路径规划中的应用情况，即把机器人在未知环境中为躲避障碍所采取的动作看作一种行为，采用Q-学习机制进行机器人的避碰行为学习，在文中的最后给出了详细的仿真结果.
2　Q-学习的基本算法［3］
　　设环境是一个有限状态的离散马尔科夫过程，智能系统每步可在有限动作集合中选取某一动作，环境接受该动作后状态发生转移，同时给出评价r.例如，在时刻t选择动作at，环境由状态st转移到st+1，给出评价rt，rt及st+1的概率分布取决于at及st.环境状态以如下概率变化到st+1
prob［s=ss+1/st,at］=P［st,at,st+1］
(1)
智能系统面临的任务是决定一个最优策略，使得总的折扣奖励信号期望值最大.在策略π的作用下，状态s的值为

(2)
由于智能系统希望立即收到强化信号r(π(x))，然后以概率移动到一个赋值为Vπ(st+1)的一个状态.动态规划理论保证至少有一个策略π使得

(3)
　　Q-学习面临的任务是在初始条件未知的情况下来决定π.Watkins把Q-学习看成一个增量式动态规划，用一步方式来决定策略.希望找到一个策略（动作序列）使评价总和得到最大.如果环境模型（即状态转移概率及评价模型）已知或由观测估计出来，则上述问题可用动态规划（DP）解决，Q-学习的思想的是不去估计环境模型，而是直接优化一个可迭代计算的Q函数，Watkins定义此Q函数为在状态st时执行动作at，且此后按最优动作序列执行时的折扣累计强化值，即

(4)
　　在Q-学习中，智能系统的经历包括一系列不同的阶段，在每个阶段，其学习步骤如下：
　　(1)观察现在的状态st;
　　(2)选择并执行一个动作at;
　　(3)观察下一个状态st+1;
　　(4)收到一个立即强化信号rt;
　　(5)调整Q值：

(5)
其中:

(6)
　　在初始阶段学习中，Q可能是不准确地反映了它们所定义的策略，初始值Q0(s,a)对于所有的状态和动作假定是给出的.Watkins证明了Q-学习在一定条件下的收敛性.收敛的条件是：
　　(1)环境是马尔科夫过程；
　　(2)用lookup表来表示Q函数；
　　(3)每个状态-动作对，可无限次地重复试验；
　　(4)学习速率的正确选择.
　　定理1.给定有界强化信号|rt|≤R，学习率0≤αt≤1及

(7)
则：当t→∞时，Qt(s,a)以概率1收敛于最优Q(s,a).
　　Q函数的实现方法主要有两种方式：一种是采用神经网络方法；另一种是采用lookup表格方法；采用lookup表格方法，也就是利用表格来表示Q函数，设Q（s,a）（s∈S，a∈A）为一lookup表格，S，A为有限集合.Q(s,a)代表s状态下执行动作a的Q值.表的大小等于S×A的笛卡尔乘积中元素的个数.当环境的状态集合S、智能系统可能的动作集合A较大时，Q(s,a)需要占用大量的内存空间，而且也不具有泛化能力.
　　采用神经网络实现Q-学习时，网络的输出对应每个动作的Q值，网络的输入对应描述环境的状态.采用神经网络实现Q-学习后，可以克服上述存在的问题.
3　Q-学习的神经网络实现
3.1　Q-学习系统的结构
　　Q-学习系统结构不同于AHC算法的结构，采用Q-学习的智能系统只有一个决策单元，同时起到动作的评价及选择作用，其结构如图1所示.

图1　Q-学习系统结构

　　如果一个智能系统要想获取较高的强化值，在每个状态，智能系统不得不选择具有最高Q值的动作，特别是在学习的初始阶段，对状态动作的经验了解的比较少，Q值不能准确地表示正确的强化值.通常，选择最高Q值的动作导致了智能系统总是沿着相同的路径而不可能探索到较好值.因此，基于上述情况，智能系统必须随机地选择动作，根据当前的Q值也许选择的动作不是最优的.有许多方法来随机地选择动作.如Boltzmann分布方法：

(8)
　　其中T为温度值；T的大小代表了随机性的大小.T越大，随机性越大.在学习的初试阶段，T取较高的值，因为此时学习的经验较小，需要增加搜索能力；在学习的过程中，逐渐降低温度，保证以前的学习效果不被破坏.
　　Q-学习可用各种神经网络来实现，每一个网络的输出对应于一个动作的Q值，即：Q(s,ai).用神经网络实现Q-学习的关键是学习算法的确定.根据Q函数的定义：

(9)
只有在得到最优策略的前提下上式才成立.在学习阶段上式两边不成立，误差信号为

(10)
其中，Q(st+1,at)表示下一状态所对应的Q值，其中ΔQ通过调整网络的权值调整使误差尽可能小一些.
3.2　综合神经网络的Q-学习算法
　　这里我们结合竞争神经网络和自组织映射网络的思想实现Q-学习算法.网络的结构如图2所示：

图2　综合神经网络
　　网络由3层组成，即输入层、中间层、输出层(竞争组织层).其特点主要体现在竞争组织层上.网络的输出节点对应一系列的动作和状态的评价值Q(S,aj).这里对动作按一定的顺序排列，即ai与ai-1是相近的动作.其工作原理是这样的：在状态St={s1,s2,…,sn}输入时，网络正向传播产生相应的输出Q(S,aj)，随机动作选择单元根据Q(S,aj)值随机选取动作.假设动作ai被选中，在Q-学习中，

(11)
其中，根据竞争思想令Qmax=1.
　　另外，动作ai被选中后，其相邻的动作也产生一定的权值的调整.基于自组织映射的思想，对同一种输入应有多个动作反应，只不过反应的程度不同而已，这里我们采用正态分布的形式，来确认相邻动作的反应强度：

(12)
　　若网络输出节点对应一系列的相反动作，如a1与am、a2与am-1等都是相互对立的动作，则随机单元选取一动作ai后，其误差为ΔQmax，而相反的动作am-i的误差为-ΔQmax.am-i相邻的动作对应按下式修改：

(13)
　　这样，每次学习时就产生多个节点的误差值.网络的目标函数是

(14)
　　利用误差反向传播算法来进行网络的权值调整.
4　Q-学习在智能机器人局部路径规划中的应用研究
4.1　强化值的确定
　　强化信号的作用是对学习系统性能的一种评价，主要用于改善系统的性能.强化信号根据控制任务的不同，其形式有所不同.在机器人避碰行为学习中，其目的是使机器人离障碍物越远越好.当机器人与障碍物相碰时，应该得到惩罚.在我们研究的机器人中，共配置了6个声纳用于避碰，如图3所示.应该综合考虑这6个声纳的距离信息，有的探测距离较远，有的探测距离较近.

图3　机器人与障碍物的关系
　　这里我们采用势场法来确定外部强化值.首先计算机器人所受斥力的合力：

(15)
其中ki为比例系数；ρi为第i声纳的探测距离；ρ0为安全距离，ρmi为声纳的最大探测距离；θi为声纳i与环境坐标系的夹角.体现了机器人距障碍物的综合相对位置关系.较大则表明机器人总体上离障碍物较近，反之较远.相邻时刻的受力之差为

(16)
表明机器人运动的趋势.ΔF(t)＜0表明机器人远离障碍物，应该得到奖励，ΔF(t)＞0表示机器人走近障碍物，因该得到惩罚.故强化信号r(t)为
r(t)=g［ΔF(t)］
(17)
g(x)函数取为

(18)
在实验中，ki={2,2,2,2,1,1};ρ0［i］={1.5,1.5,1.5,1.5,1.0,1.0};ρm［i］={4.5,4.5,4.5,4.5,1.5,1.5}
另外，当机器人与障碍物相碰时r(t)=-1.
4.2　输入、输出的表示形式
　　在我们研究的机器人系统中，避碰的主要传感器是避碰声纳.因此，作为强化学习系统的输入信号就是这6个声纳传感器的距离信息，对于声纳信息，我们划分4个等级，即Danger，Near，Middle，Far，对于前方向声纳划分如下：

(19)
对于侧向声纳：

(20)
把机器人的旋转角度划分为7个离散动作，即0°,±10°,±20°,±30°.机器人根据传感器的信息，经过学习后选择合适动作.令
a1=-30°,a2=-20°,a3=-10°,a4=0°,a5=10°,a6=20°,a7=30°
其中：a1与a7，a2与a6，a3与a5互为对立动作.为了使机器人尽快学习避碰能力，让机器人在比较复杂的环境中以漫游方式运动，当机器人与障碍物相碰时，回到起点重新开始学习，即在上次学习结果的基础上重新进行权值的调整.我们用机器人漫游所经过的路径来衡量学习效果的好坏，机器人所走的路径越长表明机器人避碰能力越强.
4.3　基于Q-学习的机器人避碰实验结果
　　基于Q-学习的机器人避碰动作学习系统采用3层神经网络来实现.网络的输入为6个节点，输出为7个节点，中间层选择16个节点.将动作进行有序的排列，而转角动作以零为中心，均为互相对称的动作.每次学习时，随机动作选择器根据Borlzmann分布随机选取一个动作.为了方便更清晰的观察机器人的学习效果，我们采用了对多次试验的统计方法来描述曲线，其实验曲线如图4所示.

图4　实验结果
　　综合Q-学习算法（实线）的学习速度明显提高，且平均路径长度远远大于标准的Q-学习算法（虚线）.从曲线上可以看出，采用标准的神经网络Q-学习方法，其学习的时间比较长，而且没有达到稳定的效果.图5为该算法在学习初试的学习轨迹.其轨迹比较杂乱，不平滑，好像无头苍蝇到处乱撞.图6为经过一段时间学习后的轨迹，其轨迹比较平滑.

图5　机器人学习初始阶段的运动轨迹

图6　机器人经过一段时间学习后的运动轨迹
　　为了进一步检验学习效果，让训练好的机器人在另一环境中漫游（不再学习），图7为漫游的结果.考虑到局部路径规划的问题，让机器人在杂乱的环境中到达指定的目标点，其仿真的结果如图8所示.

图7　机器人在迷宫中运动的仿真结果

图8　基于Q-学习的局部路径规划结果
　　从仿真结果可以看出，具有Q-学习机制的机器人经过学习后可以在比较复杂的环境中运动，同时可以实现局部路径规划任务.
5　结　　论
　　本文提出了具有竞争思想和自组织机制的Q-学习神经网络学习算法，与标准的Q-学习方法相比，学习速度大大提高.采用该算法的机器人通过学习后具有较强的避碰能力，从而提高了机器人对环境的适应能力.该算法同样可以应用到其它的智能控制系统中.
作者简介：张汝波，男，1963年3月生，副教授，博士，主要研究方向为机器学习、智能控制及
　　　　　智能机器人.
　　　　　杨广铭，男，1974年3月生，硕士研究生，主要研究方向为机器学习及智能机器人.
　　　　　顾国昌，男，1946年4月生，博士生导师，主要研究方向为智能机器人、机器人体系
　　　　　结构、行动决策和控制技术.
　　　　　张国印，男，1962年9月生，博士，副教授，主要研究方向为智能控制及智能机器人.
作者单位：哈尔滨工程大学计算机系　哈尔滨　150001
参考文献
　1　Sebastian T, Mitchell T M. Lifelong robot learning. Robotics and Autonomous System, 1995, 15: 25～46
　2　阎平凡. 再励学习——原理、算法及其在智能控制中的应用. 信息与控制, 1996, 25(1): 28～34
　　（Yan Pingfan. Reinforcement learning——principle, algorithm and its application in intelligent control. Information and Control(in Chinese), 1996, 25(1): 28～34）
　3　Watkins J C H, Dayan P. Q-learning. Machine Learning，1992, 8: 279～292
　4　Szepesvári C. The asymptotic convergence-rate of Q-learning. In: Proceedings of Neural Information Processing Systems. Cambridge, MA: MIT Press, 1997. 1064～1070
　5　Williams R J. Simple statistical gradient-following algorithms for connectionist. Machine Learning, 1992, 8： 229～256
　6　Beom H B. A sensor-based navigation for a mobile robot using fuzzy logic and reinforcement learning. IEEE Trans on SMC, 1995, 25(3): 464～477
　7　Winfried I, Karsten B. A learning architecture based on adaptive control of the walking machine LAURON. Robotics and Autonomous System，1995, 15： 323～334
原稿收到日期：1999-03-10；修改稿收到日期：1999-08-26
