Darkness 1999-06-03 00:00:00 UTC
 
Twilight 1999-06-04 00:00:00 UTC
 
Daylight 1999-06-05 00:00:00 UTC
 
Finish 1999-06-10 00:00:00 UTC

Mars Surveyor - Winners

Strategies, Randomizations, and Optimizations:
an analysis of the winning entry

There are many interesting stories to be told about the contest. The entry names alone would be enough to write a whole article. To give you a sense of that, the name of the final winning entry was NoSoup4U !1 Unfortunately, this short report cannot tell all of these stories. This report looks at the contest from an algorithmic perspective. This is a brief discussion of the final winning entry of the contest, with a closer look at some of the strategies and optimizations that brought it to the top of our rankings.

Problem and rules

First, we will summarize the contest problem. For a complete rules and instructions, see the Rules page. The problem is to direct five rovers to survey an area as completely as possible.

You are given a map of the area, represented by a 50 by 50 matrix. The map shows the passable and impassable regions, indicated by 1's and -1's. You are also given a state matrix to indicate the initial starting point and orientations of the 5 rovers. The state matrix is represented by a 5 row by 3 column matrix. The first two columns denote the XY coordinates (that is, the row and column indices in the map matrix) and the third column denote the orientation: North = 1, East = 2, South = 3, and West = 4.

At each time step, the rover can move one step forward or it can rotate 90 degrees to the left or to the right. The instruction for each rover should be indicated as one of: Forward = 1, Rotate Left = 2, Rotate Right = 3, Do Nothing = 4.

Given the map and initial state matrices, each entry should return a 500 row by 5 column matrix which indicates the directions for each of the 5 rovers at each time step for the maximum 500 time steps.

The objective is to instruct the rovers to survey (i.e. visit with at least one of the rovers) as many spots as they can within 500 instructions, while also minimizing the CPU time that is used to generate these instructions.

The scoring function takes into account both the CPU time and survey coverage percentage.

 
score = alpha * CPU time + beta * percentage unsurveyed

The smaller the score, the better. For this scoring formula, the ratio alpha/beta is the key factor. After some testing, we decided that 1 to 4 is about the right ratio and chose alpha = 5 and beta = 20.

Test Suite

The other key variable in the scoring was our particular choice of maps that we used in the test suite. You can now download them here:
surveyortestsuite.m...

Simple optimizations

We provided two sample entries to illustrate the rules and to get the contest started. Most of the initial contest entries started out by tweaking one of these two sample programs. During the evolution of this program, several key techniques had been introduced:
  1. Go straight if possible, because turning "wastes" a step.
  2. Use a transition matrix for the orientation. This technique can make the code clearer and improve the speed by avoiding conditionals and MOD or REM functions.
  3. Look ahead several steps instead of just looking at the immediate neighbors. This is like adding a telescope to the rover. It's also a step from local optimization towards global optimization.
  4. Use 1-d indexing instead of 2-d indexing.
  5. "Build a wall" around the borders of the map. That is, add an additional row or column at the edges of the map and fill this border with -1, so we can treat the boundary the same as we treat internal forbidden regions. This saves a lot of CPU time by avoiding constant checking to see if a rover has reached the edge of the map.
  6. The most important breakthrough is to compute a complete path for each Rover separately instead of handling all 5 rovers at each time step in parallel. Contrary to our intuitions, this turned out to be more effective.

These techniques were very effective, and they reduced the score from the initial 1193 of our sample lookmove to 263.9, achieved by Roger Stuckey's SiRov (whose lineage can be traced back to the original lookmove through contributions by Peter Acklam, Paulo Uribe, He Qiang, and Anders Holtsberg). This is quite a significant improvement. However, most of these techniques were efforts to improve the CPU time for the algorithm. The survey coverage percentage stood still for quite a while. (Note that in this report, we report scores to the nearest integer. The scores were reported with more precision in the contest rankings.)

Further minor reductions in cputime continued to improve the score. However, the top score score reached a plateau at 238 with Murray Simpson's FrwSiRov 6.5.MSX. There was little that could be done to improve the score without improving the survey coverage beyond the 10.1% left unsurveyed by these entries. One contestant even computed that in order to reach our next prize target of 200 points, the entries would have to achieve a negative execution time unless the coverage percentage was significantly improved.

