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

  • 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

Resumen (en_US)

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_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.

Descargas

La descarga de datos todavía no está disponible.

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
Martínez Santa, F., Martínez Sarmiento, F. H., & Jacinto Gómez, E. (2014). Uso de la triangulación Delaunay y diagramas de Voronoi para la navegación en entornos observables. Tecnura, 18, 81-88. https://doi.org/10.14483/udistrital.jour.tecnura.2014.SE1.a06
Publicado: 2014-12-01
Sección
Investigación

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

1 2 3 4 > >>