Optimization of an Autonomous Mobile Robot Path Planning Based on Improved Genetic Algorithms

N. S. Abu, W. M. Bukhari, M. H. Adli, Alfian Ma’arif

Abstract


Mobile robots are intended to operate in a variety of environments, and they need to be able to navigate and travel around obstacles, such as objects and barriers. In order to guarantee that the robot will not come into contact with any obstacles or other objects during its movement, algorithms for path planning have been demonstrated. The basic goal while constructing a route is to find the fastest and smoothest route between the starting point and the destination. This article describes route planning using the improvised genetic algorithm with the Bezier Curve (GA-BZ). This study carried out two main experiments, each using a 20x20 random grid map model with varying percentages of obstacles (5%, 15%, and 30% in the first experiment, and 25% and 50% in the second). In the initial experiments, the population (PN), generation (GN), and mutation rate (MR) of genetic algorithms (GA) will be altered to the following values: (PN = 100, 125, 150, or 200; GN = 100, 125, 150; and MR = 0.1, 0.3, 0.5, 0.7) respectively. The goal is to evaluate the effectiveness of AMR in terms of travel distance (m), total time (s), and total cost (RM) in comparison to traditional GA and GA-BZ. The second experiment examined robot performance utilising GA, GA-BZ, Simulated Annealing (SA), A-Star (A*), and Dijkstra's Algorithms (DA) for path distance (m), time travel (s), and fare trip (RM). The simulation results are analysed, compared, and explained. In conclusion, the project is summarised.


Keywords


Genetic Algorithm; Bezier Curve; Obstacles Avoidance; Robot Optimization; Path Planning.

Full Text:

PDF

References


C. Kim and J. S. Won, “A fuzzy analytic hierarchy process and cooperative game theory combined multiple mobile robot navigation algorithm,” Sensors, vol. 20, no. 10, p. 2827, 2020.

T. Shen and J. Zhai, “Reactive Obstacle Avoidance Strategy Based on Fuzzy Neural Network and Arc Trajectory,” 2019 Chinese Automation Congress (CAC), pp. 4792-4796, 2019, doi: 10.1109/CAC48633.2019.8996374.

L. E. Zarate, M. Becker, B. D. M. Garrido, and H. S. C. Rocha, “An artificial neural network structure able to obstacle avoidance behavior used in mobile robots,” IEEE 2002 28th Annual Conference of the Industrial Electronics Society, vol. 3, pp. 2457-2461, 2002, doi: 10.1109/IECON.2002.1185358.

H. Li, Y. Luo, and J. I. E. Wu, “Collision-Free Path Planning for Intelligent Vehicles Based on Bézier Curve,” IEEE Access, vol. 7, pp. 123334–123340, 2019, doi: 10.1109/ACCESS.2019.2938179.

N. S. Abu, W. M. Bukhari, M. H. Adli, S. N. Omar, and S. A. Sohaimeh, “A Comprehensive Overview of Classical and Modern Route Planning Algorithms for Self-Driving Mobile Robots,” Journal of Robotics and Control (JRC), vol. 3, no. 5, pp. 666-678, 2022.

C. S. Tan, R. Mohd-Mokhtar, and M. R. Arshad, “A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms,” in IEEE Access, vol. 9, pp. 119310-119342, 2021, doi: 10.1109/ACCESS.2021.3108177.

R. P. Padhy, F. Xia, S. K. Choudhury, P. K. Sa, and S. Bakshi, “Monocular Vision Aided Autonomous UAV Navigation in Indoor Corridor Environments,” IEEE Transactions on Sustainable Computing, vol. 4, no. 1, pp. 96–108, 2019, doi: 10.1109/TSUSC.2018.2810952.

S. Campbell, N. O’Mahony, A. Carvalho, L. Krpalkova, D. Riordan, and J. Walsh, “Path Planning Techniques for Mobile Robots A Review,” 2020 6th International Conference on Mechatronics and Robotics Engineering, ICMRE 2020, pp. 12–16, 2020, doi: 10.1109/ICMRE49073.2020.9065187.

P. G. Luan and N. T. Thinh, “Real-time hybrid navigation system-based path planning and obstacle avoidance for mobile robots,” Applied Sciences, vol. 10, no. 10, p. 3355, 2020.

A. Dechemi and N. Achour, “An approach of data fusion for FuzzyART based visual recognition,” Proceedings - 2019 6th International Conference on Electrical and Electronics Engineering, ICEEE 2019, pp. 86–90, 2019, doi: 10.1109/ICEEE2019.2019.00024.

