机器人足球比赛决策及实现

文文献综述研究课题：机器人足球决策系统研究组员〔班级及学号〕：熊汇韬(3班10)罗运真研究课题：机器人足球决策系统研究组员〔班级及学号〕：熊汇韬(3班10)罗运真(3班15)赵大帅(2班24)彭晗(2班23)唐昊(2班21)游斌(2班19)杨荃月(2班28)机器人足球比赛是近年来在国际上迅速开展起来的国际对抗活动。它是人工智能领域与机器人研究领域的根底研究课程，是一个极富挑战性的研究工程。机器人足球比赛对研究多智能体的合作与竞争理论具有重要的实践与指导意义。而在机器人足球比赛中,决策系统根据视觉系统提供的机器人位姿和足球位置信息,进行快速准确的决策,是取得胜利的关键。本文以机器人系统的核心子系统决策子系统的开发为背景，主要介绍ROBOCUP〔机器人足球世界杯比赛〕机器人足球赛仿真技术，关于机器人的根本动作、路径规划、决策能力的研究，研究行之有效的决策推理方法。对目前决策系统问题主要是实时性、准确性、适应性和稳定性。针对上述问题,开发了面向RoboCup小型组机器人足球比赛的决策系统,重点解决了算法设计与系统特性之间的矛盾。关键词:机器人足球;可视化编程;算法；决策；目录TOC\o"1-3"\h\z\u19023一.介绍：423763二.系统分级6204271.视觉子系统：7306032.决策子系统：8158093.通讯子系统：913425决策六步经典方法推理模型912122三.系统核心决策模块10125141.机器人足球比赛系统决策子系统的一般结构：10266122.产生式推理模型：1062553.决策编程的可视化11112274.决策系统各模块分析1320781预处理模块136116态势分析与策略选择模块1324425队型确定与角色分配模块1314025目标位置确定模块1425617运动轨迹规划模块1419058动作选择模块14295235.决策系统各模块设计1412440输入信息预处理模块1411581态势分析与策略选择模块1517761队型确定与角色分配模块164202目标位置确定模块1731712运动轨迹规划模块1732507动作选择模块1825509四．决策层中KICK的智能算法20287781.基于倒脚踢球策略的模糊逻辑算法20193902.基于屡次踢球策略的遗传算法2124324五．机器人路径规划典型方法22304291.栅格法：22138262.人工势场法：2312664六．论述2525118七．总结：2511397参考文献26一.介绍：近年来，随着计算机技术的开展，分布式人工智能〔DistributedArtificialIntelligence,DAI〕已经成为人工智能领域的重要研究方向之一。分布式人工智能一般分为分布式问题求解和多Agent系统〔multi-agentsystem,简称MAS〕。其中，多Agent系统是分布式人工智能的一个重要领域。1.Agent:2.MAS:如上图，通常足球机器人系统可以划分为机器人本体子系统、通信子系统、视觉子系统和决策子系统四个局部,通过计算机视觉子系统闭环而构成智能决策和控制系统。视觉子系统负责识别球和机器人,得到现场信息;通信子系统负责传送现场获得的信息和发送机器人车体的运动指令;机器人车体系统负责接收指令并驱动机器人车体运动;决策子系统那么根据现场信息推理计算从而得到机器人运动控制指令，由决策子系统组织机器人协作,做出适当的战术配合,是取得胜利的关键。足球机器人主要需要完成的根本行为有：原地旋转，直线运动，曲线运动。根本动作有：跑位和转角、截球、踢球、射门、守门。当然,仿真平台除了要提供和智能体相关这两类接口外,还需要充当裁判功能,还必须提供相应的接口和监视器连接,以支持比照赛场地及场上所有参赛者的虚拟。另外,为了能够更好的提供离线训练和在线学习的功能,仿真平台还提供了教练接口(包括在线教练和离线教练)。一个完整的仿真比赛以CS/方式进行,如以下图2一2所示。二.系统分级1.视觉子系统：实时采集足球场地图像，实时处理并辨识这些图像，获取场上己方队员，对方队员及足球位置信息传给决策系统。2.决策子系统：根据感知子系统获得场上各类信息，利用智能体协作及对策理论，做出本组机器人行动决策，控制个机器人行为。机器人决策系统中，推理模型占有重要地位，为足球机器人决策系统设计提供整体思路指导。3.通讯子系统：完成小车子系统、决策子系统、感知子系统间的信息交换。决策六步经典方法推理模型第一步：场上信息预处理。第二步：攻守姿态分析和策略选择。第三步：机器人的阵型确定和角色分配。第四步：目标位置确定和动作选择。第五步：机器人运动轨迹规划。第六步：机器人左右轮速确定。三.系统核心决策模块1.机器人足球比赛系统决策子系统的一般结构：机器人足球控制决策系统中普遍采用了分层控制的结构[6]。东北大学提出由信息预处理、态势分析和策略选择、队形确定、角色分配、目标位姿确定和左右轮速确定等六个步骤组成的决策推理系统,并运用到足球机器人决策系统设计中;中南大学提出过由协调层、运动规划层和动作层组成的三层决策模型[7]。图1是Mirosot机器人足球比赛决策子系统的一般结构。现场信息是视觉子系统对现场某周期信息识别的结果,包括球与双方队员的位姿等信息。推理模块是根据视觉子系统传递来的现场信息,对场上的形式进行判断和推理,并根据比赛决策库产生相应的下一周期的比赛决策。比赛决策确定了本方球员在下一周期的角色、任务以及执行任务的位置。角色分配模块确定每个队员在某种策略下,下个周期的角色。动作模块是根据每个机器人当前周期的角色与任务确定相应的动作。根本的动作为踢球、射门、拦截、守门、避碍等。2.产生式推理模型：产生式推理与决策：首先选定某个策略,然后在此策略的根底上,生成一系列决策,从而形成决策库。为方便推理,决策由前件与后件组成。前件也称为产生式推理的条件,后件也称为产生式推理的结果。决策的前件即产生式推理的条件由球的位置Ball_location、本方球门受威胁程度Danger、对方球员位置Opponent_location构成;决策的后件即产生式推理的结果由本方球员的角色Role、任务Task以及执行任务的位置Location构成。用户决策集与根底决策集：由于决策库中的决策很多,用户编制的决策库可能不能包含全部的729条决策。当进行推理时,可能没有相匹配的决策,此时会出现某个周期的推理中断,影响比赛。为了防止种情况的发生,我们编写了根本决策集。当进行推理时,先在用户决策集中进行,当在用户决策集中未找到相应的决策时,再在根本决策集中推理。因此,我们把决策子系统的推理模型，修改为图2所示。3.决策编程的可视化在客户程序中定义了两个结构体类型:structdecision_result{unsignesdrole;unsignedtask;unsignedlocation_x;unsignedlocation_y;}structdecisiontype{unsignedball_location_x;unsignedball_location_y;unsigneddanger;unsignedopponent_location;structdecision_resultrole[3];}利用structdecisiontype结构体类型的变量,可以存储界面中输入的决策数据,从而把决策存储于决策库中。在进行比赛时,翻开用户决策库,从决策库中传入决策进行推理。当用户决策库没有对应的决策时,从根本决策库选择相应的决策进行推理。可视化程序,可以实现新建决策集、翻开决策集、关闭决策集、添加决策、删除决策、显示某条或全部决策、删除决策集等功能。只要理解输入界面中各个因素中的数字代码的含义就可以编制覆盖各个决策的决策库。比赛时,将此决策库与客户程序的决策子系统连接,就能够进行比赛了。决策系统推理模型采用六步推理模型。按照推理步骤,依次为信息预处理、态势分析与决策、队型确定与角色分配、目标位置确定、运动轨迹规划和动作选择。该决策推理模型的输入是视觉系统获得的机器人位姿和足球位置信息,输出是本队机器人的控制信息。4.决策系统各模块分析4.1预处理模块对视觉系统输入的机器人位姿信息、足球位置信息和比赛信息进行预处理,计算出决策使用的目标相对距离、角度信息和比赛参考信息。4.2态势分析与策略选择模块根据预处理模块输出的信息,判断进攻防守态势,判断依据可以是足球的位置、持球方、机器人的位姿。根据已经判断的信息,结合比赛信息,例如比分、剩余时间,对手强弱等,从策略库中选取进攻防守策略,例如全攻全守策略、区域进攻防守策略、强攻强守策略等。4.3队型确定与角色分配模块根据选择的策略,在队型库中选取进攻防守队型,例如1-3-1、1-2-2、1-1-3等。在确定队型后,可以对应队型进行角色分配。一般角色定义有守门员、主攻、副攻、主守、副守。4.4目标位置确定模块机器人足球是在动态环境下完成,机器人必须能够确定下一个目标位置,来完成指定的动作。4.5运动轨迹规划模块机器人运动到目标位置的路径有很多种,或者在运动过程中会遇到障碍,选择一个最优路径那么属于路径规划。4.6动作选择模块根据决策信息,在不同层次动作库中选择动作,按照一定的动作命令格式,构造成命令,命令包括机器人左右轮速、动作方向、动作角度、动作距离等参数信息。通过通信系统发送到机器人的控制系统,控制系统完成命令解释,控制机器人按照上层决策完成动作。5.决策系统各模块设计5.1输入信息预处理模块输入信息预处理模块采用向量计算的方法,所有的输入信息是以向量的形式描述的,定义一个向量计算类完成所有需要的向量计算。定义1维和2维结构数组保存计算结果,结构包括距离和角度域。为提高计算速度和减少计算量,提出基于数组对称性的存储访问方法和基于按需的首次访问计算方法。基于数组对称性的存储访问方法思想:因为数组下标为机器人编号,所以必然造成数据的对称性,对于距离方向无关量是一致,对于例如角度方向相关量是相反的。在存储上选择左下角或者右上角,访问上根据数组下标判断正负符号。基于按需的首次访问计算方法思想:如果全部计算所有数据,计算量过大,实际也并不需要那么多数据,这样影响系统效率。可以根据需要,如果没有计算过,那么先计算,再访问,否那么直接访问,这样可以大大降低计算量,提高系统效率。5.2态势分析与策略选择模块在态势分析与策略选择模块采用决策树和多参考因素系数加权求和的分析方法,其思想为:决策条件为持球方、机器人对足球位姿最优、足球所在区域、比赛信息等,决策判断优先级可以静态设置,也可以动态调整。对于态势分析可以以判断方式按照一定优先级逐层局部判断,或者同时考虑所有条件,对各条件分配一定的权重,然后进行系数加权求和运算,求得最优解。对于策略选择事先需要定义策略库,可以静态或者动态进行策略选择。静态策略选择是事先设定态势与策略映射关系,比赛过程不调整。动态策略选择是根据比赛情况,动态调整态势与策略的映射关系,映射的动态建立可以参照态势分析同样的算法。决策树分析方法例如:足球区域判断y持球方判断y目标位姿判断y比赛信息参考y策略。多参考因素系数加权求和分析方法数学模型:完成多参考因素系数加权求和计算。其中:S为态势和,N为参考因素总数,F(i)为参考因素i系数,G(i)为参考因素i权重。函数F和函数G可以通过实验测试获得。D=M(s)完成态势与策略的映射。其中M为从态势分析到策略选择的映射关系。M映射可以通过实验测试建立。5.3队型确定与角色分配模块按照选择的策略与队型的映射关系,在队型库中确定一个队型,映射关系的建立可以是静态设置好的,也可以是根据比赛情况动态设置的。每个机器人在一个队型中充当一个角色,在角色分配上,按照主副分配原那么,先分配主角色,然后根据主角色特征,分配副角色。主角色分配参考原那么同态势分析与策略选择模块。副角色分配原那么还需考虑主角色分配特征。例如距离主角色尽量近,距离对方尽量远,不要影响主角色功能发挥,最大程度辅助主角色功能发挥等。角色分配可以是静态的,也可以是动态的,除一些极限情况,例如守门员角色分配,一般角色分配都是动态的,时刻都可能发生角色交换,在有利于该角色情况下可以保持该角色一段时间,在不利于该角色情况下,发生角色交换(即使是守门员角色)。5.4目标位置确定模块目标位置确定模块采用决策树的分析方法,其思想为:根据机器人的角色、位姿、球门和场地信息进行判断,确定目标点。例如,作为主攻的机器人可以选择尽量靠近对方球门,根据机器人的位姿,可以直接快速完成攻门的一点。作为副攻的机器人要根据主攻机器人进行跑位,选择尽量靠近主攻机器人,靠近、面向球门,不要阻挡主攻机器人的进攻路线,远离防守机器人的一点。作为主守的机器人可以根据自身和足球位置,选择可以截断进攻路线,盯人、封堵射门角度的一点。作为副守的机器人可以根据主守机器人进行跑位,选择最大程度封堵角度,阻挡进攻路线,靠近面向对方机器人的一点。对于守门员的机器人,由于足球运动速度很快,一般守门员机器人只活动在球门附近,根据足球的位置水平跑位,尽量封堵角度,在特殊情况下,可以直接选择足球位置为目标点,这样必须进行角色转换,由另一个机器人作为守门员。5.5运动轨迹规划模块运动轨迹规划模块采用改良的12点加权求和分析方法。12点加权求和分析方法思想(图2):以机器人的位置为圆心,按一定的半径画一个圆,以时钟刻度的方式选12个点。其中半径的选取应该以机器人速度乘以一帧图像处理的时间间隔。参考因素包括障碍系数、边界系数、距离系数、角度系数、前方系数。障碍系数主要考虑避障问题,边界系数主要考虑边界处理,距离系数、角度系数、前方系数主要考虑进攻防守效率。根据进攻和防守态势,分别计算各点的进攻系数和防守系数。表示形式为各系数的加权求和,如果忽略某个系数,可以使该系数为零。得到最优解的点与机器人位置点来确定机器人运动方向。此算法的局限性为:(1)没有根据角色进行区分。(2)全部计算12个点,无谓判断点多,计算量大。(3)没有必要均匀分配12点,可以根据机器人与目标点连线,确定一个角度范围,再根据角度间隔分配判断点。改良算法思想为:可以在确定角色后,根据角色,选取一个角度判断范围,然后设定一个角度变化间隔,确定几个判断点,进行加权求和判断。角度范围、角度间隔需要根据角色静态设置或者动态调整。5.6动作选择模块动作选择模块采用动作分层设计的思想。算法思想为:应用面向对象的方法,将足球机器人的动作分为根底动作、技术动作、战术动作、组合动作四类。根底动作包括到定点动作、转角动作、移动动作等。技术动作包括射门动作、防守动作、盯人防守动作和边界球处理动作、传球到顶点动作等。组合动作包括避障碍到定点动作,守门员动作等。战术动作包括一传一射动作、底线传中射门动作等。动作的设计和实现与机器人本体的硬件密切相关,反映到机器人就是左右轮速确实定。在动作的选择上,要根据机器人角色、采用的策略、实际比赛信息来合理选择动作,确定机器人本体的线速度、角速度、动作时间、位移等参数,按照通信子系统定义好的命令格式构造命令,然后将格式化后的命令发送到机器人。例如,主攻机器人在有利射门的条件下,应该选择直接射门的动作,否那么应该选择传球动作。副攻机器人应该选择转角动作、移动动作调整自己到有利进攻的位姿,辅助主攻机器人进攻。主守机器人应该采用封堵进攻机器人路线和角度、截球等动作,尤其在球门前,调整好位态,防止乌龙球,选择动作的原那么就是尽快将球踢出防守区域。副守机器人应该选择转角动作、移动动作等调整自己到有利防守的位态,辅助主守机器人和守门员机器人防守,扩大防守面积。守门员应该选择转角动作、移动动作,最大程度封堵进攻角度,选择动作的原那么是根据足球的位置,快速精确的移动转角,不要轻易弃门出击。在一些特殊情况,例如在场地边界、场地四角可以采用扫球动作。也可以设计一些典型的条件,采用组合的动作,到达机器人之间的配合。四．决策层中KICK的智能算法1.基于倒脚踢球策略的模糊逻辑算法一个KICK难以把球调整到目标方向，此时需要一系列的KICK，把球的方向不断调整，这类似一个旋转加速的过程，直到调整到目标方向为止，然后踢出。此时，采用倒脚踢球策略，具体过程见图3。图中，d为目标速度，r为实际速度。图3倒脚踢球策略显然，对于任意初速度和目标速度，这样的可选择的KICK路线数量极大，相应地，搜索空间极为庞大。此时，需要有一个评价值作为搜索的向导，寻找一个最优的KICK序列。由于球的初速度和球相对于球员的距离是影响KICK重要参数，采用初速度和相对距离作为输入，经过模糊化、模糊推理和解模糊等运算，得到一个评价值cost，同时结合A*搜索方法，可以得到一个最优的KICK序列，以此到达预期的目标速度和方向。经实验说明:用10个球员进行测试，平均踢球次数为38次，踢一个球的平均周期数为3.5，速度平均误差为0.34m/s,方向平均误差为0.5度，失败的平均次数为0。由此可见，利用模糊逻辑算法，结合专家的先验知识建立规那么库，能成功地描述一个cost值，然后结合一种启发式搜索算法可以很好地规划出一条最优的KICK路线。2.基于屡次踢球策略的遗传算法屡次踢球策略类似于倒脚踢球策略，就是沿切线方向不断地把球踢向球员自身，以使球传到所需的方向，然后再踢出去。用以下公式计算踢球的角度θ：θ=ab+α*vdist*δt+θθ=cos-1(rp+rb)/d+90-tan-1〔ε/(d’sinθ2)〕d’=d+α*vdist*δt此处，d是球员到球的距离，δt是仿真周期，ab是相对角度，rp和rb代表球员和球的半径，vdist是SoccerServer提供的参数DistChng，tan-1项主要是为了防止球和队员互相碰撞。在式子中，α和ε是常量，两者的结合决定了转球动作完成的好坏。采用α和ε作为个体进行编码;选取球连续转过的总的角度作为适应度，通过遗传算法选取个体，群体大小取为1000，进行10代运算后，群体最好的个体参数为:α=1.68、ε=0.44、fitness=1430。由此意味着采用此参数的球员能使球围绕自己连续转3圈以上，假设用人工进行的调整的参数几乎不能做到这一点。五．机器人路径规划典型方法1.栅格法：栅格法[.wE.Howdne1968年]是在静态路径规划中避障过程搜索最优路径的常见方法。将工作区域划分成NxM个方格,每个方格的面积比一个机器人所占的面积略大。用状态空间法表示机器人的信息,对机器人的位置进行n个周期的预测,将两个相邻周期的预测位置连成直线,假设直线与某方格接触,那么认为覆盖了该方格的12/以上面积,对应的二维数组分量置1,其余数组分量置0。最优路径的搜索就是在空的方格内寻找连通路径。如下图。通过仿真实验可以看出,在动态的未知环境下的机器人足球比赛中,对障碍物先进行位置预测,在一定时间T内可把障碍物看作是静态的,用栅格法搜索最优路径。把静态栅格法结合预测算法后得到的方法称为动态栅格法,在全局路径规划上能取得较好的策略性。虽然动态栅格法在搜索路径中具有全局性、策略表现力强的优点,但动态栅格法是在动态过程中将某个时间段T内的片段看作静态状况而进行路径搜索。丁的选取决定了搜索的效果是否良好:2取得太大,那么预测的空间很大,容易导致搜索失败;2取得太小,那么不能预测出机器人的可能位置,搜索出的路径无效。2.人工势场法：人工势场法[atibandKrohg.Khatibalo]研究机器人手臂在笛卡尔空间中如何直接由任务相关的参数、运动、受力来控制其运动。把问题看成使系统状态由给定的初始状态转移到理想的目标状态,而防止状态空间中的禁止区域。并引入了一个重要的概念:广义势场,不仅考虑位置,也考虑速度。人工势场法是将机器人在周围环境中的运动,设计成在一种势场中运动,是对机器人运行环境的一种抽象描述,机器人在场中具有一定的抽象势能,势场的源有两类:斥力极和引力极。机器人不希望进入的区域和障碍物属干斥力极;目标及机器人系统建议通过的区域为引力极。在极的周围由一定的算法产生相应的势,在任何一点的势为两极在该点产生的势之和。通过搜索势函数的下降方向来寻找从初始位置到达目标位置的无碰撞路径。整个机器人足球比赛场地被虚拟成一个有力存在的场地,把力分为引力和斥力,根据比赛的进行,场上队员位置会发生变化,因而整个力场中各局部的受力情况也会发生变化,因此决策系统就可以根据场上的这种变化去实时的控制足球机器人的运动情况。具体而言,即首先建立斥力场和引力场,如图4.6所示。在机器人的周围,分布着环状的虚拟力场,用环带的宽度和环的斥力系数来表示环的参数,各个机器人之间表现为排斥力,通过设置各环的参数可以调整队员周围的力场。这样做有两个目的:在双方机器人因为争球而发生碰撞时,可以在一定程度上起到缓冲作用,以减少对机器人本身机械结构的损坏;在追逐争球时可以平滑的绕过对方球员,到达实时避障,夺得先机的效果。在人工势场方法路径规划中,把双方机器人和小球看成可自由移动的质点。六．论述Agent是近年来计算机科学领域中的一个重要概念,这一概念已被广泛应用于人工智能、分布式计算等领域,为分布开放系统的分析、设计和实现提供了一个崭新的途径，未来的工作将在原有的代码根底上,增加新的策略的分析和实现,构造角色更明确的Agent,使机器人球员具有学习、协调及协作的能力,使研究更加接近MAS理论的定义。而在机器人足球比赛的成绩关键在于决策,。本文将决策各局部进行分解研究并通过对各种算法和规划方式的可视化研究,实现对机器人足球决策层面的理解。从实际角度出发,介绍机器人足球决策软件与硬件系统的设计实现方案,描述了系统的软件结构和设计思想,以及一系列的方法概述，对应用和现有的一些算法的总结。对于各种算法和方法的理论研究,都有一定的局限性和针对性,但是大都比拟容易实现,实用和科学。七．总结：RoboCup是研究动态不可预测环境中的多智能体系统的典型平台。在RoboCup仿真比赛中,机器人整体团队协作和局部对抗规划都是比赛成功的关键。通过