Path Optimization of Moving Object in Presence of Obstacles Using Messy Genetic Algorithm for N-dimensional Space

Subject Areas :

Ali Hasanabadi ¹

1 - Mechanical Engineering Department, University of Birjand, Birjand, Iran

Received: 2022-08-10 Accepted : 2022-10-28 Published : 2022-10-01

Keywords: Optimization, Moving Object Path Design, Messy Genetic Algorithm,

Abstract :

Optimizing the path of the movement of moving objects such as various robots in the industry can have a significant effect on reducing manufacturing and production time and costs. In this research, using a messy genetic algorithm, a new method is presented to optimize the movement path of a mobile object such as a robot in the presence of multiple obstacles. The movement path can be considered two-dimensional or multi-dimensional, and the obstacles in the path are assumed to be circles and spheres. The method used is that first, several chromosomes are created in the zero generation and their fitness is calculated. Then, using competitive selection, the parents of the new generation are created and from there the chromosomes of the next generation are made, and their fitness is calculated. This process continues until the considered condition, i.e. the ratio of the average fitness divided by maximum fitness in each generation is satisfied. Since in the messy genetic algorithm, the length of the chromosome can be variable, the proposed algorithm can examine all types of paths with a variable number of points depending on the existing obstacles and with high efficiency, find the shortest path with an approximate difference of 3.4 percentage compared to the ideal path. This method can optimize even paths with more than three dimensions.

References:

[1] Tzafestas, S.G. 2013. Introduction to Mobile Robot Control. Elsevier.

[2] Mallahi Kolahi, P. and Mosayebi, M. 2021. Optimal trajectory planning for an industrial mobile robot using optimal control theory.  Journal of Modern Processes in Manufacturing and Production. 10(3): 25-34.

[3] Matveev, A.S., Savkin, A.V., Hoy, M. and Wang, C. 2016. Survey of algorithms for safe navigation of mobile robots in complex environments. Safe Robot Navigation among Moving and Steady Obstacles. Butterworth-Heinemann, Elsevier.

[4] Esmaili, M. and Saadat, M. 2020. Path planning and control of an industrial robot used for opening tap hole of an electric arc furnace.  Journal of Modern Processes in Manufacturing and Production. 9(4): 5-14.

[5] Esmaeili, M. and Saadat, M. 2019. Dynamic modeling of a robot manipulator for opening the tap hole of an electric arc furnace.  Journal of Modern Processes in Manufacturing and Production. 8(4): 17-24.

[6] Nazarahari, M., Khanmirza, E. and Doostie, S. 2019. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm.  Expert Systems with Applications. 115(1): 106-120.

[7] Ever, Y.K. 2017. Using simplified swarm optimization on path planning for intelligent mobile robot.  Procedia Computer Science. 120(1): 83-90.

[8] Nasrollahy, A.Z. and Javadi, H.H.S. 2009. Using particle swarm optimization for robot path planning in dynamic environments with moving obstacles and target. Proceeding Third UKSim European Symposium on Computer Modeling and Simulation. Athens, Greece.

[9] Halder, R.K. 2021. Particle swarm optimization in global path planning for swarm of robots. Springer International Publishing.

[10] Ge, S.S. and Cui, Y.J. 2000. New potential functions for mobile robot path planning.  IEEE Transactions on Robotics and Automation. 16(5): 615-620.

[11] Brand, M., Masuda, M., Wehner, N. and Xiao-Hua, Y. 2010. Ant colony optimization algorithm for robot path planning. Proceeding of International Conference on Computer Design and Applications. Qinhuangdao, China.

[12] Dai, X., Long, S., Zhang, Z. and Gong, D. 2019. Mobile robot path planning based on ant colony algorithm with a heuristic method.  Frontiers in Neurorobotics. 13(1): 1-9.

[13] Latombe, J.C. 2012. Robot motion planning. Springer Science & Business Media.

[14] Lamini, C., Benhlima, S. and Elbekri, A. 2018. Genetic algorithm based approach for autonomous mobile robot path planning.  Procedia Computer Science. 127(1): 180-189.

[15] Nagib, G. and Gharieb, W. 2004. Path planning for a mobile robot using genetic algorithms. International Conference on Electrical, Electronic and Computer Engineering, Cairo, Egypt.

[16] Jianping, T. and Yang, S.X. 2003. Genetic algorithm based path planning for a mobile robot. Proc. IEEE International Conference on Robotics and Automation. Taipei, Taiwan.

[17] Ou, J., Hong, S.H., Ziehl, P. and Wang, Y. 2022. Gpu-based global path planning using genetic algorithm with near corner initialization.  Journal of Intelligent & Robotic Systems. 104(2): 1-17.

[18] Goldberg, D.E., Korb, B. and Deb, K. 1989. Messy genetic algorithms: Motivation, analysis, and first results.  Complex Systems. 3(5): 493-530.

[19] Https://www.Woodmagazine.Com/workshop/inspiring-shops/group-dynamic.