With the continuous development of mobile robot technology, its application fields are becoming increasingly widespread, and path planning is one of the most important topics in the field of mobile robot research. This paper focused on the study of the path planning problem for mobile robots in a complex environment based on the ant colony optimization (ACO) algorithm. In order to solve the problems of local optimum, susceptibility to deadlocks, and low search efficiency in the traditional ACO algorithm, a novel parallel ACO (PACO) algorithm was proposed. The algorithm constructed a rank-based pheromone updating method to balance exploration space and convergence speed and introduced a hybrid strategy of continuing to work and killing directly to address the problem of deadlocks. Furthermore, in order to efficiently realize the path planning in complex environments, the algorithm first found a better location for decomposing the original problem into two subproblems and then solved them using a parallel programming method-single program multiple data (SPMD)-in MATLAB. In different grid map environments, simulation experiments were carried out. The experimental results showed that on grid maps with scales of 20 $ \times $ 20, 30 $ \times $ 30, and 40 $ \times $ 40 compared to nonparallel ACO algorithms, the proposed PACO algorithm had less loss of solution accuracy but reduced the average total time by 50.71, 46.83 and 46.03%, respectively, demonstrating good solution performance.
Citation: Jian Si, Xiaoguang Bao. A novel parallel ant colony optimization algorithm for mobile robot path planning[J]. Mathematical Biosciences and Engineering, 2024, 21(2): 2568-2586. doi: 10.3934/mbe.2024113
With the continuous development of mobile robot technology, its application fields are becoming increasingly widespread, and path planning is one of the most important topics in the field of mobile robot research. This paper focused on the study of the path planning problem for mobile robots in a complex environment based on the ant colony optimization (ACO) algorithm. In order to solve the problems of local optimum, susceptibility to deadlocks, and low search efficiency in the traditional ACO algorithm, a novel parallel ACO (PACO) algorithm was proposed. The algorithm constructed a rank-based pheromone updating method to balance exploration space and convergence speed and introduced a hybrid strategy of continuing to work and killing directly to address the problem of deadlocks. Furthermore, in order to efficiently realize the path planning in complex environments, the algorithm first found a better location for decomposing the original problem into two subproblems and then solved them using a parallel programming method-single program multiple data (SPMD)-in MATLAB. In different grid map environments, simulation experiments were carried out. The experimental results showed that on grid maps with scales of 20 $ \times $ 20, 30 $ \times $ 30, and 40 $ \times $ 40 compared to nonparallel ACO algorithms, the proposed PACO algorithm had less loss of solution accuracy but reduced the average total time by 50.71, 46.83 and 46.03%, respectively, demonstrating good solution performance.
| [1] |
O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robot. Res., 5 (1986), 90–98. https://doi.org/10.1177/027836498600500106 doi: 10.1177/027836498600500106
|
| [2] |
X. Li, L. Wang, Y. An, Q. Huang, Y. Cui, H. Hu, Dynamic path planning of mobile robots using adaptive dynamic programming, Expert Syst. Appl., 235 (2023), 121112. https://doi.org/10.1016/j.eswa.2023.121112 doi: 10.1016/j.eswa.2023.121112
|
| [3] |
F. Duchon, A. Babinec, M. Kajan, P. Beno, M. Florek, T. Fico, et al., Path planning with modified A star algorithm for a mobile robot, Proc. Eng., 96 (2014), 59–69. https://doi.org/10.1016/j.proeng.2014.12.098 doi: 10.1016/j.proeng.2014.12.098
|
| [4] |
C. Li, X. Huang, J. Ding, K. Song, S. Lu, Global path planning based on a bidirectional alternating search A* algorithm for mobile robots, Comput. Ind. Eng., 168 (2022), 108123. https://doi.org/10.1016/j.cie.2022.108123 doi: 10.1016/j.cie.2022.108123
|
| [5] | M. Shayestegan, M. H. Marhaban, Mobile robot safe navigation in unknown environment, in Proceedings of the 2012 IEEE International Conference on Control System, Computing and Engineering (ICCSCE 2012), Penang, Malaysia, (2012), 44–49. https://doi.org/10.1109/ICCSCE.2012.6487113 |
| [6] |
J. Wang, Z. Xu, X. Zheng, Z. Liu, A fuzzy logic path planning algorithm based on geometric landmarks and kinetic constraints, Inf. Technol. Control, 51 (2022), 499–514. https://doi.org/10.5755/j01.itc.51.3.30016 doi: 10.5755/j01.itc.51.3.30016
|
| [7] |
H. Miao, Y. Tian, Dynamic robot path planning using an enhanced simulated annealing approach, Appl. Math. Comput., 222 (2013), 420–437. https://doi.org/10.1016/j.amc.2013.07.022 doi: 10.1016/j.amc.2013.07.022
|
| [8] |
K. Shi, Z. Wu, B. Jiang, H. R. Karimi, Dynamic path planning of mobile robot based on improved simulated annealing algorithm, J. Frankl. Inst. Eng. Appl. Math., 360 (2023), 4378–4398. https://doi.org/10.1016/j.jfranklin.2023.01.033 doi: 10.1016/j.jfranklin.2023.01.033
|
| [9] |
A. Tuncer, M. Yildirim, Dynamic path planning of mobile robots with improved genetic algorithm, Comput. Electr. Eng., 38 (2012), 1564–1572. https://doi.org/10.1016/j.compeleceng.2012.06.016 doi: 10.1016/j.compeleceng.2012.06.016
|
| [10] |
T. Zhang, G. Xu, X. Zhan, T. Han, A new hybrid algorithm for path planning of mobile robot, J. Supercomput., 78 (2022), 4158–4181. https://doi.org/10.1007/s11227-021-04031-9 doi: 10.1007/s11227-021-04031-9
|
| [11] |
B. Song, Z. Wang, L. Zou, On global smooth path planning for mobile robots using a novel multimodal delayed PSO algorithm, Cogn. Comput., 9 (2017), 5–17. https://doi.org/10.1007/s12559-016-9442-4 doi: 10.1007/s12559-016-9442-4
|
| [12] |
Q. Yuan, R. Sun, X. Du, Path planning of mobile robots based on an improved particle swarm optimization algorithm, Processes, 11 (2023), 26. https://doi.org/10.3390/pr11010026 doi: 10.3390/pr11010026
|
| [13] |
Q. Luo, H. Wang, Y. Zheng, J. He, Research on path planning of mobile robot based on improved ant colony algorithm, Neural Comput. Appl., 32 (2020), 1555–1566. https://doi.org/10.1007/s00521-019-04172-2 doi: 10.1007/s00521-019-04172-2
|
| [14] |
Y. Shi, H. Zhang, Z. Li, K. Hao, Y. Liu, L. Zhao, Path planning for mobile robots in complex environments based on improved ant colony algorithm, Math. Biosci. Eng., 20 (2023), 15568–15602. https://doi.org/10.3934/mbe.2023695 doi: 10.3934/mbe.2023695
|
| [15] |
Z. Jin, G. Luo, R. Wen, J. Huang, WOA-AGA algorithm design for robot path planning, Int. J. Comput. Commun. Control, 18 (2023), 5518. https://doi.org/10.15837/ijccc.2023.5.5518 doi: 10.15837/ijccc.2023.5.5518
|
| [16] |
Y. Dai, J. Yu, C. Zhang, B. Zhan, X. Zheng, A novel whale optimization algorithm of path planning strategy for mobile robots, Appl. Intell., 53 (2023), 10843–10857. https://doi.org/10.1007/s10489-022-04030-0 doi: 10.1007/s10489-022-04030-0
|
| [17] |
G. Hu, B. Du, G. Wei, HG-SMA: hierarchical guided slime mould algorithm for smooth path planning, Artif. Intell. Rev., 56 (2023), 9267–9327. https://doi.org/10.1007/s10462-023-10398-3 doi: 10.1007/s10462-023-10398-3
|
| [18] |
L. Zheng, Y. Tian, H. Wang, C. Hong, B. Li, Path planning of autonomous mobile robots based on an improved slime mould algorithm, Drones Basel, 7 (2023), 257. https://doi.org/10.3390/drones7040257 doi: 10.3390/drones7040257
|
| [19] |
M. Abdel-Basset, K. A. Eldrandaly, L. A. Shawky, M. Elhoseny, N. M. AbdelAziz, Hybrid computational intelligence algorithm for autonomous handling of COVID-19 pandemic emergency in smart cities, Sust. Cities Soc., 76 (2022), 103430. https://doi.org/10.1016/j.scs.2021.103430 doi: 10.1016/j.scs.2021.103430
|
| [20] |
X. Dai, Y. Wei, Application of improved moth-flame optimization algorithm for robot path planning, IEEE Access, 9 (2021), 105914–105925. https://doi.org/10.1109/ACCESS.2021.3100628 doi: 10.1109/ACCESS.2021.3100628
|
| [21] | C. Li, Q. Si, J. Zhao, P. Qin, A robot path planning method using improved harris hawks optimization algorithm, Meas. Control, (2023). https://doi.org/10.1177/00202940231204424 |
| [22] | C. Cai, C. Jia, Y. Nie, J. Zhang, L. Li, A path planning method using modified harris hawks optimization algorithm for mobile robots, PeerJ Comput. Sci., 9 (2023). https://doi.org/10.7717/peerj-cs.1473 |
| [23] |
R. Kumar, L. Singh, R. Tiwari, Path planning for the autonomous robots using modified grey wolf optimization approach, J. Intell. Fuzzy Syst., 40 (2021), 9453–9470. https://doi.org/10.3233/JIFS-201926 doi: 10.3233/JIFS-201926
|
| [24] |
Y. Hou, H. Gao, Z. Wang, C. Du, Improved grey wolf optimization algorithm and application, Sensors, 22 (2022), 3810. https://doi.org/10.3390/s22103810 doi: 10.3390/s22103810
|
| [25] | M. Dorigo, G. Di Caro, The ant colony optimization meta-heuristic, in New Ideas in Optimization, McGraw Hill, London, (1999), 11–32. |
| [26] |
M. Dorigo, G. Di Caro, L.M. Gambardella, Ant algorithms for discrete optimization, Artif. Life, 5 (1999), 137–172. https://doi.org/10.1162/106454699568728 doi: 10.1162/106454699568728
|
| [27] | M. Dorigo, T. Stützle, Ant Colony Optimization, MIT Press, Cambridge, 2004. https://doi.org/10.1109/MCI.2006.329691 |
| [28] |
H. Tseng, C. Chang, S. Lee, Y. Huang, Hybrid bidirectional ant colony optimization (hybrid BACO): An algorithm for disassembly sequence planning, Eng. Appl. Artif. Intell., 83 (2019), 45–56. https://doi.org/10.1016/j.engappai.2019.04.015 doi: 10.1016/j.engappai.2019.04.015
|
| [29] |
Y. Wang, L. Wang, G. Chen, Z. Cai, Y. Zhou, L. Xing, An improved ant colony optimization algorithm to the periodic vehicle routing problem with time window and service choice, Swarm Evol. Comput., 55 (2020), 100675. https://doi.org/10.1016/j.swevo.2020.100675 doi: 10.1016/j.swevo.2020.100675
|
| [30] |
W. Gao, Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem, Soft Comput., 25 (2021), 3263–3289. https://doi.org/10.1007/s00500-020-05376-8 doi: 10.1007/s00500-020-05376-8
|
| [31] |
W. Deng, L. Zhang, X. Zhou, Y. Zhou, Y. Sun, W. Zhu, et al., Multi-strategy particle swarm and ant colony hybrid optimization for airport taxiway planning problem, Inf. Sci., 612 (2022), 576–593. https://doi.org/10.1016/j.ins.2022.08.115 doi: 10.1016/j.ins.2022.08.115
|
| [32] |
D. B. M. M. Fontes, S. M. Homayouni, J. F. Gonçalves, A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources, Eur. J. Oper. Res., 306 (2023), 1140–1157. https://doi.org/10.1016/j.ejor.2022.09.006 doi: 10.1016/j.ejor.2022.09.006
|
| [33] |
T. T. Erguzel, C. Tas, M. Cebi, A wrapper-based approach for feature selection and classification of major depressive disorder-bipolar disorders, Comput. Biol. Med., 64 (2015), 127–137. https://doi.org/10.1016/j.compbiomed.2015.06.021 doi: 10.1016/j.compbiomed.2015.06.021
|
| [34] |
A. Qi, D. Zhao, F. Yu, A. A. Heidari, Z. Wu, Z. Cai, et al., Directional mutation and crossover boosted ant colony optimization with application to COVID-19 X-ray image segmentation, Comput. Biol. Med., 148 (2022), 105810. https://doi.org/10.1016/j.compbiomed.2022.105810 doi: 10.1016/j.compbiomed.2022.105810
|
| [35] |
K. Akka, F. Khaber, Mobile robot path planning using an improved ant colony optimization, Int. J. Adv. Robot. Syst., 15 (2018), 1729881418774673. https://doi.org/10.1177/1729881418774673 doi: 10.1177/1729881418774673
|
| [36] |
X. You, S. Liu, C. Zhang, An improved ant colony system algorithm for robot path planning and performance analysis, Int. J. Robot. Autom., 33 (2018), 527–533. https://doi.org/10.2316/Journal.206.2018.5.206-0071 doi: 10.2316/Journal.206.2018.5.206-0071
|
| [37] |
M. Dorigo, L. M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput., 1 (1997), 53–66. https://doi.org/10.1109/4235.585892 doi: 10.1109/4235.585892
|
| [38] |
W. Gao, Q. Tang, B. Ye, Y. Yang, J. Yao, An enhanced heuristic ant colony optimization for mobile robot path planning, Soft Comput., 24 (2020), 6139–6150. https://doi.org/10.1007/s00500-020-04749-3 doi: 10.1007/s00500-020-04749-3
|
| [39] |
X. Deng, L. Zhang, L. Luo, An improved ant colony optimization applied in robot path planning problem, J. Comput., 8 (2013), 585–593. https://doi.org/10.4304/jcp.8.3.585-593 doi: 10.4304/jcp.8.3.585-593
|
| [40] |
J. Liu, J. Yang, H. Liu, X. Tian, M. Gao, An improved ant colony algorithm for robot path planning, Soft Comput., 21 (2017), 5829–5839. https://doi.org/10.1007/s00500-016-2161-7 doi: 10.1007/s00500-016-2161-7
|
| [41] |
X. Dai, S. Long, Z. Zhang, D. Gong, Mobile robot path planning based on ant colony algorithm with A* heuristic method, Front. Neurorobotics, 13 (2019), 15. https://doi.org/10.3389/fnbot.2019.00015 doi: 10.3389/fnbot.2019.00015
|
| [42] |
Z. Zhang, J. Lu, Z. Xu, T. Xu, Mobile robot path planning based on hybrid ant colony optimization, J. Intell. Fuzzy Syst., 45 (2023), 2611–2623. https://doi.org/10.3233/JIFS-231280 doi: 10.3233/JIFS-231280
|
| [43] |
G. Li, C. Liu, L. Wu, W. Xiao, A mixing algorithm of ACO and ABC for solving path planning of mobile robot, Appl. Soft. Comput., 148 (2023), 110868. https://doi.org/10.1016/j.asoc.2023.110868 doi: 10.1016/j.asoc.2023.110868
|
| [44] | B. Bullnheimer, R. F. Hartl, C. Strauss, A new rank based version of the ant system – A computational study, Central Eur. J. Oper. Res. Econ., 7 (1999), 25–38. |
| [45] | D. Wang, H. Yu, Path planning of mobile robot in dynamic environments, in Proceedings of the 2011 2nd International Conference on Intelligent Control and Information Processing (ICICIP 2011), (2011), 691–696. https://doi.org/10.1109/ICICIP.2011.6008338 |
| [46] |
H. Qu, L. Huang, X. Ke, Research of improved ant colony based robot path planning under dynamic environment, J. Univ. Electron. Sci. Technol. China, 44 (2015), 260–265. https://doi.org/10.3969/j.issn.1001-0548.2015.02.017 doi: 10.3969/j.issn.1001-0548.2015.02.017
|
| [47] | J. Cao, S. Fan, X. Yang, Spmd performance analysis with parallel computing of Matlab, in Proceedings of the 2012 Fifth International Conference on Intelligent Networks and Intelligent Systems (ICINIS 2012), (2012), 80–83. https://doi.org/10.1109/ICINIS.2012.31 |
Figures(9) / Tables(4)
Jian Si, Xiaoguang Bao. A novel parallel ant colony optimization algorithm for mobile robot path planning[J]. Mathematical Biosciences and Engineering, 2024, 21(2): 2568-2586. doi: 10.3934/mbe.2024113
DownLoad: