Cyrus Soccer 2D Simulation Team Description Paper 2015

Nader Zare, Maryam Karimi, Ashkan Keshavarzi, Ehsan Asali, Hassan Ali Poor, Armin Aminian, Ehsan Beheshtian, Hadi Mola, Hossein Jafari, Mohammad Javad Khademian

Shiraz University of Technology; Tehran University; Shiraz University; Urmia University of Technology

Abstract This description expresses brief explanation about algorithms and aims in Cyrus 2D simulation team and presents an overview of team's performance and players capabilities. The main goal is to get the players the ablility to decide based on accurate and noise-free information. By checking different solutions in defense decision making and using communication between agents, environmental noise was omitted and defense decision making was improved. Different situations and approaches that could be used in defense will be discussed and a new approach of using message passing in 2D simulation for coordination between agents with the least expense will be introduced. The base code that Cyrus used is agent 3.11.

Introduction

Cyrus RoboCup team has formed by students of Shiraz University of Technology and participated in many competitions since spring 2011. This team has achieved First place in Iran Open 2014, 5th place in World Cup Brazil 2014, 8th place in World Cup Netherland 2013, First place in Kordestan 2013 and First place in Fazasazan 2012. This team has also participated in Iran Open 2013, Iran Open 2012, SharifCup 2012, Iran Open 2011, Sama RoboCup 2011 and etc. The goal of this team is to increase the level of knowledge, advance the achievement of the RoboCup competitions objectives and intelligent learning and using artificial intelligence in RoboCup [1, 2].

After Iran Open 2014 competition, one of the most important goals of the team was to omit noise and make defense system intelligent. The old techniques that has been used in the past included designing automatic agents, coordination between agents and team strategy, Kalman Filter, offline methods and machine learning techniques.

In this paper a new approach to solve problems related to decision making in 2D simulation is introduced. In this approach decision making in 2D simulation is considered as coordination and team work to achieve an objective. In this paper this approach is being used in defense decision making. In order to omit noise effect in agents' decision making, some massages should be passed between players. In the situation that coordination between agents is needed, an agent that has better view of environment tell the others what to do.

In the following, first communication between agents will be discussed, and then different approaches in multi-agent systems will be reviewed and compared with older methods.

Communication in RoboCup

In this paper Base agent3 has been studied. In this base players are allowed to send limited number of broadcast messages in each game. Simulated agents have some predefined type of messages and can send important messages to teammate agents. This should be noted that number of messages is limited and just some near agents can hear the message rather than all teammates. In addition to mentioned limitations in communication between agents in simulator, in each cycle just one of the players can send the message and if two players send messages simultaneously, it is possible that none of the messages will be heard by other players.

Defense strategy

In soccer 2D simulation according to game state, agents choose one of the possible behaviors related to present state automatically. Game situation can be split in to two situations, defense and offence. In defense mode, behaviors include block, mark, tackle and etc.

In each situation, agents need to do one of the mentioned behaviors; at the same time they need to gain game and players information. In soccer 2D simulation, information has too much noise and agents should decide base on noisy information. In the following 3 approaches for reducing noise will be discussed.

problem solving with greedy methods

In this approach agents specified defensive behaviors evaluation, according to the present state and specified state in the team formation. The agent decided based on those evaluations. As expected error possibility is too much in this method and specifying a suitable team formation is very important. Actually this approach had not used the benefit of multi-agency in soccer 2D simulation.

problem solving by considering players position

Agents in soccer 2D simulation have information about players' position in the field, but according to the view angle, each player sees a part of the field in each moment and updates the information about that part, so there is noise in information and it is inaccurate. If a player does not look at another player's direction, he should decide based on his old information.

In this approach each agent decided based on teammate players' positions and opponent players' positions for doing a defensive behavior. For example, for avoiding opponents from being near to our goal an eleven-cell-matrix including our players was created and each player calculated his teammates' evaluation for block behavior and chose a player with the highest value for doing defensive behavior.

This solution is a simplified problem in multi-agent environment, but when players' information is not accurate other agents' behaviors should be simulated too. It seems that if game's information was noise-free, this approach was suitable but according to the fact that this information is noisy the improvement of this method than the last one is not significant so we should find an approach to omit noise.

