Motion-encoded Gravitational Search Algorithm for moving target search using UAVs

Document Type : Original Article

Authors

1 Master's student, Computer Department, Lorestan University, Lorestan, Iran

2 Assistant Professor, Computer Department, Lorestan University, Lorestan, Iran

Abstract

In this paper, a new algorithm called Motion Coding Gravitational Search Algorithm (MGSA) is proposed to find a moving target using a unmanned aerial vehicles (UAVs). Using the laws of physics and the properties of the earth, each dimension has its own equation of motion based on the type of variable. Many traditional exploratory methods can not achieve the desired solution in high-dimensional spaces to search for a moving target. The optimization process of the gravitational search algorithm, which is based on the gravitational interaction between particles, the dependence on the distance and the relationship between mass values, and the fit calculation, make this algorithm unique. In this paper, the proposed MGSA algorithm is proposed to solve the path complexity challenge problem in order to find the moving target through motion coding using UAVs. A set of particles in the path of search for the target will reach a near-optimal solution through the gravity constant, weight factor, force and distance, which evolved with many search scenarios in a GSA algorithm. This coded method of motion makes it possible to preserve important particle properties, including the optimum global motion. The results of the existing simulation show that the proposed MGSA improves the detection performance by 12% and the time performance by 1.71 times compared to APSO. It works better.

Keywords

Smiley face

References

