MATLAB Programming Contest Analysis
Our analysis of the Surveyor contest is in two parts:
-
"Strategies, Randomizations, and Optimizations"
-
First, we take
you line by line through the winning entry, in an analysis of the
algorithms, strategies, and optimizations in the final winner,
NoSoup4U !1.
- "In Praise of Tweaking"
-
Next we take a quantitative look at how these innovations developed
over the course of the contest. In
"In Praise of Tweaking", we look the
interplay between radical innovations and tweaking battles in the
development of the winning entry.
MATLAB Contest Analysis
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:
- Go straight if possible, because turning "wastes" a step.
- 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.
- 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.
-
Use 1-d indexing instead of 2-d indexing.
- "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.
- 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!
|
