 Artificial Intelligence and Robotics Research 人工智能与机器人研究, 2013, 2, 24-28 http://dx.doi.org/10.12677/airr.2013.21004 Published Online February 2013 (http://www.hanspub.org/journal/airr.html) Multi-Robot Reinforcement Learning Based on LCS and LS-SVM* Jie Shao1,2, Lijuan Du3, Haixia Lin1 1Department of Information Engineering, Zhengzhou Chenggong University of Finance and Economics, Zhengzhou 2School of Computer Science, Nanjing University of Science and Technology, Nanjing 3School of Information and Electonic, Shangqiu Institute of Technology, Shangqiu Email: sj012328@163.com Received: Jan. 5th, 2013; revised: Jan. 25th, 2013; accepted: Feb. 4th, 2013 Abstract: This paper presents a multi-robot reinforcement learning method combination LCS and LS-SVM, the optimal learning strategy LS-SVM obtained as an initial rule set of LCS. LCS interact with the environment, which can quickly find the guiding rules for multi-robot reinforcement learning, provide real-time, dynamic feedback, so that multi-robot autonomously learn the optimal strategy of mutual cooperation. Algorithm analysis and simulation show that a large space for multi-robot learning, the learning speed converges slowly, uncertainties and other learning problems can get a great improvement. Keywords: Learning Classifier System; LS-SVM; Reinforcement Learning; Multi-Robot 基于 LCS 和LS-SVM 的多机器人强化学习* 邵 杰1,2，杜丽娟 3，林海霞 1 1郑州成功财经学院信息工程系，郑州 2南京理工大学计算机科学与技术学院，南京 3商丘工学院信息与电子学院，商丘 Email: sj012328@163.com 收稿日期：2013 年1月5日；修回日期：2013年1月25 日；录用日期：2013 年2月4日 摘 要：本文提出了一种LCS 和LS-SVM相结合的多机器人强化学习方法，LS-SVM 获得的最优学习策略作为 LCS 的初始规则集。LCS通过与环境的交互，能更快发现指导多机器人强化学习的规则，为强化学习系统的动 作选择提供实时、动态的反馈，使多机器人自主地学习到相互协作的最优策略。算法的分析和仿真表明多机器 人学习空间大、学习速度收敛慢、学习效果不确定等问题得到很大的改善。 关键词：学习分类器；协同最小二乘支持向量机；强化学习；多机器人 1. 引言 机器人强化学习问题自提出至今已有众多学者 做了多年的深入研究并产生了大量研究成果[1-4]。Q学 习方法作为一典型的强化学习方法，且不需要建立环 境和任务的精确数学模型，已被广泛地应用于机器人 领域[5]。但在多机器人的学习过程中，经常出现由于 学习空间大、造成学习速度慢、学习效果不确定等问 题[6]。 基于上述分析，本文提出了将 LCS 和LS-SVM 结合用于解决多机器人的强化学习问题。LS-SVM 获 得的最优学习策略作为LCS 的初始规则集。LCS 通过 与环境的交互，可以发现一组用于指导机器人学习的 规则，为 LCS 系统的动作选择提供实时、动态的反馈， 使机器人自主地学习到最优路径规划策略。 *基金项目：河南省教育厅重点资助项目(12B520047)。 Copyright © 2013 Hanspub 24  基于 LCS和LS-SVM的多机器人强化学习 2. 相关技术原理 2.1. 基于学习分类器的多机器人强化学习模型 多机器人强化学习的任务是利用环境回报来学 习针对某个环境的最优策略。其原理是通过对感知的 环境状态采取各种试探动作，获得此种试探动作对此 种环境状态的回报，并能不断调整学习策略以获得较 大的回报，同时反馈给其它机器人，最终获得最好协 作的强化学习策略。 权值调整：Q学习是著名的强化学习之一，该算 法无需任何数学模型，Q值和最优策略的算法更新如 下： Ste p1 ：LCS 系统观察当前状态 t s ，按一定的学习 策略选取学习规则 ； t a Ste p2 ：LCS 从环境中获得即时回报 ； r Ste p3：LCS 系统状态 t s 由转换为 1t s ，更新 Q值。 11 111 , ,max, ttttt ttttt tttt QQsaQ QsarQs aQsa , (1) 11 π,argmax, t tt tt aA s aQ sa 1 1 (2) 其中是学习率， 是折扣系数。 0 0 2.2. 基于最小二乘支持向量机的 Q学习 典型强化学习系统的映射关系包括：状态空间到 动作空间的映射 、状态空间到回报函数的映 射、 (状态，动作)对到值函数的映射 以及(状态，动作)对到转移函数的映射 。王 雪松 等[7]提出了协同最小二乘支持向 量机的 学习算法。该学习系统由一个最小二乘支持 向量回归机(Least squares support vector regression machine, LS-SVRM)和一个最小二乘支持向量分类机 (Least squares support vector classification machine, LS-SVCM)，分别采用 LS-SVRM和LS-SVCM 实现对 和S映射的学习估计。 SA A Sr SA Q SA P Q SA Q 协同最小二乘支持向量机的 学习过程如下[7]： Q Ste p1 ：在环境的初始状态 t s 下，LCS系统直接选 择执行由LS-SVCM 给出的初始动作 ，并依据环境 反馈信号 ，更新此时状态下的。 t a t rt Q Step2 ：与 LCS 系统的 t Q , tt s a组合后形成 LS-SVRM 训练样本集合 S1，对 LS-SVRM模型进行 在线训练； , tt s a则送入 LS-SVCM 的训练样本集 S2， 对其进行在线训练。 Ste p3 ：在 ,, tt t s aQ 和 , tt s a加入样本集S1 和 S2 时，需要对样本进行有效性判断，当实际动作执行 前后系统的变化满足下列条件⑶时， ,, tt t s aQ加入 S1，满足条件⑷时， t , t s a加入集合S2。 1tt ss (3) 1td td s sss (2) 其中， 为状态阈值， d s 表示目标状态。 Step4：当 LS-SVRM 给出的动作选择与LS-SVCM 给出的动作相同时，此时 LS-SVCM 失去作用， LS-SVRM 需对 Q值进行在线估计，学习系统根据得 到的数据 ,, tt t s aQ ，依据动作被选择的概率 ， 及时对 LS-SVRM 模型作出调整，重复上述 Step1 、 Step2、Step3 过程，直至学习到准确的最优学习策略。 t a p , exp , exp tt t tt t at Qsa T pa asQsa T 1 (5) 其中： 为温度系数，控制动作选择的随机程度， 一般在学习初期选择较高的温度，在学习的过程中逐 渐降低温度，以保证较好的学习效果。 0 t T 0max 1min min tt TT TT TT (6) 其中： 0 为退火因子， 和为设定的最 大和最小温度。 max Tmin T 3. 基于学习分类器和最小二乘支持向量机 的Q学习 LCS[8,9]是一个集成强化学习和遗传算法的新型 进化算法，其主要功能是如何通过信用分配和基于遗 传算法的规则发现机制对环境不断学习，不断产生出 新的学习规则。LCS 系统主要由规则与消息系统、基 于信用分配系统的强化学习和基于遗传算法(GA) 的 规则发现系统三部分组成。 规则及消息系统可用IF<Condition>THEN <ACTION>，strength 表示的特殊产生式，直接与外部 Copyright © 2013 Hanspub 25  基于 LCS和LS-SVM的多机器人强化学习 环境发生作用。信用分配系统用于调整现有LCS 的学 习规则强度，并对分配算法进行更新，同时产生三种 LCS 学习规则：匹配规则集中未中标的 LCS 学习规 则、匹配规则集中竞标获胜的LCS 学习规则、未匹配 的LCS 学习规则。 三种 LCS 学习规则强度的信用分配算法如下： ii Bt Stf i 1 (7) 其中 0 ，投标风险系数。 是当前学习规则 的权值强度。 为规则参与投标的投标值。 i St i Bt i f 表 示规则参与投标的力度，01 i f 。 i f lL (8) 其中 为规则条件部分中非“#”的 位数，为规则条 件部分的长度， 。 l1 L 16L life bid 11 iii StTaxStRtTaxBt i (9) life Tax 为规则的生存税，防止其权值人为地增长。 b id Tax 为规则需支付的投标税，用于调节规则的权值 强度。 3.1. 学习规则编码 机器人的学习策略规由三元组0,1, #的22 位字 符位串组成的 , tt s a数据，前 16位是学习规则的条 件部分，后 6位是学习规则的动作部分。机器人传感 器的探测区域为一定偏转度的扇形区域，机器人共有 16 个声纳传感器，可感知每一个扇形区域中障碍物和 机器人分布情况。学习规则编码系统用 6位二进制代 码表示机器人动作，其中 4位代码表示转向角，1位 代码控制速度快慢，1位代码表示前进或后退。 学习策略规则编码描述如下： Condition::0,1,# Action ::0,1 l m 环境信息的编码格式为： Condition::0,1 k 其中 分别为规则的条件和动作部分的长度，这里 。 ,lm 16,lm6, 16k 3.2. 学习优化模型 本文的强化学习采取-Greedy 探索策略，无限范 围衰减模型，基于一定的衰减因子 进行几 何衰减，多机器人系统最优化的期望奖励值为： 0 1 0 tt t r (10) 其中代表将来的第 t步接收到的奖励。 t r 3.3. 适应度函数 遗传算法是 LCS 内嵌的集成算法，在 LCS 系统 的每一次工作周期中，如果LCS 受到了奖励或惩罚， 权值分配系统都会相应调整匹配规则集中学习规则 的强度，而权值强度则作为内嵌遗传算法的适应度函 数来产生新的学习规则。 在不考虑环境其它因素的情况下，基于LCS 和 LS-SVM 的多机器人强化学习的适应度函数为： i fS 1t (11) 3.4. 遗传算子策略的改进 LCS 系统在进化过程中，将权值最大的学习策略 规则直接传递，能有效防止学习“早熟收敛”和“搜 索迟钝”，同时引入冲突消解功能的竞争择优交叉操 作，加快LCS 系统学习的收敛速度，为滤除相似的个 体，减小学习空间，采取学习策略规则合并的策略， 并对遗传算法的交叉算子进行了如下改进： Step1：在 LCS 的匹配规则集中选定两个父类分 类器 11 1 112 ,,, pp p l paa a , ii i ii pp aa lu 和 其 中p i a 2 p a22 212 ,,, pp l paa， 。 Step2：设定一随机值 0, 0.5 。 Step3：计算父代分类器的最低下限 12 min min , ii pp iaa cl max i cmi i c lu和最高上限 值，以及和 的距离： 12 ma i p ia xmax , i p a cu max min ii n I cc 1,1 1,1 and1,1 and1,1 。 Step4：产生新分类器 和的上限和下限值 1 o2 o 1 1 2 2 min min min min rand rand 1r 1r i i i i o a o a o a o a lc I uc I lc I ucI 其中函数 rand 1,1的值为 1或−1，当 的值较小 时，产生的子代分类器与父代分类器很相似，适用于 机器人局部搜索；当 的值较大时，产生的子代分类 Copyright © 2013 Hanspub 26  基于 LCS和LS-SVM的多机器人强化学习 器与父代分类器差异较大，适用于机器人对未知领域 环境的探索。 3.5. 基于 LCS 和LS-SVM 强化学习策略描述 Step1：最小二乘支持向量机的 Q学习产生的最优 学习策略作为LCS 的初始规则集，并随机执行其中的 学习策略。 Step2：调用拍卖模块判断当前学习策略的条件部 分与消息列表中消息是否匹配，匹配的学习策略规则 送入匹配规则集。 Step3：从匹配规则集中选择较优的学习策略规则 送往效应器并产生相应动作， LCS 系统依据环境反馈 值来判断学习效果。 Step4：重复 Step2~Step3 过程，直到匹配规则集 为空。 Step5：启动进化(规则发现)系统构造新的学习策 略规则。 经规则合并后，发送到LCS 公共规则集中，供其 它机器人LCS 产生新学习规则时共享。 Step6 ：如果机器人未达到学习效果，则返回 Step2。 4. 实验及仿真结果 我们以多机器人路径规划效果来验证本文提出 的混合学习策略。图 1内O1-O3 机器人均是用直径为 0.3 m的圆柱体表示，各机器人根据自己的路况，可 进行 0˚、左曲线 5˚、左曲线 10˚、左曲线 15˚、右曲线 5˚、右曲线 10˚、右曲线 15˚或停止当前动作的八种学 习策略。活动区域内圆形和方形图形均为静态障碍 物。图 2为基于LCS 学习的多机器人收敛学习曲线； 图3是基于 LCS和LS-SVM 混合方法的多机器人的 学习收敛曲线。与图 2相比图 3明显地提高了学习效 率和收敛速度。 一般情况下，一个强化学习算法的性能需要两方 面的判定，一个是算法的收敛性，一个是算法的收敛 速度。从图 4、图 5中可以看出，系统经过若干次数 的学习后，算法出现收敛的趋势，在学习初始过程， 的震荡幅度较大。经过若干次数的学习之后， 振荡幅度就很小了，我们可以认为已经近似地收 敛了。图 4为基于传统LCS 强化学习的收敛情况，体 现了传统强化学习时间较长、收敛速度慢的缺陷；图 5为基于梯度的 LCS 和LS-SVM 的强化学习情况，不 管是机器人个体强化学习或是团队学习，均能在较短 的时间内收到理想的学习效果。 Rt Rt Figure 1. The evolution algebra and fitness curve based on LCS 图1. 进化代数与适应度曲线图(LCS 学习) 00.2 0.40.6 0.811.2 1.41.6 1.8 2 -0.2 0 0. 2 0. 4 0. 6 0. 8 1 1 200 Figure 2. Reinforc ement learning convergence based on the traditional LCS 图2. 基于传统的 LCS 强化学习收敛情况 00.2 0.4 0.6 0.8 11.2 1.4 1.6 1.8 2 -0. 2 0 0. 2 0. 4 0. 6 0. 8 1 1 200 Figure 3. Algebra and fitness curves based on LCS and LS-SVM 图3. 化代数与适应度曲线图(LCS 和LS-SVM) Copyright © 2013 Hanspub 27  基于 LCS和LS-SVM的多机器人强化学习 Copyright © 2013 Hanspub 28 0100 200 300400500 600700 800 9001000 -4 -3 -2 -1 0 1 2 3 4 1: 10 R(t) Figure 4. Reinforc ement learning convergence based on the traditional LCS 图4. 基于传统的 LCS 强化学习收敛情况 0100200300400 500 600700800900 1000 -4 -3 -2 -1 0 1 2 3 4 1:10 R(t) Figure 5. Reinforcement learning convergence based on LCS and LS-SVM 图5. 基于LCS 和LS-SVM的强化学习收敛情况 5. 结束语 本文提出了 LCS 系统和LS-SVM 算法结合的混 合算法，解决多机器人在复杂环境下的强化学习问 题。LCS 内嵌的遗传算法采用了特有的遗传算子策 略，加强了LCS 系统的强化学习效果，由学习空间大 造成的学习速度慢、学习效果不确定等问题得到很大 的改善。仿真实验结果也表明将LCS 用于多机器人的 强化学习是有效的。 参考文献 (References) [1] J. shao, J. Y. Yang. Multi-robot reinforcement learning based on learning classifier system with gradient descent methods. Jour- nal of Computational Information Systems, 2010, 6(8): 2449- 2455. [2] 高阳, 陈世福, 陆鑫. 强化学习研究综述[J]. 自动化学报, 2004, 30(1): 86-100. [3] 沈晶, 程晓北, 刘海波等. 动态环境中的强化学习[J]. 控制理 论与应用, 2008, 25(1): 71-74. [4] 邵杰, 杨静宇, 万鸣华, 黄传波. 基于学习分类器的多机器人 路径规划收敛性研究[J]. 计算机研究与发展, 2010, 47(5): 948-955. [5] 焦殿科, 石川. 共享经验的多主体强化学习研究[J]. 计算机 工程, 2008, 34(11): 219-221. [6] 陈卫东, 席玉庚, 顾东雷. 自主机器人的强化学习进展[J]. 机 器人, 2001, 23(4): 379-384. [7] 王雪松, 田西兰, 程玉虎, 易建强. 基于协同最小二 乘支持向 量机的 Q学习[J]. 自动化学报, 2009, 35(2): 215-219. [8] X.-L. Wang, Z.-J. Yin, Y.-B. Lv and S.-F. Li. Operating rules classification system of water supply reservoir based on learning classifier system. Expert Systems with Applications, 2008, 36(3): 5654-5659. [9] P. Musilek. Enhanced learning classifier system for robot navi- gation. International Conference on Intelligent Robots and Sys- tems, Edmonton, 2-6 August 2005: 3390-3395. |