View Original PDF

RoboSina 2005 Team Description

H. Bashiri, N. Kaviani, M. Rafaie, H. Zarrabi-Zadeh

Department of Computer Engineering, Bu-Ali Sina University, Hamedan, Iran

http://basu.ac.ir/~robosina

Abstract RoboSina 2005 soccer simulation team is the result of a research project in Bu-Ali Sina University. Obtained Honors for RoboSina Soccer Simulation Team can be summarized as 5th place of RoboCup World Cup 2004, Championship of American Open RoboCup Competitions 2004, Championship of Iranian Open RoboCup Competitions 2004 and, 10th place of RoboCup World Cup 2003. Many new improvements have been made in RoboSina 2005 in comparison to the preceding version, RoboSina 2004. This paper describes the main features of RoboSina 2005 as well as the improvements that have been made on this team.

Introduction

RoboSina 2005 is a soccer simulation team that participates for the third time in the RoboCup world cup. In its first participation, RoboSina ranked 10th among 48 teams participating the simulation league of RoboCup 2003 world cup in Italy and its second time participation resulted in a jerk to the 5th place in world cup competitions. RoboSina is the result of a research project funded by Bu-Ali Sina University in Iran. The research group started with four undergraduate students as well as an instructor who served as the head of the research group but now it is reduced to a team of two students, an instructor, and a team advisor. From the beginning, the group members decided not to copy codes from other RoboCup teams because most of the released source codes were not well structured and in most cases, they were not so efficient and optimized. Most of lower level parts hence have been redesigned and reprogrammed by our team members.

Having studied the low-level methods used by some previous top teams such as CMUnited, UvA Trilearn, and TsinghuAeolus [2, 3, 6], we provided several essential ideas to improve the existing low-level methods and implement them in our team. Although our higher-level strategies were very simple in the first stage of developing the team, having powerful low-level skills such as dribbling and accurate localizing made RoboSina a successful team in RoboCup 2003.

In the next year of research, we made several improvements in both low-level and strategy-level skills of our team. Using neural networks to achieve a more reliable scoring policy, employing reinforcement learning to obtain an enhanced blocking strategy, and utilizing Matrix Decision method to reach a more precise way for updating visual information in the world model were some of our new improvements applied to RoboSina 2004.

As Robosina served as a test bed for our researches and the project is going to be finished regarding graduation of team members, the main concentration in RoboSina 2005 has been applied to improvement of previously designed and implemented algorithms and to enhance their reliability, proficiency and order of execution. Making the algorithms work faster and more accurate is another approach in RoboSina 2005.

Improved Localization Algorithm

One of the most important tasks for a mobile agent is to find its location in the field using visual information. Because of existence of noise in our perception information, an agent must have ability to find its location in such an environment with the least possible error. We have made a substantial effort on providing a good algorithm for localizing a player agent in the soccer simulation environment, which leads to a fast O(n lg n) time algorithm, where n is the number of flags visible in the field. We have used some computational geometry algorithms for intersecting convex polygons and adopt them to reach a very fast and accurate localization algorithm.

Our algorithm constructs a convex polygon corresponding to visual information obtained from each flag in the field. The algorithm then employs a plane sweep method in which a sweep line is moved downward over the plane and maintains the convex polygons intersecting it. Using a divide and conquer method, we developed an O(n lg n) time algorithm to compute the intersection of n convex polygons, which is a good approximation for the exact position of the player. The error of our algorithm is considerably smaller than what have already reported by many other teams. Details of our method can be found in [8].

Enhanced World Model

The world model of each agent is a probabilistic representation of the world state based on past perception. The world model is updated when the agent receives new information about the objects in the field. Unseen objects are also updated based on their last observed velocity.

In our new improvement, for each agent of the team we find a region in the field that has the most valuable data for updating the world model. To achieve this, the filed is divided into several regions by means of a gridding algorithm, and then, a very fast algorithm is used to find the 'best' region for an agent to look at.

Moreover, we have improved the world model to provide a better perception of other teammates and opponents presence in the field. It enables us to form a more reliable plot of important parts in the pitch and conducts our decision making automatas to a suitable state of acting, in as much as we can choose better decision even in case of missing a visual data.

Higher-Level Strategies

Our higher-level strategies were very simple in RoboSina 2003, however, we made many improvements in the strategies in RoboSina 2004 and have made improvements to make them work more accurate. Some of these improvements are addressed in the following subsections.

Scoring Policy

