论文部分内容阅读
摘 要：机器人足球比赛是一个有趣并且复杂的新兴的人工智能研究领域，它是一个典型的多智能体系统。在足球机器人比赛中，由于攻防转换速度较快，各个机器人要不断地进行角色转化。采用Q学习方法研究了机器人足球比赛中的足球机器人的角色转换问题，实验结果证明了该方法的有效性。
关键词：多智能体；q学习；角色分配；
中图分类号:TP242.6 文献标识码:A
Application of Robot Soccer Role Assignment Based on Q Learning in Multi Agent Cooperation
ZHANG Jie，LI Xiu-juan，ZHANGXiao-dong
（School of Electrical Engineering, Henan University of Technology,HenanZhengzhou450007）
Key words: multi Agent； Q learning； role selecting
近年来，多智能体系统逐渐成为人工智能领域中一个引人注目的分支[1]。多智能体系统是由多个可计算的智能体组成的集合，它能协调一组自主体的行为知识、目标、方法和规划等，以协同地动作和求解问题。在多机器人系统中每个机器人都被视为一个具有基本行为Agent，一般只处理与自身相关的局部目标和本地信息进行自主运动。各机器人可根据系统总任务目标,动态地规划各自的运动序列，而不是由集中规划器进规划；同时又可充分发挥其智能和自主行为来与其它机器人进行合作。
机器人足球比赛是一个有趣并且复杂的新兴的人工智能研究领域[2]。它融合了实时视觉系统、机器人控制、无线通讯、多机器人控制等多个领域的技术，被称为是"坪上的技术战争"。它已经成为研究多智能体系统的一个标准实验平台。在足球比赛中由于比赛的需要，机器人要经常进行角色的转换，以便于取得良好的运动效果。原有的角色分配采用权值法存在一个缺陷，即权值的确定具有太大的主观性[3]。本文采用Q学习方法研究了机器人足球比赛中的角色分配问题问题，实验结果表明了该方法的有效性。
1 Q-学习
Q-学习是根据将状态－行动对映射为期望返回值的行动的价值函数Q，求解具有不完整信息的马尔可夫行动问题的一种简单方式[4]。
Q-学习的目标是估计一条最优策略的价值。状态的价值可以定义为该状态最好的状态－行动对的价值：
V(S)=maxaQ(s,a)（1）
按照一定策略函数确定最优策略使得，
V(S)=Q(s,a)=maxb∈actions Q(s,a) （2）
在一步Q-学习中，一步延迟之后，只有最近的状态－行动对的行动－价值函数Q被更新，在第n步，Q值的更新规则是基于时间差分方法，其中sn是当前状态，an是选定的行动：
η表示学习效率，r是衰减因子，取值在[0,1]之间。
在学习的早期步骤中，Q值可能不能准确反映它隐式定义的策略。通过在所有状态重复所有的行动，由长期的折扣奖赏判断，可以学习到整体最优。
在Q-学习中，智能系统的经历包括一系列不同的阶段，在每个阶段，其学习步骤如下：
（1） 观察现在的状态si；
（2） 选择并执行一个行为ai；
（3） 观察下一个状态si+1；
（4） 收到一个立即强化信号ri；
（5） 按照公式（3）调整Q值；
（6） 重复以上过程。
2 基于Q学习的角色分配
原有的角色分配采用权值法存在一个缺陷，即权值的确定具有太大的主观性。权值的确定直接影响到球队整体的效率。如果权值选择不合适，球队反应太慢，不能快速针对场上
态势跟上球。从态势分析来看，无论球在哪个区域，绝大部分时候总有一个主攻球员担任进攻或者拦截的任务，担任这个角色的球员是唯一的触球队员，担负着追球、碰球的重大职责，也决定着比赛的激烈程度。所以这个角色的选择非常重要，采用Q学习算法，针对影响角色分配的n个因素，设定多种状态，并进行学习，以期获得最佳的加权分配。
守门员角色不计算在内，在其余四个队员中间选择主攻队员。
设定如下boolean型参量：bb、preID、sl、sa。bb为1（真）表示机器人在球后，即机器人位于球和己方底线之间，反之则为0（假）；preID表示当前选择的最优主攻机器人ID和上一周期选择的主攻机器人ID的关系，如果相同则为preID=1，否则为0；sl值为1，则表示选择为主攻角色的机器人和球的距离是四个机器人中最小的，为0则不是；sa表示球与对方球门中点的连线和沿机器人角度作的直线之间的夹角小于30。，如图1所示，如果β<30。，那么则sa的值是1，否则为0。四种因素的权值分别为Pbb、Pid、Psl、Psa。
Pglaobal=Pbb+Pid+Psl+Psa（5）
那么每次进行角色分配时依据的公式为：
P(k)=Lk(1-Pbb/Pglaobal)(1-Pbb/Pglaobal)(1-Pid/Pglaobal)(1-Psl/Pglaobal)(1-Psa/Pglaobal)（6）
将四个机器人的权值计算出来，然后选P(k)最小的机器人作为主攻机器人，看作权值最高。选择时间周期为t=33ms，也就是决策子系统的运行周期。
Q学习模块内嵌在角色分配模块中，每一步，Q学习模块会提供当前奖罚和感应的状态，并返回给选择器应该激活的状态。Q学习自动跟踪之前的状态和奖罚过程，并重新制定新的策略。
最优主攻队员可能有的状态s如表1。
总共有15种状态，每周期选中的主攻机器人肯定是其中之一，假定它属于状态si（0 学习策略依赖奖罚函数来训练机器的学习能力。
R(t)=1如果状态
s，已方进球了
-1 如果状态
s，对方进球了
0其它 （6）
Rchange(t)=1如果状态
s，主攻机器人与球的距离在缩小
-1 如果状态
s，主攻机器人与球的距离扩大到8cm以上
0其它 (7)
为了检验和训练Q值，学习过程以双方得分和满10分为一回合，连续100个回合作为一次实验，拟进行10次实验。
每次实验开始时Q值初始化为0到1之间的一个随机数。每次感应到状态改变或者进球了则改变Q值，然后将所有的Q值排序，选择Q值最大时所对应的行为。
3 具体实现
3.1Q学习系统的组成
Q学习系统包括如下几个部分：
a．一组状态：列举了角色分配中选取主攻机器人所有可能的状态；
这里对应着状态s，总共有表一列举15种状态。
b．一组动作：主体可能做的基本动作；
在角色分配中，动作概念有一定的变化，这里不是指机器人实际进行的动作，而是指如何来选用主攻机器人这个动作，对应着角色分配依据公式。
c．一个转换映射：将二维空间的每个元素（状态，动作）映射到一个结果状态；
将根据角色分配依据公式最后选中的机器人所产生的行为作为结果状态，即主攻机器人是否能很快缩短与球的距离，是否能进球得分等。
d．一组效益值：表示训练中动作的效益，有正值、负值之分，即上一节定义的奖惩函数Rscore和Rchange。
e．一个效益函数：根据主体和环境交互的实际结果计算效益值，即Q值。
3.2学习算法实现
这一部分分为学习模块和主攻机器人寻优模块，简单来说是训练模块和执行模块。
训练模块的执行过程：
Repeat
判断系统上一轮状态；
找出上一轮根据角色分配依据公式得到的主攻机器人扮演者；
根据奖惩函数评价主攻机器人上一轮扮演角色的成功情况；
用效益函数计算即时Q值；
选取最大Q值，并找到彼时所对应的状态；
根据当时的奖惩函数，更新所有因子的权值；
确定新的角色分配依据公式；
更新Q值
Until Q值收敛
执行模块的执行过程：
Repeat
判断系统当前状态；
根据角色分配依据公式选取能产生最大效益的主攻机器人；
给其分配主攻角色；
Until 程序终止或比赛结束
算法实现时将训练模块内嵌在执行模块中，执行模块每个系统周期都要执行一次，而学习模块则只有当系统状态改变或进球才被执行。初始的角色分配公式可以自行选择值，期待在数次学习后Q值收敛，确定Q值最高的角色分配公式。
4 实验和结论
以MiroSot三对三为例进行了基于Q学习的角色分配训练学习。图2为实际运行时ID号为1的机器人角色转换图。三对三中，大部分情况下机器人或者处于主攻位置或者处于助攻或防守位置，所以只有两种角色可选，设定角色序号为1则扮演主攻角色，序号为1则表明它扮演辅助角色。图中选择了其中90个时间周期，每个时间周期为40ms。从图中可以看出，该机器人在0到10周期内扮演辅助角色，由于态势变化，它处于比较有利于触球的位置，在10到31周期被分配主攻角色。说明该机器人的角色是稳定的，这种角色分配方案非常合理。
参考文献：
[1]张小川,李祖枢,刘海涛.足球机器人决策子系统的分析与设计.华中科技大学学报(自然科学版)[J],2004,32:146-149.
[2]洪炳熔，刘新宇．基于视觉的足球机器人系统．计算机应用研究[J]，2001，1：1～3
（本文系河南工业大学科研基金项目：170176）
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
关键词：多智能体；q学习；角色分配；
中图分类号:TP242.6 文献标识码:A
Application of Robot Soccer Role Assignment Based on Q Learning in Multi Agent Cooperation
ZHANG Jie，LI Xiu-juan，ZHANGXiao-dong
（School of Electrical Engineering, Henan University of Technology,HenanZhengzhou450007）
Key words: multi Agent； Q learning； role selecting
近年来，多智能体系统逐渐成为人工智能领域中一个引人注目的分支[1]。多智能体系统是由多个可计算的智能体组成的集合，它能协调一组自主体的行为知识、目标、方法和规划等，以协同地动作和求解问题。在多机器人系统中每个机器人都被视为一个具有基本行为Agent，一般只处理与自身相关的局部目标和本地信息进行自主运动。各机器人可根据系统总任务目标,动态地规划各自的运动序列，而不是由集中规划器进规划；同时又可充分发挥其智能和自主行为来与其它机器人进行合作。
机器人足球比赛是一个有趣并且复杂的新兴的人工智能研究领域[2]。它融合了实时视觉系统、机器人控制、无线通讯、多机器人控制等多个领域的技术，被称为是"坪上的技术战争"。它已经成为研究多智能体系统的一个标准实验平台。在足球比赛中由于比赛的需要，机器人要经常进行角色的转换，以便于取得良好的运动效果。原有的角色分配采用权值法存在一个缺陷，即权值的确定具有太大的主观性[3]。本文采用Q学习方法研究了机器人足球比赛中的角色分配问题问题，实验结果表明了该方法的有效性。
1 Q-学习
Q-学习是根据将状态－行动对映射为期望返回值的行动的价值函数Q，求解具有不完整信息的马尔可夫行动问题的一种简单方式[4]。
Q-学习的目标是估计一条最优策略的价值。状态的价值可以定义为该状态最好的状态－行动对的价值：
V(S)=maxaQ(s,a)（1）
按照一定策略函数确定最优策略使得，
V(S)=Q(s,a)=maxb∈actions Q(s,a) （2）
在一步Q-学习中，一步延迟之后，只有最近的状态－行动对的行动－价值函数Q被更新，在第n步，Q值的更新规则是基于时间差分方法，其中sn是当前状态，an是选定的行动：
η表示学习效率，r是衰减因子，取值在[0,1]之间。
在学习的早期步骤中，Q值可能不能准确反映它隐式定义的策略。通过在所有状态重复所有的行动，由长期的折扣奖赏判断，可以学习到整体最优。
在Q-学习中，智能系统的经历包括一系列不同的阶段，在每个阶段，其学习步骤如下：
（1） 观察现在的状态si；
（2） 选择并执行一个行为ai；
（3） 观察下一个状态si+1；
（4） 收到一个立即强化信号ri；
（5） 按照公式（3）调整Q值；
（6） 重复以上过程。
2 基于Q学习的角色分配
原有的角色分配采用权值法存在一个缺陷，即权值的确定具有太大的主观性。权值的确定直接影响到球队整体的效率。如果权值选择不合适，球队反应太慢，不能快速针对场上
态势跟上球。从态势分析来看，无论球在哪个区域，绝大部分时候总有一个主攻球员担任进攻或者拦截的任务，担任这个角色的球员是唯一的触球队员，担负着追球、碰球的重大职责，也决定着比赛的激烈程度。所以这个角色的选择非常重要，采用Q学习算法，针对影响角色分配的n个因素，设定多种状态，并进行学习，以期获得最佳的加权分配。
守门员角色不计算在内，在其余四个队员中间选择主攻队员。
设定如下boolean型参量：bb、preID、sl、sa。bb为1（真）表示机器人在球后，即机器人位于球和己方底线之间，反之则为0（假）；preID表示当前选择的最优主攻机器人ID和上一周期选择的主攻机器人ID的关系，如果相同则为preID=1，否则为0；sl值为1，则表示选择为主攻角色的机器人和球的距离是四个机器人中最小的，为0则不是；sa表示球与对方球门中点的连线和沿机器人角度作的直线之间的夹角小于30。，如图1所示，如果β<30。，那么则sa的值是1，否则为0。四种因素的权值分别为Pbb、Pid、Psl、Psa。
Pglaobal=Pbb+Pid+Psl+Psa（5）
那么每次进行角色分配时依据的公式为：
P(k)=Lk(1-Pbb/Pglaobal)(1-Pbb/Pglaobal)(1-Pid/Pglaobal)(1-Psl/Pglaobal)(1-Psa/Pglaobal)（6）
将四个机器人的权值计算出来，然后选P(k)最小的机器人作为主攻机器人，看作权值最高。选择时间周期为t=33ms，也就是决策子系统的运行周期。
Q学习模块内嵌在角色分配模块中，每一步，Q学习模块会提供当前奖罚和感应的状态，并返回给选择器应该激活的状态。Q学习自动跟踪之前的状态和奖罚过程，并重新制定新的策略。
最优主攻队员可能有的状态s如表1。
总共有15种状态，每周期选中的主攻机器人肯定是其中之一，假定它属于状态si（0
R(t)=1如果状态
s，已方进球了
-1 如果状态
s，对方进球了
0其它 （6）
Rchange(t)=1如果状态
s，主攻机器人与球的距离在缩小
-1 如果状态
s，主攻机器人与球的距离扩大到8cm以上
0其它 (7)
为了检验和训练Q值，学习过程以双方得分和满10分为一回合，连续100个回合作为一次实验，拟进行10次实验。
每次实验开始时Q值初始化为0到1之间的一个随机数。每次感应到状态改变或者进球了则改变Q值，然后将所有的Q值排序，选择Q值最大时所对应的行为。
3 具体实现
3.1Q学习系统的组成
Q学习系统包括如下几个部分：
a．一组状态：列举了角色分配中选取主攻机器人所有可能的状态；
这里对应着状态s，总共有表一列举15种状态。
b．一组动作：主体可能做的基本动作；
在角色分配中，动作概念有一定的变化，这里不是指机器人实际进行的动作，而是指如何来选用主攻机器人这个动作，对应着角色分配依据公式。
c．一个转换映射：将二维空间的每个元素（状态，动作）映射到一个结果状态；
将根据角色分配依据公式最后选中的机器人所产生的行为作为结果状态，即主攻机器人是否能很快缩短与球的距离，是否能进球得分等。
d．一组效益值：表示训练中动作的效益，有正值、负值之分，即上一节定义的奖惩函数Rscore和Rchange。
e．一个效益函数：根据主体和环境交互的实际结果计算效益值，即Q值。
3.2学习算法实现
这一部分分为学习模块和主攻机器人寻优模块，简单来说是训练模块和执行模块。
训练模块的执行过程：
Repeat
判断系统上一轮状态；
找出上一轮根据角色分配依据公式得到的主攻机器人扮演者；
根据奖惩函数评价主攻机器人上一轮扮演角色的成功情况；
用效益函数计算即时Q值；
选取最大Q值，并找到彼时所对应的状态；
根据当时的奖惩函数，更新所有因子的权值；
确定新的角色分配依据公式；
更新Q值
Until Q值收敛
执行模块的执行过程：
Repeat
判断系统当前状态；
根据角色分配依据公式选取能产生最大效益的主攻机器人；
给其分配主攻角色；
Until 程序终止或比赛结束
算法实现时将训练模块内嵌在执行模块中，执行模块每个系统周期都要执行一次，而学习模块则只有当系统状态改变或进球才被执行。初始的角色分配公式可以自行选择值，期待在数次学习后Q值收敛，确定Q值最高的角色分配公式。
4 实验和结论
以MiroSot三对三为例进行了基于Q学习的角色分配训练学习。图2为实际运行时ID号为1的机器人角色转换图。三对三中，大部分情况下机器人或者处于主攻位置或者处于助攻或防守位置，所以只有两种角色可选，设定角色序号为1则扮演主攻角色，序号为1则表明它扮演辅助角色。图中选择了其中90个时间周期，每个时间周期为40ms。从图中可以看出，该机器人在0到10周期内扮演辅助角色，由于态势变化，它处于比较有利于触球的位置，在10到31周期被分配主攻角色。说明该机器人的角色是稳定的，这种角色分配方案非常合理。
参考文献：
[1]张小川,李祖枢,刘海涛.足球机器人决策子系统的分析与设计.华中科技大学学报(自然科学版)[J],2004,32:146-149.
[2]洪炳熔，刘新宇．基于视觉的足球机器人系统．计算机应用研究[J]，2001，1：1～3
（本文系河南工业大学科研基金项目：170176）
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文