UTUtd2005-3D Team Description Paper

HesamAddin Torabi Dashti, Nima Aghaeepour, Sahar Asadi, Meysam Bastani, Zahra Delafkar, Fatemeh Miri Disfani, Serveh Mam Ghaderi, Shahin Kamali, Sepideh Pashami, Alireza Fotuhi Siahpirani

Math and Computer Science Department, Faculty of Science, University of Tehran, Iran

http://www.fos.ut.ac.ir/robocup

Abstract UTUtd-3D 2005 is based on experience of UTUtd-3D 2004 that won the third place in the RoboCup 2004 competitions [1]. Last year the team worked on basic skills especially on the motion acceleration control of players and prediction of ball's position. This year we have focused on decision making and high-level skills (e.g. pass, shoot and dribble). Strategy of team has improved by developing a new positioning method and implementing a new structure for ball handling based on learning with Artificial Neural Networks and, . . .

Introduction

UTUtd is the RoboCup team of faculty of science, University of Tehran. This team has started its activity in 2D since 2000 year, and in the year 2004 when soccer simulation 3D competition became a part of RoboCup for the first time, this team started its work on 3D.

Soccer simulation is a Multi-Agent System. In Multi-Agent Systems several independent agents are defined in a world model and act autonomously based on the goal of team. So RoboCup Soccer Simulation is a very suitable test bed for implementation of intelligent Multi-Agent Systems.

RoboCup Soccer Simulation Server 3D (rcssserver3D) is a Multi-Agent simulation system for physical agent in three dimensional environment and resembles to the real world much better than 2D. This server is based on SPADES [2], which is a middleware system and has unique properties; it is an event-based system that can be distributed among several machines. Rcssserver3D is relatively new and very different from 2D and considers real physical rules like friction and gravity. So calculation of some facts like prediction of position and velocity of ball and agent or interception are much more complex.

Basic skills and decision were the most important issues that were studied last year at the first 3D soccer simulation competition, so the activity of the team in this year is focused on high-level skills (like pass, shoot and dribble) and decision making and strategy planning (like Ball Handling and Positioning).

One of the best methods for implementation of decision making problem, strategy planning and high-level skills is the learning algorithm, which our team has developed. Furthermore neural network is used for implementing ball handling and high-level skills.

We introduced a new method for positioning (DPVC) that uses Voronoi Diagram [3] for distributing agents in the field and it makes DPVC so dynamic and flexible in comparison with other methods that was used last year and had some limitation.

In following, pass, shoot and dribble as high-level skills, decision making methods for ball handling and positioning and goalie decision making using Artificial Neural Networks has been described in detail.

Skills

Last year after improving credibility of the basic skills (like intercept and kick), we started to develop new high-level skills. In following, you can find the description of dribble, pass, and shoot.

Dribble

Dribbling is one of the most important skills. Generally, definition of dribble is ability to control the ball and protect it for making better situations. To improve dribble skill, we use an Artificial Neural Network to recognize direction and power of dribble. For this purpose, our algorithm counts number of opponents, finds out the distance from the ball and also calculates the direction of player to decide the direction and power to kick the ball. This can cause the team to be able to keep the ball for a longer time.

Pass

Passing is accomplished in two steps. In the first step, the player determines which playmate among the players is in the best position to receive a pass. In the next step, the player figures out how to pass to the selected player. First step of decision making should be based on the position of opponents near each teammate, density and opponent position near each teammate, passing angle, and also player role. Feeding these parameters as input to a neural network, the best player to get the ball will be in output. In the next step, we must determine the direction and power of the ball to kick. We used another Artificial Neural Network for this purpose.

Shoot

According to this fact that in soccer games all attempts and strategies are to advance the ball into the opponent team's goal zone, shooting into the goal is the most important skill for each team. Obviously it should be very precise and the velocity of ball should be as much as possible, so that the opponent has no time to block the ball from reaching into the goal.