One approach to improving the coverage was to introduce random variations in the alorithm parameters, in an effort to tune the entries to the test suite. Several people decided to play the entry lottery. One contestant submitted the same entry over one hundred times! Unfortunately, none of the hundreds of submissions hit the jackpot.

Observing that the contest had stalled, we posted some facts about what we had learned about the problem in our own internal contest. Primarily, we wanted to point out the existence of significantly better algorithms, none of which relied on the use of random numbers.

Publicizing these facts prompted a fresh batch of entries with a host of new strategies and algorithms. In particular, Martin Leach introduced a 'put-your-right-hand-on-the-wall' approach to move the rover when it hit a barrier. This was a revolutionary approach. It was a simple local strategy that was very often effective in getting a stuck rover to a free unsurveyed spot. This strategy improved the survey coverage to under 6.2%. With Soup Dragon 34, Martin shattered the long standing 200 point barrier with a score of 174. With several more rounds of tweaking, Paulo Uribe finally reached a score of 109 with the winning, NoSoup4U !1.

Let's now take a look at the winning entry.

The Winning Entry

The winning entry and most of the top ranked entries in the contest used the same basic heuristics which we will discuss as strategies (i), (ii), and (iii). In pseudo-code:

 
    if (we can go straight)
       (i) go straight
    else if (there is an unsurveyed spot to the left or right)
       (ii) turn towards the unsurveyed spot
    else
       (iii) try to get to an unsurveyed spot
    end
Each of these strategies is described below. First, we describe the entry's handling of two particular special cases, the setup of state and transition matrices to simplify computation within the loop, and the design of the main loop.

Special cases and known cases

It turns out that the image shown on the results page for each entry is actually one of the maps used in the contest test suite. Roger Green noticed this and, most probably with the diligent efforts of some overworked graduate student, he was able to hand code an optimized solution to this particular map in Apriori II. Colin Sinclair discovered that one of the maps in the test suite was a "clear" map, with no obstructions, and created an algorithm tailored to that case in SneakyClearSoup2. Thus, the first 179 lines of code are specifically tuned to the two known maps.

 
3  mapsum=sum(map(:));
4  if mapsum==2500

In lines 3-4, we look for a blank map, a matrix with all 1's, meaning no obstructions. In that case, it uses a specialized algorithm, in lines 5-120, to survey the map. The map is divided into five equal sized horizontal regions, and the rovers are directed to go to the top left corner of its assigned region and then scan back and forth across each row in the region.

 
121 elseif p==[50 1 3;49 2 3;48 3 3 ; 47 4 3 ; 46 5 3];

Line 121 looks for the initial state which matches that of the map that's shown on each entry's results page. In this case, the instruction matrix is simply hard coded in lines 122-176. Since all of the top entries use this block of precomputed code, the images on the results pages are not helpful in understanding the distinctions between the entries.

Setup

The real program starts here, at line 180. The following chunk of code selects a weight vector based on a particular feature of the test case. This weight vector is used in lines 288-314 in decided which direction to turn in strategy (ii). This weight vector claims to be tuned to the test suite, so this may help improve the final score. However, there doesn't seem to be any theory behind these weight vectors.

 
  3  mapsum = sum(map(:));
...
180  % This is *cheap*.
181  % The wv-vector is tuned to fit each test case.
182  qix=4;                            
183  if mapsum>1500                   
184     qix=qix+(mapsum-1500)/100;
185  end
186  if(sum(map(:,7))<=20)
187     wv = 1./([1:55]+0.1);
188  elseif sum(map(:,7))<=26
189     wv = 1./([1:55]);
190  elseif sum(map(:,7))<=47
191     wv = 1./([1:55]+0.05);
192  else
193     if sum(map(17,:))<=30
194        wv = 1./([1:55]);
195     elseif sum(map(17,:))<=40
196        wv = 1./([1:55]+0.05);
197     else
198        wv = 1./([1:55]+0.05);
199     end
200  end

From a MATLAB programming point of view, there's one thing we need to point out about these lines. As Mike Watson recognized in Brackets are Expensive, the square bracket for [1:55] is not necessary. The square bracket operator is a generalized concatenation operator. We do not need to do any concatenation in this case, we simply need to create an array so (1:55) will do the job. We can improve the speed of the code by avoiding the preparation that MATLAB must do to set up for concatenation.

