1. INTRODUCTION

We use team robotics as a model for the planning, design, management and control of multilevel complex socio-technical systems including organisations such hospitals, airlines, and banks, and socio-economic policy at national and international levels. We choose robot soccer as the example for team robotics because it has well-established rules, there are many games to study, and it provides a platform for experimentation and communication.

The great advantage of studying team robotics as an exemplar of complex systems is being able to focus on team interactions without being distracted by the greater complexities of human agents. For example, unless such behaviour is programmed into them, robots will not pick up the ball and run with as William Webb-Ellis is said to have done in 1823, thereby inventing the game of rugby. Thus team robotics provides a class of complex socio-technical systems that is more complex than many physical systems, but less complex than most social systems. The methodological framework developed here for team robots is intended to be extended and applied to social systems.

The challenge of robot soccer goes back more than 20 years [1], and can be simply stated as “By the middle of the 21st century, a team of fully autonomous humanoid robot soccer players shall win a soccer game, complying with the official rules of FIFA, against the winner of the most recent World Cup.” Of many varieties of robot soccer we choose to study the RoboCup simulation league. This enables us to focus on the spatio-temporal structures of the team interactions without being distracted by the considerable engineering challenges of building physical robots.

2. MULTIDIMENSIONAL STRUCTURE IN ROBOT SOCCER

Atkin [2] proposed analysing the relational structure of chess with his methodology of Q-analysis. Atkin studied the relations between the pieces and the squares of the board, e.g., in Figure 1a the black rook, black king and white knight form a structure called a knight fork while in Figure 1b they do not. However, the configuration in Figure 1b is a precursor to the knight fork, and this plays a part on the evolving structure of the game. Although not a knight fork itself, unless black moves to prevent it, the white knight can move to form the knight fork configuration of Figure 1a.

Figure 1

Structure in the game of chess. (a) A knight fork in chess. (b) a knight fork precursor.

Gould and Gatrell [3] suggested that Atkin’s method could be applied to soccer analysing the 1977 Football Association Cup Final in the UK. Johnson [4] suggested applying the method to robot soccer [5] and it was further developed by Johnson and Iravani [5] using Johnson’s theory of hypernetworks [6]. Recently Ramos et al. [7] showed how the hypernetwork approach can be applied in sports science.

At the heart of the hypernetwork methodology is the fact that in most complex systems the relationships of interest are not just between two elements but can be between n > 2 elements. This is illustrated in Figure 2.

Figure 2

n-ary relation structures in soccer (from Johnson [6]). (a) The defender’s dilemma. (b) The goalkeeper’s dilemma.

The “defender’s dilemma” (Figure 2a) involves three players – two red team players and a blue team player. This can be written as <r₁, r₂, b₁> which generalises the notation of network edge. In fact this structure could be written as three binary relations <r₁, r₂> + <r₁, r₂> + <r₁, r₂> but this would be a poor representation because the dilemma involves all the players at once, not just a combination of binary relations.

Figure 2b shows the goalkeeper’s dilemma as a 4-ary relation <r₂, b₀, G_b, ball> which, again, is not just a combination of 2-ary relations (G_b is the blue goal). Apart from the need to generalise networks to higher dimensional edges (which are called simplices) another essential generalisation of network theory is to include the relation symbol in the notation. Thus the defenders dilemma can be better represented by the notation <r₁, r₂, b₁, ball; R_{defenders_dilemma}> which allows the relational structure to be discriminated from other 4-ary relations on these elements – of which there may be many in a soccer match. A set of n elements with and n-ary relation between them is called a hypersimplex. A set of hypersimplices is called a hypernetwork [6].

Figure 3 shows how the binary (2-ary) relations of networks can be generalised. A 3-ary relation between three players can be represented by a triangle with three vertices; a 4-ary relation between four players can be represented by a tetrahedron with four vertices; a 5-ary relation between five players can be represented by a multidimensional polyhedron with five vertices, and so.

Figure 3

Hypersimplices as multidimensional polyhedra.

Figure 4 shows that hypersimplices can have higher dimensional connectivities, e.g. in Figure 4a the tetrahedra and triangles share edges, or one-dimensional connections. Figure 4b shows how two tetrahedra can be connected through a two-dimensional triangular face. In general simplices can be connected through multi-dimensional faces, generalising network connectivity through single vertices. This provides a new kind of connectivity structure with potential for exploitation in robot soccer.

Figure 4

Multidimensional connectivity between hypersimplices. (a) a 1-connected chain. (b) 2-connected tetrahedra.

In soccer three kinds of neighbourhood structures can be identified:

