Improving Efficiency and Effectiveness of Wheeled Mobile Robot Pathfinding in Grid Space Using a Genetic Algorithm with Dynamic Crossover and Mutation Rates
(1) Dyah Lestari Mail (Universitas Negeri Malang, Indonesia)
(2) * Siti Sendari Mail (Universitas Negeri Malang, Indonesia)
(3) Ilham Ari Elbaith Zaeni Mail (Universitas Negeri Malang, Indonesia)
(4) Samsul Arifin Mail (Institut Teknologi dan Bisnis Asia Malang, Indonesia)
(5) Rina Dewi Indah Sari Mail (Institut Teknologi dan Bisnis Asia Malang, Indonesia)
*corresponding author

Abstract


Incorrect parameter tuning of crossover and mutation rates in Genetic Algorithms (GA) can negatively impact their effectiveness and efficiency in mobile robot pathfinding. This study focuses on improving the performance of wheeled mobile robots in grid-based environments by introducing a Dynamic Crossover and Mutation Rates (DCMR) strategy within the GA framework. The primary contribution of this research is enhancing the efficiency and effectiveness of mobile robot pathfinding, resulting in shorter average path lengths and faster convergence times. Additionally, this method addresses the challenge of selecting appropriate GA parameters while increasing the algorithm's adaptability to different phases of the search process. The DCMR approach involves linearly increasing the crossover rate by 10% (from 0% to 100%) and decreasing the mutation rate by 10% (from 100% to 0%) over every 10 generations during the GA's evolution. Unlike fixed parameter tuning or exponential and sigmoid parameter tuning—both of which require trial and error to determine optimal values—the DCMR method provides a systematic and efficient solution without additional computational cost. Experiments were conducted across eight scenarios featuring varying distances between the start and target points, with two obstacles randomly placed in the robot's environment. The results showed that implementing the DCMR method consistently identified the optimal path, reduced average path lengths by 0.99%, and accelerated algorithm convergence by 48.39% compared to fixed parameter tuning. These findings demonstrate that the DCMR method significantly enhances the performance of GAs for mobile robot pathfinding, offering a reliable and efficient approach for navigating complex environments.

Keywords


Wheeled Mobile Robot; Pathfinding; Grid Space; Genetic Algorithm; Dynamic Crossover and Mutation Rates

   

DOI

https://doi.org/10.31763/ijrcs.v5i1.1573 		      

Article metrics

10.31763/ijrcs.v5i1.1573 Abstract views : 129 | PDF views : 29

   

Cite

How to cite item
   

Full Text

Download

References


[1] S. Sendari et al., “Grasping and Repositioning Objects Using Inverse Kinematic Method for Arm Robot Based on Pixel Position Regression,†Journal of Advanced Manufacturing Technology (JAMT), vol. 16, no. 3, 2024, https://jamt.utem.edu.my/jamt/article/view/6409

[2] S. Tahmasebi, N. Rasouli, A. H. Kashefi, E. Rezabeyk, and H. R. Faragardi, “SYNCOP: An evolutionary multi-objective placement of SDN controllers for optimizing cost and network performance in WSNs,†Computer Networks, vol. 185, p. 107727, 2021, https://doi.org/10.1016/j.comnet.2020.107727.

[3] S. Sendari et al., “Dual-Stage Identifying Data of Arm Robot for Recognizing and Sorting Objects with Double Faces Permitted-Prohibited Area,†Journal of Advanced Manufacturing Technology (JAMT), vol. 18, no. 1, 2024, https://jamt.utem.edu.my/jamt/article/view/6635.

[4] S. Sendari et al., “Movement of Trolley Robot using Fuzzy Logic Control and Camshift Algorithms in Following Similar Object,†International Journal of iRobotics, vol. 5, no. 2, pp. 10–15, 2022, https://iroboticsjournal.org/index.php/irobotics/article/view/125.

[5] W. Dawid and K. Pokonieczny, “Methodology of Using Terrain Passability Maps for Planning the Movement of Troops and Navigation of Unmanned Ground Vehicles,†Sensors, vol. 21, no. 14, p. 4682, 2021, https://doi.org/10.3390/s21144682.

[6] Z. A. Adeola-Bello and N. Z. Azlan, “Power Assist Rehabilitation Robot and Motion Intention Estimation,†International Journal of Robotics and Control Systems, vol. 2, no. 2, pp. 297-316, 2022, https://doi.org/10.31763/ijrcs.v2i2.650.

[7] R. Sukwadi et al., “Comparative Analysis of Path Planning Algorithms for Multi-UAV Systems in Dynamic and Cluttered Environments: A Focus on Efficiency, Smoothness, and Collision Avoidance,†International Journal of Robotics and Control Systems, vol. 4, no. 4, pp. 1602-1616, 2024, http://dx.doi.org/10.31763/ijrcs.v4i4.1555.

[8] J. R. Sánchez-Ibáñez, C. J. Pérez-del-Pulgar, and A. García-Cerezo, “Path Planning for Autonomous Mobile Robots: A Review,†Sensors, vol. 21, no. 23, p. 7898, 2021, https://doi.org/10.3390/s21237898.

[9] L. Liu, X. Wang, X. Yang, H. Liu, J. Li, and P. Wang, “Path planning techniques for mobile robots: Review and prospect,†Expert Systems with Applications, vol. 227, p. 120254, 2023, https://doi.org/10.1016/j.eswa.2023.120254.

[10] Z. Yu, Z. Si, X. Li, D. Wang and H. Song, "A Novel Hybrid Particle Swarm Optimization Algorithm for Path Planning of UAVs," IEEE Internet of Things Journal, vol. 9, no. 22, pp. 22547-22558, 2022, https://doi.org/10.1109/JIOT.2022.3182798.

[11] C. Miao, G. Chen, C. Yan, and Y. Wu, “Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm,†Computers & Industrial Engineering, vol. 156, p. 107230, 2021, https://doi.org/10.1016/j.cie.2021.107230.

[12] C. Qu, W. Gai, J. Zhang, and M. Zhong, “A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle (UAV) path planning,†Knowledge-Based Systems, vol. 194, p. 105530, 2020, https://doi.org/10.1016/j.knosys.2020.105530.

[13] M. M. J. Samodro, R. D. Puriyanto, and W. Caesarendra, “Artificial Potential Field Path Planning Algorithm in Differential Drive Mobile Robot Platform for Dynamic Environment,†International Journal of Robotics and Control Systems, vol. 3, no. 2, pp. 161-170, 2023, http://dx.doi.org/10.31763/ijrcs.v3i2.944.

[14] M. G. Mohanan and A. Salgaonkar, “Robotic Motion Planning in Dynamic Environments and its Applications,†International Journal of Robotics and Control Systems, vol. 2, no. 4, pp. 666-691, 2022, https://doi.org/10.31763/ijrcs.v2i4.816.

[15] A. N. Jasim and L. Chaari Fourati, "Guided Genetic Algorithm for Solving Capacitated Vehicle Routing Problem With Unmanned-Aerial-Vehicles," IEEE Access, vol. 12, pp. 106333-106358, 2024, https://doi.org/10.1109/ACCESS.2024.3438079.

[16] L. Wijayathunga, A. Rassau, and D. Chai, “Challenges and Solutions for Autonomous Ground Robot Scene Understanding and Navigation in Unstructured Outdoor Environments: A Review,†Applied Sciences, vol. 13, no. 17, p. 9877, 2023, https://doi.org/10.3390/app13179877.

[17] K. Katona, H. A. Neamah, and P. Korondi, “Obstacle Avoidance and Path Planning Methods for Autonomous Navigation of Mobile Robot,†Sensors, vol. 24, no. 11, p. 3573, 2024, https://doi.org/10.3390/s24113573.

[18] H. Qin, S. Shao, T. Wang, X. Yu, Y. Jiang, and Z. Cao, “Review of Autonomous Path Planning Algorithms for Mobile Robots,†Drones, vol. 7, no. 3, p. 211, 2023, https://doi.org/10.3390/drones7030211.

[19] L. Yang et al., “Path Planning Technique for Mobile Robots: A Review,†Machines, vol. 11, no. 10, p. 980, 2023, https://doi.org/10.3390/machines11100980.

[20] M. Reda, A. Onsy, A. Y. Haikal, and A. Ghanbari, “Path planning algorithms in the autonomous driving system: A comprehensive review,†Robotics and Autonomous Systems, vol. 174, p. 104630, 2024, https://doi.org/10.1016/j.robot.2024.104630.

[21] N. S. Abu, W. M. Bukhari, M. H. Adli, and A. Ma’arif, “Optimization of an Autonomous Mobile Robot Path Planning Based on Improved Genetic Algorithms,†Journal of Robotics and Control, vol. 4, no. 4, pp. 557–571, 2023, https://doi.org/10.18196/jrc.v4i4.19306.

