**FIRST EMAIL**/Updated Alliance Pairing Algorithm

[gblake]

Originally Posted by Mark McLeod

Greetings Teams:

FIRST staff and Game Design Committee have been working to improve the method used to generate alliances for the 2008 FRC season. We are trying to make sure that the new method will produce alliances that we all will regard as appropriate. We have developed a list of criteria to define the factors that influence the algorithm results. These criteria are:

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)

Below is a link to a discussion thread on the FIRST Forum. There you will find a stand-alone algorithm that can be used to generate alliances. This particular algorithm currently meets the above criteria. We invite you to try out the program and post your feedback in this thread. Where are the holes? What issues can you find? We want to know!

http://forums.usfirst.org/forumdisplay.php?f=442

Additionally, please post comments about generating alliance pairings in general. It is FIRST's intent to produce the best solution for all teams.

Mark,

Are you implying that FIRST staff and the GDC are searching for an algorithm, or that they have chosen this algorithm from among a list of candidates solicited earlier?

If there was a solicitation, I'm surprised that I missed it.

If there is going to be a solictation, can you tell us when?

If there isn't going to be a solicitation, I'm a bit disappointed.

About this algorithm, some quick questions are listed below. If the answer to some of them is "Read the description at ___"; that answer won't hurt my feelings. I think the answers to some of these questions might turn up points that should become part of a match scheduling algorithm's requirements; and that the others might turn up points that should constrain the implementation of those scheduling requirements.

1) Does it allow one to start with a partial schedule and then compute only the rest of the schedule?

2) Does it allow users to create a schedule and then submit it to the algorithm (as input data) for initial or further annealing?

3) Does it allow users to request that each team have at least one long break (perhaps at a user selected time) (for things like giving a team a chance to have a chat with the judges)?

4a) Does it currently anticipate matches in which only 2 teams comprise an alliance, or in which more than 3 teams ally?

4b) In a long shot I'll ask if it anticipates matches comprised of more than 2 alliances?

5a) Are the results deterministic (same input always yields the same outputs)?

5b) If the results are deterministic, unless one wants to do some of the iterative activites I mentioned in questions #1 and #2, why pass out the results of this work as a black-box algorithm? Instead just run it for a large-enough number of matches (25 or so) for each possible number of teams from 6 to N (N would be 100 or so); and then just publish the resulting schedules. Those schedules can be analyzed by people and the people can adjust them to fix any glitches that survived the annealing.

6) Does the implementation allow us to vary the importance of each of the five constraints you listed in your request?

7a) Does the algorithm search forever (until a user spec'ed time limit is reached) for a globally optimal schedule, and in that search recognize when it finds a globally optimal one? If we run it for a long time do we get a better answer?

7b) When searching for an optimal schedule, if the algorithm gets stuck on a locally optimal one, does it recognize that situation and then tunnel over to some new part of the search space to look for the globally optimal one?

8) During the annealing, when evaluating whether a match should be changed, are the five criteria you listed applied in a sequence of decisions or are they the basis for a metric (aX + bY+ cZ +... = evaluation) that is compared to a threshold or is compared to the other matches' evaluations?

