UnKnown2009 2D Simulation
Mostafa Rafaie, Amir Tavafi, Mehran Ranjbar, Fatemeh Tavafi, Hamidreza Afzali, Hamed Rahmati
RoboCup Lab., Department of Computer Engineering, Azad University of Lahijan, Lahijan, Iran
Abstract Unknown is the result of a research project in Islamic Azad University of Lahijan. The project started in October 2008. This paper briefly describes main features of the Unknown 2D soccer simulation team based on Robosina05 code. Many improvements and innovations have been made on it, especially in high-level strategies.
Keywords: RoboCup 2D Soccer Simulation, Unknown, Robosina, Neural Network, multi-agent systems, artificial intelligence
1 Introduction
Soccer is a very complex game, both very animated to play and exciting to watch. It is probably the most popular team sport in the world, capable of attracting thousands of wild fans in stadiums and billions through television. The soccer server simulator [1], although being 2D simplified soccer simulation, manages to keep most of this complexity, animation and excitement. Because of this, we argue that in the simulation league on RoboCup, to be successful and win, a team must be able to play like a real soccer team. Thus, UnKnown project was conceived as an effort to create intelligent players, capable of thinking like real soccer players and behave like a real soccer team. According to all incomplete modules implemented in last stages of Robosina05 project, we found it favorable to complete these remaining parts, and also add some new ideas which were come up during five past years of soccer 2D simulation, using the experience of our team leader, leader of the Robosina. This paper describes main features of our team based on Robosina05 code. Many improvements and innovations have been made on it, especially in the high-level strategies.
2 Robosina's Architecture and New High Level Skills
Robosina's Architecture consists of four layers: Connection Layer, World Model Layer, Skills Layer and Decision Layer.
Main object of connection layer is making a network connection with soccer simulation server and send/receive data. After parsing incoming connection layer delivered this data to upper layer. World Model layer makes recognition of environment. Main duty of this layer is processing information and decrease noise of sensors. We have a lot of skills in skills layer such as block, intercept, and mark and so on. Decision layer decides what kind of skills must be done. After that each layer sends data to lower layer. At the end of this procedure connection layer send agent decision to server. We added some new high level skills to RoboSina such as Pass, Trough pass and Goalie Skill.
2.1 Pass
A new method is used for pass in UnKnown. According to this new method, the ball controller spots all players in the field, in each cycle and according to some parameters such as distance, possibility of intercept, time difference, effective opponent players and … , calculate a score for each player and with identifying the best pass receiver, send the pass. But we define an important parameter for each player, called effective which has the most affection on selecting best pass receiver. This parameter certifies offensive play for our team. Furthermore, with using auditory system, the receiver prepares for receiving pass. In this algorithm, a function evaluates the space around a player for existence of effective blocker players.
$$distanceToReceiver = init_ball_speed \cdot \frac{1 - ball_decay^{cycles}}{1 - ball_decay} \Rightarrow$$
$$cycles = \left[\log_{ball_decay}\left(1 - \frac{distanceToReceiver \cdot (1 - ball_decay)}{init_ball_speed}\right)\right] + 1$$
Figure 1. Implementation of computational algorithm for pass skill
2.2 Trough Pass
Like direct pass, ball controller calculates score for each teammate player according to mentioned parameters. Through pass is a pass to a particular point, so we need to find the proper point for sending pass. Therefore a lot of points are spotted for each player and the probability of receiving ball in that point effects on player score. Finally, if a proper player exists for receiving through pass, based on some strategic factors, ball controller decides whether to execute trough pass or not. The auditory system is also used for informing receiver player.
Figure 2. Trough pass model
2.3 Dribble
Dribble is a skill that depends on personal decision making. It contains three steps: run with ball, mislead player and hold ball. Given the fact that implementation of accounting algorithm which can gain the best kick to return ball to player's kickablearea without any extra turn and also give the maximum time for running with ball to player, is very difficult. So we used neural network to educate this expertness. Mislead player is the most important part in dribble skill. Therefore attention in implementation and check more details can improve this skill's capability. Figure 3 represents important points for dribble based on central point of agent's body.
Figure 4 shows a sample of successful dribble. This kind of misleading is similar to real footsal dribble and it's fastest and prosperous kind of misleading. The ball is taken to the place that opponent defender assumes to have ball in its kickable area in next cycle. The ball controller can take opponent defender to its back to acquire opportunity for executive final step.
Figure 5. Presentation of a successful long dribble
2.4 Shooting toward Goal
Shooting toward goal is the last task to reach the final aim. Similar to previous models, using learning method for shooting is essential.
Figure 6. Method of training the learner agent for shooting
3 Localization Algorithms
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. Robosina's 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 [3].
4 Scoring Policy
We have completed the development of scoring policy. 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 [4] 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 is raised to 75% of the shooting attempts.
5 Blocking and Marking
Another improvement in the high-level skills is developing an enhanced blocking skill using reinforcement learning. 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. We are going to develop this idea to make it more powerful for this year competitions.
Another strategy that is implemented 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 cannot move closer to the goal, or send and receive a pass.
6 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.
7 Conclusions and Future Work
In this team description paper, we have quickly addressed some improvements in our new soccer simulation team, UnKnown. For future directions, we are interested in studying reinforcement-learning techniques and applying fuzzy control and expert control to our team strategy and we are still working on intelligent algorithms to improve our team skills. Improving and adjustment low-level implements according to the new versions of soccer simulations server is our main concern. We hope to solve our team problems and add new abilities to agents. We have some new ideas for high level decision based on float playing.
References
- Emiel Corten et al. Soccerserver Manual,Version 5 rev 00 beta,. At URL http://www.dsv.su.se/ ~johank/ Robocup/ manual, July 1999.
- Amiri, F., Bashiri, H., Kafi, S., Kaviani, N.,Rafaie, M., Zarrabi-Zadeh, H.:: Robosina 2004 Team Description. In: RoboCup 2004 Symposium and Competitions.
- H. Zarrabi-Zadeh, M. Rafaie, M. Shabani, and N. Kaviani. Robot Positioning Using Visual Information. In 2nd National Computer Conference (NCC'2003), Mashhad, Iran, Dec. 2003.
- 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.
- M. Riedmiller, T. Gabel: Brainstormers 2D Team Description 2007: RoboCup 2007 Simulation 2D League Champion.