在RoboCup中，带球具有相当重要的作用。研究RoboCup中带球等动作的意义不仅仅局限于RoboCup本身，它对于Agent的计算、甚至人工智能基础理论的发展都具有重要意义。
　　带球是智能体控球同时移动到目标点的技术，对于带球最关键的策略是下一步应采取哪条路径。这个过程至少要完成两个任务：避免跟对方球员的冲突和运用路径搜索算法找到从起点到目标点的带球路径。
　　带球路径可以采取多种不同的搜索求解方法，本文集中考虑对方球员的影响，找到适合智能体带球的较优路径。首先建立一个优化的环境状态描述图，使它支持球员智能体在比赛场地中的路径搜索；然后设计使智能体高效执行的路径搜索策略，估算出一条到达目标点的较优带球路径。
1 策略总体设计
　　整个策略包括两部分。第一部分利用细胞自动机对环境建模，根据对方球员的影响演化出环境状态描述图，分析规划以后要使用的路径搜索空间。据此，智能体能够对未来可能发生的状态进行分析预测而有效避开对方球员的攻击。第二部分在规划好的搜索空间内，运用合理的路径搜索算法，设计启发函数" title="启发函数">启发函数为智能体提供最佳可行的解路径。
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)演化规则：根据当前对方球员朝向状态进行演化，对每个被对方队员占据的细胞演化出它们最可能的影响范围。
　　为方便描述，设S_i^t为细胞i在t时刻的状态，i为演化细胞代号，S_j1^t、S_j2^t、S_j3^t、S_j4^t、S_j5^t、S_j6^t、S_j7^t、S_j8^t分别为位于i细胞北面、东北面、东面、东南面、南面、西南面、西面、西北面八个方向上的邻居细胞状态，jn(n=1，2，……8)为邻居细胞代号，下面是此算法的伪码实现。
　　

　　
　　带球队员每进行一次信息更新即可对环境状态图进行几次演化迭代，演化迭代次数由所选细胞尺寸、对方能力强弱等确定。
　　这种根据朝向演化的影响区域是合理的。因为每个智能体一般只能对本身的朝向做出快速反应，所以考虑对方队员的朝向因素，预测以后可能的环境状态。假定在某影响区域内，对方队员会在我方队员之前到达这个区域内的任何一个位置，所以我方队员以后的路径规划必须避开此区域。演化后得到的细胞状态图如图1所示，是构造下一个细胞自动机模型的基础。