Shooting happens in three steps. First we have to determine whether or not it is an appropriate position for shooting. In order to reach this conclusion, we should pay attention to the opponents' locations, velocity and their distance from the ball. Second, if shooting is possible, we'll search for a point in the goal that has the highest probability of scoring; this is a function of opponents' defender locations and our attackers' positions. If the probability of scoring a goal at a point is higher than a desired threshold, shooting will be chosen among the skills (pass, shoot and dribble). The last step is to select between grounded shoot and lofted shoot, because rcssserver3D gives us an opportunity to use lofted shoot. Vision error is a major problem that reduces the precision of shooting and appears more in lofted shoots; a neural network is used to solve this problem.

Decision

If any agent except goalie owns the ball, he must decide to do one of the highlevel skills. This selection is called ball handling. In the case he does not own the ball; he must position himself on the field according to the team's strategy. But the goalie has different duties from the other agents. For example, Goalie's role is to protect the goal from entering the shot ball almost without any cooperation with other teammates so the positioning of goalie is different from other players. In the following, these tasks have been explained in detail.

Handle Ball

Decision making is one of the most important challenges of Robocop Soccer Simulation. So far there has been several decision making methods proposed. This year, we developed a Regional Decision Maker using Artificial Neural Networks as a new method for decision making. This method divides the field into partitions. The idea of field's partitioning comes from UvA Trilearn team [4]. For each partition a partial purpose has been defined, so by achieving these partial goals general purpose of team can be achieved. We separate players into active agents and passive agents [5]. Active agent is the agent who possesses the ball or can intercept the ball. Passive agents distribute over the field according to team's strategy (positioning).

In this method, we have a supervised learning to train agents. Learning process is done by implementing Local Supervisor and Global Supervisor. These supervisors are running during training time, in a way that Local supervisor scores actions when they are issued. After a sequence of actions is performed the Global supervisor scores all actions of that sequence, with regard to these rewards. Using this method will improve agent's decision making.

Positioning

As mentioned before coordination between playersis an important issue in Soccer Simulation. So, passive players must determine the best position on the field with respect to team's strategy.

This position, which is called target position, can be calculated by getting the game situation, the player role and ball position. Therefore positioning can be defined as an arrangement of players on the field in order to implement the strategy. The positioning, we implemented for RoboCup2004 competitions, was based on the home position of each player. In this strategy, players tend to stay around their home position that causes players to stay sparse over the field and to fill strategic areas. These home positions are fixed within a formation.

Since RoboCup Soccer Simulation is a dynamic environment, it's important to have a dynamic positioning strategy. Dynamic positioning means that players' roles can be changed during the game and there is no fixed home position that players tend to stay at. Here we present a dynamic method for positioning called Dynamic Positioning based on Voronoi Cells (DPVC) method.

In this method the player role will be specified according to his position and game situation, although the player number doesn't have any effect.

To control agents' movements on the field, we use attraction vectors for each player. These vectors indicate the agent's tendency toward different objects of the field like ball, opponent goal and opponent players. Attraction points and rates change depending on the situation. Vectors are calculated from the base point of each player to the target position. The home position for each agent is calculated using a Voronoi Diagram. A Voronoi Diagram divides the field into n polygons, which are called cells. Each cell contains exactly one agent that is the nearest agent to every point in the cell.

We've designed an algorithm to compute Voronoi Cells. Each player computes only the cell in which his home position is placed. A center is defined for each cell by using the definition of center of mass for polygons. This center can be considered as a reference point for each agent. So the attraction vector will be added to this point and the player will move toward the target position.

To improve agents' cooperation in this method, we should find appropriate attraction functions. We define a function whose output is a real number between 0 and 1, which indicates the rate of offense or defense. With this number, we adjust attractions so the players will act accordingly during the game.

We also define specific attractions for defenders. In defensive situations, defenders should block the opponents. Therefore, blocking points are calculated for defenders to be directed toward. The remaining players then narrow the angle of the opponent in front of the goal. The blocking and angle narrowing mechanisms are as follows:

