Match Scheduling Algorithm Competition

FIRST General Forum
#1

At the TopCoder open the “marathon match” problem is scheduling for FIRST events. Contestants have to come up with a computer program to generate schedules for FIRST events. They are scored on a number of things like the amount of time between matches for each team, number of times the same teams play, etc. FIRST is sponsoring the problem so they will probably use the winning algorithm at future events. You can view the problem statement here (needs an account) http://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=21964&rd=14632

For those who don’t know TopCoder is a programming contest. The TopCoder Open is their yearly championship which is in Florida this year. In the marathon match format the contestants get 12 hours to come up with the best solution to a problem given. They have about 3 hours left in the contest now.

#2

I wonder why FIRST didn’t publicize this?

#3

Best I can tell from rooting through their site, this particular challenge is their championship round and is thus invite-only.

The challenge has seven quality metrics they’re trying to minimize (with each metric carrying its own definable weight):

-Difference in average team age on each alliance between the two alliances
-Difference in average rank of a team (defined from 1 to 10 in the challenge, where 1 is rookie and 10 is reigning champion) between the two alliances
-Unique partners
-Unique opponents
-Time between matches (more is better)
-Assignment to red or blue
-Position in player station

If FIRST took the current match assignment criteria (as defined in The Tournament–PDF link) and put the age and (reasonably-calculated) rank criteria in beneath the unique opponent/partner criteria, then it could reduce the number of “oh-crap-we-play-against-Beatty-AND-Simbots-this-match?!” rounds–at that point, the algorithm is likely to switch one of them to your alliance (especially at Championship, where they’d have the benefit of regular-season data).

TLDR: This could evolve into a good thing or a bad thing, depending on what weight you put on the factors.

#4

FIRST has no valid way of ranking teams, and thus the only fair way to do selections is randomly. Factoring age or some arbitrary rank will never be fair.

#5

I’d go with ditching the age entirely. Remember the Algorithm of Doom in 2007, where you might end up against 1114 AND 2056 (a rookie that year) AND 71 at the same time, and all of them multiple times (assuming that the age breakup worked out that way), and very rarely with one or the other?

Yeah. Age has very little to do with anything around here–I’m somewhat scared of what Dr. Joe is starting up in Boston…or any team 1114 mentors.

The rank part, OTOH, I can live with, if it’s done right. If you’re careful about the implementation, and use the available data about record/seeding/result, then I think it could work very well. If you’re arbitrary about it, like the Algorithm of Doom was with age, it’ll go down as a lousy idea.

#6

Take the other point of view and ask yourself how to minimize the “Hey, we’re one of the top teams at this event and we get to play with a box on wheels and one that only spun in circles last match”. True random is the only way that you can make fair schedules. The last time FIRST tried to introduce “smarts” into the system the worst schedules in history were seen (remember the low/mid/high system)…I hope they never try to do that again.

EDIT: Looks like Eric was thinking along the same lines as me.

#7

Agreed–there will always be really great rookies and really awful veterans, and there are teams that reach Einstein one year that fall off the radar entirely the next. No formula accounting past years’ performances will account for student and mentor turnover perfectly.

However, one could certainly compute rank for within the season, especially at the Region Championship and Championship levels where everyone has played this game before.

Edit: Dave got in between my reading and my posting. I’m not advocating for those two to be anywhere before line D in this year’s criteria (read: just ahead of equal red/blue assignments), if anywhere. I’d definitely want to see some sample outputs before I put my blessing on any such method.

#8

If they want a good algorithm… why not put the challenge out there, offer a cash prize or a free pass to champs for your team, and give everybody 3 MONTHS (instead of 12 hours) to work on it

**

#9

I wouldn’t take a single coder 3 months, and a team of 4-6 could easily do a rough draft in 12 hours. I’d say that we should give them the same length as the build season: 45 days. There are 2 basic approaches I’ve tried in the past:

  1. A combinatorial approach that uses all 500,000-some unique match pairings of a 84-team event (worst case example) and begins to brute-force build a schedule based upon rules. Conceivably this would be a fine approach until the end, where the rules would be harder to meet given the dwindling pool of match pairings that meet the rules.
  2. An approach that calculates the ‘buckets’ of teams, assuming even spacing. For example, if 24 teams play 6 matches each, then one can create a long list of teams that is a simple stitching of 6 shorter lists {{1…24}{1…24}…{1…24}}. For minimum match spacing, the edges of the stitches should be checked for duplicate teams (easily done if one uses Collections.disjoint() in Java). After that, the list could be broken up into alliance pairings (multiple of N teams per alliance) and then match pairings (M alliances per match). Then an algorithm could check for duplicate alliance pairings, duplicate opponent pairings, etc. If the algorithm finds them (very likely if the stitched lists are randomly-generated) it’s up to the coder to figure out what to do next – live with them, regenerate new stitched lists to find a better pairing with less duplicates, etc.

I dug into match scheduling some, with various modifications to the approaches for efficiency. It’s not easy to get it perfect, but it IS easy to get it started and is a great way to teach object-oriented programming to students who already have the basics of programming under their belt.

Really they should have 2 competitions: 1 that creates the algorithm, and 1 that creates an intuitive User-Interface for it. Both are equally difficult, IMO, and the latter would teach very fundamental concepts of software product design.

#10

I am vehemently opposed to the idea of factoring either team age OR rank into FIRST match schedules - AT ALL.

#11

Co-Signed, with one exception:

I’d prefer to not see Three Rookie Teams playing on the same alliance at the same time.

#12

So am I. The only thing equal to or more inspiring/motivating than teaming with 1114 is getting stomped by them (lol). IMO, the problem is more about the perception of what ‘should not’ happen under ‘random’ circumstances. Under random circumstances, lopsided match pairings are equally likely to evenly-skilled match pairings. Yet at run-time (i.e. at competition), the lopsided matches are often undesired and perceived as the product of a ‘bad’ algorithm.

This perception is similar to the perception of coin-flipping: often times, after a streak of ‘heads’ one incorrectly often perceives the chances of getting ‘tails’ to be higher – when in reality nothing about the probability has changed. I don’t have the article that I read on probability psychology bookmarked, but I’ll look for it later if I remember to.

#13

Of course not. But 3 months calendar time (not man-hours) makes the challenge accessible to a larger talent pool.

**

#14

And allows for adequate testing and analysis.

#15

Like Jesse, I too have written a scheduling program. I took the brute force & heuristics approach. It wasn’t too hard even for someone like me who does software work mostly as a hobby. Mine was for 2-team matches because I was focused on FVC (FTC/VRC) at the time.

Truth in advertising - The heuristics still need to be tweaked to avoid getting “trapped” by early arbitrary choices that force a bad choice later; but the overall results are pretty good.

A couple of points to make:

  1. I have written this before, but it bears repeating; there is no such thing as a scheduling algorithm that is simply “fair”. Algorithms are only fair in some “sense(s)”. In conversations like this thread, if you don’t pair the word “fair” with a description of the sense(s) in which you are using it, the conversation falls apart.

When the word is used you have to clarify whether you mean fair in the sense of putting all teams at each of the red and blue alliance station positions evenly, or do you mean fair in the sense of ignoring the expected skill level of their allies, or do you mean fair in the sense of attempting to give each alliance a similar expectation of winning each match, or…

In this and many other contexts, I recommend banishing the word “fair” from your vocabulary if it isn’t paired up with more information.

  1. I remain surprised that the scheduling algorithms at STEM robotics tournaments aren’t drawn from open source descriptions and code. The scheduling problem isn’t that hard. Tournament organizers (either at a worldwide HQ level or at local levels) should choose the heuristics they want to employ, proudly announce them, pluck a tried-and-true implementation off the shelf, and then get on with the rest of the season.

In the scenario I outlined above, folks (participants) could certainly suggest different heuristic choices (and certainly would), but once the choices are made, there shouldn’t be any mystery about them or about how they are implemented.

Blake

#16

Well said !

Like Jesse, I too have written a scheduling program.

As have I, for widely different tournament situations.

I took the brute force & heuristics approach.

Meaning what, exactly?

  • generate the space S of all possible tournaments

  • assign a score to each of these tournaments using weighted criteria

  • pick the tournament with the highest score

OR

  • randomly generate a tournament

  • assign a score to the tournament using weighted criteria

  • stop when you find one with an acceptable score

OR

  • construct a tournament using some rules

  • assign a score to the tournament using weighted criteria

  • stop when you find one with an acceptable score

OR

something else?

The scheduling problem isn’t that hard.

Finding an acceptable solution isn’t that hard. Finding the solution that best fits your selection criteria can be quite difficult if the search space is large.

**

#17

The FRC scheduling algorithm has been pretty good in the past few years, hasn’t it? I don’t think they need a new one.

#18

I’m all for iterating on systems to improve them but when you have things that don’t work and things that do you need to prioritize utilization of resources. That being said, outsourcing this to a competition is a pretty good use of resources. It only costs FIRST some time writing requirements and reviewing results rather than spinning up a dev team.

But who knows, they might not ever use the results. They could have just had the problem description laying around from when they had their algorithm written.

#19

It is hard enough for the seeding algorithm to work accurately with such a small sample size; deliberately biasing the schedule for or against some teams will just make it harder to determine who should be ranked where.

#20

After the algorithm of doom* (2007), FIRST did a few things.

They provided a list of requirements for a scheduling algorithm.

a. Maximum time (in number of matches) between each match played for all teams
b. Minimum possible number of times a team plays opposite any team
c. Minimum possible number of times a team is allied with any team
d. Minimize the use of surrogates.
e. Even distribution of matches played on Blue and Red Alliance (without sacrificing a, b, c and d)

FIRST also solicited comments on additional requirements, but did not incorporate any. Most of the comments I remember related to the minimum time between matches, either taking into account natural breaks (end of day and lunch) or allowing a single long break, for things like judge interviews. I don’t remember any proposals for incorporating team rankings or age into the schedule.

Third, they provided a program that would provide rate a schedule based on the requirements. This way, any other algorithm could be evaluated objectively.

Finally, they provided a reference program, Idleloop Software’s MatchMaker (Written by Tom and Cathy Saxton of team 1318) and challenged people to beat it. I only know of one other scheduler that was submitted, and it was marginally worse then MatchMaker. The challenge was issued in September, so there was about 3 months, however, it seemed like all activity died out within 2 weeks or so.

Even though the MatchMaker software was available for months, just having it available didn’t catch all the initial bugs. It was only a week before the championship that people started noticing a clumping problem with large events.

*One thing to remember was that while the Algorithm of Doom did group teams by team number the main reason it was hated is that it did a horrible job at creating a schedule with varied opponents and partners. If the algorithm had done a better job at giving teams different partners and opponents, it might still be used.