Match Scheduling Algorithm Competition

[theycallhimtom]

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/longco...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.

[Joe Ross]

I wonder why FIRST didn't publicize this?

[Billfred]

Originally Posted by Joe Ross

I wonder why FIRST didn't publicize this?

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.

[AdamHeard]

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.

Originally Posted by Billfred

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.

[EricH]

Originally Posted by Billfred

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

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

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.

[Dave Scheck]

Originally Posted by Billfred

then it could reduce the number of "oh-crap-we-play-against-Beatty-AND-Simbots-this-match?!" rounds

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.

[Billfred]

Originally Posted by AdamHeard

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.

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.

[Ether]

Originally Posted by theycallhimtom

...FIRST is sponsoring the problem so they will probably use the winning algorithm at future events. ...the contestants get 12 hours to come up with the best solution to a problem given.

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

[JesseK]

Originally Posted by Ether

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

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.

[Jared Russell]

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

[thefro526]

Originally Posted by Jared341

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

Co-Signed, with one exception:

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

[JesseK]

Originally Posted by Jared341

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

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.

[Ether]

Originally Posted by JesseK

I wouldn't take a single coder 3 months

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

[Andrew Schreiber]

Originally Posted by Ether

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

And allows for adequate testing and analysis.

[gblake]

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.

2) 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