[22] D. Debnath and A. F. Hawary, “Adapting Travelling Salesmen Problem for Real-Time UAS Path Planning Using Genetic Algorithm,†Intelligent Manufacturing and Mechatronics, pp. 151–163, 2021, https://doi.org/10.1007/978-981-16-0866-7_12.

[23] D. Debnath, F. Vanegas, S. Boiteau, and F. Gonzalez, “An Integrated Geometric Obstacle Avoidance and Genetic Algorithm TSP Model for UAV Path Planning,†Drones, vol. 8, no. 7, p. 302, 2024, https://doi.org/10.3390/drones8070302.

[24] K. Sriniketh et al., “Robot-aided human evacuation optimal path planning for fire drill in buildings,†Journal of Building Engineering, vol. 72, p. 106512, 2023, https://doi.org/10.1016/j.jobe.2023.106512.

[25] Y. Li, J. Zhao, Z. Chen, G. Xiong, and S. Liu, “A Robot Path Planning Method Based on Improved Genetic Algorithm and Improved Dynamic Window Approach,†Sustainability, vol. 15, no. 5, p. 4656, 2023, https://doi.org/10.3390/su15054656.

[26] J. Shao, “Robot Path Planning Method Based on Genetic Algorithm,†Journal of Physics: Conference Series, vol. 1881, no. 2, p. 022046, 2021, https://doi.org/10.1088/1742-6596/1881/2/022046.

[27] Z. Ke-qi, “Path Planning of Mobile Robots Based on Improved Genetic Algoritm,†International Journal of Engineering Continuity, vol. 2, no. 1, pp. 40-48, 2022, https://doi.org/10.58291/ijec.v2i1.84.

[28] J. Ma, Y. Liu, S. Zang, and L. Wang, “Robot Path Planning Based on Genetic Algorithm Fused with Continuous Bezier Optimization,†Computational Intelligence and Neuroscience, vol. 2020, no. 1, pp. 1–10, 2020, https://doi.org/10.1155/2020/9813040.

[29] A. Hussain and Y. S. Muhammad, “Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator,†Complex & Intelligent Systems, vol. 6, no. 1, pp. 1–14, 2020, https://doi.org/10.1007/s40747-019-0102-7.

[30] P. K. Nandi and A. K. Dutta, “Global Path Planning for Mobile Robots with optimization through Advanced Neuro-Genetic Algorithms: A Cutting-Edge Exploration,†SAMRIDDHI: A Journal of Physical Sciences, Engineering and Technology, vol. 15, no. 04, pp. 398–405, 2023, https://doi.org/10.18090/samriddhi.v15i04.03.

[31] K. S. Suresh, R. Venkatesan, and S. Venugopal, “Multi-objective optimization for solving mobile robot path planning problem employing hybridization of algorithms,†International Journal Of Health Sciences, vol. 6, no. S5, p. 1973–1992, 2022, https://doi.org/10.53730/ijhs.v6nS5.9058.

[32] S. A. Fatemi Aghda and M. Mirfakhraei, “Improved routing in dynamic environments with moving obstacles using a hybrid Fuzzy-Genetic algorithm,†Future Generation Computer Systems, vol. 112, pp. 250–257, 2020, https://doi.org/10.1016/j.future.2020.05.024.

[33] P. T. Zacharia and E. K. Xidias, “AGV routing and motion planning in a flexible manufacturing system using a fuzzy-based genetic algorithm,†The International Journal of Advanced Manufacturing Technology, vol. 109, no. 7, pp. 1801–1813, 2020, https://doi.org/10.1007/s00170-020-05755-3.

[34] F. Chen, “Optimal Design of Computer Network Security Performance Based on Genetic Algorithm,†Journal of Physics: Conference Series, vol. 1852, no. 3, p. 032054, 2021, https://doi.org/10.1088/1742-6596/1852/3/032054.

[35] A. Alhroob, W. Alzyadat, A. Tareq Imam, and G. M. Jaradat, “The Genetic Algorithm and Binary Search Technique in the Program Path Coverage for Improving Software Testing Using Big Data,†Intelligent Automation & Soft Computing, vol. 26, no. 4, pp. 725–733, 2020, https://doi.org/10.32604/iasc.2020.010106.

[36] U. K. Acharya and S. Kumar, “Genetic algorithm based adaptive histogram equalization (GAAHE) technique for medical image enhancement,†Optik, vol. 230, p. 166273, 2021, https://doi.org/10.1016/j.ijleo.2021.166273.

