Search this site
Embedded Files
BBOLab@Univ. Tsukuba
  • Home
  • Joining BBOLab
  • Research Topics
    • New to the field?
    • Learning materials
    • Research findings
    • Software
  • Publications and Awards
  • Lecture (Japanese only)
    • 情報科学類主専攻実験
BBOLab@Univ. Tsukuba
日本語

New to the field?

This page introduces the two research areas we work on, evolutionary computation and reinforcement learning, using simple examples.

An Example: Automatic Ship Berthing

Together with a group at Osaka University, we study technology for autonomous ships, that is, ships that can operate without a person at the controls. We use this research to explain evolutionary computation and reinforcement learning.

Automatic berthing

Berthing means bringing a ship safely to a target position at a pier or quay and stopping it there. You can see how a large ship berths in a video published by the Osaka University group. Automatic berthing is a technology that lets a ship do this by itself. It is one of the key technologies for autonomous ships.

To berth automatically, the ship must keep checking its own condition (such as its position and speed) and its surroundings (such as obstacles and the weather). It must then decide what to do next (such as the rudder angle and the propeller speed). For this, it needs a rule for making decisions.

We call the ship’s condition together with its surroundings the state, written s, and what the ship does the action, written a. The rule is then a function that takes a state s and returns an action a. It can also be a rule that gives the probability of choosing each action in each state. Such a rule is called a controller or a policy. So automatic berthing comes down to one question: how do we find a good policy?

Reinforcement learning

One way to find a policy is reinforcement learning, which finds a good policy by trial and error.

In reinforcement learning, the learner is called the agent, and everything else is called the environment. In automatic berthing, the ship is the agent, and the sea, the quay and the wind are the environment. Learning goes like this:

  1. The agent looks at the current state s and chooses an action a by following its policy.

  2. The ship moves as a result. The wind may also change the state, whatever the action is. Moving from state s to a new state s′ is called a state transition.

  3. The agent observes the new state and receives a reward, a number that tells how good the situation is. People design the reward.

  4. The agent changes its policy so that it will get more reward in the future.

By repeating these steps many times, the agent learns a policy that collects as much reward as possible. This is reinforcement learning.

In practice, we cannot simply let a real ship learn by trial and error. While learning, the ship may take bad actions and crash into the pier, which is dangerous. Moving a real ship over and over also costs a great deal of money and time.

One solution is to build a simulator, a computer program that reproduces how the ship moves, and let the agent learn inside it. A crash in a simulator harms no one, so learning is safe. And once the simulator is built, learning costs far less time and money. However, no simulator is perfect, and a policy learned in a simulator may not work as well on a real ship. This is an important research problem, and we are working on it.

A policy learning by trial and error to berth a ship in a simple ship model. At first the ship hits the quay or wanders off, but after many trials it learns to stop at the target position, parallel to the quay. (The policy was trained with CMA-ES.)

Evolutionary computation

Above, we said that we build a simulator. But building an accurate ship simulator is itself difficult.

A ship simulator calculates how the ship moves by solving its equations of motion (differential equations). Given the current state and action, they tell us the next state. Standard mathematical models of ship motion exist, but the numbers in their equations, called coefficients, are hard to determine correctly.

So we work backwards. We record many real movements of a ship, each of the form “in state s, the ship took action a and moved to state s′”. Then we look for coefficients that make the simulator reproduce these records. This kind of backward problem is called system identification.

In system identification, we choose a set of coefficients x, run the simulator with them, and measure how far the simulated motion is from the real records. Call this difference f(x). The goal is to find the x that makes f(x) as small as possible, written min<sub>x</sub> f(x). There is no simple formula that gives f(x) from x: we can find out f(x) only by running the simulator. Problems like this are called black-box optimization.

Evolutionary computation is a family of methods for solving black-box optimization problems. Like reinforcement learning, it finds solutions by trial and error. It was first inspired by biological evolution and borrows ideas such as mutation, crossover and natural selection. Today these methods also have a mathematical foundation and have become more refined.

One kind of evolutionary computation, called evolution strategies, works like this:

  1. Generate several candidate solutions x at random from a normal (Gaussian) distribution.

  2. Run the simulation to compute f(x) for each candidate.

  3. Use the results to update the normal distribution (its mean vector and covariance matrix), so that the next candidates are likely to be better.

