Match Scheduling Algorithm Competition

[Ether]

Originally Posted by gblake

I recommend banishing the word "fair" from your vocabulary if it isn't paired up with more information.

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.

[Nemo]

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.

[Andrew Schreiber]

Originally Posted by Nemo

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.

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.

[John]

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.

[Joe Ross]

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.

[Ether]

Thanks for the history lesson Joe. Very interesting.

Four years have passed since 2007, and a whole new student class is now in place. Maybe it's time for FIRST to put this out there again.

One point of clarification:

a. Maximum time (in number of matches) between each match played for all teams

I assume that means "maximize the minimum time"

[gblake]

Originally Posted by Ether

...
Meaning what, exactly?
...
something else?

From memory, and it was a while ago...

Compute all possible (2-team) alliances.
Use a simple arbitrary scheme for pairing alliances in 1st round matches
For 2nd round and beyond matches:

Disregard possible alliances that were used in previous matches
Assign each possible alliance the shortest off-the-field time associated with the two teams in that alliance.
Pick the possible alliance that has been off the field for the longest (break ties arbitrarily).
Pick an opponent from among the remaining alliances. Choose one that:

Doesn't include a team that was allied before with the teams of the already selected alliance
Doesn't include a team that previously opposed the teams of the already selected alliance
Has been off the field the longest

Continue

Continue

I also think that, in order to preserve a minimum inter-match time interval, I put in a heuristic that would permit the first alliance put into a match to face opponents who had been allies earlier.
[Edit] Thanks to Joe I was reminded of this long post that I wrote a while ago - It contains a better description of the heuristics I used - Look near the bottom of it.Link [/Edit]

Originally Posted by Ether

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.

As you know, looking for the "best" of solution to problems in algorithmic domains like one is often fraught with confusion, peril, and frustration. Looking for "good enough" often is the best choice

I should have been more clear. I was willing to accept minor separation between my results and perfection. Creating a good enough scheduling implementation isn't all that hard.

Blake
PS: Joe's info surprised me - Either I totally forgot or totally missed the solicitation and evaluation process he described, so I sent him a PM asking if has any still-valid links or other info I can look at to learn about it.

[JesseK]

At this point, I dunno why we aren't simply creating our own open-sourced algorithm and associated interface. The software engineering prowess of the CD community as a whole could probably out-do a single contestant in any contest, regardless of how long the contest ran. Multiple small tasks are very easily delegated and worked on with a good group.

When I find some time (heh, my fiancee moves in this weekend) I'll resurrect some old stuff and make a Google Code project out of it. It'll start off in Java since that's what I made it in at the time.

[gblake]

Originally Posted by JesseK

At this point, I dunno why we aren't simply creating our own open-sourced algorithm and associated interface. ... It'll start off in Java since that's what I made it in at the time.

I'll contribute.

[Ed Law]

If it is possible, the software should have an option to take into account the team's performance so far in the season in order to generate a "fair" match schedule for FiM or MAR Region Championship or World Championship. Let me define what is team's performance and what is fair.

Team's performance can be highest OPR, weighted average OPR or season world ranking.

Fair does not mean trying to make every match as close in score as possible so that any alliance would have a fair chance of winning. Fair means no teams should have a heavier "load" than other teams. Mathematically, it will mean that the average OPRs of the opposing alliance that each team will have to face will be about the same. In this way, teams that have higher OPRs will still have a higher chance of winning their matches. I like this way because it does not actually look at the predicted score of each match based on OPR and artificially modify it to force the outcome. There is still some inherent randomness to it.

[Andrew Schreiber]

Originally Posted by Ed Law

If it is possible, the software should have an option to take into account the team's performance so far in the season in order to generate a "fair" match schedule for FiM or MAR Region Championship or World Championship. Let me define what is team's performance and what is fair.

Team's performance can be highest OPR, weighted average OPR or season world ranking.

Fair does not mean trying to make every match as close in score as possible so that any alliance would have a fair chance of winning. Fair means no teams should have a heavier "load" than other teams. Mathematically, it will mean that the average OPRs of the opposing alliance that each team will have to face will be about the same. In this way, teams that have higher OPRs will still have a higher chance of winning their matches. I like this way because it does not actually look at the predicted score of each match based on OPR and artificially modify it to force the outcome. There is still some inherent randomness to it.

What about years where OPR/metric du jour are not really applicable?

[Ed Law]

Originally Posted by Andrew Schreiber

What about years where OPR/metric du jour are not really applicable?

If FIRST wants to follow the sports model, tell me a sport where there is scoring that OPR is not applicable? The only recent game I know that does not work is 2007 Rack "N" Roll where the score goes exponentially up if you have a few tubes forming a chain. What can I say? The game may be good but the scoring is bad from spectators' viewpoint. It is too complicated. We need games and scoring that is simple to explain to visitors. I think I am going off topic.

I guess we can use win/loss, being alliance captain or be drafted in elimination round and how far they advance, which is what the ranking point system is for the Michigan district model.

If you don't like using OPR, do you have any suggestions what we can use?

[Andrew Schreiber]

Originally Posted by Ed Law

If FIRST wants to follow the sports model, tell me a sport where there is scoring that OPR is not applicable? The only recent game I know that does not work is 2007 Rack "N" Roll where the score goes exponentially up if you have a few tubes forming a chain. What can I say? The game may be good but the scoring is bad from spectators' viewpoint. It is too complicated. We need games and scoring that is simple to explain to visitors. I think I am going off topic.

I guess we can use win/loss, being alliance captain or be drafted in elimination round and how far they advance, which is what the ranking point system is for the Michigan district model.

If you don't like using OPR, do you have any suggestions what we can use?

I'm not saying OPR is a wrong metric. I'm just saying that algorithms are determined before the game is played, what if it is found that the metric chosen is not a good indicator of performance?

I'll also come out and say that any attempt to make schedules "fair" is doomed to failure in my opinion due to differing opinions on what metrics to categorize on. I claim that the only fair way to do scheduling is to not look at the team numbers at all. That way every team has the same chance of getting an easy schedule or an impossible one.

[AdamHeard]

Weighting matches based on current years ranking is inherently unfair. You are punishing a team and decreasing their chance of future success based on previous success, and rewarding teams with low success with a higher chance of future success.

In FRC efforts to make it fair should end after registration; Every team has equal opportunity to compete, build, find mentors, fund raise, etc... No competitive boost should be given to under-performing teams. They had just as much of a chance to make amazing happen as the teams that routinely do, don't punish the teams that work hard for that.

[Jared Russell]

Originally Posted by Ed Law

If FIRST wants to follow the sports model, tell me a sport where there is scoring that OPR is not applicable? The only recent game I know that does not work is 2007 Rack "N" Roll where the score goes exponentially up if you have a few tubes forming a chain.

OPR has biases in each and every year. In general, given the nature of FIRST scoring (finite number of game pieces and/or scoring locations), as the quality of teams at an event trends up, OPR for teams near the top and bottom flattens out - at some point, there are simply not enough tubes, or balls, or whatever for each team to score to their maximum ability. Compare the OPRs from the Michigan State Championship with those from a middle-tier Regional and tell me that they make sense.

Regardless, I think there is no need to balance scheduling with any consideration of robot performance or capability. Random is at least as "fair" as any other method. If you draw an easy schedule, enjoy your cakewalk but have fun getting bounced out of the playoffs if your bot isn't up to the task. Likewise, if you draw a tough schedule but the robot performs up to its abilities, you will be drafted and have a great chance to go deep into elims. IMO, the best way to be "fair" about it is to maximize the number of matches (random draws) that each team plays.