（计算机软件与理论专业论文）robocup2d中的多agent协作技术研究.pdf

r o b o c u p 2 d 中的多a g e n t 协作技术研究 摘要 多a g e n t 协作问题是r o b o c u p 2 d 中研究的热点问题。r o b o c u p 仿真2 d 中， 协作问题解决的好坏直接关乎比赛效果。针对仿真2 d 中的实际问题，本文首 先介绍了多a g e n t 协作研究背景及研究现状，国内外r o b o c u p 2 d 中的多a g e n t 协作研究现状； 其次研究r o b o c u p 2 d 中的队友模型理论，在此基础上提出了换位思考模 型，换位思考模型思想是在多智能体协作中考虑了协作a g e n t 周围的环境，并 预测该a g e n t 行为模式，从而做出协作决策，利用该模型研究其在多a g e n t 协 作进攻中的应用； 最后从对手a g e n t 的角色，频繁活动区域，异构类型方面进行分析预测， 利用教练对对手建模，结合q 学习算法在此基础上给出了换位思考模型在协作 防守中的应用。 换位思考思想应用在队友协作进攻中，即设身处地在队友的周围环境状态 中预测该队友的模型是传球，带球，射门等模式，从而根据该队友的模式去协 助其进攻。换位思考思想应用在协作防守中即，在分析得到对手a g e n t 的角色， 区域，异构类型等特征之后，设身处地在此对手的环境中，预测其进攻模式， 并根据此对手的决策去防守。 关键词：换位思考对手异构类型h m m 模型多a g e n t 协作 4 m u l t i - - a g e n tc o l l a b o r a t i v er e s e a r c hi nr o b o c u p 2 d a b s t r a c t r e s e a r c ho fm u l t i a g e n tc o l l a b o r a t i v ei sp o p u l a rr e c e n t l y i nt h er o b o c u p2 d m a t c h ，t h er e s u l to fm a t c hd e c i d e so nh o wt or e s o l v ec o l l a b o r a t i o n a c c o r d i n gt o t h ef a c ti nr o b o c u p2 dm a t c h ，t h ed i s s e r t a t i o nf i r s t l ya n a l y s e sb a c k g r o u n da n d a c t u a l i t yi nm u l t i a g e n tc o l l a b o r a t i v er e s e a r c h , m e a n w h i l e ，t h ed i s s e r t a t i o n i n t r o d u c e ss t u d ys t a t u so fm u l t ia g e n ts y s t e m s e c o n d l y ，s t u d i e st e a m m a t em o d e lt h e o r y , p o p su pc h a n g e r o l em o d e la n d g i v e si t sa p p l i c a t i o ni nc o l l a b o r a t i v ea t t a c k ，a n df o r e c a s t sa g e n tm o d e la c c o r d i n gt o t h ea g e n t se n v i r o n m e n ta n dg e t sm o r ea c c u r a t ec o l l a b o r a t i v ed e c i s i o n t r a d i t i o n c o d i n gm e t h o d so n l yc o n s i d e rd e c i d e - a g e n t se n v i r o n m e n t t h i r d l y ，a n a l y z e sr o l e ，a c t i v ea r e aa n dh e t e r o g e n e o u st y p e so fo p p o n e n t s ，a n d g i v e sa p p l i c a t i o ni nc o l l a b o r a t i v ed e f e n s i v ea c c o r d i n gt oq l e a r n i n gm e t h o d c h a n g r o l ei d e ai nc o l l a b o r a t i v ea t t a c ka p p l i c a t i o nd e s c r i b ea sa sf o l l o w s ： f o r e c a s tt e a m m a t e s m o d e li ne a s eo fe n v i r o n m e n to ft e a m m a t e s ，t h em o d e lm a yb e p a s sb a l l ，d r i b b l eb a l l ，o rs h o o tb a l l t h e n ，t h ea g e n tm a k e sc o l l a b o r a t i v ed e c i s i o n a c c o r d i n gt ot h em o d e lo ft e a m m a t e s c h a n g - r o l ei d e ai nc o l l a b o r a t i v ed e f e n s i v e a p p l i c a t i o nd e s c r i b ea sf o l l o w s ：a n a l y z er o l e ，a c t i v ea r e aa n dh e t e r o g e n e o u st y p e s o fo p p o n e n t s ，f o r e c a s tm o d e lo fo p p o n e n t s ，t h e nm a k ec o l l a b o r a t i v ed e f e n s i v e d e c i s i o n k e y w o r d s ：c h a n g r o l e ；h e t e r o g e n e o u st y p e so fo p p o n e n t s ；h m mm o d e l ； m u l t i 。a g e n tc o l l a b o r a t i v e 5 插图清单 图2 1r o b o c u p 中的换位思考情景图1 0 图2 2 换位思考模型图1 1 图2 3 教练工作过程图1 3 图2 4 传球模式1 3 图2 5 带球模式13 图2 6 射门模式1 3 图2 7 教练建模流程图1 4 图2 8 模式匹配与比赛周期的关系趋势图1 7 图2 9 平均传球成功率与训练周期关系图1 8 图3 1 角色分工示意图。1 9 图3 2 教练分析对手异构类型结果2 4 图3 35 0 0 周期仿真环境的对手真实异构类型截图2 4 图3 - 4 对手异构识别的平均成功率和比赛周期之间的关系趋势2 5 图3 5 教练分析对手异构类型和不分析对手异构类型的比赛效果2 5 图3 - 6h m m 模型定位对手前锋a g e n t 的误差趋势图3 0 图3 7h m m 模型定位对手中场a g e n t 误差趋势图3 0 图3 8h m m 模型定位对手后卫a g e n t 误差趋势图31 图4 1 牛顿迭代截球示意图3 2 图4 2 曲面截球示意图3 3 图4 3 截球曲线示意图3 4 图4 - 4 截球模式3 6 图4 5 在线教练对手建模流程图3 6 图4 6 截球决策流程图3 8 图4 7 截球平均成功率比较3 9 图4 8 截球平均所耗体力比较3 9 9 表格清单 表2 - 1 传球结果统计1 6 表2 - 2 改进q 学习算法学习传球协作得到的q 表1 7 表2 - 3 换位思考与传统方法的传球成功率比较1 8 表3 - 1 规整方法的性能比较2 1 表3 2c o s s i g m o i d 性能比较2 l 表3 - 3 异构球员的参数矛盾对2 2 表3 - 4 分析异构类型结果表2 3 表4 - 1 截球结果统计3 7 1 0 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得合肥工业大学或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签字： 尚两签字日期：弘和年仁月沙日 学位论文版权使用授权书 本学位论文作者完全了解金胆王些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金胆工业盔堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：尚而 签字日期：铀年心月媚 学位论文作者毕业后去向： 工作单位： 通讯地址： 3 翮躲互夕乏 _ 。一 签字日期：勿咖年争月矽日 电话： 邮编： 致谢 首先，特别感谢导师王浩教授，谢谢导师提供的良好学习研究环境，提供的 r o b o c u p 实验室和环境。从实验方案，实验的开展，实验结果分析到论文的修改无不 渗透着导师的心血。三年来，在学业上得到导师的指导，在生活中受到导师的无微不 至的关怀。导师学识渊博、治学严谨，在工作上兢兢业业、事业上孜孜不倦的精神， 永远保持饱满的精神和良好的状态，在生活中严于律己、宽以待人的态度值得学生学 习践行。 特别感谢方宝富老师，谢谢他提供的一切帮助，关照，指导及个人影响。方老 师视野开阔、诲人不倦、严格要求，对我的研究工作提出了许多中肯、宝贵的 意见，令我受益匪浅。在此向敬爱的导师致以衷心的感谢和美好的祝愿。 其次，感谢同组的老师，他们是姚宏亮，方帅，于磊，杨静，李俊照和其他课题 组的师弟师妹同学和舍友华德梅，感谢他们在本人试验时给予的各种帮助及方便，在 生活中给予的关心。感谢实验室共同努力生活的同学，他们是施国强，方辉，谢谢他 们在研究和学习中给予的帮助。感谢师兄师弟们给予的帮助，他们是李龙，王国庆， 高明，感谢他们所给予的帮助和友情及关心。感谢跟我一起努力奋斗的本科生同学， 他们是代成俊，程伟，尹力，马海龙，谢谢他们一起陪我走过了艰苦的时光。 特别感谢我的父亲，母亲，妹妹，感谢家人给予的无微不至的照顾和关怀，生活 上的，精神上的教导。 最后向以上所有的人士以及所有关注我成长的人士致以最真诚的感谢。对评审论 文和参加答辩的各位老师，专家致以最真诚的感谢，谢谢您们在论文评审和答辩过程 中提出的宝贵意见，愿您们平安健康快乐。 6 作者：尚丽 2 0 1 0 4 2 0 1 1 引言 第一章绪论 目前对于a g e n t 相关技术研究已经成为国内外的热点研究问题。不同相关 领域的专家对a g e n t 定义持有不同的理解和看法，然而对于a g e n t 理解已有部 分达成共识，比如任a g e n t 都具有自治性。关于a g e n t 具体定义，可以参照 w o o l d r i d g e 和j e n n i n g s t l l ，即定义a g e n t 是一个特定环境中的独立计算机系统， 并且该独立系统有能力自己做出决策，完成特定情况下的目标。单一a g e n t 与 环境具有交互性，即根据环境状态做出适应的简单动作和决策，然而在动态复 杂的环境中，单一a g e n t 不能适应环境给出复杂动作和决策。最多只能部分的 从环境中抽象信息，分流信息，做出决策和动作，并反作用于环境。当然，环 境具有动态复杂，有噪音，随机，不确定性，a g e n t 目前还不能够很好的适应 这样一个不确定的环境，往往会产生不好的效果。通常，a g e n t 存有一个数据 库，包含相关的执行底层动作和基本决策集。一般情况下a g e n t 根据该动作决 策集做出决策反应，完成局部范围内的简单任务。当然，数据库是有限的，因 此a g e n t 的反应具有局限性。同样，并不是数据库中所有的动作都能够执行， 因为某些特定动作只有在特定情况下才能被执行。举个简单例子，一个a g e n t 要完成“搬椅子 这个简单动作，必须当该椅子的重量足够小，a g e n t 可以搬 起来的情况下才能进行。 a g e n t 的基本属性i z l 有以下几点： 自治性( a u t o n o m y ) a g e n t 具有自治性，这是所有a g e n t 共性，即某个 a g e n t 可以单独完成简单动作，不借助其他外力或者人为因素。并且可以控制 自己的行为和内部状态。 社会能力( s o c i a la b i l i t y ) a g e n t 具有通讯能力，该通讯能力不仅体现在实 物机器人用传感器等完成，体现在仿真环境中则可以通过信息的编码和解码来 完成。 反应能力( r e a c t i v i t y ) ：a g e n t 具有观察能力，可以根据周围的环境变化作出 相关反应和决策，从而完成目标或者改变环境。 预动能力( p r e a c t i v e n e s s ) ：a g e n t 不仅具有反应能力即能够简单地对环境做 出反应，而且能够通过环境的某些变化预测其下一步的行为。 目前随着对a g e n t 研究的逐步深入，机器人技术的逐步提高，人们对a g e n t 的能力期望逐步加大，一些专家学者，特别是来自人工智能领域的研究人员认 为，a g e n t 不仅应该具有以上定义的属性，而且还应具有一些通常人类才具有 的属性，如知识、目的、信念、义务，情感等。s h o h a m 认为 3 1 ，a g e n t 就是一 种实体，它可以看作是由多种心智状态，如信念、能力、选择和承诺等组成的。 另外，a g e n t 还应该具有其他一些属性，如：移动性( m o b i l i t y ) ，指a g e n t 可以 在互联网上移动，充分利用互联网的优势解决分布式a g e n t 难题。真实性 ( v e r a c i t y ) ，假设a g e n t 没有故意传输错误信息，并且反馈的信息都是准确无误 的。仁慈性( b e n e v o l e n c e ) ，假设a g e n t 之间友好相待，不相互抵触，因此每个 a g e n t 通常有求必应。合理性( r a t i o n a l i t y ) ，假设团队中的每个a g e n t 一如既往 的努力实现总体目标，不故意制造事端，不充当目标的阻碍者，至少在它的信 念应该如此。同时a g e n t 还应该具有一定的情感，可以和用户更好的交互。 a g e n t 与环境交互基本流程如下：从第一个状态开始，a g e n t 随机选择某个 动作，执行该动作并达到某种可能状态。只有当动作执行完毕，第二个状态才 能真正实现。在第二个状态的基础上开始选择新的动作，只有第三个状态真正 实现才能够继续执行新的动作，如此循环反复，是环境状态和动作交替的一个 序列。a g e n t 抽象结构如下： 纯反应式a g e n t ：有一种a g e n t 在决定如何行动时并不参照其历史，它们 的决策完全取决于当前状态。不考虑过去的状态，这种a g e n t 称为纯反应式 a g e n t ，因为它们只是直接对环境做出反应。 有状态的a g e n t ：其思路是认为a g e n t 具有内部状态，这些a g e n t 有内部 数据结构，一般用来记录环境状态和环境的历史。a g e n t 的决策过程基于这种 信息。 单一a g e n t 只能完成简单、单一的动作，然而现实中的大部分工作是复杂 的，需要多个a g e n t 共同完成。这就需要多个a g e n t 之间相互通信，相互协作 完成目标。多a g e n t 系统研究应运而生，重点研究a g e n t 的行为管理，多个a g e n t 构成的复杂系统的原理和a g e n t 之间的协调与交互机制，从而实现多个a g e n t 能选择有利于系统联合目标的行为。、 多a g e n t 系统具有如下特点： ( 1 ) 由多个具有自主性a g e n t 构成，这些a g e n t 是独立的实体，可以分工 完成不同目标，具有各自的行为模型，同时还可以相互通讯： ( 2 ) 处于系统中的单个a g e n t 只具有独立的信息资源，有限的问题求解能 力，不能够实现全局的协作动作，知识和数据分散，是分布式的； ( 3 ) 多a g e n t 系统中的a g e n t 通过交互求解问题，系统不存在全局控制， 即控制是分布的。 智能a g e n t 技术是多a g e n t 系统研究的重点和微观层次，它主要研究单个 a g e n t 的基础知识和构造方法：而多a g e n t 系统高层次的研究主要是关于系统 与系统之间的问题，包括系统的原理与结构、a g e n t 之间的协作关系、系统的 宏观特性以及a g e n t 个体行为产生的社会意义等问题。 多a g e n t 系统研究内容和范围比较广泛，目前研究热点主要从以下四个方 2 面进行探索： ( 1 ) 关于a g e n t 个体的研究：主要探讨多a g e n t 系统中各子类a g e n t 的组 织结构、基础知识、行为决策等个体方面的性质： ( 2 ) 关于多a g e n t 群体协作技术的研究：主要探讨多a g e n t 系统的高层性 质，包括多a g e n t 系统的组织关系和结构关系、a g e n t 之间的通讯、整体行为、 协同、协商、多a g e n t 规划【4 】、相互影响1 5 等； ( 3 ) 关于一些特定的系统组织方法的研究：如分布式开放式系统、多a g e n t 组织设计、类市场机制、智能协同的信息系统等； ( 4 ) 关于设计与开发方法的研究：如建造多a g e n t 系统、测试床、设计工 具以及多a g e n t 系统应用的方法与实现技术【6 】【7 】等。 目前关于多a g e n t 之间协作的研究热点在于如何有效的实现分布式a g e n t 之间更好的协作。很多相关领域专家给出不同的解决方案，其中普遍的方法是 采用集中控制管理，由某管理者a g e n t 统一分配任务并负责控制他们的行为。 但是由于多a g e n t 系统往往是研究在动态、不可预测环境中进行问题求解，如 果每一时刻的各个a g e n t 的行为都需要由集中控制机制来决定的话，会造成时 间和空间上的不可解，这样协作问题根本无法解决。 为此，研究人员提出了以下三种解决途径： ( 1 ) 统一a g e n t 约定和规则，采用黑板方式公开各自的信息，从而在规 范其行为同时，有效了解单一a g e n t 的作为，实现总体部署，避免冲突； ( 2 ) 扩充a g e n t 之间的通信手段，如统一编码或者通过红外遥感等方法 实现a g e n t 之间更多的通信和交流，从而a g e n t 之间能避免冲突和增进协作关 系； ( 3 ) 增加部分学习机制，使得a g e n t 能够在执行任务过程中不断学习， 改进不足，吸取经验，为以后更好的协作。 可见，一方面，为多a g e n t 系统增加学习机制是有效地实现协作的一种重 要途径；另一方面，为多a g e n t 系统增加协作机制也能改善多a g e n t 学习的性 能。两者相互促进，相得益彰。 1 2 多a g e n t 协作技术研究背景 多a g e n t 系统可定义为由多个a g e n t 构成的可以相互通讯相互协作共同解 决问题的一个系统，这些a g e n t 一起工作可以解决很多复杂问题，完成复杂动 作和目标，超出单个a g e n t 能力。多a g e n t 系统作为分布式问题求解整体，除 具有单a g e n t 的特性外，还具有如下特点：数据是分布或分散的；计算过程异 步、并发或并行；每个a g e n t 具有不完全的信息和问题求解能力，不存在全局 的集中控制；a g e n t 之间可以交互、动态自组织、协调以及合作，从而大大提 高求解问题的能力。 关于多a g e n t 协作的研究，近年来引起人们广泛的兴趣。国内外研究多 a g e n t 协作最多最广泛也最成熟的算法包括强化学习算法，神经网络算法，马 尔科夫决策算法，遗传算法等。 多a g e n t 机器学习 8 1 算法方面，l i t t m a n 提出基于零和对策提出了达到平衡 点的学习算法。h u 和w e l l m a n 给出了在非零和对策论【9 】基础上的算法，并证 明了这种算法的收敛性。上述两种算法的共同特点是智能体采用联合行动，且 都具有彼此间的完备信息( 对策结构、状态转移概率、奖赏函数) 。c l a u s 和 b o u t i l i e r 研究了协作的多智能体决策过程【l o 】，比较了a g e n t 独立学习和联合 学习的差别，但无法保证这两种学习收敛到平衡点，对此他们给出一些加强联 合学习的建议。另外，w o l p e r t 等为每个智能体建立了各自的奖赏函数，但该方 法使学习过程的分析复杂化，并增加了计算代价。 m a r k o v 模型的特性在于，下一周期的状态只跟当前状态有关，与历史信息 无关。这对于多a g e n t 协作通常具有反复性和随机性来说，m a r k o v 对策正好 可以解决该问题，因此可以用于建立动态的多a g e n t 协作交互模型。强化学习 是一种交互式的学习方法，是指a g e n t 不断的从环境中学习新的知识，用于改 变环境，并更好的适应新的环境。强化学习算法和m a r k o v 模型相结合更适应 于解决a g e n t 之间的协作问题。 强化学习算法中最适应与解决仿真环境中算法是q 学习算法，该算法是由 w a t k i n s 1 1 j 在19 8 9 年提出的。它提供a g e n t 在马尔科夫环境中利用经历的状态 动作序列选择最优动作的一种学习能力。并且不需要建立环境模型。q 学习算 法是一种基于m a r k o v 过程的递增式动态规划算法。该算法是强化学习的一种 有效的基本算法，并且适宜于扩展到多a g e n t 协作的协调学习过程。q 学习算 法实际是马尔科夫决策过程m d p ( m a r k o vd e c i s i o np r o c e s s e s ) 的一种变化形式。 w a t k i n s 采用l o o k u p 表来表示输入状态，证明了q 学习的收敛性【1 1 1 。 q 学习算法在强化学习领域受到了普遍关注，针对该算法的改进也层出不 穷。在w a t k i n s 的q 学习原型中，a g e n t 在每一个状态下选择下一步的行动时 采用贪心策略，针对w a t k i n sq 学习的这个特点有发展出了许多改进。其中p e n g 在19 9 6 年提出了增量式多步q 学习【l 引，即q ( 旯) 算法，它结合了q 学习和t d ( 见) 回报的思想，利用将来无限多步的信息更新当前q 函数，并给出了基于资格迹 的实现算法。w a t k i n sq 学习和q ( 旯) 存在两个极端，前者利用了一步的信息， 预见能力不强，后者对大量的状态动作对s a p ( s t a t e a c t i o np a i r ) 的q 值和相应 的资格迹矩阵进行更新，当状态动作这个空间规模很大时计算量较大，学习效 率不高。 基于神经网络算法的多a g e n t 协作在最近几年也得到进一步的深入研究，比如可 以通过构建b p 网络学习单个a g e n t 的动作，以环境信息和状态作为输入层，通过不 断的与环境交互，调整学习因子，学习得到适应的动作作为输出层。同时神经网络算 4 法和理论的进一步研究和深入，目前可以通过神经网络学习多个a g e n t 的协作技术。 比如可以通过输入不同a g e n t 的位置，速度，状态等信息，学习训练得到总体的协作 阵型，决策等。 1 3r o b o c u p 2 d 中的多a g e n t 协作技术 r o b o c u p 2 d 比赛属于机器人足球世界杯【l 列( 简称r o b o c u p ) 的仿真组。首先 介绍一下r o b o c u p 的相关内容。r o b o c u p 是一个国际性的比赛项目，通过提供 一个标准平台作为比赛来促进人工智能和机器人技术的发展。参赛对象包括各 教育机构，相关机器人技术的企业等，可以团体报名也可以单个参加比赛。每 年举行一次，当然各国家也可以组织相关的国内赛。目前比赛项目包括：( 1 ) 仿 真组比赛；( 2 ) 小型机器人组比赛；( 3 ) 中型机器人组比赛；( 5 ) s o n y 有腿机器人 比赛；( 6 ) 类人机器人组比赛；( 7 ) 机器人舞蹈比赛；( 8 ) r o b o c u p 展示会。各组 别主要可以归为两类即仿真组和实物组。仿真组的特点主要是机器人竞赛委员 会提供一个标准的仿真平台和相应的s e r v e r 程序，各参赛队负责编写客户端程 序参加比赛。仿真组的平台都是高度模拟现实中的实物比赛场地，包括模拟实 际环境中的噪音和阻力等因素，只要有计算机就可以参赛，节省经费，同时仿 真程序可以直接移植到实物比赛中，方便可行。实物组机器人的研制主要涉及 物理，传感，遥控，精密机械，计算机等领域。其主要特点更具有形象性和实 用性。 组织各高校和科研机构进行的机器人足球比赛，是当前人工智能领域的研 究热点之一，也是主要的研究平台。创立机器人世界杯足球赛的目的是促进人 工智能和机器人学的研究，通过足球这个具有普遍意义的平台，来评价各种理 论、算法和a g e n t 的体系结构。r o b o c u p 仿真2 d 组以它特有的特性作为研究 多a g e n t 协作的最佳平台。研究实物机器人有易损坏、高投入的缺点，研究门 槛比较高。许多高校因此望而却步。 r o b o c u p 涉及到的研究领域包括智能机器人系统、多智能体系统、实时模 式识别与行为系统、智能体结构设计、实时规划和推理、基于网络的三维图形 交互、传感器技术。其技术特点有：动态实时系统、分布式合作与协调、带噪 声非全信息的环境模型、非符号化的环境信息、受限的通讯带宽等。 p e t e rs t o n e l l 4 j 主要研究分层学习，并将该方法体现于r o b o c u p 2 d 仿真组的 研究当中，在设计机器人的底层动作和高层决策时候，采用分层学习的方法。 他把学习分成底层基本动作层和高层复杂决策层，在不同层次采用不同学习方 法实现，高层决策建立在底层基本动作基础之上。葡萄牙里兹本大学队是2 0 0 0 年r o b o c u p 仿真组的冠军，他们的主要特点是将现实中人类足球的知识充分应 用在机器人球队中，并通过建立准确的世界模型来实现。由于环境具有噪声且 部分可观，如何利用得到的信息去推测当前的世界模型成了问题的关键。往往 这种利用得到有噪音的信息去推测是有偏差，不精确的。 卡尔斯鲁厄大学l l5 j 以再励学习( r e i n f o r c e m e n tl e a r n i n g ) 为主要研究方向。 再励学习的基本思想是让a g e n t 自主的决策，只传递a g e n t 要达到的基本目标 信息，如要完成一定的进行任务等。此时，a g e n t 必须要通过在环境状态中不 断再励学习策略和技能以达到该目标。再励学习在r o b o c u p 遇到的最大的两个 挑战是： ( 1 ) 再励学习最初是以离散空间为求解空间设计的，而r o b o c u p 环境是 连续的； ( 2 ) r o b o c u p 中的再励信号延迟太长，因为只有进球才是最本质的再励 信号。从思维的层次上说，再励学习模仿的更多的是人较为低级的智能行为， 它很难表现如推理这类人类思维中较高级、较抽象的行为。 荷兰阿姆斯特丹大学【1 6 l r o b o c u p 仿真小组开发了多线程的三层a g e n t 体系 结构，柔性的a g e n t 环境同步机制，并用粒子滤波算法实现了定位和速度估计。 框架清晰，脚法流畅，其源代码是球队开发处于起步阶段的首选。实践表明， 粒子滤波算法定位和对速度的估计对a g e n t 的历史信息考虑不周全导致预测结 果不精确，会对比赛的高层决策带来影响。 清华大学【l7 j 的仿真小组以“层 作为a g e n t 的系统结构，使用神经元网络 实现全队的基本阵形。在不改变a g e n t 本身结构的基础上，将上层的行为指导 以战术方式给定，使多个a g e n t 产生有意识的局部合作行为，并根据行为的结 果对行为指导进行合适的调整。随着s e r v e r 的不断更新，新的铲球，加速，体 力模型发生变化，这种方法已经不适应a g e n t 协作决策问题。 中国科技大学的蓝鹰队采用基于效用【1 8 】的决策方法，对所有可能的行为进 行概率分析，并对每个行为可能导致的不同结果做效用评价，执行期望效用最 大的行为。他们还对球员进行建模和预测，将信息的不确定性引入决策考虑中。 基于效用的决策方法意义明确，实现简便，但是由于对所有可能的行为进行概 率分析没有站在分析对象的立场去考虑问题，从而有一定的改进和提升空间。 本文采用有的放矢，保留以上方法中的优点比如采用u v a 作为底层开发基 础，继续使用多线程的三层a g e n t 系结构，考虑仿真空问状态连续性，环境动 态性，信息噪音性等特点，提出了换位思考模型研究多a g e n t 协作技术的新方 法，即站在被分析对象的立场去估计分析其所有可能的行为概率，利用教练 a g e n t 抽象出行为模式，结合强化学习算法，执行期望概率最大的行为决策。 r o b o c u p 2 d 中存在以下实际问题： 在实际r o b o c u p 2 d 仿真比赛中，某个球员a g e n t 由于突发情况，决策突然 改变导致协作失职，团队目标在紧急状态下的改变，紧急的进攻和防守形势等 都是不确定因素，对团队的目标即比赛得分会带来不确定的影响。一个好的协 作势必能够足够限度的包容这些不确定因素，实时的根据突发情况发生调整， 6 改变原有的协作思路，促进特定状态下新的协作。但是目前的团队协作模型很 大程度上不具有这种灵活性，团队协作在这个领域中还没有真正意义上的体现。 针对协作在该方面存在的问题，本文在协作决策之前，动态的对a g e n t 建模， 比如动态预测对手的角色类型，活动区域，异构类型等，实时的得到这些特征 并不断的更新预测结果，从而适应协作决策中出现的突发情况。 另一方面，基于仿真比赛平台的多a g e n t 协作研究都只考虑了主动性a g e n t 的周围环境，而没有站在协作a g e n t 的立场和周围环境去考虑协作决策问题。 比如采用基于效用的决策方法，对所有可能的行为进行概率分析，并对每个行 为可能导致的不同结果做效用评价，执行期望效用最大的行为。对所有可能行 为进行概率分析过程中没有换角度的站在被分析a g e n t 的环境中进行统计，因 此这样的决策结果是存在不足之处的。针对该问题，提出换位思考模型结合强 化学习方法研究r o b o c u p 2 d 中的新方法。 再次，团队协作挑战重点强调团队的实时计划、重新计划以及在动态对抗 环境中多a g e n t 团队协作的执行能力同时，仿真足球赛中团队协作模型是否能 够应用到其他非机器人足球赛领域也被作为衡量团队质量的一个因素。本文给 出了换位思考模型在r o b o c u p 协作进攻和防守的应用。同时换位思考思想也可 以应用在机器人避障，机器人救援等多个领域。 i 4 本文主要工作 本文首先分析了多a g e n t 协作研究背景及研究现状；其次分析了 r o b o c u p 2 d 中的队友模型理论，在此基础上提出了换位思考模型，并给出了换 位思考模型在多a g e n t 协作进攻中的应用；然后对对手a g e n t 的角色，频繁活 动区域，异构类型进行分析预测，在此基础上给出了换位思考模型在协作防守 中的应用。 换位思考思想应用在队友协作进攻中即，设身处地在队友的周围环境状态 中预测该队友的模型是传球，带球，射门等等，从而根据该队友的决策去协助 其进攻。 换位思考思想应用在协作防守中即，在分析得到对手a g e n t 的角色，区域， 异构类型等特征之后，设身处地在该对手的客观世界中，预测其进攻模式，并 根据对手的决策去防守。 论文共分5 章，主要结构如下： 第一章分析了多a g e n t 协作研究背景，研究内容和必要性，总结了其他 r o b o c u p 球队研究协作的方法，在此基础上提出了本文采用换位思考模型研究 协作的新方法，并概括了本文研究的主要内容。 第二章提出了换位思考思想，并利用教练智能体作为分布式和集中式之间 的桥梁以分析球队中某一a g e n t 的队友智能体的行为模式，并利用改进的q 学 7 习方法预测出队友协作进攻的决策。该方法在协作传球应用中取得了很好的效 果。 第三章针对对手特征进行建模，包括对手智能体的角色分工预测、对手智 能体的频繁活动区域预测、对手智能体的异构类型预测等，最终形成了对手的 特征模型，为协作防守提供依据。 第四章利用第三章得到的对手特征模型，预测其行为，应用到我方协作截 球中，并且与传统的数学截球方法比较，实验证明该方法具有更好的优势。 8 2 1 引言 第二章换位思考模型在多a g e n t 协作进攻中的应用 r o b o c u p 2 d 仿真比赛是基于一个模拟现实人类足球的标准计算机仿真平 台，该平台模拟了噪音，视觉局限性，阻力等因素，采用c l i e n t s e r v e r 方式， 由r o b o c u p 联合会提供s o c c e rs e r v e r 系统，参赛队编写各自的客户端程序，模 拟实际足球队1 1 名队员进行比赛。这是一个典型的动态复杂环境下m a s 应用 研究平台。 在复杂实时比赛环境中，由于每个球员的时间资源和信息资源存在局限性， 如何在有限时间内解决多a g e n t 协作冲突问题是研究重点。因此必须设计一个 最优方法使得团队的协作利益最大化。因而m a s 研究重点在于使功能独立的 智能体通过协商，协调和协作，完成复杂的控制任务或解决复杂的问题。在 r o b o c u p 仿真比赛中，每个机器人都是一个a g e n t ，它们都是具有相似思维方 法的自治系统，都能利用局部信息进行自主决策，并通过人工智能方法和自适 应策略解决局部冲突，最终实现多个机器人智能体的协作，共同完成团队策略。 r o b o c u p 仿真比赛中，每个a g e n t 都有自己独立的一套世界状态信息，并 且该信息是随着比赛时间推进而不断更新的。同时该信息不具有全局性，存在 视觉和感知噪音，单个a g e n t 根据自己内部的状态和采用的动作模块做出局部 的独立决策。由于a g e n t 仅能得到有限视觉范围的感知信息，而且有限的信息 也带有噪音，因此维护一个精确的世界状态模型对a g e n t 的决策具有重要意义。 随着r o b o c u p 仿真技术的发展，已经出现了一些对a g e n t 行为进行预测， 来实现对a g e n t 的世界状态模型更新的深入研究，比如：利用模糊q 学习算法 分析a g e n t 的历史速度，位置等信息，从而预测其行为；利用遗传算法预测a g e n t 行为：应用神经网络原理，输入a g e n t 状态信息，预测输出a g e n t 行为。分析 研究发现，这些传统的方法在对其他球员a g e n t 行为进行预测时候只考虑了当 前a g e n t 的周围环境，而没有考虑所被预测的a g e n t 的实时环境，从而造成预 测信息不准确，r o b o c u p 比赛中体现为a g e n ta 不了解a g e n tb 的意图，不能 够根据a g e n tb 的意图做出正确的协作决策。 本章在分析上述研究方法基础上，提出一种基于换位思考模型的多a g e n t 协作研究新方法。利用教练a g e n t 对a g e n t 信息的准确获取的能力，对队友a g e n t 建模，考虑了被预测a g e n t 的周围环境，从而提高了预测准确度。 换位思考并不是真正交换位置，而是从其他智能体角度模拟思考其意图，做出 协作或者对抗决策，换位思考的示意图如图2 1 ： 9 图2 - 1 看出在紧急比赛状态下，3 号球员从2 号球员角度模拟其意图，通 过数理统计和建模等方法得到其周围的环境状态，得出2 号此时更有利于阻断 对手射门，因此发出通讯请求2 号暂时代替3 号原有角色执行防守任务。 豳2 - 1r o b o c u p 中的换位思考情景翻 本章主要是对队友a g e n t 的换位思考，增强队友之间的协作。 文章内容结构如下： 首先提出换位思考模型：其次介绍了换位思考模型思想和利用该模型学习 最好的协作动作；最后介绍该模型在p , o b o c u p 传球中的应用举例。 2 2 换位思考模型 2 2 1 换位思考模型概述 在研究多智能协作中，前面提到的方法都是根据当前a g e n t 所处的周围环 境感知其他a g e n t 的信息，并应用机器学习等算法预测a g e n t 行为模式，从而 做出相应的决策。文献f 1 9 1 介绍一种基于遗传算法预测a g e n t 行为模式的方法， 该算法针对特定环境预测的结果，不具有适应突发情况的能力。作为研究基础， 接下来首先概述换位思考模型。 换位思考模型是为了减少a g e n t 有限视觉范围获取的信息做出的决策误差 而提出的新模型。该模型的核心思想是利用教练建模预测a g e n t 行为模式，并 更新世界状态模型，这样每个a g e n t 可以预测其他a g e n t 的行为模式，从而得 出自己最佳的协作策略。图2 - 2 显示换位思考模型图。 图2 - 2 换位思考模型图 由于仿真比赛环境是动态和随机的，可以假定每个周期a g e n t 的行为是正 态分布的( 备注：a g e n t 是独立决策的) ，独立正态分布之和服从z 2 分布。因此 我们可以利用z 2 分布预测a g e n t 的行为模式。 在线教练( o n l i n e c o a c h ) t 2 0 】通过感知器获取环境中所有球员a g e n t 无噪音 信息，利用z 2 分布计算得到模式即下个周期a g e n t 的行为模式，比如带球模式， 传球模式，持球模式等。这样a g e n t 可以得到其他a g e n t 的精确模型，根据换 位思考得到的模式，选择最好的动作执行，并发送该动作到服务器执行。以上 是一个周期的循环，只要s e r v e r 不中断，在线教练将持续建模并更新，从而保 证a g e n t 得到的信息都是最新信息，能够适应突发情况。 利用换位思考模型构造多a g e n t 协作框架可以总结如下： 首先，教练通过感知器感知到所有队友的当前信息，包括位置，速度，身 体角度等； 其次，教练利用当前信息，根据高斯分布抽象出a g e n t 行为模式，比如带 球，传球，射门等模式，然后，将新的模式反馈给环境； 再者，队友a g e n t 感知到新的行为模式，利用改进q 学习得到最好的协作 动作； 最后，执行决策； 本章主要工作在于教练对队友建模和q 学习协作决策。 下面重点研究教练对队友建模。 2 2 2 在线教练介绍 一支完整的球队包括球员和教练，球员与教练的配合情况直接影响到比赛结果。 相比于人类足球，r o b o c u p 仿真环境也定义了教练概念，但仿真教练有很多特别之处， 本章将从教练模型、教练分类、教练的功能及权限等角度对教练a g e n t 进行深入研究， 重点研究教练a g e n t 如何分析得到对手异构类型，这样可以得到更多的关于对手的世 界模型，从而球员a g e n t