9) Does the algorithm insure that when teams face repeat opponents (let's say that everyone has faced everyone else already, and teams have to start facing repeat opponents), does it ensure that the team is not facing the same alliance in which it encountered those opponents the first time around? What about avoiding making a team face alliances that contain pairs of teams that were paired when the team faced them in an earlier match?

MM and I started on some similar algorithmic work earlier this year (http://www.chiefdelphi.com/forums/sh...4&postcount=42) (http://www.chiefdelphi.com/forums/sh...7&postcount=40)
(http://www.chiefdelphi.com/forums/sh...9&postcount=43) and the constraints I set for myself are listed below (I have some preliminary results for two algorithms for 2-team FTC alliances). I think that the constraints net out to be identical (or nearly so) to the five constraints you set out above; but some implementation differences might show up in the resulting schedules. That is one reason why I asked question 8 above.

Near term

• Number of teams is an integer from 8 to 32,
• Teams compete in alliance vs alliance matches
• Each alliance consists of two teams.

Want to conduct M matches in which

• No team is ever allied with the same team more than once (until after is has allied with all teams at least once)
• No team ever faces the same opposing alliance more than once (unitl after it has faced all teams at least once)
• Minimize the number of times each team is on the field with any other team (until it has been on the field with all teams once)
• Each team sees each other team on the field (as an ally or opponent) at least once (if enough matches are played)
• Maximize the minimum number of matches between any/all single team's consecutive appearances on the field.
• All teams play the same minimum number of matches.
• No team plays more than one match more than any other team.

Longer term

• Number of teams is an integer from 8 to 64
• Each alliance consists of 3 teams
• Otherwise no change from near-term constraints.

Blake
PS: I'm jealous of the folks who put together the simulated annealing, that is one of the many fun/hobby projects I have taken a bite out of in the past, but have not finished. I want to write my own routine that will rearrange graphs of connected nodes in order to minimize the greatest distance between any two connected nodes (or perhaps minimize the average of the lengths of the links connecting the nodes, or....) when the graph is projected onto a plane.

[petek]

Originally Posted by Bharat Nain

There are a couple problems with that because teams want time in between their rounds, but as you correctly pointed out, in a small-event, you really have no choice. Maybe the software should suggest the *optimal* round spacing depending on the number of teams participating and the number of matches. Either that or someone from FIRST should be responsible to tell the event organizers how to generate a proper match list. There was open communication between FIRST and the FTA's at event(at least at LI) so they were available if we needed help. I also have a feeling this is one of those problems that might never be *completely* solved, but rather we should make the best what we can.

There is another solution to this dilemma for small events: use the minimum match spacing, but set a minimum time between a team's matches and allow the number of rounds to adjust. After all, what the teams are really looking for here is having enough turnaround time between matches. It then becomes a balancing act between number of matches each team plays and the event's pace.

So, teams, would having more time between matches be worth giving up one round of matches at smaller events?

Of course with this scheduling, we'd have to reign in us FTAs and Field Managers - whose natural tendency is to drive the teams and field reset crews with whips cracking, to minimize match turnaround time...

[Richard Wallace]

Originally Posted by petek

There is another solution to this dilemma for small events: ...

So, teams, would having more time between matches be worth giving up one round of matches at smaller events?

Of course with this scheduling, we'd have to reign in us FTAs and Field Managers - whose natural tendency is to drive the teams and field reset crews with whips cracking, to minimize match turnaround time...

I'd like to echo (and rephrase) Pete's question for teams: Assuming a fixed limit on time available to run qualifying matches, would you prefer one more match with the potential for one or more short turn-around(s), or one less match without that potential?

[Joe Ross]

Originally Posted by 1885.Blake

Mark,

Are you implying that FIRST staff and the GDC are searching for an algorithm, or that they have chosen this algorithm from among a list of candidates solicited earlier?

If there was a solicitation, I'm surprised that I missed it.

If there is going to be a solictation, can you tell us when?

If there isn't going to be a solicitation, I'm a bit disappointed.

About this algorithm, some quick questions are listed below. If the answer to some of them is "Read the description at ___"; that answer won't hurt my feelings. I think the answers to some of these questions might turn up points that should become part of a match scheduling algorithm's requirements; and that the others might turn up points that should constrain the implementation of those scheduling requirements.

Mark is just the messenger posting the e-mail that FIRST forwarded. Many of these questions and comments would be better directed to the post on the official FIRST forums.

I'll attempt to answer the ones that I know from playing with the program and general knowledge of simulated annealing. In some cases the implementation that was provided doesn't have a particular option, but it seems that it would be trivial to add.

1) Does it allow one to start with a partial schedule and then compute only the rest of the schedule?

2) Does it allow users to create a schedule and then submit it to the algorithm (as input data) for initial or further annealing?

3) Does it allow users to request that each team have at least one long break (perhaps at a user selected time) (for things like giving a team a chance to have a chat with the judges)?

No.

As a small team, having the option to have a longer break where we could guarantee that there are people to talk to the judges would be great. I'm not sure I've ever seen someone suggest this, but I think it is definitely something that FIRST should consider.

4a) Does it currently anticipate matches in which only 2 teams comprise an alliance, or in which more than 3 teams ally?

4b) In a long shot I'll ask if it anticipates matches comprised of more than 2 alliances?

