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 coordinates of objects based on sensory data on ags and lines are considered: trigonometric methods and methods based on the use of the Kalman lter and particle lter. A software tool developed for experimental research and allowing arbitrary variation of the conditions for solving the navigation problem is brie y described. Experimental results of the comparative 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 implementation of the assessment of the tactical situation in virtual soccer are determined.
The creation of intelligent agents (IA) and based on them multi-agent systems
(MAS) is currently the main direction of the development of arti cial intelligence
[
The features of the navigation task in the soccer environment Virtual soccer environment (VS) RoboCup Soccer Server allows real-time simulation 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 eld 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 eld. 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 eld with ags 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 eld of view: the ball (b), players (p), ags (f), lines (l) and goals (g). Flag speci ers determine their position on the eld. For example, (f c) { ag in the center of the eld; (f p l b) - ag marking the bottom corner (b { bottom) of the penalty area (p { penalty area) of the left half of the eld (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 di erent points of time (simulation
cycles) in the eld of view of the agent, depending on its position and direction
of view are di erent navigation bindings ( ags and lines). At the same time, the
number of such bindings and the distance to them vary widely. A signi cant
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
object; 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 di erent methods and
algorithms, depending on the time spent and the accuracy of the solution.
In [
Based on the analysis of the literature [
Navigation methods based on trigonometric models Navigation on the nearest ag and back lines. In this case, the nearest ag and the farthest line are determined rst among all visible objects. The player's direction to the line is used to nd 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 eld 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 j j) (2)
After calculating the angle , you can proceed to processing information about the ag. Sensory information about the f ag 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 ags a priori, it can calculate its absolute coordinates (px; py) based on the relative sensory information. To do this, you must rst 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) Navigation on the two nearest ags and the farthest line. In this algorithm, the two closest ags among all visible ags are rst determined. Knowing the absolute coordinates of the ag and the distance to it sets the circle of possible positions of the agent with the center at the location of the ag and the radius determined by the distance to it. Similarly, de nes the range of possible positions of the agent and the second ag. 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 ags f and g using their absolute coordinates: d = q (gx fx)2 + (gy fy)2
Distance d, as seen in Fig. 3, consists of segments [f; p'] and [p'; g]. The gure shows: a-the distance from the ag f to the point p'; b-the distance from the point p' to the ag g; h-the distance from the point p to the point p'. For triangles gpp' and fpp', you can write:
Given the ratio b = (d { a), you can calculate the value of a: f r2 = a2 + h2gr2 = b2 + h2 a = f 2 r gr2 + d2 2d Then the absolute coordinates of the point p' will be de ned as follows: (p0x; p0y) = (fx + a cos( ); fy + a sin( )) The values cos( ) and sin( ) are determined from the relations: sin( ) =
; cos( ) = y d x d Based on this, the absolute coordinates of player p will be equal: (px; py) = (p0x
h Sign sin( ); p0y + h Sign cos( ))
The true location of the player can be determined using the Sign sign: if the di erence is positive (g' { f'), Sign = +1, otherwise Sign = -1. (4) (5) (6) (7) (8) (9)
Navigation methods based on the lters When determining the absolute coordinates of the agent on the football eld, trigonometric methods use visual information obtained only in the current measure. At the same time, information about a certain object obtained in di erent sensory measures can be considered as successive observations of a dynamic process.
In approaches that use ltering 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+1jxt; 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 conditionally independent of the xt. Then the navigation problem can be reduced to an estimate of a posteriori probability density P (xtjyt) in the state space X, describing the current state of the agent at time t. by the Bayes rule, you can write:
N P (xtjyt) = X ti (xt
xit) 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+1jxt)P (xtjyt)dxt
This formula uses the Markov assumption that the current values are independent of previous time steps.
Equations allow us to construct an iterative Bayesian ltering scheme, in which the integral must be calculated according to the expression in order to analytically determine a posteriori probability. The result of the calculation must be multiplied by the value of the probability density P (yt+1jxt+1), and then normalize the probability density P (xt+1jyt+1). A posteriori probability can be calculated analytically if the observation and transition models are linear Gaussian. Since the Robocup Soccer simulation environment does not meet this requirement, approximations must be used.
An e ective method for calculating a posteriori distribution in Bayesian ltering is the particle lter. 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: (10) (11) (12)
Using the formula above, the integral for calculating the expression can be replaced with summation:
N P (xt+1) = X tiP (xt+1jxit)
i=1
After replacing all integrals with sums and all continuous density functions with discrete expressions, the normalization of the xed a posteriori function is reduced to the normalization of discrete values per unit of the sum.
N P (xt+1jyt+1) / P (xt+1jyt+1) X i=1 tiP (xt+1jxt) i Navigation based on the Kalman lter. The Kalman lter 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 lter enlarged includes the following steps: 1. Analysis and analysis of the received visual information in order to obtain a list of ags visible to the player and their relative coordinates. 2. Cyclic processing of various pairs of ags. In each cycle, two visible ags are selected and the absolute coordinates of the agent are calculated by these ags. 3. Calculation of the variance of the sensor error. (The quality of the variance estimation determines the quality of the Kalman lter). 4. Updating the value of the Kalman gain taking into account the obtained dispersion. The coe cient value should provide the maximum proximity of the calculated op-timal values of the absolute coordinates to their true values. (13) (14) (15) (16) (17) 2 i+1 = (rmax
rmin)2 2 K =
^i2 ^i2 + ^i2+1 x^i+1 = x^i + K (yi x^i) 5. Correction using the Kalman coe cient of the estimated value of the absolute co-ordinates of the agent in this iteration.
Particle lter navigation. A particle lter is a method for determining the absolute coordinates of an agent, in accordance with which many hypotheses (particles) about their current values are created to estimate coordinates. The algorithm for determining absolute coordinates based on a particle lter includes ve steps: initialization, forecast, correction (calculation of weighting coe cients and resampling), and state estimation. Particle lter initialization is performed at the mo-ment of receiving the rst 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 particles, 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 ltering. 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 result. 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 nal estimation of the state vector, but they spend computational resources. The resampling procedure allows you to re-allocate computing resources by discarding low-weight particles and duplicating high-weight particles.
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 e ectiveness of various navigation algorithms, a tool program in the Java language has been developed that allows: 1. randomly position the agent on the eld 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 ( ags) falling into the agent's eld of vision depends signi cantly on the viewing angle, the experiments were carried out sep-arately for di erent viewing angles: narrow, normal, and wide. The results of the study with a normal viewing angle, when the agent sees few ags, are presented in Fig. 4.
The errors of the algorithms were calculated at di erent 50 absolute coordinates. The graphs in the gure correspond to the following algorithms for calculating the abso-lute coordinates of the agent: A1 - by the nearest ag and the far line; A2 - by the two nearest ags; A3-using the Kalman lter; A4-using the particle lter.
As can be seen from the above dependencies, the greatest error is given by the algorithm for determining the coordinates of the two nearest ags. The most accurate method is the particle lter method, since it uses information about all visible ags, 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 lter works 7-15 times slower than other algorithms, due to the large number of processing operations. The averaged values of the error in determining the absolute coordinates of the agent and the time spent for di erent 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 characteristics - accuracy and time { the algorithm of determining the absolute coordinates of the agent by the nearest ag and the far line is preferable. This time-consuming algorithm is slightly inferior to the fastest algorithm for determining the coordinates of the two nearest ags and, at the same time, gives an error comparable to the algorithm based on the Kalman lter. 4
According to the criterion of accuracy of the solution of the navigation problem in the VS, the algorithm based on the particle lter is the best. However, it requires the maximum time (4 ms on average). Trigonometric algorithms for determining absolute coordinates are fast, but have a signi cantly lower accuracy, signi cantly dependent on the number of visible ags 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 ags. 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 deliberation process agent decisions based on dynamic (situational) changing time limits. Thus, the directions of further research are: - creation of the re ned pro les 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.