Memoryless cooperative graph search based on the simulated annealing algorithm

doi:10.1088/1674-1056/20/4/048103

摘要/Abstract

摘要： We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter--radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.

Abstract: We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter—radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.

Key words: search, simulated annealing, graph partition, globally optimal

中图分类号: (Cold working, work hardening; annealing, post-deformation annealing, quenching, tempering recovery, and crystallization)

81.40.Ef

05.65.+b (Self-organized systems) 93.85.Bc (Computational methods and data processing, data acquisition and storage)

候健, 颜钢锋, 樊臻. Memoryless cooperative graph search based on the simulated annealing algorithm[J]. 中国物理B, 2011, 20(4): 48103-048103.

Hou Jian(候健), Yan Gang-Feng(颜钢锋), and Fan Zhen(樊臻) . Memoryless cooperative graph search based on the simulated annealing algorithm[J]. Chin. Phys. B, 2011, 20(4): 48103-048103.

参考文献 27

[1]	Koopman B O 1946 Operations Evaluations Group Report
[2]	Stone L D 1975 Theory of Optimal Search (New York: Academic Press) p. 1
[3]	Ieong S, Lambert N, Shoham Y and Brafman R 2007 Proceedings of the National Conference on Artificial Intelligence, British Columbia, Canada, July 22--26, 2007 p. 1158
[4]	Liu F and Xu X P 2007 Chin. Phys. 16 282
[5]	DasGupta B, Hespanha J P, Riehl J R and Sontag E 2006 Nonlinear Anal. Theor. E 65 1773
[6]	Riehl J R and Hespanha J P 2005 Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, Seville, Spain, December 12--15, 2005 p. 2188
[7]	Riehl J R, Collins G E and Hespanha J P 2007 Proceedings of the 2007 IEEE Conference on Decision and Control, New Orleans, USA, December 12--14, 2007 p. 2998
[8]	Sujit P B and Ghose D 2004 IEEE. T. Aero. Elec. Sys. E 40 491
[9]	Chung T H, Kress M and Royset J O 2009 Proceedings of the 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan, May 12--17, 2009 p. 243
[10]	Polycarpou M M, Yang Y and Passino K M 2001 Proceedings of the 2001 IEEE International Symposium on Intelligent Control, Mexico City, Mexico, September 5--7, 2001 p. 1
[11]	Riehl J R and Hespanha J P 2007 Proceedings of the 2007 American Control Conference, New York, USA, July 9--13, 2007 p. 2557
[12]	Avetisyan V V 2002 J. Comput. Sys. Sci. Int. E 41 57
[13]	Blum T and Kohlbacher O 2008 Bioinformatics E 24 2108
[14]	Vlachos M, Kozat S S and Yu P S 2010 Acm. T. Web. E 4 1
[15]	Guruprasad K R and Ghose D 2007 Proceedings of the 1st International Conference on Advances in Control and Optimization of Dynamical Systems, Bangalore, India, February 1--2, 2007 p. 380
[16]	Sujit P B and Ghose D 2004 Proceedings of the 2004 American Control Conference, Boston, USA, June 30--July 2, 2004 p. 5564
[17]	Göbel F and Jagers A A 1974 Stoch. Proc. Appl. E 2 311
[18]	Lovász L 1993 Combinatorics E 2 1
[19]	Hanusse N, Kranakis E and Krizanc D 2004 Discrete Appl. Math. E 137 69
[20]	Hanusse N, Kavvadias D, Kranakis E and Krizanc D 2008 Theor. Comput. Sci. E 402 190
[21]	Zhao Z J, Zheng S L, Xu C Y and Kong X Z 2007 Chin. Phys. 16 1619
[22]	Kirkpatrick S 1984 J. Stat. Phys. E 34 975
[23]	Wang L and Smith K 1998 IEEE T. Neural Network E 9 716
[24]	Aarts E H L and Laarhoven P J M 2008 Stat. Neerl. E 43 31
[25]	Alrefaei M H and Andradóttir S 1999 Manage. Sci. E 45 748
[26]	Kashyap A, Basar T and Srikant R 2007 Algorithmica E 43 1192
[27]	Romeo F and Sangiovanni-Vincentelli A 1991 Algorithmica E 6 302 endfootnotesize