It has options for 2 teams per alliance and 3 teams per alliance, but not more alliances.

5a) Are the results deterministic (same input always yields the same outputs)?

The exact team numbers in each match are non-deterministic, because by design, simulated annealing uses randomization. It does seem to do a decent job at producing the same final statistics (repeated opponents, time between matches, etc).

6) Does the implementation allow us to vary the importance of each of the five constraints you listed in your request?

No.

7a) Does the algorithm search forever (until a user spec'ed time limit is reached) for a globally optimal schedule, and in that search recognize when it finds a globally optimal one? If we run it for a long time do we get a better answer?

It provides 3 different "qualities" which vary in time from a few seconds to a few minutes

[gblake]

Originally Posted by Joe Ross

The exact team numbers in each match are non-deterministic, because by design, [sic] simulated annealing.

When given identical inputs, its a pretty good bet that single-threaded computer programs only create different outputs if they purposefully invoke functions with pseudorandom characteristics.

So, I'm guessing that either this code has multiple threads that are racing one another, or that it explicitly includes pseudorandom operations as part of its use of simulated annealing methods. I don't think (however, my recollection could certainly be fuzzy...) that non-deterministic results are inherently a part of simulated annealing.

Regardless, I definitely thank you for the bottom line answer - Given identical inputs, separate invocations of this software will produce results that are likely to differ.

Thanks for that and the other answers!
Blake

[Dave Flowerday]

Originally Posted by 1885.Blake

I don't think (however, my recollection could certainly be fuzzy...) that non-deterministic results are inherently a part of simulated annealing.

You may want to check the Wikipedia article that's been mentioned a few times on simulated annealing to better understand what it does. Randomization is a very critical piece of the method. The whole point of the algorithm is that you explore (semi-)random spaces of the solution set because it is impractical to search the full solution space.

[Alan Anderson]

Originally Posted by 1885.Blake

Regardless, I definitely thank you for the bottom line answer - Given identical inputs, separate invocations of this software will produce results that are likely to differ.

The "results" in this context might mean different things to different people. The actual alliance pairings are almost certain to differ from run to run, but the statistical nature of those pairings seems to be pretty consistent. Those statistics are what the algorithm was designed to produce, and that's the "results" we've been asked to assess.

[gblake]

Originally Posted by Alan Anderson

The "results" in this context might mean different things to different people. The actual alliance pairings are almost certain to differ from run to run, but the statistical nature of those pairings seems to be pretty consistent. Those statistics are what the algorithm was designed to produce, and that's the "results" we've been asked to assess.

Yes - But. That approach makes things harder than they need to be. Once a suitable schedule exists for a large number of matches for any/each desired number of teams, you can choose to be done for the rest of eternity.

Just randomize the assignment of actual teams to the hypothetical teams in the approrpiately-sized, precomputed schedule each time an event's staff knows the final team list for the event.

I think doing this would be "best for FIRST" because teams could come to events already knowing the pattern in each pre-computed schedule and could fill in the actual team assignments quickly once the event staff announces them. That would mean that teams could create elegant tools for scouting and related matters, and could use them at events without having to waste time punching a jilliion numbers (the match pairings) into them at the events.

I think doing this would be best for FIRST because it would eliminate the need to be able to execute a program to create match schedules. Instead anyone with a text editor and a printer could produce a fine schedule quickly. A simple, optional, runs-almost-anywhere, Java program could make the process nearly painless, would be more portable than a .net program, and would ice the cake.

Blake

PS: Maybe you were asked to evaluate the statistics of a simulated annealer's outputs; but I don't recall seeing that question posted here. Scheduling approaches exist that are deterministic, and given that I prefer them (for the reasons given above), I hope you can better understand my line of questioning.

PPS: I'm not sure that the current algorithm satisfies the criteria Mark listed. It does minimize and maximize appropriate features of the schedules it produces; but I don't think that we can claim yet that it produces schedules that exhibit the minimum and maximum values of those features (requested in Mark's criteria).

We might be able to come up with a set of deterministic heuristics that do produce true minimum numbers of repeats, etc. MM and I are already reasonably close (but can not guarantee success) for the 2-teams-per-alliance version of the problem.

[gblake]

Originally Posted by Dave Flowerday

You may want to check the Wikipedia article that's been mentioned a few times on simulated annealing to better understand what it does. Randomization is a very critical piece of the method. The whole point of the algorithm is that you explore (semi-)random spaces of the solution set because it is impractical to search the full solution space.

Dave,

It appears my recollection was rather fuzzy, and at the same time a bit correct.

In general, folks using the term "simulated annealing", almost always are referring to both the metric simulated annealers use to evaluate candidate solutions and the typical pseudo-random searching process used to generate those candidate solutions.

On the other hand, it is only that metric, and not the searching process, that gives the method its name. Using a pseudo-random exploration of the search space is just one way to explore it.

However, by doing the suggested reading I was reminded that using a deterministic heuristic to generate candidate solutions would be a very rare thing to combine with a simulated annealing metric. Thanks.

I think I was wise to insert the "fuzzy recollection" escape hatch into my earlier post.

Blake

[Tom Saxton]

Originally Posted by 1885.Blake

About this algorithm, some quick questions are listed below. If the answer to some of them is "Read the description at ___"; that answer won't hurt my feelings.

I posted a description of the scheduling problem and the solution Cathy and I developed on our team web site in April:

http://www.issaquahrobotics.org/MatchMaker/

This is the article that describes the general algorithm used:

http://grids.ucs.indiana.edu/courses/xinformatics/Scientific%20American%20Analysis%20Algorithm%20of% 20the%20Gods%20March%201997.htm


Most of the questions have been answered correctly. I'll just answer the ones not already covered.

Originally Posted by 1885.Blake

4b) In a long shot I'll ask if it anticipates matches comprised of more than 2 alliances?

It doesn't handle that now, but there are only a few bits of code that would need to be adjusted to accommodate more alliances. Are duplicated opponents all the same for accounting purposes, or does it matter which opposing alliance they are on? How should alliance position balancing be generalized?

Originally Posted by 1885.Blake

5a) Are the results deterministic (same input always yields the same outputs)?