Repeating these steps moves the distribution toward the best solution and narrows it down there.

Evolutionary computation has two main strengths. It needs no knowledge of how f(x) is computed, so it is easy to use. It can also run many simulations in parallel, which matters because simulations are usually the slowest part. Finding a policy in reinforcement learning can also be seen as black-box optimization. So evolutionary computation is sometimes used instead of reinforcement learning, for tasks that standard reinforcement learning finds hard.

On the other hand, because it uses no knowledge of f(x), evolutionary computation tends to need many evaluations of f(x), and it offers only limited guarantees of finding the best solution. We are working on these problems too.

CMA-ES, a widely used evolution strategy, on a function with many local minima (the Rastrigin function). The white and gold dots are candidates (gold: the better half), and the ellipse shows the normal distribution. The distribution first spreads over many dips, follows the overall bowl shape, and then shrinks onto the best solution (★).

Another Example: Video Games

Here we explain evolutionary computation and reinforcement learning again, using two tasks in video games: creating game levels (stages or maps) and training AI players.

Creating video game levels with machine learning and evolutionary computation

A level in a video game is a stage or map that the player plays. A generated level must at least be playable: the game must not end the moment it starts, and it must be possible to clear. Beyond that, we want levels whose difficulty suits the player, and that the player finds fun

Playability can be checked by rules. But difficulty and fun can be judged only by having a person play the level, or by letting an existing AI player play it and looking at the result. So the link between a level and how good it is, is a black box, and finding the best level is a black-box optimization problem. This is where evolutionary computation helps: by repeatedly creating levels and evaluating them, it can find good ones.

Here we introduce our study on creating levels for Science Birds, a research version of the game Angry Birds [Tanabe et al., GECCO 2021].

First, we used a machine-learning technique called a sequential VAE (variational autoencoder) and a collection of existing levels to learn a function G. G takes a vector of real numbers x and turns it into a playable level L = G(x). This function is called a decoder. When x changes, the level L = G(x) changes, and how good the level is, U(L), is judged by an AI player or by a person.

Instead of changing the level L directly, evolutionary computation changes x. Because the decoder always produces playable levels, every candidate is playable, and we search for good levels among playable ones only.

Since x is a vector of real numbers, we used CMA-ES, a widely used evolutionary method for real-valued problems, to maximize f(x) = U(G(x)). CMA-ES draws several candidates x at once from a normal distribution. It then updates the distribution’s parameters (mean vector and covariance matrix) using the candidates judged to be good. The update rules are designed on statistical grounds. Repeating this moves the distribution toward the region where f(x) is high.

The video below shows an AI player playing a generated level. The level has many targets (pigs) and many blocks, yet it was designed so that one shot destroys all the targets and only the targets. To score a level, we let the AI player play it and counted how many targets and other blocks were left. Clearly, no formula gives this score f(x) directly from x. Finding good solutions even for such black-box functions is a strength of evolutionary computation.

angrybirds.mov

Training AI players with reinforcement learning

To design an AI player, we use reinforcement learning. In Science Birds, the AI player looks at the current state of the level (where the blocks are, how many birds are left) and decides its next action (the direction and strength of the shot). The rule that turns what it sees into what it does is its policy, and the policy is learned by trial and error.

The policy is learned from the reward, a score given to each pair of a state and an action. For example, if destroying as many targets as possible matters most, the reward can be the number of targets destroyed. If we also want an elegant policy that hits the targets without breaking other blocks, the reward can be the number of targets destroyed minus a small penalty for each other block destroyed.

In reinforcement learning, the agent takes an action, receives a reward, and adjusts its policy to get more reward. Nobody tells it the correct action in each state; it learns only from rewards. This is the defining feature of reinforcement learning.

To get a good policy, however, the reward must be designed well, and that is hard. This is one of the practical challenges of reinforcement learning. One way to tackle it is inverse reinforcement learning. It estimates the reward an expert seems to be following from records of the expert’s actions, and then uses that reward for learning.

There is one more important point when training game AI with reinforcement learning. A policy may play well only on the levels it saw during training, and poorly on new ones. This is called the generalization problem. To avoid it, the agent should experience many different levels during training, and automatic level generation helps here. Researchers also study ways to train efficiently on levels that the current policy finds difficult.

Report abuse
Report abuse