Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm

Zhenao Yu; Peng Duan; Leilei Meng; Yuyan Han; Fan Ye; Zhenao Yu; Peng Duan; Leilei Meng; Yuyan Han; Fan Ye

doi:10.3934/mbe.2023117

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 2: 2501-2529. doi: 10.3934/mbe.2023117

Previous Article Next Article

Research article

Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm

School of Computer Science, Liaocheng University, Liaocheng 52059, China

Academic Editor: Weining Wu

Received: 13 September 2022 Revised: 24 October 2022 Accepted: 09 November 2022 Published: 23 November 2022

Effective path planning (PP) is the basis of autonomous navigation for mobile robots. Since the PP is an NP-hard problem, intelligent optimization algorithms have become a popular option to solve this problem. As a classic evolutionary algorithm, the artificial bee colony (ABC) algorithm has been applied to solve numerous realistic optimization problems. In this study, we propose an improved artificial bee colony algorithm (IMO-ABC) to deal with the multi-objective PP problem for a mobile robot. Path length and path safety were optimized as two objectives. Considering the complexity of the multi-objective PP problem, a well-environment model and a path encoding method are designed to make solutions feasible. In addition, a hybrid initialization strategy is applied to generate efficient feasible solutions. Subsequently, path-shortening and path-crossing operators are developed and embedded in the IMO-ABC algorithm. Meanwhile, a variable neighborhood local search strategy and a global search strategy, which could enhance exploitation and exploration, respectively, are proposed. Finally, representative maps including a real environment map are employed for simulation tests. The effectiveness of the proposed strategies is verified through numerous comparisons and statistical analyses. Simulation results show that the proposed IMO-ABC yields better solutions with respect to hypervolume and set coverage metrics for the later decision-maker.
- path planning,
- multi-objective optimization,
- improved artificial bee colony algorithm,
- hybrid initialization strategy,
- variable neighborhood local search
Citation: Zhenao Yu, Peng Duan, Leilei Meng, Yuyan Han, Fan Ye. Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm[J]. Mathematical Biosciences and Engineering, 2023, 20(2): 2501-2529. doi: 10.3934/mbe.2023117

Related Papers:

Abstract

Effective path planning (PP) is the basis of autonomous navigation for mobile robots. Since the PP is an NP-hard problem, intelligent optimization algorithms have become a popular option to solve this problem. As a classic evolutionary algorithm, the artificial bee colony (ABC) algorithm has been applied to solve numerous realistic optimization problems. In this study, we propose an improved artificial bee colony algorithm (IMO-ABC) to deal with the multi-objective PP problem for a mobile robot. Path length and path safety were optimized as two objectives. Considering the complexity of the multi-objective PP problem, a well-environment model and a path encoding method are designed to make solutions feasible. In addition, a hybrid initialization strategy is applied to generate efficient feasible solutions. Subsequently, path-shortening and path-crossing operators are developed and embedded in the IMO-ABC algorithm. Meanwhile, a variable neighborhood local search strategy and a global search strategy, which could enhance exploitation and exploration, respectively, are proposed. Finally, representative maps including a real environment map are employed for simulation tests. The effectiveness of the proposed strategies is verified through numerous comparisons and statistical analyses. Simulation results show that the proposed IMO-ABC yields better solutions with respect to hypervolume and set coverage metrics for the later decision-maker.

References