No, we intentionally used a randomly seeded pseudorandom number generator. Even if we didn't, the results would differ from one OS version to another.

Originally Posted by 1885.Blake

6) Does the implementation allow us to vary the importance of each of the five constraints you listed in your request?

Surprisingly, most of the criteria are orthogonal, that is they have no effect on each other.

The minimum number of matches between each team's successive matches is a fixed rule, no schedule that breaks that rule is even considered.

The minimum number of surrogate teams is just a matter of structuring the match so that only one match at the end has surrogate teams to fill in any odd slots for the last team getting their last match.

The red/blue balancing is done after the schedule is computed by swapping red/blue sides, so it has no effect on the other criteria.

The only criteria that play against each other is avoiding duplicate opponents and avoiding duplicate partners. Slightly extra weight is given to avoiding duplicate partners.

Originally Posted by 1885.Blake

7a) Does the algorithm search forever (until a user spec'ed time limit is reached) for a globally optimal schedule, and in that search recognize when it finds a globally optimal one? If we run it for a long time do we get a better answer?

The "quality" setting determines a number of randomly generated schedules that will be considered, 100,000; 750,000; or 5,000,000. The program runs for however long that takes, so the running time will vary according to the speed of the computer, but the quality of the results will not be afffected by the machine.

Originally Posted by 1885.Blake

7b) When searching for an optimal schedule, if the algorithm gets stuck on a locally optimal one, does it recognize that situation and then tunnel over to some new part of the search space to look for the globally optimal one?

The algorithm can get out of a local minimum. The Scientic American article explains how that works.

Originally Posted by 1885.Blake

8) During the annealing, when evaluating whether a match should be changed, are the five criteria you listed applied in a sequence of decisions or are they the basis for a metric (aX + bY+ cZ +... = evaluation) that is compared to a threshold or is compared to the other matches' evaluations?

There is a scoring function that rates the duplication criteria; that's used to evaluate the schedules.

Originally Posted by 1885.Blake

