Medallia Blog

Many developers here at Medallia have participated extensively in algorithmic coding competitions like the ACM World Championship of Programming and TopCoder Open. These are fast-paced and get the blood flowing, as you spend around an hour to solve a problem, and either your solution gives the correct answer for every single test case, or you score zero. This year, however, the TopCoder Open added a new competition format, the marathon. Here you have typically one full week to work on a problem which is too hard to find the optimal solutions, but instead your solution is scored based on how well it fares compared to your competitors. With the possibility of all-paid travel to the finals in Las Vegas for the 8 best competitors and $15,000 to the winner, I decided to give this interesting new competition a shot.

There were 1249 registrants, which got narrowed down to 500, 200, 50, and finally 8 through four online rounds. In one problem you had to make an AI for a simplified version of poker, and in another you had to write a strategy for a lumberjack running around in a forest. It is however the fourth problem that is my topic, as here the competition gets really tough for those 8 finalist spots.

The problem is about directing an army of up to several thousands robots as they go around in a warehouse delivering products, with the objective of completing all the assigned tasks as quickly as possible. Researchers have studied the general concept of multi-robot collaborative routing before, but it's much more fun to see what 50 good programmers can come up with in two weeks for this particular problem formulation.

Read the full entry to see a full explanation of my algorithms, the source code, and the results.

A little more background on the problem: The warehouse is represented as a grid, which can be from 20x10 to 100x400 in size, so the solution will need to deal well with this dynamic range in board sizes. Around the warehouse are shelves, placed in a regular pattern, which are obstacles to the robots, and where the products are located. The products need to be dropped off at the left edge of the board.

If you really want the details, you can download my source code. It's about 1000 lines of Java. No JavaDoc! I'm a bad guy :) While the code is clearly not production quality, it's far cleaner than what you'll find in the typical one-hour algorithmic contest problems. In this case, working on the problem over several days, I rewrote parts of the solution many times to try out different strategies, and then it helps quite a bit that the code isn't totally intertwined.

My analogy in dealing with this problem has been traffic planning. The robots are not allowed to crash into each other, and so one of the main challenges with the problem is moving the robots about in a manner that they don't hinder each other. With thousands of robots, the way to go is to introduce traffic rules. I consider as a lane each row or column without shelves. In a lane you can only go in one direction, and this direction will alternate between left and right in the rows, and up and down in the columns. This is what the picture illustrates (for a very small board).

Now, in order to route the robots given these traffic rules, I repeatedly need to find shortest paths from a robot's current location to its next destination, and that needs to be done really fast. With up to 40,000 locations on the map, we cannot precompute all the pairwise distances. However, we can precompute the pairwise distances between all intersections in the map, and now in order to find the distance from A to B you only need to add the distance from A to the next intersection, the distance from that intersection to the one before B, and the remaining distance to B.

I'm not a very strict traffic police :) I allow the traffic rules to be broken, as long as nobody's hurt. I.e. I will let a robot make a U-turn if it finds it opportune, given that no other robot is trying to move into that same spot.

I take one time step at a time, deciding on every single robot's action before moving on to the next time step, and so on until all the products have been delivered. Due to the intersections, there can be multiple robots bidding for the same spot at the same time, and those conflicts need to be resolved. I implemented a fairly simple recursive strategy where each robot just prioritises the different moves it can make, and tries performing it. If there's already another robot there, it asks that robot to move, and so on. This might sound like a potentially exponential run-time, but in fact it is linear in the number of robots. The reason is that if a robot is unable to move, then it won't be able to move the next time either, and if a robot moves, then it cannot move again that same time step, so either way the answer is "no" the second time a robot is asked to move.