(Note: This is true in general. However, in this case, the square brackets do not occur inside the loop so these statements account for very little of the computation. Brackets are Expensive actually performs slightly more slowlythan its predecessor, TimeToGoHome, Sneaky needs a life!, whose code survives intact in NoSoup4U !1. This is another example of the measurement noise inherent in this test and in all benchmarks.)

 
124  inst = ones(510,5); % a bit more to allow for 
                         % overflow of while loop
Here we preallocate and initialize the instruction set to be all ones. This is better than initializing it to be zeros since most of the instructions will be 1 (move forward). We can save a lot of assignments this way.

 
124  % Stick some impassable edges around the map
125  edge1 = -ones(1,52); edge2 = -ones(50,1);
126  map = [ edge1 ; edge2 map edge2 ; edge1 ];

These lines add some impassable edges around the map, so that the edge can be treated like impassable inner regions and thus we can avoid constantly checking to see if a rover is at the boundary. Once again, the square bracket in line 126 is costly; a better way to do this is to pre-allocate a 52 by 52 matrix filled with -1, and then assign the initial map to the middle 50 by 50 block, i.e.

 
     map1 = -ones(52);
     map1(2:51,2:51) = map;
Lines 208-211 initialize some frequently used vectors.
 
208  sub1 = 0:50;
209  add1 = 2:503;
210  add2 = 3:504;
211  add3 = 4:505;

Next we set up for 1-d indexing. 1-d indexing is more efficient then 2-d indexing for this problem. For example, a 3 by 4 matrix may be indexed by x(row,column) or by x(i), where:

 
x = [1  4  7 10; ...
     2  5  8 11; ...
     3  6  9 12];
 
x(2,3) --> 8
x(8)   --> 8

So i is a column vector of the 1-d index positions of the rovers in the 52 by 52 matrix. (Line 214 is equivalent to line 213.)
 
213  %i = 1+p(1:5,1)+52*p(1:5,2);
214  i = 1 + p*[1;52;0];

Here we separate the orientation of the rover from the initial state matrix.

 
215  d = p(1:5,3);

Lines 217-224 construct some transition vectors and matrices. They make the computing the new orientation vector easier. Without these transition matrices, we have to use MOD or REM very frequently, which is not very efficient.

 
217  idxleft = [-52 -1 52 1];
218  idxright = [52 1 -52 -1];
219  idxfwd = [-1 52 1 -52];
220  idxback = [1 -52 -1 52];
221  idxbackright = [53 -51 -53 51];
222  turnleft = [4 1 2 3]; 
223  turnright = [2 3 4 1];
224  turnback = [3 4 1 2];

For example in line 271 below, map(idx+idxfwd(dir)) returns the contents of the map space directly ahead of the rover at position idx with orientation dir.

