View Original PDF

WrightEagle 2D Soccer Simulation Team Description 2015

Xiao Li, Rongya Chen, Xiaoping Chen

Department of Computer Science, University of Science and Technology of China

http://www.wrighteagle.org/2d/

Abstract WrightEagle 2D soccer simulation team has been participating in annual RoboCup competitions since 1999 and won 5 champions and 5 runners-up at RoboCup world championships in the past 10 years. In this paper, we briefly present our current research efforts and some newly introduced techniques since the last year competition.

1 Introduction

WrightEagle 2D soccer simulation team, which was established in 1998 as the first branch of WrightEagle RoboCup team developed by Multi-agent Systems Lab. of USTC, has been participating in annual competitions of RoboCup since 1999. In recent years, we have won the champions of RoboCup 2014, 2013, 2011, 2009 and 2006, the runners-up of RoboCup 2012, 2010, 2008, 2007 and 2005.

We take RoboCup soccer simulation 2D as a typical problem of multi-agent systems, and we concentrate on planning algorithm research and other challenging problems in artificial intelligence [1]. This year we implemented a fuzzy inference system in WrightEagle2015, and based on our research efforts [5,6,7,8,9,10,11,12,13,14,15].

In this paper, we present a brief description of some of our progress mentioned above.

In Jul. 2014, we also released the latest version (4.1.0) of our team's base code WrightEagleBASE to the public as an open-source software which can be freely accessed from our team's website. After this update, we added a wizard to help others to use the WrightEagleBASE. We believe that will greatly expand the scope of the use of WrightEagleBASE. We hope that our released software will be helpful to a team who wants to participate in the RoboCup event and/or start a research of multi-agent systems.

The reminder of this paper is organized as follows. Section 2 introduces the fuzzy inference based forecasting in WrightEagle. Section 3 presents the multistep pass strategy. Finally, the paper is concluded in Section 4.

2 Fuzzy Inference based Forecasting

Fuzzy inference is the process of formulating the mapping form a given input to an output using fuzzy logic [2]. In fuzzy logic, a statement is able to assume any real value between 0 and 1, representing the degree to which an element belongs to a set. So it is able to work with human inputs. On the other hand, fuzzy logic does not need complicated mathematical models. So the Fuzzy Inference System (FIS) is easy to implement.

FIS has been applied to WrightEagle in some aspects to forecast the behavior of the opponents, especially in defensive area.

Mamdani-Type Fuzzy Inference and Sugeno-Type Fuzzy Inference are two of the most common types of fuzzy methodology. These two methods will be introduced in the following part.

2.1 Mamdani-Type Fuzzy Inference

The Mamdani's fuzzy inference method is the most common fuzzy methodology. It was first proposed by Ebrahim Mamdani [3] in 1975. A Mamdani's fuzzy inference system is generally composed of five steps:

  1. Determine a set of fuzzy rules,
  2. Fuzzify inputs with the input membership functions,
  3. Obtain each rule's conclusion,
  4. Aggregate conclusions obtained in step 3,
  5. Defuzzification.

The form of fuzzy rules in Mamdani's fuzzy inference system is always like this:

If $x$ is $A$ and/or $y$ is $B$ , then $z$ is $C$ .

where A, B and C are linguistic values defined in the fuzzy set.

For a fuzzy set A, its membership function is defined as µ^A : X → [0, 1]. Set X is the universe of discourse. For each x ∈ X, the value µA(x) is called the degree of membership of x to fuzzy set A. For example, if µA(x) = 0.7, we can say that x belongs to A to a degree of 0.7.

With the fuzzy set, we can describe fuzzy concept like "large" and "small". Therefore, the FIS is able to deal with human inputs.

2.2 Sugeno-Type Fuzzy Inference

The Sugeno fuzzy inference method was first proposed in 1985 [4], it is very similar to the Mamdani's method. Generally, the Sugeno fuzzy inference system is composed of four steps:

  1. Determine a set of fuzzy rules,
  2. Fuzzify inputs with the input membership functions,
  3. Obtain each rule's conclusion,
  4. Aggregate conclusions obtained in step 3.

The form of the rules in Sugeno method is like this:

If x is A and/or y is B, then z is $f(x, y)$ .

Unlike the Mamdani's method, the output of Sugeno method is no longer a fuzzy set. It is a function of the inputs. So there is no need of defuzzification.

2.3 Comparison between Mamdani and Sugeno

Based on the form of the rules, we can find out that the Mamdani's method is more intuitive. But in 2D simulation, every decision should be made within 100ms. If the number of the rules is large, it will take much time to compute. So we should apply the Mamdani's method on scenes with small number of rules. Science the output is a function of the inputs in Sugeno method, it is computationally efficient. So it is able to handle with scenes with large number of rules.

