|
摘要：为提高RoboCup仿真比赛中智能体带球的成功率，设计了带球路径策略。通过细胞自动机建立了比赛环境演化模型，能够对智能体带球路径的搜索空间进行分析规划，在此基础上设计了智能体带球的路径搜索策略。测试结果说明该策略能保证智能体在复杂实时的环境下进行有效的带球。
关键词：带球策略细胞自动机启发式搜索机器人足球 在RoboCup中，带球具有相当重要的作用。研究RoboCup中带球等动作的意义不仅仅局限于RoboCup本身，它对于Agent的计算、甚至人工智能基础理论的发展都具有重要意义。
带球是智能体控球同时移动到目标点的技术，对于带球最关键的策略是下一步应采取哪条路径。这个过程至少要完成两个任务：避免跟对方球员的冲突和运用路径搜索算法找到从起点到目标点的带球路径。
带球路径可以采取多种不同的搜索求解方法，本文集中考虑对方球员的影响，找到适合智能体带球的较优路径。首先建立一个优化的环境状态描述图，使它支持球员智能体在比赛场地中的路径搜索；然后设计使智能体高教执行的路径搜索策略，估算出一条到达目标点的较优带球路径。 1 策略总体设计
整个策略包括两部分。第一部分利用细胞自动机对环境建模，根据对方球员的影响演化出环境状态描述图，分析规划以后要使用的路径搜索空间。据此，智能体能够对未来可能发生的状态进行分析预测而有效避开对方球员的攻击。第二部分在规划好的搜索空间内，运用合理的路径搜索算法，设计启发函数为智能体提供最佳可行的解路径。
2 基于细胞自动机对环境的建模
细胞自动机是由一组规则网格组成的阵列，每个格子就是一个细胞，其组成三要素为细胞的状态、邻居细胞以及演化规则。它具有组成单元的简单性、单元之间作用的局部性和信息处理的高度并行性等特点，适合对复杂实时的动态系统进行有效建模。
将球员智能体进行带球决策的区域(设定为智能体前方一块矩形区域)用一系列离散方格细胞序列表示。细胞自动机算法的输入即为智能体的感知信息。细胞自动机通过不断的状态利新，进行决策区域内环境状态的演化。
2．1 构造模型1
(1)定义细胞状态：没有被任何球员占据的状态为0；被对方队员占据时根据对方队员的身体朝向可以离散化地定义各种状态：北1、东北2、东3、东南4、南5、西南6、西7、西北8(根据比赛服务器所提供的参数设置，设定各状态代表的角度范围是：东(-22.5-22.5)、南(-112.5~-67.5)、西(-180!-157.5＆＆157.5～180)、北(67.5~112.5)、东南(-67.5~-22.5)、东北(22.5~67.5)、西南(-157.5~-112.5)、西北(112.5～157.5))。
(2)邻居细胞：每个细胞周围的8个细胞为其邻居细胞，分别位于北面、东北面、东面、东南面、南面、西南面、西面、西北面。
(3)演化规则：根据当前对方球员朝向状态进行演化，对每个被对方队员占据的细胞演化出它们最可能的影响范围。
为方便描述，设Sti为细胞i在t时刻的状态，i为演化细胞代号，S，。、蹄、封、嗣、耐、蹄、对、嗣分别为位于i细胞北面、东北面、东面、东南面、南面、西南面、西面、西北面八个方向上的邻居细胞状态，jn(n=l，2，……8)为邻居细胞代号，下面是此算法的伪码实现。  
带球队员每进行一次信息更新即可对环境状态图进行几次演化迭代，演化迭代次数由所选细胞尺寸、对方能力强弱等确定。
这种根据朝向演化的影响区域是合理的。因为每个智能体一般只能对本身的朝向做出快速反应，所以考虑对方队员的朝向因素，预测以后可能的环境状态。假定在某影响区域内，对方队员会在我方队员之前到达这个区域内的任何一个位置，所以我方队员以后的路径规划必须避开此区域。演化后得到的细胞状态图如图1所示，是构造下一个细胞自动机模型的基础。 
2.2 构造模型2
模型1得到的结果直接作为第二个模型的初始状态。模型2的构造如下：
(1)定义细胞状态：细胞救有被任何智能体占据的状态为0；对方球员的控制能力值x作为细胞状态值，设对方队员速度值的10倍(取整舍去小数位)为对方队员的控制能力值，速度较快的对方队员进攻性比较强，移动打乱我方队员进攻的可能性较大，因此按照速度值设定控制能力值。根据仿真比赛服务器的参数设置，x可取1～12的自然数。
(2)邻居细胞包括每个细胞周围的8个细胞。
(3)演化规则：以影响力地图的思想为基础。如果此细胞的状态值为O，则将其各邻居细胞的状态值折半取整，再叠加作为此细胞演化后的状态值。下面是这个算法的伪码实现，演化后生成的细胞状态图作为最终的环境状态描述图，如图2。 
这里的演化规则即是对对方队员控制能力值的耗散处理，使智能体可以通过演化后环境状态描述图中的各个细胞位置的状态值预见对方球员以后可能的影响状况，这些信息使智能体知道某个位置作为带球路径的价值信息。
3 带球路径搜索策略的实现
最终演化好的细胞状态图描述了对方球员的影响，提供了各个位置作为带球路径的价值信息。下面运用人工智能的启发式搜索策略，设计有效的启发函数加速问题求解，使路径搜索向着最有希望的方向前进，找到最优路径。
整个路径搜索算法主要完成以下工作：(1)取得代价值最小的节点；(2)判断产生当前节点的子节点集合；(3)把节点放入Closed表。路径搜索核心流程的伪码实现如下： 
3.1 设计启发函数
以上搜索算法的关键是设计启发函数评价路径，不同的启发函数会导致不同的解路径。根据带球策略，将Cost、Costθ1、cosk三个因素作为启发函数的参数，设计如下：
根据优先级的大小分别赋予这三个因素合适的权值a、卢和7。这些权值的选取对于带球路线的搜索十分关键，它们的数值是基于公式中各项的优先级以及范围，可以通过调整权值改变各个因素的优先次序。优先级较高的因素在结果中应占较大比重，这些权值需要经过大量的测试或使用学习等技术得到。
在本应用中，取Ⅱ>口>y。因为最重要的是避开接近的对方球员，相对于高层规划指定的目标位置的角度偏移以及原来带球方向角度偏移则次之。这样使智能体向相对对方队员控制能力较弱位置、朝目标位置方向以及它原本前进的方向带球前进。这样选择是因为方向的改变会额外花费一些时问，有时还会引起不理想的震荡。
3．2 路径搜索的优化执行
为提高路径搜索算法的效率，结合前一节中介绍的细胞自动机的演化结果，采取制定搜索界限的方法进行路径搜索。即在搜索算法上附加表示当前调用的界限参数。这样算法占用较小的内存，被考察的节点较少，以下是根据界限参数获得子节点集合的示例：
本文的策略对于细胞位置允许的最大状态值为界限参数。在环境状态描述图的基础上，设定界限1：细胞状态值为O，此界限区域为带球搜索最安全区域，不在对方球员的控制之下；界限2：相对界限l放宽一些，定细胞状态值稍大，此界限区域为从最安全区域出发分别向左向右扩散出的带球搜索较安全区域．对方球员对此区域的控制能力增加；根据情况还可继续放宽界限，制定界限3、界限4等。如果一个小界限的初始搜索能找到路径，则搜索算法只要在最安全区域尝试少数几个位置就能找到正确的路径。如果没有成功找到路径，将在随后的调用中逐渐放宽界限，取界限2、3，即让其在较安全区域甚至弱安全区域搜索路径，直到搜索成功或者到达取值范围的端点。
这样，即使是失败的几次调用findpath()也只使用了较少的内存；同时也加快了路径检测的速度。因为小界限调用会更快地达到失败条件，也提高了路径暂被其他行动者阻断时的执行性能。
如果没有成功找到通向目标点的带球路径，可能是路径不存在或者搜索已经到了强加的极限，这时不应该让球员反复调用失败的搜索算法而延误动作时机。为了使带球智能体的反应更加灵敏，采取返回findpartpath()，先得到部分路径的策略。只需修改findpath()，即设定搜索节点循环相应次数后停止计算(循环次数确保能产生一条合理长度的路径)，把离目标点最近的点作为子目标点，返回实现的部分路径。从小界限开始趋向最大界限进行路径搜索的伪码实现如下：
带球队员通过一个小界限参数调用搜索算法，可以立即沿着返回的部分路径移动，然后使用一个逐渐增大的界限参数再次调用搜索算法得到部分或全部路径，带球者最终会找到一条通往目的地的路径，或者在一个离终点不远的地方停止。总之，界限参数和返回部分路径的方法可以使智能体的反应更加灵敏，不管发生什么情况，带球队员总会有所作为，而不是只站在原地。 4 应用效果测试
本文进行的比赛测试是在SoccerServer1O．XX版本下完成的。将基于细胞自动机的带球路径搜索策略应用到中南大学RoboCup仿真球队(CSU_Yunlu 2005)中，先后对采用本文策略和不采用本文策略的CSU_YunLu仿真球队作了长时间的测试。
将未采用新策略的球队和采用新策略的球队与同一支仿真球队比赛，运用仿真调试工具SoccerDoctor得到两次比赛中带球成功率的统计图，如图3、图4所示。 
其中横坐标为球员智能体的编号，纵坐标为带球次数，深色柱形为相应球员带球总次数，浅色柱形为相应球员带球成功的次数。统计结果表明，未采用新策略以前球队整体带球成功率为77％，如图3；采用新策略后的球队整体带球成功率为90％，如图4。整套策略在RoboCup实时带球过程中表现出令人满意的运行性能。
本文将细胞自动机算法和启发式路径搜索算法融合进带球路径搜索策略中，使智能体能够对环境进行实时的分析预测，有效避免与对方球员的冲突并能高效地执行道路搜索。这样带球智能体行动得更快，对环境状态改变的响应也更加灵敏．从而保证了带球决策的实时性和高效性。在2005年中国机器人大赛RoboCup仿真组比赛中，CSU_Yunlu 2005云麓队获得了三等奖，达到了预期效果。
() | 
