球队决策策略

第7章球队决策策略本章的主要内容Robocup球队策略里面应该包含的那些内容。一个经典的跑位规划方法―FCPortugal的SBSP(SituationBasedStrategicPositioning)介绍了一个局部战术配合3Vs.2战术。一般进攻体系的设计，主要包含进攻队员的动作选择，一般队员的协同以及跑位。一般防守体系的设计，涉及到防守点的选择，防守动作的评价、守门员的防守的动作等方面的内容。7.1Robocup球队策略综述从足球比赛的角度来看，体现球队整体策略的就是球队的整体进攻和防守体系，当所有球员都按照相同的决策框架来进行决策时，球员的决策依据都相同，对其他队员的预测就比较准确，整个球队就能够体现出一定的协调性了。当Agent间的意愿一致的时候他们就会进行协作，当他们的意愿不一致的时候，就要进行协商，处理矛盾。Remco在他的论文中对球队的整体策略进行了一下归纳。7.1RoboCup球队策略综述(1)．整体策略指定了队伍的阵型以及其中队员的位置。更进一步，它可以决定什么情况下应该采用什么样的阵型。(2)．整体策略定义了阵型中不同的角色，并把角色分配给不同位置的球员，同时确定哪种异构球员适合哪种角色。(3)．对于每种类型的球员（后卫，中场，前锋等）球队策略应该根据它的角色确定分配给他哪些相应的行为。如对一个防守队员来说，一般它应该比进攻队员保守，它选择的动作也应该是偏向防守的。7.1RoboCup球队策略综述(4)．整体策略一般还包括球员应该如何根据场上形势来调整行为的信息。比如在特定的策略下，一个球员在对自己的动作进行选择的时候应该考虑到位置和位置所在的区域，同时还要考虑队友和对手的位置。(5)．整体策略应该指定如何协调各个球员的行为．因为不同的球员由于感知的不同，在策略的执行上可能出现不协调。如何减小这种潜在不协调的危险是策略的一部分。(6)．整体策略还应该能够在比赛中合理的管理球员的体力。如球员在比赛中如果自己的体力特别低，除非万不得已一般尽量减少跑动以恢复体力。7.1RoboCup球队策略综述此外，球队的整体策略还应该考虑其他一些因素。比如说(1)．对手的强弱。对强弱不同的对手的动作是不一样的，如对手的截球能力强在传球的时候对传球的细节考虑就应该更细一点，对手弱，考虑的就少一点，可以为追求更好的结果而采用更加冒险的传球。(2)．对方球队的整体倾向。如对手是倾向于进攻还是倾向于防守。(3)．比赛的场上情况。比如说场上的比分，是落后还是领先。7.1Robocup球队策略综述(4)．场上是否处于关键状态。如我们已经攻入对方禁区或对手攻入我方的禁区采取紧急动作。(5)．其他一些因素。是否考虑换人、是否考虑球员类型的转换等等。在设计的时候应尽量考虑到上面的情况。7.2基于场上形势的战术跑位(SBSP)SBSP首先是由FCPortugal提出的，它是结合了PeterStone在CMU球队里面的阵型和位置的概念，并在此基础上面引入了战术、场上情况、队员类型等概念。SBSP的一些定义SBSP的一些定义（续）SBSP的一些定义（续）SBSP的一些定义（续）SBSP的使用SBSP的使用（续）SBSP的使用（续）最后得出了球员(Agent)在场上的战略跑位：SBSP小结SBSP是一个比较成功的球队整体策略的应用。它的基本思想是把场上状态分为积极的和战略的。球员的策略也分积极的和战略的。当场上状态是积极的时候，一般这是也就是关键的时候，如已经攻入了对方禁区，或进行战术配合的时候，这时Agent就不在考虑在进行高层的决策直接采用反应式的方式，如进入禁区面对守门员形成单刀，这是只有一个动作选择，那就是射门。当场上状态进入战略状态的时候，如进攻时，控球队员是处于积极状态，它进行动作的选择，其他队员都进入战略状态，这时它们的选择就是跑位，这就是使用SBSP，跑到一个战略位置。防守时在考虑盯人、阻截球的情况下，其他队员就要选择合适的位置进行跑位。这时使用的也是SBSP。SBSP的一般算法IF场上是战略状态IF本方进攻进攻球员进行动作选择、其他队员按SBSP跑位ELSE防守队员截球、盯人、按SBSP跑位ELSE采用积极状态下的即时动作设计RoboCup仿真比赛程序的主要难点：在连续空间作连续的决策；多个Agent的存在给状态空间带来维数灾难；环境的反馈延迟太长。环境具有强实时性和动态性；环境通讯带宽很窄；环境有噪声；环境具有部分可观性；环境不具有马尔可夫性；7.3强化学习实现局部战术实际上，机器人足球比赛中的动作选择可以看成是在一定的环境下Agent在自己获取的世界状态(s)情况下的选择什么样的a,由于系统实现的时候引入了噪音，因此环境不具有Markov性，也就是不可再现性，原则上说他就不具有使用强化学习的可能。当如果简化这些影响，也可以把这个过程看成马尔可夫过程，进而采用强化学习的方法。强化学习的关键是Agent与环境的交互可以看成是一个马尔可夫模型，也就是说，环境应该具有再现性。7.3强化学习实现局部战术在Robocup中，我们考虑“战术”任务是这样一种情况：进攻一方在一活动范围内试图保持控球权，同时另一方试图夺回控球权。无论何时防守方获得控球权或球离开此区域，这个时间段就结束，球员便放置到另一个时间段（进攻方再次被给予控球权）。7.3强化学习实现局部战术区域设定为20M*20M的正方形，并总有3个进攻队员和2个防守队员。球员涉及的动作主要有：HoldBall()：持球，持球保持静止并尽可能远离对手。PassBall(f)：传球，将球直接踢给f。GotoBall()：跑向球。GetOpen()：跑位，跑到一个空旷的位置，在这个位置能得到传出的球。所有防守方都采用固定的策略GOTOBALL()，也就是说他们试图阻截球，拿到球后用HOLDBALL()保持控球权。在学习的时候，使用一个全能的教练Trainer(也是agent)在控制比赛，当防守队员在设定时间里获得控球权或球离开区域时Trainer就结束此时间段，就完成了一次对抗。在每个时间段开始，他在区域内随机的置球和球员的位置，两个防守方队员从区域的一个角落开始，而每个进攻球员随机放在其他三个角落，每个角落一个球员。学习过程学习过程（续）学习过程（续）13个函数表示状态（WS）dist(F1,C)dist(F1,F2)dist(F1,F3)dist(F1,D1)dist(F1,D2)dist(F2,C)dist(F3,C)dist(D1,C)dist(D2,C)Minimum(dist(F2,D1),dist(F2,D2))Minimum(dist(F3,D1),dist(F3,D2))Minimum(ang(F2,F1,D1),ang(F2,F1,D2))Minimum(ang(F3,F1,D1),ang(F3,F1,D2))TileCoding采用Tilecoding方法来进行，状态用一个13维的空间来表示，用网格表示每个具体状态，在分析的时候，每个格对应一个二进制状态，或是1（当状态在这个格内）或是0（状态不在这个格内）。状态评价函数这里γ是学习率，一个固定的参数，T是从s开始的时间段内经过了T个时间步。规定，进攻队员能确切控球的状态有最高值0；所有其他状态是负值，立即失球的状态值接近-1。1000()|,{,}tTttVsErssEss策略学习强化学习去完善进攻队员的策略以达到尽可能长的时间控球。使用Q-learning，即每个进攻队员独立学习。这样，所有的进攻队员都能学会相似的策略或不同的策略。每个进攻队员有三个动作选择，对应于控球时的每个可能动作（GetOpen()，GotoBall()，{HoldBall(),PassBall(f)}）这是我们的策略评价试验中最有效的情况。策略学习给出一个被用于每个进攻队员的学习算法。函数UpdateRL(r)在后面定义。counter=-1;If(球出界或防守方得到球)·If(counter0)UpdateRL(-1)elseif(球不可踢)·{If(counter≥0)counter++;If(可以跑向球达到控球)GoToBall();elseGetOpen();elseif(球可控){If(counter0),UpdateRL(0){LastAction=Max(ActionValue(a,currentstatevariables));ExecuteLastAction;counter=0;}}Else(这时球被另外一个前锋控制){If(counter0)UpdateRL(0);counter=-1;}函数UpdateRL(r)UpdateRL(r):用TDError来更新状态评价函数。11=+Max(ActionValue())-ActionValue()countercounterTdErrorra,current,state,variablesLastAction,LastVariables注意事项：为了鼓励策略空间的扩展，可以使用简单的初始条件：未经过训练的逼近函数开始输出为0，这在所有真实值为负的情况下是可行的。由于任何没有试过的动作往往看上去比已经试过多次并被确切赋值的动作更好，这就使所有动作都有机会被尝试。小结：使用强化学习进行局部3VS.2战术的学习要求对手的防守能力强，也就是对球的截球能力强，这方面存在两个困难：（1）跟自己比赛，提高有限，（2）和强队比赛，高层策略无法控制。另外，3VS.2只是一个针对局部区域的策略，理论上是可以扩充到全局(11VS.11)，这时一个实际需要解决的问题是就是怎么解决庞大的状态空间。这也是我们以后的研究方向。7.4进攻体系进攻是从本方队员控球开始，直到本方失去控球权为止。进攻体系考虑的问题持球队员进行备选动作的选择，其他队员或进行策应，或进行合理的跑位。可以分为战术配合（局部的几个球员）和战略配合。7.4.1战术配合战术触发条件战术的实施过程战术的终止条件…………战术的设计主要涉及到2个方面：战术本身的设计通讯协议7.4.2战略配合持球队员（进攻的核心球员）的动作选择设计。接球队员的响应设计一般队员的跑位设计7.4.2.1持球队员的动作选择决策树（ifelse规则）：这实际上是MAS中的策略学选取中的比较匹配函数、兴趣或爱好函数的方法。基于效用对策论进行动作选择。基于效用对策论前面介绍了HfutAgent的个体技术，一个球员在控球以后，它可以选择带球、开球、传球（包括选择哪个队友进行传球）等动作。如何恰当地选择合适的动作是比较重要的问题。归根结底，在选择这些动作的时候必须考虑其他球员的利益，这就是多Agent的协作问题了。上节介绍了使用强化学习的方法来进行动作的选择。本节讨论一下使用对策论的方法来进行动作的选择。基于效用的对策论是MAS协作是的一种常用的方法。对策论对策论，又称博弈论，是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论。它的研究方法和其他很多利用数学工具研究社会经济现象的学科一样，是从复杂的现象中抽象出基本的元素，对这些基本元素构成的数学模型进行详尽分析，而后逐步引入对其形势产生影响的其他因素，从而分析其结果。为建立冲突对抗条件下决策的数学模型，必须数学化地描述冲突的参与者所有可能的行为方式及其行为结果，因此它也被视为数学的一个分支。对策论Robocup中对策论的方法实际上解决的就是在对抗条件下(在考虑多方面影响因素)怎么使自己(本方球队)的利益最大化。MAS中的对策论就是求参与MAS协作和规划的所有Agent的整体效用，针对Robocup，选择动作的影响因素，以及选择该动作的效用作为对策论的基础，持球者计算得出所有参与进攻的球员的效用最大值，并把最大值对应下的动作作为该持球队员的输出动作。基于效