Comparison between Meta-Heuristic Algorithms for Path Planning
Resumo
Unmanned Aerial Vehicle (UAV) has been increasingly employed in several missions with a pre-defined path. Over the years, UAV has become necessary in complex environments, where it demands high computational cost and execution time for traditional algorithms. To solve this problem meta-heuristic algorithms are used. Meta-heuristics are generic algorithms to solve problems without having to describe each step until the result and search for the best possible answer in an acceptable computational time. The simulations are made in Python, with it, a statistical analyses was realized based on execution time and path length between algorithms Particle Swarm Optimization (PSO), Grey Wolf Optimization (GWO) and Glowworm Swarm Optimization (GSO). Despite the GWO returns the paths in a shorter time, the PSO showed better performance with similar execution time and shorter path length. However, the reliability of the algorithms will depend on the size of the environment. PSO is less reliable in large environments, while the GWO maintains the same reliability.
Referências
Dutta, S., Cai, Y., Huang, L., Zheng, J.: Automatic re-planning of lifting paths for robotized tower cranes in dynamic bim environments. Automation in Construction 110 (2020) 102998.
Vivaldini, K., Martinelli, T., Guizilini, V., Souza, J., Oliveira, M., Ramos, F., Wolf, D.: Uav route planning for active disease classification. Autonomous Robots 43 (07 2018).
Freimuth, H., König, M.: Planning and executing construction inspections with unmanned aerial vehicles. Automation in Construction 96 (2018) 540–553.
Aggarwal, S., Kumar, N.: Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges. Computer Communications 149 (2020) 270–299.
Kulkarni, S., et. al: Uav aided search and rescue operation using reinforcement learning. Computer Science, Engineering (2020).
Puliti, S., Dash, J.P., Watt, M.S., Breidenbach, J., Pearse, G.D.: A comparison of uav laser scanning, photogrammetry and airborne laser scanning for precision inventory of small-forest properties. Forestry: An Int. Journal of Forest Research 93(1) (2020) 150–162.
Pandey, P., Shukla, A., Tiwari, R.: Three-dimensional path planning for unmanned aerial vehicles using glowworm swarm optimization algorithm. International Journal of System Assurance Engineering and Management 9(4) (2018) 836–852.
Zhao, H., Zhang, X., Yu, R., Li, R., Zhu, M.: Research on uav formation network technology in high dynamic environment. In: IEEE Int. Conf. on Virtual Reality and Intelligent Systems. (2019).
Mikhaylov, I., Kukhtiaeva, V.: Algorithm of autonomous uav orientation for applying in complex indoor environment. In: 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), IEEE (2017) 943–946.
Goldreich, O.: P, NP, and NP-Completeness: The basics of computational complexity. Cambridge University Press (2010).
Osman, I.H., Laporte, G.: Metaheuristics: A bibliography (1996).
Rubio, F., Rodrı́guez, I.: Water-based metaheuristics: How water dynamics can help us to solve np-hard problems. Complexity 2019 (2019).
Shao, S., Peng, Y., He, C., Du, Y.: Efficient path planning for uav formation via comprehensively improved particle swarm optimization. ISA transactions 97 (2020) 415-430.
Panda, M., Das, B.: Grey wolf optimizer and its applications: A survey. In: Proc. of Third Int. Conf. on Microelectronics, Computing and Communication Systems, Springer (2019) 179–194.
McKinley, S., Levine, M.: Cubic spline interpolation. College of the Redwoods 45(1) (1998) 1049–1060.
Fritsch, F.N., Carlson, R.E.: Monotone piecewise cubic interpolation. SIAM Journal on Numerical Analysis 17(2) (1980) 238–246.
Eberhart, R., Kennedy, J.: Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks. Volume 4., Citeseer (1995) 1942–1948.
Kaipa, K.N., Ghose, D.: Glowworm swarm optimization: theory, algorithms, and applications. Volume 698. Springer (2017).
Dewangan, R.K., Shukla, A., Godfrey, W.W.: Three dimensional path planning using grey wolf optimizer for uavs. Applied Intelligence 49(6) (2019) 2201–2217.
Francis, G., Ott, L., Marchant, R., Ramos, F.: Occupancy map building through bayesian exploration. The International Journal of Robotics Research 38(7) (2019) 769–792.
