清华大学毕业设计论文目录第一章背景介绍 (1)第二章设计理念和决策框架 (3)2.1设计理念 (3)2.2决策框架 (4)第三章截球技术的实现 (6)3.1 问题介绍 (6)3.2 RoboCup仿真环境的运动模型 (6)3.3二分法求解 (7)3.4 训练作截球判断的BP神经网络 (8)3.5 比较和总结 (9)第四章脚法的实现 (10)4.1 问题介绍 (10)4.2 再励学习（Reinfocement Learning） (10)4.2.1再励学习简介 (10)4.2.2 Bellmen最优方程 (12)4.2.3 动态规划算法简介 (12)4.2.4 Q学习算法简介 (13)4.3 用再励学习训练脚法 (13)4.3.1 Kalsruhe Brainstormers 的方法 (13)4.3.2 我们的实验结果 (14)4.3.3 我们的方法 (15)第五章仲裁算法 (19)5.1 问题介绍 (19)5.2 RoboCup仿真环境中队员的观察模型 (19)5.3 仲裁算法 (20)5.4视野宽度的决策 (23)第六章传球线路的搜索算法 (24)6.1 问题介绍 (24)6.2 传球线路搜索算法 (25)6.2.1 简单的搜索算法 (25)清华大学毕业设计论文6.2.2 优化搜索算法 (25)6.2.3 穿越速度的计算 (28)第七章防守体系 (29)7.1 问题介绍 (29)7.2 角色的定义 (29)7.3 阵形的定义 (30)7.4 一个简单的防守系统 (30)7.5 考虑全局利益的防守系统 (31)7.5.1 考虑全局利益防守体系介绍 (31)7.5.2 求解全局利益最优的防守方案 (32)7.5.3 实战效果 (32)7.5.4 缺点 (33)第八章 TSINGHUAEOLUS的程序结构 (34)参考文献 (36)致谢 (37)清华大学毕业设计论文第一章背景介绍机器人足球世界杯(RoboCup)是国际上一项为促进分布式人工智能、智能机器人技术及其相关领域的研究与发展而举行的大型比赛和学术活动。

它通过提供一个标准的比赛平台来检验各种智能机器人技术。

它的最终梦想是能在2050年发展出能打败人类足球运动员的机器人足球队。

RoboCup仿真组重点研究多个智能体（MultiAgent）的竞争与合作的关系。

设计RoboCup仿真比赛程序面临的主要难点在于：在连续空间作连续的决策；多个智能体的存在给状态空间带来维数灾难；环境的反馈延迟太长。

环境具有强实时性和动态性；环境通讯带宽很窄；环境有噪声；环境具有部分可观性；环境不具有马尔可夫性；前三点使得直接利用从环境中的得到的信息和反馈进行决策几乎不可能实现。

曾经有球队直接利用遗传算法（Genetic Algorithm）训练球队，效果并不好。

巨大的状态空间和长延时的反馈特性使得RoboCup的研究者纷纷转向分层的决策结构。

Peter Stone在他的博士论文中把层学习的方法运用于RoboCup 的研究当中。

他把决策分成底层技术层和顶层决策层，在不同的层次采用不同的方法决策，上层决策构筑在下层决策基础之上。

其实，层学习的概念非常的简单，当整个复杂的决策任务被分层，分到每个层次的决策任务都变成简单可行了。

第1页清华大学毕业设计论文汉堡大学采用Case-base的思想研究RoboCup。

其主要想法是利用定义各种典型的场景，根据当前场景和典型场景的匹配度来进行决策。

可以设想，这种方法无法克服状态空间巨大的问题，而且很难跟得上环境对动态性的要求。

卡尔斯鲁厄大学以再励学习（reinforcement learning）为他们的主要研究方向。

他们的梦想是能够做到仅仅告诉智能体去完成进球的任务，而智能体能够自主的通过和环境的交互，学习各种技能甚至是策略。

再励学习在RoboCup中遇到的最大的两个挑战是：一、再励学习最初是以离散空间为求解空间设计的，而RoboCup环境是连续的；二、RoboCup中的再励信号延迟太长，因为只有进球是最本质的再励信号。

从思维的层次上说，再励学习模仿的更多是人较为低级的智能行为，它很难表现如推理这类人类思维中较高级、较抽象的行为。

关于再励学习的问题，本文第四章“脚法的实现”有所涉及。

葡萄牙的里兹本大学队是2000年RoboCup仿真组的冠军，他们的主要特点是充分利用人类足球的知识和建立准确的世界模型。

由于环境具有噪声而且是部分可观的，如何充分利用得到的信息去推测当前的世界模型成了比赛的一个关键所在。

RoboCup的仿真比赛的场景如下图：图1 RoboCup仿真比赛场景第2页清华大学毕业设计论文第二章设计理念和决策框架2.1设计理念由于状态空间的过于庞大以及反馈延迟过大，不融入任何先验知识来设计决策几乎不可能实现。

许多非常简单的概念如：带球、截球、射门、传球等要让智能体从与环境的交互当中总结出来，而且组织成知识都是十分困难的。

从人类自身获取知识的途径来说，通过教学活动的占了很大的比例。

基于以上考虑，我们认为一个融入人类的先验知识，并且能在一定程度上自主学习的决策系统是一个有价值而且可行的设计目标。

人类的知识主要作为框架和建议的形式存在。

比如人类可以不加思索的把决策分成控球和无球，进攻和防守，如果还有点足球知识的话，带球、截球、传球、射门几类。

在我们的决策体系中，这些概念都是事先假定的，也就是我们所谓的以框架的形式存在。

