搜索
读书报告班级25111001学号1120103379姓名刘明亮读书报告之——博弈论的足球机器人进攻策略研究姓名：刘明亮班级：25111001学号1120103379专业：工业设计读书报告班级25111001学号1120103379姓名刘明亮摘要：为提高足球机器人在比赛中进攻中的成功率，通过分析足球机器人一些进攻策略算法的不足和足球机器人进攻的任务以及Nash均衡的主要特征，提出了一种基于博弈论足球机器人进攻策略算法。博弈的战略考虑射门和传球，通过获得的收益函数值选择最佳策略。实验结果表明，足球机器人能迅速合理选择进攻策略，有效地提高机器人在比赛中进攻中的成功率。关键词：足球机器人；博弈论；Nash均衡；进攻策略1引言机器人足球比赛是国际上一项为促进分布式人工智能、智能机器人技术及相关领域的研究与发展而举行的大型教育、比赛和学术活动。它融合机器人学、人工智能、图像处理、自动控制、传感器学和通信等多门学科[1]。足球机器人比赛表现为由非实时、离散、静态环境下的单Agent控制到实时、连续、动态环境下的多Agent冲突、合作协调、控制[2]。利用足球机器人这个优秀平台，策略系统的开发者可以最大程度地把当前人工智能和智能控制领域的新方法和新理论应用于系统开发过程中，借以检验所用方法的先进性。按照国际机器人足球联盟的规则，在整个比赛过程中进球多的球队获得胜利，机器人足球比赛的环境和形势复杂多变，并具有较强的不确定性，因此进攻中策略门好坏直接决定了比赛结果。近年来，针对足球机器人策略研究一般采用有限状态机算法，该方法既能简化控制流程，同时也能兼顾系统的规划能力和快速反应特性，具有较高的鲁棒性，但是在复杂情况比赛中，会存在策略错误选择，智能化程度不高[3-4]。博弈论是研究多个个体或团队之间在特定条件制约下的对局中利用相关方法的策略，而实施对应策略的学科，是研究具有斗争或竞争性质现象的理论和方法，很多学者将经济学中的博弈论应用于任务分配中，能较好地解决了资源分配问题[5-6]。因此可借鉴这种思想，但目前针对此方法极少用于多机器人实际任务环境中。针对以上特点，本文采用博弈论Nash均衡解决足球机器人进攻策略问题，通过算法实现机器人选择合理的进攻策略，尽量达到最佳进攻策略组合。2基于博弈论的足球机器人进攻策略2.1博弈论的策略模型博弈论是将这些选择的本质抽象出来，它将各种错综复杂的关系数学化、理论化，以便更精确更抽象地理解其中的逻辑，从而对实际应用提供决策指导。用数学模型加以建模，来研究某个个人或是组织，面对一定的环境条件，在一定的规则约束下，如何依靠所掌握的信息，从各自选择的行为或是策略进行最优的选择。定义一个博弈一般需要设定以下几个要素[6-7]：（1）博弈的参与者即在所定义的博弈中究竟有哪几个独立决策、独立承担结果的个人或组织。参与者也被称之为“博弈方”，一般记参与者为i（i=1，2，…，n），本文中表示为球队机器人。（2）可以选择的全部战略或行动的集合读书报告班级25111001学号1120103379姓名刘明亮即规定每个参与者在进行决策，可以选择的方法的数量值。在同一个博弈中，不同参与者的可选择战略或行动的内容和数量也常不同，可以是有限个数或者是无限个数。这里行动指的是博弈参与者i在决策时可供选择的动作，一般记为ai。全部行动的集合称为行动空间，一般记为A，即A={a1，a2an}。战略指的是博弈参与者i在决策时针对其他参与者所选择的行动做出应对的行动安排，一般用si表示。用S表示战略空间，即S={s1s2sn}。（3）行动博弈的次序即参与者是同时做出选择，还是依次做出选择，有时候某些参与者还需要反复做出选择。（4）博弈的收益收益是指对应于各参与者的每一组可能的战略组合(s1,s2,,sn)下参与者i所得到的效用（通常表现为博弈中参与者i的输赢、得失、盈亏）。参与者i的收益通常记为ui(s1,s2,,sn)。严格占优战略[6-7]：如果对其他n-1个参考者的任何战略组合s-i=(s1si-1si+1sn)，参与者具有唯一的最优战略s*，也就是对任何s-i以及任一s'i¹s*i(s'ÎSi)，都有ui(s*is-i)³ui(s'is-i)，那么s*i就称为参与者i的严格占优战略。Nash均衡[6-7]：在n个参与者的战略式表达博弈G=(S1S2Sn;u1u2un)中如果对每个参与者i，s*i是针对其他n-1个参与者所选的战略组合s*-i=(s*1s*i-1s*i+1s*n)的最优反应战略，即ui(s*is*-i)³ui(sis*-i)，i=1，2，…，n，对Si中的所有si都成立，那么战略组合s*=(s*is*-i)=(s*1s*2s*n)称为博弈G的纳什均衡。定理[6]Nash均衡存在性每个有限的博弈至少存在一Nash均衡。因此，考虑的进攻策略的Nash均衡是存在的。2.2博弈论的进攻策略和收益函数基于博弈论进攻策略是寻找Nash均衡点将任务分配给每个机器人，这里的Nash均衡是一种最优策略组合。因此本文在机器人越过中场时，进行博弈分析选择策略应该射门、传球或者继续带球。以双机器人博弈模型为例，带球机器人Dir的收益函数uDir不仅与其自身的动作选择有关，还与队友机器人i有关。足球机器人博弈模型如表1所列。uDir(ss)表示带球机器人Dir选择战略s，队友机器人i选择战略s时，带球机器人Dir的收益值；ui(ps)表示带球机器人Dir选择战略p，队友机器人i接球后选择战略s，队友机器人i的收益值；同理，其他依次类推。在机器人足球比赛中射门的影响因素主要有足球机器人的朝向、守门员、射门的角度、离球门距离、防守机器人的干扰等。其主要有以下因子：(1)射门角度：射门的角度是进攻机器人当前位置点与对方两门柱间形成的夹角θ，由于射读书报告班级25111001学号1120103379姓名刘明亮门角度越大进球的机会就越大，即cosθ的值就越小，可构造射门角度的适应值：x1=a*(1-cosθ)=a*[1-(OA·OB)/(|OA|·|OB|)]（1）式中，a为射门的最大适应值，OA、OB为射门点到两门柱的矢量，|OA|、|OB|射门点到两门柱的距离。当θ大于90°时，视为射门角度已经足够大，以90°作为射门的上限值，即θ大于90°，cosθ值均取0。（2）射门距离：在射门时，进攻机器人离球门的距离越远，被防守机器人和守门员拦截的机会越大。则构造射门距离适应值：x2=a×(1-d1/d)（2）式中，d1为射门点到对方球门中点的距离，d为球场的长度。（3）防守机器人干扰：防守机器人离射门机器人越近，那么对射门机器人的进球影响将越大。则构造防守机器人干扰的适应值：x3=a×d2/d3（3）式中，d2为防守机器人离射门机器人的距离，d3为防守机器离射门机器人射门的安全距离。如果防守机器人离射门机器人的距离大于安全距离，则取d2=d3。通过考虑射门的影响因素，把期望值作为战略的收益函数，根据各种因素对射门影响的重要程度分配概率p1p2pn(åj=1npj=1)，则：假如带球机器人不射门，传球给队友，在传球过程中也会受到对方机器人的干扰，传球越远，对战机延误和干扰程度就越大，因此构造传球的适应值：式中，d4为带球机器人离接球机器人的距离。因此接球球员与带球球员有关，可得：如果带球机器人Dri在当前位置选择射门，则球与其他机器人无关，于是取ui(ss)、ui(sp)值为0；同理机器人选择传球，那么机器人ui(pp)值为0。2.3博弈论的进攻策略算法描述算法中如果把多个机器人同时进行博弈，则博弈模型比较复杂，为满足比赛的实时性，采用双机器人博弈模型。博弈论的进攻策略算法描述如下：步骤1获取比赛信息，初始化各机器人当前位置点的相关数据。步骤2采用式（4）（5）（7）计算在当前点带球机器人与各队友第i（i=1，2，…，n－1）个机器人在当前位置各收益值u。步骤3根据严格占优战略和Nash均衡，获得带球机器人与队友第i个机器人在当前位置最优战略。如果in-1则跳转步骤2。读书报告班级25111001学号1120103379姓名刘明亮步骤4从上获得的n-1组最优战略的收益值比较，找出带球机器人获得最大收益umax的战略组合，设置一个收益值的下限值u'min，如果umax³u'min，则执行带球机器人执行以上获得最大收益的战略组合，否则当前带球机器人传球或继续带球。步骤5在比赛球场上，把比赛场地分分割为小块，数量为n，如图1所示，获得n小块的中心点和当前机器人的位置点的数据；机器人在比赛中的角色（前锋、中场、后卫）分配区域，对该区域的n个小块采用式（7）计算n个小块各自的收益值ui（i=1，2，…，n）；比较找出最大收益值的位置点并向该区域移动，转步骤1。3实验与分析由于SimuroSot仿真平台已经有一段时间，机器人为一个长方体，机器人需要调整姿态才能侧面传球，类人程度不高。近几年机器人发展迅速，机器人越来越稳定，足球机器人系统的各项关键技术不断快速发展，机器人的类人程度越来越高。因此本实验以VC++6.0为平台，在SimuroSot仿真平台的机器人的所有行为基础上，增加仿人机器人的侧方位传球，侧方位的传球方向与机器人朝向的角度越大，那么传球的力就越小，同时机器人转向也需时间。在仿真中，可以看出机器人的类人程度更高，这也是足球机器人的发展方向。实验中，每场比赛10分钟，每种方法进行6场比赛。蓝队采用有限状态机算法进攻策略，红队在采用有限状态机算法基础上，结合博弈论算法。从实验仿真中取出比赛部分进攻图，如图2Nash均衡射门博弈模型所示和如图3Nash均衡移动博弈模型所示。从图1发现，采用有限状态机算法的进攻策略时带球机器人11位置会选择射门，但在增加博弈论算法后，执行机器人11传球给12机器人后由12机器人射门策略读书报告班级25111001学号1120103379姓名刘明亮时的收益值最大，于是机器人执行该策略。从图2发现，通过博弈论算法，带球机器人11不满足射门要求，而且其他机器人位置也不满足要求，于是11机器人继续带球；机器人移动中不断地博弈，当各个机器人在移动到如图中的A、B、C、D时，C点满足博弈论中的射门要求，于是11机器人和执行该进攻策略传球给13机器人射门。通过分析，红队采用了博弈论的算法后，比赛的进攻更加理性化，效率更高。实验结果如表2所列。从表2的实验结果可以看出，两队都采用有限状态机算法时，两队各有胜负，虽然红队输多了一场，但相差都不大。蓝队采用有限状态机算法，红队增加博弈论算法后，红队的进攻效率明显得到改善，比赛中蓝队由于进攻策略的失误给红队带来反攻机会，球场是胜负得到扭转，胜5场平1场，保持不败，并且平均净胜球数达到2.5个。实验还表明执行一次博弈论算法所花平均时间为0.153秒，因此采用该算法足球机器人能迅速合理地选择进攻策略，智能化程度高。4结论通过实际实验和比赛表明，采用博弈论的进攻策略效果十分明显，大大提高机器人进攻的成功率。本文算法虽然比现有的一些进攻策略算法有了进步，同时在仿真中也增加相应的干扰，但在硬件实现上它还没有考虑到机器人本身的性能和机器人足球的视觉等因素。在实际比赛中，机器人视觉处理带来的误差以及机器人本身性能的优劣对机器人每一个动作的执行都会产生很大的影响，因此，综合考虑各种因素，更健壮、更有效的进攻算法将有待于进一步研究。读书心得通过这次对博弈论的足球机器人进攻策略研究的学习，了解了如何通过一些算法提高足球机器人在比赛中进攻中的成功率，并且能够通过分析足球机器人一些进攻策略算法的不足和足球机器人进攻的任务以及Nash均衡的主要特征，这次阅读文中提出了一种基于博弈论足球机器人进攻策略算法。博弈的战略考虑射门和传球，通过获得的收益函数值选择最佳策略。实验结果表明，足球机器人能迅速合理选择进攻策略，有效地提高机器人在比赛中进攻中的成功率。读书报告班级25111001学号1120103379姓名刘明亮参考文献：[1]李鹏，朱建公.BP神经网络在机器人足球比赛系统中的应用[J].计算机仿真，2009，26（9）