一种基于URWPGSim2D启发式博弈策略设计

李生武+肖兆强+杨为民

摘要：针对北京大学机器鱼仿真平台URWPGSim2D 中“抢球博弈”项目控制目标数量多，仿真机器鱼之间的对抗性与团队协作性强，复杂多变的竞赛规则与模拟环境，设计一套稳定，有效且对抗性强的控制策略，实现仿真鱼的协同分工，最终获得比赛胜利。由于仿真环境的复杂性与不确定性，为提高控制策略的高效性，提出先对仿真鱼进行任务分工；其次依据仿真周期数将比赛进行阶段划分，再次根据场地中目标水球的位置信息将场地进行区域划分，最后利用启发函数计算目标球优先级。然后综合考虑这四个因素，给出多仿真鱼协同抢球的高效策略。该策略在“2015国际水中机器人大赛”中获得一等奖的成绩，充分证明了该优化策略的有效性及鲁棒性。

关键词：仿真鱼；抢球博弈；协作；启发函数；多目标；优先级

中图分类号： TP242.6 文献标志码： A 文章编号：1009-3044（2016）12-0075-05

以北京大学作为发起人联合众多科研机构同开发了水中机器人URWPGSim2D （under robot water polo game simulation 2D）仿真平台，该仿真系共统具有实时性强，逼真性高和人机交互性强的特点，有效地解决了实体机器鱼在研究过程中遇到的问题，降低了实体鱼的研究难度。

在2015年5月发布的新的仿真平台URWPGSim2D 3.0中，抢球博弈项目的球门位置与模型均未发生变化，而目标球的位置，目标球分值及项目规则均有较大变化。平台版本的更新使得在制定策略的时候需要更多的考虑单个目标球对比赛得分的影响，而且对机器鱼的运输有效性提出了更高的要求。因此本文分别对制约策略有效性的四个因素进行了优化，得到了一种在新平台下更为有效的智能策略。

1 水中机器人2D仿真简介

1.1 URWPGSim2D平台简介

URWPGSim2D包括服务（URWPGSim2DServer）和客户端（URWPGSim2DClient）两大部分。服务端模拟水中环境，控制和呈现仿真过程及结果，向客户端发送实时仿真环境和过程信息；半分布式客户端模拟水中机器人队伍，全分布式客户端模拟单个水中机器人，加载比赛或实验策略，完成决策计算过程，向服务端发送决策结果[1]。其整体结构如图1所示：

1.2 抢球博弈项目简介

水中机器人2D仿真抢球博弈采用3000mm*2000mm的标准比赛场地。2D仿真抢球博弈项目的仿真环境包括4条被分为两支队伍的仿真鱼，9个拥有不同分值的仿真水球和2个由矩形障碍物组成的球门。随着多次大赛的成功举行，为了提高比赛对抗的激烈性和机器鱼团队之间的协同性，开发人员将平台做了如下更新（如图2，图3）所示。

1.3 计分规则

1） 水球分值：在图3中场地四个角落的目标球分值均为一分，场地中心附近的三个目标球分值均为三分，其余两个球的分值均为两分。

2） 胜负标准：单场比赛，在6000个仿真周期内得分多的队伍获胜，若分数相同则率先进球的队伍获胜。

3） 进球得分：仿真水球被顶入球门时，该球门对应的队伍得到相应分数，每个球在一场比赛中如果被多次顶入同一队伍的球门，不重复计分被顶出不扣分。

2策略设计思想

2.1 策略运行原理

仿真平台开始运行后，平台就会以40ms为周期循环执行策略，以6000仿真周期总数逐步减少。这样的循环执行方式可以有效地提高仿真系统的实时性，使用者先在客户端工程中编写策略，在编译通过后生成后缀名为dll的动态链接库，开发者定义的函数模块和平台的部分信息都被封装在了该dll文件中。在比赛时双方在同一个服务器端加载各自策略的动态链接库，准备完成之后即可经行比赛。

2.2任务调度

在笔者所提出的策略中每条己方仿真鱼都有两种任务的动态调度，一种任务是己方运球得分，另一种任务是破坏对方得分。

处于运球任务的仿真鱼根据选球函数计算出来的优先级确定运输目标，将目标球迅速的运输到己方球门。

处于破坏任务的仿真鱼的是为干扰对方，破坏对方的运球状态，抑制对方的得分。

2.3 区域划分

受制于仿真鱼智能水平的限制，仿真鱼并不能主动对仿真场地障碍物和边界做出响应动作，因此会严重影响仿真鱼的动作准确度和运输效率。因此笔者对比赛场地做了一定的划分，一方面可以在不同的区域赋予仿真鱼不同的动作策略以提高仿真鱼的场地适应能力，另一方面仿真鱼可以根据不同区域中目标球权值的不同可以智能选择最有利的得分区域作为自己行动的目标位置。

Zone 0为主要抢夺区域。此区域中目标球较多且单个目标球分值较大，需要综合运用多种策略使己方迅速占领优势地位。

Zone 1，Zone 3为己方球门转角区域。当己方仿真鱼进入此区域后在参考目标点A，M1，B或G，M3，H（右半场则为C，M2，D或E，M4，F）的指引下迅速的完成运输球从Zone 0到Zone 2或Zone 0到Zone3的任务。为防止仿真鱼将目标球带入场地死角产生僵持现象所以需检测函数，判断是否满足条件后进而调用相应的处理模块解决问题。

Zone 2为己方球门区域。在此区域己方鱼易得分，加载射门函数，完成射门任务。

Zone 5为敌方球门区域。在此区域对方易于得分。对于己方来说，基于对得分规则和运输代价的考虑，己方应在在保证除Zone 5外的区域中无剩余目标球的前提下才去考虑运输Zone 5中的目标球。