[37] H. Ansar, A. Jalal, M. Gochoo, and K. Kim, “Hand Gesture Recognition Based on Auto-Landmark Localization and Reweighted Genetic Algorithm for Healthcare Muscle Activities,†Sustainability, vol. 13, no. 5, p. 2961, 2021, https://doi.org/10.3390/su13052961.

[38] S. Sendari, A. B. Putra Utama, N. S. Fanany Putri, P. Widiharso, and R. J. Putra, “K-Means and Fuzzy C-Means Optimization using Genetic Algorithm for Clustering Questions,†International Journal of Advanced Science and Computer Applications, vol. 1, no. 1, pp. 1–9, 2021, https://doi.org/10.47679/ijasca.v1i1.2.

[39] K. M. Hamdia, X. Zhuang, and T. Rabczuk, “An efficient optimization approach for designing machine learning models based on genetic algorithm,†Neural Computing and Applications, vol. 33, no. 6, pp. 1923–1933, 2021, https://doi.org/10.1007/s00521-020-05035-x.

[40] D. Lestari, S. Sendari, and I. A. E. Zaeni, “Genetic algorithm for finding shortest path of mobile robot in various static environments,†Jurnal INFOTEL, vol. 15, no. 3, pp. 281–287, 2023, https://doi.org/10.20895/infotel.v15i3.961.

[41] M. N. Ab Wahab et al., “Improved genetic algorithm for mobile robot path planning in static environments,†Expert Systems with Applications, vol. 249, p. 123762, 2024, https://doi.org/10.1016/j.eswa.2024.123762.

[42] K. Li, Q. Hu, and J. Liu, “Path Planning of Mobile Robot Based on Improved Multiobjective Genetic Algorithm,†Wireless Communications and Mobile Computing, vol. 2021, no. 1, p. 8836615, 2021, https://doi.org/10.1155/2021/8836615.

[43] Z. Chen, J. Xiao, and G. Wang, “An Effective Path Planning of Intelligent Mobile Robot Using Improved Genetic Algorithm,†Wireless Communications and Mobile Computing, vol. 2022, no. 1, p. 9590367, 2022, https://doi.org/10.1155/2022/9590367.

[44] T. Feng et al., "The Optimal Global Path Planning of Mobile Robot Based on Improved Hybrid Adaptive Genetic Algorithm in Different Tasks and Complex Road Environments," IEEE Access, vol. 12, pp. 18400-18415, 2024, https://doi.org/10.1109/ACCESS.2024.3357990.

[45] K. Hao, J. Zhao, B. Wang, Y. Liu, and C. Wang, “The Application of an Adaptive Genetic Algorithm Based on Collision Detection in Path Planning of Mobile Robots,†Computational Intelligence and Neuroscience, vol. 2021, no. 1, p. 5536574, 2021, https://doi.org/10.1155/2021/5536574.

[46] W. Rahmaniar and A. Rakhmania, “Mobile Robot Path Planning in a Trajectory with Multiple Obstacles Using Genetic Algorithms,†Journal of Robotics and Control (JRC), vol. 3, no. 1, pp. 1–7, 2021, https://doi.org/10.18196/jrc.v3i1.11024.

[47] A. Loganathan and N. S. Ahmad, “A systematic review on recent advances in autonomous mobile robot navigation,†Engineering Science and Technology, an International Journal, vol. 40, p. 101343, 2023, https://doi.org/10.1016/j.jestch.2023.101343.

[48] M. S. Abed, O. F. Lutfy, and Q. F. Al-Doori, “A Review on Path Planning Algorithms for Mobile Robots,†Engineering and Technology Journal, vol. 39, no. 5A, pp. 804–820, 2021, https://doi.org/10.30684/etj.v39i5A.1941.

[49] M. N. A. Wahab, S. Nefti-Meziani, and A. Atyabi, “A comparative review on mobile robot path planning: Classical or meta-heuristic methods?,†Annual Reviews in Control, vol. 50, pp. 233-252, 2020, https://doi.org/10.1016/j.arcontrol.2020.10.001.

[50] H. K. Tripathy, S. Mishra, H. K. Thakkar, and D. Rai, “CARE: A Collision-Aware Mobile Robot Navigation in Grid Environment using Improved Breadth First Search,†Computers & Electrical Engineering, vol. 94, p. 107327, 2021, https://doi.org/10.1016/j.compeleceng.2021.107327.

