Quote:
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.
Quote:
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.
Quote:
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.
Quote:
|
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).
Quote:
|
6) Does the implementation allow us to vary the importance of each of the five constraints you listed in your request?
|
No.
Quote:
|
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