Winner Paulo Uribe (NoSoup4U !1)
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:- 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
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;
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.
Finally, before entering the main loop, we mark our initial positions as visited.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.';
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!