Blocking. A defender blocks an opponent to prevent any receptions of passes and tries to intercept the ball if possible. Blocking within a reasonable distance from an opponent is necessary. An eligible opponent for blocking is one that does not have the ball, and is not currently being blocked by any teammate. Then the defender positions themselves between the opponent and the goal depending on the positions of the ball, opponent, and goal. Another situation occurs when the defender is behind the opponent. When this happens, the defender blocks the approximated position of the opponent at ∆t seconds into the future. In these calculations, a distance should be kept between the defender and the opponent that is being blocked. This distance is dependent on the distance between the ball and the opponent and distance between the opponent and the goal. Thus, the purpose of blocking which is to cover the opponents that do not have the ball is achieved.

Angle Narrowing. The best strategy to defend against an opponent with the ball is to narrow their view angle toward the goal. It means that one or more defenders narrow the shoot angle of the opponent with the ball. Having some parameters such as the velocity of the defenders and the shortest time for the opponent to reach to an appropriate position to shoot toward the goal, the best direction to intercept the ball by defenders is calculated. As a result, defenders intercept the ball in the best way of angle narrowing to get the opportunity of shooting for the opponent.

Goalie

As mentioned before, the basic role of the goalie is to avoid the ball from getting into the goal. So the goalie must work according to a different algorithm from others. Steps of algorithm for the goalie are as follows:

• He should intercept the ball, if the ball is shot [1].
• He should intercept the ball, if he is the first one that receives the ball.
• If there isn't any defender to block opponents, he should go out of the goal and intercepts the ball.
• If none of the above situations happens, he should do positioning.

It is clear that in the first and second situations, interception is the best action. In the third one, he intercepts the ball and goes toward the ball, in order to restrict the free space in front of the shooter. At the last situation, the purpose of the goalie positioning is to get the best place to position against the probable shoot whenever goalie isn't in emergency conditions.

Goalie Positioning. The goalie should position in the best location against the probable shoot, whenever the ball isn't shot toward the goal, and it doesn't need to be far from the goal. One intuitive selection of this position can be on the bisector of the angle that ball makes with two flags of the goal. Considering this fact that in rcssserver3D, each agent can shoot just towards the line between player and ball, in order to improve positioning, the goalie moves x meters on the positioning line (between the goal and ball, parallel to the goal line) from the intersection point of the bisector of the angle and positioning line (as shown in Fig. 1).

Future Works

The following is a brief list of our activities for development in the year 2005:

• Optimization of structure and parameters of Artificial Neural Networks used in Regional Decision Maker with Genetic Algorithm, also analyzing the effect of input parameter on the network
• Implementation of Reinforcement Learning (RL) algorithm and Electric Charge Concept for attraction vectors in Positioning
• Maintaining Blocking and creating new algorithms
• Developing new algorithms for basic skills using learning techniques

Acknowledgements

UTUtd team wishes to acknowledge in part support of TAM-Irankhodro Co., a sister company of Irankhodro Industrial Group working in the field of advanced manufacturing engineering in automotive industry, during the development of this team.

References

1. Mahmoudian, P., Asadi, S., Bastani, M., Fotuhi, A., Dashti, H.T., UTUtd2004-3D Team Description Paper (2004), http://www.fos.ut.ac.ir/robocup/download.htm
2. Riley, P., Riley, G.: SPADES A Distributed Agent Simulation Environment with Software-in-the-Loop Execution. In: Winter Simulation Conference Proceedings (2003) 817–825
3. Sutherland, I.E., Hodgman, G.W., Reentrant polygon clipping, Communications of the ACM, Vol.17 No.1 (1974) 32–42
4. de Boer, R., Kok, J.: The Incremental Development of a Synthetic Multi-Agent System: The UvA Trilearn 2001 Robotic Soccer Simulation Team. M.S. Thesis. Faculty of Science, University of Amsterdam (2002) Section 9.5.3
5. Veloso, M., Bowling, M., Achim, S., Han, K., Stone, P., CMUnited-98: RoboCup-98 Small-Robot World Champion Team. AI Magazine, Vol.21 No.1 (2000) 29–36