INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
Prev
Next
|
|
|
Memoryless cooperative graph search based on the simulated annealing algorithm |
Hou Jian(候健), Yan Gang-Feng(颜钢锋), and Fan Zhen(樊臻)† |
Department of Systems Science and Engineering, Zhejiang University, Hangzhou 310027, China |
|
|
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.
|
Received: 24 October 2010
Revised: 16 November 2010
Accepted manuscript online:
|
PACS:
|
81.40.Ef
|
(Cold working, work hardening; annealing, post-deformation annealing, quenching, tempering recovery, and crystallization)
|
|
05.65.+b
|
(Self-organized systems)
|
|
93.85.Bc
|
(Computational methods and data processing, data acquisition and storage)
|
|
Cite this article:
Hou Jian(候健), Yan Gang-Feng(颜钢锋), and Fan Zhen(樊臻) Memoryless cooperative graph search based on the simulated annealing algorithm 2011 Chin. Phys. B 20 048103
|
[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
|
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|