Quote:
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.