FRA-UNIted — Team Description 2016

Thomas Gabel, Constantin Roser

Faculty of Computer Science and Engineering Frankfurt University of Applied Sciences

Abstract The main focus of FRA-UNIted's effort in the RoboCup soccer simulation 2D domain is to develop and to apply machine learning techniques in complex domains. In particular, we are interested in applying reinforcement learning methods, where the training signal is only given in terms of success or failure. This paper outlines the history and architecture of the FRA-UNIted team and highlights current educational and research efforts.

1 Introduction

The soccer simulation 2D team FRA-UNIted is a continuation of the former Brainstormers project which has ceased to be active in 2010. The ancestor Brainstormers project was established in 1998 by Martin Riedmiller, starting off with a 2D team which had been led by the first author of this team description paper since 2005. Over the years, a number of sister teams emerged (e.g. the Tribots and Twobots) participating in real robot leagues. Our efforts in the RoboCup domain have been accompanied by the achievement of several successes such as multiple world champion and world vice champion titles as well as victories at numerous local tournaments throughout the first decade of the new millennium.

While the real robot teams mentioned were closed down entirely, the 2D team has been in suspend mode since 2010 and was re-established in 2014 at the first author's new affiliation, Frankfurt University of Applied Sciences, reflecting this relocation with the team's new name FRA-UNIted, as well.

As a continuation of our efforts in the ancestor project, the underlying and encouraging research goal of FRA-UNIted is to exploit artificial intelligence and machine learning techniques wherever possible. Particularly, the successful employment of reinforcement learning (RL) methods for various elements of FRA-UNIted's decision making modules – and their integration into the competition team – has been and is our main focus.

Moreover, the extended use of the FRA-UNIted framework in the context of university teaching has moved into our special focus. So, we aim at employing the 2D soccer simulation domain as a fundament for teaching agent-based programming, foundations of multi-agents systems as well as applied machine learning algorithms.

In this paper, we specifically focus on the most recent changes and extensions to the team as well as on the results of currently conducted research-oriented case studies. We start this team description paper, however, with a short general overview of the FRA-UNIted framework. Obviously, to this end, there is a lot of overlap with our older team description papers written in the context of our ancestor project (Brainstormers 2D, 2005-2010) which is why the interested reader is also referred to those publications.

1.1 Design Principles

FRA-UNIted relies on the following basic principles:

There are two main modules: the world module and the decision making module.
Input to the decision module is the approximate, complete world state as provided by the soccer simulation environment.
The soccer environment is modelled as a Markovian Decision Process (MDP).
Decision making is organized in complex and less complex behaviors where the more complex ones can easily utilize the less complex ones.
A large part of the behaviors is learned by reinforcement learning methods.
Modern AI methods are applied wherever possible and useful (e.g. particle filters are used for improved self localization).

1.2 The FRA-UNIted Agent

The decision making process the FRA-UNIted agent is inspired by behaviorbased robot architectures. A set of more or less complex behaviors realize the agents' decision making as sketched in Figure 1. To a certain degree this architecture can be characterized as hierarchical, differing from more complex behaviors, such as "no ball behavior", to very basic, skill-like ones, e.g. "pass behavior". Nevertheless, there is no strict hierarchical sub-divisioning. Consequently, it is also possible for a low-level behavior to call a more abstract one. For instance, the behavior responsible for intercepting the ball may, under certain circumstances, decide that it is better to not intercept the ball, but to focus on more defensive tasks and, in so doing, call the "defensive behavior" delegating responsibility for action choice to it.

2 Case-Based Opponent Modeling

Recognizing and predicting agent behavior is of crucial importance specifically in adversary domains. In [1], we recently published the results of a case study that is concerned with the prediction of the low-level behavior of soccer simulation 2D agents. Case-based reasoning [2] represents one of the potentially useful methodologies for accomplishing the analysis of the behavior of a single or a team of agents. In this sense, the basic idea of our approach is to make a case-based agent observe its opponent and, in an on-line fashion, i.e. during real game play, build up a case base to be used for predicting the opponent's future actions.

