Using the delaunay triangulation and voronoi diagrams for navigation in observable environments

Uso de la triangulación Delaunay y diagramas de Voronoi para la navegación en entornos observables

Autores/as

  • Fernando Martínez Santa Universidad Distrital Francisco José de Caldas
  • Fredy Hernán Martínez Sarmiento Universidad Distrital Francisco José de Caldas
  • Edwar Jacinto Gómez Universidad Distrital Francisco José de Caldas

Descargas

Resumen (en)

The navigation system of mobile robot should have the capability of environment cognition, action decision, motion control, and state monitoring. This paper proposes a prediction algorithm route based on Voronoi diagrams, applicable for mobile robots with range sensors operating in indoor and unknown environments. The proposed control law is a hybrid navigation strategy composed of Voronoi diagrams and Delaunay triangulation, which is used to avoid the routes that may eventually block the advance of the robot. An efficient implementation of the control law is presented. Simulation results validate the efficacy of the proposed modified control law.

Resumen (es)


El sistema de navegación del robot móvil debe tener la capacidad de conocimiento del entorno, decisión de acción, control de movimiento y monitoreo del estado. Este documento propone una ruta de algoritmo de predicción basada en diagramas de Voronoi, aplicable para robots móviles con sensores de rango que operan en entornos interiores y desconocidos. La ley de control propuesta es una estrategia de navegación híbrida compuesta por diagramas de Voronoi y triangulación de Delaunay, que se utiliza para evitar las rutas que eventualmente pueden bloquear el avance del robot. Se presenta una implementación eficiente de la ley de control. Los resultados de la simulación validan la eficacia de la ley de control modificada propuesta.

Biografía del autor/a

Fernando Martínez Santa, Universidad Distrital Francisco José de Caldas

Ingeniero en Control Electrónico e Instrumentación, magíster en Ingeniería Electrónica y de Computador. Docente, Universidad Distrital Francisco José de caldas. Bogotá.

Fredy Hernán Martínez Sarmiento, Universidad Distrital Francisco José de Caldas

Ingeniero Electricista, especialista en Gestión de Proyectos de Ingeniería, candidato a doctor en Ingeniería. Docente, Universidad Distrital Francisco José de Caldas. Bogotá.

Edwar Jacinto Gómez, Universidad Distrital Francisco José de Caldas

Ingeniero en Control Electrónico e Instrumentación, magíster (c) en Ciencias de la Informacion y Comunicaciones. Docente, Universidad Distrital Francisco José de Caldas. Bogotá.

Referencias

Afzulpurkar, N. & Thanh, N. T. (2008). Path planning for a mobile robot in a dynamic environment. In IEEE International Conference on Robotics and Biomimetics ROBIO 2008, 2115-2120.

Bin-qiang, Y.; Ming-fu, Z. & Yi, W. (2011). Research of path planning method for mobile robot based on artificial potential field. In 2011 International Conference on Multimedia Technology ICMT, 3192-3195.

Bobadilla, L.; Martínez, F.; Gobst, E.; Gossman, K. & LaValle, S. M. (2012). Controlling wild mobile robots using virtual gates and discrete transitions. In American Control Conference ACC2012, 743-749.

Cuevas, E.; Zaldívar, D. & Pérez, M. (2010). Procesamiento digital de imágenes con Matlab y Simulink. México: Alfaomega Grupo Editor.

Demyen, D. & Buro, M. (2006). Efficient triangulation-based pathfinding. In Proceedings of the 21st National Conference on Artificial Intelligence, AAAI American Association for Artificial Intelligence, 942-947.

Dong, H.; Li, W.; Zhu, J. & Duan, S. (2010). The path planning for mobile robot based on Voronoi diagram. In 2010 3rd International Conference on Intelligent Networks and Intelligent Systems ICINIS, 446-449.

Guanghui, L.; Yamashita, A.; Asama, H. & Tamura, Y. (2012). An efficient improved artificial potential field based regression search method for robot path planning. In 2012 International Conference on Mechatronics and Automation ICMA, 1227-1232.

Hongyang, Y.; Huifang, W.; Yangzhou, Ch. & Guiping, D. (2008). Path planning based on constrained Delaunay triangulation. In 7Th World Congress on intelligent control and automation 2008, 5168-5173.

Kallmann, M. (2005). Path planning in triangulations. In Proceedings of the Workshop on Reasoning, Representation, and Learning in Computer Games, International Joint Conference on Artificial Intelligence IJCAI, 49-54.

LaValle, S. M. (2006). Planning algorithms. Cambridge, U.K.: Cambridge University Press.

Mannadiar, R. (2010). Optimal coverage of a known arbitrary environment. In 2010 IEEE International Conference on Robotics and Automation ICRA, 5525-5530.

