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.

Keywords: search simulated annealing graph partition globally optimal

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

[1]	Lorentz quantum computer Wenhao He(何文昊), Zhenduo Wang(王朕铎), and Biao Wu(吴飙). Chin. Phys. B, 2023, 32(4): 040304.
[2]	Quantum search of many vertices on the joined complete graph Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Chin. Phys. B, 2022, 31(7): 070504.
[3]	Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube Yao-Yao Jiang(姜瑶瑶), Peng-Cheng Chu(初鹏程), Wen-Bin Zhang(张文彬), and Hong-Yang Ma(马鸿洋). Chin. Phys. B, 2022, 31(4): 040307.
[4]	Single-molecular methodologies for the physical biology of protein machines Shuang Wang(王爽), Ying Lu(陆颖), and Ming Li(李明). Chin. Phys. B, 2022, 31(12): 128702.
[5]	Effects of initial states on the quantum correlations in the generalized Grover search algorithm Zhen-Yu Chen(陈祯羽), Tian-Hui Qiu(邱田会), Wen-Bin Zhang(张文彬), and Hong-Yang Ma(马鸿洋). Chin. Phys. B, 2021, 30(8): 080303.
[6]	Structure prediction, electronic, and mechanical properties of alkali metal MB₁₂ ( M= Be, Mg, Ca, Sr) from first principles Chun-Ying Pu(濮春英), Rong-Mei Yu(于荣梅), Ting Wang(王婷), Zhen-Yan X\"ue(薛振彦), Yong-Sheng Zhu(朱永胜), and Da-Wei Zhou(周大伟). Chin. Phys. B, 2021, 30(1): 017102.
[7]	On the time-independent Hamiltonian in real-time and imaginary-time quantum annealing Jie Sun(孙杰)† and Songfeng Lu(路松峰)‡. Chin. Phys. B, 2020, 29(10): 100303.
[8]	SymTopo:An automatic tool for calculating topological properties of nonmagnetic crystalline materials Yuqing He(贺雨晴), Yi Jiang(蒋毅), Tiantian Zhang(张田田), He Huang(黄荷), Chen Fang(方辰), Zhong Jin(金钟). Chin. Phys. B, 2019, 28(8): 087102.
[9]	Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method Tan Li(李坦), Shuo Zhang(张硕), Xiang-Qun Fu(付向群), Xiang Wang(汪翔), Yang Wang(汪洋), Jie Lin(林杰), Wan-Su Bao(鲍皖苏). Chin. Phys. B, 2019, 28(12): 120301.
[10]	High-pressure electrides: From design to synthesis Biao Wan(万彪), Jingwu Zhang(张静武), Lailei Wu(吴来磊), Huiyang Gou(缑慧阳). Chin. Phys. B, 2019, 28(10): 106201.
[11]	Simulation of a torrential rainstorm in Xinjiang and gravity wave analysis Rui Yang(杨瑞), Yi Liu(刘毅), Ling-Kun Ran(冉令坤), Yu-Li Zhang(张玉李). Chin. Phys. B, 2018, 27(5): 059201.
[12]	High-throughput research on superconductivity Mingyang Qin(秦明阳), Zefeng Lin(林泽丰), Zhongxu Wei(魏忠旭), Beiyi Zhu(朱北沂), Jie Yuan(袁洁), Ichiro Takeuchi, Kui Jin(金魁). Chin. Phys. B, 2018, 27(12): 127402.
[13]	Excitation of chorus-like waves by temperature anisotropy in dipole research experiment (DREX): A numerical study Hua Huang(黄华), Zhi-Bin Wang(王志斌), Xiao-Gang Wang(王晓钢), Xin Tao(陶鑫). Chin. Phys. B, 2018, 27(1): 015201.
[14]	Transitionless driving on local adiabatic quantum search algorithm Feng-guang Li(李风光), Wan-su Bao(鲍皖苏), Shuo Zhang(张硕), Xiang Wang(汪翔), He-liang Huang(黄合良), Tan Li(李坦), Bo-wen Ma(马博文). Chin. Phys. B, 2018, 27(1): 010308.
[15]	Structural optimization of Au-Pd bimetallic nanoparticles with improved particle swarm optimization method Gui-Fang Shao(邵桂芳), Meng Zhu(朱梦), Ya-Li Shangguan(上官亚力), Wen-Ran Li(李文然), Can Zhang(张灿), Wei-Wei Wang(王玮玮), Ling Li(李玲). Chin. Phys. B, 2017, 26(6): 063601.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Memoryless cooperative graph search based on the simulated annealing algorithm

Cite this article:

Online attention