While in previous and related work it has frequently been claimed that the prediction of low-level actions of an opponent agent (kick, dash, or turn including its real-valued parameters) in this application domain is infeasible, we show that – at least in certain settings – an on-line prediction of the opponent's actions can be made with high accuracy. We also stress why the ability to know the opponent's next low-level move can be of enormous utility to one's own playing strategy.

As an example, Figure 2 shows how accurately the parameters of an action were predicted, given that the type of the action could be identified correctly beforehand. Here, we compare (a) an "early" case base with only 10 cases, (b) an intermediate one¹ with $|\mathcal{C}|=100$ as well as (c) one that has resulted from 2000 simulated time steps and contains approximately 1500 cases. Interestingly, even in (a) comparatively low errors can be obtained. In (b) and (c), however, the resulting average absolute prediction errors become really competitive ($\pm 2.9$ for dash powers x with $x \in [0, 100]$, $\pm 6.3$ for kick powers x with $x \in [0, 100]$, and $\pm 19.7^{\circ}$ for kick angles $\alpha$ with $\alpha \in [0^{\circ}, 360^{\circ}]$). For the full set of results and a detailed description of the entire on-line learning approach, the reader is referred to [1].

¹ A case base of a size of about 100 to 500 cases can easily be created within the first half of a match for most players.

Fig. 2. Exactness of the prediction of the action parameters for different stages during ongoing learning (10, 100, and $\approx 1500$ cases in the case base). Left: Average error of the predicted angle of a kick action. Right: Average error of the predicted relative power of a kick action and dash action (averages over agents from all opponent teams considered).

3 About Progress in Soccer Simulation

In human soccer playing, it is impossible to make sound statements about the development of the playing performance level over years. With respect to longterm comparisons, one might argue that the situation is better in robot soccer. Practice in RoboCup has taught, however, that such an approach is infeasible with real robots. RoboCup's simulation leagues adopt a special role [3]. However, the performance of soccer-playing software agents strongly relies on the simulation of the physical world they are placed in. If the characteristics of that simulation change, a meaningful evaluation of the progress made over years is rendered impossible. From 2003 to 2007 as well as from 2010 to present, however, the Soccer Server underwent no significant changes such that all team binaries released within these time periods are fully comparable. In [4], we performed an extensive empirical analysis that focused on the five-year period of stability (2003-2007) where no changes were introduced into the Soccer Server. In brief, our findings indicated that the progress made during the stable period (2003- 2007) is astonishing. For example, while admired for their sophisticated play in 2003 and 2004 [5], world champions of those times played at the level of a lowclass team a few years later, sometimes losing in the double digits against top teams from 2006 or 2007.

A dangerous development that might arise in a situation where a group is dominated by a small fraction of its members (like in soccer simulation where WrightEagle and HELIOS happened to be the dominating teams for years) is that some kind of over-specialization is generated. For the soccer simulation domain this means that most, if not all, participants start optimizing their teams' strategies specifically against the most recent versions of last year's winner or runner-up teams. If this kind of incestuous overfitting takes place, then we should expect to see that (much) older team binaries start to come off better the older their date of publishing.

In [6], we specifically focused on the development of the playing strength of our former team throughout the time period from 2003 to 2007. Given the fact that (a) the last time the former Brainstormers team (called BS10 in the following) participated in a tournament was during the German Open 2010 in Magdeburg, Germany, and (b) that the Soccer Server was kept stable once more (except from bug fixes) for a number of subsequent years (from 2010 to the time being), a highly interesting question to answer is, to what extent did the performance of our non-modified team from 2010 decline during the past five years.

Given the mentioned key findings for the period from 2003 to 2007, we should expect that BS10's performance should have dropped significantly over the years from 2010 to 2015, i.e. it should perform much worse when playing against top teams from 2015 or 2014. Otherwise, if we find that, as an example, BS10 plays better against teams from 2014 than it plays against teams from 2011, then we should start wondering why and speculate that some kind of team strategy overfitting has taken place.