[1]	K. Sharma, R. Doriya, Path planning for robots: An elucidating draft, Int. J. Intell. Robot., 4 (2020), 1–14. https://doi.org/10.1007/s41315-020-00129-0 doi: 10.1007/s41315-020-00129-0
[2]	H. Zhao, J. Liu, H. Chen, J. Chen, Y. Li, J. Xu, et al., Intelligent diagnosis using continuous wavelet transform and gauss convolutional deep belief network, IEEE T. Reliab., (2022), 1–11. https://doi.org/10.1109/TR.2022.3180273
[3]	S. Liu, G. Tian, Y. Zhang, P. Duan, Scene recognition mechanism for service robot adapting various families: A CNN-based approach using multi-type cameras, IEEE T. Multimedia, 2021. https://doi.org/10.1109/TMM.2021.3080076
[4]	M. Zhang, G. Tian, Y. Zhang, P. Duan, Service skill improvement for home robots: Autonomous generation of action sequence based on reinforcement learning, Knowl.-based Syst., 212 (2021). https://doi.org/10.1016/j.knosys.2020.106605
[5]	Y. Zhang, G. Tian, X. Shao, S. Liu, M. Zhang, P. Duan, Building metric-topological map to efficient object search for mobile robot, IEEE Trans. Ind. Electron., 69 (2022), 7070–7087. https://doi.org/10.1109/TIE.2021.3095812 doi: 10.1109/TIE.2021.3095812
[6]	M. Basavanna, M. Shivakumar, An overview of path planning and obstacle avoidance algorithms in mobile robots, IJERT, 8 (2019). https://doi.org/10.17577/IJERTV8IS120252
[7]	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
[8]	A. A. Ravankar, A. Ravankar, T. Emaru, Y. Kobayashi, HPPRM: Hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots, IEEE Access, 8 (2020), 221743–221766. https://doi.org/10.1109/ACCESS.2020.3043333 doi: 10.1109/ACCESS.2020.3043333
[9]	F. Islam, J. Nasir, U. Malik, Y. Ayaz, O. Hasan, RRT-Smart: Rapid convergence implementation of RRT towards optimal solution, in 2012 IEEE International Conference on Mechatronics and Automation, (2020), 1651–1656. https://doi.org/10.1109/ICMA.2012.6284384
[10]	J. Suh, J. Gong, S. Oh, Fast dampling-based cost-aware path planning with nonmyopic extensions using cross entropy, IEEE Trans. Robot., 33 (2017), 1313–1326. https://doi.org/10.1109/TRO.2017.2738664 doi: 10.1109/TRO.2017.2738664
[11]	R. Szczepanski, A. Bereit, T. Tarczewski, Efficient local path planning algorithm using artificial potential field supported by augmented reality, Energies, 14 (2021), 1–14. https://doi.org/10.3390/en14206642 doi: 10.3390/en14206642
[12]	H. Wang, S. Lou, J. Jing, Y. Wang, W. Liu, T. Liu, The EBS-A* algorithm: An improved A* algorithm for path planning, Plos One, 17 (2022), 1–27. https://doi.org/10.1371/journal.pone.0263841 doi: 10.1371/journal.pone.0263841
[13]	Y. Singh, S. Sharma, R. Sutton, D. Hatton, Towards use of dijkstra algorithm for optimal navigation of an unmanned surface vehicle in a real-time marine environment with results from artificial potential field, TransNav Int. J. Marine Navigat. Safety Sea Transp., 12 (2018), 125–131. https://doi.org/10.12716/1001.12.01.14 doi: 10.12716/1001.12.01.14
[14]	M. T. Jensen, Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms, IEEE Trans. Evolut. Comput., 7 (2003), 503–515. https://doi.org/10.1109/TEVC.2003.817234 doi: 10.1109/TEVC.2003.817234
[15]	C. Lamini, S. Benhlima, A. Elbekri, Genetic algorithm based approach for autonomous mobile robot path planning, Procedia Comput. Sci., 127 (2018), 180–189. https://doi.org/10.1016/j.procs.2018.01.113 doi: 10.1016/j.procs.2018.01.113
[16]	K. Hao, J. Zhao, B. Wang, Y. Liu, C. Wang, The application of an adaptive genetic algorithm based on collision detection in path planning of mobile robots, Comput. Intell. Neurosci., 2021 (2021), 1–20. https://doi.org/10.1155/2021/5536574 doi: 10.1155/2021/5536574
[17]	Y. Liu, X. Zhang, X. Guan, D. Delahaye, Potential odor intensity grid based UAV path planning algorithm with particle swarm optimization approach, Math. Probl. Eng., 2016 (2016), 1–20. https://doi.org/10.1155/2016/7802798 doi: 10.1155/2016/7802798
[18]	J. Li, X. Chen, P. Duan, J. Mou, KMOEA: A knowledge-based multi-objective algorithm for distributed hybrid flow shop in a prefabricated system, IEEE Trans. Ind. Inf., 18 (2022), 5318–5329.
[19]	Z. Xie, Y. Jia, C. Zhang, X. Shao, D. Li, Blocking flow shop scheduling problem based on migrating birds optimization, Comput. Int. Manu. Syst., 21 (2015), 2099–2107. https://doi.org/10.13196/j.cims.2015.08.015 doi: 10.13196/j.cims.2015.08.015
[20]	W. Deng, J. Xu, X. Gao, H. Zhao, An enhanced MSIQDE algorithm with novel multiple strategies for global optimization problems, in IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52 (2022), 1578–1587. https://doi.org/10.1109/TSMC.2020.3030792
[21]	Y. Song, X. Cai, X. Zhou, B. Zhang, H. Chen, Y. Li, et al., Dynamic hybrid mechanism-based differential evolution algorithm and its application, Expert Syst. Appl., 213 (2022). https://doi.org/10.1016/j.eswa.2022.118834
[22]	W. Deng, H. Ni, Y. Liu, H. Chen, H. Zhao, An adaptive differential evolution algorithm based on belief space and generalized opposition-based learning for resource allocation, Appl. Soft. Comput., 127 (2022). https://doi.org/10.1016/j.asoc.2022.109419
[23]	E. Masehian, D. Sedighizadeh, A multi-objective PSO-based algorithm for robot path planning, in 2010 IEEE International Conference on Industrial Technology, (2010), 465–470. https://doi.org/10.1109/ICIT.2010.5472755
[24]	M. Davoodi, F. Panahi, A. Mohades, S. N. Hashemi, Multi-objective path planning in discrete space, Appl. Soft Comput., 13 (2013), 709–720. https://doi.org/10.1016/j.asoc.2012.07.023 doi: 10.1016/j.asoc.2012.07.023
[25]	P. Duan, J. Li, H. Sang, Y. Han, Q. Sun, A developed firefly algorithm for multi-objective path planning optimization problem, in 2018 IEEE 8th Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems (CYBER), (2018), 1393–1397. https://doi.org/10.1109/CYBER.2018.8688342
[26]	F. Guo, H. Wang, Y. Tian, Multi-objective path planning for unrestricted mobile, in 2009 IEEE International Conference on Automation and Logistics, (2009), 1046–1051. https://doi.org/10.1109/ICAL.2009.5262574
[27]	D. Gong, J. Zhang, Z. Yong, Multi-objective particle swarm optimization for robot path planning in environment with danger sources, J. Comput., 6 (2011), 1554–1561. https://doi.org/10.4304/jcp.6.8.1554-1561 doi: 10.4304/jcp.6.8.1554-1561
[28]	Y. Zhang, D. Gong, J. Zhang, Robot path planning in uncertain environment using multi-objective particle swarm optimization, Neurocomputing, 103 (2013), 172–185. https://doi.org/10.1016/j.neucom.2012.09.019 doi: 10.1016/j.neucom.2012.09.019
[29]	T. T. Mac, C. Copot, D. T. Tran, R. D. Keyser, A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization, Appl. Soft Comput., 59 (2017), 68–76. https://doi.org/10.1016/j.asoc.2017.05.012 doi: 10.1016/j.asoc.2017.05.012
[30]	A. Hidalgo-Paniagua, M. Vega-Rodríguez, J. Ferruz, N. Pavón, Solving the multi-objective path planning problem in mobile robotics with a firefly-based approach, Soft Comput., 21 (2017), 1–16. https://doi.org/10.1007/s00500-015-1825-z doi: 10.1007/s00500-015-1825-z
[31]	A. Hidalgo-Paniagua, M. Vega-Rodríguez, J. Ferruz, N. Pavón, MOSFLA-MRPP: Multi-objective shuffled frog-leaping algorithm applied to mobile robot path planning, Eng. Appl. Artif. Intell., 44 (2015), 123–136. https://doi.org/10.1016/j.engappai.2015.05.011 doi: 10.1016/j.engappai.2015.05.011
[32]	D. Karaboga, B. Akay, A comparative study of artificial bee colony algorithm, Appl. Math. Comput., 214 (2009), 108–132. https://doi.org/10.1016/j.amc.2009.03.090 doi: 10.1016/j.amc.2009.03.090
[33]	J. Li, M. Song, L. Wang, P. Duan, Y. Han, H. Sang, et al., Hybrid artificial bee colony algorithm for a parallel batching distributed flow-shop problem with deteriorating jobs, IEEE Trans. Cybern., 50 (2020), 2425–2439. https://doi.org/10.1109/TCYB.2019.2943606 doi: 10.1109/TCYB.2019.2943606
[34]	J. Li, Y. Han, A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system, Cluster Comput., 23 (2020), 2483–2499. https://doi.org/10.1007/s10586-019-03022-z doi: 10.1007/s10586-019-03022-z
[35]	L. Meng, C. Zhang, Y. Ren, B. Zhang, C. Lv, Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem, Comput. Ind. Eng., 142 (2020). https://doi.org/10.1016/j.cie.2020.106347
[36]	L. Meng, K. Gao, Y. Ren, B. Zhang, H. Sang, C. Zhang, Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., 71 (2022). https://doi.org/10.1016/j.swevo.2022.101058
[37]	P. G. Asteris, M. Nikoo, Artificial bee colony-based neural network for the prediction of the fundamental period of infilled frame structures, Neural Comput. Appl., 31 (2019), 4837–4847. https://doi.org/10.1007/s00521-018-03965-1 doi: 10.1007/s00521-018-03965-1
[38]	P. Duan, T. Wang, M. Cui, H. Sang, Q. Sun, Multi-person pose estimation based on a deep convolutional neural network, J. Visual Commun. Image Rep., 62 (2019), 245–252. https://doi.org/10.1016/j.jvcir.2019.05.010 doi: 10.1016/j.jvcir.2019.05.010
[39]	Z. Wang, R. Song, P. Duan, X. Li, EFNet: Enhancement fusion network for semantic segmentation, Pattern Recogn., 118 (2021). https://doi.org/10.1016/j.patcog.2021.108023
[40]	M. H. Saffari, M. J. Mahjoob, Bee colony algorithm for real-Time optimal path planning of mobile robots, in 2009 Fifth International Conference on Soft Computing, Computing with Words and Perceptions in System Analysis, Decision and Control, (2009), 1–14. https://doi.org/10.1109/ICSCCW.2009.5379462
[41]	P. Bhattacharjee, P. Rakshit, I. Goswami, A. Konar, A. Nagar, Multi-robot path-planning using artificial bee colony optimization algorithm, in 2011 Third World Congress on Nature and Biologically Inspired Computing, (2011), 219–224. https://doi.org/10.1109/NaBIC.2011.6089601
[42]	D. Cui, X. Gao, W. Guo, Mechanism design and motion ability analysis for wheel/track mobile robot, Adv. Mech. Eng., 8 (2016), 1–13. https://doi.org/10.1177/1687814016679763 doi: 10.1177/1687814016679763
[43]	J. Hao, J. Li, Y. Du, M. Song, P. Duan, Y. Zhang, Solving distributed hybrid flowshop scheduling problems by a hybrid brain storm optimization algorithm, IEEE Access, 7 (2019), 66879–66894. https://doi.org/10.1109/ACCESS.2019.2917273 doi: 10.1109/ACCESS.2019.2917273
[44]	J. Li, S. Bai, P. Duan, H. Sang, Y. Han, Z. Zheng, An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system, Int. J. Prod. Res., 57 (2019), 6922–6942. https://doi.org/10.1080/00207543.2019.1571687 doi: 10.1080/00207543.2019.1571687
[45]	Y. Du, J. Li, C. Li, P. Duan, A reinforcement learning approach for flexible job shop scheduling problem with crane transportation and setup times, IEEE Trans. Neural Networks Learn. Syst., (2022). https://doi.org/10.1109/TNNLS.2022.3208942
[46]	J. Li, Y. Du, K. Gao, P. Duan, D. Gong, Q. Pan, et al., Hybrid iterated greedy algorithm for a crane transportation flexible job shop problem, IEEE Trans. Autom. Sci. Eng., 19 (2022), 2153–2170. https://doi.org/10.1109/TASE.2021.3062979 doi: 10.1109/TASE.2021.3062979
[47]	Y. Du, J. Li, X. Chen, P. Duan, Q. Pan, Knowledge-based reinforcement learning and estimation of distribution algorithm for flexible job shop scheduling problem, IEEE Trans. Emerg. Topics Comput. Intell., 2022. https://doi.org/10.1109/TETCI.2022.3145706

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)