|
|
|
| Algebra Property and Application of Coalition Structure Graph |
| LIU Jing-Lei, ZHANG Wei, WANG Ling-Ling |
| School of Computer, Yantai University, Yantai 264005 |
|
|
|
|
Abstract The space of coalition structure is abstracted as a coalition structure graph, and two operators, union and intersection, are defined. Thus, all the coalition structures form an algebra structure, coalition structure lattice (CSL). In order to simplify the study of CSL algebra property, the integer split graph is introduced, and a mapping relation F from coalition structures to integer splits and an equivalent relation EF based on F are constructed. Therefore, during searching optimal coalition structure in CSL, the current optimal value and average value are used as prune function. When the upper bound of some equivalent class is lower than the prune function, a large number of coalition structures in equivalent class are pruned. Finally, better dynamic programming (BDP) algorithm is given, and the validity of the proposed algorithm is proved by experimental analysis. Furthermore, the results indicate that BDP decreases 43% searching numbers than dynamic programming when there are 20 agents.
|
|
Received: 24 November 2008
|
|
|
|
|
|
［1］Liu Jinglei, Tong Xiangrong, Zhang Wei. A Kind of Method for Quick Constructing Optimal Coalition Structure. Computer Engineering & Application, 2006, 42(4): 35-44 (in Chinese)(刘惊雷,童向荣,张 伟.一种快速构建最优联盟结构的方法.计算机工程与应用, 2006, 42(4): 35-44)
［2］ Su Shexiong, Hu Shanli, Lin Chaofeng, et al. A Coalition Generation Algorithm Based on Local Optimum. Journal of Computer Research and Development, 2007, 44(2): 277-281 (in Chinese)(苏射雄,胡山立,林超峰,等．基于局部最优的联盟结构生成算法．计算机研究与发展, 2007, 44(2): 277-281)
［3］ Zhang Xinliang, Shi Chunyi. A Dynamic Formation Algorithm of MultiAgent Coalition Structure. Journal of Software, 2007, 18(3): 574 -581 (in Chinese)(张新良,石纯一．多Agent联盟结构动态生成算法．软件学报, 2007, 18(3): 574-581)
［4］ Rahwan T, Jennings N R. An Improved Dynamic Programming Algorithm for Coalition Structure Generation // Proc of the 7th International Conference on Autonomous Agents and MultiAgent Systems. Estoril, Portugal, 2008, Ⅲ: 1417-1420
［5］ Rahwan T, Ramchurn S D, Dang V D, et al. NearOptimal Anytime Coalition Structure Generation // Proc of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India, 2007: 2365-2371
［6］ Rahwan T, Ramchurn S D, Giovannucci A, et al. Anytime Optimal Coalition Structure Generation // Proc of the 22nd Conference on Artificial Intelligence. Vancouver, Canada, 2007: 1184-1190
［7］ Dang V D, Jennings N R. Generating Coalition Structures with Finite Bound from the Optimal Guarantees // Proc of the 3rd International Joint Conference on Autonomous Agents and MultiAgent Systems. New York, USA, 2004: 564-571
［8］ Shehory O, Kraus S. Task Allocation via Coalition Formation among Autonomous Agents // Proc of the 14th International Joint Conference on Artificial Intelligence. Montreal, Canada, 1995: 655-661
［9］ Shehory O, Kraus S. Methods for Task Allocation via Agent Coalition Formation. Artificial Intelligence, 1998, 101(1/2): 165-200
［10］ Sandholm W, Larson K, Andersson M,et al. Coalition Structure Generation with Worst Case Guarantees. Artificial Intelligence, 1998, 111(1/2): 209-238 |
|
|
|
2009, Vol. 22 
