Please wait a minute...
Chin. Phys. B, 2011, Vol. 20(4): 048103    DOI: 10.1088/1674-1056/20/4/048103
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.
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 MB12 ( 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!