FUZZ-IEEE 2007 Simulated Car Racing Competition (competition closed - results summary; also see CEC 2007 Competitions) Simon M. Lucas

Contents Introduction Simulation Software Interface Source Code Sample Fuzzy Controller Race Server Important Dates and Rules

Introduction

Congratulations to winning team:
Ho Duc Thang, Phil Birkin and Jon Garibaldi, from Nottingham University, UK
(see results summary)

Car racing is a fascinating sport that attracts enormous public interest and participation, from Formula One and IndyCar, rallying, model car racing, and of course one of the most important and long lived computer game genres.

This competition presents a very simple form of car racing: the challenge is to find the best fuzzy controller for this.  The aim is to race a simulated car to a series of waypoints all within a unit square on a two-dimensional plane.  Even given this simple definition leads to a challenging problem for machine learning and computational intelligence techniques.  A simpler version of this problem was the immensely challenging optimisation problem, Physical Travelling Salesman Problem (PTSP).  The PTSP essentially used a holonomic car (one able to move freely in any direction).  However, there are several twists to the current problem that add even more interest:

• At any point in time, each car can only see the next three waypoints.  These must be visited in order by the racing cars, but once one a car has reached a waypoint, then the opponent car can miss this and go directly for the next waypoint.
• Waypoints are generated randomly: every track is different, and tests general driving ability rather than how well specialised a driver is to a particular track
• The car competes against an opponent car.
• Only the first car to reach each waypoint score a point for that waypoint. 
• The winning car for each race is the one with the most points after 500 time steps have elapsed.
• Each controller competes against each other in a round-robin league; the overall winner is the one that finishes top of the league.
• Cars do not collide with each other.  This allows for an entirely symmetric race - each controller is fed identical information, and the cars start in identical positions.
• The car has imperfect sensors and actuators.  At each time step, the driver gets a noisy estimate of the car's position and velocity.  Gaussian noise is added to the observed position and velocity.  Furthermore, Gaussian noise is also added to the actual position of the car when the update is calculated.  For exact details see the update() and noisyCopy() methods of the Car class.

Everyone in the fuzzy control community is familiar with the fuzzy truck backer-up.  This competition allows you to apply similar ideas, but in a competitive environment where you race against other controllers.  Also, the behaviours exhibited are more complex, and require control of speed as well as steering angle.

Simulation

The problem is specified on a 2d plane.  The simulation consists of the following objects:

• A Track (generates the waypoints on demand)
• Two Car objects, one for the you, one for your opponent
• Two Car Controllers (again, for you and your opponent)
• An Evaluation Engine.  Runs the simulation, updating the car states, detecting when waypoints have been hit, keeps the scores for each car.

Note that if there are any discrepancies between the above description and the Java code, the Java code is the reference.

Software Interface

The interface for a controller is as follows:

public interface Controller {
    public Action getAction(WayPoint[] track, ICar you, ICar oppo);
}

At each time step, the simulator will call the getAction() method of your controller.

It passes the track (an array containing the next three waypoints), a reference to your car (you) and a reference to the opponent's car (oppo) as parameters.  It returns an Action object.  An Action specifies the desired acceleration and steering angle.  Let's look in more detail at the definitions of these, first the WayPoint class.  Note that the definitions listed below are incomplete, and in some cases the snippets you do see have been slightly simplified from the real code.  The full source is available in the zip file (see download section below).

public class WayPoint {
    public Vector2d p;
    public double r;
    // ...
}

A WayPoint is a defined by it's x,y position, and it's radius.  Within this simulation, there are many things defined by their x,y values, so it is convenient to wrap these in a class called Vector2d:

public class Vector2d {
    public double x, y;
    // ... contains methods for adding, multiplying, rotating, and distance calculations
}

Next, the ICar interface.  Note that an interface is used to separate the specification of this from the implementation.  This way, it is simple to plug and play alternative car implementations with potentially very different underlying physical models:

public interface ICar {
    public Vector2d s();        // position of car
    public Vector2d v();        // velocity of car
    public Vector2d heading();  // which way the car is pointing
    public double rad();        // radius of car, used for collision detection
    public ICar update(int action);          // updates the state of the car given this action
    public ICar copyAndUpdate(int action);   // returns an updated copy of this car
    public void reset();                     // returns car to its initial state
}

The Action class is defined as follows:

public class Action {
    public double acc;
    public double steer;
    // constructor omitted
}

In other words, Action is a wrapper that combines a selected acceleration with a selected steering angle.

Source Code

The Java source code is available here in a zip file. 

The code is split into many classes, and it is recommended that you view the source files using a good IDE, such as Eclipse or NetBeans (both free).

After extracting the zip file, you can run this by typing:

java games.twod.Evaluator

See the main method of that class for the options used.  The heuristic controller contains two parameters that can be set: velocity penalty, and opponent attraction.  The velocity penalty stops the car from going too fast.  The opponent attraction is just there for fun :).

The code is supplied with a simple heuristic state-based controller.

This works by considering a set of next states given a set of possible actions applied to the current state, and selecting the action that leads to the best state.

A run of two of these controllers is shown for the first 50 time steps below.  A car is shown as a circle, with a line to indicate its current heading.  The green car below has a faster more aggressive driving strategy, which has led to some success.

The title bar shows the score for the green car followed by the score for the red car.

Note that a Key Board controller is also included in the distribution.  This enables you to race as a human against the computer-based controllers.

The complete code for the heuristic controller is shown below:

public class HeuristicController implements Controller, Constants {

  public double velocityPenalty = 5.0;
  public double oppoAttraction = 0;

  public Action action(WayPoint[] track, ICar hc, ICar oppo) {
    // try each possible action
    // and take the one with the lowest penalty score
    Action bestAction = null;
    double best = Double.MAX_VALUE;
    for (Action ac : a) {
      ICar next = hc.copyAndUpdate(ac);
      double score = score(track, next, oppo);
      if (score < best) {
        best = score;
        bestAction = ac;
      }
    }
    return bestAction;
  }

  public double score(WayPoint[] track, ICar hc, ICar oppo) {
    // this one ignores oppo
    double dist = track[0].p.dist(hc.s());
    double oppoDist = hc.s().dist(oppo.s());
    return dist + velocityPenalty * hc.v().mag() * hc.v().mag() +
           oppoAttraction * oppoDist;
  }
}

Sample Fuzzy Controller

We may be able to provide a complete fuzzy controller for this problem later.

For now, the zip file here contains a fuzzy controller to control the steering angle (but not the acceleration).

Many thanks to Christian Wagner, PhD student at the University of Essex, for providing this.

Race Server

The details of this are currently being worked out.  The server will allow you to play your controller on-line against other controllers.

Important Dates

Competition entry deadline: Monday July 9th, 2007

Competition session: during FUZZ-IEEE July 23 - 26 2007

All competitions entries must involve fuzzy systems.  Hybrid fuzzy methods are welcome.

Winner (leading entrant who is registered for the conference) to be presented with certificate and cash prize (USD250) at the conference banquet.

All competition entries should be accompanied by a brief description of the method used (e.g. 3 pages in PDF format)

Please email Simon Lucas (sml@essex.ac.uk) if you intend entering the competition.

Note: in order to run, this competition requires at least five independent entrants.