In order to investigate this issue, we made BS10 [6] play repeatedly against the top teams from each year from the period from 2010-15². By "top teams" we here restrict ourselves to those four teams that made it to the semi-finals in the respective years' RoboCup world championships. So, BS10 had to play 400 matches against representatives from each of the six years considered (2010-15). In Figure 3, we plot the share of matches won/drawn/lost from BS10's perspective. Clearly, this old team binary performs the worse the newer its opponents – which is good from the point of view of the overall further development of the 2D league, as it contradicts the above-mentioned overfitting hypothesis.

Next, we extended this analysis to all other teams published during recent years (to be exact we focused on the top four teams from each year, only). So, we determined for all these team binaries (a) how well they played when they made it to the top four (and thus became a representative for the respective) by playing against all other representatives from their year and (b) how much better or worse (relative to (a)) they performed when playing against the representatives of the following year. We continued this analysis for all remaining years from 2010 to 2015, denoting the time elapsed as the "age" of the respective binary.

Although there are a few exceptions, Figure 4 shows clearly that there is no indication that – with a team binary's increasing age – its performance starts increasing again due to reasons of over-specialization of the other teams against the most recent top teams. Percentage values in this figure are based on the point sums each team carved out it in a specific year (three points for a victory, one for a draw, zero for a defeat) compared to the point sum in its year of publishing. This finding is in alignment with the trend for BS10 reported above (see Figure 3, here denoted as data series "Inactive"). BS10's performance, though slightly above the average, decreases slightly from year to year, and there is no sign of a turn-around in terms of improving performance with increased age. To sum up, on average a team binary published and used in year y loses about 10-20% of its strength per year and will, for example when playing against the representatives from year y + 3, yield only about 60% of the number of points it had carved out against the top teams from year y. The entire set of results of this study is to appear in a yet to be published paper submitted recently.

² Corresponding team binaries retrieved from http://chaosscripting.net/

Fig. 3. Our ancestor team, Brainstormers, at its state reached in 2010, when playing 400 matches each against the top teams from each of the years from 2010 to 2015.

Fig. 4. No Sign of Over-specialization: Team binaries do, in general, perform worse the older they get.

4 Summary

In this team description paper we have outlined the characteristics of the FRA-UNIted team participating in RoboCup's 2D Soccer Simulation League. We have stressed that this team is a continuation of the former Brainstormers project, pursuing similar and extended goals in research, development as well as for teaching purposes. Specifically, we have put emphasis on a number of recent research activities that included opponent modeling and a progress analysis of the soccer simulation 2D league in general.

References

Gabel, T., Godehardt, E.: I Know What You're Doing: A Case Study on Case-Based Opponent Modeling and Low-Level Action Prediction. In: Workshop on Case-Based Agents at the International Conference on Case-Based Reasoning (ICCBR-CBA 2015), Frankfurt (2015) 13–22
Richter, M., Weber, R.: Case-Based Reasoning: A Textbook. Springer, Heidelberg, Germany (2013)
Akiyama, H., Dorer, K., Lau, N.: On the Progress of Soccer Simulation Leagues. In: R. Bianchi, H. Akin, S. Ramamoorthy, K. Sugiura, editors, RoboCup 2014: Robot Soccer World Cup XVIII, LNCS, Joao Pessoa, Brazil, Springer (2014) 599–610
Gabel, T., Riedmiller, M.: On Progress in RoboCup: The Simulation League Showcase. In: J. Ruiz-del-Solar, E. Chown, P. Plger, editors, RoboCup 2010: Robot Soccer World Cup XIV, LNCS, Singapore, Springer (2010) 36–47
Pagello, E., Menegatti, E., Bredenfeld, A., Costa, P., Christaller, T., Jacoff, A., Polani, D., Riedmiller, M., Safiotti, A., Sklar, E., Tomoichi, T.: RoboCup-2003. New Scientific and Technical Advances. AI Magazine 25 (2004) 81–98
Gabel, T., Riedmiller, M.: Brainstormers 2D Team Description Paper. Technical report, Faculty of Engineering, Department of Computer Science, University of Freiburg, Freiburg i.B., Germany (2010)