ICFP 2008 Programming Contest
Recent breakthroughs in higher-order, statically-typed, metaspatial communication will enable data to be transferred between Mars and Earth almost instantaneously. As such, NASA is seeking examples of real-time control software to operate its latest model Martian rovers from control centers on Earth. Since it is well known that the ICFP contest attracts the crème de la crème of programmers from around the world, NASA has decided to use the current contest as a means of gathering software prototypes for their new control system. We are pleased to announce that this year’s winning entry will in fact be used to control the rover on NASA’s very next mission to Mars!1
Your control software will communicate with the rover over a network socket. Its object is to guide the rover safely from a given starting location to its home base. The controller’s primary function is to avoid the boulders and craters that litter the Martian surface. As an added nuisance, the local inhabitants, who are decidedly hostile, will immediately destroy any rover they can get their fourteen sticky fingers on. Note that Martians, like dogs, vary in intelligence.
Control software prototypes will be evaluated according to their performance in a series of trials, the details of which are given below. Each trial consists of five runs on a given region of Mars. As a means of preparing for these trials, this document and its accompanying software provide sufficient details and infrastructure for the development of prototype candidates. Good luck, and may yours be the winning entry, to be used on Mars itself.
The rover is a circular vehicle of radius 0.5m, which your controller must guide across the Martian terrain. To do so, your controller must establish a connection to the rover over a TCP/IP socket. This socket it used for all communication to and from the rover. While metaspatial communication is very fast, there is some latency in the connection (on the order of 75 microseconds).
Once the connection is established, the controller will be sent an initial message about the dimensions of the world and the physical characteristics of the vehicle. The world is modeled as a rectangular segment of the xy-plane centered at the origin. The home base — the rover’s intended destination — is a circle (radius 5m) located at the origin. The vehicle’s characteristics include its maximum speed, its maximum rotational speed when turning, and a few other facts. NASA is testing various different models of rovers, which have varying performance. They are also testing different regions of Mars, with a wide range of characteristics. For a given trial, the rover’s performance and the map will be fixed, but these will vary from trial to trial. Complete information on the initial message is furnished in Section 3.1.1 below.
About one second after the initial message is sent, the first run starts and the server begins sending a stream of vehicle telemetry data to the controller. Telemetry data consists of location, speed, and information about the local terrain (see Section 3.1.2 for full details). At any time after the telemetry data has started streaming to the controller, the controller may issue commands back to the server to direct the vehicle towards home base.
The rover must avoid three kinds of perils on its way home. If the rover hits a boulder, or the edge of the map, it bounces off and loses speed. Hitting a boulder happens if the distance between the center of the boulder and the center of the rover is less than the sum of their radii. If the center of the rover enters a crater, it falls in and explodes. If a vehicle is caught by a Martian, it is destroyed and its remains are sacrificed to the Gods of Barsoom, of whom it is best not to speak further.
Martians, while hostile, possess no special physical abilities; that is, they cannot drive through craters, pass through objects, or escape the boundary of the map. The physics of Martian movement is the same as for the rover, although they may be faster or slower, etc. Martians are slightly smaller than the rover, having a radius of 0.4m.
An illustration of a typical Martian region appears in Figure 1. Boulders, craters and home base are marked b, c and h respectively.
The rover’s visual sensors cover an elliptical area that extends further in the direction that the rover is facing. Figure 2 depicts this region.
The rover is oriented toward the right in this illustration. Implicitly, there is an ellipse defined by min and max, with the rover always positioned at one of the foci. The rover can see everything within this ellipse, with the exception of those objects that are occluded by boulders. In the figure, the rightmost boulder is not visible to the rover because of the larger boulder blocking it. The lowermost boulder, on the other hand, is visible, since craters do not occlude vision.
The linear speed of the rover at time t′ (st′) is computed according to its speed at its predecessor time t according to the following formula.
|st′ = max(st + (t′ − t) a − k (t′ − t) st2, 0)|
The latter term is the simulated drag on the vehicle. Note a, the acceleration, can be negative if the rover is braking. The rover’s acceleration and braking rates are not known, although they can be determined by experiment. The effect of drag is to limit the maximum speed of the rover. The maximum speed is known (it is communicated as part of the initial message), but the drag coefficient is not known.
The rover has two turning speeds — regular turns and hard turns — in both directions. When the rover receives a command to turn left, its turning state moves one “notch” in the leftward direction; likewise for right. Note that while the turn rate and hard-turn rates are known, the rotational acceleration of the vehicle is finite and thus it will take some time change from one turning mode to another. Section 3.2 addresses the mechanics of steering messages in greater detail.
Communication between the server and controller will be over a TCP/IP socket using plain-text messages encoded in ASCII. The controller will be given a server hostname and port number as command-line arguments at the beginning of each trial. The controller should establish a client-side TCP/IP connection to the server; this socket will be used by the controller to send commands to the vehicle and by the server to send telemetry data to the controller.
A message is a sequence of tokens delimited by the ASCII space character (0x20) and terminated by a semicolon. The tokens in a message represent quantities of various kinds and have the following formats:
There are a variety of messages that the rover sends to the controller. Each message begins with a single character that denotes the message kind.
The exact characteristics of the vehicle are unspecified and may differ between trials, but information about the vehicle will be given at the beginning of each trail. Once the connection to the server is established, the controller will receive an initial message with the following format:
During a run, the server sends a steady stream of telemetry data to the vehicle controller (roughly one message every 100 milliseconds). This data includes information about the vehicle’s current state (control-state, heading, velocity, etc.) as well as information about the local map conditions (obstacles and enemies).
Here is an example telemetry message. Note that we have split this message over multiple lines to improve readability — the actual message would not contain any newline characters.
T 3450 aL -234.040 811.100 47.5 8.450
b -220.000 750.000 12.000
m -240.000 812.000 90.0 9.100 ;
This message describes the vehicle’s state at 3.45 seconds after the start of the run. It is currently accelerating and turning hard to the left. Its position is (−234.040, 811.100), its direction is 47.5 degrees (roughly NE), its velocity is 8.450 meters per second, and it sees one boulder and one Martian.
There are also messages to signal unhappy occurrences. These messages have the format:
where the message-tag is one of
The server sends the message “S t ;” when the vehicle reaches home base safely. The current run is terminated on success.
At the end of a run, the server sends the message “E t s ;,” where t is the time since the beginning of the run, and s is the score (i.e., the run time plus any penalties). Note that each run will end with exactly one of the following sequences of server messages:
Once a run has terminated, there will be a pause of at least one second before the start of the next run. Note that the controller should not exit at the end of the run, but instead should prepare for another run. Also note that the initialization message described in Section 3.1.1 is only sent once per trial. Each run of the trial uses the same map, although the rover’s initial position and the number and location of Martians can vary from run to run.
The rover behavior is controlled by a pair of state machines (Figure 3), which, in turn, are controlled by commands sent by the controller.
Each command consists of an optional acceleration (a) or braking (b) command, followed by an optional turning command (l for left and r for right), and followed by a semicolon (;). Thus, the grammar of controller-to-server messages is
|Message ::= ; | a; | b; | l; | r; | al; | ar; | bl; | br;|
No other characters (including whitespace) should be sent over the command stream!
While communication with the rover is fast, there may be some latency (less than 20 milliseconds) in processing the commands. The controller may send messages as often as it likes, although flooding the network can negatively affect performance. We recommend only sending messages in response to telemetry data, although you may need a sequence of messages to reach the desired control state.
The contest is run as a series of trials of varying difficulty. A trial consists of five runs on the same map. Each map has an associated time limit of some number of milliseconds. A limit-n map has an upper limit of n milliseconds.
The score for a run is the amount of time it takes to complete the run or be destroyed, plus any penalties.
As in ski racing, lower scores are better.
The trial score is the sum of the three lowest scores in the trial.
The winner of the contest will be determined by a series of heats. A heat consists of all remaining competitors being subjected to the same trial. After each heat, the competitors are ranked by their trial score and some fraction of the better competitors will advance to the next heat, while the remaining competitors will be eliminated. Heats will continue until there is a single winner remaining. From one heat to the next, the given trial may differ arbitrarily.
Programs that core dump will be disqualified.
Programs that attempt to subvert the host or server, or that generate illegal messages will be disqualified.
Your submission must run in the Linux environment provided by the LiveCD provided on the contest web site. The LiveCD includes many popular language implementations, but if your favorite language is not included, you may still submit a solution. The only restriction is that it must run in the LiveCD environment. Details about the LiveCD can be found at
Contest entries must consist of a single gzipped tarball named icfp08.tgz. You submit your entry using the web form at
The first time that you submit your entry, you will be given a unique identifier that you must use for any resubmissions.
After unbundling, an optional installation script is run. The resulting directory tree must include all of the following:
John Doe <firstname.lastname@example.org>Name/address pairs must appear one per line.
bin/run hostname portfrom inside the icfp08 directory.
Your tarball may include other files as well, including code for general-purpose third-party libraries, with your submission as long as your README enumerates those libraries. Teams may not use code written by other teams working on the contest as a “library.” Only generic libraries, e.g., one that provides matrix operations, may be used. Teams who use libraries as a means of sharing code with one another will be disqualified.
The structure of a contest entry is illustrated in Figure 4.
In addition, your archive may contain an optional installation script install in the bin directory. If this script is present, it will be executed using the command
from inside the icfp08 directory. The PWD shell variable and pwd command can be used to determine the path to the icfp08 directory (and thus to your scripts, etc.). The layout of your submission is not checked until after this program is run, so it may be used to generate or modify the files in your submission, but it should not attempt to copy files outside the icfp08 directory.
The process of running your client for a given trial will involve the following steps:
tar -xzf icfp08.tgz
if test -r bin/install ; then
chmod +x bin/install
chmod +x bin/run
bin/run hostname port
These commands will be run as user knoppix (not root) in a temporary directory.
The specifications above must be matched exactly, since contest entries will be processed by scripts depending on the exact structure presented here. Failure to meet the specifications is grounds for disqualification.
NASA is providing a Martian simulator and sample maps for contestants to test their code on while developing their contest entries. Note that while this simulator is a physically accurate simulation of the Martian environment, the vehicle characteristics may vary in the actual trials. Furthermore, the environment used to test your controller may be harsher (i.e., more obstacles) than the samples and the Martians therein may be faster and smarter. Prepare for the worst!
The sample simulator and maps are available for download from
To run the server, you must supply it with the name of a map file. Details on the map file format appear on the web site.
Because the controller program is sensitive to network latency, you should disable Nagle’s algorithm for the socket. You can do this using the setsockopt system call with the TCP_NODELAY option.
Implementations may use information gathered in early runs of a trial to improve their score in later runs. Note that since a single execution of the controller program is used for the whole trial, you do not need to use disk storage to communicate information between runs. No information can be communicated between trials.
This document was translated from LATEX by HEVEA.