H. S. Hewawasam, M. Y. Ibrahim, and G. K. Appuhamillage, “Past, Present and Future of Path-Planning Algorithms for Mobile Robot Navigation in Dynamic Environments,” in IEEE Open Journal of the Industrial Electronics Society, vol. 3, pp. 353-365, 2022, doi: 10.1109/OJIES.2022.3179617.

X. Zhou, T. Bai, Y. Gao, and Y. Han, “Vision-based robot navigation through combining unsupervised learning and hierarchical reinforcement learning,” Sensors (Switzerland), vol. 19, no. 7, pp. 1–23, 2019, doi: 10.3390/s19071576.

A. Molina-Leal, A. Gómez-Espinosa, J. A. Escobedo Cabello, E. Cuan-Urquizo, and S. R. Cruz-Ramírez, “Trajectory planning for a Mobile robot in a dynamic environment using an LSTM neural network,” Applied Sciences, vol. 11, no. 22, p. 10689, 2021.

C. Wang and J. Mao, “Summary of AGV Path Planning,” 2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE), pp. 332-335, 2019, doi: 10.1109/EITCE47263.2019.9094825.

X. Li, X. Hu, Z. Wang, and Z. Du, “Path planning based on combinaion of improved A-STAR Algorithm and DWA algorithm,” Proceedings - 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture, AIAM 2020, pp. 99–103, 2020, doi: 10.1109/AIAM50918.2020.00025.

J. Liu, Z. Chen, Y. Zhang, and W. Li, “Path Planning of Mobile Robots based on Improved Genetic Algorithm,” PervasiveHealth: Pervasive Computing Technologies for Healthcare, pp. 49–53, 2020, doi: 10.1145/3438872.3439054.

R. Szczepanski, A. Bereit, and T. Tarczewski, “Efficient local path planning algorithm using artificial potential field supported by augmented reality,” Energies, vol. 14, no. 20, p. 6642, 2021.

Y. J. Zheng, Y. C. Du, H. F. Ling, W. G. Sheng, and S. Y. Chen, “Evolutionary Collaborative Human-UAV Search for Escaped Criminals,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 2, pp. 217–231, 2020, doi: 10.1109/TEVC.2019.2925175.

P. Marin-Plaza, A. Hussein, D. Martin, and A. De La Escalera, “Global and Local Path Planning Study in a ROS-Based Research Platform for Autonomous Vehicles,” Journal of Advanced Transportation, vol. 2018, 2018, doi: 10.1155/2018/6392697.

Y. Wu, S. Wu, and X. Hu, “Cooperative Path Planning of UAVs UGVs for a Persistent Surveillance Task in Urban Environments,” IEEE Internet of Things Journal, vol. 8, no. 6, pp. 4906–4919, 2021, doi: 10.1109/JIOT.2020.3030240.

J. Ning, H. Chen, T. Li, W. Li, and C. Li, “COLREGs-compliant unmanned surface vehicles collision avoidance based on multi-objective genetic algorithm,” IEEE Access, vol. 8, pp. 190367–190377, 2020, doi: 10.1109/ACCESS.2020.3030262.

V. S. Raghavan, D. Kanoulas, D. G. Caldwell, and N. G. Tsagarakis, “Reconfigurable and Agile Legged-Wheeled Robot Navigation in Cluttered Environments with Movable Obstacles,” IEEE Access, vol. 10, pp. 2429–2445, 2022, doi: 10.1109/ACCESS.2021.3139438.

A. A. Nasr, N. A. El-Bahnasawy, and A. El-Sayed, “Straight-Line: A new global path planning algorithm for Mobile Robot,” 2021 International Conference on Electronic Engineering (ICEEM), pp. 1-5, 2021, doi: 10.1109/ICEEM52022.2021.9480376.

Y. Tao, H. Gao, F. Ren, C. Chen, T. Wang, H. Xiong, and S. Jiang, “A mobile service robot global path planning method based on ant colony optimization and fuzzy control,” Applied Sciences, vol. 11, no. 8, p. 3605, 2021.

K. Hao, J. Zhao, K. Yu, C. Li, and C. Wang, “Path planning of mobile robots based on a multi-population migration genetic algorithm,” Sensors, vol. 20, no. 20, p. 5873, 2020.

Y. Wu, K. H. Low, B. Pang, and Q. Tan, “Swarm-Based 4D Path Planning for Drone Operations in Urban Environments,” IEEE Transactions on Vehicular Technology, vol. 70, no. 8, pp. 7464–7479, 2021, doi: 10.1109/TVT.2021.3093318.

L. Xu, B. Song, and M. Cao, “A new approach to optimal smooth path planning of mobile robots with continuous-curvature constraint,” Systems Science & Control Engineering, vol. 9, no. 1, pp. 138-149, 2021.

