|
|
|
![]() |
|
|||||||
|
||||||||
|
|
Thread Tools |
Rating:
|
Display Modes |
|
#12
|
||||
|
||||
|
Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
Quote:
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
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.Last edited by gblake : 14-09-2007 at 12:31. |
| Thread Tools | |
| Display Modes | Rate This Thread |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Best Alliance in the Alliance Era of FIRST | Corey Balint | General Forum | 28 | 05-09-2006 20:14 |
| Updated Manuals at FIRST | dez250 | General Forum | 0 | 26-01-2004 19:53 |
| **IMPORTANT FIRST EMAIL BLAST**/Updated Bill of Materials | Winged Globe | FIRST E-Mail Blast Archive | 0 | 08-01-2004 13:49 |
| Alliance pairing disaster at NYC | patrickrd | General Forum | 3 | 24-03-2002 10:39 |
| Pairing Drill Motors to Chiaphua | Matt_White | Motors | 15 | 16-01-2002 13:15 |