第3卷第3期 智能系统学报 Vol 3 Na 3 2008年6月 CAA I Transactions on Intelligent Systems Jun 2008 模糊Q学习的足球机器人双层协作模型 曹卫华，徐凌云，吴敏 (中南大学信息科学与工程学院，湖南长沙410083) 摘要：针对传统的足球机器人3层决策模型存在决策不连贯的问题和缺乏适应性与学习能力的缺点，提出了一种 基于模糊Q学习的足球机器人双层协作模型.该模型使协调决策和机器人运动成为2个功能独立的层次，使群体意 图到个体行为的过度变为一个直接的过程，并在协调层通过采用Q学习算法在线学习不同状态下的最优策略，增强 了决策系统的适应性和学习能力.在Q学习中通过把状态繁多的系统状态映射为为数不多的模糊状态，大大减少了 状态空间的大小，避免了传统Q学习在状态空间和动作空间较大的情况下收敛速度慢，甚至不能收敛的缺点，提高 了Q学习算法的收敛速度.最后，通过在足球机器人SmurSotf仿真比赛平台上进行实验，验证了双层协作模型的有 效性. 关键词：足球机器人；双层决策模型，基于行为的控制系统；Q学习 中图分类号：TP18文献标识码：A文章编号：1673-4785(2008)03023405 A double-layer dec ision making model based on fuzzy Q-learnng for robot soccer CAO Wei-hua,XU L ing-yun,WU Min (School of Inomation Science and Engineering.Central South University,Changsha 410083,China) Abstract:W ith the conventional triple-layer decison-making model of soccer obots,decisions are sometmes in- consistent,leading to weaknesses in adap tability and self-leaming ability.A double-layer cooperation model for a robot soccer system based on fuzzyQLeaming is presented to olve these issues Thismodel divides cooperative de- cisions and robot movement into to layers with their own independent functions,so that the transition from group strategy to individual behavior becomes a direct process To enhance the adaptability and self-leaming capabilities of the decision making system,the Q-leaming algorithm was used in the cooperation layer to leam the optmal strat egy for various conditions To speed up the convergence ofQ-leaming and decrease the size of the state space,the numerous system states were mapped to seven fuzzy states in Q-leaming This avoids problems with Q-leaming's sbw converging rate when the size of the state pace is large This model was verified on the SmuroSot Robot Soc- cer Game platfom. Keywords:robot soccer,double-layer decision-making model behavor-based control system;Q-leaming 近年来，对于多智能体的研究已经成为人工智中.足球机器人是一个典型的多智能体系统，在FF 能研究领域的重要方向和热点，其中多智能体协作 RA系列足球机器人系统中一般包括4个子系统： 模型的研究最为瞩目.很多学者提出使用机器学习 视觉子系统、决策子系统通信子系统和机器人车体 的方法来实现多智能体之间的协作和协调，例如遗子系统，它具有比赛环境复杂、难以建立准确数学模 传算法、神经网络和强化学习等 型等特点.其中，决策子系统是整个系统的关键，它 20世纪80年代末，随着分布式人工智能的发 负责接收经视觉子系统处理后的场地信息，通过设 展，多智能体技术逐渐被应用到各种多机器人系统 计的决策算法实现机器人的协作和控制，因此决策 子系统设计的好坏直接关系到整个系统的性能口 收稿日期：2007-11-15 一种广泛使用的方法采用基于专家经验和规划的3 基金项目：湖南省自然科学基金资助项目(06JJ50144). 通讯作者：吴敏.Email min@csu edu cn 层结构模型来设计决策子系统2)3层结构的模型 虽然在逻辑结构上非常清晰，但是存在决策不连贯 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 3期 智 能 系 统 学 报 Vol. 3 №. 3 2008年 6月 CAA I Transactions on Intelligent System s Jun. 2008 模糊 Q学习的足球机器人双层协作模型 曹卫华 ,徐凌云 ,吴 敏 (中南大学 信息科学与工程学院 ,湖南 长沙 410083) 摘 要 :针对传统的足球机器人 3层决策模型存在决策不连贯的问题和缺乏适应性与学习能力的缺点 ,提出了一种 基于模糊 Q学习的足球机器人双层协作模型. 该模型使协调决策和机器人运动成为 2个功能独立的层次 ,使群体意 图到个体行为的过度变为一个直接的过程 ,并在协调层通过采用 Q学习算法在线学习不同状态下的最优策略 ,增强 了决策系统的适应性和学习能力. 在 Q学习中通过把状态繁多的系统状态映射为为数不多的模糊状态 ,大大减少了 状态空间的大小 ,避免了传统 Q学习在状态空间和动作空间较大的情况下收敛速度慢 ,甚至不能收敛的缺点 ,提高 了 Q学习算法的收敛速度. 最后 ,通过在足球机器人 SimuroSot仿真比赛平台上进行实验 ,验证了双层协作模型的有 效性. 关键词 :足球机器人 ;双层决策模型 ;基于行为的控制系统 ; Q学习 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0320234205 A double2layer dec ision2making model based on fuzzy Q2learn ing for robot soccer CAO W ei2hua, XU L ing2yun, WU M in ( School of Information Science and Engineering, Central South University, Changsha 410083, China) Abstract:W ith the conventional trip le2layer decision2making model of soccer robots, decisions are sometimes in2 consistent, leading to weaknesses in adap tability and self2learning ability. A double2layer cooperation model for a robot soccer system based on fuzzyQ2Learning is p resented to solve these issues. Thismodel divides cooperative de2 cisions and robot movement into two layers with their own independent functions, so that the transition from group strategy to individual behavior becomes a direct p rocess. To enhance the adap tability and self2learning capabilities of the decision2making system, the Q2learning algorithm was used in the cooperation layer to learn the op timal strat2 egy for various conditions. To speed up the convergence of Q2learning and decrease the size of the state space, the numerous system states were mapped to seven fuzzy states in Q2learning. This avoids p roblem s with Q2learning’s slow converging rate when the size of the state space is large. Thismodel was verified on the SimuroSot Robot Soc2 cer Game p latform. Keywords: robot soccer; double2layer decision2making model; behavior2based control system; Q2learning 近年来 ,对于多智能体的研究已经成为人工智 能研究领域的重要方向和热点 ,其中多智能体协作 模型的研究最为瞩目. 很多学者提出使用机器学习 的方法来实现多智能体之间的协作和协调 ,例如遗 传算法、神经网络和强化学习等 通讯作者 :吴 敏. E2 收稿日期 : 2007211215. 基金项目 :湖南省自然科学基金资助项目 ( 06JJ50144) . mail: m in@ csu. edu. cn. . 20世纪 80年代末 ,随着分布式人工智能的发 展 ,多智能体技术逐渐被应用到各种多机器人系统 中. 足球机器人是一个典型的多智能体系统 ,在 FI2 RA系列足球机器人系统中一般包括 4个子系统 : 视觉子系统、决策子系统、通信子系统和机器人车体 子系统 ,它具有比赛环境复杂、难以建立准确数学模 型等特点. 其中 ,决策子系统是整个系统的关键 ,它 负责接收经视觉子系统处理后的场地信息 ,通过设 计的决策算法实现机器人的协作和控制 ,因此决策 子系统设计的好坏直接关系到整个系统的性能 [ 1 ] . 一种广泛使用的方法采用基于专家经验和规划的 3 层结构模型来设计决策子系统 [ 223 ] . 3层结构的模型 虽然在逻辑结构上非常清晰 ,但是存在决策不连贯
第3期 曹卫华，等：一种基于模糊Q学习的足球机器人双层协作模型 ·235· 的缺点文献[5提出了一种基于行为的双层决 体1.本文主要针对强化学习在协调层中研究，以 策模型，能够解决3层结构的缺点，但它也是采用基 提高双层决策模型的适应性和自学习能力 于专家经验的方法来实现机器人间的协作，因此决 Q学习是由W atkins于1989年提出来的一种模 策系统缺乏适应性和自学习能力 型无关的强化学习算法6).单步Q学习算法的基 通过在协调层中引入Q学习算法，针对Q学习 本形式如式(1)所示： 算法在收敛性方面的不足，提出一种基于状态空间 0(s,a)=0(,a,)+a(i+1+ 模糊化Q学习的足球机器人双层决策模型，在一定 Y maxo(&+,a)-Q(s,a,).(1) 程度上提高了决策系统的适应性和自学习能力： 式中：Y为折扣率，a为学习率或学习步长.Agent 1双层决策模型结构与模糊Q学习 在s状态下，根据策略选择函数确定动作a,得到 奖赏值和训练例(s,a,号+1，+1：然后根据此奖赏 决策子系统通过视觉子系统获得比赛场地上的 值，依据式(1)修改Q值.当Agenti访问到目标状 各种信息，通过分析这些信息做出决策，并最终产生 态，算法终止一次迭代循环.研究表明，当ā满足一 各个机器人的左右轮速发送给通信子系统.双层决 定条件时，Q学习算法必然收敛在最优解， 策模型把整个决策子系统分为2个层次：协调层和 虽然Q学习在单个Agent领域应用非常成熟 运动控制层，总体结构图如图1所示 也较多地应用于多智能体领域，但是运用于足球机 环境状态 器人决策还存在以下问题：Q学习算法在状态空间 和动作空间较大的情况下，学习效率低，收敛速度 基于模糊状态空间的强化学习 慢.而足球机器人比赛的状态复杂繁多 针对此问题，通过分析足球机器人的行为特征 层 决策子模块 及双层决策模型的特点，仅在上层进行决策的Q学 … 习.这样，机器人的基本行为动作集中体现在下层 采用基于行为的控制方式，缩小了Q学习的动作空 间：在上层进行的Q学习中，通过引入状态模糊化 机器人1 机器人4 (基于行为 (基于行为 的思想，把状态繁多的精确状态映射到7个模糊状 的智能体) 的智能体) 态，进一步缩小Q学习的状态空间.这种双层决策 模型大大降低了Q学习原始状态空间的维数 2基于模糊Q学习的协调层设计 仿真平台 足球机器人系统是一个多智能体系统，它的环 图1双层决策模型总体结构图 境复杂多变.因此，在协调层算法设计中需要解决状 Fig I Structure of the double-layer decisionmak- 态空间划分、策略库设计、奖励函数设计等问题，它 ing model 们设计的好坏直接关系到整个系统的收敛性问题. 下文将具体阐述这些问题的设计方法 协调层用于产生机器人的群体意图.它把整个决 21协调层模型 策意图划分为4个子决策模块：积极进攻模块、保守 通过以上分析，设计了如图2所示的基于强化 进攻模块禁区防守模块、重叠防守模块，然后通过分 学习的协调层模型.其中，s为仿真环境当时的状态 析当时比赛环境和对手的策略，采用基于模糊状态空 输出：为环境的奖赏值：s为比赛进行后的环境的 间的O学习方法来选择最优决策子模块，使得己方策 改变：为感知器通过对原始环境的处理后，得出的 略能够最大限度压制对手决策，从而能在比赛中获得 各个机器人的信息、球的信息和对手的策略等 优势：最后把决策意图发送给运动控制层 首先，感知器通过分析环境s得出场上形势和 在运动控制层中，机器人接收上层决策传送过 对手的策略t然后，策略选择器选择相应的策略” 来的机器人全局目标描述并把这个全局目标描述转 下发到运动控制层，并由运动控制层把具体的策略 化为自己局部视觉描述，然后针对每个机器人采用 作用到仿真环境上：最后，仿真环境状态变化为， 基于行为方法来设计其行动方式，使得每个机器人 并产生相应的强化信号给学习器，学习器通过r 成为一个有自主路径规划等决策能力的单独智能 来更新策略库.这样，通过很多周期的反复迭代，协 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的缺点 [ 4 ] . 文献 [ 5 ]提出了一种基于行为的双层决 策模型 ,能够解决 3层结构的缺点 ,但它也是采用基 于专家经验的方法来实现机器人间的协作 ,因此决 策系统缺乏适应性和自学习能力. 通过在协调层中引入 Q学习算法 ,针对 Q学习 算法在收敛性方面的不足 ,提出一种基于状态空间 模糊化 Q学习的足球机器人双层决策模型 ,在一定 程度上提高了决策系统的适应性和自学习能力. 1 双层决策模型结构与模糊 Q学习 决策子系统通过视觉子系统获得比赛场地上的 各种信息 ,通过分析这些信息做出决策 ,并最终产生 各个机器人的左右轮速发送给通信子系统. 双层决 策模型把整个决策子系统分为 2个层次 :协调层和 运动控制层 ,总体结构图如图 1所示. 图 1 双层决策模型总体结构图 Fig. 1 Structure of the double2layer decision2mak2 ing model 协调层用于产生机器人的群体意图. 它把整个决 策意图划分为 4个子决策模块:积极进攻模块、保守 进攻模块、禁区防守模块、重叠防守模块,然后通过分 析当时比赛环境和对手的策略,采用基于模糊状态空 间的 Q学习方法来选择最优决策子模块,使得己方策 略能够最大限度压制对手决策,从而能在比赛中获得 优势;最后把决策意图发送给运动控制层. 在运动控制层中 ,机器人接收上层决策传送过 来的机器人全局目标描述并把这个全局目标描述转 化为自己局部视觉描述 ,然后针对每个机器人采用 基于行为方法来设计其行动方式 ,使得每个机器人 成为一个有自主路径规划等决策能力的单独智能 体 [ 5 ] . 本文主要针对强化学习在协调层中研究 ,以 提高双层决策模型的适应性和自学习能力. Q学习是由 W atkins于 1989年提出来的一种模 型无关的强化学习算法 [ 629 ] . 单步 Q 学习算法的基 本形式如式 (1)所示 : Q (st , at ) =Q (st , at ) + a ( rt+1 + γmax a Q (st+1 , a) - Q (st , at ) ). (1) 式中 :γ为折扣率 ,α为学习率 (或学习步长 ). Agent 在 st 状态下 ,根据策略选择函数确定动作 at ,得到 奖赏值和训练例 ( st , at , st + 1 , rt + 1 ) ;然后根据此奖赏 值 ,依据式 ( 1)修改 Q 值. 当 Agent访问到目标状 态 ,算法终止一次迭代循环. 研究表明 ,当 α满足一 定条件时 , Q学习算法必然收敛在最优解 [ 10 ] . 虽然 Q学习在单个 Agent领域应用非常成熟 , 也较多地应用于多智能体领域 ,但是运用于足球机 器人决策还存在以下问题 : Q学习算法在状态空间 和动作空间较大的情况下 , 学习效率低 , 收敛速度 慢. 而足球机器人比赛的状态复杂繁多. 针对此问题 ,通过分析足球机器人的行为特征 及双层决策模型的特点 ,仅在上层进行决策的 Q学 习. 这样 ,机器人的基本行为动作集中体现在下层 , 采用基于行为的控制方式 ,缩小了 Q学习的动作空 间;在上层进行的 Q 学习中 ,通过引入状态模糊化 的思想 ,把状态繁多的精确状态映射到 7个模糊状 态 ,进一步缩小 Q 学习的状态空间. 这种双层决策 模型大大降低了 Q学习原始状态空间的维数. 2 基于模糊 Q学习的协调层设计 足球机器人系统是一个多智能体系统 ,它的环 境复杂多变. 因此 ,在协调层算法设计中需要解决状 态空间划分、策略库设计、奖励函数设计等问题 ,它 们设计的好坏直接关系到整个系统的收敛性问题. 下文将具体阐述这些问题的设计方法. 2. 1 协调层模型 通过以上分析 ,设计了如图 2所示的基于强化 学习的协调层模型. 其中 , s为仿真环境当时的状态 输出; r为环境的奖赏值; s′为比赛进行后的环境的 改变; i为感知器通过对原始环境的处理后 ,得出的 各个机器人的信息、球的信息和对手的策略等. 首先 ,感知器通过分析环境 s得出场上形势和 对手的策略 i;然后 ,策略选择器选择相应的策略 n 下发到运动控制层 ,并由运动控制层把具体的策略 作用到仿真环境上;最后 ,仿真环境状态变化为 s′, 并产生相应的强化信号 r给学习器 ,学习器通过 r 来更新策略库. 这样 ,通过很多周期的反复迭代 ,协 第 3期 曹卫华 ,等 :一种基于模糊 Q学习的足球机器人双层协作模型 ·235·
·236- 智能系统学报 第3卷 策略 运动 23学习算法设计 感知器 选择 策略n 控制 针对以上分析，采用极小极大Q算法来设计协 器 层 调层.通过最小化对方决策的奖赏来选择使己方获 得最大奖赏的策略.其值函数如下 学习器 v(s)=maxm in o.(s d.o). (3) d∈Doe0dD 协调层的Q函数Q。(sdo的更新规则为 仿其环境 2(s d.o)-(1-a)e(s d.o)+ a(r(d.o.s)+Yv (s')). (4) 图2协调层结构图 式中：s为当前的环境状态，d为己方在状态s下的 Fig 2 Frame of the cooperation layer 策略，D为己方策略集合，o为对手在状态s下的策 略，O为对方策略集合，：为强化信号，s为新的环 调层就可以学习到在具体情况下的最优策略 境状态，a为学习率，Y为折扣因子 22状态空间的划分与状态映射函数 具体学习过程如下 由于足球机器人比赛环境复杂，形势瞬息万变， 1)观察当前状态s 如果状态集合设计得不合理，会使得Q学习状态空 2)通过以下方法选择一个动作d 间非常庞大，这将直接影响到强化学习算法的收敛 exp (Q(s d,)/T) 速度.因此设计合适的状态空间十分关键.针对这种 P(d,s)=- 5) ∑expQ(sd)/T) 情况，本文采用模糊化的方法把实际状态转化为模 糊状态，从而一定程度上降低了状态空间的大小.以 式中：T称作温度值.式(5)用来确定随机策略的随 我方从左向右进攻为例，其结构图3所示.将整个场 机度.这种方法被称作Boltamann:选择方法，也可采 地划分为11个区间、7种状态，这样，状态空间即可 用ε贪心策略等探测方法 表示为S=底线有利边路有利、中路有利、中路相 3)观察新的状态s! 持、边路威胁、中路威胁、底线威胁人.以我方从左向 4)从环境中获得即时回报r 右进攻为例，其状态划分如图3所示 5)根据式(4)对状态s和动作d相应的Q值进 底 底 行更新 边路威胁 边路有利 6)如果新的状态s满足结束条件，结束这次学 威 有 胁 利 习：否则s→s,返回2) 24策略设计 中路威胁 中路相持 中路有利 策略设计分为己方策略D设计和对方策略O 设计.由于协调智能体的输出为决策子模块，这使得 线威 底线有 策略维数大大降低.通过分析，本文设计了4个决策 边路威胁 边路有利 子模块，即己方策略D=积极进攻，保守进攻，重 叠防守，禁区防守.由于采用的是极小极大Q算 图3状态划分图 法，所以对方策略O={禁区防守，重叠防守，保守 Fig 3 Schematic diagram for state divison 进攻，积极进攻 25基于目标的奖赏函数设计 在状态划分中，考虑3个主要的环境因素：1) 奖励函数是决定智能体执行特定动作后环境给 球在场上的坐标位置P(xy以，依然将其模糊化：根 它的强化信号.传统的Q学习中，如果决策目标达 据图3，将球的位置状态模糊为7种状态h,k∈[1， 成，则得到正的奖励m,反之则得到负的奖励-m. 72)球的速度v及运动角度0：3)对方球员在我 如式(6)所示 方球门附近的个数m.因此设计了把1)、2)、3)作 已方进球 为模糊模块的输入，输出为场上状态的映射函数，如 m, 对方进球，m>0: (6) 式(2 0. 其他 s(h,g0,nl=w·A(v·tan0+n. 2) 但是很多情况下，动作执行的结果很难在一开始 式中：ω为模糊因子 就看到例如，一个进球是由很多决策加在一起后执 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 2 协调层结构图 Fig. 2 Frame of the cooperation layer 调层就可以学习到在具体情况下的最优策略. 2. 2 状态空间的划分与状态映射函数 由于足球机器人比赛环境复杂 ,形势瞬息万变. 如果状态集合设计得不合理 ,会使得 Q学习状态空 间非常庞大 ,这将直接影响到强化学习算法的收敛 速度. 因此设计合适的状态空间十分关键. 针对这种 情况 ,本文采用模糊化的方法把实际状态转化为模 糊状态 ,从而一定程度上降低了状态空间的大小. 以 我方从左向右进攻为例 ,其结构图 3所示. 将整个场 地划分为 11个区间、7种状态 ,这样 ,状态空间即可 表示为 S = {底线有利、边路有利、中路有利、中路相 持、边路威胁、中路威胁、底线威胁 }. 以我方从左向 右进攻为例 ,其状态划分如图 3所示. 图 3 状态划分图 Fig. 3 Schematic diagram for state division 在状态划分中 ,考虑 3个主要的环境因素 : 1) 球在场上的坐标位置 p ( x, y) ,依然将其模糊化 :根 据图 3,将球的位置状态模糊为 7种状态 pk , k∈[ 1, 7 ]; 2) 球的速度 v及运动角度 θ; 3) 对方球员在我 方球门附近的个数 n;. 因此设计了把 1)、2) 、3)作 为模糊模块的输入 ,输出为场上状态的映射函数 ,如 式 (2). s( pk , v,θ, n) =ω·pk ( v·tanθ+ n). (2) 式中 :ω为模糊因子. 2. 3 学习算法设计 针对以上分析 ,采用极小极大 Q算法来设计协 调层. 通过最小化对方决策的奖赏来选择使己方获 得最大奖赏的策略. 其值函数如下 V (s) = max d∈D m in o∈O d∑∈D Qc (s, d, o). (3) 协调层的 Q函数 Qc (s, d, o)的更新规则为 Qc (s, d, o) ← (1 - α) Qc (s, d, o) + α( rc ( d, o, s) +γVc (s′) ). (4) 式中 : s为当前的环境状态 , d为己方在状态 s下的 策略 , D为己方策略集合 , o为对手在状态 s下的策 略 , O为对方策略集合 , rc 为强化信号 , s′为新的环 境状态 ,α为学习率 ,γ为折扣因子. 具体学习过程如下 1) 观察当前状态 s。 2) 通过以下方法选择一个动作 d: P ( di | s) = exp (Q (s, di ) /T) a∑k∈A exp (Q (s, dk ) / T) . (5) 式中 : T称作温度值. 式 ( 5)用来确定随机策略的随 机度. 这种方法被称作 Boltzmann选择方法 ,也可采 用 ε2贪心策略等探测方法. 3) 观察新的状态 s′. 4) 从环境中获得即时回报 r. 5) 根据式 (4)对状态 s和动作 d相应的 Q值进 行更新. 6) 如果新的状态 s满足结束条件 ,结束这次学 习;否则 s→s′,返回 2). 2. 4 策略设计 策略设计分为己方策略 D 设计和对方策略 O 设计. 由于协调智能体的输出为决策子模块 ,这使得 策略维数大大降低. 通过分析 ,本文设计了 4个决策 子模块 ,即己方策略 D = {积极进攻 ,保守进攻 ,重 叠防守 ,禁区防守 }. 由于采用的是极小极大 Q 算 法 ,所以对方策略 O = { 禁区防守 ,重叠防守 ,保守 进攻 ,积极进攻 }. 2. 5 基于目标的奖赏函数设计 奖励函数是决定智能体执行特定动作后环境给 它的强化信号. 传统的 Q 学习中 ,如果决策目标达 成 ,则得到正的奖励 m ,反之则得到负的奖励 - m. 如式 (6)所示 : rs = m , - m , 0, 已方进球; 对方进球 , m > 0; 其他. (6) 但是很多情况下 ,动作执行的结果很难在一开始 就看到. 例如,一个进球是由很多决策加在一起后执 ·236· 智 能 系 统 学 报 第 3卷
第3期 曹卫华，等：一种基于模糊Q学习的足球机器人双层协作模型 ·237 行的结果.因此，采用单纯的传统设计方法，Q学习收 方法得到了如式(9)所示的奖励函数： 敛速度将会很慢，很难达到要求.针对这种情况，本文 E=①。·6+①。·6 (9) 设计了一系列基于目标的奖励函数设计方法 式中：0。、⊙。为对应的加权系数，且0。，⊙。≥0，。+ 在足球机器人中，最主要的目标是小球.所以衡 0，=1 量一个策略有效性的重要指标就是策略执行后球的 3 位置、运动方向速度是不是朝着策略的目标方向行 仿真实验 进.将球在场上的位置做x、y的坐标分解，可以看 仿真实验是在足球机器人仿真平台Robot Soc~ 出，球在x方向上与球门的距离关系更为重要.针对 cer vl.5a上进行的. 这种情况，本文设计了一种基于球在一个周期内在 按照上述方法进行设计协调层，并采用文献 移动的水平距离S与球在一个周期内能够移动的 [5中基于行为的运动控制层来编写决策算法，在 最大水平距离S的比值的奖励分配方法.以球在 足球机器人仿真平台上进行了算法仿真.算法的参 球场上的位置为原点作局部坐标系，如图4所示 数设置为：折扣因子Y=Q9,学习率a的初始值设 为Q8仿真过程中，对手采用随机策略选择动作， 0.40 0.35 0.30 0.25 0.20 ball 50 0.15 0.10 0.05 图4目标坐标分解图 0100200300400500600700800 Fig 4 Schematic diagram for target coordinate dis 学习步数 assemnbling 图5Q值曲线 图4中，v,和v+1分别为球在时刻和1+1时 Fig 5 Q-value curve 刻的速度，x轴为己方进攻方向俱有正负方向)，0 首先实验在经过500步学习后对学习效果进行 为球的运动方向角.则球运动的距离S为 S.=cos0((W,+V1)·1/2) 观察.图5显示了在一次进攻中进攻机器人的积极 7) 假设机器人最大速度为Vmax,那么在时间内， 进攻策略Q值情况.从图中可以看出，随着学习步 运行的最大水平距离为Sm=Vmx·t 数地增加，Q值快速上升，最后收敛于一个稳定的 综上所述，本文设计的基于水平距离的奖赏函 值.所以，基于模糊Q学习的决策算法收敛速度快 学习效率高，算法稳定 数如式(8所示： 然后对500场比赛内每20场比赛的平均净胜 6=m·(S5/max·功 8) 球数进行统计，分别采用基于模糊O学习的双层协 式中：m与式(6)中的m相同，为最大奖励值，速度 作模型策略和传统的基于专家经验的策略进行比 V的正方向跟x轴的正方向相同. 赛，并将结果进行分析对比，结果如图6所示.其中 除了上述奖励方法，还设计了其他一些有效的 奖励方法，并综合输出奖惩值： 坐标y表示净胜球数： 1)如果一个防守队员转化为进攻队员，则奖 基于模糊Q学习的协作模型，→一 6 励，反之，如果一个进攻队员转化为防守队员，惩罚： ◆ 基于专家经验的策略 2)将模糊化的场上状态空间分为3种类型：有 2 利状态底线有利、中路有利、边路有利)，中间状态 0 仲场相持)，被动状态底线威胁、中路威胁、边路 威胁人.参考本周期的场上状态s到下一周期的场上 80 160240320400480 形势s,如果从被动状态转化为中间状态或有利状 比赛场数 态，则奖励.如果从有利状态转化为中间状态或被动 图6净胜球统计 状态，则惩罚 Fig 6 Statistics or gal difference 最后，通过综合考虑3类奖励信息，按照加权的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
行的结果. 因此,采用单纯的传统设计方法, Q学习收 敛速度将会很慢 ,很难达到要求. 针对这种情况,本文 设计了一系列基于目标的奖励函数设计方法. 在足球机器人中 ,最主要的目标是小球. 所以衡 量一个策略有效性的重要指标就是策略执行后球的 位置、运动方向、速度是不是朝着策略的目标方向行 进. 将球在场上的位置做 x、y的坐标分解 ,可以看 出 ,球在 x方向上与球门的距离关系更为重要. 针对 这种情况 ,本文设计了一种基于球在一个周期内在 移动的水平距离 Sx 与球在一个周期内能够移动的 最大水平距离 Smax的比值的奖励分配方法. 以球在 球场上的位置为原点作局部坐标系 ,如图 4所示. 图 4 目标坐标分解图 Fig. 4 Schematic diagram for target coordinate dis2 assembling 图 4中 , vt 和 vt + 1分别为球在 t时刻和 t + 1时 刻的速度 , x轴为己方进攻方向 (具有正负方向 ) ,θ 为球的运动方向角. 则球运动的距离 Sx 为 Sx = cosθ( (Vt +Vt+1 ) ·t/2). (7) 假设机器人最大速度为 Vmax ,那么在时间 t内 , 运行的最大水平距离为 Smax =Vmax ·t. 综上所述 ,本文设计的基于水平距离的奖赏函 数如式 (8)所示 : ra = m ·(Sx / (Vmax ·t) ). (8) 式中 : m 与式 ( 6)中的 m 相同 ,为最大奖励值 ,速度 V的正方向跟 x轴的正方向相同. 除了上述奖励方法 ,还设计了其他一些有效的 奖励方法 ,并综合输出奖惩值 rc : 1) 如果一个防守队员转化为进攻队员 , 则奖 励 ,反之 ,如果一个进攻队员转化为防守队员 ,惩罚; 2) 将模糊化的场上状态空间分为 3种类型 :有 利状态 (底线有利、中路有利、边路有利 ) ,中间状态 (中场相持 ) ,被动状态 (底线威胁、中路威胁、边路 威胁 ). 参考本周期的场上状态 s到下一周期的场上 形势 s′,如果从被动状态转化为中间状态或有利状 态 ,则奖励. 如果从有利状态转化为中间状态或被动 状态 ,则惩罚. 最后 ,通过综合考虑 3类奖励信息 ,按照加权的 方法得到了如式 (9)所示的奖励函数 : rc =ωa ·ra +ωb ·rb . (9) 式中 :ωa、ωb 为对应的加权系数 ,且 ωa ,ωb ≥0,ωa + ωb = 1. 3 仿真实验 仿真实验是在足球机器人仿真平台 Robot Soc2 cer v1. 5a上进行的. 按照上述方法进行设计协调层 , 并采用文献 [ 5 ]中基于行为的运动控制层来编写决策算法 ,在 足球机器人仿真平台上进行了算法仿真. 算法的参 数设置为 :折扣因子 γ= 0. 9,学习率 α的初始值设 为 0. 8. 仿真过程中 ,对手采用随机策略选择动作. 图 5 Q值曲线 Fig. 5 Q2value curve 首先实验在经过 500步学习后对学习效果进行 观察. 图 5显示了在一次进攻中进攻机器人的积极 进攻策略 Q值情况. 从图中可以看出 ,随着学习步 数地增加 , Q 值快速上升 ,最后收敛于一个稳定的 值. 所以 ,基于模糊 Q学习的决策算法收敛速度快 , 学习效率高 ,算法稳定. 然后对 500场比赛内每 20场比赛的平均净胜 球数进行统计 ,分别采用基于模糊 Q学习的双层协 作模型策略和传统的基于专家经验的策略进行比 赛 ,并将结果进行分析对比 ,结果如图 6所示. 其中 , 坐标 y表示净胜球数 : 图 6 净胜球统计 Fig. 6 Statistics for goal difference 第 3期 曹卫华 ,等 :一种基于模糊 Q学习的足球机器人双层协作模型 ·237·
·238· 智能系统学报 第3卷 净胜球数=我方进球数·对方进球数 Institute of Teachnology,2004,36 (7):871-873 从图6中可以看出，基于模糊Q学习的双层协 [5曹卫华，桂卫华，吴敏，等.一种基于行为的足球机器 作模型的净胜球趋势线是上升的.在学习的开始阶 人双层决策模型[C]/哈尔滨：2006中国控制会议论文 集.2006：871-873. 段大约第50场比赛之前)，赢的场数比输的场数 CAO Weihua,G IW eihua,WU Min,et al A double-lay- 要少.这表明系统还在探索学习，因此学习的效果并 er decisionmaking model based on behavior[C]//Proceed- 没有采用经验知识的策略好.但是趋势线上升明显， ings of the 25 th Chinese Control Conference(III).Harbin: 说明学习的方法逐渐显示出了它的作用.从第50场 2006:871-873 开始，赢的场数比输的场数逐渐增多，平均净胜球个 「6郭锐，吴敏，彭军等.一种新的多智能体Q学 数成为正数.从第120场开始，趋势线的上升开始逐 习算法[J].自动化学报，2007,33(4)：367-372 GO Rui.WU Min,PENG Jun,et al A new Q leaming 渐变缓.这是由于在进行了多场比赛后，Q学习已经 algorithm formulti-Agent system s[J ]Acta Autmatica Sin- 学习到大多数对方的策略.而基于传统专家经验策 ica,2007,33(4):367-372 略的净胜球趋势线显示出了明显的随机性，净胜球 [7高阳，陈世福，陆鑫.强化学习研究综述[J]自动 数在0左右震荡，没有明显的规律性.图6中的趋势 化学报，2004,30(1)：86-100 线表明基于Q学习的策略是有效的，并且比赛的结 GAO Yang,CHEN Shifu,LU Xin Research on reinforce- 果也是越来越好.基于该协作模型的机器人系统在 ment leaming technolgy:a review [J].Acta Automatica Sinica,2004,30(1):86-100 2006年全国机器人赛Middle League SmuroSot项目 [8 ]WATKNS C H,DA YAN P Technical note:Q-leaming 中获得二等奖的好成绩。 [J].Machine Leaming.1992,8(3-4):279-292 [9]TSITS IKL IS J N.Asynchronous stochastic approxmation 4结束语 and Q-leaming [J ]Machine Leaming,1994,16 (3): 185-202 提出足球机器人双层决策模型并在协调层中引 [10 L ITIMAN L,SZEPESVAR I C A generalized reinforce- 入模糊Q学习方法，它能够有效地解决传统决策模 ment leaming model convergence and Applications 型中由于决策交错而引起的机器人运动不连贯的缺 [C]//Proc of the 13th Intemational Conference on Ma- 点，并提高了决策系统的适应性和自学习能力.在协 chine Leaming Bari,Italy:Morgan Kanfnann,1996: 调层中，针对机器人足球比赛的特点，通过采用对比 310 赛场地分区和位置映射的方法，大大地降低了状态 作者简介： 空间大小.另外，提出了一种基于水平距离的奖励函 曹卫华，男，1972年生，副教授、博 数设计方法，使奖励分配更加合理，这在一定程度上 士，主要研究方向为机器人与智能系统 提高了Q学习的收敛速度 技术和过程控制.1996~1997年赴日本 金泽大学留学一年.获省部级科技进步 参考文献： 二等奖2项、三等奖2项。 [1 ]ASADA M,KITANO H The robocup challenge [J].Ro- botics and Autonomous System,1999,29(1):3-12 [2赵逢达，孔令富，李贤善.基于分层结构模型的机器人 徐凌云，男，1982年生，硕士研究 足球决策系统设计[J1哈尔滨工业大学学报，2005,37 生，主要研究方向为足球机器人系统与 (7):933935 多智能体技术 ZHAO Fengda.KONG L ingfu,LI Xianshan Design of ro- bot soccer decisionmaking subsystem based on layered structure model[J ]Joumal of Harbin Institute of Technol- gy,2005,37(7):933-935 吴敏，男，1963年生，博士生导师 [3陆永忠，柯文德.足球机器人决策系统的设计与实现 主要研究方向为过程控制、鲁棒控制 [J]计算机仿真，2007,24(9)：129-32 和智能系统.1989~1990年在日本东 LU Yonghong,KE Wende Design and mplementaton of 北大学进修：1996~1999年赴日本东京工 decision system or soccer robot[J]Computer Smulation, 业大学从事国际合作研究，2001~2002年 2007,24(9):129-132 得到英国皇家学会资助，为英国诺丁汉 [4浏云江，韩光胜.基于多智能体规划的机器人足球决策 大学访问教授.1999年与中野道雄教授和余锦华博士一起获 模型[J]哈尔滨工业大学学报，2004,36(7)：871- 国际自动控制联合会(IFAC)控制工程实践优秀论文奖. 873 L U Yunjiang,HAN Guangsheng Decisonmaking model for robot-soccer based on multi-Agent[J].Joumal of Harbin 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
净胜球数 = 我方进球数 - 对方进球数. 从图 6中可以看出 ,基于模糊 Q学习的双层协 作模型的净胜球趋势线是上升的. 在学习的开始阶 段 (大约第 50场比赛之前 ) ,赢的场数比输的场数 要少. 这表明系统还在探索学习 ,因此学习的效果并 没有采用经验知识的策略好. 但是趋势线上升明显 , 说明学习的方法逐渐显示出了它的作用. 从第 50场 开始 ,赢的场数比输的场数逐渐增多 ,平均净胜球个 数成为正数. 从第 120场开始 ,趋势线的上升开始逐 渐变缓. 这是由于在进行了多场比赛后 , Q学习已经 学习到大多数对方的策略. 而基于传统专家经验策 略的净胜球趋势线显示出了明显的随机性 ,净胜球 数在 0左右震荡 ,没有明显的规律性. 图 6中的趋势 线表明基于 Q学习的策略是有效的 ,并且比赛的结 果也是越来越好. 基于该协作模型的机器人系统在 2006年全国机器人赛 M iddle League SimuroSot项目 中获得二等奖的好成绩. 4 结束语 提出足球机器人双层决策模型并在协调层中引 入模糊 Q学习方法 ,它能够有效地解决传统决策模 型中由于决策交错而引起的机器人运动不连贯的缺 点 ,并提高了决策系统的适应性和自学习能力. 在协 调层中 ,针对机器人足球比赛的特点 ,通过采用对比 赛场地分区和位置映射的方法 ,大大地降低了状态 空间大小. 另外 ,提出了一种基于水平距离的奖励函 数设计方法 ,使奖励分配更加合理 ,这在一定程度上 提高了 Q学习的收敛速度. 参考文献 : [ 1 ]ASADA M, KITANO H. The robocup challenge [J ]. Ro2 botics and Autonomous System, 1999, 29 (1) : 3212. [ 2 ]赵逢达 , 孔令富 , 李贤善. 基于分层结构模型的机器人 足球决策系统设计 [J ]. 哈尔滨工业大学学报 , 2005, 37 (7) : 9332935. ZHAO Fengda, KONG L ingfu, L I Xianshan. Design of ro2 bot soccer decision2making subsystem based on layered structure model[J ]. Journal of Harbin Institute of Technolo2 gy, 2005, 37 (7) : 9332935. [ 3 ]陆永忠 ,柯文德. 足球机器人决策系统的设计与实现 [J ]. 计算机仿真 , 2007, 24 (9) : 1292132. LU Yongzhong, KE W ende. Design and imp lementation of decision system for soccer robot[J ]. Computer Simulation, 2007, 24 (9) : 1292132. [ 4 ]刘云江 , 韩光胜. 基于多智能体规划的机器人足球决策 模型 [ J ]. 哈尔滨工业大学学报 , 2004, 36 ( 7) : 8712 873. L IU Yunjiang, HAN Guangsheng. Decision2making model for robot2soccer based on multi2Agent[J ]. Journal of Harbin Institute of Teachnology, 2004, 36 (7) : 8712873. [ 5 ]曹卫华 , 桂卫华 , 吴 敏 ,等. 一种基于行为的足球机器 人双层决策模型 [C ] / / 哈尔滨 : 2006中国控制会议论文 集. 2006: 8712873. CAO W eihua, GU IW eihua, WU M in, et al. A double2lay2 er decision2makingmodel based on behavior[C ] / / Proceed2 ings of the 25 th Chinese Control Conference ( Ⅲ). Harbin: 2006: 8712873. [ 6 ]郭 锐 , 吴 敏 , 彭 军 ,等. 一种新的多智能体 Q学 习算法 [J ]. 自动化学报 , 2007, 33 (4) : 3672372 GUO Rui, WU M in, PENG Jun, et al. A new Q learning algorithm formulti2Agent system s[J ]. Acta Automatica Sin2 ica, 2007, 33 (4) : 3672372. [ 7 ]高 阳 , 陈世福 , 陆 鑫. 强化学习研究综述 [J ]. 自动 化学报 , 2004, 30 (1) : 862100. GAO Yang, CHEN Shifu, LU Xin. Research on reinforce2 ment learning technology: a review [ J ]. Acta Automatica Sinica, 2004, 30 (1) : 862100. [ 8 ]WATKINS C H, DAYAN P. Technical note: Q2learning [J ]. Machine Learning, 1992, 8 (324) : 2792292. [ 9 ] TSITSIKL IS J N. A synchronous stochastic app roximation and Q2learning [ J ]. Machine Learning, 1994, 16 ( 3 ) : 1852202. [ 10 ] L ITTMAN L, SZEPESVAR I C. A generalized reinforce2 ment learning model: convergence and App lications [C ] / /Proc of the 13 th International Conference on Ma2 chine Learning. Bari, Italy: Morgan Kanfmann, 1996: 310. 作者简介 : 曹卫华 ,男 , 1972年生 ,副教授、博 士 ,主要研究方向为机器人与智能系统 技术和过程控制. 1996～1997年赴日本 金泽大学留学一年. 获省部级科技进步 二等奖 2项、三等奖 2项. 徐凌云 ,男 , 1982 年生 ,硕士研究 生 ,主要研究方向为足球机器人系统与 多智能体技术. 吴 敏 ,男 , 1963年生 ,博士生导师 , 238· 主要研究方向为过程 控 制、鲁 棒 控 制 和 智 能 系 统.1989～1990年在日本东 北大学进修;1996～1999年赴日本东京工 业大学从事国际合作研究;2001～2002年 得到英国皇家学会资助,为英国诺丁汉 大学访问教授.1999年与中野道雄教授和佘锦华博士一起获 国际自动控制联合会(IFAC)控制工程实践优秀论文奖. · 智 能 系 统 学 报 第 3卷