Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

534 lines (530 sloc) 37.592 kb
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html><head>
<title>ICFP 2008 Programming Contest
Task Description
</title>
<meta http-equiv="Pragma" content="no-cache">
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="GENERATOR" content="hevea 1.10">
<style type="text/css">
.li-itemize{margin:1ex 0ex;}
.li-enumerate{margin:1ex 0ex;}
.dd-description{margin:0ex 0ex 1ex 4ex;}
.dt-description{margin:0ex;}
.toc{list-style:none;}
.thefootnotes{text-align:left;margin:0ex;}
.dt-thefootnotes{margin:0em;}
.dd-thefootnotes{margin:0em 0em 0em 2em;}
.footnoterule{margin:1em auto 1em 0px;width:50%;}
.caption{padding-left:2ex; padding-right:2ex; margin-left:auto; margin-right:auto}
.title{margin:2ex auto;text-align:center}
.center{text-align:center;margin-left:auto;margin-right:auto;}
.flushleft{text-align:left;margin-left:0ex;margin-right:auto;}
.flushright{text-align:right;margin-left:auto;margin-right:0ex;}
DIV TABLE{margin-left:inherit;margin-right:inherit;}
PRE{text-align:left;margin-left:0ex;margin-right:auto;}
BLOCKQUOTE{margin-left:4ex;margin-right:4ex;text-align:left;}
TD P{margin:0px;}
.boxed{border:1px solid black}
.textboxed{border:1px solid black}
.vbar{border:none;width:2px;background-color:black;}
.hbar{border:none;height:2px;width:100%;background-color:black;}
.hfill{border:none;height:1px;width:200%;background-color:black;}
.vdisplay{border-collapse:separate;border-spacing:2px;width:auto; empty-cells:show; border:2px solid red;}
.vdcell{white-space:nowrap;padding:0px;width:auto; border:2px solid green;}
.display{border-collapse:separate;border-spacing:2px;width:auto; border:none;}
.dcell{white-space:nowrap;padding:0px;width:auto; border:none;}
.dcenter{margin:0ex auto;}
.vdcenter{border:solid #FF8000 2px; margin:0ex auto;}
.minipage{text-align:left; margin-left:0em; margin-right:auto;}
.marginpar{border:solid thin black; width:20%; text-align:left;}
.marginparleft{float:left; margin-left:0ex; margin-right:1ex;}
.marginparright{float:right; margin-left:1ex; margin-right:0ex;}
.theorem{text-align:left;margin:1ex auto 1ex 0ex;}
.part{margin:2ex auto;text-align:center}
DIV.center{}
.title{width: 100%}
.titlemain{border: 3px solid ; padding : 2px ; background-color: #acf ; border-color : #c99; text-align : center}
.titlerest{border: 3px solid ; padding : 2px ; background-color: #ccf ; border-color : #99c}
.section{border: 3px solid ; padding : 2px ; background-color: #cfc ; border-color : #9c9}
.subsection{border: 3px solid ; padding : 2px ; background-color: #ccf ; border-color : #99c}
</style>
</head>
<body>
<!--HEVEA command line is: hevea -exec xxdate.exe -fix -o html/task.html png.hva task.tex -->
<!--CUT DEF section 1 --><table class="title"><tbody><tr><td><h1 class="titlemain">ICFP 2008 Programming Contest<br>
Task Description </h1><h3 class="titlerest">(Version 1.5)</h3></td></tr>
</tbody></table><!--TOC section Overview-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc1">1</a>&nbsp;&nbsp;Overview</h2><!--SEC END --><p>
<a name="sec:overview"></a>
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 <i>cr&#232;me de la cr&#232;me</i> 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&#8217;s
winning entry will in fact be used to control the rover on NASA&#8217;s very
next mission to Mars!<sup><a name="text1" href="#note1">1</a></sup></p><p>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&#8217;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.</p><p>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.
</p><!--TOC section Mars rover behavior-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc2">2</a>&nbsp;&nbsp;Mars rover behavior</h2><!--SEC END --><p>
<a name="sec:behavior"></a>
</p><p>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).</p><blockquote class="figure"><div class="center"><hr size="2" width="80%"></div>
<div class="center">
<img src="2008-icfp_files/task001.png">
</div><div class="caption"><table cellpadding="0" cellspacing="6"><tbody><tr><td valign="top" align="left">Figure 1: A region of Mars</td></tr>
</tbody></table></div>
<a name="fig:sim"></a>
<div class="center"><hr size="2" width="80%"></div></blockquote><p>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 <i>xy</i>-plane
centered at the origin.
The <i>home base</i> &#8212; the rover&#8217;s intended destination &#8212; is a circle
(radius 5m) located at the origin.
The vehicle&#8217;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&#8217;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&nbsp;<a href="#sec:rover-char">3.1.1</a> below.</p><p>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&nbsp;<a href="#subsec:telemetry">3.1.2</a> 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.</p><p>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.</p><p>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, <i>etc</i>.
Martians are slightly smaller than the rover, having a radius of 0.4m.</p><p>An illustration of a typical Martian region appears in Figure&nbsp;<a href="#fig:sim">1</a>.
Boulders, craters and home base are marked <i>b</i>, <i>c</i> and <i>h</i> respectively.</p><!--TOC subsection Vision-->
<h3 class="subsection"><!--SEC ANCHOR --><a name="htoc3">2.1</a>&nbsp;&nbsp;Vision</h3><!--SEC END --><p>
<a name="subsec:vision"></a></p><p>The rover&#8217;s visual sensors cover an elliptical area that extends further in the direction that the
rover is facing.
Figure&nbsp;<a href="#fig:vision">2</a> depicts this region.
</p><blockquote class="figure"><div class="center"><hr size="2" width="80%"></div>
<div class="center">
<img src="2008-icfp_files/task002.png">
</div><div class="caption"><table cellpadding="0" cellspacing="6"><tbody><tr><td valign="top" align="left">Figure 2: A sketch of the vision model</td></tr>
</tbody></table></div>
<a name="fig:vision"></a>
<div class="center"><hr size="2" width="80%"></div></blockquote><p>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.</p><!--TOC subsection Speed-->
<h3 class="subsection"><!--SEC ANCHOR --><a name="htoc4">2.2</a>&nbsp;&nbsp;Speed</h3><!--SEC END --><p>
<a name="subsec:speed"></a>
The linear speed of the rover at time <i>t</i>&#8242; (<i>s</i><sub><i>t</i>&#8242;</sub>) is computed according to its speed at
its predecessor time <i>t</i> according to the following formula.
</p><table class="display dcenter"><tbody><tr valign="middle"><td class="dcell">&nbsp;&nbsp;<i>s</i><sub><i>t</i>&#8242;</sub>&nbsp;=&nbsp;max(<i>s</i><sub><i>t</i></sub>&nbsp;+&nbsp;(<i>t</i>&#8242;&nbsp;&#8722;&nbsp;<i>t</i>)&nbsp;<i>a</i>&nbsp;&#8722;&nbsp;<i>k</i>&nbsp;(<i>t</i>&#8242;&nbsp;&#8722;&nbsp;<i>t</i>)&nbsp;<i>s</i><sub><i>t</i></sub><sup>2</sup>,&nbsp;0)
</td></tr>
</tbody></table><p>The latter term is the simulated <i>drag</i> on the vehicle.
Note <i>a</i>, the <i>acceleration</i>, can be negative if
the rover is braking.
The rover&#8217;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.</p><!--TOC subsection Turning-->
<h3 class="subsection"><!--SEC ANCHOR --><a name="htoc5">2.3</a>&nbsp;&nbsp;Turning</h3><!--SEC END --><p>
The rover has two turning speeds &#8212; regular turns and hard turns &#8212; in both
directions.
When the rover receives a command to turn left, its turning state moves one &#8220;notch&#8221;
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&nbsp;<a href="#subsec:c2s">3.2</a> addresses the mechanics of steering messages in greater detail.</p><!--TOC section Network protocol-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc6">3</a>&nbsp;&nbsp;Network protocol</h2><!--SEC END --><p>
<a name="sec:protocol"></a>
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.</p><p>A <i>message</i> is a sequence of tokens delimited by the ASCII space
character (<tt>0x20</tt>) and terminated by a semicolon.
The tokens in a message represent quantities of various kinds and have the
following formats:
</p><ul class="itemize"><li class="li-itemize">
Distances, lengths, and locations (<i>x</i> and <i>y</i> coordinates) are given in
meters in fixed-point representation rounded to the nearest thousandth (millimeter).
</li><li class="li-itemize">Angles are given in degrees in fixed-point representation
rounded to the nearest tenth.
</li><li class="li-itemize">Angular velocities are given in degrees per second
in fixed-point representation rounded to the nearest tenth.
</li><li class="li-itemize">Speeds are given in meters per second in fixed-point representation
rounded to the nearest thousandth.
</li><li class="li-itemize">Durations are given in whole milliseconds (since the start of the simulation).
</li></ul><!--TOC subsection Messages from the server to the controller-->
<h3 class="subsection"><!--SEC ANCHOR --><a name="htoc7">3.1</a>&nbsp;&nbsp;Messages from the server to the controller</h3><!--SEC END --><p>
<a name="subsec:s2c"></a></p><p>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.</p><!--TOC subsubsection Initialization-->
<h4 class="subsubsection"><!--SEC ANCHOR --><a name="htoc8">3.1.1</a>&nbsp;&nbsp;Initialization</h4><!--SEC END --><p>
<a name="sec:rover-char"></a></p><p>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:
</p><div class="center">
<tt><b>I</b></tt> <i>dx</i> <i>dy</i> <i>time-limit</i> <i>min-sensor</i> <i>max-sensor</i> <i>max-speed</i> <i>max-turn</i> <i>max-hard-turn</i> <tt><b>;</b></tt>
</div><dl class="description"><dt class="dt-description">
<b><tt><b>I</b></tt></b></dt><dd class="dd-description"> is the message tag signifying initialization.
</dd><dt class="dt-description"><b><i>dx</i></b></dt><dd class="dd-description"> is the span of the map&#8217;s <i>x</i>-axis (meters).
A map with <i>dx</i> 100.000 extends from -50.000 to 50.000 on the <i>x</i>-axis.
</dd><dt class="dt-description"><b><i>dy</i></b></dt><dd class="dd-description"> is the span of the map&#8217;s <i>y</i>-axis (meters).
A map with <i>dy</i> 100.000 extends from -50.000 to 50.000 on the <i>y</i>-axis.
</dd><dt class="dt-description"><b><i>time-limit</i></b></dt><dd class="dd-description"> is the time limit for the map (milliseconds).
Map time limits are discussed in Section&nbsp;<a href="#sec:scoring">4</a> below.
</dd><dt class="dt-description"><b><i>min-sensor</i></b></dt><dd class="dd-description"> is the minimum range of the vehicle&#8217;s visual sensors (meters).
See the discussion of the vision model in Section&nbsp;<a href="#subsec:vision">2.1</a> above.
</dd><dt class="dt-description"><b><i>max-sensor</i></b></dt><dd class="dd-description"> is the maximum range of the vehicle&#8217;s visual sensors (meters).
See the discussion of the vision model in Section&nbsp;<a href="#subsec:vision">2.1</a> above.
</dd><dt class="dt-description"><b><i>max-speed</i></b></dt><dd class="dd-description"> is the maximum speed of the vehicle (meters per second).
</dd><dt class="dt-description"><b><i>max-turn</i></b></dt><dd class="dd-description"> is the maximum rotational speed when turning (degrees per second).
</dd><dt class="dt-description"><b><i>max-hard-turn</i></b></dt><dd class="dd-description"> is the maximum rotational speed when
turning hard (degrees per second).
</dd></dl><!--TOC subsubsection Telemetry stream-->
<h4 class="subsubsection"><!--SEC ANCHOR --><a name="htoc9">3.1.2</a>&nbsp;&nbsp;Telemetry stream</h4><!--SEC END --><p>
<a name="subsec:telemetry"></a></p><p>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&#8217;s current state (control-state, heading, velocity, <i>etc</i>.) as
well as information about the local map conditions (obstacles and
enemies).
</p><div class="center">
<tt><b>T</b></tt> <i>time-stamp</i> <i>vehicle-ctl</i> <i>vehicle-x</i> <i>vehicle-y</i> <i>vehicle-dir</i> <i>vehicle-speed</i> <i>objects</i> <tt><b>;</b></tt>
</div><p>where
</p><dl class="description"><dt class="dt-description">
<b><tt><b>T</b></tt></b></dt><dd class="dd-description"> is the message tag signifying telemetry data.
</dd><dt class="dt-description"><b><i>time-stamp</i></b></dt><dd class="dd-description"> is the number of milliseconds since the start of the run.
</dd><dt class="dt-description"><b><i>vehicle-ctl</i></b></dt><dd class="dd-description"> is the current state of the vehicle controls.
It is a two-character sequence with the first character specifying the acceleration
state (<tt><b>a</b></tt> for accelerating, <tt><b>b</b></tt> for braking, or
<tt><b>-</b></tt> for rolling, <i>i.e.</i>, moving at a constant speed) and the second
character specifying the turning
state (<tt><b>L</b></tt> for hard-left turn, <tt><b>l</b></tt> for left turn, <tt><b>-</b></tt>&nbsp;for
straight ahead, <tt><b>r</b></tt> for right turn, and <tt><b>R</b></tt> for hard-right turn).
Note that the rover will gradually slow down when rolling, because of drag.
</dd><dt class="dt-description"><b><i>vehicle-x</i></b></dt><dd class="dd-description"> is the <i>x</i>-coordinate of the vehicle&#8217;s current position.
</dd><dt class="dt-description"><b><i>vehicle-y</i></b></dt><dd class="dd-description"> is the <i>y</i>-coordinate of the vehicle&#8217;s current position.
</dd><dt class="dt-description"><b><i>vehicle-dir</i></b></dt><dd class="dd-description"> is the direction of the vehicle measured as a counterclockwise
angle from the <i>x</i>-axis.
</dd><dt class="dt-description"><b><i>vehicle-speed</i></b></dt><dd class="dd-description"> is the vehicle&#8217;s current speed (meters per second).
</dd><dt class="dt-description"><b><i>objects</i></b></dt><dd class="dd-description"> is a sequence of zero or more obstacles and/or enemies that
are visible to the vehicle.
An item is <i>visible</i> if it falls in the range of the vehicle&#8217;s visual sensors; recall
that range is part of the rover characteristics given in the server&#8217;s initial message.
Object messages have two different formats depending on the type of object.
If the object is a boulder, crater, or home base, the format is
<div class="center">
<i>object-kind</i> <i>object-x</i> <i>object-y</i> <i>object-r</i>
</div>where
<dl class="description"><dt class="dt-description">
<b><i>object-kind</i></b></dt><dd class="dd-description"> is one of <tt><b>b</b></tt> (for a boulder), <tt><b>c</b></tt> (for a crater), or <tt><b>h</b></tt> (for home base).
</dd><dt class="dt-description"><b><i>object-x</i></b></dt><dd class="dd-description"> is the <i>x</i>-coordinate of the object&#8217;s center.
</dd><dt class="dt-description"><b><i>object-y</i></b></dt><dd class="dd-description"> is the <i>y</i>-coordinate of the object&#8217;s center.
</dd><dt class="dt-description"><b><i>object-r</i></b></dt><dd class="dd-description"> is the radius of the object.
</dd></dl>If the object is a Martian, the description has the format
<div class="center">
<tt><b>m</b></tt> <i>enemy-x</i> <i>enemy-y</i> <i>enemy-dir</i> <i>enemy-speed</i>
</div></dd></dl><p>Here is an example telemetry message.
Note that we have split this message over multiple lines to improve readability &#8212;
the actual message would not contain any newline characters.
</p><blockquote><font color="blue"><tt>
T 3450 aL -234.040 811.100 47.5 8.450<br>
b -220.000 750.000 12.000<br>
m -240.000 812.000 90.0 9.100 ;
</tt></font></blockquote><p>This message describes the vehicle&#8217;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 (&#8722;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.</p><!--TOC subsubsection Adverse events-->
<h4 class="subsubsection"><!--SEC ANCHOR --><a name="htoc10">3.1.3</a>&nbsp;&nbsp;Adverse events</h4><!--SEC END --><p>
<a name="subsec:adverse"></a></p><p>There are also messages to signal unhappy occurrences.
These messages have the format:
</p><div class="center">
<i>message-tag</i> <i>time-stamp</i> <tt><b>;</b></tt>
</div><p>where the <i>message-tag</i> is one of
</p><dl class="description"><dt class="dt-description">
<b><tt><b>B</b></tt></b></dt><dd class="dd-description"> for a crash against a boulder or the map edge.
When the rover crashes into a boulder, it bounces off and loses speed.
Each crash message is immediately followed by a telemetry message so that the
controller can update its state.
</dd><dt class="dt-description"><b><tt><b>C</b></tt></b></dt><dd class="dd-description"> if the vehicle fell into a crater.
Falling into a crater destroys the rover and ends the run.
</dd><dt class="dt-description"><b><tt><b>K</b></tt></b></dt><dd class="dd-description"> if the vehicle was killed by a Martian, which
ends the run.
</dd></dl><!--TOC subsubsection Success message-->
<h4 class="subsubsection"><!--SEC ANCHOR --><a name="htoc11">3.1.4</a>&nbsp;&nbsp;Success message</h4><!--SEC END --><p>
<a name="subsec:success"></a></p><p>The server sends the message &#8220;<tt><b>S</b></tt> <i>t</i> <tt><b>;</b></tt>&#8221; when the vehicle reaches
home base safely.
The current run is terminated on success.</p><!--TOC subsubsection End-of-run message-->
<h4 class="subsubsection"><!--SEC ANCHOR --><a name="htoc12">3.1.5</a>&nbsp;&nbsp;End-of-run message</h4><!--SEC END --><p>
<a name="subsec:end-run"></a></p><p>At the end of a run, the server sends the message &#8220;<tt><b>E</b></tt> <i>t</i> <i>s</i> <tt><b>;</b></tt>,&#8221;
where <i>t</i> is the time since the beginning
of the run, and <i>s</i> is the score (<i>i.e.</i>, the run time plus any penalties).
Note that each run will end with exactly one of the following sequences of
server messages:
</p><ul class="itemize"><li class="li-itemize">
<tt><b>C</b></tt> <i>t</i> <tt><b>;</b></tt>, then <tt><b>E</b></tt> <i>t</i> <i>s</i> <tt><b>;</b></tt>
</li><li class="li-itemize"><tt><b>K</b></tt> <i>t</i> <tt><b>;</b></tt>, then <tt><b>E</b></tt> <i>t</i> <i>s</i> <tt><b>;</b></tt>
</li><li class="li-itemize"><tt><b>S</b></tt> <i>t</i> <tt><b>;</b></tt>, then <tt><b>E</b></tt> <i>t</i> <i>s</i> <tt><b>;</b></tt>
</li><li class="li-itemize"><tt><b>E</b></tt> <i>t</i> <i>s</i> <tt><b>;</b></tt> preceded by none of
<tt><b>C</b></tt>, <tt><b>K</b></tt>, or <tt><b>S</b></tt>, indicating that the
time limit has been reached
</li></ul><p>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&nbsp;<a href="#sec:rover-char">3.1.1</a> is only
sent once per trial.
Each run of the trial uses the same map, although the rover&#8217;s initial position and the
number and location of Martians can vary from run to run.</p><!--TOC subsection Messages from the controller to the server-->
<h3 class="subsection"><!--SEC ANCHOR --><a name="htoc13">3.2</a>&nbsp;&nbsp;Messages from the controller to the server</h3><!--SEC END --><p>
<a name="subsec:c2s"></a>
The rover behavior is controlled by a pair of state machines (Figure&nbsp;<a href="#fig:control">3</a>),
which, in turn, are controlled by commands sent by the controller.
</p><blockquote class="figure"><div class="center"><hr size="2" width="80%"></div>
<div class="center">
<img src="2008-icfp_files/task003.png">
</div><div class="center">
<img src="2008-icfp_files/task004.png">
</div><div class="caption"><table cellpadding="0" cellspacing="6"><tbody><tr><td valign="top" align="left">Figure 3: Vehicle-control state machines</td></tr>
</tbody></table></div>
<a name="fig:control"></a>
<div class="center"><hr size="2" width="80%"></div></blockquote><p>Each command consists of an optional acceleration (<tt><b>a</b></tt>) or braking
(<tt><b>b</b></tt>) command, followed by an optional turning command (<tt><b>l</b></tt> for left
and <tt><b>r</b></tt> for right), and followed by a semicolon (<tt><b>;</b></tt>).
Thus, the grammar of controller-to-server messages is
</p><table class="display dcenter"><tbody><tr valign="middle"><td class="dcell"><i><i>Message</i></i>&nbsp;::=
<tt><b>;</b></tt>&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>a;</b></tt>&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>b;</b></tt>&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>l;</b></tt>&nbsp;&nbsp;&nbsp;|&nbsp;
<tt><b>r;</b></tt>&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>al;</b></tt>&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>ar;</b></tt>&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>bl;</b></tt>&nbsp;&nbsp;|&nbsp;&nbsp;
<tt><b>br;</b></tt>
</td></tr>
</tbody></table><p>
<em>No other characters (including whitespace) should be sent over the command stream!</em></p><p>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.
</p><!--TOC section Contest organization and scoring-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc14">4</a>&nbsp;&nbsp;Contest organization and scoring</h2><!--SEC END --><p>
<a name="sec:scoring"></a>
</p><p>The contest is run as a series of trials of varying difficulty.
A <i>trial</i> consists of five <i>run</i>s on the same map.
Each map has an associated <i>time limit</i> of some number of milliseconds.
A <i>limit-</i><i><i>n</i></i><i> map</i> has an upper limit of <i>n</i> milliseconds.</p><p>The <i>score</i> for a run is the amount of time it takes to complete the run or be destroyed, plus any penalties.
</p><ul class="itemize"><li class="li-itemize">
If a rover reaches home base on a given limit-<i>n</i> map in some <i>t</i> &#8804; <i>n</i> number of milliseconds,
the run score is <i>t</i>.
</li><li class="li-itemize">If the rover fails to reach home base on a given limit-<i>n</i> map, the run score is given
by the equation 2 <i>n</i> &#8722; <i>t</i> + <i>p</i>, where <i>t</i> is the elapsed time, and <i>p</i> is the penalty
as follows:
<ul class="itemize"><li class="li-itemize">
100 if the time limit has been exceeded,
</li><li class="li-itemize">600 if the rover was destroyed by a Martian, or
</li><li class="li-itemize">1000 if the rover fell into a crater.
</li></ul>Note that <i>t</i> is at most <i>n</i> in this formula, since the run is halted when
<i>t</i> exceeds <i>n</i>.
Therefore (2<i>n</i>&#8722;<i>t</i>) will always be between <i>n</i> and 2<i>n</i> inclusive.
</li></ul><p>As in ski racing, lower scores are better.</p><p>The <i>trial score</i> is the sum of the three lowest scores in the trial.</p><p>The winner of the contest will be determined by a series of <i>heats</i>.
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.</p><p>Programs that core dump will be disqualified.</p><p>Programs that attempt to subvert the host or server, or that generate
illegal messages will be disqualified.
</p><!--TOC section Submission instructions-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc15">5</a>&nbsp;&nbsp;Submission instructions</h2><!--SEC END --><p>
<a name="sec:submission"></a>
</p><p>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
</p><div class="center">
<tt>http://icfpcontest.org/live-cd.html</tt>
</div><p>Contest entries must consist of a single gzipped tarball named <tt>icfp08.tgz</tt>.
You submit your entry using the web form at
</p><div class="center">
<tt>http://icfpcontest.org/submit.php</tt>
</div><p>The first time that you submit your entry, you will be given a unique identifier
that you must use for any resubmissions.</p><p>After unbundling, an optional installation script is run.
The resulting directory tree must include all of the following:
</p><ul class="itemize"><li class="li-itemize">
at the top level, a directory <tt>icfp08</tt>.
</li><li class="li-itemize">a file <tt>team</tt>, inside <tt>icfp08</tt>,
which consists of a single line of text, the team name.
Your team name must be no longer that 63 ASCII characters.
</li><li class="li-itemize">a file <tt>contact</tt>, inside <tt>icfp08</tt>,
which consists of the team member names and email addresses in
the following format:
<blockquote><font color="blue"><tt>
</tt></font><font color="blue"><tt>John Doe &lt;johndoe@gmail.com&gt;</tt></font><font color="blue"><tt>
</tt></font></blockquote>Name/address pairs must appear one per line.
</li><li class="li-itemize">a directory <tt>src</tt> containing all the source code for your contest entry.
Inside <tt>src</tt>, your code may be organized however you like.
Please note: you <em>must</em> provide source code, even if you use an
unsupported language or compiler to develop your entry.
Submissions with no accompanying source code will be disqualified.
</li><li class="li-itemize">a file <tt>README</tt>, inside <tt>src</tt>, to assist the judges&#8217; understanding of your code.
If you used tools not among those provided on the LiveCD, specify the language and
compiler your team used in this file and describe how to obtain and install the tools.
</li><li class="li-itemize">a directory <tt>bin</tt>, inside <tt>icfp08</tt>, containing whatever executables and scripts support the
running of your controller.
</li><li class="li-itemize">an executable file <tt>run</tt>, inside <tt>bin</tt>, which runs your client.
It may be an executable, or it may
be a shell script that manages running your client. It must take
two command-line arguments, the server&#8217;s hostname and the port number, in that order.
That is, the judges must be able to execute your client with
<blockquote><font color="blue"><tt>
</tt></font><font color="blue"><tt>bin/run</tt></font><font color="blue"><tt> </tt></font><font color="blue"><tt><i>hostname</i></tt></font><font color="blue"><tt> </tt></font><font color="blue"><tt><i>port</i></tt></font><font color="blue"><tt>
</tt></font></blockquote>
from inside the <tt>icfp08</tt> directory.
</li></ul><p>
Your tarball may include other files as well, including
code for general-purpose third-party libraries, with
your submission as long as your <tt>README</tt> enumerates those libraries.
Teams may not use code written by other teams working on the contest as a &#8220;library.&#8221;
Only generic libraries, <i>e.g.</i>, one that provides matrix operations, may be used.
Teams who use libraries as a means of sharing code with one another will be disqualified.</p><p>The structure of a contest entry is illustrated in Figure&nbsp;<a href="#fig:submit">4</a>.
</p><blockquote class="figure"><div class="center"><hr size="2" width="80%"></div>
<div class="center">
<img src="2008-icfp_files/task005.png">
</div><div class="caption"><table cellpadding="0" cellspacing="6"><tbody><tr><td valign="top" align="left">Figure 4: Submission directory structure</td></tr>
</tbody></table></div>
<a name="fig:submit"></a>
<div class="center"><hr size="2" width="80%"></div></blockquote><p>In addition, your archive may contain an optional installation script <tt>install</tt> in the <tt>bin</tt> directory.
If this script is present, it will be executed using the command
</p><blockquote><font color="blue"><tt>
</tt></font><font color="blue"><tt>bin/install</tt></font><font color="blue"><tt>
</tt></font></blockquote><p>
from inside the <tt>icfp08</tt> directory.
The <tt>PWD</tt> shell variable and <tt>pwd</tt> command can be used to determine the path
to the <tt>icfp08</tt> directory (and thus to your scripts, <i>etc</i>.).
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 <tt>icfp08</tt>
directory.</p><p>The process of running your client for a given trial will involve the following steps:
</p><blockquote><font color="blue"><tt>
tar -xzf icfp08.tgz<br>
cd icfp08<br>
if test -r bin/install ; then<br>
chmod +x bin/install<br>
bin/install<br>
fi<br>
chmod +x bin/run<br>
bin/run </tt></font><font color="blue"><tt><i>hostname</i></tt></font><font color="blue"><tt> </tt></font><font color="blue"><tt><i>port</i></tt></font><font color="blue"><tt>
</tt></font></blockquote><p>These commands will be run as user <tt>knoppix</tt> (<em>not</em> <tt>root</tt>) in
a temporary directory.</p><p>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.</p><!--TOC section How to test your program-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc16">6</a>&nbsp;&nbsp;How to test your program</h2><!--SEC END --><p>
<a name="sec:howto"></a>
</p><p>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>i.e.</i>, more obstacles) than the samples and the Martians therein
may be faster and smarter.
Prepare for the worst!</p><p>The sample simulator and maps are available for download from
</p><div class="center">
<tt>http://smlnj.org/icfp08-contest/simulator.html</tt>
</div><p>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.</p><!--TOC section Implementation hints-->
<h2 class="section"><!--SEC ANCHOR --><a name="htoc17">7</a>&nbsp;&nbsp;Implementation hints</h2><!--SEC END --><p>
<a name="sec:impl"></a>
Because the controller program is sensitive to network
latency, you should disable Nagle&#8217;s algorithm for
the socket.
You can do this using the <tt>setsockopt</tt> system call with
the <tt>TCP_NODELAY</tt> option.</p><p>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.
</p><p>Good luck!</p><!--TOC section Document history-->
<h2 class="section"><!--SEC ANCHOR -->Document history</h2><!--SEC END --><dl class="description"><dt class="dt-description">
<b>Version 1.0</b></dt><dd class="dd-description"> Initial version.
</dd><dt class="dt-description"><b>Version 1.1</b></dt><dd class="dd-description"> Changed installation behavior to make the
<tt>install</tt> and <tt>run</tt> scripts executable before running it.
</dd><dt class="dt-description"><b>Version 1.2</b></dt><dd class="dd-description"> Correction in Section&nbsp;<a href="#sec:protocol">3</a>: &#8220;IP address&#8221;
changed to &#8220;hostname.&#8221;
</dd><dt class="dt-description"><b>Version 1.3</b></dt><dd class="dd-description"> Fixed small text typo.
Clarified the fact that drag is unknown.
Fixed installation behavior description.
Clarified falling and crashing behavior.
</dd><dt class="dt-description"><b>Version 1.4</b></dt><dd class="dd-description">
Removed erroneous definition of a run from Section&nbsp;<a href="#sec:scoring">4</a>.
Stated that generic third-party libraries <em>may</em> be submitted in
Section&nbsp;<a href="#sec:submission">5</a>.
</dd><dt class="dt-description"><b>Version 1.5</b></dt><dd class="dd-description">
Stated that angular velocity (degrees per second, as in
<i>max-turn</i> and <i>max-hard-turn</i>) are given
to the nearest tenth of a degree.
</dd></dl><!--BEGIN NOTES document-->
<hr class="footnoterule"><dl class="thefootnotes"><dt class="dt-thefootnotes">
<a name="note1" href="#text1">1</a></dt><dd class="dd-thefootnotes">
Subject to budget constraints.
</dd></dl>
<!--END NOTES-->
<!--CUT END -->
<!--HTMLFOOT-->
<!--ENDHTML-->
<!--FOOTER-->
<hr size="2"><blockquote class="quote"><em>This document was translated from L<sup>A</sup>T<sub>E</sub>X by
</em><a href="http://hevea.inria.fr/index.html"><em>H</em><em><font size="2"><sup>E</sup></font></em><em>V</em><em><font size="2"><sup>E</sup></font></em><em>A</em></a><em>.</em></blockquote>
</body></html>
Jump to Line
Something went wrong with that request. Please try again.