View Single Post
  #25   Spotlight this post!  
Unread 15-09-2007, 01:14
Tom Saxton's Avatar
Tom Saxton Tom Saxton is offline
Registered User
no team (Issaquah Robotics Society)
Team Role: Mentor
 
Join Date: Dec 2003
Rookie Year: 2003
Location: Sammamish, WA
Posts: 98
Tom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud ofTom Saxton has much to be proud of
Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm

Quote:
Originally Posted by 1885.Blake View Post
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.

Quote:
Originally Posted by 1885.Blake View Post

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?

Quote:
Originally Posted by 1885.Blake View Post

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.

Quote:
Originally Posted by 1885.Blake View Post

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.

Quote:
Originally Posted by 1885.Blake View Post

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.

Quote:
Originally Posted by 1885.Blake View Post

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.

Quote:
Originally Posted by 1885.Blake View Post

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.

Quote:
Originally Posted by 1885.Blake View Post

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
http://www.idleloop.com/
Reply With Quote