Agent Navigation in Virtual Soccer: Comparative Analysis of Algorithms Michail Panteleyev1[0000−0002−6077−760X] and Anushervon Salimov1[0000−0003−1592−7012] Saint Petersburg Electrotechnical University ”LETI”, Department of Computer Science and Engneering, ul. Professora Popova 5, 197376 St. Petersburg, Russian Federation {mpanteleyev,safmail96}@gmail.com Abstract. The article is devoted to the analysis of various methods of solving navigation problems by an intelligent agent in the environment of virtual football Robocup Soccer on the basis of noisy data coming from a visual sensor. Two groups of methods for calculating the absolute coordi- nates of objects based on sensory data on flags and lines are considered: trigonometric methods and methods based on the use of the Kalman filter and particle filter. A software tool developed for experimental re- search and allowing arbitrary variation of the conditions for solving the navigation problem is briefly described. Experimental results of the com- parative analysis of the speed and accuracy of algorithms implementing various methods are presented. The obtained results allow the agent to solve the navigation problem using anytime-algorithms, exchanging the solution time for the quality (accuracy) of the result. Taking into account the obtained results, the directions of further research on the implemen- tation of the assessment of the tactical situation in virtual soccer are determined. · · · · · · Keywords: intelligent agent multi-agent system virtual soccer RoboCup Soccer localization anytime algorithms particle filter. 1 Introduction The creation of intelligent agents (IA) and based on them multi-agent systems (MAS) is currently the main direction of the development of artificial intelligence [1, 2]. IA is understood as autonomous systems that perceive the environment and implement purposeful behavior in this environment. An important feature of IA is their ability to act in groups, including in the face of active opposition from other groups of agents. In recent years, virtual soccer has been used as Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 2 M. Panteleyev, A. Salimov a reference platform for practicing various approaches to building real-time IA (RIA) and tactics of group behavior of MAS in conditions of group opposition [3-5]. An ambitious task has been set by the community of experts in the field of IA and MAS - by 2050 to create a team of autonomous soccer players who can beat the team of world champions. One of the important tasks solved by the IA is navigation (determination of one’s own location) based on information received from visual sensors. To solve this problem, probabilistic approaches are widely used, the most famous of which are the Kalman filter and particle filter [6, 7]. The selection of the most effective methods and algorithms for solving the navigation problem, taking into account the specific features of the specific operational environment of the IA, requires their experimental comparative analysis. 1.1 The features of the navigation task in the soccer environment Virtual soccer environment (VS) RoboCup Soccer Server allows real-time sim- ulation of the game of football teams consisting of 11 Autonomous IA. Each player is implemented as an independent program that connects to the server via a UDP socket. The server provides a virtual field on which it simulates the actions of players in accordance with the commands coming from them. In each step of the simulation, the player receives sensory information from the server and sends back commands about his own actions. The agent has three sensors: visual, auditory and body sensor. The agent receives the main information from the visual sensor, which it can control by setting the width and direction of the view. At any given time, the agent sees only a part of the field. The frequency of receiving visual information from the server depends on the agent’s chosen sensor mode. Figure 1 shows a general view of the field with flags placed on it (see Fig. 1). Flags are static objects with a priori known coordinates and, as a result, can be used as navigation bindings along with lines. The visual sensor provides information about all objects in the field of view: the ball (b), players (p), flags (f), lines (l) and goals (g). Flag specifiers determine their position on the field. For example, (f c) – flag in the center of the field; (f p l b) - flag marking the bottom corner (b – bottom) of the penalty area (p – penalty area) of the left half of the field (l – left). An example of a frame of visual information coming from the server is shown below: (see 0 ((f c) 32.4 0 0 0) ((f r t) 45.3 -4) ((f c t) 53.3 40) ((f p l t) 39.7 35) ((f p l c) 36.4 23) ((f t 0) 62.3 -8) ((f t r 10) 59 5) ((f t r 20) 64.7 9) ((f t r 30) 63.3 17) ((f t r 40) 74 19) ((f t r 50) 82.6 28) ((f t l 10) 65.3 -17) ((f t l 20) 67.7 -26) ((f t l 30) 65 -32) ((f t l 40) 74.5 -44) ((f r t 20) 77.6 42) ((f r t 30) 85.6 34) ((b) 24.3 0 0 0) ((p ”TeamName” 10) 43.1 32) ((l t) 63.4 66)) The agent receives visual information about each observed object in the polar coordinate system, the center of which is itself (i.e. azimuth and distance to the object). Using this relative information and a priori knowledge of the coordinates of static objects, he can calculate his own absolute coordinates and then the absolute coordinates of other players. At different points of time (simulation cycles) in the field of view of the agent, depending on its position and direction Agent Navigation in Virtual Soccer: Comparative Analysis of Algorithms 3 Fig. 1. General view of the field with flags placed on it. of view are different navigation bindings (flags and lines). At the same time, the number of such bindings and the distance to them vary widely. A significant factor in solving the navigation problem is the inaccuracy (noise) of the sensory information received from the server. In particular, the noise imposed on the distance to the object is calculated by the server using the following formula: QDistance = Quantize(exp(Quantize(ln(Distance), StepV alue)), 0.1) (1) where QDistance is the distance perceived by the agent to the observed ob- ject; distance is the true distance to the object; quantizeStep is the quantization step.Thus, for an object located at a distance of 1 m, the error in determining the distance can be 10 cm, and at a distance of 10 m-up to 1 m. The problem of determining the absolute coordinates of the players (themselves and others) on the observed information can be solved by different methods and algorithms, depending on the time spent and the accuracy of the solution. In [2, 8-10], an approach to the construction of IA was developed, according to which the agent in problem situations dynamically determines the available stock of time and adapts the process of thinking about the solution to it. Within the frame-work of this approach, algorithms for solving particular problems are constructed as anytime-alghoritms(AA), in which the quality of the results (in particular, accuracy) depends on the time allocated to this algorithm. In the framework of this approach, the solution of the navigation problem is considered from the standpoint of the AA. Comparative experimental analysis of various 4 M. Panteleyev, A. Salimov methods of solving the navigation problem is necessary to construct the AA pro- files that fix the dependence of the accuracy of the result on the time allocated to the algorithm. 2 Navigation methods and algorithms Based on the analysis of the literature [6, 7] the following methods of solving the navigation problem in the VS environment were identified: 1. on the nearest flag and the long line 2. by the two nearest flags 3. based on Kalman filter 4. based on Kalman filter 2.1 Navigation methods based on trigonometric models Navigation on the nearest flag and back lines. In this case, the nearest flag and the farthest line are determined first among all visible objects. The player’s direction to the line is used to find the angle of rotation of the agent’s head. Let lb be the bisector of the player’s viewing angle passing through his absolute coordinates. If the line l is in the player’s field of vision, the visual message he receives will contain the distance d to the intersection point lb with l and the angle α between lb and l (see Fig. 2). In this case, the angle α will be equal to the rotation angle lb until it coincides with l, which has a positive value when rotating clockwise and a negative value otherwise. In this case, the angle α will be equal to the angle of rotation lb until it coincides with l, which has a positive value when rotating clockwise and a negative value otherwise. To get the angle of rotation of the player’s head, calculate the angle β between lb and the lp line perpendicular to l. the angle β is calculated using the following formula: β = −sign(α) · (90 − |α|) (2) After calculating the angle θ, you can proceed to processing information about the flag. Sensory information about the f flag includes the direction fϕ is pointing at it relative to the player’s head rotation angle and the distance fr to it. Since the agent knows the absolute coordinates (fx , fy ) of all flags a priori, it can calculate its absolute coordinates (px , py ) based on the relative sensory information. To do this, you must first perform a rotation by the angle θ of the player’s head rotation in the polar coordinate system. The absolute coordinates of the player (px , py ) can be obtained by converting polar coordinates to Cartesian coordinates: (px , py ) = (fx , fy ) − π · (fr , fϕ + θ) (3) Agent Navigation in Virtual Soccer: Comparative Analysis of Algorithms 5 a) b) Fig. 2. Navigation on the nearest flag and back lines Navigation on the two nearest flags and the farthest line. In this algorithm, the two closest flags among all visible flags are first determined. Knowing the ab- solute coordinates of the flag and the distance to it sets the circle of possible positions of the agent with the center at the location of the flag and the radius determined by the distance to it. Similarly, defines the range of possible posi- tions of the agent and the second flag. The position of the agent is obviously determined by the intersection of these circles (see Fig. 2). To determine a point unambiguously, you must calculate the distance d between the flags f and g using their absolute coordinates: q d = (gx − fx )2 + (gy − fy )2 (4) Distance d, as seen in Fig. 3, consists of segments [f; p’] and [p’; g]. The figure shows: a-the distance from the flag f to the point p’; b-the distance from the point p’ to the flag g; h-the distance from the point p to the point p’. For triangles gpp’ and fpp’, you can write: f 2r = a2 + h2 gr2 = b2 + h2  (5) Given the ratio b = (d – a), you can calculate the value of a: fr2 − gr2 + d2 a= (6) 2d Then the absolute coordinates of the point p’ will be defined as follows: (p0x , p0y ) = (fx + a · cos(α), fy + a · sin(α)) (7) The values cos(α) and sin(α) are determined from the relations: ∆y ∆x sin(α) = , cos(α) = (8) d d Based on this, the absolute coordinates of player p will be equal: (px , py ) = (p0x − h · Sign · sin(α), p0y + h · Sign · cos(α)) (9) The true location of the player can be determined using the Sign sign: if the difference is positive (gϕ – fϕ ), Sign = +1, otherwise Sign = -1. 6 M. Panteleyev, A. Salimov 2.2 Navigation methods based on the filters When determining the absolute coordinates of the agent on the football field, trigonometric methods use visual information obtained only in the current mea- sure. At the same time, information about a certain object obtained in different sensory measures can be considered as successive observations of a dynamic pro- cess. In approaches that use filtering ideas, agent states (coordinates) are considered as a managed Markov process with hidden States xt and a time step t. Let’s denote x0 – the initial state of the player, P (x0 ) - the initial distribution at time t = 0. Then the player dynamics implemented by the server can be considered as a stochastic transition model P (xt+1 |xt , at ), in which the agent changes its state xt to the state xt+1 by its actions at performed at time t. We will assume that the yt sensor data sent by the server in each clock cycle is con- ditionally independent of the xt . Then the navigation problem can be reduced to an estimate of a posteriori probability density P (xt |yt ) in the state space X, describing the current state of the agent at time t. by the Bayes rule, you can write: P (xt+1 |yt+1 ) ∝ P (xt+1 |yt+1 )P (xt+1 ) (10) where the a priori probability density function P (xt+1 , yt+1 ) corresponds to a posteriori function from the last time step. For P (xt+1 ), you can write: Z P (xt+1 ) = P (xt+1 |xt )P (xt |yt )dxt (11) This formula uses the Markov assumption that the current values are inde- pendent of previous time steps. Equations allow us to construct an iterative Bayesian filtering scheme, in which the integral must be calculated according to the expression in order to analyt- ically determine a posteriori probability. The result of the calculation must be multiplied by the value of the probability density P (yt+1 |xt+1 ), and then nor- malize the probability density P (xt+1 |yt+1 ). A posteriori probability can be cal- culated analytically if the observation and transition models are linear Gaussian. Since the Robocup Soccer simulation environment does not meet this require- ment, approximations must be used. An effective method for calculating a posteriori distribution in Bayesian filtering is the particle filter. It is based on a discrete approximation of the continuous function of the posterior density using a set of Xti particles with corresponding weights πti , where i = 1, ..., N. the Empirical a posteriori estimate has the form: N X P (xt |yt ) = πti δ(xt − xit ) (12) i=1 Agent Navigation in Virtual Soccer: Comparative Analysis of Algorithms 7 Using the formula above, the integral for calculating the expression can be replaced with summation: N X P (xt+1 ) = πti P (xt+1 |xit ) (13) i=1 After replacing all integrals with sums and all continuous density functions with discrete expressions, the normalization of the fixed a posteriori function is reduced to the normalization of discrete values per unit of the sum. N X P (xt+1 |yt+1 ) ∝ P (xt+1 |yt+1 ) πti P (xt+1 |xit ) (14) i=1 Navigation based on the Kalman filter. The Kalman filter allows you to get an estimate of the state vector of an object (in this case, the player’s coordinates) based on a series of noisy measurements. Solving the navigation problem in the VS using the Kalman filter enlarged includes the following steps: 1. Analysis and analysis of the received visual information in order to obtain a list of flags visible to the player and their relative coordinates. 2. Cyclic processing of various pairs of flags. In each cycle, two visible flags are selected and the absolute coordinates of the agent are calculated by these flags. 3. Calculation of the variance of the sensor error. (The quality of the variance estimation determines the quality of the Kalman filter). 2 (rmax − rmin )2 σi+1 = (15) 2 4. Updating the value of the Kalman gain taking into account the obtained dispersion. The coefficient value should provide the maximum proximity of the calculated op-timal values of the absolute coordinates to their true values. σ̂i2 K= (16) 2 σ̂i2 + σ̂i+1 5. Correction using the Kalman coefficient of the estimated value of the absolute co-ordinates of the agent in this iteration. x̂i+1 = x̂i + K · (yi − x̂i ) (17) Particle filter navigation. A particle filter is a method for determining the ab- solute coordinates of an agent, in accordance with which many hypotheses (par- ticles) about their current values are created to estimate coordinates. The algorithm for determining absolute coordinates based on a particle filter includes five steps: initialization, forecast, correction (calculation of weighting coefficients and resampling), and state estimation. Particle filter initialization is 8 M. Panteleyev, A. Salimov performed at the mo-ment of receiving the first sensor frame and is reduced to randomly generating parti-cles around the obtained point. As a result, in the vicinity of the point, N particles with initially equal weights are generated. The position of each particle is determined on the basis of information about the trajectory and distance received from the visual sensor. At the forecasting stage, the range of possible values of the distance to the agent is taken into account. If the distance between the particle and the agent is out-side this range of values, the particle is removed from the set. Thus, after the forecast-ing stage, taking into account information on the range of values from the initial set of N parti- cles, K particles remain. The correction procedure is performed each time new sensory information is received and includes two steps: determining value ranges and resampling. Before calculating the range of values, some particles can be removed using Kalman filtering. Each time new information is received, the upper and lower bounds of the distances between the particles and the agent are determined. Particles that are out of range based on the prediction results are removed from the total set of particles. This allows you to discard false hypotheses about the possible position of the object and, thus, reduce computational costs and improve the accuracy of the re- sult. After a few steps of the correction procedure, most particles that correspond to erroneous hypotheses may have weights close to zero. Such particles hardly contribute to the final estimation of the state vector, but they spend computa- tional resources. The resampling procedure allows you to re-allocate computing resources by discarding low-weight particles and duplicating high-weight parti- cles. At the last stage of the state assessment, the absolute coordinates of the agent are calculated as a weighted sum of the states of all particles. 3 Approach and results of experimental evaluation of navigation algorithms For experimental research and comparative analysis of the effectiveness of various navigation algorithms, a tool program in the Java language has been developed that allows: 1. randomly position the agent on the field and set the direction and mode of operation of its visual sensor; 2. solve the navigation problem by various methods and evaluate the accuracy of the solution and the time spent Since the number of navigational anchors (flags) falling into the agent’s field of vision depends significantly on the viewing angle, the experiments were carried out sep-arately for different viewing angles: narrow, normal, and wide. The re- sults of the study with a normal viewing angle, when the agent sees few flags, are presented in Fig. 4. Agent Navigation in Virtual Soccer: Comparative Analysis of Algorithms 9 Fig. 3. Error of the algorithms The errors of the algorithms were calculated at different 50 absolute coor- dinates. The graphs in the figure correspond to the following algorithms for calculating the abso-lute coordinates of the agent: A1 - by the nearest flag and the far line; A2 - by the two nearest flags; A3-using the Kalman filter; A4-using the particle filter. As can be seen from the above dependencies, the greatest error is given by the algorithm for determining the coordinates of the two nearest flags. The most accurate method is the particle filter method, since it uses information about all visible flags, taking into account the sequence of observations. The results of the experimental estimation of the algorithm implementation time are shown in Fig. 5. The experiments were carried out on a PC with the following charac-teristics: PC 2 cores, 4 logic processors, frequency 2.2 GHz As the experiment showed, the algorithm using the particle filter works 7-15 times slower than other algorithms, due to the large number of processing oper- ations. The averaged values of the error in determining the absolute coordinates of the agent and the time spent for different algorithms at a narrow viewing angle are presented in summary table 1. The analysis of the obtained results shows that in the aggregate of two char- acteristics - accuracy and time – the algorithm of determining the absolute co- ordinates of the agent by the nearest flag and the far line is preferable. This time-consuming algorithm is slightly inferior to the fastest algorithm for deter- mining the coordinates of the two nearest flags and, at the same time, gives an 10 M. Panteleyev, A. Salimov Fig. 4. Algorithm’s time complexity Table 1. Comparison of algorithms Algorithm for determining the absolute coordinates of the agent Average error (m) Time (ms) On the nearest flag and the long line 0,2482 0,0274 By the two nearest flags 1,0154 0,0222 Based on Kalman filter 0,2901 0,1826 Based on particle filter 0,0974 2,0154 error comparable to the algorithm based on the Kalman filter. 4 Summary According to the criterion of accuracy of the solution of the navigation problem in the VS, the algorithm based on the particle filter is the best. However, it requires the maximum time (4 ms on average). Trigonometric algorithms for de- termining absolute coordinates are fast, but have a significantly lower accuracy, significantly dependent on the number of visible flags and the selected quality of the visual sensor. In addi-tion, these methods can give abnormally high errors at close azimuths of the direction to the nearest flags. The presence of various algorithms for solving the navigation task, wherein the accu-racy of the result, allows us to consider them from the standpoint of AA and adapt the delibera- tion process agent decisions based on dynamic (situational) changing time limits. Agent Navigation in Virtual Soccer: Comparative Analysis of Algorithms 11 Thus, the directions of further research are: - creation of the refined profiles of AA of the decision of a navigational problem and their use in architecture of RIA for the environment of VS; - use of the calculated absolute coordinates of the players to determine the tactical arrangements of the teams during the game. References 1. Russell S., Norvig p. Artificial intelligence: a modern approach, 2nd ed. Moscow: Izdat. Williams House, 2006. - 1408 p 2. Panteleyev M. G., Puzankov D. V. Intelligent agents and multi-agent systems: a monograph.:Publishing house SPbGETU ”LETI”, 2015. - 215 p. 3. Official website of the tournament: [Electronic resource] http://www.robocup.org Last accessed 10 Dec 2019 4. Robocup Soccer Server: https://github.com/rcsoccersim/rcssserver/ Last accessed 10 Dec 2019 5. Thrun S., Wolfram B., Fox D. probabilistic robotics (intelligent robotics and Au- tonomous agents)/ / The MIT Press, 2005. – 672 P. 6. Panteleyev M. G. the Concept of constructing intelligent real-time agents based on the model of advanced iterative planning / / proceedings of the 13th NAC. Conf. AI with international participation CII-2012. T 3. - Belgorod: Publishing house of BSTU. - 2012. - 25-33. 7. Panteleyev M. G. Formal model of advanced iterative planning of actions of intelli- gent real-time agents. proceedings of the 14th national Academy of Sciences. Conf. at the AI con-ference. on artificial intelligence with international participation CII- 2014. T 1. - Kazan: pub-lishing house RIC ”school”. - 2014. 323-333. 8. Panteleyev M. G. extended iterative action planning for intelligent real-time agents / / Proceed-ings Computer Science, 2019, Vol. 150, PP.