1. (i)

   a player has possession of the ball.

2. (ii)

   a player dribbles the ball.

3. (iii)

   a player tackles an opponent.

   The first of these is characterised by a relation between the player and the ball, <player, ball; R_possession; z, t>.

   The symbol t denotes time. In the simulation version of robot soccer in this paper the game lasts for 6000 ticks of the clock, notionally 10 min at 10 ticks per second. Let <player, ball; R_possession; z, t> be called a possession point. The symbol z represents the position of the possession point. At its simplest we could write z = (x_player, y_player, x_ball, y_ball). Thus the symbols z and t represent the space-time structure of the robot soccer dynamics.

   The second structure, dribbling the ball, can be denoted as a sequence of possession points involving just one player <<player, ball; R_possession; z, t>, <player, ball; R_possession; z; t′>; <player, ball; R_possession; z; t″>; . . . …; R_dribble>>.

   The third structure is a relation between members of opposite teams, r in the ‘red’ team and b in the ‘blue’ team, denoted <<r, ball; R_possession; z; t>, <b, ball; R_possession; z; t′ >; R_tackle>.

   Another fundamental structure in robot soccer is

4. (iv)

   a player passes the ball to a team-mate

   This structure can be characterised as <<player, ball; R_possession; z; t>, <player′, ball; R_possession; z; t′>; R_pass>. Let this be called a pass structure.

3. MULTILEVEL SYSTEMS

The structures (iii) and (iv) in the previous section are interesting because they are built on relations between two possession points, i.e. they are structures formed from more elementary structures. If the players and ball are said to be elements at Level N, a structure such as a possession point exists at Level N + 1, and a pass or a tackle exists at Level N + 2. A multilevel representation is essential for soccer because, as will be illustrated, the game is one of players trying to create ‘good’ multilevel structures and trying to destroy ‘bad’ multilevel structures.

The RoboCup simulation league soccer games that will be used for illustration last for 6000 ticks of the clock (10 min if 10 ticks represent 1 s). Although it would be possible to provide information about the whole game, e.g. the percentage time each team has possession, chunks of time naturally occur over intervals as short as a 100 ticks. Figure 5 illustrates how the 6000 ticks of a soccer game can be structured by possession between the red Gliders’ team and the blue CYRUS team.

Figure 5

The temporal possession structure in robot soccer.

The red rectangles represent periods when the red players are closest to the ball. For example, the period 0–170 is controlled by the red team at the kick-off and the period 1204–1346 is controlled by the blue team. The pink (cyan) line at the beginning indicates that the ball is not moving, i.e. the red (blue) team is taking a long time to initiate play. The solid red (blue) rectangles are periods when red (blue) is in direct possession. The white gaps at the bottom are periods when neither red nor blue players are close enough to the ball to be in possession but, in this case, the red (blue) team controls the ball. The black lines show that the ball is out of play.

4. AN ILLUSTRATIVE EXAMPLE

Figure 6 shows a green-coloured trajectory for the ball between a throw-in at A and a goal being scored at I. The red team has players denoted r₁, r₂, r₃, . . ., and attacks the goal on the right. The blue team has players denoted b₁, b₂, b₃, . . ., and attacks the goal on the left. The trajectory has discernable parts beginning with AB where r₅ takes the throw-in to r₈.

Figure 6

A soccer ball trajectory beginning at t = 4131.

Let R_pass be the passing relation where <r₅, r₈; R_pass> means that r₅ passes to r₈, and <r₅, r₈; z; t = 4131; R_p> means that r₅ passes to r₈ at time t = 4132.

The closest opponent relation, R_closest, between the players at time 4131 is shown by thin grey lines. A thick grey line between players shows that they are mutually closest to each other under the relation R_{mutually_closest}. The closest opponent relation here results in four connected components:

R_c components at time t = 4132

• C1 → <r₁, r₂, r₄, r₇, b₁₁; z; t; R_closest>

• C2 → <r₃, r₆, r₁₁, b₁, b₂, b₃, b₆, b₁₀; z; t; R_closest>

• C3 → <r₅, r₈, r₁₀, b₄, b₇, b₉; z; t; R_closest>

• C4 → <r₉, b₅, b₈; R_closest>

The fundamental hypothesis is that structures such as these may be predisposed to good or bad outcomes for one or other team. In soccer the ultimate objective is to score goals, but usually goals only emerge at the end of a sequence of ‘good’ discrete structures such as that illustrated by the ball trajectory in Figure 6. The challenge is to be able to recognise structures as being ‘good’ or ‘bad’ and to move so that ‘good’ structures emerge.