3 Multi-Step Pass Strategy

WrightEagle combines best-first strategy with the thought of anytime using topdown tree search method, and is able to plan multi-step pass strategy among several players. The planning assumes that the position of opponents and teammates never change, which does not usually happen in real game. In order to be close to the real situation of soccer game, one of our focus of this year is to consider the initiative of certain players teammates, which will change search heuristics and pruning strategy. We first use it in some scenes, such as that when player get no solution in attack situation. If it meets the requirements of real-time game, we will consider applying it in more scenarios.

The most important part of behavior predictor is to estimate the position of partner in robotic soccer simulation game. The uncertainty of both players observation and the partners decision tends to bring "jitter" in decision, and the accuracy of players location plays a key role in the assessment of search results. WrightEagle has applied "Inverse Calculation" method to predict the position of passing point in a single step. Machine learning mechanism has been widespread used in cooperative strategy by many other teams. Combined with new approach on our basis, it is expected to achieve better results in a multi-step pass behavior. So in following days, we will put more effort on it.

For example, as shown in Figure 1, player 4 successfully speculates that he should dribble to a certain yellow point and then pass the ball to the red point labled PassAssist, while player 11 is getting ready to perform a cooperation. Figure 2 shows player 11s decision that he should prepare for getting the ball as player 4 is dribbling. One of the most import thing is to make player 4 and player 7 to know the result of each others calculation. The result may be not accurate but should be approximate to the real result.

Fig. 1.
Fig. 1.
Fig. 2.
Fig. 2.

4 Conclusion

For the purpose of forecasting actions of opponents in soccer simulation 2D, we introduced Mamdani-Type Fuzzy Inference and Sugeno-Type Fuzzy Inference to deal with scenes in soccer simulation 2D. The most important advantage of FIS is that it can work well without the knowledge of the mathematical description of the opponent. Another advantage of the FIS is that, when we want to take account more things, what we need to do is to add new rules or edit old rules. Then we do not have to take much time to write a new algorithm. On the other hand, multi-step pass strategy has been applied to WrightEagle to predict the position of passing point. We will make more efforts to improve its performance.

References

  1. Chen, X.: Challenges in research on autonomous robots. Communications of China Computer Federation 3(12) (2007)
  2. Zadeh, L.A.: Fuzzy Sets. In: Information and Control 8 (3) , pp. 338-353. (1965)
  3. Mamdani, E.H., S. Assilian,.: An experiment in linguistic synthesis with a fuzzy logic controller. In: International Journal of Man-Machine Studies, Vol. 7, No. 1, pp. 1-13 (1975)
  4. Sugeno, M.: Industrial applications of fuzzy control, Elsevier Science Pub. Co. (1985)
  5. Fan, C., Chen, X.: Bounded incremental real-time dynamic programming. In: Frontiers in the Convergence of Bioscience and Information Technologies, 2007. FBIT 2007, IEEE (2007) 637-644
  6. Wu, F., Chen, X.: Solving large-scale and sparse-reward dec-pomdps with correlation-mdps. RoboCup 2007: Robot Soccer World Cup XI (2008) 208-219
  7. 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
  8. Shi, K., Chen, X.: Action-driven markov decision process and the application in robocup. Journal of Chinese Computer Systems (2009)
  9. Wu, F., Zilberstein, S., Chen, X.: Point-based policy generation for decentralized pomdps. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems (2010) 1307-1314
  10. Zhang, Z., Chen, X.: Accelerating point-based pomdp algorithms via greedy strategies. Simulation, Modeling, and Programming for Autonomous Robots (2010) 545-556
  11. Wu, F., Zilberstein, S., Chen, X.: Online planning for multi-agent systems with bounded communication. Artificial Intelligence 175(2) (2011) 487-511
  12. Bai, A., Wu, F., Chen, X.: Online planning for large mdps with maxq decomposition (extended abstract). In: Proc. of 11th Int. Conf. on Autonomous Agents and Multiagent Systems, Valencia, Spain (June 2012)
  13. Wu, F., Zilberstein, S., Chen, X.: Online planning for ad hoc autonomous agent teams. In: Twenty-Second International Joint Conference on Artificial Intelligence. (2011)
  14. Bai, A., Wu, F., Chen, X.: Towards a principled solution to simulated robot soccer. In Chen, X., Stone, P., Sucar, L.E., der Zant, T.V., eds.: RoboCup-2012: Robot Soccer World Cup XVI. Volume 7500 of Lecture Notes in Artificial Intelligence. Springer Verlag, Berlin (2013)
  15. Bai, A., Wu, F., Chen, X.: Online planning for large mdps with maxq decomposition. In: Proceedings of the Autonomous Robots and Multirobot Systems workshop (at AAMAS-12). (Jun 2012)