One interesting aspect of this kind of competition format, is that you have to discover what works or not during the coding. Work progresses as a sequence of come up with ideas, implement, run, analyse the outcome, and find new or modified solutions for the issues that you come across. One thing I learned pretty fast is that traffic congestion spreads quickly. Once traffic is jammed in one place, robots will take long to get out of there, but more robots will pass by and get stuck, and you get a self-reinforcing process going. It is therefore essential to prevent congestion from arising in the first place. I did this by kicking robots that get stuck in an intersection, out of there, even if they don't want to. It's better to take a small hit in terms of a robot having to go longer, than risking a congestion which could stop the combined efforts of all the robots.

It proved impossible to avoid for all types of boards some level of congestion at the left edge of the board, since all the products are being dropped off there. That's why I deviated slightly from alternating the main directions of the lanes, by having both the leftmost lanes be upwards. This avoids robots trying to move down the very leftmost lane, where traffic is doomed to be blocked by robots dropping off robots, but instead have access to two lanes for moving upwards only.

In fact, the most effective measure for avoiding the congestion at the left edge of the board had to do with grouping together products that a robot is handling. The robots have capacity to carry a certain number of products at the same time. So the first step of my solution is to batch up all the tasks into assignments. I only allowed tasks to be grouped together that had the exact same drop-off point for the product. This effectively prevents robots from moving up or down the already congested left edge to deliver several products.

With this restriction, I could concentrate on each point on the left edge at a time while batching tasks, with typically a couple of hundred products to be delivered there. I begin with the task whose starting point is closest to the drop-off point, and consider each of the others in turn to find the one closest to this again, and so on until the capacity has been filled up. Then I start over again with the point closest to the drop-off of those remaining.

When I say "closest to the drop-off", I actually used two different definitions. One distance measure was the actual routing distance from the location of the product to the drop-off. The other one was simply the vertical distance between the pick-up and the drop-off, completely ignoring the horizontal distance. The idea of the first is obviously to reduce total routing distance, whereas the idea of the second is to avoid vertical movements at the congested left side of the board. I experienced that from test case to test case one or the other would be considerably better, but I could not immediately see what characterized the different situations. Looking at the parameters for the cases, I spotted a correlation with the number of robots available, but it was not enough to determine for sure which distance measure would be better. However, a little more analysis showed that the number of robots divided by the area of the board would give a clear separation. This lead to the only really magical constant in my program, namely that I switch distance function depending on whether the density is above or below 8.2%

After creating the batches of tasks, they also need to be assigned to the robots. The assignments that were the most unfortunate in the sense of having the longest route, are assigned first, in order for them not to delay the completion time. Each of these heaviest assignments in turn select the robot that is initially closest to them. The rest of the robots get to pick the assignments themselves, i.e. they pick the assignments that are closest to their initial position.

As the end of all the tasks is approaching, it gets increasingly important to help out the robots that seem to have the longest route left to go. This is done in two ways. One is that they're given first choice when resolving conflicting move requests. The other is that robots that finish their assignments, after there are no new assignments to pick, go through the robots that are still working and see if they can help them out by taking over some of their tasks.

The run time of my program varies between like a second and up to 40 to route all the robots through all the time steps, depending on the difficulty of the board. The time limit is 60 seconds per test case, which means I have plenty of time available. I used that to run the same algorithm several times, with different random seeds, and picking the best result. Typically there would be time enough for 20 rounds, and that improves the solutions somewhat since there's some level of variance.

I have here given a reasonably complete overview of all the features that are in the ultimate solution I ended up with.
So how did it fare in the competition? Pretty well actually, I'm currently in 2nd place. It scored 30.37 points out of 35, which means that I'm on average like 15% behind the best answer from the aggregate of all the submitted solutions. The leader scored 32.72 points. The results are available here.

So I am all set for Las Vegas! That will be really fun, and let's just hope I win more at the programming than I lose at poker, because I don't think that AI of mine from the previous round is going to help me much there. For the finals itself we get only 9 hours to solve the problem. It could turn out to be the most fun competition at TopCoder Open to watch onsite at the Mirage, as we'll probably be provided with a visualizer for our testing purposes and the spectators' amusement.