Rules

The Challenge

You work for NASA, on the project team that's designing the successor to the Mars Pathfinder mission. This is the first of a series of missions designed to complete a detailed survey of the planet's surface. Your team will be landing a set of five robotic surface rovers to survey the a region of the planet's surface. Your job is write an algorithm to direct those rovers.

Your team has already selected a region of the surface to survey. For each mission, you will have a map of the surface that you'd like to study in detail. Each map marks areas that you've identified as impassable by the rovers and marks spots that have been identified as safe for landing. For each region, you will be given this surface map and the starting positions of your rovers. Since communications with the rovers is costly, you will be directing the rovers by issuing all of their instructions at once, in a form that's detailed in the rules section.

The rovers have relatively short range sensors, so you want them to physically traverse as much of the region as possible. The rovers have a limited supply of power, so there is an upper limit to the number of instructions that they can execute. Your job is to design an algorithm which will direct the rovers, once you have the mapping information and the initial landing positions of the rovers.

Problem

Your job is to write a MATLAB M-file function to direct the rovers. Given a matrix which represents a graph of the region to be surveyed, your solution should specify a path for each of your rovers which traverses as many nodes of the graph as possible.

Region map

You will be given an [50 x 50] square matrix, map, which represents your map of the region of interest. At each point in the matrix, the different types of terrain on the surface to be surveyed are represented by the following:

 1

Clear, open space, not yet surveyed

 0

Space that has been surveyed

-1

Impassable space, where the rovers are unable to go

Rover state

You will also be given a [5 row x 3 column] matrix, state, which indicates the initial positions and orientations of the each of your five rovers. For rover i, the initial state is:
startingRow=state(i,1);
startingColumn=state(i,2);
startingDirection=state(i,3);
where the direction is one of:

1

North: towards descending row numbers

2

East: towards ascending column numbers

3

South: towards ascending row numbers

4

West: towards descending column numbers

Instruction set

Each of the five rovers has enough power to respond to 500 instructions. During each time step, each rover can either move forward one space, or turn 90 degrees to the left or the right. So for each turn, these instructions can be one of:

1

Move forward one space

2

Rotate left (changes orientation only, not position)

3

Rotate right

4

Do nothing

Sample Sequence

The diagram below depicts the motion of a rover on the 4 x 4 map:

1  1  1 -1
1  1  1 -1
1  1  1  1
1  1  1  1

[1 1 3 1 1 2 1 2 1]

Function header

In MATLAB syntax, the function header for your solution should look like this:

function inst = myrover(map, p)

Developing and Testing

• testsoln.m: Run this first: a simple script for testing and visualizing contest solutions.
• theplanet.m: creates a set of test regions and starting positions, against which you can test your algorithm
• survey.m: Given a map, an initial state, and a set of instructions, survey tests the function, plots the paths of your surveying rovers graphically and returns the number of unsurveyed nodes.
• survey2.m: An alternative function for visualizing your solution. Shows overlapping paths more clearly and allows you to point and click to show and hide the paths of specific rovers.
• randmove.m: sample solution, a very simple random algorithm
• lookmove.m: sample solution, makes decisions about how to move each rover based on what is found near each rover, and includes subfunctions for keeping track of state and "looking around" locally in the neighborhood of each rover.

%   create two cell arrays, maps and states
theplanet
%   test the look-around solution on the second sample
inst = lookmove(maps{2},states{2});   
%   visualize and validate the results
survey(maps{2},states{2},inst);       

For this example, we get this result, with 170 spaces left unsurveyed:

Each color represents the path of a single rover: orange, blue, red, yellow, or purple. The triangle points in the direction of travel. When you run survey.m on your own machine, you will be able to see the path of travel animated as the paths are drawn. The black squares represent impassable areas of the region.

Judging Criteria

Note: you are not required to find the optimal solution!

There are two criteria for the judging of this contest:

• unexplored, the number of spaces left unsurveyed by your rovers after 500 steps
  
• time, the execution time of the algorithm.

    score = (alpha * unexplored) + (beta * time)

where alpha and beta are constant scaling factors.

The winning entry is the one with the lowest average score over the test suite.

The MATLAB Contest server will also place a cap on the maximum time allowed for each entry over the test suite. Entries which exceed 90 seconds for the test suite will time out and fail.

Optimizing your code

You can use the MATLAB profile command to help you optimize your code. For more information on the MATLAB profiler, type helpwin profile at the command line or doc profile to read the online documentation. The profiler has been enhanced significantly in MATLAB 5.3 (R11).

Deadline

The contest will close on Friday, June 18, at 5 PM EDT (21:00 GMT).

At that time, the contest queue will be closed to new entries. All remaining entries in the queue will continue to be processed.

Collaboration and editing existing entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and modify any entries in the queue. The contest server maintains a history for each modified entry. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We encourage you to discuss your solutions and strategies with others. We invite you to use the Usenet newsgroup comp.soft-sys.matlab to share ideas.

The Prizes

Prizes will be awarded at roughly daily intervals throughout the period of the contest to the final author of the current highest ranking entry. Daily prizes will include MATLAB or NASA/JPL shirts and mugs. Watch the Message of the Day for details and daily deadlines.

The author of the final winning entry in the contest will receive their choice of:

• a complete box set of the raw images sent back by the Pathfinder mission (3 CD-ROM set) OR
• assorted MATLAB goodies.

Winning entries must be original or must be improvements on other entries. The contest administrators reserve the right the disqualify trivial changes which happen to result in better scores.
 

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 5.3 (R11).

The following are prohibited:

• MEX-files
• eval, feval, etc.
• Shell escape such as !, dos, unix
• Handle Graphics commands
• ActiveX commands
• File I/O commands
• Debugging commands
• Printing commands
• Simulink commands
• Benchmark commands such as tic, toc, and flops

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

Disclaimer