Publicado:
2022-04-15Número:
Vol. 16 Núm. 1 (2022)Sección:
Visión InvestigadoraPlanificación de trayectorias usando metaheurísticas
Path planning using metaheuristics
Palabras clave:
Ant Colony optimization, Artificial Bee Colony, Mobile Robot, Robotic simulation (en).Palabras clave:
Colonia de abejas, Colonia de hormigas, Robot Móvil, Simulación de robots (es).Descargas
Resumen (es)
En este trabajo se presenta una comparación entre dos métodos metaheurísticos para resolver problemas de planificación de rutas. Estos métodos son: 1) Colonia de hormigas artificiales y 2) Colonia de abejas artificiales. Para evaluar estas implementaciones, se utilizan las siguientes métricas: 1) Longitud de ruta y 2) Tiempo de ejecución. El comparativo se probó utilizando diez mapas obtenidos del Departamento de Cibernética Inteligente y Mobil Robotics Group de la Universidad de Praga. Se realizaron varias ejecuciones con el objetivo de encontrar los mejores parámetros de los algoritmos y obtener el mejor algoritmo para la tarea de planificación de ruta. El mejor algoritmo fue la colonia de abejas artificiales. Estas evaluaciones se visualizaron utilizando el paquete VPython, aquí se simuló un robot móvil diferencial para seguir la trayectoria calculada por el mejor algoritmo. A partir de esta simulación fue posible observar que el robot realiza la trayectoria correcta desde el punto de inicio hasta el punto objetivo en cada uno de los mapas evaluados.
Resumen (en)
In this work, a comparison between two metaheuristic methods to solve the path planning problem is presented. These methods are 1) Artificial ant colony and 2) Artificial bee colony. The following metrics are used to evaluate these implementations: 1) Path length and 2) Execution time. The comparison was tested using ten maps obtained from the University of Prague Department of Intelligent Cybernetics and the Mobil Robotics Group. Several runs were carried out to find the best algorithm parameters and get the best algorithm for the route planning task. The best algorithm was the artificial bee colony. These evaluations were visualized using the VPython package; here, a differential mobile robot was simulated to follow the trajectory calculated by the best algorithm. This simulation made it possible to observe that the robot makes the correct trajectory from the starting point to the objective point in each evaluated map.
Referencias
P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968. https://doi.org/10.1109/TSSC.1968.300136
J. H. Holland, “Genetic algorithms”, Scientific American, vol. 267, no. 1, pp. 44-50, 1992. https://doi.org/10.1038/scientificamerican0792-66
M. Dorigo, G. Di Caro. "Ant colony optimization: a new meta-heuristic", Congress on Evolutionary Computation, 1999. CEC 99. Proceedings of 1999, vol. 2, 1999.
A. K. Guruji, H. Agarwal, D. K. Parsediya, "Time-efficient A* Algorithm for Robot Path Planning", Procedia Technology, vol. 23, pp. 144-149, 2016, https://doi.org/10.1016/j.protcy.2016.03.010
D. L. Almanza Ojeda, Y. Gomar Vera, M. A. Ibarra Manzano, "Obstacle Detection and Avoidance by a Mobile Robot Using Probabilistic Models", IEEE Latin America Transactions, vol. 13, no. 1, pp. 69-75, 2015. https://doi.org/10.1109/TLA.2015.7040630
G. D. Goez, R. A. Velasquez Velez, J. S. Botero Valencia, "UAV route planning optimization using PSO implemented on microcontrollers", IEEE Latin America Transactions, vol. 14, no. 4, pp. 1705-1710, 2016. https://doi.org/10.1109/TLA.2016.7483504
H. E. Espitia Cuchango, J. Sofrony Esmeral, “Algoritmo para la planeación de trayectorias de robots móviles empleando enjambres de partículas brownianas”, Visión Electrónica, vol. 5, no. 1, pp. 4–14, 2011.
X. Li, D. Wu, J. He, M. Bashir, M. Liping, "An Improved Method of Particle Swarm Optimization for Path Planning of Mobile Robot”, Journal of Control Science and Engineering, 2020. https://doi.org/10.1155/2020/3857894
C. Marquez Sanchez et al., "Trajectory Generation for Wheeled Mobile Robots Via Bézier Polynomials”, in IEEE Latin America Transactions, vol. 14, no. 11, pp. 4482-4490, 2016. https://doi.org/10.1109/TLA.2016.7795818
G. Diaz-Arango, H. Vázquez-Leal, L. Hernandez-Martinez, M. T. S. Pascual and M. Sandoval-Hernandez, "Homotopy Path Planning for Terrestrial Robots Using Spherical Algorithm”, in IEEE Transactions on Automation Science and Engineering, vol. 15, no. 2, pp. 567-585, 2018. https://doi.org/10.1109/TASE.2016.2638208
S. G. Moctezuma Gutiérrez, A. Cruz Pazarán, R. Galicia Mejía, L. N. Oliva Moreno, “Desarrollo de plataforma para implementación de robots colaborativos”, Vis. Electron., vol. 12, no. 1, pp. 22–31, 2018. https://doi.org/10.14483/22484728.13308
A. Rodríguez-Molina, J. Solís-Romero, M. G. Villarreal-Cervantes, O. Serrano-Pérez, and G. Flores-Caballero, “Path-Planning for Mobile Robots Using a Novel Variable-Length Differential Evolution Variant”, Mathematics, vol. 9, no. 4, p. 357, 2021 https://doi.org/10.3390/math9040357
F. Campos Archila, V. Pinzón Saavedra, F. Robayo Betancourt, “Fuzzy control of quadrotor Ar. Drone 2.0 in a controlled environment”, Vis Electron., vol. 13, no. 1, pp. 39–49, feb. 2019. https://doi.org/10.14483/22484728.14406
D. Canca, A. De-Los-Santos, G. Laporte, J. A. Mesa, "An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem”, Elsevier Computers & Operations Research, vol. 78, pp. 1–14, 2017. https://doi.org/10.1016/j.cor.2016.08.008
Y. Kergosein, Ch. Lenté, J. Billaut, S. Perrin, "Metaheuristic algorithms for solving two interconnected vehicle routing problems in a hospital complex”, Elsevier Computers & Operations Research, vol. 40, pp. 2508–2518, 2013. https://doi.org/10.1016/j.cor.2013.01.009
J. C. Ferreira, M. T. Arns Steiner, and M. Siqueira Guersola, "A Vehicle Routing Problem Solved Through Some Metaheuristics Procedures: A Case Study”, in IEEE Latin America Transactions, vol. 15, no. 5, pp. 943-949, 2017. https://doi.org/10.1109/TLA.2017.7910210
S. Q. Liu, E. Kozana, "A hybrid metaheuristic algorithm to optimize a real-world robotic cell”, Elsevier Computers & Operations Research, 2016. https://doi.org/10.1016/j.cor.2016.09.011
R. M. Molano Pulido, F. Parca Acevedo, F. M. Cabrera, H. Ñungo Londoño, “Prototipo control de vehículo robot por señales EMG”, Vis. Electron., vol. 15, no. 2, 2021.
K. Hao, J. Zhao, K. Yu, C. Li, C. Wang, "Path Planning of Mobile Robots Based on a Multi-Population Migration Genetic Algorithm”, Sensors, vol. 20, no. 20, p. 5873, 2020. https://doi.org/10.3390/s20205873
R. K. Panda, B. B. Choudhury, "An Effective Path Planning of Mobile Robot Using Genetic Algorithm”, 2015 IEEE International Conference on Computational Intelligence & Communication Technology, pp. 287-291, 2015. https://doi.org/10.1109/CICT.2015.145
S. Wu, Y. Du, Y. Zhang, "Mobile Robot Path Planning Based on a Generalized Wavefront Algorithm”, Mathematical Problems in Engineering, vol. 2020, 2020. https://doi.org/10.1155/2020/6798798
S. K. Pattnaik, D. Mishra, S. Panda, “A comparative study of meta-heuristics for local path planning of a mobile robot”, Engineering Optimization, 2021. https://doi.org/10.1080/0305215X.2020.1858074
D. Karaboga, "An idea based on honey bee swarm for numerical optimization”, Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, vol. 200, 2005.
R. Razif, N. Perumal, I. Elamvazuthi, M. Kamal Tageldeen, M. Ahamed Khan, S. Parasuraman, "Mobile robot path planning using Ant Colony Optimization", in Robotics and Manufacturing Automation (ROMA), 2016 2nd IEEE International Symposium on, pp. 1-6, 2016. https://doi.org/10.1109/ROMA.2016.7847836
L. Jianhua, J. Yang, H. Liu, X. Tian, M. Gao. "An improved ant colony algorithm for robot path planning", Soft Computing, vol. 21, no. 19, pp. 5829-5839, 2017. https://doi.org/10.1007/s00500-016-2161-7
Y. Zhongrui, Y. Houyu, H. Miaohua, "Improved Ant Colony Optimization Algorithm for Intelligent Vehicle Path Planning”, 2017 International Conference on Industrial Informatics - Computing Technology, Intelligent Technology, Industrial Information Integration (ICIICII), Wuhan, pp. 1-4, 2017. https://doi.org/10.1109/ICIICII.2017.55
L. Yong, L. Yu, G. Yipei, C. Kejie, "Cooperative path planning of robot swarm based on ACO”, 2017 IEEE 2nd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), Chengdu, pp. 1428-1432, 2017. https://doi.org/10.1109/ITNEC.2017.8285033
E. Mouhcine, M. Khalifa, Y. Mohamed, "Route optimization for school bus scheduling problem based on a distributed ant colony system algorithm”, 2017 Intelligent Systems and Computer Vision (ISCV), Fez, pp. 1-8, 2017.
Y. Gigras, K. Choudhary, K. Gupta, Vandana, "A hybrid ACO-PSO technique for path planning”, 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom), New Delhi, pp. 1616-1621, 2015.
Y. Tao, H. Gao, F. Ren, C. Chen, T. Wang, H. Xiong, S. Jiang, "A Mobile Service Robot Global Path Planning Method Based on Ant Colony Optimization and Fuzzy Control”, Applied Sciences, vol. 11, no. 8, p. 3605, 2021. https://doi.org/10.3390/app11083605
M. Contreras-Cruz, V. Ayala-Ramirez, H. Hernandez-Belmonte. "Mobile robot path planning using artificial bee colony and evolutionary programming", Applied Soft Computing, vol. 30, pp. 319-328, 2015. https://doi.org/10.1016/j.asoc.2015.01.067
P. Bhattacharjee, P. Rakshit, I. Goswami, A. Konar, A. Nagar, "Multi-robot path-planning using artificial bee colony optimization algorithm", in Nature and Biologically Inspired Computing (NaBIC), pp. 219-224, 2011. https://doi.org/10.1109/NaBIC.2011.6089601
A. Nizar Hadi, J. Ahmed Abdulsaheb. "An Adaptive Multi-Objective Artificial Bee Colony Algorithm for Multi-Robot Path Planning", Association of Arab Universities Journal of Engineering Sciences, vol. 24, no. 3, pp. 168-189, 2017.
L. Jun-Hao, C. Hung Lee. "Efficient collision-free path planning of multiple mobile robots system using efficient artificial bee colony algorithm”, Advances in Engineering Software, vol. 79, pp. 47-56, 2015. https://doi.org/10.1016/j.advengsoft.2014.09.006
C. H. Chen, S. Y. Jeng, C. J. Lin, "Using an Adaptive Fuzzy Neural Network Based on a Multi-Strategy-Based Artificial Bee Colony for Mobile Robot Control”, Mathematics, vol. 8, no. 8, p. 1223, 2020. https://doi.org/10.3390/math8081223
V. Vanásek, “Intelligent and Mobile Robotics Group”, 2009. [online]. Available: http://imr.felk.cvut.cz/planning/maps.xml
Possiblywrong, “Web simulador turtle”, https://possiblywrong.wordpress.com/2010/12/04/robot-simulator-and-turtle-graphics/
Python, “Web Visual Python”, http://vpython.org/
Cómo citar
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Descargar cita
Visitas
Descargas
Licencia
Derechos de autor 2022 Visión electrónica
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
.png)
atribución- no comercial 4.0 International
.jpg)
