Run-time Evaluation of Collaborative Opportunities

 

One of CMUnited-97's main features is the robots' ability to collaborate by passing the ball. When in active mode, the robots use an evaluation function that takes into account teammate and opponent positions to determine whether to pass the ball or whether to shoot. In particular, as part of the formation definition, each position has a set of positions to which it considers passing. For example, a defender might consider passing to any forward or midfielder, while a forward would consider passing to other forwards, but not backwards to a midfielder or defender.

For each such position that is occupied by a teammate, the robot evaluates the pass to that position as well as evaluating its own shot. To evaluate each possible pass, the robot computes the obstruction-free-index of the two line segments that the ball must traverse if the receiver is to shoot the ball (lines b and c in Figure 7). In the case of a shot, only one line segment must be considered (line a). The value of each possible pass or shot is the product of the relevant obstruction-free-indices. Robots can be biased towards passing or shooting by further multiplying the values by a factor determined by the relative proximities of the active robot and the potential receivers to the goal. The robot chooses the pass or shot with the maximum value. The obstruction-free-index of line segment l is computed by the following algorithm (variable names correspond to those in Figure 7):

• obstruction-free-index = 1.
• For each opponent O:
  • Compute the distance x from O to l and the distance y along l to l's origin, i.e. the end at which the ball will be kicked by the robot (See Figure 7).
  • Define constants min-dist and max-denominator. Opponents farther than min-dist from l are not considered. When discounting obstruction-free-index in the next step, the y distance is never considered to be larger than max-denominator. For example, in Figure 7, the opponent near the goal would be evaluated with y = max-denominator, rather than its actual distance from the ball. The reasoning is that beyond distance max-denominator, the opponent has enough time to block the ball: the extra distance is no longer useful.
  • if x < min-dist and x < y,
    obstruction-free-index *= max-demoninator, .
• return obstruction-free-index.

  
Figure 7: Pass Evaluation--To evaluate a pass to a teammate, the robot considers how open the paths are from the ball to the teammate (line b) and from the teammate to the goal (line c). When evaluating shots, it considers the line from the ball to the goal (line a). For each opponent and each line segment, it computes the opponent's distance to the segment (x) and along the segment to the origin. The smaller x is and the larger y is, the easier it would be for the opponent to intercept the ball. Note that some opponents would cause discounts in the values of passes along more than one segment.

Thus the obstruction-free-index reflects how easily an opponent could intercept the pass or the subsequent shot. The closer the opponent is to the line and the farther it is from the ball, the better chance it has of intercepting the ball.