[1] F. Bourgault, T. Furukawa, & H. F. Durrant-Whyte, “Optimal Search for a Lost Target in a Bayesian World,” in Field and Service Robotics, vol. 24, S. Yuta, H. Asama, E. Prassler, T. Tsubouchi, and S. Thrun, Eds. Berlin/Heidelberg: Springer-Verlag, pp. 209-222, 2010.
[2] S. F. Ochoa & R. Santos, “Human-centric wireless sensor networks to improve information availability during urban search and rescue activities,” Inf. Fusion, vol. 22, pp. 71-84, 2015.
[3] M. D. Phung & Q. P. Ha, “Motion-encoded particle swarm optimization for moving target search using UAVs,” Appl. Soft Comput., vol. 97, pp. 106-705, 2020.
[4] Raap Manon, Meyer-Nieberg Silja, Pickl Stefan, & Zsifkovits Martin, “Aerial Vehicle Search-Path Optimization,” J. Optim. Theory Appl., 2017.
[5] F. Farivar & M. A. Shoorehdeli, “Stability analysis of particle dynamics in gravitational search optimization algorithm,” Inf. Sci., vol. 33, pp. 25-43, 2016.
[6] E. Rashedi, H. Nezamabadi-pour, & S. Saryazdi, “GSA: A Gravitational Search Algorithm,” Inf. Sci., vol. 179, no. 13, pp. 2232-2248, 2011.
[7] S. Tabatabaei, “A new gravitational search optimization algorithm to solve single and multiobjective optimization problems,” J. Intell. Fuzzy Syst., vol. 26, no. 2, pp. 993-1006, 2014.
[8] D. Pelusi, R. Mascella, & L. Tallini, “Revised Gravitational Search Algorithms Based on Evolutionary-Fuzzy Systems,” Algorithms, vol. 10, no. 2, p. 44, 2017.
[9] S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, & J. M. de la Cruz, “Ant colony optimization for multi-UAV minimum time search in uncertain domains,” Appl. Soft Comput., vol. 62, pp. 789-806, 2018.
[10] R. Peng, “Joint routing and aborting optimization of cooperative unmanned aerial vehicles,” Reliab. Eng. Syst. Saf., vol. 177, pp. 131-137, 2018.
[11] M. Garraffa, M. Bekhti, L. Letocart, N. Achir, & K. Boussetta, “Drones path planning for WSN data gathering: A column generation heuristic approach,” pp. 1-6, 2018.
[12] B. J. Olivieri de Souza & M. Endler, “Evaluating flight coordination approaches of UAV squads for WSN data collection enhancing the internet range on WSN data collection,” J. Internet Serv. Appl., vol. 11, no. 1, 2020.
[13] K. E. Trummel & J. R. Weisinger, “Technical Note—The Complexity of the Optimal Searcher Path Problem,” Oper. Res., vol. 34, no. 2, pp. 324-327, 1986.
[14] D. S. Bernstein, R. Givan, N. Immerman, & S. Zilberstein, “The Complexity of Decentralized Control of Markov Decision Processes,” Math. Oper. Res., vol. 27, no. 4, pp. 819-840, 2010.
[15] R. M. C. Santiago, A. L. De Ocampo, A. T. Ubando, A. A. Bandala, & E. P. Dadios, “Path planning for mobile robots using genetic algorithm and probabilistic roadmap,” pp. 1-5, 2017.
[16] G. Flores-Caballero, A. Rodriguez-Molina, M. Aldape-Perez, & M. G. Villarreal-Cervantes, “Optimized Path-Planning in Continuous Spaces for Unmanned Aerial Vehicles Using Meta-Heuristics,” IEEE Access, vol. 8, pp. 176774-176788, 2020.
[17] M. Gendreau & J.-Y. Potvin, Eds., "Handbook of Metaheuristics," vol. 146. Boston, MA: Springer US, 2010.
[18] ‏I. H. Osman & G. Laporte, “Metaheuristics: A bibliography,” Ann. Oper. Res., vol. 63, no. 5, pp. 511-623, 1996.
[19] D.B Fogel, & Z Mich, "Handbook of Evolutionary Computation," Ann. Oper. Res., vol. 87, no. 9, pp. 251-320, 2021.
[20] A. Y. Zomaya, Ed., "Handbook of Nature-Inspired and Innovative Computing," Boston: Kluwer Academic Publishers, 2010.
[21] E. Rashedi, E. Rashedi, & H. Nezamabadi-pour, “A comprehensive survey on gravitational search algorithm,” Swarm Evol. Comput., vol. 41, pp. 141-158, 2018.
[22] C. Sean M., “Spacetime and Geometry: An Introduction to General Relativity,” ResearchGate. Appl. Soft Comput., vol. 97, pp. 207-877, 2021.
[23] M. Du, & Q. Ph, “Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization,” Inf. Sci., vol. 179, no. 13, pp. 2232-2248, 2020.
[24] M. Raap, S. Meyer-Nieberg, S. Pickl, & M. Zsifkovits, “Aerial Vehicle Search-Path Optimization: A Novel Method for Emergency Operations,” J. Optim. Theory Appl., vol. 172, no. 3, pp. 965-983, 2017.
[25] O. Avalos, “GSA for machine learning problems: A comprehensive overview,” Appl. Math. Model., vol. 92, pp. 261-280, 2021.
[26] S. K. Gan & S. Sukkarieh, “Multi-UAV target search using explicit decentralized gradient-based negotiation”, pp. 751-756, 2011.
[27] M. B. Dowlatshahi, H. Nezamabadi-pour, & M. Mashinchi, “A discrete gravitational search algorithm for solving combinatorial optimization problems,” Inf. Sci., vol. 258, pp. 94-107, 2014.
[28] F. Su, C. Duan, & R. Wang, “Analysis and improvement of GSA’s optimization process,” Appl. Soft Comput., vol. 107, pp. 107-367, 2021.
[29] D. Yulong et al., “Path Planning of Messenger UAV in Air-ground Coordination,” IFAC-Pap., vol. 50, no. 1, pp. 8045-8051, 2017.
[30] Y. Jiang, Q. Wu, G. Zhang, S. Zhu, & W. Xing, “A diversified group teaching optimization algorithm with segment-based fitness strategy for unmanned aerial vehicle route planning,” Expert Syst. Appl., vol. 185, pp. 115-690, 2021.
[31] V. T. Hoang, M. D. Phung, T. H. Dinh, & Q. P. Ha, “System Architecture for Real-Time Surface Inspection Using Multiple UAVs,” IEEE Syst. J., vol. 14, no. 2, pp. 2925-2936,  2020.
[32] S. Zhang & J. Ou, “BP-PSO-based intelligent case retrieval method for high-rise structural form selection,” Sci. China Technol. Sci., vol. 56, no. 4, pp. 940-944, 2013.
[33] H. Duan & C. Sun, “Pendulum-like oscillation controller for micro aerial vehicle with ducted fan based on LQR and PSO,” Sci. China Technol. Sci., vol. 56, no. 2, pp. 423-429, 2013.
[34] ‏Y. Chen & H. Duan, “Multiple UCAVs mission assignment based on modified Gravitational Search, pp. 540-545, 2014.
[35] J. Khalil Pour, M.Veisi & F. Rahimi, “Distributed control and control of the UAV network,” Scientific Journal of Electronic and Cyber., vol. 7, no. 4, pp. 117-129, 2020. (in persian)

Files

History

  • Receive Date: 09 February 2022
  • Revise Date: 16 April 2022
  • Accept Date: 09 August 2022
  • Publish Date: 21 January 2023

Share

How to cite

Statistics