Updated Alliance Pairing Algorithm

[Matt Pilotte]

Hello FRC Teams,

FIRST staff and Game Design Committee have been working to improve the method used to generate alliances for the 2008 FRC season. Our goal is 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)

Attached is 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!

For those of you with a thirst for details, this algorithm is based on the simulated annealing method. More about this methodology can be learned by reading these articles from Scientific American and the Society for Amateur Scientists.

Scientific American Article
Society for Amateur Scientist Article

Additionally, we welcome any comments in this thread about generating alliance pairings in general. It is FIRST’s intent to produce the best solution for all teams.

Thanks to all, and good luck in 2008!

-Matt Pilotte
FRC Electrical Engineer

[Richard]

Thanks for posting on this topic, Matt. The criteria seem correct to me, and absence of a criterion based on presumed team strength is a major improvement vs. 2007.

Can we view/download the algorithm now? The box frame say pending approval.

[Matt Pilotte]

Can we view/download the algorithm now? The box frame say pending approval.

Attachment approved, sorry for the confusion.

[Steve W]

One of the issues from 2 years ago was that there was too much time given between matches which lowered the amount of teams that you could face. Would it not be better to have a minimum number of matches that could be played before you could play again to allow for a greater mixing of teams?

Thank you FIRST for communicating with us early in the season.

[sciencewhiz]

Just in case anyone has trouble running the program, it requires .net framework 2.0.

There is an in depth discussion going on at the Chief Delphi forums: http://www.chiefdelphi.com/forums/sh...threadid=58733

[bespenship]

Would it be possible to get the source code for your implementation of the algorithms? I'm as interested in how you implemented it as what it does.

Just a polite request - I understand if you don't want to share your code.

Cheers,
-Brent-

[Matt Pilotte]

I appreciate your enthusiasm! Unfortunately we will not be providing the source code for the algorithm. Our intent is to understand where the pitfalls of this algorithm exist, and to correct as many issues as possible prior to the season. We also want to be clear to the FRC community the criteria we have chosen for the algorithm in an effort to avoid confusion about how alliances are created.

Additional detail on simulated annealing can be found in the articles linked in my original post. Also, a quick search turned up some pseudo-code on Wikipedia which may be of use.

http://en.wikipedia.org/wiki/Simulated_annealing

Regards.

[1885.blake]

Unfortunately we will not be providing the source code for the algorithm.

Why?

I intend to publish the Java source code for the algorithm I am working on and I intend to do that so that it can be part of a GUI-oriented client-server setup that allows teams to develop their own clients or offer improvements to the server side.

I am expecting that those clients will be used analyze electronically supplied copies of the schedule and match results as the teams plan their alliance strategies and do other scouting duties. I will supply a decent initial client.

I would think that this sort of thing would be in line with a volunteer-developed match algortihm of any sort.

Blake

[1885.blake]

Folks in the Chief Delphi thread about this topic say that the info below is better posted here.

Does the existance of this thread imply that FIRST staff and the GDC are currently 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.

If work like this needs to be done, let's tap into the entire community's brainpower. Many of us are individually pretty clever. All of us together are very, very clever.

Blake

[Matt Pilotte]

FIRST and the GDC are actively looking for a new algorithm to use for generating alliances. The algorithm attached in my original post currently is the best solution we have that meets the criteria.

There is no doubt that other algorithms exist that could be used for alliance generation. We are open to evaluating those algorithms, Tom and Cathy Saxton's MatchRater tool (included in the attachment above) can be used for this task.

The purpose of this thread is to create a discussion about generating alliances. Are the criteria proposed by the GDC sufficient? If not, what are some alternatives? Are there issues with proposed algorithm?