P. Ren, S. Chen, and H. Fu, “Intelligent Path Planning and Obstacle Avoidance Algorithms for Autonomous Vehicles Based on Enhanced RRT Algorithm,” Proceedings of the 6th International Conference on Communication and Electronics Systems, ICCES 2021, pp. 1868–1871, 2021, doi: 10.1109/ICCES51350.2021.9489113.

Z. M. Elgamal, N. B. M. Yasin, M. Tubishat, M. Alswaitti, and S. Mirjalili, “An improved harris hawks optimization algorithm with simulated annealing for feature selection in the medical field,” IEEE Access, vol. 8, pp. 186638–186652, 2020, doi: 10.1109/ACCESS.2020.3029728.

J. Faigl and P. Váňa, “Surveillance Planning With Bézier Curves,” in IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 750-757, April 2018, doi: 10.1109/LRA.2018.2789844.

Z. Yu, N. Qi, M. Huo, Z. Fan, and W. Yao, “Fast Cooperative Trajectory Generation of Unmanned Aerial Vehicles Using a Bezier Curve-Based Shaping Method,” in IEEE Access, vol. 10, pp. 1626-1636, 2022, doi: 10.1109/ACCESS.2021.3136874.

Y. Zhou, B. Rao, and W. Wang, “UAV swarm intelligence: Recent advances and future trends,” IEEE Access, vol. 8, pp. 183856–183878, 2020, doi: 10.1109/ACCESS.2020.3028865.

G. Klančar, M. Seder, S. Blažič, I. Škrjanc, and I. Petrović, “Drivable Path Planning Using Hybrid Search Algorithm Based on E* and Bernstein–Bézier Motion Primitives,” in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 51, no. 8, pp. 4868-4882, Aug. 2021, doi: 10.1109/TSMC.2019.2945110.

L. B. Amar and W. M. Jasim, “Hybrid metaheuristic approach for robot path planning in dynamic environment,” Bulletin of Electrical Engineering and Informatics, vol. 10, no. 4, pp. 2152-2162, 2021.

D. S. A. Elminaam, A. Nabil, S. A. Ibraheem, and E. H. Houssein, “An Efficient Marine Predators Algorithm for Feature Selection,” IEEE Access, vol. 9, pp. 60136–60153, 2021, doi: 10.1109/ACCESS.2021.3073261.

F. Gul, I. Mir, W. Rahiman, and T. U. Islam, “Novel Implementation of Multi-Robot Space Exploration Utilizing Coordinated Multi-Robot Exploration and Frequency Modified Whale Optimization Algorithm,” IEEE Access, vol. 9, pp. 22774–22787, 2021, doi: 10.1109/ACCESS.2021.3055852.

J. Xu and L. Xu, “Optimal stochastic process optimizer: A new metaheuristic algorithm with adaptive exploration-exploitation property,” IEEE Access, vol. 9, pp. 108640–108664, 2021, doi: 10.1109/ACCESS.2021.3101939.

J. Lu and U. Kintak, “Mobile robot navigation based on adaptive neuro-fuzzy inerence ssystem with virtual target strategy,” 2017 International Conference on Wavelet Analysis and Pattern Recognition (ICWAPR), pp. 132-136, 2017, doi: 10.1109/ICWAPR.2017.8076677.

G. Y. Jeon and J. W. Jung, “Water sink model for robot motion planning,” Sensors (Switzerland), vol. 19, no. 6, 2019, doi: 10.3390/s19061269.

H. Deng, S. Guan, Y. Ji, L. Zhou, and X. Luo, “A hybrid predicting model for displacement of multifactor-Triggered landslides,” 11th International Conference on Advanced Computational Intelligence, ICACI 2019, pp. 139–143, 2019, doi: 10.1109/ICACI.2019.8778500.

A. Saad, A. E. H. Benyamina, and A. Gamatie, “Water Management in Agriculture: A Survey on Current Challenges and Technological Solutions,” IEEE Access, vol. 8, pp. 38082–38097, 2020, doi: 10.1109/ACCESS.2020.2974977.

W. Wang, J. Zhao, Z. Li, and J. Huang, “Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm,” vol. 2021, 2021.

H. Li, “Robotic Path Planning Strategy Based on Improved Artificial Potential Field,” Proceedings - 2020 International Conference on Artificial Intelligence and Computer Engineering, ICAICE 2020, pp. 67–71, 2020, doi: 10.1109/ICAICE51518.2020.00019.

N. M. Mirza, “Application of fuzzy neural networks in robotic path planning,” Proceedings - 2019 International Arab Conference on Information Technology, ACIT 2019, pp. 58–62, 2019, doi: 10.1109/ACIT47987.2019.8991028.

