DOI:
https://doi.org/10.14483/22487638.19197Publicado:
2024-07-26Número:
Vol. 27 Núm. 78 (2023): Octubre - DiciembreSección:
InvestigaciónCooperative strategy to reduce path length in risky environments
Estrategia cooperativa para reducir la longitud de la ruta en entornos riesgosos
Palabras clave:
agent-based modeling, autonomous robots, collaborative work, collision avoidance, cooperative systems, multiagent systems, navigation, path planning (en).Palabras clave:
modelado basado en agentes, robots autónomos, trabajo colaborativo, sistemas multiagente, navegación, planificación de rutas (es).Descargas
Resumen (en)
Objective: Design an artificial intelligence system based on information from the environment that can recommend the shortest path to an individual or vehicle, or robot that moves between two points with the lowest risk of contagion with coronavirus COVID-19.
Methodology: The cooperative strategy for path reduction involves a management and monitoring system and two explorer agents. Explorer agents are equipped with path planning algorithms (GBFS and A*) enhanced with incremental heuristics in order to find two different sets of preliminary paths (the first in direction start-goal and the second in the opposite direction). Subsequently, a management and monitoring system estimates a preliminary shortest path for each path planner then obtains a shortest path by comparing the paths attained with the path planners. This research emerges within the field of distributed intelligence in robotics to determine the benefits of teamwork interactions compared to individual work. In this study, 300 tests that involve the cooperative strategy were executed using ten different environments.
Results: The results of this paper illustrate that in 79 % of analyzed situations, definitive shortest estimated paths obtained by cooperative strategy outperformed preliminary paths found individually by path planners. Over 20.5 % of tested cases yielded significant path reductions (greater than 100 % in relation to the shortest definitive path).
Conclusions: In this work, an artificial intelligence system was designed, whose tests show a good performance. The intelligent system uses Distributed Intelligence implemented in a cooperative team formed by a management and monitoring system and two explorer agents, who, based on information from the environment, recommend the shortest path to an individual or vehicle or robot who wants to travel between two points located in an environment at risk of contagion with coronavirus COVID-19.
Financing: This work was supported in part by the Universidad Tecnológica de Pereira through Vicerrectoría de Investigaciones Innovación y Extensión, Project name: Sistema de obtención de rutas más seguras bajo situación de pandemia caso covid-19, Project code: 3-20-11, and in part by the Universidad nacional de Colombia.
Resumen (es)
Objetivo: Diseñar un sistema de inteligencia artificial que con base a información del entorno pueda recomendar la ruta más corta a un individuo que quiera desplazarse entre dos puntos con el menor riesgo de contagio con coronavirus COVID-19.
Metodología: La estrategia cooperativa para la reducción de rutas involucra un sistema de administración y monitoreo y dos agentes exploradores. Los agentes exploradores están equipados con algoritmos de planificación de rutas (GBFS y A*) mejorados con heurísticas de tipo incremental a fin de encontrar dos conjuntos diferentes de rutas preliminares (la primera en dirección inicio-meta y la segunda en dirección opuesta). Posteriormente, el sistema de administración y monitoreo estima de forma preliminar el camino más corto para cada planificador de rutas y luego se obtiene el camino más corto comparando los caminos obtenidos con cada uno de los planificadores de rutas. Esta investigación surge dentro del campo de la inteligencia distribuida en robótica para determinar los beneficios de las interacciones del trabajo en equipo frente al trabajo individual. En este estudio se ejecutaron 300 pruebas que involucran la estrategia cooperativa utilizando diez ambientes diferentes.
Resultados: Los resultados de este artículo ilustran que en el 79 % de las situaciones analizadas, las rutas estimadas más cortas obtenidas por la estrategia cooperativa fueron aún más cortas que las rutas preliminares encontradas individualmente por los planificadores de rutas. Adicionalmente, en más del 20,5 % de las pruebas realizadas se obtuvieron reducciones de ruta significativas (superiores al 100 % en relación con la ruta más corta).
Conclusiones: En este trabajo se diseñó un sistema de inteligencia artificial, cuyas pruebas muestran un buen desempeño. El sistema inteligente utiliza Inteligencia Distribuida implementada en un equipo cooperativo formado por un sistema de administración y monitoreo y dos agentes exploradores, los cuales, con base a información del entorno, recomiendan el camino más corto a un individuo o vehículo o robot que quiera desplazarse entre dos puntos ubicados en un entorno con riesgo de contagio de coronavirus COVID-19.
Financiamiento: Este trabajo es financiado en parte por la Universidad Tecnológica de Pereira a través del VIIE, Nombre del proyecto: sistema de obtención de rutas más seguras bajo situación de pandemia caso covid-19, Código del proyecto: 3-20-11 y en parte por la Universidad Nacional de Colombia.
Referencias
Aljehani, M., & Inoue, M. (2019). Performance evaluation of multi-UAV system in post-disaster application: Validated by HITL simulator. IEEE Access, 7. https://doi.org/10.1109/ACCESS.2019.2917070
Amanatiadis, A. A., Chatzichristofis, S. A., Charalampous, K., Doitsidis, L., Kosmatopoulos, E. B., Tsalides, P., . . . Roumeliotis, S. I. (2013). A multi-objective exploration strategy for mobile robotsunder operational constraints. IEEE Access, 1. https://doi.org/10.1109/ACCESS.2013.2283031
Becerra-Mora., Y.A. y Arbulu-Saavedra, M.R. (2022). Uso de robótica en una emergencia sanitaria. Tecnura, 26 núm 73, 130-141. https://doi.org/10.14483/22487638.17320
Bruce, J., & Veloso, M. M. (2003). Real-time randomized path planning for robot navigation. En Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) (Vol. 2752). https://doi.org/10.1007/978-3-540-45135-8_23
Cho, K. B., & Cho, S. Y. (2014). The concept of collision-free motion planning using a dynamic collision map. International Journal of Advanced Robotic Systems, 11. https://doi.org/10.5772/58707
Chonnaparamutt, W., & Birk, A. (2006). Using rescue robots to increase construction site safety. En 2006 Proceedings of the 23rd International Symposium on Robotics and Automation in Construction, ISARC 2006. https://doi.org/10.22260/isarc2006/0047
Duchon, F., Babinec, A., Kajan, M., Beno, P., Florek, M., Fico, T., & Jurišica, L. (2014). Path planning with modified A star algorithm for a mobile robot. En Procedia Engineering (Vol. 96). https://doi.org/10.1016/j.proeng.2014.12.098
Espitia Cuchango, H. E., & Sofrony Esmeral, J. I. (2012). Algoritmo para planear trayectorias de robots móviles, empleando campos potenciales y enjambres de partículas activas brownianas. Ciencia e Ingeniería Neogranadina, 22(2). https://doi.org/10.18359/rcin.242
Estlin, T., Volpe, R., Issa, N., Mutz, D., Fisher, F., Engelhardt, B., & Chien, S. (2001). Decision-Making in a Robotic Architecture for Autonomy. International Conference on Intelligence Analysis. https://ai.jpl.nasa.gov/public/papers/isairas01-estlin.pdf
Fernández, M. (2005). Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los juegos de video.EST. https://users.exa.unicen.edu.ar/catedras/aydalgo2/docs/TFca06aCompleto.pdf
Fortune, S., & Wilfong, G. (1991). Planning constrained motion. Annals of Mathematics and Artificial Intelligence, 3(1). https://doi.org/10.1007/BF01530887
Freedman, L. (2015). Strategy: A history. Oxford University Press.
García, D. A. L., Bravo, F. G., & del Toro Peral, M. (2007). Comparativa entre planificadores de trayectorias para su uso combinado en la generación de maniobras. https://rabida.uhu.es/dspace/bitstream/handle/10272/5501/Nuevas_aportaciones_en_algoritmos_de_planificacion.pdf?sequence=2
Garrido, S., Moreno, L., Blanco, D., & Munoz, M. L. (2007). Sensor-based global planning for mobile robot navigation. En Robotica (Vol. 25). https://doi.org/10.1017/S0263574707003384
Garrido, Santiago, Moreno, L., Blanco, D., & Martin, F. (2007). Exploratory navigation based on voronoi transform and fast marching. En 2007 IEEE International Symposium on Intelligent Signal Processing, WISP. https://doi.org/10.1109/WISP.2007.4447541
Goyal, J. K., & Nagla, K. S. (2014). A new approach of path planning for mobile robots. En Proceedings of the 2014 International Conference on Advances in Computing, Communications and Informatics, ICACCI 2014. https://doi.org/10.1109/ICACCI.2014.6968200
Guichard, D. (s/f). Combinatorics and Graph Theory. Department of Mathematics Whitman College. https://www.whitman.edu/mathematics/cgt_online/book/
Heusner, M., Keller, T., & Helmert, M. (2018). Search progress and potentially expanded states in greedy best-first search. En IJCAI International Joint Conference on Artificial Intelligence (Vol. 2018-July). https://doi.org/10.24963/ijcai.2018/735
Hussein, A. A. M. (2018). Control and communication systems for automated vehicles cooperation and coordination. http://hdl.handle.net/10016/27674
Islam, M. N., & Islam, A. K. M. N. (2020). A Systematic Review of the Digital Interventions for Fighting COVID-19: The Bangladesh Perspective. IEEE Access, 8, 114078–114087. https://doi.org/10.1109/ACCESS.2020.3002445
J.s, & M.R. (1996). Diseño y manejo de estructuras de datos en C. Mc Graw-Hill Interamericana.
Jamshidi, M., Lalbakhsh, A., Talla, J., Peroutka, Z., Hadjilooei, F., Lalbakhsh, P., . . . Mohyuddin, W. (2020). Artificial Intelligence and COVID-19: Deep Learning Approaches for Diagnosis and Treatment. IEEE Access, 8. https://doi.org/10.1109/ACCESS.2020.3001973
Kim, C., Yang, H., Kang, D., & Lee, D. (2015). 2-D cooperative localization with omni-directional mobile robots. En 2015 12th International Conference on Ubiquitous Robots and Ambient Intelligence, URAI 2015. https://doi.org/10.1109/URAI.2015.7358894
Koenig, S., & Likhachev, M. (2002). D* lite. AAAI/IAAI, 15, 476–483.
Koenig, S., Likhachev, M., & Furcy, D. (2004). Lifelong Planning A*. Artificial Intelligence, 155(1–2). https://doi.org/10.1016/j.artint.2003.12.001
Koenig, S., Likhachev, M., Liu, Y., & Furcy, D. (2004). Incremental heuristic search in AI. AI Magazine, 25(2). https://ddn.aaai.org/AAAI/2002/AAAI02-072.pdf
Konakalla, S. V. (2014). A Star Algorithm. unpublished. http://cs.indstate.edu/~skonakalla/paper.pdf
Kuhnt, F., Pfeiffer, M., Zimmer, P., Zimmerer, D., Gomer, J. M., Kaiser, V., . . . Zöllner, J. M. (2016). Robust environment perception for the audi autonomous driving cup. En IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC. https://doi.org/10.1109/ITSC.2016.7795744
Kumar Das, P., Patro, S. N., Panda, C. N., & Balabantaray, B. (2011). D* lite algorithm based path planning of mobile robot in static Environment. Int. J. Comput. Commun. Technol.(IJCCT), 2, 32–36. http://dx.doi.org/10.47893/IJCCT.2012.1158
Latombe, J.-C. (2012). Robot motion planning (Vol. 124). Springer Science & Business Media. Laumond, J. P., Jacobs, P. E., Taïx, M., & Murray, R. M. (1994). A Motion Planner for Nonholonomic Mobile Robots. IEEE Transactions on Robotics and Automation, 10(5). https://doi.org/10.1109/70.326564
LaValle, S. M. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning. In, 129. https://msl.cs.illinois.edu/~lavalle/papers/Lav98c.pdf
Liu, Y., Nejat, G., & Vilela, J. (2013). Learning to cooperate together: A semi-autonomous control architecture for multi-robot teams in urban search and rescue. En 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics, SSRR 2013. https://doi.org/10.1109/SSRR.2013.6719367
López, D., Gómez-Bravo, F., Cuesta, F., & Ollero, A. (2006). Planificación de trayectorias con el algoritmo RRT. Aplicación a robots no holónomos. Revista Iberoamericana de Automática e Informática Industrial, 3(3), 56–67. https://www.polipapers.upv.es/index.php/RIAI/article/view/8144
López García, D. A. (2011). Nuevas aportaciones en algoritmos de planificación para la ejecución de maniobras en robots autónomos no holónomos. http://hdl.handle.net/10272/5501
Lozano-Pérez, T., & Wesley, M. A. (1979). An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles. Communications of the ACM, 22(10). https://doi.org/10.1145/359156.359164
Mac, T. T., Copot, C., Tran, D. T., & De Keyser, R. (2016). Heuristic approaches in robot path planning: A survey. Robotics and Autonomous Systems, 86. https://doi.org/10.1016/j.robot.2016.08.001
Martínez-Valencia., J.L. Holguín-Londoño., M. y Ramírez-Vanegas., C.A. (2021). Methodology for the Synthesis of Automata in the Planning of Movements for Autonomous Systems with Multiple Agents. Tecnura, 25(70), 46-70. https://doi.org/10.14483/22487638.1713
Muntean, P. (2016). Mobile robot navigation on partially known maps using a fast a star algorithm version. arXiv preprint arXiv:1604.08708. https://doi.org/10.48550/arXiv.1604.08708
Murphy, R. R. (2004). Trial by fire [rescue robots]. IEEE Robotics & Automation Magazine, 11(3). https://doi.org/10.1109/MRA.2004.1337826
Murray-Lasso, M. A. (2003). Math puzzles, powerful ideas, algorithms and computers in teaching problem-solving. Journal of Applied Research and Technology, 1(03). https://doi.org/10.22201/icat.16656423.2003.1.03.606
Murray, R. M., & Sastry, S. S. (1993). Nonholonomic motion planning. Steering using sinusoids. IEEE Transactions on Automatic Control, 38(5). https://doi.org/10.1109/9.277235
Ospina, A. G., Garzán, C., & Baldomiro, H. (2011). Diseño, implementación y aplicación de una estrategia de búsqueda preferente por amplitud, para uso multidireccional sobre sistemas distribuidos o de procesamiento en paralelo, usando un simulador de escenarios, construido para el trazado de rutas en robots. https://hdl.handle.net/11059/2609
Parker, L. E. (2008). Distributed Intelligence: Overview of the Field and its Application in MultiRobot Systems. Journal of Physical Agents, 2(1). https://doi.org/10.14198/JoPha.2008.2.1.02
Patel’s, A. (s/f). Stanford, California, USA. Recuperado el 3 de agosto de 2019, de https://www.redblobgames.com/pathfinding/a-star/introduction.html
Ponticelli Lima, R. C. (2010). Sistema de exploración de terrenos con robots móviles: aplicación en tareas de detección y localización de minas antipersonas.
RamaKrishna, A., Sowmya Bala, G., S. N. Chakravarthy, A., Bhanu Prakash Sarma, B., & Sai Alla, G. (2012). Design of a Rescue Robot Assist at Fire Disaster. International Journal of Computer Applications, 47(10). https://doi.org/10.5120/7225-0056
Russell, S. J., & Norvig, P. (2016). Artificial intelligence: a modern approach. Malaysia. Pearson Education Limited London, UK.
Singh, Y., Sharma, S., Sutton, R., Hatton, D., & Khan, A. (2018). A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents. Ocean Engineering, 169, 187–201. https://doi.org/10.1016/j.oceaneng.2018.09.016
Spangelo, I., & Egeland, O. (1994). Trajectory Planning and Collision Avoidance for Underwater Vehicles Using Optimal Control. IEEE Journal of Oceanic Engineering, 19(4). https://doi.org/10.1109/48.338386
Stentz, A. (1995). Optimal and efficient path planning for unknown and dynamic environments. International Journal of Robotics and Automation, 10(3). https://doi.org/10.1007/978-1-4615-325-9_11
Sundfeld, D., Razzolini, C., Teodoro, G., Boukerche, A., & de Melo, A. C. M. A. (2018). PA-Star: A disk-assisted parallel A-Star strategy with locality-sensitive hash for multiple sequence alignment. Journal of Parallel and Distributed Computing, 112. https://doi.org/10.1016/j.jpdc.2017.04.014
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., et al. (2018). Valuedecomposition networks for cooperative multi-agent learning based on team reward. En Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (Vol. 3). https://doi.org/10.48550/arXiv.1706.05296
Vargas, H. C. (2007). Generación de trayectorias para un robot móvil Khepera II usando técnicas de aprendizaje automático. https://www.repositoriodigital.ipn.mx/bitstream/123456789/5703/1/Tesis12175.pdf
Vargas-Pardo, L.F. y Giraldo-Ramos, F.N. (2022). Firefly Algorithm for Facility Layout Optimization. Tecnura, 26(74), 35-48. https://doi.org/10.14483/22487638.17731
Vilela, J., Liu, Y., & Nejat, G. (2013). Semi-autonomous exploration with robot teams in urban search and rescue. En 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics, (SSRR 2013). https://doi.org/10.1109/SSRR.2013.6719366
Cómo citar
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Descargar cita
Licencia
Derechos de autor 2024 José Andrés Chaves Osorio, Jimy Alexander Cortés Osorio, Edward Andrés González Ríos
Esta obra está bajo una licencia internacional Creative Commons Atribución-CompartirIgual 4.0.
Esta licencia permite a otros remezclar, adaptar y desarrollar su trabajo incluso con fines comerciales, siempre que le den crédito y concedan licencias para sus nuevas creaciones bajo los mismos términos. Esta licencia a menudo se compara con las licencias de software libre y de código abierto “copyleft”. Todos los trabajos nuevos basados en el tuyo tendrán la misma licencia, por lo que cualquier derivado también permitirá el uso comercial. Esta es la licencia utilizada por Wikipedia y se recomienda para materiales que se beneficiarían al incorporar contenido de Wikipedia y proyectos con licencias similares.
