摘 要：机器人足球中的路径优化算法，虽然大多数都考虑到了球的运动问题，并且在机器人的移动时间和击球点位置是否有利于进行下一步策略(例如射门，解围)做出了综合的考虑，但并没有具体考虑球在移动中是否会达到更加有利于击球的位置。该文提出击球点择优的算法，旨在配合路径优化算法，求解更好的截球射门点，并通过实验验证了其有效性。
关键词：机器人足球； 击球点；路径优化；预测； 射门
机器人足球比赛对抗激烈，场上形势瞬息万变，实时性非常强。合理地判断场面情况并采用相应的策略是通往比赛成功最关键的钥匙。其中，机器人足球爱好者们对于路径优化算法问题做了大量的研究。
和真正的足球比赛相同，机器人足球比赛也需要掌握触球的优先权，从而把握比赛的主动权，成为比赛的主导。因此路径优化算法的研究目标大多数是节约到达定点的时间，从而减少机器人追逐球的时间，更快地碰到球。但并非所有情况下触球的优先权都是首要考虑的因素。球是长期处于运动状态中的，延长触碰到球的时间，就可以让球的移动时间增加。某些形势下，球的运动时间增加，可以让球到达更有利于机器人击球的位置。这就涉及到击球点择优的问题。
击球点择优中较流行的是基于粒子群优化算法(particle swarm optimization ， PSO)[1]的策略[2]，但大多数算法考虑的范围太大，时间复杂度较高，并且有可能球无法到达所求出的击球点。另外还有许多路径优化算法中包含了对击球点择优的考虑，但并没有详细展开进行研究。
1击球点择优算法
现在普遍采用的路径优化算法都已球员首先触球为第一优先，在这种情况下，前锋射门时并不能找到最优的射门地点。例如:如图1所示，机器人小车有vr的初始速度，球有vb的初始速度，图中实线是球的移动方向。基于快速触球的路径优化算法大多数会让机器人选择p1那样的S型路径(因为初速度以及调整射门角度才会产生这样的路径)。虽然这个路径更快地接触到球，并且也通过调整得到了一定的射门角度，但是如果机器人选择P2路线进行射门，可选择的射门角度范围比通过P1路线进行射门要大的多。
笔者提出击球点择优的算法，旨在通过射门时调用以达到机器人选择p2路径的效果。击球点择优算法并不是独立的路径优化算法，而是其辅助算法。击球点择优算法的目的在于让机器人选择更具优势的击球点。
图1
2击球点择优算法的构成:
击球点择优算法基于预测模块，评价模块，动作模块三个模块组成，其每个模块的具体作用如下:
1. 预测模块:该模块旨在进行局面预测，判断算法触发条件(触球周期)是否符合比赛情势要求，并最终确定是否调用择优动作。
2. 评价模块:该模块通过一定的预测计算算法在可选范围内得出最有利的击球点。
3. 动作模块:该模块通过调整机器人的运动参数使目标机器人在计算好的时间到达最有利的击球点。
3击球点择优—预测模块
预测模块的计算是基于递推算法的,并考虑到常用的路径择优算法，以达到预测机器人运动路径并计算其时间周期开销的目的。其中路径择优算法可以参考文献[3-6]。
预测模块流程图如图2所示，用于预测机器人最快碰到球的时间周期。注意，因为无法知道对方策略的路径算法，所以预测对方机器人时应该采用快速碰到球的算法，而尽量少考虑调整角度的时间周期开销。事实上，这保证了尽管在最短的时间内，我方仍然能首先触球的要求。
球场上的局势总是动态的，基于静态的策略往往因为跟不上实际比赛的速度要求而显得非常被动。大多数机器人足球队都在预测方面下足了功夫，各种预测算法也取得了较好的效果。在此不再赘述。
图2
4 击球点择优—评价模块
评价模块是击球点择优算法中必不可少的一部分。击球点择优算法需要通过评价模块判定各击球点的适应度，从中挑选中最有优势的击球点。评价模块需要总结大量实验数据，依靠实验结果和经验确定各个因素的重要程度。笔者结合自身的比赛经验以及实验数据，得到一个适合用于射门的击球点适应度评价函数。
F = -k1t+k2θ1+k3θ2
式中F(fitness)即为适应度，t为球到达击球点所需要的预测时间。如图3所示，θ1为球到达击球点时球心和球门中点的连线与底线的角度(≤90°)，θ2为球到达击球点时车的中心和球心连线与球心和球门中点连线的夹角(≤180°)，k1，k2，k3为对应的调整参数。
图3
5 击球点择优—动作模块
因为机器人行动的基本要求为尽快碰触到球，所以机器人的跑位速度始终维持在机器人可以到达的最高速度上，这样就不能实现等待或者减速以使足球达到择优点的要求。并且，为了使机器人在达到击球点后还有满足一定要求的速度以及角度来进行完美的射门动作，在得到击球择优点和预计到达周期后，还要根据结果进行计算，修正机器人的跑位动作。
在实际策略中，笔者采用根据距离击球点的距离和时间进行分段处理的分段算法控制跑位动作。
本质上，该部分不属于击球点择优算法的求解部分，而是在得出击球点之后的动作，考虑到，如果存在一个良好的可根据目标点和要求到达时间运作的跑位函数，那么该部分的算法可以被其完美代替，故不再赘述。
6 击球点择优—算法实现
实现击球点择优算法，首先必须放弃最快速触碰球，但如果让对方机器人先碰到球，整个算法就毫无意义，因此不能放弃触碰球的优先权。平衡这两个看起来比较矛盾的想法，需要判断哪段时间周期内，我方机器人是占有优势的。
6.1预测占优的时间周期
利用预测模块，预测出对方机器人最快触碰到球所需要的时间周期t。然后进行T = t - dt的计算。其中T为我方机器人的择优可能时间，t为对方机器人将接触到球的时间，dt为调整参数，约等于我方机器人完成射门动作的时间，用以减少”如果我方机器人在临近t时间周期时到达击球点，对方机器人同时也很接近击球点，此时将对我方机器人的动作造成干扰的可能”。
该算法在每周期执行一次，因此公式中的每个时间参数，包括调整值，都为动态变化。
这里需要注意的是，因为球和机器人都是处于运动状态的，并非该轨迹上所有点都是机器人能够达到的击球点。因此在求最优击球点时，还需要预测机器人是否能在球到达该点的同时可以触球。
6.2求出最优的击球点
因为T时间内不会有机器人接触球，球的运动轨迹实
际为一条直线，此时可能的击球点已经收缩成为一条直线，此时调用评价模块，评价该线段上的每个点的击球有利度，并得出有利度最高的点，该点即为该周期内的预计最有利击球点。
接着，就会调用动作模块根据求出的击球点调整机器人的动作。
6.3每周期重复计算过程
赛场上的情况瞬息万变，己方也无法推断对方的策略，所以每周期该算法都会被重复调用，并根据最新的场上情况逐步修正结果。上周期的最优击球点可能因为某些原因在这周期成为次优，或者更可能因为对方防守机器人的速度提升成为安全时间内无法达到的点。而我方机器人经过一周期的运动调整，所需要的调整时间dt也已经减少。所以，这样每周期不断进行计算修正，直到最终触球，才算完成了整个击球点择优算法的计算过程。
7仿真实验与总结
笔者在Robot Soccer 5V5仿真实验平台上进行该算法实际有效性测试，测试计划为分别在场地的左上，左下，右上，右下半场使用同一传中动作对足球进行传中并造成前锋射门机会，然后统计在更为有利的机器点进行射门的次数。同时，我们还采用了一个不调用击球点择优算法的策略作为对照组进行测试。测试结果如下:
组别测试次数传中次数在择优点射门择优165153110不择优15014219
一次对照分析:
仿真平台为Robot Soccer仿真5V5。实验的击球点择优类型为射门点择优。
图4-1为初始状态，此时我方1号机器人进行传球，2号机器人在跑动中接应，2号机器人已经有朝向球门的速度。
图4-2为没有加入击球点择优算法的机器人跑动击球情况。
图4-3为加入了击球点择优算法后机器人的跑动击球情况。
图4-4为有对方球员阻扰的情况。
图4-1 图4-2
图4-3 图4-4
如图4-2所示，由于没有击球点择优算法的辅助，机器人选择了快速触碰球的策略，导致触碰球时射门非常困难。如图4-3所示，加入了击球点择优算法之后机器人放慢了移动速度，让球移动到更好的位置后再触碰球，此时射门角度极佳，进球率大大提高。如图4-4所示，因为有对方机器人的阻扰，不可能形成4-3所示的射门，因此我方机器人采取了和4-2所示的相同的路径，这样能优先于对方机器人触碰到球，从而拿到主动权。
由实验结果可见，击球点择优算法帮助机器人更明智地选择击球的时间，并且又不放弃击球的主动权，在机器人足球比赛的策略中具有可行性和有效性。
参考文献：
.西安交通大学学报， 2007， 41 (11) : 1326 - 1329。
