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)