Kybernetika 60 no. 3, 293-316, 2024

An effective global path planning algorithm with teaching-learning-based optimization

Emad Hazrati Nejad, Sevgi Yigit-Sert and Şahin Emrah AmrahovDOI: 10.14736/kyb-2024-3-0293

Abstract:

Due to the widespread use of mobile robots in various applications, the path planning problem has emerged as one of the important research topics. Path planning is defined as finding the shortest path starting from the initial point to the destination in such a way as to get rid of the obstacles it encounters. In this study, we propose a path planning algorithm based on a teaching-learning-based optimization (TLBO) algorithm with Bezier curves in a static environment with obstacles. The proposed algorithm changes the initially randomly selected control points step by step to obtain shorter Bezier curves that do not hit obstacles. We also improve the genetic algorithm-based path planning algorithm. Experimental results show that they provide better paths than other existing algorithms.

Keywords:

mobile robot, path planning, teaching-learning based optimization, Bezier curve

Classification:

68T40, 68W25, 78M50

paper.pdf

References:

  1. R. M. Alguliyev, R. M. Aliguliyev and R. G. Alakbarov: Constrained K-means algorithm for resource allocation in mobile cloudlets. Kybernetika 59 (2023), 1, 88-109.   DOI:10.14736/kyb-2023-1-0088
  2. S. Alnasser and H. Bennaceur: An efficient genetic algorithm for the global robot path planning problem. In: Sixth International Conference on Digital Information and Communication Technology and its Applications (DICTAP), Turkey 2016, pp. 97-102.   CrossRef
  3. K. M. Ang, E. S. M. El-kenawy, A. A. Abdelhamid, A. Ibrahim, A. H. Alharbi, D. S. Khafaga, S. S. Tiang and W. H. Lim: Optimal design of convolutional neural network architectures using teaching-learning-based optimization for image classification. Symmetry 14 (2022), 2323.   DOI:10.3390/sym14112323
  4. A. Q. Ansari and I. Katiyar: Comparison and analysis of obstacle avoiding path planning of mobile robot by using ant colony optimization and teaching learning based optimization techniques. In: Proc. First International Conference on Information and Communication Technology for Intelligent Systems, Volume 2. Smart Innovation, Systems and Technologies, 2016, pp. 563-574.   CrossRef
  5. A. Aouf, L. Boussaid and A. Sakly: TLBO-based adaptive neurofuzzy controller for mobile robot navigation in a strange environment. Comput. Intell. Neurosci. 4 (2018).   DOI:10.1155/2018/3145436
  6. Y. Ar: An initialization method for the latent vectors in probabilistic matrix factorization for sparse datasets. Evolution. Intell. 13 (2020), 2, 269-281.   DOI:10.1109/MITS.2021.3116446
  7. Y. Ar, S. Emrah Amrahov, N. Gasilov and S. Yigit-Sert: A new curve fitting based rating prediction algorithm for recommender systems. Kybernetika 58 (2022), 3, 440-455.   DOI:10.14736/kyb-2022-3-0440
  8. P. Bezier: Style, mathematics and NC. Computer-aided Design 22 (1990), 9, 524-526.   DOI:10.1016/0010-4485(90)90037-D
  9. D. Bodhale, N. Afzulpurkar and N. T. Thanh: Path planning for a mobile robot in a dynamic environment. In: IEEE International Conference on Robotics and Biomimetics, Thailand 2009, pp. 2115-2120.   CrossRef
  10. H. Bouchekara, M. Abido and M. Boucherma: Optimal power flow using teaching-learning-based optimization technique. Electric Power Systems Research 114 (2014), 49-59.   DOI:10.1016/j.epsr.2014.03.032
  11. I. Chaari, A. Koubaa, H. Bennaceur, S. Trigui and K. Al-Shalfan: A hybrid ACO-GA algorithm for robot path planning. In: IEEE Congress on Evolutionary Computation, Brisbane 2012, pp. 1-8.   CrossRef
  12. S. H. Chia, K. L. Su, J. H. Guo and C. Y. Chung: Ant colony system based mobile robot path planning. In: IEEE International Conference on Genetic and Evolutionary Computing, China 2010, pp. 210-213.   CrossRef
  13. Y. Dai, J. Yu, C. Zhang, B. Zhan and X. Zheng: A novel whale optimization algorithm of path planning strategy for mobile robots. Appl. Intell. 53 (2023), 10843-10857.   DOI:10.1007/s10489-022-04030-0
  14. Z. Duraklı and V. Nabiyev: A new approach based on bezier curves to solve path planning problems for mobile robots. J. Comput. Sci. 58 (2022), 101542.   DOI:10.1016/j.jocs.2021.101540
  15. M. Elhoseny, A. Tharwat and A. E. Hassanien: Bezier curve based path planning in a dynamic field using modified genetic algorithm. J. Comput. Sci. 25 (2018), 339-358.   CrossRef
  16. S. Feng, S. Zhang, M. Xu and G. Deng: Parallel navigation for 3-D autonomous vehicles. Kybernetika 59 (2023), 4, 592-611.   DOI:10.14736/kyb-2023-4-0592
  17. N. Gasilov, M. Dogan and V. Arici: Two-stage shortest path algorithm for solving optimal obstacle avoidance problem. IETE J. Res. 57 (2011), 3, 278-285.   DOI:10.4103/0377-2063.83650
  18. B. C. Guevara: An Overview of the Class of Rapidly-Exploring Random Trees. M.Sc. Thesis, Utrecht University 2018.   CrossRef
  19. M. S. Güzel, M. Kara and M. S. Beyazkilic: An adaptive framework for mobile robot navigation. Adaptive Behavior 25 (2017), 1, 30-39.   DOI:10.1177/1059712316685875
  20. M. A. Hossain and I. Ferdous: Autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique. In: International Conference on Electrical Information and Communication Technology (EICT), Bangladesh 2014, pp. 1-6.   DOI:10.1155/2014/904374
  21. J. H. Holland: Adaptation in natural and artificial systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, 1992.   CrossRef
  22. A. T. Ismail, A. Sheta and A. Al-Weshah: A mobile robot path planning using genetic algorithm in static environment. J. Computer Sci. 4 (2008), 4, 341-344.   DOI:10.3844/jcssp.2008.341.344
  23. A. Kroll and S. Soldan: Survey results on status, needs and perspectives for using mobile service robots in industrial applications. In: 11th International Conference on Control Automation Robotics and Vision, Singapore 2010, pp. 621-626.   DOI:10.1109/icarcv.2010.5707243
  24. A. Kumar, G. Ahmad and M. Shahid: Portfolio selection strategy: A teaching-learning-based optimization (TLBO) approach. In: Proc. International Joint Conference on Advances in Computational Intelligence, Singapore 2023, pp. 553-564.   DOI:10.1007/978-981-99-1435-7\_46
  25. C. Li, X. Huang, J. Ding, K. Song and S. Lu: Global path planning based on a bidirectional alternating search A* algorithm for mobile robots. Comput. Industr. Engrg. 168 (2022), 108123.   DOI:10.1016/j.cie.2022.108123
  26. J. Li, Y. Chen, X. Zhao and J. Huang: An improved DQN path planning algorithm. J. Supercomput. 78 (2022) 616-639.   DOI:10.1007/s11227-021-03878-2
  27. X. Li, G. Zhao and B. Li: Generating optimal path by level set approach for a mobile robot moving in static/dynamic environments. Appl. Math. Modell. 85 (2020), 210-230.   DOI:10.1016/j.apm.2020.03.034
  28. Y. Li, Z. Huang and Y. Xie: Path planning of mobile robot based on improved genetic algorithm. In: 3rd International Conference on Electron Device and Mechanical Engineering (ICEDME), China 2020, pp. 691-695.   CrossRef
  29. Y. Li, W. Wei, Y. Gao, D. Wang and Z. Fan: PQ-RRT*: An improved path planning algorithm for mobile robots. Expert Systems Appl.152 (2020), 113425.   DOI:10.1016/j.eswa.2020.113425
  30. J. Liu, J. Yang, H. Liu, X. Tian and M. Gao: An improved ant colony algorithm for robot path planning. Soft Comput. 21 (2017), 5829-5839.   DOI:10.1007/s00500-016-2161-7
  31. J. Liu, X. Wei and H. Huang: An improved grey wolf optimization algorithm and its application in path planning. IEEE Access 9 (2021), 121944-121956.   DOI:10.1109/ACCESS.2021.3108973
  32. E. S. Low, P. Ong, C. Y. Low and R. Omar: Modified q-learning with distance metric and virtual target on path planning of mobile robot. Expert Systems Appl. 199 (2022), 117191.   DOI:10.1016/j.eswa.2022.117191
  33. P. G. Luan and N. T. Thinh: Hybrid genetic algorithm based smooth global-path planning for a mobile robot. Mechanics Based Design Structures Machines 51 (2023), 1758-1774.   DOI:10.1080/15397734.2021.1876569
  34. S. Luo, M. Zhang, Y. Zhuang, C. Ma and Q. Li: A survey of path planning of industrial robots based on rapidly exploring random trees. Frontiers Neurorobotics 17 (2023).   DOI:10.3389/fnbot.2023.1268447
  35. D. Lyu, Z. Chen, Z. Cai and S. Piao: Robot path planning by leveraging the graph-encoded floyd algorithm. Future Generation Computer Systems 122 (2021), 204-208.   DOI:10.1016/j.future.2021.03.007
  36. J. Ma, Y. Liu, S. Zang and L. Wang: Robot path planning based on genetic algorithm fused with continuous Bezier optimization. Comput. Intell. Neurosci. (2020).   DOI:10.1155/2020/9813040
  37. A. Maoudj and A. Hentout: Optimal path planning approach based on q-learning algorithm for mobile robots. Appl. Soft Comput. 97 (2020), 106796.   DOI:10.1016/j.asoc.2020.106796
  38. C. Miao, G. Chen, C. Yan and Y. Wu: Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Comput. Industr. Engrg. 156 (2021), 107230.   DOI:10.1155/2021/6853809
  39. S. Mirjalili: Genetic Algorithm, Evolutionary Algorithms and Neural Networks. Springer Cham 2019, 43-55.   CrossRef
  40. V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski and et al.: Human-level control through deep reinforcement learning. Nature 518 (2015), 529-533.   DOI:10.1038/nature14236
  41. H. F. Naji, P. Kullu and S. Emrah Amrahov: An augmented reality-based system with sound effects for teaching english in primary school. Educat. Inform. Technolog. (2023), 1-13.   DOI:10.1007/s10639-023-12350-y
  42. N. Kartli, E. Bostanci and M. S. Guzel: A new algorithm for the initial feasible solutions of fixed charge transportation problem. In: 7th International Conference on Computer Science and Engineering (UBMK), IEEE, 2022, pp. 82-85.   DOI:10.1109/ubmk55850.2022.9919524
  43. N. Kartli, E. Bostanci and M. S. Guzel: A new algorithm for optimal solution of fixed charge transportation problem. Kybernetika 59 (2023), 1, 45-63.   DOI:10.15625/2615-9023/18488
  44. V. Rajinikanth, S. C. Satapathy, S. L. Fernandes and S. Nachiappan: Entropy based segmentation of tumor from brain mr images - a study with teaching learning based optimization. Pattern Recognit. Lett. 94 (2017), 87-95.   DOI:10.1016/j.patrec.2017.05.028
  45. R. V. Rao, V. J. Savsani and D. Vakharia: Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems. Computer-aided Design 43 (2011), 303-315.   DOI:10.1016/j.cad.2010.12.015
  46. A. D. Sabiha, M. A. Kamel, E. Said and W. H. Hussein: Path planning algorithm based on teaching-learning-based-optimization for an autonomous vehicle. Communications 24 (2022), C33-C42.   DOI:10.26552/com.C.2022.2.C33-C42
  47. S. Y. Sert, Y. Ar and G. E. Bostanci: Evolutionary approaches for weight optimization in collaborative filtering-based recommender systems. Turkish J. Electr. Engrg. Computer Sci. 27 (2019), 3, 2121-2136.   DOI:10.3906/elk-1812-175
  48. D. H. Shin and A. Ollero: Mobile robot path planning for fine-grained and smooth path spcification. J. Robotic Syst. 12 (1995), 7, 491-503.   DOI:10.1002/rob.4620120704
  49. H. Tang, B. Fang, R. Liu, Y. Li and S. Guo: A hybrid teaching and learning-based optimization algorithm for distributed sand casting job-shop scheduling problem. Appl. Soft Comput. 120 (2022), 108694.   DOI:10.1016/j.asoc.2022.108694
  50. H. Tu, Y. Deng, Q. Li, M. Song and X. Zheng: Improved RRT global path planning algorithm based on bridge test. Robotics Autonomous Systems 171 (2024), 104570.   DOI:10.1016/j.robot.2023.104570
  51. J. Wang, W. Chi, C. Li, C. Wang and M. Q. H. Meng: Neural RRT*: Learning-based optimal path planning. IEEE Trans. Automat. Sci. Engrg. 17 (2020), 1748-1758.   DOI:10.1109/tase.2020.2976560
  52. W. Wang, J. Li, Z. Bai, Z. Wei and J. Peng: Towards optimization of path planning: An RRT*-ACO algorithm. IEEE Access (2024).   DOI:10.1109/access.2024.3359748
  53. Z. Wu, W. Fu, R. Xue and W. Wang: A novel global path planning method for mobile robots based on teaching-learning-based optimization. Information 7 (2016), 39.   DOI:10.3390/info7030039
  54. L. Xu, M. Cao and B. Song: A new approach to smooth path planning of mobile robot based on quartic bezier transition curve and improved pso algorithm. Neurocomputing 473 (2022), 98-106.   DOI:10.1016/j.neucom.2021.12.016
  55. H. B. Yildirim, K. Kullu and S. Emrah Amrahov: A graph model and a three-stage algorithm to aid the physically disabled with navigation. Universal Access Inform. Soc. (2023), 1-11.   DOI:10.1007/s10209-023-00981-4
  56. X. Yuan, X. Yuan and X. Wang: Path planning for mobile robot based on improved bat algorithm. Sensors 21 (2021), 4389.   DOI:10.3390/s21134389
  57. L. Zhang, H. Min, H. Wei and H. Huang: Global path planning for mobile robot based on A* algorithm and genetic algorithm. In: IEEE International Conference on Robotics and Biomimetics (ROBIO), China 2012, pp. 1795-1799.   CrossRef
  58. T. W. Zhang, G. H. Xu, X. S. Zhan and T. Han: A new hybrid algorithm for path planning of mobile robot. J. Supercomput. 78 (2022), 4158-4181.   DOI:10.1007/s11227-021-04031-9
  59. Y. Zhang, Z. Jin and Y. Chen: Hybrid teaching-learning-based optimization and neural network algorithm for engineering design optimization problems. Knowledge-Based Systems 187 (2020), 104836.   DOI:10.1016/j.knosys.2019.07.007
  60. Z. Zhang, R. He and K. Yang: A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm. Adv. Manufactur. 10 (2022), 114-130.   DOI:10.1007/s40436-021-00366-x