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.

[ajd]

Why is this a programming challenge? It seems like creating the specification is the hard part, not the actual coding.

[EricH]

Originally Posted by ajd

Why is this a programming challenge? It seems like creating the specification is the hard part, not the actual coding.

Well...

You have variable numbers of teams.
You have a number of different parameters that the user needs to input. (Match cycle time, number of matches per team, break times--and all of those will vary slightly.)
You have the 7 items in the challenge statement, which will have different weightings.
You need to make it user-friendly.

Your program needs to handle every one of those items, and handle it cleanly and effectively.

That's why it's a programming problem (aside from the standard "Everything's a programming problem" jokes.)

The other thing is that the challenge was a 12-hour time duration, which greatly adds to the challenge.

[gyroscopeRaptor]

IMO, the only restriction for team age should be that rookies change their team color less. I'm speaking from personal experience that changing bumpers can be time-consuming and it would be easier if they changed them less- easier on the team and they would have more time to iron out the kinks in their system.

[Ed Law]

Originally Posted by gyroscopeRaptor

IMO, the only restriction for team age should be that rookies change their team color less. I'm speaking from personal experience that changing bumpers can be time-consuming and it would be easier if they changed them less- easier on the team and they would have more time to iron out the kinks in their system.

Ah bumpers, my favorite topic. Do you know that the rules for bumpers are three and a half pages long? You can easily use up 4 weeks just to design and build bumpers. That was how long it took us last year. Fortunately it was done in parallel with doing the robot.

About changing bumpers, in our rookie year, our bumper would take one person about 5-10 minutes to remove and re-install. Fortunately that was Lunacy and we didn't need to change bumper yet. We only had to do that to pass through a standard 30" wide door. In our second year, we had a better design but it would still take one person 1-2 minutes to change to a different color bumper. Last year, our latest bumper design only takes one person 20-30 seconds to change. WIth 3 people, we can do it easily in 5-10 seconds. We really like the design so we probably will not change it unless FIRST comes up with new bumper rules that are 6 pages long.

[Ed Law]

Sorry I changed the subject. Back to match schedules.

I think it is very important that the algorithm will produce the same answer no matter how many times you run it. The current one that FIRST use does not produce the same results each time, which leads people to suspect others may run it until they like the match schedule.

Even if it produce the same results each time, how do we consider assigning real team numbers to the placeholder numbers? People can still reassign it until they like it. I personally don't think people will do that, but my proposal earlier will take care of this problem if the average strength of opponents is about the same for everyone, then there is no difference.