Creating intelligent agents that can carry out team interaction is one of the most important tasks in the eld of arti cial intelligence. For experimental veri cation of the e ectiveness of the proposed theoretical approaches to its construction, virtual football championship held annually as a part of the Robocup world championship One of the important tasks in building the intelligence of a robot football player is the implementation of the pass. As part of this task, the agent must be able to correctly understand the situation, determine the possibility of performing a pass, and calculate the parameters of the ball strike. The article will consider the method of determining the area where the ball will be passed without the possibility of interception of the ball during its ight by an opponent and with a known advantage of the receiver within its limits. This area is calculated by determining the receivers, interceptors, and calculating special areas, including the Voronoi diagram. The proposed algorithm also meets the requirements for anytime algorithms, which allows you to achieve a result whose quality is proportional to the time spent on calculations, which is extremely important in such a rapidly changing environment as virtual football. Experimental testing con rmed the algorithm's performance as an anytime algorithm, namely the ability to execute the algorithm faster due to the quality of the result.
The creation of intelligent agents that would be capable of solving problems in
groups when opposing another team is currently one of the central problems in
arti cial intelligence [
In [
In [
The solution for a ball interception behaviour developed as part of the
CAMBADA team from University of Aveiro for RoboCup Middle Size League is
presented in [
In [
An important feature of the virtual football environment is the need to make
decisions in real time [
The game involves two teams of robot agents, 11 players on each side: T = Ti; O = Oi, where i = 1; 11.
Each player has a set of static parameters, which include the radius r of the body, the area of possession of the ball KICKABLE AREA, the maximum running speed Vmax, etc. In addition, the current state of the player is characterized by dynamic parameters, such as coordinates (x; y), current speed V , direction of movement w, etc.
The players can perform commands: Kick - kick the ball (the ball must be
in the KICKABLE AREA of the player); Dash - accelerate the run; Catch
capture the ball (only for the goalkeeper), etc [
To implement the pass, the player must execute the Kick command so that the ball begins to move towards the partner. Let us consider the situation when the player Ti decided to give the pass to partner Tj. Agent needs to determine the direction of movement and the initial speed of the ball so that the partner Tj would reach the ball at the desired point and at the same time no players of the other team (opponents) can intercept the ball, i.e. reach it earlier than Tj.
Let's consider the problem under the worst case assumption, when all opponents are already moving along the shortest path to the ball trajectory at maximum speed Vmax to intercept the ball.
In addition, we assume that the agent knows the exact (cleared of servergenerated noise) global (Cartesian) coordinates of the ball and all players involved in the episode.
Under these assumptions, the task boils down to the de nition of a "Safety Pass Area" (SPA), each point of which satis es the above conditions.
Algorithm of SPA calculation will be developed as an anytime algorithm. 3
Let's denote the necessary concepts: "The Game Area" - GA, "The In uence Area" - IA, "The Reach Area" - RA, "The Safe Catching Area" - SCA.
Then, SPA can be calculated by nding the intersection of these sets as follows:
SP A = GA \ IA \ RA \ SCA (1) 3.1
It is represented by the four coordinates that de ne the area of the possible
location of the objects in the game. It is the constant parameters set by the
server [
To nd the area of in uence, you need to build a Voronoi diagram[
If for the number of points required to build a diagram the coordinates of players is taken, and for plane - game area, the locus of the graphs will be considered as areas of in uence of each player (see Fig. 1).
This diagram can also be used for solving other tasks, such as analyzing the situation on the eld, which makes it useful to calculate it. This area is a set of points in which the ball can be after the Kick command execution. If the calculated area does not have any shared points with IA, then a safe pass cannot be executed.
We need to calculate the maximum ight length L of the ball, which becomes the radius of the circle with center in the coordinate of the ball (see Fig 2). To nd it, the agent needs to calculate the value of the power parameter of the kick command.
Let the real value of the force be act pow. Then, we calculate it by using the
formula 2 [
act pow = power (1 0:25 dir dif f 180 0:25
dist dif f
kickable margin
)
Then, putting the obtained value into the formula 3 allows us to nd the absolute
of the applied acceleration vector, where kick power rate is the parameter set by
the server [
To nd them, you need to calculate the reach area and the area of in uence of each player.
We consider potential receivers as players who have at least one vertex of the in uence area within the reach area. 3.5
It is advisable to consider the Receivers in a non-random order.
Three options can be o ered at least for creating an order: { those who are closer to the goal go rst { those who are closer to the ball go rst { those who border strongly with my dominant area and weakly with enemies go rst
The amount of receivers to be considered can be decreased. 3.6
We need limit the amount of potential trajectories of the ball. To begin, we nd two points of DA, which are at the minimum angle and maximum angle relative to the coordinate of the ball.
Then, let the interceptors be players-opponents who are closer to the ball then target-player (the player to whom the pass is given), and at an angle in the range [ 90; + 90] relative to the ball. Let's mark them as E = Ei (see Fig. 3.), where i = 1; p. It is advisable to consider the interceptors also in a non-random order.
Three options can be o ered at least for creating an order: { those who are closer to the receiver go rst { those who are closer to the ball go rst { those who border strongly with receivers dominant area go rst
The amount of interceptors to be considered can be decreased. 3.8
Potential ight trajectories of the ball will be considered as a set of rays casted in the range of previously found angles. The number of possible angles is limited and equal to amount of trajectories. ATA's requirements force agent to check only some of them. To ensure the optimal result the simple order of checking the angles consider as non-optimal.
One of the possible approaches to choose the order is to begin with checking of the extreme angles and then at each step check the angle, which is between the already checked neighbor angles and divides the greatest interval.
Also, there is an approach in which the agent have the point of interest. For example, the task is to push the ball closer to the goal. So, it might help if the angle's probability of checking depends on the distance to the target angle. 3.9
Further, let B; Ei; Ti be the coordinates of the objects. We cast in the range of previously found angles [ ; ] M rays R = Ri, where i = 1; m, which are vectors of unit length. Then, (B + R!) - the set of possible trajectories of the ball.
For each i and j in (B + R!i) and Ej we nd the intercept point Iij . As mentioned earlier, we assume that the opponent Ej chose the shortest path to the trajectory of the ball, namely, the perpendicular line to (B + R!i). Then, to calculate the point Iij nd the projection of the vector (B + BE!j) on the ray Ri, which is the length of the vector BI!ij , by the formula (5). So, the intercept point can be calculated by the formula (6): jBI!ij j = proj !B
Ri
BE!j =
B
BE!j Ri
! ! jRij
Iij = B + R!i jB!Iij
For each Ej time tij of reaching Iij can be obtained by the formula (7). Regarding the initial assumption that the opponent moves at the constant speed Vmax follows: tij = jEj I!ij j
Vmax
We calculate a point Xij , which is the farthest point, passing to which the ball will be intercepted. Firstly, by the formula 8 we nd the value of the initial velocity V0ji , at which it during tij will pass the distance jBIij j. Take into account act pow, calculated by the formula (2). Secondly, we calculate the distance Sij , which the ball will pass with V0ji , by the formula 9.
Then, the point Xij (see Fig. 5.a) will be:
V0ij = (1 jBIij j (1 DECAY )
DECAY tij )) act pow Sij = (1
V0ij
DECAY ) Xij = B + R!i Sij (5) (6) (7) (8) (9)
Next, we select for each i of Xij the most farthest point from B and call it Gi. The curve obtained by connecting the points Gi (see Fig. 5.b) is the boundary of the safe pass area from below and the boundary of the interception area from above.
a. Xij calculation b. Gi calculation
The selection of the speci c point from the SPA can be performed based on various criteria such as: { distance to the goal { distance to the target player { distance to the edge of the eld 3.11
The player must correctly determine that he was selected as the receiver and start moving immediately to the assumed point of receiving the pass. For correct calculation of this point, it is necessary to take into account that he will be able to see the ball ying in his direction only after one frame. 4
The pseudocode of the algorithm will be o ered below: Data: Ti - coordinate of the player with ball; Tj - coordinate of the receiver; B - coordinate of the ball; T = Ti, where i = 1; n - teammates' coordinates; O = Oi, where i = 1; n - opponents' coordinates; M = const - the amount of trajectories; Result: SP A = SP Ai, where i = 1; m ; RA RA Calculation(Ti; B); IA IA Calculation(GA; T; O); R Receivers M arking(RA; IA); Receivers Ordering(R); R Receivers M arking(RA; IA); SP A ; for r 2 R do if need to interrupt then
interrupt; end alpha; beta Caclulate A B(RA; IA); T r Calculate T rajectories(alpha; beta); T rajectories Ordering(T r); I Interceptors M arking(alpha; beta; IA); Interceptors Ordering(I); for i 2 I do if need to interrupt then
interrupt; end X ; ; for tr 2 T r do if need to interrupt then
interrupt; end x Calculate X(tr; B; i); end
Add T o X(X; x); end G Calculate G(X); spa Calculate SP A(G; IA; RA);
Add T o SP A(SP A; spa); end P ASS P OIN T
Select P oint(SP A); 5
In this section, we apply our algorithm to the RoboCup Simulation League and evaluate how well it works.
The graph above shows how the algorithm execution time depends on the quality of its result (see Fig. 6). The algorithm works as the anytime algorithm, as you can see. There are three curves on the graph: the receiving curve, the interceptor curve, and the trajectory curve.
The experiment was carried out with a separate decrease in the number of considered receivers, interceptors, and trajectories. Reducing several parameters at the same time can result in an even greater reduction of the algorithm execution time. 5.1
The estimated parameter Quality was calculated as follows:
Quality = Calculated SP A Area 100=SP A Rael Area (11)
A decrease of the number of considered receivers strongly a ects the result time (see Fig. 6). 5.2
A decrease of the number of considered interceptors does not signi cantly a ect the result time (see Fig. 6). 5.3
The estimated parameter Quality was calculated as follows in equation (12).
A decrease of the number of considered interceptors has a little e ect on the result time (see Fig. 6).
In this paper we presented a variety of methods to calculate the possibility and parameters of the pass in the virtual environment of the RoboCup Simulation League. We introduced an approach to ball passing that has quality which depends on the time of calculation.
We introduced an approach to ball passing that has quality which depends on the time of calculation.