Paper:
A Heuristic Lowest Unknown-Degree Target Search Strategy Under Non-Structured Environment for Multi-Agent Systems
Chunye Wang*,** and Chen Chen*,**,
*School of Automation, Beijing Institute of Technology
5 South Zhongguancun Street, Haidian District, Beijing 100081, China
**State Key Laboratory of Intelligent Control and Decision of Complex System
Beijing 100081, China
Corresponding author
Multi-target searching is a hotspot and foundation topic in multi-agent systems research. However, most of the research is based on simple environment or known environment, which greatly limits the application of target search. In the non-structured environment, the searching result can be greatly affected by the complex terrain constraints and detectability of targets especially when we have no prior knowledge about the environment. In the paper, a novel search strategy combining maximum visibility and particle swarm optimization is proposed for the target search problem in a completely unknown and non-structural environment. The strategy utilizes the concept of visibility to describe how well the agent detects the map, and guides the agent to perform online path planning to complete the search task. In addition, considering the limited communication distance and communication bandwidth, the strategy introduces a cooperative mechanism for each agent to improve the search efficiency. Finally, in the experimental part, the search strategy is compared with the commonly used search strategies. Compared with the methods combining advantages, the proposed strategy can still achieve similar results, which proves the feasibility and efficiency of the strategy.
- [1] F. Zhou, Z. Huang, W. Liu, and L. Li, “Formation Control with Event-Triggered Strategy for Multi-Agent Systems,” J. Adv. Comput. Intell. Intell. Inform., Vol.18, No.1, pp. 71-77, doi: 10.20965/jaciii.2014.p0071, 2014.
- [2] H. Igarashi, Y. Adachi, and K. Takahashi, “Adaptive Cooperation for Multi Agent Systems Based on Human Social Behavior,” J. Adv. Comput. Intell. Intell. Inform., Vol.16, No.1, pp. 139-146, doi: 10.20965/jaciii.2012.p0139, 2012.
- [3] K. Zhang, Y. Maeda, and Y. Takahashi, “Group Behavior Learning in Multi-Agent Systems Based on Social Interaction Among Agents,” J. Adv. Comput. Intell. Intell. Inform., Vol.15, No.7, pp. 896-903, doi: 10.20965/jaciii.2011.p0896, 2011.
- [4] F. Sharifi, M. Mirzaei, Y. Zhang, and B. W. Gordon, “Cooperative multi-vehicle search and coverage problem in an uncertain environment,” Unmanned Systems, Vol.3, No.1, pp. 35-47, 2014.
- [5] A. Dhariwal, G. S. Suhkatme, and A. A. G. Requicha, “Bacterium-inspired robots for environmental monitoring,” Proc. of the 2004 Int. Conf. on Robotics and Automation, pp. 1436-1443, 2004.
- [6] Z. T. Zhang, J. J. Ni, and Z. P. Mo, “Robot Target Searching Method Based on Improved Biologically Inspired Neural Network,” Computer and Modernization, pp. 106-110+116, 2018 (in Chinese).
- [7] E. Bonabeau, M. Dorigo, and G. Theraulaz, “Swarm intelligence: from natural to artificial systems,” Oxford University Press, 1999.
- [8] K. N. Krishnanand and D. Ghose, “A glowworm swarm optimization based multi-robot system for signal source localization,” D. Liu, L. Wang, and K. C. Tan (Eds.), “Design and Control of Intelligent Robotic Systems,” pp. 49-68, Springer, 2009.
- [9] M. S. Couceiro, R. P. Rocha, and N. M. F. Ferreira, “Ensuring ad hoc connectivity in distributed search with robotic Darwinian particle swarms,” Proc. of the IEEE Int. Symp. on Safety, Security, and Rescue Robotics, pp. 284-289, 2011.
- [10] A. Bandala, E. Dadios, R. Vicerra, and L. A. Gan Lim, “Swarming Algorithm for Unmanned Aerial Vehicle (UAV) Quadrotors – Swarm Behavior for Aggregation, Foraging, Formation, and Tracking –,” J. Adv. Comput. Intell. Intell. Inform., Vol.18, No.5, pp. 745-751, doi: 10.20965/jaciii.2014.p0745, 2014.
- [11] J. M. Liu, C. H. Gong, and Y. F. Hou, “Improved particle swarm optimization algorithm motivated by application of robots searching moving-targets,” Application Research of Computers, Vol.35, No.4, pp. 1046-1051, 2018 (in Chinese).
- [12] M. S. Couceiro, P. A. Vargas, and R. P. Rocha, “Benchmark of swarm robotics distributed techniques in a search task,” Robotics and Autonomous Systems, Vol.62, No.2, pp. 200-213, 2014.
- [13] F. Yan, Y. Zhuang, M. Bai, and W. Wang, “3D Outdoor Environment Modeling and Path Planning Based on Topology-elevation Model,” Acta Automatica Sinica, Vol.36, No.11, pp. 1493-1501, 2010 (in Chinese with English abstract).
- [14] N. Wu and Q. Wu, “Cooperative Search Control Method with Multi-UAVs for Uncertain Targets,” Computer Applications and Software, Vol.2015, No.2, pp. 174-177, 2015 (in Chinese).
- [15] S. Li, L. Li, G. Lee, and H. Zhang, “A hybrid search algorithm for swarm robots searching in an unknown environment,” PLOS ONE, doi: 10.1371/journal.pone.0111970, 2014.
- [16] L. Li, L. Yang, and B. Li, “Formation control for multiple robots in uncertain environments,” Proc. of the 10th World Congress on Intelligent Control and Automation, doi: 10.1109/WCICA.2012.6359072, 2012.
- [17] Y. Cai and S. X. Yang, “A potential field-based PSO approach for cooperative target searching of multi-robots,” Proc. of the 11th World Congress on Intelligent Control and Automation, pp. 1029-1034, 2015.
- [18] J. Eguchi and K. Ozaki, “Development of Autonomous Mobile Robot Based on Accurate Map in the Tsukuba Challenge 2014,” J. Robot. Mechatron., Vol.27, No.4, pp. 346-355, doi: 10.20965/jrm.2015.p0346, 2015.
- [19] W. Meng, Z. He, R. Su et al., “Decentralized control of multi-UAVs for target search, tasking and tracking,” IFAC Proc. Volumes, Vol.47, No.3, pp. 10048-10053, 2014.
- [20] S. Doctor, G. K. Venayagamoorthy, and V. G. Gudise, “Optimal PSO for collective robotic search applications,” Proc. of the 2004 Congress on Evolutionary Computation, pp. 1390-1395, 2004.
- [21] J. Pugh and A. Martinoli, “Distributed adaptation in multi-robot search using particle swarm optimization,” Proc. of the 10th Int. Conf. on Simulation of Adaptive Behavior, pp. 393-402, 2008.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.