We developed a new scoring policy for RoboSina 2004 using neural networks [5]. The scoring policy determines whether an agent that holds the ball attempts to shoot at the goal. It also determines the best target point in the goal, along with a probability of scoring when the ball is shot at that point. We adopted the idea of [1] to develop a new scoring policy using neural networks. We have employed a two-layered back-propagate neural network that uses tgsigmoid function in its first layer and logsigmoid in the second layer. The space before the goal is divided into 16 regions. In the training phase, the agent tries to shoot at each region more than 5000 times. According to the relative distance and relative direction of the agent to the goal and the position of the opponent goalie, the agent is either successful or unsuccessful in scoring. The network is then trained by the obtained results and the scoring regions are marked as good regions for shooting. Using this method, the percentage of successful scoring attempts of our team raised to 75% of the shooting attempts. In RoboSina 2005 we have trained our scoring policy with a new network in which number of layers are increased to three and more exact data is applied to the network.

Blocking Skill

Another improvement in the high-level skills is to improve our blocking skill using reinforcement learning [4, 7]. This skill prevents an opponent to move with ball toward our goal, better to say, it enables our agents to stop a dribbler opponent. We tried to use reinforcement learning to define a state and action space and train our agents to select the best action in each state. In our first model, each state was defined by seven parameters, namely opponent's relative distance and direction, ball relative distance and direction, relative velocity of opponent and ball, and opponent's body direction. Such a detailed model resulted in a substantial growth of state matrix and a large amount of computation effort. To make it better, we reduced the state space by transferring the space to a vector space. Our new policy leads to a significant reduction of state space and also an easier method for state recognition. Tackling against an opponent ball holder is another obstruction against his moving toward our goal, which enables us to change the situation by means of forming a fully-fledged attack toward opponent goal.

Linear Defense

Having collected soccer knowledge from some expert players and coaches, we also developed a new defensive strategy for our team. In this strategy, four defenders are organized in a linear arrange such that they can block many penetration that may be used by opponent to attack our goal. This strategy is used in real soccer to prevent attackers from moving toward goal easily. This strategy also enables a team to break an attack by putting the opponent attackers in 'offside' position. The results of this strategy can be precisely viewed in RoboSina 2004 log files, especially the one against Brain Stormers in which opponent attackers were captured in the trap for many times and thus they couldn't perform all their predefined strategies in the field. In RoboSina 2005 some new communication methods are applied which enable defenders work better in a defensive situation.

Man-To-Man Marking

Another strategy that is improved to be used by our team according to the status of the game is a man-to-man marking strategy in which each agent from the opponent team having the opportunity of scoring a goal is guarded by exactly one of our team agents such that it can not move closer to the goal, or send and receive a pass. Two modes of marking are likely to be used regarding the situation of the defender. An opponent player which is sited in a terribly dangerous situation is required to be marked more severely and the defender is forced to follow the opponent attacker closely. Once the opponent loses its chance to score, it is not any more required to keep a close position to the opponent so the defender marks a larger area rather than having a severe marking strategy.

Conclusion and Future Plan

In this paper we have discussed the main features and improvements of RoboSina 2005 soccer simulation team. Above mentioned skills and improvements in RoboSina 2004 led to score 55 goals and conceive only 5 goals, facing no defeats in robocup world cup 2004. Our lower-levels are currently works reasonably and many improvements have been made on higher-level issues. Our future research will mainly focus on improving our higher-level strategies, using machine learning techniques and probably employing a coach to analyze the game and give advice on the best possible strategy.

References

  1. R. de Boer and J. Kok. The Incremental Development of a Synthetic Multi-Agent System: The UvA Trilearn 2001 Robotic Soccer Simulation Team. Master's thesis, University of Amsterdam, The Netherlands, Feb. 2002.
  2. R. de Boer, J. Kok, and F. Groen. UvA Trilearn 2001 Team Description. In Robocup-2001: Robot Soccer world cup V, Springer Verlag, Berlin, 2002.
  3. Y. Jinyi, C. Jiang, C. Yunpeng, and L. Shi, Architecture of TsinghuAeolus. In Robocup-2001: Robot Soccer world cup V, Springer Verlag, Berlin, 2002.
  4. Y. Jinyi, C. Jiang, and S. Zengqi. An application in RoboCup combining Q-learning with Adversarial Planning. In the 4th World Congress on Intelligent Control and Automation (WCICA'02), Shanghai, China, June 2002.
  5. S. Y. Kung. Digital Neural Networks. PTI Prentice Hall, Englewood Cliffs, New Jersey, 2002.
  6. P. Stone. Layered Learning in Multi-Agent Systems. PhD thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 1998.
  7. R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
  8. H. Zarrabi-Zadeh, M. Rafaie, M. Shabani, and N. Kaviani. Robot Positioning Using Visual Information. In the 2nd National Computer Conference (NCC'03), pages 54-59, Mashhad, Iran, Dec. 2003.