作为建议的人类知识通常以限定求解的方向的形式存在。

这就类似于启发式搜索的思想，利用外来的信息来加速搜索，当然形式不限于此。

还有一部分人类知识以教练的形式存在，如角色、角色行为的定义、阵形、定位球配合等等。

环境的复杂性使得我们不可能全部通过先验的知识来确定智能体每一时刻的行为，而且人类的知识不能完全适合模拟环境。

智能体本身具有学习和适应能力，能够自己从环境中获取知识，也成为决策系统是否成功的关键所在。

目前流行的自适应学习的算法有BP、动态规划、Q-learning、遗传算法等。

当运用于决策时，这些学习算法普遍面临的问题是能处理的问题形式单一，能力有限。

如何能合理的把这些学习算法获取的知识运用在决策体系中，使之能够处理形式复杂的各种决策场景，也是我们研究的一个重点。

第3页清华大学毕业设计论文2.2决策框架在纵向，我们采用了分层的结构，分成基本动作层和策略层两层；在横向，我们按足球的各个基本的战术动作来划分模块，分成截球、传球、带球、射门、跑位、视觉、通讯几个模块。

每个模块由底层的基本动作和上层的决策策略构成。

底层评价在不考虑战术利益情况下动作的合理性（feasibility）。

而上层策略层结合战术利益，对候选动作进行进一步的评价和仲裁。

模块内部的候选动作先进行局部竞争，然后再提交给更上层的仲裁器进行模块之间的仲裁。

概括的说，总体的结构是一个分层、分模块的多级评价仲裁器。

结构示意图如下：图2 决策系统结构之所以采用多级仲裁和局部竞争是由于模块的评价器往往对同一模块内的候选动作评价有合理性，而在模块之间就失去可比性了。

尽管如此，模块的评价结果至少表明了该候选动作在目前环境中的适应程度，也即在目前状况下执行该动作的好坏，只不过不同模块之间用来评价好坏的标准不同。

模块之间的仲裁器可以等价于一个平衡标准的动态加权器，对不同模块之间的评价结果进行动态加权，使它们具有可比性。

这个全局的动态仲裁器，可以根据实际的比赛效果来学习调整，也可以由人类足球专家进行建议。

比如设计者可以有意的第4页清华大学毕业设计论文加重传球动作的权值来向智能体灌输多传球的战略意图。

接下来的几章将依照模块为序介绍几个重点的技术的设计与实现，第三章介绍截球技术，第四章是踢球技术，第五章是仲裁算法和视觉决策，第六章搜索传球线路的优化算法，第七章防守跑位体系，第八章简要介绍一下程序的结构。

第5页清华大学毕业设计论文第三章 截球技术的实现3.1 问题介绍对球运动的判断是足球运动员需要具备最基本的素质。

仿真环境物理模型与实际比赛球的运动的物理模型有很大差异，即使是在人类足球比赛当中由于存在不同的场地条件和不同的天气条件，球运动的物理模型也会不同。

所以对于一个人类足球队员来说，最基本应该具备适应比赛场地的能力，对于我们的仿真队员也是一样。

截球技术需要解决的就是对球运动的判断，从而作出正确的截球决策，它是其他决策的基础。

我们把截球问题归纳成如图3的一个简单的场景：白点代表球，红色的圆圈代表球员，dist 为球员到球的距离，a 为球到球员之间的连线和球运动方向的夹角，speed 为球的即时的运动速度。

球的速度随运动衰减。

截球问题归结为给定dist 、a 和speed ，决策出队员正确的截球角度b ，或者是当截到球时，球运动的距离，并给出对截球所可能花的时间的估计。

在介绍截球的算法之前，下一节将先对RoboCup 仿真环境中的运动模型做简单的介绍。

图3 截球场景3.2 RoboCup 仿真环境的运动模型在RoboCup 仿真环境中，时间被离散为周期，所以运动也是离散的。

物理模型由下面的公式决定：（u ）=（v ）+（）：accelerate11,++ty t x u ty t x v ,ty t x a a ,（）=（）+（u ）：move 11,++ty t xp p ty t x p p ,11,++ty t x u 第6页清华大学毕业设计论文（v ）=：decayspeed11,++ty t x v ),(11++×ty t x u u decay （）=（0）：resetacceleration 11,++ty t xa a 0,其中t 表示周期，（）和（）分别表示t 周期物体的位置和即时速度，（u ）为t-1到t 周期物体的平均速度。

Decay 是一个运动的衰减因子，球的衰减因子为0.94，球员为0.4。

（）表示对象的加速度，球的加速度由踢球动作（kick ）获得，球员的加速度由冲刺（dash ）获得。

ty t x p p ,ty t x v v ,ty t x a a ,ty t xu , 仿真环境中的截球问题，等价于解一个由上面公式确定的球的运动轨迹和球员运动轨迹的交点。

只不过在这里我们假设球在运动过程中不会获得加速度，也就是不考虑球在过程中被踢的情况。

因为球员可以不断冲刺使自己保持匀速，所以我们假定球员的运动为匀速，这有助于简化问题。

下面将介绍我们采用的两种求解算法，然后进行比较，并且提出可能的改进方案。

第一种二分法假设了物理模型，第二种BP 网络求解的方法没有假设物理模型。

3.3二分法求解这个算法的原理比较简单，见图4.1。

这里我们求解的目标是当截到球时球运动的距离。

假设球员沿着绿线的方向尝试截球，当球员跑到球的运动轨迹上时，根据球的运动模型，可以估计球这时所在位置，假设如红点所示。