**
Winner Paulo Uribe
**
(NoSoup4U !1)

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.

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.

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:

Initially, all spaces are either clear (1) or impassable (-1).

- 1
- Clear, open space, not yet surveyed
- 0
- Space that has been surveyed
- -1
- Impassable space, where the rovers are unable to go

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);
```

where the direction is one of:

startingColumn=state(i,2);

startingDirection=state(i,3);

- 1
- North: towards descending row numbers
- 2
- East: towards ascending column numbers
- 3
- South: towards ascending row numbers
- 4
- West: towards descending column numbers

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

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

The motion of the rover corresponds to the instruction set: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]`

The initial state of the rover is [4;1;1] (row 4, column 1, direction 1 (North)) The final state of the rover is [1;2;3], (row 1, column 2, direction 3 (West)).

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

Your function should return a [500 x 5] matrix,

`function inst = myrover(map, p)`

`inst`

, of
instructions, where each column of the matrix represents all of the
instructions for one rover.

: Run this first: a simple script for testing and visualizing contest solutions.**testsoln.m**

: creates a set of test regions and starting positions, against which you can test your algorithm**theplanet.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.**survey.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.**survey2.m**

: sample solution, a very simple random algorithm**randmove.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.**lookmove.m**

Example:Download the files above to a place on your MATLAB path, then run the script, .
That script runs the sample solution and presents a visualization of the results: % 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.

**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.

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).

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.

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 newsreader to share ideas.

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.

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

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

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

**Darkness**- You can't see the code or scores for any of the entries.**Twilight**- You can see scores but no code.**Daylight**- You can see scores and code for all entries.**Finish**- Contest end time.