H. Zhuang, K. Dong, Y. Qi, N. Wang, and L. Dong, “Multi-destination path planning method research of mobile robots based on goal of passing through the fewest obstacles,” Applied Sciences, vol. 11, no. 16, p. 7378, 2021.

Á. J. O. Vargas, J. E. C. Serrano, L. C. Acuña, and J. C. Martinez-Santos, “Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm,” 2020 IEEE Games, Multimedia, Animation and Multiple Realities Conference (GMAX), pp. 1-5, doi: 10.1109/GMAX49668.2020.9256835.

Y. Li, D. Dong, and X. Guo, “Mobile Robot Path Planning based on Improved Genetic Algorithm With A-star Heuristic Method,” 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), pp. 1306-1311, 2020, doi: 10.1109/ITAIC49862.2020.9338968.

R. J. Wai and A. S. Prasetia, “Adaptive Neural Network Control and Optimal Path Planning of UAV Surveillance System with Energy Consumption Prediction,” IEEE Access, vol. 7, pp. 126137–126153, 2019, doi: 10.1109/ACCESS.2019.2938273.

S. K. Huang, W. J. Wang, and C. H. Sun, “A path planning strategy for multi-robot moving with path-priority order based on a generalized voronoi diagram,” Applied Sciences (Switzerland), vol. 11, no. 20, 2021, doi: 10.3390/app11209650.

K. P. Cheng, R. E. Mohan, N. H. K. Nhan, and A. V. Le, “Graph Theory-Based Approach to Accomplish Complete Coverage Path Planning Tasks for Reconfigurable Robots,” IEEE Access, vol. 7, pp. 94642–94657, 2019, doi: 10.1109/ACCESS.2019.2928467.

M. Luo, X. Hou, and S. X. Yang, “A multi-scale map method based on bioinspired neural network algorithm for robot path planning,” IEEE Access, vol. 7, pp. 142682–142691, 2019, doi: 10.1109/ACCESS.2019.2943009.

Q. Zhang, M. Li, and X. Wang, “Global path planning method of mobile robot in uncertain environment,” 2010 Chinese Control and Decision Conference, CCDC 2010, pp. 4320–4324, 2010, doi: 10.1109/CCDC.2010.5498378.

D. D. Zhu and J. Q. Sun, “A New Algorithm Based on Dijkstra for Vehicle Path Planning Considering Intersection Attribute,” IEEE Access, vol. 9, pp. 19761–19775, 2021, doi: 10.1109/ACCESS.2021.3053169.

K. P. Cheng, R. E. Mohan, N. H. Khanh Nhan, and A. V. Le, “Multi-Objective Genetic Algorithm-Based Autonomous Path Planning for Hinged-Tetro Reconfigurable Tiling Robot,” IEEE Access, vol. 8, pp. 121267–121284, 2020, doi: 10.1109/ACCESS.2020.3006579.

M. Fox, S. Yang, and F. Caraffini, “An Experimental Study of Prediction Methods in Robust optimization over Time,” 2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Conference Proceedings, 2020, doi: 10.1109/CEC48606.2020.9185910.

L. Li, Q. Gu, and L. Liu, “Research on path planning algorithm for multi-uav maritime targets search based on genetic Algorithm,” Proceedings of 2020 IEEE International Conference on Information Technology, Big Data and Artificial Intelligence, ICIBA 2020, no. Iciba, pp. 840–843, 2020, doi: 10.1109/ICIBA50161.2020.9277470.

D. Yu, C. L. P. Chen, and H. Xu, “Intelligent Decision Making and Bionic Movement Control of Self-Organized Swarm,” IEEE Transactions on Industrial Electronics, vol. 68, no. 7, pp. 6369–6378, 2021, doi: 10.1109/TIE.2020.2998748.

H. Y. Zhang, W. M. Lin, and A. X. Chen, “Path planning for the mobile robot: A review,” Symmetry, vol. 10, no. 10, 2018, doi: 10.3390/sym10100450.

B. K. Patle, G. Babu L, A. Pandey, D. R. K. Parhi, and A. Jagadeesh, “A review: On path planning strategies for navigation of mobile robot,” Defence Technology, vol. 15, no. 4, pp. 582–606, 2019, doi: 10.1016/j.dt.2019.04.011.

L. Chen, Y. Ma, Y. Zhang, and J. Liu, “Obstacle avoidance and multitarget tracking of a super redundant modular manipulator based on bezier curve and particle swarm optimization,” Chinese Journal of Mechanical Engineering, vol. 33, no. 1, pp. 1-19, 2020.




DOI: https://doi.org/10.18196/jrc.v4i4.19306

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 N. S. Abu, W. M. Bukhari, M. H. Adli, Alfian Ma’arif

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 

Journal of Robotics and Control (JRC)

P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com

Kuliah Teknik Elektro Terbaik