Investigations show that in RoboCup specially in 2D soccer simulation, teams used machine learning methods to omit noise and improve agents decision making by offline problem solving [4, 5].

Message passing in defense decision making

Previous works removed data noise and improve decision making by using machine learning and offline problem solving methods. In this paper the approach of message passing between players considering limitations has been discussed.

From the second approach, it can be understood that if agents' information from present state was accurate, each agent could solve problem considering other agents' position and game state, but since they have not a complete correct view of the game the decision could be wrong or two players may decide to do the same behavior.

First step to use message passing is too chose an agent that can decide accurately. This agent should have a better view than other agents. In other words this agent should have newer updates of information and can decide for other agents.

The player should be able to decide for other players but this situation is very rare and happens in limited number of states; so in order to find a suitable player and to reduce message passing, it is needed to omit opponent defensive player from effective players to make a more accurate decision.

In fig. 1 the players that are far from the ball were omitted from effective set of players and just effective agents from yellow team will be in this set and have effect in calculations. Then among the players that could have effect on present state, the one with the better view will decide for defensive behavior. In fig. 1 the yellow agent number 8 has the best view of other agents. In each cycle this calculation could be done so it should be as simple as possible.

$$E(agent[i]) = (3 - count_seen_ball) + (5 - dist_to_opponent)$$

According to formula 1evaluation of an agent for managing other players' behavior was calculated. By considering ball poscount cycle, best player was chosen. According to (1) and considering the condition of positive function, values for effective agents calculated and best agent was chosen.

For optimizing and satisfying communication limitations, number of times that each agents needs to send and receive messages is based on following conditions:

• The opponent ball owner player pass
• End of TTL of sent message
• Change in value of agents

According to the mentioned parameters agent can send limited number of messages and reduce the overhead of message sending.

Experiments and results

In order to test different approaches mentioned in this paper, a team with base Agent3 and mentioned algorithm were created. According to test results, the average numbers of received goals in 20 games with 4 first teams of World-Cup competition were as followed:

Statistical results achieved from first method

Statistical results achieved from second method

Statistical results achieved from third method

As it is obvious, the second method improved and reduce goal received by 37% in comparison to the first method and third method improved 82% in comparison to the first method.

Conclusion

In this paper by checking different methods that were used in Soccer 2D Simulation, a new method introduced. This new method is less complex and less expensive in comparison to older methods like machine learning, but it is not perfect. In order to avoid overhead of message passing, factors for optimizing number of messages should be defined. Finally it is concluded that using messages in coordination between agents in a system is a possible way to improve algorithms in multi-agent systems.

References

1. R.Khayami, N.Zare, M.karimi, P.Mahor, F.Tekara, E.Asali, A.Keshavarzi, A.Afshar, M.Asadi, M.Najafi, "CYRUS 2D Simulation Team Description Paper 2014", The 18th annual RoboCup International Symposium, Brazil, Joao Pessoa, 2014
2. R.Khayami, N.Zare, H.Zolanvar, M.karimi, P.Mahor, F.Tekara, E.Asali, M.Fatehi, "Cyrus Soccer 2D Simulation Team Description Paper 2013", The 17th annual RoboCup International Symposium, Netherland, Eindhoven, July 1, 2013
3. Mota,L., Lau,N., Reis, L,.: Co-ordination in RoboCup's 2D Simulation League: Setplays as flexible, Multi-Robot plans. IEEE(2010).
4. Wu, F., Zilberstein, S., Chen, X.: Online planning for multi-agent systems with bounded communication. Artificial Intelligence 175(2) (2011) 487-511.
5. Wu, F., Zilberstein, S., Chen, X.: Multi-agent online planning with communication. In: Proc. of the 19th Int. Conf. on Automated Planning and Scheduling. (2009) 321-328.
6. Noda, I., Stone, P.: The RoboCup Soccer Server and CMUnited Clients: Implemented Infrastructure for MAS Research. Autonomous Agents and Multi-Agent Systems 7(1{2) (July-September 2003) 101-120.
7. N. Lau, L. S. Lopes, and G. Corrente, "CAMBADA: Information sharing and team coordination," in Eighth Conference on Autonomous Robot Systems and Competitions. Aveiro, Portugal: Universidade de Aveiro,2008, pp. 27–32