Lines 232-256 compute distances from every position in the map to the closest blocked region in each direction, later these distances will be used to make decisions as to which direction to turn.

 
225   Oneto50 = [1:50];
226   picknorth = -Oneto50;
227   picksouth = Oneto50;
228   pickeast = 52*Oneto50;
229   pickwest = -52*Oneto50;
230  
231   % precompute distances to blockages for all idx
232   allkw = zeros(52,52);
233   allke = allkw;
234   allkn = allkw;
235   allks = allkw;
236   blockns = find(map<0).';
237   blockwe = find(map'<0).';
238   dns = diff(blockns);
239   dwe = diff(blockwe);
240   distinc = [-1:49];
241   distdec = fliplr(distinc);
242   for idx = blockns([dns 1]~=1)
243     allkn(min(idx:idx+50,2704)) = distinc;
244   end
245   for idx = fliplr(blockns([1 dns]~=1))
246      allks(max(idx-50:idx,1)) = distdec;
247   end
248   for idx = blockwe([dwe 1]~=1)
249     allkw(min(idx:idx+50,2704)) = distinc;
250   end
251   for idx = fliplr(blockwe([1 dwe]~=1))
252      allke(max(idx-50:idx,1)) = distdec;
253   end
254   allkw = allkw.';
255   allke = allke.';

Finally, before entering the main loop, we mark our initial positions as visited.
 
258   % Mark the initial locations as visited.
259   map(i) = 0;

Main loop

The main loop starts here at line 261. Originally, the outer loop was on t, the time step. Intuitively, it might seem that computing the paths of the rovers in parallel would be more efficient. However, it turns out this is not the case. We get better coverage if we compute the instructions one rover at a time. Of course, when the algorithm is tested, each of the rovers is moved in parallel.

This approach allows us to take advantage of the knowledge of the future that we already have. Rover 2 and each succeeding rover can, in essence, see into the future. For example, at every time step, rover 2 "knows" which squares will be eventually covered by rover 1 over its entire path.

 
261  for rover = 1:5
262    
263    dir = d(rover);
264    idx = i(rover);
265    t = 1;
266    tries = qix;
267    rtries = 2;
268
269    while (t<=500)

Line 269 begins the inner loop over t, the time step. In the next line, we begin a set of heuristics to determine what move to take next.

Strategy (i): Go straight if we can

271 if (map(idx+idxfwd(dir))==1) & tries 272 % if square in front empty move forward 273 idx = idx+idxfwd(dir); 274 t = add1(t); 275 map(idx)=0; 276 tries = sub1(tries);

If the front square is passable (and not surveyed), go there. This is the basic rule for all rovers, and is the most efficient way to survey since turning costs an action.

Strategy (ii): Turn if there's an opening in the immediate neighborhood

If the front square is blocked or already surveyed, decide which direction to turn based on the weight vector and the distance (to the block region) matrix that were computed earlier.

 
278      else
279         tries = qix;
280         % check left, right, forward and back for spaces
281         % wv weights free space, blocks still negative
282         kw = allkw(idx);
283         ke = allke(idx);
284         kn = allkn(idx);
285         ks = allks(idx);
286         
287         if dir==1
288            
289            sw = sum(wv(2:kw+1) .* map(idx+pickwest(1:kw)));
290            se = sum(wv(2:ke+1) .* map(idx+pickeast(1:ke)));
291            sn = sum(wv(1:kn) .* map(idx+picknorth(1:kn)));
292            ss = sum(wv(4:ks+3) .* map(idx+picksouth(1:ks)));
293            [val, move] = max([sn sw se ss]);
294            
295         elseif dir==2
296            sw = sum(wv(4:kw+3) .* map(idx+pickwest(1:kw)));
297            se = sum(wv(1:ke) .* map(idx+pickeast(1:ke)));
298            sn = sum(wv(2:kn+1) .* map(idx+picknorth(1:kn)));
299            ss = sum(wv(2:ks+1) .* map(idx+picksouth(1:ks)));
300            [val, move] = max([se sn ss sw]);
301            
302         elseif dir==3
303            sw = sum(wv(2:kw+1) .* map(idx+pickwest(1:kw)));
304            se = sum(wv(2:ke+1) .* map(idx+pickeast(1:ke)));
305            sn = sum(wv(4:kn+3) .* map(idx+picknorth(1:kn)));
306            ss = sum(wv(1:ks) .* map(idx+picksouth(1:ks)));
307            [val, move] = max([ss se sw sn]);
308         else
309            sw = sum(wv(1:kw) .* map(idx+pickwest(1:kw)));
310            se = sum(wv(4:ke+3) .* map(idx+pickeast(1:ke)));
311            sn = sum(wv(2:kn+1) .* map(idx+picknorth(1:kn)));
312            ss = sum(wv(2:ks+1) .* map(idx+picksouth(1:ks)));
313            [val, move] = max([sw ss sn se]);
314         end

Strategy (iii): Follow the wall until we're unstuck

If no good direction is produced, it means we can't get to an unsurveyed spot simply by turning. We are stuck here; we are surrounded by impassable or already surveyed spaces. The strategy we use here in lines 316-347 is equivalent to putting your right hand on the wall and following it until we see a surveyable spot.

 
316         if val == 0 % no space in any direction
317            
318            % if stuck keep a blockage on right hand side
319            if (map(idx+idxbackright(dir))==-1) ...
                     & (map(idx+idxright(dir))==0) & rtries
320               % turn right move forward
321               idx = idx + idxright(dir); dir = turnright(dir);
322               inst(t,rover) = 3;
323               t = add2(t);
324               rtries = sub1(rtries);
325            elseif (map(idx+idxfwd(dir))==0)
326               % move forward
327               idx = idx + idxfwd(dir);
328               t = add1(t);
329            elseif (map(idx+idxleft(dir)) == 0)
330               % turn left move forward
331               idx = idx + idxleft(dir); dir = turnleft(dir); 
332               inst(t,rover) = 2;
333               t = add2(t);
334               rtries = 3;
335            elseif (map(idx+idxright(dir)) == 0) & rtries
336               % turn right move forward
337               idx = idx + idxright(dir); dir = turnright(dir);
338               inst(t,rover) = 3;
339               t = add2(t);
340               rtries = sub1(rtries);
341            else
342               % turn back move forward
343               idx = idx + idxback(dir); dir = turnback(dir);
344               inst(t:add1(t),rover) = 3;
345               t = add3(t);
346               rtries = 3;
347            end

Update state

Now that we have a decision, we need to update the current status. Please note that since the instruction set has already been initialized to ones, we don't need to update inst when we want to move forward. This saves a lot of time, since that is the most common move.

 
349         else % some space
350            
351            if move==1
352               % move forward
353               idx = idx + idxfwd(dir);
354               t = add1(t);
355            elseif move==2
356               % turn left move forward
357               idx = idx + idxleft(dir); dir = turnleft(dir); 
358               inst(t,rover) = 2;
359               t = add2(t);
360            elseif move==3
361               % turn right move forward
362               idx = idx + idxright(dir); dir = turnright(dir);
363               inst(t,rover) = 3;
364               t = add2(t);
365            else
366               % turn back move forward
367               idx = idx + idxback(dir); dir = turnback(dir);
368               inst(t:add1(t),rover) = 3;
369               t = add3(t);
370            end
371            map(idx)=0;
372            
373         end % if no space
374         
375      end % full check
376      
377   end % while
378   
379 end % rover

Return result

Since earlier we padded inst to guard against overflow, we need to return only the first 500 instructions as our final result.

380 inst = inst(1:500,1:5);

Limitations

Going from very local "looking around" to this simple path construction yields significant improvements in the coverage. This, along with many optimizations to the code, was the one of the keys to achieving the winning score. However, this put-your-righthand-on-the-wall approach sometimes takes many instruction steps to move clear of an obstacle. Also, rovers may end up stuck do laps of already surveyed paths alongside impassable regions; this technique is not guaranteed to find the remaining unsurveyed spots. For that we need a true search mechanism.

Other strategies

Some people were curious about the entries in our internal MathWorks contest. Here's a brief description. All of the best entries in our internal contest followed the same basic strategy as that in the winning entry, i.e.

 
    if (we can go straight)
       (i) go straight
    else if (there is an unsurveyed spot to the left or to the right)
       (ii) turn towards the unsurveyed spot
    else
       (iii) try to get to an unsurveyed spot
    end

The primary difference in our internal contest was the introduction of search algorithms in strategy (iii) to compute a complete path from a stuck position to the nearest unsurveyed spot. There were three approaches to this problem in our internal contest, all of which essentially use a breadth first search algorithm to find this path.

The first approach uses a large (2500 by 2500) state transition matrix, M. M(i,j) represents a transition from position i in the 50 by 50 matrix (1-d indexing again) to the position j in the 50 by 50 survey area. Since only a few positions j are accessible from each position i, the matrix is quite sparse. When a rover is stuck, we can use the transition matrix to help us compute what states (positions on the map) are reachable in a given number of steps and the shortest path to get there. It is an effective way to keep track of state during the search, but it is a bit slow.

The others both use more conventional implementions of breadth first search to compute a new path for a stuck rover. They differed primarily in programming style, e.g. the use of vectorization. These last two approaches achieved an uncovered percentage of 3.7%. The winning entry in the internal contest used only about 3 seconds of cputime.

At first, it may seem that it is too costly to perform this search. But since most of the time the rovers run unobstructed, this search is performed only infrequently; it is activated only in strategy (iii) when the other strategies have failed. Breadth first search is an efficient strategy for finding the nearest open space and finding a path to it. Since the target space is usually close by, the average depth of the search is also low. We found that the time that it takes to conduct this search is more often offset by the improvement in coverage that is achievable.

The next contest...

We'll be holding the next contest in December, 1999. Watch for an announcement in the Winter edition of the MATLAB Digest and on the MathWorks home page, www.mathworks.com. We'll also announce it on the Usenet group comp.soft-sys.matlab, where you can always find lots of great advice on optimizing your MATLAB code.

We're always on the lookout for new contest problems, so if you have some ideas, drop us a line at contest@mathworks.com. Hope to see you next time!