Okabe, A.; Boots, B.; Sugihara, K. & Chiu, S. N. (2000). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. England: John Wiley & Sons, Ltd.

Ollero, A. (1995). Planificación de trayectorias para Robots Móviles. España: Universidad de Málaga.

Ortega, L. (2010). El Diagrama de Voronoi. España: Universidad de Jaen.

Rombaut, M.; Segovia, A.; Meziel, D. & Preciado, A. (1991). Displacements of a mobile robot in a known environment. In IMACS-IFAC Symposium MCTS.

Shao, M. & Lee, J. Y. (2010). Development of autonomous navigation method for nonholonomic mobile robots based on the generalized Voronoi diagram. In 2010 International Conference on Control Automation and Systems ICCAS, 309-313.

Zhang, L.; Kim, Y. J. & Manocha, D. (2007). A hybrid approach for complete motion planning. In IEEE/RSJ International Conference on Intelligent Robots and Systems IROS 2007, 7-14.

Xu, D.; Zhang, F. & Yao, Y. (2009). Constructing visibility graph and planning optimal path for inspection of 2D workspace. In IEEE International Conference on Intelligent Computing and Intelligent Systems ICIS 2009, 693-698

Cómo citar

APA

Martínez Santa, F., Martínez Sarmiento, F. H., y Jacinto Gómez, E. (2014). Using the delaunay triangulation and voronoi diagrams for navigation in observable environments. Tecnura, 18, 81–88. https://doi.org/10.14483/udistrital.jour.tecnura.2014.SE1.a06

ACM

[1]
Martínez Santa, F. et al. 2014. Using the delaunay triangulation and voronoi diagrams for navigation in observable environments. Tecnura. 18, (dic. 2014), 81–88. DOI:https://doi.org/10.14483/udistrital.jour.tecnura.2014.SE1.a06.

ACS

(1)
Martínez Santa, F.; Martínez Sarmiento, F. H.; Jacinto Gómez, E. Using the delaunay triangulation and voronoi diagrams for navigation in observable environments. Tecnura 2014, 18, 81-88.

ABNT

MARTÍNEZ SANTA, Fernando; MARTÍNEZ SARMIENTO, Fredy Hernán; JACINTO GÓMEZ, Edwar. Using the delaunay triangulation and voronoi diagrams for navigation in observable environments. Tecnura, [S. l.], v. 18, p. 81–88, 2014. DOI: 10.14483/udistrital.jour.tecnura.2014.SE1.a06. Disponível em: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/8159. Acesso em: 28 mar. 2024.

Chicago

Martínez Santa, Fernando, Fredy Hernán Martínez Sarmiento, y Edwar Jacinto Gómez. 2014. «Using the delaunay triangulation and voronoi diagrams for navigation in observable environments». Tecnura 18 (diciembre):81-88. https://doi.org/10.14483/udistrital.jour.tecnura.2014.SE1.a06.

Harvard

Martínez Santa, F., Martínez Sarmiento, F. H. y Jacinto Gómez, E. (2014) «Using the delaunay triangulation and voronoi diagrams for navigation in observable environments», Tecnura, 18, pp. 81–88. doi: 10.14483/udistrital.jour.tecnura.2014.SE1.a06.

IEEE

[1]
F. Martínez Santa, F. H. Martínez Sarmiento, y E. Jacinto Gómez, «Using the delaunay triangulation and voronoi diagrams for navigation in observable environments», Tecnura, vol. 18, pp. 81–88, dic. 2014.

MLA

Martínez Santa, Fernando, et al. «Using the delaunay triangulation and voronoi diagrams for navigation in observable environments». Tecnura, vol. 18, diciembre de 2014, pp. 81-88, doi:10.14483/udistrital.jour.tecnura.2014.SE1.a06.

Turabian

Martínez Santa, Fernando, Fredy Hernán Martínez Sarmiento, y Edwar Jacinto Gómez. «Using the delaunay triangulation and voronoi diagrams for navigation in observable environments». Tecnura 18 (diciembre 1, 2014): 81–88. Accedido marzo 28, 2024. https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/8159.

Vancouver

1.
Martínez Santa F, Martínez Sarmiento FH, Jacinto Gómez E. Using the delaunay triangulation and voronoi diagrams for navigation in observable environments. Tecnura [Internet]. 1 de diciembre de 2014 [citado 28 de marzo de 2024];18:81-8. Disponible en: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/8159

Descargar cita

Visitas

537

Dimensions


PlumX


Descargas

Los datos de descargas todavía no están disponibles.

Artículos más leídos del mismo autor/a

1 2 3 4 > >> 
Loading...