=Paper=
{{Paper
|id=Vol-2590/paper25
|storemode=property
|title=Development of Anytime Algorithms for Pass Implementation in Robocup Simulation League
|pdfUrl=https://ceur-ws.org/Vol-2590/paper25.pdf
|volume=Vol-2590
|authors=Borislav Novikov,Michail Panteleyev
|dblpUrl=https://dblp.org/rec/conf/micsecs/NovikovP19
}}
==Development of Anytime Algorithms for Pass Implementation in Robocup Simulation League==
https://ceur-ws.org/Vol-2590/paper25.pdf
Development of Anytime Algorithms for Pass
Implementation in Robocup Simulation League
Borislav Novikov[0000−0001−6283−720X] and Michail
Panteleyev[0000−0002−6077−760X]
Saint Petersburg Electrotechnical University, ul. Professora Popova 5, 197376 St.
Petersburg, Russian Federation
{bnovikov012, MPanteleyev}@gmail.com
Abstract. Creating intelligent agents that can carry out team interac-
tion is one of the most important tasks in the field of artificial intelli-
gence. For experimental verification of the effectiveness 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
flight by an opponent and with a known advantage of the receiver within
its limits. This area is calculated by determining the receivers, intercep-
tors, 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
confirmed the algorithm’s performance as an anytime algorithm, namely
the ability to execute the algorithm faster due to the quality of the result.
Keywords: RoboCup · Intelligent agents · Anytime algorithm · Virtual
soccer · Pass implementation.
1 Introduction
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
artificial intelligence [1]. The Robot World Cup (RoboCup) [2] championship
is held annually to experimentally examine the multi-agent counteraction mod-
els in virtual soccer. One of the important particular tasks in the construction
Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
2 B.M. Novikov, M.G. Panteleyev
of intelligence of the football player agent is to determine the possibility and
parameters of the pass implementation in a given situation.
In [3] an approach to ball interception based on introduced concepts of qual-
itative and relative velocity (quick to left, neutral, quick to right) are proposed
and investigated. An experimental comparison of several methods was carried
out: an exact numerical calculation of the interception point, a naive method
with movement directly to the ball, a method based on reinforcement learning,
and method with qualitative velocities. The experiments have shown the numer-
ical method and the learned behavior to be the best, while the numerical method
is slightly preferable.
In [4] a simple and robust algorithm for the interception of a moving ball
by an omnidirectional robot for RoboCup Small Size League is proposed. The
heuristic algorithm requires minimal knowledge of robot dynamics and based on
two key ideas: (i) consideration of ball motion via transition to a reference frame
where the ball is static and (ii) planning the motion of the robot in such a refer-
ence frame from the geometric viewpoint. Experiments conducted in a real SSL
environment confirmed successful interception in a variety of scenarios, char-
acterized by different directions of ball motion and the positional relationships
between the ball, robot and goal.
The solution for a ball interception behaviour developed as part of the CAM-
BADA team from University of Aveiro for RoboCup Middle Size League is pre-
sented in [5]. CAMBADA solution is based on a uniformly accelerated robot
model, that takes into account a number of parameters, in particular ball veloc-
ity, robot current v
In [6] is considered an approach based on the calculation of the dominant
area of one agent team with respect to an opponent team. Inside the calculated
area, players have an advantage, namely, each point of this area is closer to them
than to the opponent. It means that the implementation of the pass along the
trajectory located inside this area will be made under the assumption that the
opponent will not be the first on the ball.
An important feature of the virtual football environment is the need to make
decisions in real time [7]. According to that, the allowable thinking time can vary
significantly depending on the situation. It follows that algorithms for solving
specific problems should be constructed as anytime algorithms (ATA) [8], which
allow the agent exchange the computation time for the quality of the result.
2 Problem statement
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 char-
acterized by dynamic parameters, such as coordinates (x, y), current speed V ,
direction of movement w, etc.
Title Suppressed Due to Excessive Length 3
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 [9].
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 op-
ponents 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 server-
generated noise) global (Cartesian) coordinates of the ball and all players in-
volved in the episode.
Under these assumptions, the task boils down to the definition of a ”Safety
Pass Area” (SPA), each point of which satisfies the above conditions.
Algorithm of SPA calculation will be developed as an anytime algorithm.
3 Calculating the Safe Pass Area
Let’s denote the necessary concepts: ”The Game Area” - GA, ”The Influence
Area” - IA, ”The Reach Area” - RA, ”The Safe Catching Area” - SCA.
Then, SPA can be calculated by finding the intersection of these sets as
follows:
SP A = GA ∩ IA ∩ RA ∩ SCA (1)
3.1 The Game Area
It is represented by the four coordinates that define the area of the possible
location of the objects in the game. It is the constant parameters set by the
server [9].
3.2 The Influence Area [10]
To find the area of influence, you need to build a Voronoi diagram[11]. This
diagram is based on a set of points P of the plane S. It is a partition of this
plane, in which each point pi of the set P is mapped to the area of this partition
si . Each area contains all the points of the plane that are closer to the point of
this area pi than to other points pj , where j! = i. the area si Mapped to point
pi is a polygon and is called a locus.
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 influence of each player (see Fig. 1).
This diagram can also be used for solving other tasks, such as analyzing the
situation on the field, which makes it useful to calculate it.
4 B.M. Novikov, M.G. Panteleyev
Fig. 1: The Influence Area
3.3 The Reach Area
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 flight length L of the ball, which becomes
the radius of the circle with center in the coordinate of the ball (see Fig 2). To
find 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 [12]. Its value depends on the distance dist dif f between the player
and ball and the angle dir dif f between the direction of the body and ball. The
power value will be equal to 100, because it is a maximum value of the power
parameter of the kick command. The kickable margin parameter is set by the
server and is pre-known [9].
dir dif f dist dif f
act pow = power ∗ (1 − 0.25 ∗ − 0.25 ∗ ) (2)
180 kickable margin
Then, putting the obtained value into the formula 3 allows us to find the absolute
of the applied acceleration vector, where kick power rate is the parameter set by
the server [9]:
−
→
|V0 | = |→
−
a | = act pow ∗ kick power rate (3)
−→
Thus, we know the maximum initial velocity of the ball V 0 = |V 0|. Knowing
the ball speed deceleration parameter DECAY set by the server DECAY [9], L
can be obtained as follows:
V0
L= (4)
1 − DECAY
Title Suppressed Due to Excessive Length 5
Fig. 2: The Reach Area
3.4 Marking the Receivers
The receiver is within the reach area or can reach it earlier than anyone else, at
least at one point.
To find them, you need to calculate the reach area and the area of influence
of each player.
We consider potential receivers as players who have at least one vertex of the
influence area within the reach area.
3.5 The Order of Receivers
It is advisable to consider the Receivers in a non-random order.
Three options can be offered at least for creating an order:
– those who are closer to the goal go first
– those who are closer to the ball go first
– those who border strongly with my dominant area and weakly with enemies
go first
The amount of receivers to be considered can be decreased.
3.6 Marking the Interceptors
We need limit the amount of potential trajectories of the ball. To begin, we find
two points of DA, which are at the minimum angle α and maximum angle β
relative to the coordinate of the ball.
6 B.M. Novikov, M.G. Panteleyev
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.
Fig. 3: Marking the Interceptors
3.7 The Order of Interceptors
It is advisable to consider the interceptors also in a non-random order.
Three options can be offered at least for creating an order:
– those who are closer to the receiver go first
– those who are closer to the ball go first
– those who border strongly with receivers dominant area go first
The amount of interceptors to be considered can be decreased.
3.8 The Flight Trajectories
Potential flight 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.
Title Suppressed Due to Excessive Length 7
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 The Area Calculation
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 + Ri ) and Ej we find 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 + Ri ). Then, to
−−−−−−−→
calculate the point Iij find the projection of the vector (B + BEj ) on the ray
−−→
Ri , which is the length of the vector BIij , by the formula (5). So, the intercept
point can be calculated by the formula (6):
−−−−−−→ − →
−−→ −−−−−−→ B − BEj · Ri
|BIij | = proj−
→ B − BEj = −
→ (5)
Ri |Ri |
−
→ −−→
Iij = B + Ri ∗ |BIi | (6)
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:
−−−→
|Ej Iij |
tij = (7)
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 find the value of the initial
velocity V0ji , at which it during tij will pass the distance |BIij |. 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.
|BIij | ∗ (1 − DECAY )
V0ij = (8)
(1 − DECAY tij )) ∗ act pow
V0ij
Sij = (9)
(1 − DECAY )
Then, the point Xij (see Fig. 5.a) will be:
−
→
Xij = B + Ri ∗ Sij (10)
8 B.M. Novikov, M.G. Panteleyev
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
Fig. 5: SCA Calculation
3.10 The Point Selection.
The selection of the specific 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 field
3.11 The Actions of the Receiver
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 flying in his direction only after one frame.
4 The SPA Calculation Algorithm
The pseudocode of the algorithm will be offered below:
Title Suppressed Due to Excessive Length 9
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 ∈ 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 ∈ I do
if need to interrupt then
interrupt;
end
X←∅;
for tr ∈ 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 The Results of Experiments
In this section, we apply our algorithm to the RoboCup Simulation League and
evaluate how well it works.
10 B.M. Novikov, M.G. Panteleyev
Fig. 6: Experiments Results
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 parame-
ters at the same time can result in an even greater reduction of the algorithm
execution time.
5.1 Reducing the amount of receivers considered
Table 1: Comparison of the quality and execution time of the algorithm for different
values of the number of considered receivers
Amount, % Quality, % Time, ms
20 22 11.2
40 44 22.4
60 64 33.6
80 89 44.8
100 100 56
Title Suppressed Due to Excessive Length 11
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 affects the result
time (see Fig. 6).
5.2 Reducing the number of interceptors considered
Table 2: Comparison of the quality and execution time of the algorithm for different
values of the number of considered interceptors
Amount, % Quality, % Time, ms
20 51 11.2
40 72 22.4
60 91 33.6
80 96 44.8
100 100 56
The estimated parameter Quality was calculated as follows:
Quality = Calculated SCA Area ∗ 100/SCA Real Area (12)
A decrease of the number of considered interceptors does not significantly
affect the result time (see Fig. 6).
5.3 Reducing the number of trajectories considered
Table 3: Comparison of the quality and execution time of the algorithm for different
values of the number of considered trajectories
Amount, % Quality, % Time, ms
20 84 11.2
40 92 22.4
60 95 33.6
80 99 44.8
100 100 56
The estimated parameter Quality was calculated as follows in equation (12).
A decrease of the number of considered interceptors has a little effect on the
result time (see Fig. 6).
12 B.M. Novikov, M.G. Panteleyev
6 Conclusion Remarks
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 de-
pends on the time of calculation.
We introduced an approach to ball passing that has quality which depends
on the time of calculation.
References
1. Panteleev M.G., Puzankov D.V. Intelligent agents and multiagent systems, SP-
bGETU ”LETI” Publishing, SPb (2015)
2. RoboCup. The Robot World Cup Initiative. Robocup officiale site. Available at:
http://www.robocup.org
3. Stolzenburg, F., Obst, O., Murray, J. Qualitative velocity and ball interception. In:
Jarke, M., Lakemeyer, G., Koehler, J. (eds.) KI 2002. LNCS (LNAI), vol. 2479, pp.
283–298. Springer, Heidelberg (2002).
4. Makarov P.A. et al. A Model-Free Algorithm of Moving Ball Interception by Holo-
nomic Robot Using Geometric Approach. In: Chalup S., Niemueller T., Suthakorn
J., Williams MA. (eds) RoboCup 2019: Robot World Cup XXIII. RoboCup 2019.
LNCS, vol. 11531, pp. 166-175. Springer, Cham
5. Cunha J., Lau N., Rodrigues J. Ball Interception Behaviour in Robotic Soccer. In:
T. Rofer et al. (Eds.): Robot Soccer World Cup XV, LNCS vol. 7416, pp. 114–125,
Springer-Verlag Berlin Heidelberg (2012)
6. Nakanishi R., Bruce J., Murakami K., Naruse T., Veloso M.M. Cooperative 3-robot
passing and shooting in the RoboCup small size league. In: Lakemeyer, G., Sklar,
E., Sorrenti, D.G., Takahashi, T. (eds.) RoboCup 2006: Robot Soccer World Cup
X. LNCS (LNAI), vol. 4434, pp. 418–425. Springer, Heidelberg (2007)
7. Panteleev M.G. A formal model of proactive iterative action planning for real-time
intelligent agents [In Russian]. Proc. of the 14 National Conference on Artificial
Intelligence with International Participation KII-2014. - Kazan: Fizmatlit. - V 1. -
pp.323-334. (2014)
8. Zilberstein S. Using Anytime Algorithms in Intelligent Systems. AI Magazine 17(3),
73-83 (1996)
9. Chen M, Dorer K. RoboCup Soccer Server, 150 p. (2003)
10. Dashti H.T. et al. Dynamic Positioning Based on Voronoi Cells (DPVC). In: Bre-
denfeld A., Jacoff A., Noda I., Takahashi Y. (eds) RoboCup 2005: Robot Soccer
World Cup IX. RoboCup 2005. Lecture Notes in Computer Science, vol 4020.
Springer, Berlin, Heidelberg
11. Dobrin A. A review of properties and variations of Voronoi diagrams. Whitman
College (2005)
12. Remco de Boer, Jelle Kok, Frans Groen. UvA Trilearn 2002 team description –
Faculty of Science, University of Amsterdam (2002)