Quantum evolutionary algorithm for multi-robot coalition formation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantum evolutionary algorithm for multi-robot coalition formation

Full text

Pdf (356 KB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

SESSION: Full papers table of contents

Pages 295-302

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Zhiyong Li	Computer and Communication, Hunan University, Changsha, China
Bo Xu	School of Computer and Communication, Hunan University, Changsha, China
Lei Yang	School of Computer and Communication, Hunan University, Changsha, China
Jun Chen	Office Of Student Admission Of Hunan University, Changsha, China
Kenli Li	School of Computer and Communication, Hunan University, Changsha, China

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 45, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543874 What is a DOI?

ABSTRACT

Coalition formation is an important cooperative method in Multi-Robot System, which has been paid more and more attention. However, efficient algorithm for multi-robot coalition is lack of various real-world applications in dynamic unknown environment. In such cases, the optimization algorithm has to track the changing optimum as close as possible, rather than just finding a static appropriate solution. In this paper, The Quantum Evolutionary Algorithm is proposed for solving this problem, where a skillful Quantum probability representation of chromosome coding strategy is designed to adapt to the complexity of the multi-robot coalition formation problem. Furthermore, a strategy for updating quantum gate using the evolutionary equation is employed to avoid the premature convergence. Experiments results show that the proposed algorithm could solve the multi-robot coalition formation problem effectively and efficiently, and the proposed algorithm is valid and superior to other related methods as far as the stability and speed of convergence are concerned.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
	2	Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
	3	A. Billionnet , M. C. Costa , A. Sutter, An efficient algorithm for a task allocation problem, Journal of the ACM (JACM), v.39 n.3, p.502-518, July 1992 [doi>10.1145/146637.146646]
	4	B. Gerkey and M. J. Mataric´, "A framework for studying multi-robot task allocation," in Proc. Multi-Robot Syst.: From Swarms to Intell Automata, 2003, vol. 2, pp. 15--26.
	5	L. E. Parker, "ALLIANCE: An architecture for fault tolerant multi-robot cooperation," IEEE Trans. Robot. Autom. vol. 14, no. 2, pp.220--240, Apr. 1998.
	6	Brian P. Gerkey , Maja J. Matarić, Murdoch: publish/subscribe task allocation for heterogeneous agents, Proceedings of the fourth international conference on Autonomous agents, p.203-204, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337369]
	7	Barry Brian Werger , Maja J. Mataric, Broadcast of local eligibility: behavior-based control for strongly cooperative robot teams, Proceedings of the fourth international conference on Autonomous agents, p.21-22, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.336621]
	8	M. Bernardine Dias , Anthony Stentz, Traderbots: a new paradigm for robust and efficient multirobot coordination in dynamic environments, Carnegie Mellon University, Pittsburgh, PA, 2004
	9	B. P. Gerkey and M. J. Mataric, "A formal analysis and taxonomy of task allocation in multi-robot systems," Int. J. Robot. Res., vol. 23, no.9, pp. 939--954, 2004.
	10	Hui-Yi Liu, Jin-Feng Chen. Multi-Robot Cooperation Coalition Formation Based on Genetic algorithm {J}. Proceedings of the Fifth International Conference on Machine Learning and Cybernetics,2006, 06:85--89
	11	Xia Na, Jiang Jianguo, Wei Xing, Zhang Ling. Searching for Agent Coalition for Single Task Using Improved Ant Colony Algorithm {J}. Journal of Computer Research and Development, 2005, 42(5):734--739.
	12	Zhang Guofu, Jiang Jianguo, Xia Na. Solutions of Complicated Coalition Generation Based on Discrete Particle Swarm Optimization {J}. Acta Electronica Sinica, 2007, 35(2):323--327.
	13	Yan Shen, Bing Guo, Dianhui Wang. Optimal Coalition Structure Based on Particle Swarm Optimization Algorithm in Multi-Agent System .Proceedings of the 6th World Congress on Intelligent Control and Automation. 2006, pp.2494--2497.
	14	Lovekech Vig and Julie A. Adams. Multi-Robot Coalition Formation {J}. IEEE Transactions on Robotics, 2006, 22(4):1552--3098.
	15	Garcia, E., Jimenez. M.A., De Santos, P.G., Armada, M.; The Evolution of Robotics Research. Robotics & Automation Magazine, IEEE, 2007, 14(1):90--103.
	16	Jim Pugh and Alcherio Martinoli. The Cost of Reality: Effects of Real-World Factors on Multi-Robot Search {J} IEEE International Conference on Robotics and Automation, 2007, pp.397--404
	17	Evolutionary approaches to dynamic environments-Updated survey," in Proc. GECCO Workshop Evol. Algorithms for Dynamic Optimization Problems, 2001, pp. 27--30.
	18	K.-H. Han and J.-H Kim, "Quantum--inspired evolutionary algorithm for a class of combinatorial optimization," IEEE Trans. Evolutionary Computation, vol. 6, pp. 580--593, 2002
	19	T. Hey, "Quantum computing: An introduction," in Computing & Control Engineering Journal. Piscataway, NJ: IEEE Press, June 1999,vol. 10, no. 3, pp. 105--112
	20	K.-H. Han and J.-H Kim, "Genetic quantum algorithm and its application to combinatorial optimization problem." Proc. IEEE International Congress on Evolutionary Computation, USA, 2000, pp. 1354--1360.