From Figures 6 and 7 it can be seen that the structural change between t = 4131 and t = 4145 can be summarised as follows:

Time t = 4145 components

• C1 → <r₁, r₂, r₄, r₇, b₁₁; R_c>

• C2 → <r₃, r₆, b₁₀; R_c> + <r₁₁, b₁, b₂, b₃, b₆; R_c>

• C3 → <r₅, r₈, b₉; R_c> + <r₁₀, b₄, b₇; R_c>

• C4 → <r₉, b₈; R_mc>

Figure 7

The ball position at t = 4145.

As can be seen two of the components, C1 and C4, remain unchanged while the two closest to the ball, C2 and C3, break into substructures.

Figure 8 shows the ‘closest to’ relation between the players and small areas of the pitch. At first sight this structure suggests that the red and blue teams have comparable domination of the pitch with the blue team controlling more of it.

Figure 8

The pitch possession structure at t = 4145.

However, as Figure 9 shows player r₆ has enabled new structures to emerge by dribbling the ball from C to D. During this time the configuration <r₁, r₂, r₄, r₇, b₁₁; R_c> has changed, with b₁₁ moving to the left and r₇ moving to the right. This structural change is bad for blue since r₇ now controls more space (Figure 10), enabling r₆ to pass the ball to it at E.

Figure 9

The position at t = 4165.

Figure 10

The pitch possession structure at t = 4165.

Following this pass, r₇ dribbles the ball to F (Figure 11). During this time the structure <r₉, b₅, b₈; R_c> has changed with r₉ becoming closest to its target goal and b₅ moving upwards – a very bad structure for blue!.

Figure 11

The position at t = 4188.

By moving in this way the blue team has allowed a “corridor” to emerge, shown as a yellow triangle in Figure 12. This provides a space for the ball to be passed into an area controlled by r₉. As shown in Figure 13, r₇ takes this opportunity and passes the ball to r₉ at G.

Figure 12

The pitch possession structure at t = 4188.

Figure 13

The position at t = 4217.

This involves r₉ moving a considerable distance, but note too that r₁₁ has broken free from its component at the centre of the pitch and has created space in front of the goal, connected to the space occupied by r₉ and the ball (Figure 14).

Figure 14

The pitch possession structure at t = 4217.

The ball is then passed from r₉ to r₁₁, who scores the goal, as shown in Figure 15.

Figure 15

The position at t = 4230.

5. MULTIDIMENSIONAL HYPERSIMPLICES

Although the discussion in the previous section was based on the binary relations ‘r is closest to b’ and ‘b is closest to r’, the small networks induce n-ary relations on the players. Of course, n-ary relation can be defined that cannot be resolved into binary relations, as illustrated in Figure 16.

Figure 16

Configurations as multidimensional hypersimplices. (a) t = 3727. (b) t = 3735.

In this case a set of n players is said to be R-related if they form a polygon containing no opponents. For example, <r₇, r₉, r₁₀, r₁₁; R> is shown as a pink polygon at t = 3727. These structures are remarkably enduring in time, sometimes lasting many ticks of the clock. However, inevitably the relations change and new structure emerge. Structures of particular importance are the ‘tight’ configurations of opponent players, as illustrated by the triangle <r₆, b₆, b₁₀; R>. Such configurations occur frequently in the goal area and are often precursors to scoring goals.

6. CONCLUSION

It has been shown that configurations of soccer players in the context of areas of the pitch and it goals have a multidimensional representation as hypersimplices. This leads to three major research questions:

• Research Question 1: Are some hypersimplices particularly disposed to scoring goals?

• Research Question 2: Can the relevant n-ary relations of robot soccer be learned from historical games, or must they be formulated by humans?

• Research Question 3: How can the multidimensional connectivity of hypersimplices be exploited to plan and control the evolutionary dynamics of robot soccer?

CONFLICTS OF INTEREST

The authors declare they have no conflicts of interest.

Authors Introduction

Prof. Jeffrey Johnson

He received his PhD in Mathematics from Essex University in 1976. He is a Professor of Complexity Science and Design in the School of Engineering and Design at the Open University in the UK. He is a Past-President of the Complex Systems Society and Vice-President of the UNESCO UniTwin Complex Systems Digital Campus. He is a chartered mathematician and a chartered engineer.

Mr. Ruggero Rossi

He received his M.Sc. in Economics of Networks and Innovation, magna cum laude from the University of Modena and Reggio Emilia in 2009, and a degree in Business Economics from the University of Modena and Reggio Emilia, Faculty of Economics and Business. He is a research student in the School of Engineering and Innovation at the Open University in the UK.