БІОНАТХНЕННІ МЕТОДИ ПЛАНУВАННЯ ШЛЯХУ МОБІЛЬНИХ РОБОТІВ
DOI:
https://doi.org/10.30977/BUL.2219-5548.2022.98.0.37Ключові слова:
мобільний робот, планування шляху, методи оптимізації, біонатхненні алгоритми, алгоритми ройового інтелектуАнотація
Біонатхненні інтелектуальні алгоритми є різновидом методів оптимізації, що знайшли широке використання у мобільній робототехніці. У даній роботі представлено огляд біонатхненних алгоритмів, що використовуються для планування шляху автономних мобільних роботів у заздалегідь невідомій місцевості. Запропоновано класифікацію біонатхненних алгоритмів оптимізації. Проведено аналіз основних алгоритмів ройового інтелекту та наведені відповідні ним псевдокоди.
Посилання
T. T. Mac, C. Copot, D. T. Tran and R. De Key-ser. Heuristic approaches in robot path planning: A survey, Robotics and Autonomous Systems, 2016, vol. 86, pp. 13–28. https://doi.org/10.1016/j.robot.2016.08.001
K. Karur, N. Sharma, C. Dharmatti and J. E. Siegel. A survey of path planning algorithms for mobile robots, Vehicles, 2021, vol. 3, no 3, pp. 448–468. https://doi.org/10.3390/vehicles3030027
M. S. Abed, O. F. Lutfy and Q. Al-Doori. A review on path planning algorithms for mobile robots. Engineering and Technology Journal, 2021. vol. 39, no 5A, pp. 804–820. https://doi.org/10.30684/etj.v39i5a.1941
J. Kallannan. Bio-Inspired Algorithms in PID Controller Optimization. CRC Press, 2018. https://doi.org/10.1201/9780429486579
J. Ni, L. Wu, X. Fan and S. X. Yang. Bioinspired intelligent algorithm and its applications for mo-bile robot control: A survey. Computational Intel-ligence and Neuroscience, 2016, pp. 1–16. https://doi.org/10.1155/2016/3810903
M. N. Ab Wahab, S. Nefti-Meziani and A. Atyabi. A comprehensive review of swarm optimization algorithms. Plos One, 2015, vol. 10, no 5, e0122827. https://doi.org/10.1371/journal.pone.0122827
N. Adzhar, Y. Yusof and M. A. Ahmad. A review on autonomous mobile robot path planning algo-rithms. Advances in Science, Technology and Engineering Systems Journal, 2020, vol. 5, no 3, pp. 236–240. https://doi.org/10.25046/aj050330
M. N. A. Wahab, S. Nefti-Meziani, A. Atyabi. A comparative review on mobile robot path plan-ning: Classical or meta-heuristic methods? Annu-al Reviews in Control, 2020, vol. 50, pp. 233–252. https://doi.org/10.1016/j.arcontrol.2020.10.001
I. Skrjanc, G. Klancar, A. Zdesar, andS. Blazic. Wheeled Mobile Robotics: From Fundamentals Towards Autonomous Systems. Elsevier Science & Technology Books, 2017.
A. S. Matveev, A. V. Savkin, M. Hoy and C. Wang. Survey of algorithms for safe naviga-tion of mobile robots in complex environments. Safe Robot Navigation Among Moving and Steady Obstacles. Elsevier, 2016, pp. 21–49. https://doi.org/10.1016/b978-0-12-803730-0.00003-2
L. Armesto, et al. Mobile robot obstacle avoid-ance based on quasi-holonomic smooth paths. Advances in Autonomous Robotics. Springer Ber-lin Heidelberg, 2012, pp. 244–255. https://doi.org/10.1007/978-3-642-32527-4_22
A. Muhammad, A. H. A. Mohammed, and I. H. Shanono. Path planning methods for mobile robots: A systematic and bibliometric review, ELEKTRIKA-Journal of Electrical Engineering, 2020, vol. 19, no 3, pp. 14–34. https://doi.org/10.11113/elektrika.v19n3.225
D. Molina, et al. Comprehensive taxonomies of nature- and bio-inspired optimization: inspiration versus algorithmic behavior, critical analysis rec-ommendations. Cognitive Computation, 2020, vol. 12, no 5, pp. 897–939. https://doi.org/ Я10.1007/s12559-020-09730-8
C. Guo, H. Tang, B. Niu and C. Boon Patrick Lee. A survey of bacterial foraging optimization. Neu-rocomputing, 2021, vol. 452, pp. 728-74. https://doi.org/10.1016/j.neucom.2020.06.142
S. Das, A. Biswas and S. Dasgupta, A. Abraham. Bacterial foraging optimization algorithm: Theo-retical foundations, analysis, and applications. Foundations of Computational Intelligence. Vol. 3. Springer Berlin Heidelberg, 2009, pp. 23–55. https://doi.org/10.1007/978-3-642-01085-9_2
D. Rai and K. Tyagi. Bio-inspired optimization techniques. ACM SIGSOFT Software Engineer-ing Notes, 2013, vol. 38, no 4, pp. 1–7. https://doi.org/10.1145/2492248.2492271
T. Sarkar, et al. Application of bio-inspired opti-mization algorithms in food processing. Current Research in Food Science, 2022, vol. 5, pp. 432–450. https://doi.org/10.1016/j.crfs.2022.02.006
J. Ni, L. Wu, X. Fan and S. X. Yang. Bioinspired intelligent algorithm and its applications for mo-bile robot control: A survey. Computational Intel-ligence and Neuroscience, 2016, vol. 2016, pp. 1–16. https://doi.org/10.1155/2016/3810903
D. Simon. Biogeography-based optimization. IEEE Transactions on Evolutionary Computa-tion, 2008, vol. 12, no 6, pp. 702–713. https://doi.org/10.1109/tevc.2008.919004.
H. Burchardt, and R. Salomon. Implementation of path planning using genetic algorithms on mo-bile robots. In Proceedings of the 2006 IEEE In-ternational Conference on Evolutionary Compu-tation, Vancouver, Canada, 16–21 July 2006; pp. 1831–1836. https://doi.org/10.1109/CEC.2006.1688529
R. Deveza, D. Thiel, A. Russell and A. Mackay-Sim. Odor sensing for robot guidance. The Inter-national Journal of Robotics Research, 1994, v. 13, no 3, pp.232-239. https://doi.org/10.1177/027836499401300305
X. Chen, J. Huang. Odor source localization algo-rithms on mobile robots: A review and future out-look. Robotics and Autonomous Systems, 2019, vol. 112, pp. 123-136. https://doi.org/10.1016/j.robot.2018.11.014.
L. Wang, S. Pang and J. Li. Olfactory-based navi-gation via model-based reinforcement learning and fuzzy inference methods. In IEEE Transac-tions on Fuzzy Systems, 2021, vol. 29, no. 10, pp. 3014-3027, https://doi.org/10.1109/TFUZZ.2020.3011741
R. Gowri and R. Rathipriya. Non-swarm plant intelligence algorithm: bladderworts suction (BWS) algorithm, 2018 International Conference on Circuits and Systems in Digital Enterprise Technology (ICCSDET), 2018, pp. 1-7. https://doi.org/10.1109/ICCSDET.2018.8821225
A. Gurko and Y. Petrenko. A PSO-based control-ler tuning for a laser technical vision system. 2022 IEEE 3rd KhPI Week on Advanced Tech-nology (KhPIWeek), 2022, pp. 1-5, https://doi.org/10.1109/KhPIWeek57572.2022.9916393.
J. Kaliannan, A. Baskaran, N. Dey and A. S. Ash-our. Bio-inspired algorithms in PID controller op-timization. London: CRC Press, 2020.
C. Luo, G. E. Jan, Z. Chu and X. Li. Biologically inspired intelligence with applications on robot navigation. In Artificial Intelligence - Emerging Trends and Applications. London, United King-dom: IntechOpen, 2018 [Online]. Available: https://www.intechopen.com/chapters/61601 doi: 10.5772/intechopen.75692
Y. Liu, X. Zhang, X. Guan and D. Delahaye. Po-tential odor intensity grid based UAV path plan-ning algorithm with particle swarm optimization approach. Mathematical Problems in Engineer-ing, 2016, vol. 2016, Article ID 7802798, 16 pag-es. https://doi.org/10.1155/2016/7802798
S. Salmanpour, H. Omranpour and H. Motameni. An intelligent water drops algorithm for solving robot path planning problem. 2013 IEEE 14th In-ternational Symposium on Computational Intel-ligence and Informatics (CINTI), 2013, pp. 333-338, https://doi.org/10.1109/CINTI.2013.6705216
J. Kennedy and R. Eberhart. Particle swarm op-timization. Proceedings of ICNN'95 - Interna-tional Conference on Neural Networks, 1995, vol. 4, pp. 1942-1948. https://doi.org/10.1109/ICNN.1995.488968.
Wei Li and Gai-Yun Wang. Application of im-proved PSO in mobile robotic path planning. 2010 International Conference on Intelligent Computing and Integrated Systems, 2010, pp. 45-48. https://doi.org/10.1109/iciss.2010.5655007.
B. Song, Z. Wang and L. Zou. An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve. Applied Soft Computing, 2021, vol. 100, p. 106960. https://doi.org/10.1016/j.asoc.2020.106960.
B. Deepak and D. Parhi. PSO based path planner of an autonomous mobile robot. Open Computer Science, 2012, vol. 2, no 2, pp. 152-168. https://doi.org/10.2478/s13537-012-0009-5.
M. K. Rath and B. B. V. L. Deepak. PSO based system architecture for path planning of mobile robot in dynamic environment. 2015 Global Conference on Communication Technologies (GCCT), 2015, pp. 797-801, https://doi.org/10.1109/ GCCT.2015.7342773.
F. H. Ajeil, I. K. Ibraheem, M. A. Sahib and A. J. Humaidi. Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm. Applied Soft Com-puting, 2020, vol. 89, p. 106076. https://doi.org/10.1016/j.asoc.2020.106076.
W. Jatmiko, K. Sekiyama and T. Fukuda. A pso-based mobile robot for odor source localization in dynamic advection-diffusion with obstacles envi-ronment: theory, simulation and measurement. In IEEE Computational Intelligence Magazine, 2007, vol. 2, no. 2, pp. 37-51. https://doi.org/10.1109/MCI.2007.353419.
M. Dorigo and T. Stützle. Ant colony optimiza-tion: Overview and recent advances. In Hand-book of Metaheuristics. Boston, MA: Springer US, 2010, pp. 227–263. https://doi.org/10.1007/978-1-4419-1665-5_8.
P. Stodola, J. Mazal, M. Podhorec and O. Litvaj. Using the Ant Colony Optimization algorithm for the Capacitated Vehicle Routing Problem. Pro-ceedings of the 16th International Conference on Mechatronics - Mechatronika 2014, 2014, pp. 503-510, https://doi.org/10.1109/MECHATRONIKA.2014.7018311
Yee Zi Cong and S. G. Ponnambalam. Mobile robot path planning using ant colony optimiza-tion. 2009 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, 2009, pp. 851-856, https://doi.org/10.1109/AIM.2009.5229903.
Sh. Li, G. Zhao and W. Yue. Research on path planning for mobile robot based on improved ant colony algorithm. Journal of Physics: Confer-ence Series, 2021, vol. 2026, no. 1, p. 012049. https://doi.org/10.1088/1742-6596/2026/1/012049.
K. Akka and F. Khaber. Mobile robot path plan-ning using an improved ant colony optimization. International Journal of Advanced Robotic Sys-tems, 2018, vol. 15, no 3. https://doi.org/10.1177/1729881418774673.
X. Dai, S. Long, Z. Zhang and D. Gong. Mobile robot path planning based on ant colony algo-rithm with A* heuristic method. Frontiers in neu-rorobotics, 2019, vol. 13, article 15. https://doi.org/10.3389/fnbot.2019.00015.
X.-S. Yang. A new metaheuristic bat-inspired algorithm. In Nature Inspired Cooperative Strat-egies for Optimization (NICSO 2010). Springer Berlin Heidelberg, 2010, pp. 65–74. https://doi.org/10.1007/978-3-642-12538-6_6.
P. Suárez, A. Iglesias and A. Gálvez. Make robots be bats: specializing robotic swarms to the bat al-gorithm. Swarm and Evolutionary Computation, 2019, vol. 44, pp. 113-129. https://doi.org/10.1016/j.swevo.2018.01.005.
J. Perez, P. Et al. Trajectory optimization for an autonomous mobile robot using the bat algo-rithm. In Fuzzy Logic in Intelligent System De-sign. Cham: Springer International Publishing, 2017, pp. 232–241. https://doi.org/10.1007/978-3-319-67137-6_25.
F. H. Ajeil, I. K. Ibraheem, A. J. Humaidi and Z. H. Khan. A novel path planning algorithm for mobile robot in dynamic environments using modified bat swarm optimization. The Journal of Engineering, 2021, no 1, pp. 37–48. https://doi.org/10.1049/tje2.12009
M.A. Contreras-Cruz, V. Ayala-Ramirez and U. H. Hernandez-Belmonte. Mobile robot path planning using artificial bee colony and evolu-tionary programming. Applied Soft Computing, 2015, vol. 30, pp. 319-328. https://doi.org/10.1016/j.asoc.2015.01.067.
Y.Y. Cui, W. Hu and A. Rahmani. Fractional-order artificial bee colony algorithm with applica-tion in robot path planning. European Journal of Operational Research, 2022. https://doi.org/10.1016/j.ejor.2022.11.007
C. B. Kalayci, O. Ertenlice, H. Akyer and H. Aygoren. An artificial bee colony algorithm with feasibility enforcement and infeasibility tolera-tion procedures for cardinality constrained port-folio optimization, Expert Systems With Applica-tions, 2017, vol. 85, pp. 61–75. https://doi.org/10.1016/j.eswa.2017.05.018
X.-S. Yang and Suash Deb. Cuckoo Search via Lévy flights. 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 2009, pp. 210-214. https://doi.org/10.1109/NABIC.2009. 5393690.
P. K. Mohanty and D. R. Parhi. Optimal path planning for a mobile robot using cuckoo search algorithm, Journal of Experimental & Theoreti-cal Artificial Intelligence, 2014, vol. 28, no 1-2, pp. 35–52. https://doi.org/10.1080/0952813x.2014.971442.
P. K. Mohanty and D. R. Parhi. Cuckoo search algorithm for the mobile robot navigation. In Swarm, Evolutionary, and Memetic Computing. Cham: Springer International Publishing, 2013, pp. 527–536. https://doi.org/10.1007/978-3-319-03753-0_47
K. Sharma, S. Singh and R. Doriya. Optimized cuckoo search algorithm using tournament selec-tion function for robot path planning. Interna-tional Journal of Advanced Robotic Systems, 2021, vol. 18, no 3, p. 172988142199613. https://doi.org/10.1177/1729881421996136.
X. S. Yang and S. Deb. Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimi-sation, 2010, vol. 1, no 4, pp. 330. https://doi.org/10.1504/ijmmno.2010.035430.
S. Mirjalili, S. M. Mirjalili and A. Lewis. Grey wolf optimizer. Advances in Engineering Software, 2014, vol. 69, pp. 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007.
A. Mallikarjuna Rao, K. Ramji and T. Naveen Kumar. Intelligent navigation of mobile robot us-ing grey wolf colony optimization. Materials To-day: Proceedings, 2018, vol. 5, no 9, pp. 19116–19125. https://doi.org/10.1016/j.matpr.2018.06.265
M. Petrović, A. Jokić, Z. Miljković and Z. Kulesza. Multi-objective scheduling of single mobile robot based on grey wolf optimization al-gorithm. SSRN Electronic Journal, 2022. 29 p. [Online]. Available: https://doi.org/10.2139/ssrn.4058009
L. Doğan and U. Yüzgeç. Robot path planning using gray wolf optimizer. International Confer-ence on Advanced Technologies, Computer En-gineering and Science (ICATCES’18). [Online]. Available: http://indexive.com/uploads/papers/icatces2018-17.pdf
E. Malayjerdi, M. Yaghoobi and M. Kardan. Mobile robot navigation based on fuzzy cogni-tive map optimized with grey wolf optimization algorithm used in augmented reality. In 2017 5th RSI International Conference on Robotics and Mechatronics (ICRoM), Tehran, Iran, 25–27 Oct. 2017. IEEE. [Online]. Available: https://doi.org/10.1109/ icrom.2017.8466169
R. Kumar, L. Singh and R. Tiwari. Path planning for the autonomous robots using modified grey wolf optimization approach. Journal of Intelli-gent & Fuzzy Systems, 2021, vol. 40, no 5, pp. 9453–9470 https://doi.org/10.3233/jifs-201926.
