How we evolved a winning strategy for the RoboCup competition by imitating nature

The final of the RoboCup simulation, with Gliders2016 (Australia) defeating HELIOS2016 (Japan) 2:1. Mikhail Prokopenko, Author provided

“In football everything is complicated by the presence of the opposite team.” This observation by the French philosopher Jean-Paul Sartre has been cited in multiple contexts, ranging from tactical planning in team sports, to game-theoretic modelling of microeconomics, to full-blown robotic warfare.

The common thread in all these studies is conflict: adversarial interactions bring about a disorganisation that can disrupt the most prepared of schemes.

This operates across many domains. Once a design – whether a tactical plan or engineering blueprint – comes into a contact with some unforeseen circumstances – such as a new opponent strategy or natural disaster – then it is likely to crumble, no matter how detailed and pre-optimised the preparations were.

One way for a complex system to withstand sudden stresses is to exploit self-organisation of its constituent parts and adapt to changing circumstances.

But this comes at a cost. It is extremely hard to predict how a complex system is going to behave if you can only partition and analyse the behaviour of each of the parts separately.

So is there a way to anticipate the unexpected? This is the central challenge faced by “complex systems” researchers who design and build systems with inherent robustness and resilience.

Contents

Artificial evolution

We can illustrate this challenge by returning to football, and robot soccer in particular.

RoboCup is the World Cup of robot soccer. Now approaching its 20th anniversary, recent events have attracted more than 40,000 visitors and participants from more than 45 countries.

The final game of RoboCup-2016 Soccer Simulation 2D League in Leipzig, Germany, on July 3, 2016, between Gliders2016 (in red, University of Sydney & CSIRO, Australia) and HELIOS2016 (in yellow, Fukuoka University & Osaka Prefecture University, Japan).

It is also a leading benchmark for artificial intelligence (AI), robotics and multi-agent complex systems.

While the physical robot leagues tend to draw the most attention, there is also a simulation league, which focuses on advancing virtual AI.

In the RoboCup 2D Simulation League, two teams of 11 fully autonomous software programs (called “agents”) play soccer in a two-dimensional virtual soccer stadium, with no remote control. The entire RoboCup community has developed the open-source simulator and visualisation software over 20 years. It contains nearly a million lines of code.

Each agent has virtual visual, acoustic and physical sensors to detect what is going on around them. And each can perform some basic actions like running, turning and kicking the ball.

The main challenge is to derive the best possible action to execute at any specific time while facing the unexpected and disruptive actions of the opposing agents.

Each simulation step takes merely a tenth of a second, during which the entire sensory-motor cycle takes place within an agent. This starts with it receiving new sensory inputs from the simulator. It then evaluates possible choices – up to 100,000 per cycle – and sends the chosen action back to the simulator.

Gliders2016 team, which won the 2016 simulation competition in July this year, is a collaborative effort of the University of Sydney (Professor Mikhail Prokopenko, Dr Victor Jauregui) and CSIRO (Peter Wang, Dr Oliver Obst).

The author (centre podium, right) and Dr Obst (centre podium, left) claim the championship trophy at the 2016 RoboCup award ceremony in Leipzig, Germany.
Natalia Kishigami, Author provided

In order to optimise our team, we used a form of human-based evolutionary computation. This is how we innovated and tested new behaviours, improving performance from one artificial “generation” to another.

We evaluated the software using several supercomputer clusters, executing tens of thousands of experimental runs per day. The number of such trials is approaching 10 million.

The bigger picture

During testing, we didn’t just look at how intelligently the software agents performed individually or as a team. We also considered the bigger picture.

We looked at the complexity of the opposing team’s behaviour. And whether our software was easy to adapt, scalable and robust to changes.

We analysed how our team could respond to surprising novelties that the opposition might unleash during the next tournament. And whether it could recover from sudden setbacks during a game.

The winning goal scored by our RoboCup team, Gliders2016 (in yellow), in the 2D Simulation final of 2016.
Mikhail Prokopenko, Author provided

Many of these questions resonate with generic issues encountered in complex systems. We had to consider how a small change in the initial conditions – for example, increasing the risk tolerance in making a pass – can affect the overall outcome. Another aspect was whether the dynamics of the system tend to repeat particular trajectories. We also studied the role of randomness in the simulation and how to model hidden variables.

In short, we explored how complex systems can help in developing the RoboCup-winning team in 2016.

Inspiration from nature

One of the insights that inspired the tactics in our team was the patterns observed in flocks of birds and schools of fish. These are classic cases of complexity in biology.

In response to a predator, many schools of fish display complex patterns of spatial aggregation, so that small disturbances can quickly cascade through an entire group, transferring the survival-critical information.

For our RoboCup team, similar behaviour allows the virtual players to achieve a high degree of coherent mobility. On the one hand, the players are constantly refining their positions in response to opponent players. On the other hand, the repositioning is not erratic and the players move in co-ordinated ways.

The team tactics have also been evolved to counteract different types of opponents, creating a rich variety of behaviours and increasing robustness and resilience. We evaluated this approach using information theory, quantifying and predicting the “information flows” within the system, rather than just “data flows”. The key difference is that information provides context for data, and the information flows highlight the most relevant and salient dynamics.

The complexity of RoboCup teams will likely only grow with time, meeting new challenges and solving new problems, as the whole initiative and the technology keep advancing.

An entirely new generation of scientists and engineers will drive the innovations in 2036, when RoboCup marks another 20 years on its journey.

By then, it is quite likely that complex systems, as a field of study, will have taken a central stage in educational programs worldwide, integrating elements of information technology, physics, biology and mathematics, and developing future leaders in engineering, science and business.