TY - GEN
T1 - Anytime optimal coalition structure generation
AU - Rahwan, Talal
AU - Ramchurn, Sarvapali D.
AU - Dang, Viet D.
AU - Giovannucci, Andrea
AU - Jennings, Nicholas R.
PY - 2007
Y1 - 2007
N2 - A key problem when forming effective coalitions of autonomous agents is determining the best groupings, or the optimal coalition structure, to select to achieve some goal. To this end, we present a novel, anytime algorithm for this task that is significantly faster than current solutions. Specifically, we empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents), using much less memory (O(2n) instead of 0(3n) for n agents). Moreover, our algorithm is the first to be able to find solutions for more than 17 agents in reasonable time (less than 90 minutes for 27 agents, as opposed to around 2 months for the best previous solution).
AB - A key problem when forming effective coalitions of autonomous agents is determining the best groupings, or the optimal coalition structure, to select to achieve some goal. To this end, we present a novel, anytime algorithm for this task that is significantly faster than current solutions. Specifically, we empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents), using much less memory (O(2n) instead of 0(3n) for n agents). Moreover, our algorithm is the first to be able to find solutions for more than 17 agents in reasonable time (less than 90 minutes for 27 agents, as opposed to around 2 months for the best previous solution).
UR - http://www.scopus.com/inward/record.url?scp=36348988449&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=36348988449&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:36348988449
SN - 1577353234
SN - 9781577353232
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 1184
EP - 1190
BT - AAAI-07/IAAI-07 Proceedings
T2 - AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference
Y2 - 22 July 2007 through 26 July 2007
ER -