Zone 4，Zone 6为敌方球门转角区域。在此区域不利于己方仿真鱼的抢球动作，且容易在此区域与敌方因为争夺目标球将目标球顶入死角陷入僵持阶段，所以在此区域采取防守策略，通过干扰对方或者堵塞对方进入Zone 5的路径来达到防守目的。

2.4 仿真周期控制

抢球博弈项目共10分钟，比赛平台设置的仿真周期即每个仿真循环周期毫秒数（如100ms），转换得到该比赛项目的总仿真周期数（10*60*1000/100=6000）；比赛是通过倒计时的方式经行的，笔者在此将依据仿真周期将比赛主要分为两个阶段。

进攻阶段，此阶段为仿真周期数从6000递减至1800之间时间段。

破坏阶段，此阶段为仿真周期数从1800递减至结束比赛之间的时间段。

3 策略设计与实现

3.1 仿真鱼协作与任务调度

本文中提到的任务调度是由于比赛场上动态信息触发而引起的，笔者认为将场地中仿真鱼的实时状态作为触发信息极具代表性。在该策略中将仿真鱼所处的状态分为如下程序段所举出的5个状态。

3.1.2 仿真个体控制策略

在比赛开始后的50个仿真周期内己方仿真鱼M（M的取值为0，1）完成初始动作，之后判断仿真比赛阶段。

若当前阶段为破坏阶段，以仿真鱼M与对方球门距离为参考，若距离对方球门最近则去对方球门附近干扰对方得分，若不是则转为进攻状态。

若当前阶段为攻击阶段，仿真鱼M选择目标球后，首先判断己方球门是否有多于2个三分球，若满足条件再根据仿真鱼M到对方球门的距离指派具体任务；若不满足条件则继续执行运输目标球的任务。控制流程如图6所示。

新的平台设置了3个三分球，因此对三分球的控制直接影响着比赛结果。根据以往策略，敌我双方都为了避免与对方因争夺三分球过多浪费时间，采取一次性运输分值为1或2分的目标球，以求迅速得分占领优势而对于三分球的处理则在比赛较后阶段才会去考虑。这样不能够及时得到三分球的控制权，因此存在被对方利用三分球得分逆转的巨大风险。因此本策略摒弃此种设计思想，对三分球的处理如下：比赛开始阶段，己方两条仿真鱼直接选择3个三分球中的两个，在保证至少一个三分球能够顺利运输到己方球门的前提下，在选球策略的指引下获得下一个三分球的控制权。当己方球门中三分球大于1个时，指派一条仿真鱼做防守动作防止对方争夺；另一条仿真鱼继续选球运输。控制流程图如图6所示。

3.2 选球策略

有效的选球策略在比赛中不仅能够提高队伍的协作能力，而且能够提高己方的得分速率与得分质量，这在实时计时性对抗比赛中对比赛结果有着至关重要的影响作用。本文提出一种以权值评估为核心的启发函数，该函数综合考虑了仿真鱼、球门和目标球之间的距离关系，旋转代价和目标球 分值这四大要素。启发函数形式如下。

3.2.1 [Ts，v]的计算

在URWPGSim2D平台中由于仿真水环境的特殊性，鱼即使没有速度也难以做到相对静止，会在水波的影响下发生位移。在设置了一个目标点后，仿真鱼到达该点后并不会立即停下，而是会沿着之前的方向运动一段距离。以此这里设定一个偏移量[μ] ，并近似认为偏移量是在之前的运动方向上。偏移量[μ][μ]与速度档位VCode之间的对应关系如表1所示：

3.2.2 [Aq，ω] 计算

由于仿真鱼的动作存在延迟性，导致实际旋转角度会受到上一时刻角速度的影响，因此难以精确控制。现利用补偿原理添加补偿量，用来抵消前一时刻角速度对仿真鱼旋转的影响。

4 结束语

本文综合任务调度，区域划分，仿真周期控制和选球策略几个方面制定了一种提出的突破常规的动作策略，该策略摒弃了局部最优的缺点，使仿真鱼对场上各种变量因素综合评价，智能决策做到随机应变。经过多次实验验证表明：运用上述策略可使己方在比赛过程中处于有利的主动状态，较大的增加了己方的胜率。在本策略中主要以目标球作为驱动因素，缺少对另一方仿真鱼动作序列的检测，因此在对方变换策略后不能及时地做出响应动作。

参考文献：

[1] 中国水中机器人大赛官方网站.URWPGSim2D开发人员手册[EB/OL].北京：北京大学智能控制实验室.（2010）.http：//robot.pku.edu.cn.

[2] Liu J， Dukes I， Hu H. Novel mechatronics design for a robotic fish[C]. Proc. 2005 IEEE/RSJ International Conference on Intelligent Robots andSystems，2005：2077-2082.

[3] Auzinger D.Djumlija G. Application of advanced technology packages for improved strip profile and flatness in hot-strip-mills[J].Iron and steel， 2004，39（11）：132-133.

[4] 刘舒.多机器鱼编队控制[D].北京：华北电力大学，2012.

[5] 龙海楠，李淑琴，安永跃.仿真机器鱼抢球大作战比赛策略的研究[J].计算机仿真，2013，30（7）：312-316.

[6] 黎章. 多水下机器人协作控制[D].北京：北京大学，2008：1-10.

[7] Anna Osborne，Stuart Baur，Katie Grantham.Simulation prototyping of an experimental solar house[J].Energies，2010，8（5） ： 27-35.

[8] Leonardand，N.E，Virtual，E.F.Virtual leaders artificial potentials and coordinated control of groups[C].The 40th IEEE Conference on Decision and Control，2001：2968-2973.

[9] Denis L，Baggi.Theintelligence left in AI[J].AI & Society，2005（2）：27-35.