[51] F. H. Ajeil, I. K. Ibraheem, A. T. Azar, and A. J. Humaidi, “Grid-Based Mobile Robot Path Planning Using Aging-Based Ant Colony Optimization Algorithm in Static and Dynamic Environments,†Sensors, vol. 20, no. 7, p. 1880, 2020, https://doi.org/10.3390/s20071880.

[52] M.-K. Ng, Y.-W. Chong, K. Ko, Y.-H. Park, and Y.-B. Leau, “Adaptive path finding algorithm in dynamic environment for warehouse robot,†Neural Computing and Applications, vol. 32, no. 17, pp. 13155–13171, 2020, https://doi.org/10.1007/s00521-020-04764-3.

[53] Q. Cai, “A Comparison Between A* and RRT Algorithm in Path Planning for Mobile Robot,†Highlights in Science, Engineering and Technology, vol. 97, pp. 282–287, 2024, https://doi.org/10.54097/2stv5y97.

[54] J. Ding, Y. Zhou, X. Huang, K. Song, S. Lu, and L. Wang, “An improved RRT* algorithm for robot path planning based on path expansion heuristic sampling,†Journal of Computational Science, vol. 67, p. 101937, 2023, https://doi.org/10.1016/j.jocs.2022.101937.

[55] M. Kara, “Evaluation of popular path planning algorithms,†International Journal of Electronics and Telecommunications, vol. 70, no. 1, pp. 13–22, 2024, https://doi.org/10.24425/ijet.2023.147699.

[56] G. Joy, C. Huyck, and X.-S. Yang, “Review of Parameter Tuning Methods for Nature-Inspired Algorithms,†Benchmarks and Hybrid Algorithms in Optimization and Applications, pp. 33–47, 2023, https://doi.org/10.1007/978-981-99-3970-1_3.

[57] P. Sebastjan and W. Kuś, “Method for Parameter Tuning of Hybrid Optimization Algorithms for Problems with High Computational Costs of Objective Function Evaluations,†Applied Sciences, vol. 13, no. 10, p. 6307, 2023, https://doi.org/10.3390/app13106307.

[58] G. Airlangga, “A comparative analysis of pathfinding algorithms in static environments: modified A*, PSO, and FLA,†Jurnal Mantik, vol. 7, no. 4, pp. 3697-3976, 2024, https://www.ejournal.iocscience.org/index.php/mantik/article/view/4795/3428.

[59] L. Wang and L. Sun, “Path Planning Algorithm Based on Obstacle Clustering Analysis and Graph Search,†Symmetry, vol. 15, no. 8, p. 1498, 2023, https://doi.org/10.3390/sym15081498.

[60] E. Shem-Tov, M. Sipper, and A. Elyasaf, “Deep Learning-Based Operators for Evolutionary Algorithms,†Neural and Evolutionary Computing, 2024, https://doi.org/10.48550/arXiv.2407.10477.

[61] M. A. Albadr, S. Tiun, M. Ayob, and F. AL-Dhief, “Genetic Algorithm Based on Natural Selection Theory for Optimization Problems,†Symmetry, vol. 12, no. 11, p. 1758, 2020, https://doi.org/10.3390/sym12111758.

[62] S. T. Shishavan and F. S. Gharehchopogh, “An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks,†Multimedia Tools and Applications, vol. 81, no. 18, pp. 25205–25231, 2022, https://doi.org/10.1007/s11042-022-12409-x.

[63] J. Lengler and J. Meier, “Large population sizes and crossover help in dynamic environments,†Natural Computing, vol. 23, no. 1, pp. 115–129, 2024, https://doi.org/10.1007/s11047-022-09915-0.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Dyah Lestari, Siti Sendari, Ilham Ari Elbaith Zaeni, Samsul Arifin, Rina Dewi INdah Sari

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

 

About the JournalJournal PoliciesAuthor Information

International Journal of Robotics and Control Systems
e-ISSN: 2775-2658
Website: https://pubs2.ascee.org/index.php/IJRCS
Email: ijrcs@ascee.org
Organized by: Association for Scientific Computing Electronics and Engineering (ASCEE), Peneliti Teknologi Teknik Indonesia, Department of Electrical Engineering, Universitas Ahmad Dahlan and Kuliah Teknik Elektro
Published by: Association for Scientific Computing Electronics and Engineering (ASCEE)
Office: Jalan Janti, Karangjambe 130B, Banguntapan, Bantul, Daerah Istimewa Yogyakarta, Indonesia