9) Does the algorithm insure that when teams face repeat opponents (let's say that everyone has faced everyone else already, and teams have to start facing repeat opponents), does it ensure that the team is not facing the same alliance in which it encountered those opponents the first time around? What about avoiding making a team face alliances that contain pairs of teams that were paired when the team faced them in an earlier match?

No specific consideration is given to that, but the randomness of the algorithm should make it pretty unlikely for any team to see the same alliance multiple times. For the data sets I've looked at, there's so little partner duplication that full duplicate alliances just don't happen. If there are cases where that happens, I'd like to see an example.

[Tom Saxton]

Originally Posted by 1885.Blake

I think doing this would be best for FIRST because it would eliminate the need to be able to execute a program to create match schedules. Instead anyone with a text editor and a printer could produce a fine schedule quickly. A simple, optional, runs-almost-anywhere, Java program could make the process nearly painless, would be more portable than a .net program, and would ice the cake.

It's actually not a .Net program. It's written in very portable C. The download includes both Windows and Mac OS X versions. It would be easy to recompile it for any platform that supports an ANSI C compiler.

I couldn't figure out a way to get the latest version of Visual Studio to produce an executable that doesn't require the very latest version of the C runtime libraries. That's a problem with VC, not an inherent dependency of the program.

It's pretty easy to generate the schedule with our program: just give it the list of team numbers in a text file, hit enter, and wait a few seconds or a minute for the schedule to pop out. It you don't like that one, do it again.

[Phil Mack]

I used the program to generate schedules with a variety of parameters... 12 to 144 teams playing 7 to 10 rounds with minimum match separation between 1 and the maximum possible separation. Each of these nearly 6700 schedules was made using the "fair" setting, but only for lack of processing power. I then used a variety of tools to aggregated the data into a spreadsheet.

Interesting trends I noticed:
-The program was able to produce optimal schedules whenever the match separation was at least 5 less than the maximum possible separation. It usually produced optimal schedules when the minimum separation was 4 less then the maximum.
-The program created the worst schedules when team size was a multiple of 6.

I have attached the aggregated raw data spreadsheets. If anyone is interested in the entire data set, contact me with a way to receive a large file, and I'll give it to you.
~Phil

[Tom Saxton]

Originally Posted by Phil Mack

I used the program to generate schedules with a variety of parameters... 12 to 144 teams playing 7 to 10 rounds with minimum match separation between 1 and the maximum possible separation.

Interesting analysis. We actually did a similar, but smaller, data set like this when we were testing performance optimizations to make sure that those changes didn't alter the resulting schedules.

Originally Posted by Phil Mack

Interesting trends I noticed:
-The program was able to produce optimal schedules whenever the match separation was at least 5 less than the maximum possible separation. It usually produced optimal schedules when the minimum separation was 4 less then the maximum.

It would be interesting to see how much that improves using good or best. If we could divide up the work across several computers, it could be done in a day or two.

Originally Posted by Phil Mack

-The program created the worst schedules when team size was a multiple of 6.

If the number of teams is a multiple of 6, and the minimum separation is set to the maximum value, every team plays with the same five teams in every match. No team can move to an earlier match without breaking the rule, and no team can move to a later match without forcing another team to an earlier match. So, the only thing that can be done is swap the alliances around in the each group of six. This would be true of any algorithm given these constraints.

[Phil Mack]

Originally Posted by Tom Saxton

If the number of teams is a multiple of 6, and the minimum separation is set to the maximum value, every team plays with the same five teams in every match.

Good point... i just missed the obvious.

~Phil

[Rich Kressly]

Originally Posted by 1885.Blake

...

I think doing this would be "best for FIRST" because teams could come to events already knowing the pattern in each pre-computed schedule and could fill in the actual team assignments quickly once the event staff announces them. That would mean that teams could create elegant tools for scouting and related matters, and could use them at events without having to waste time punching a jilliion numbers (the match pairings) into them at the events.

...

There's one very practical issue when looking to implement scouting tools like this. It's not uncommon to go to an FRC event and have the actual team list differ slightly from the most recently published team list on FIRSTs and regional websites. This is even more true when you attend offseasons. Since 2001 in helping to develop scouting systems for teams (very low tech ones most of the time) we always built in the flexibility to add, delete, or switch teams. I've always found that doing lots of reasearch on teams ahead of time was good, but showing up at the event with a little flexibility built into your system was even better. It would be frustrating to develop an elegant tool, only to have to make changes at the event anyway. My .02