2.2 构造模型2
　　模型1得到的结果直接作为第二个模型的初始状态。模型2的构造如下：
　　(1)定义细胞状态：细胞没有被任何智能体占据的状态为0；对方球员的控制能力值x作为细胞状态值" title="状态值">状态值，设对方队员速度值的10倍(取整舍去小数位)为对方队员的控制能力值，速度较快的对方队员进攻性比较强，移动打乱我方队员进攻的可能性较大，因此按照速度值设定控制能力值。根据仿真比赛服务器的参数设置，x可取1～12的自然数。
　　(2)邻居细胞包括每个细胞周围的8个细胞。
　　(3)演化规则：以影响力地图的思想为基础。如果此细胞的状态值为0，则将其各邻居细胞的状态值折半取整，再叠加作为此细胞演化后的状态值。下面是这个算法的伪码实现，演化后生成的细胞状态图作为最终的环境状态描述图，如图2。

　　
　　这里的演化规则即是对对方队员控制能力值的耗散处理，使智能体可以通过演化后环境状态描述图中的各个细胞位置的状态值预见对方球员以后可能的影响状况，这些信息使智能体知道某个位置作为带球路径的价值信息。
3 带球路径搜索策略的实现
　　最终演化好的细胞状态图描述了对方球员的影响，提供了各个位置作为带球路径的价值信息。下面运用人工智能的启发式搜索策略，设计有效的启发函数加速问题求解，使路径搜索向着最有希望的方向前进，找到最优路径。
　　整个路径搜索算法主要完成以下工作：(1)取得代价值最小的节点；(2)判断产生当前节点的子节点集合；(3)把节点放入Closed表。路径搜索核心流程的伪码实现如下：
FindPath(Constrain)
{
　　//在Open表中加入新节点
　　AddNodeToList(Open，startNode)；
　　//Open表非空，进行路径搜索
　　while !OpenIsEmpty() do
　　//Open表中代价值最小的节点为当前节点
　　Node CurNode=Open.pop_front()；
　　if ArriveGoal(CurNode) then
　　flag=1；//标志路径搜索成功
　　//返回起点到当前节点的所有节点形成路径
　　return GeneratePath(curNode)；
　　else
　　//把当前节点加入到Closed表中
　　AddNodeToList(Closed，CurNode)；
　　//产生当前节点子节点集合
　　List SubNodeList=getSubNodes(CurNode，Constrain，increment)；
　　for i=0；i　　//子节点在Closed表中
　　if InClosedList(SubNode) then
　　continue；
　　//子节点不在Closed表中
　　else
　　//子节点不在Open表中
　　if !InOpenList(SubNode) then
　　//计算子节点的代价值
　　TotalCost(SubNode)=gCost(SubNode)+hCost(SubNode)；
　　//当前节点作为子节点的父节点
　　SubNode.parent=CurNode；
　　//将子节点放到Open列表中
　　AddNodetoList(Open，SubNode)；
　　else //子节点在Open表更新父节点，重排Open表
　　if gCost(SubNode)　　CurNode=SubNode.parent；
　　TotalCost(SubNode)=gCost(SubNode)+hCost(SubNode)；
　　//按代价值给Open表中元素排序
　　Sort(OpenList)；
　　end if
　　end if
　　end if
　　end for
　　end if
　　end while
　　return null；
}
3.1 设计启发函数
　　以上搜索算法的关键是设计启发函数评价路径，不同的启发函数会导致不同的解路径。根据带球策略，将Cost_s、Cost_θ1、Cost_θ2三个因素作为启发函数的参数，设计如下：
　　hCost(Node)
　　{
　　//Cost_s为节点细胞当前状态值
　　Cost_s=GetState(Node)；
　　//Cost_θ1为相对目标位置的偏移角度
　　Cost_θ1=AngDeviate(Node，Node.parent)；
　　//Cost_θ2为相对上次搜索过节点位置的偏移角度
　　Cost_θ2=AngDeviate(Node，goalNode)；
　　h(Cost)=αCost_s+βCost_θ1+γCost_θ2；
　　return h；
　　}
　　根据优先级的大小分别赋予这三个因素合适的权值" title="权值">权值α、β和γ。这些权值的选取对于带球路线的搜索十分关键，它们的数值是基于公式中各项的优先级以及范围，可以通过调整权值改变各个因素的优先次序。优先级较高的因素在结果中应占较大比重，这些权值需要经过大量的测试或使用学习等技术得到。
　　在本应用中，取α＞β＞γ。因为最重要的是避开接近的对方球员，相对于高层规划指定的目标位置的角度偏移以及原来带球方向角度偏移则次之。这样使智能体向相对对方队员控制能力较弱位置、朝目标位置方向以及它原本前进的方向带球前进。这样选择是因为方向的改变会额外花费一些时间，有时还会引起不理想的震荡。
3.2 路径搜索的优化执行
　　为提高路径搜索算法的效率，结合前一节中介绍的细胞自动机的演化结果，采取制定搜索界限的方法进行路径搜索。即在搜索算法上附加表示当前调用的界限参数。这样算法占用较小的内存，被考察的节点较少，以下是根据界限参数获得子节点集合的示例：
　　getSubNodes (CurNode，Constrain，increment)
　　{
　　//循环构造当前位置的邻居位置子节点
　　for i=-1；i<2；i++
　　for j=-1；j<2；j++
　　SubNode.x=CurNode.x+i*increment；
　　SubNode.y=CurNode.y+j*increment；
　　if i==0 && j==0 then
　　　　continue；
　　end if
　　if !InConstrain(SubNode) then
　　　　continue；//不在界限内的节点排除
　　end if
　　//将在界线参数限定范围内的节点加入子节点集合
　　AddNodeToList(SubNodeList，SubNode)；
　　return SubNodeList；//返回界限内子节点集合
　　end for
　　end for
　　}
　　本文的策略对于细胞位置允许的最大状态值为界限参数。在环境状态描述图的基础上，设定界限1：细胞状态值为0，此界限区域为带球搜索最安全区域，不在对方球员的控制之下；界限2：相对界限1放宽一些，定细胞状态值稍大，此界限区域为从最安全区域出发分别向左向右扩散出的带球搜索较安全区域，对方球员对此区域的控制能力增加；根据情况还可继续放宽界限，制定界限3、界限4等。如果一个小界限的初始搜索能找到路径，则搜索算法只要在最安全区域尝试少数几个位置就能找到正确的路径。如果没有成功找到路径，将在随后的调用中逐渐放宽界限，取界限2、3，即让其在较安全区域甚至弱安全区域搜索路径，直到搜索成功或者到达取值范围的端点。
　　这样，即使是失败的几次调用findpath()也只使用了较少的内存；同时也加快了路径检测的速度。因为小界限调用会更快地达到失败条件，也提高了路径暂被其他行动者阻断时的执行性能。
　　如果没有成功找到通向目标点的带球路径，可能是路径不存在或者搜索已经到了强加的极限，这时不应该让球员反复调用失败的搜索算法而延误动作时机。为了使带球智能体的反应更加灵敏，采取返回findpartpath()，先得到部分路径的策略。只需修改findpath()，即设定搜索节点循环相应次数后停止计算(循环次数确保能产生一条合理长度的路径)，把离目标点最近的点作为子目标点，返回实现的部分路径。从小界限开始趋向最大界限进行路径搜索的伪码实现如下：
　　for i=0；i　　if flag=1 then
　　break；//某个界限下路径搜索成功
　　else
　　if i==PathCoordinator() then
　　findpartpath(constrain[i])；//返回部分路径
　　else
　　findpath(constrain[i])；//调用整体路径搜索
　　end if
　　end if
　　end for
　　带球队员通过一个小界限参数调用搜索算法，可以立即沿着返回的部分路径移动，然后使用一个逐渐增大的界限参数再次调用搜索算法得到部分或全部路径，带球者最终会找到一条通往目的地的路径，或者在一个离终点不远的地方停止。总之，界限参数和返回部分路径的方法可以使智能体的反应更加灵敏，不管发生什么情况，带球队员总会有所作为，而不是只站在原地。
4 应用效果测试
　　本文进行的比赛测试是在SoccerServer10.xx版本下完成的。将基于细胞自动机的带球路径搜索策略应用到中南大学RoboCup仿真球队(CSU_Yunlu 2005)中，先后对采用本文策略和不采用本文策略的CSU_YunLu仿真球队作了长时间的测试。
　　将未采用新策略的球队和采用新策略的球队与同一支仿真球队比赛，运用仿真调试工具SoccerDoctor得到两次比赛中带球成功率的统计图，如图3、图4所示。