Printer Friendly

Uso de la triangulacion de delaunay y los diagramas de voronoi para navegacion en ambientes observables.

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


The route planning strategies for autonomous mobile robots have been fairly treated in many references (LaValle, 2006; Zhang et al., 2007; Afzulpurkar & Thanh, 2008; Mannadiar, 2010; Bobadilla et al., 2012). We seek to avoid obstacles using global strategies: the first and most used ones are artificial potential fields (Guanghui et al., 2012; Bin-qiang et al., 2011) or algorithms specifically purely geometric triangulation (Kallmann, 2005; Xu et al., 2009; Demyen & Buro, 2006) and many other cell-based geometry such as Voronoi diagrams (Dong et al., 2010; Shao & Lee, 2010), as well as the Delaunay method (Hongyang et al., 2008) that is also interesting. Each one of the above methods have their own difficulties and require specific criteria, such as the method based on artificial potential fields that suggests the challenge of local minima, while triangulation algorithms have problems in the decision and prediction less than the possible routes, and in some cases the algorithms to choose the best route are necessary as Dijkstra's (Dong et al., 2010). In this research, these techniques and some taken from image processing are applied, some of these navigation strategies have been studied by the research group to check its performance and behavior; in the near future comparisons will be made with each of them, in this specific job we choose a combination of Voronoi diagrams with the use of the Delaunay triangulation, implementation and simulation.

Voronoi diagrams are part of the most significant route planning structures in computational geometry. These diagrams basically start from the comparison between elements near in a plan (Okabe et al., 2000). In this method is essential to consider the route as far as possible of the obstacles. So in a 2-dimensional space, all points that are equidistant from two barriers are considered part of the Voronoi diagram (figure 1).

The Voronoi diagram is denoted as a set of points P = {[p.sub.1], [p.sub.2], [p.sub.3], ..., [p.sub.n]} in the plan, or in any m-dimensional space. In this set a particular classification is done, which consists in verify the Euclidean distance of each point regarding to the other points, calculating the distance d(p, q), distance defined as shown in equation (1):

d(p, q) = [square root of ([([p.sub.x] - [q.sub.x]).sup.2] + [([p.sub.y] - [q.sub.y]).sup.2])] (1)

Furthermore, it is defined V([p.sub.i]) as the Voronoi cell for [p.sub.i], which becomes the set of q points in the plan which are closer to [p.sub.i] than any other element. Therefore, the Voronoi cell of [p.sub.i] is defined as shown in equation (2):

v([p.sub.i]) = {q [parallel][P.sub.i]q[parallel] <[parallel] [P.sub.j]q[parallel],bj [not equal to] i} (2)

This defines the Euclidean distance between p and q. Finally, it is defined the Voronoi diagram of P, called Vor(P), as the plan which has been divided into n Voronoi cells V([p.sub.j]), one for each point in P (Okabe et al., 2000).

This paper is organized as follows: Section 2 presents the basic concepts of Voronoi diagrams as base navigation algorithm. In Section 3, the steps to implement the algorithm are presented, and in Section 4, the results and simulations with different environments are shown. Section 5, the paper is concluded.


The problem is to discard the use of onboard sensors (on the robot). The use of images to the environment taken with a camera is considered, instead. From these images, the information of the robots and obstacles are extracted; then, this information to implement the routing prediction algorithm is used. Therefore, the central control unit is responsible to calculate the navigation path and to control the movement of the robot, that is always possible to sense and known the environment. This means that the position of the robot and the obstacles in the environment are always known.

Let W [subset] [R.sup.2] be the closure of a contractible open set in the plan that has a connected open interior with obstacles that represent inaccessible regions. Let 0 be a set of obstacles, in which each O [subset] O is closed with a connected piecewise-analytic boundary that is finite in length. Furthermore, the obstacles in 0 are pairwise-disjoint and countably finite in number. Let E [subset] W be the free space in the environment, which is the open subset of W with the obstacles removed, and the boundary, [partial derivative]E, of E is the image of a piecewise-analytic closed curve.

The goal is to plan optimal navigation routes through the free space E using a global algorithm. We also use an internal algorithm to determine the best path; i.e., an algorithm that eliminates local minima, paths that block the movement of the robot, and very long paths.

The path planning should be done by image processing (figure 2). The proposed navigation algorithm (which is supported on Voronoi diagrams) must calculate the optimal route from the navigation information extracted from the images, and with the starting and arrival (or target) points.

An improvement to the design of paths with Voronoi diagrams are proposed, particularly addressing the question of the possible closed paths using Delaunay triangulation as a solution, in addition a recursive algorithm that verifies that the selected path is the shortest of the paths defined by Voronoi is implemented.


Voronoi diagrams as paths prediction method have a lower risk of collision for robot navigation within an environment, since it has a projection of free space E on a one-dimensional curves network. Formally, it is defined as a retraction (Ortega, 2010) with preservation of continuity. If the set [C.sub.l] defines the unobstructed positions of an environment, the retraction function [R.sub.T] builds a continuous subset [C.sub.v] of [C.sub.l] (equation (3)) (Ollero, 1995).

RT(q): [C.sub.l] [right arrow] [C.sub.v]/ [C.sub.v] [subset] [C.sub.l] (3)

Thus, it is said that there is a path from a starting point [q.sub.a] to another end point [q.sub.f], which is free of obstacles, if and only if there is a continuous curve from RT([q.sub.a]) to RT([q.sub.f]).

Obstacles represented as points

Considering the obstacles of a map as points (figure 3), the following properties can be defined (Ortega, 2010):

* Two points [p.sub.i] and [p.sub.j] are neighbors if they share an edge. An edge is the perpendicular bisector of the segment [p.sub.i][p.sub.j].

* A vertex is a point equidistant from three generators (if it is more than three, then degenerate cases are had) and it is the intersection of three edges.

* A Voronoi region is a convex polygon or an unbounded region.

* A Voronoi region is unbounded if its generating point belongs to the convex hull of the point cloud.

3.2 Obstacles represented as polygons

The retraction function RT definition involves construction of the Voronoi diagram (Rombaut et al., 1991). In order to make more realistic the obstacles representation, and according to the formulation of the problem, the obstacles are interpreted not as points but as polygons. Thus, the Voronoi diagram is formed by two kinds of segments: rectilinear and parabolic.

Figure 4 shows the Voronoi diagram [C.sub.v], and is represented by the demarcated lines. The environment W is delimited by polygon edges {[e.sub.1], [e.sub.2], [e.sub.3], [e.sub.4]}, the triangular obstacle vertices {[n.sub.1], [n.sub.2], [n.sub.3]} and the triangular obstacle edges {[a.sub.1], [a.sub.2], [a.sub.3]}. In the figure two kinds of lines that compose the Voronoi diagram can be seen. The segment [s.sub.1] is the locus of equidistant points between the edge [e.sub.1], and the vertex [n.sub.2]. Similarly, the rectilinear segment [s.sub.2] is defined in the same way, but with regard to the edges [e.sub.1] and [e.sub.2]. Given a configuration that does not belong to [C.sub.v], there is a unique nearest point p belonging to a vertex or edge of an obstacle O. The function RT(q) is defined as the first cut with [C.sub.v] of the line linking p with q (figure 5) (Ollero, 1995).

For path planning, the Voronoi algorithm tries to find the sequence of line segments for connecting RT([q.sub.a]) with RT([q.sub.f]). The algorithm (Ollero, 1995):

* Calculate the Voronoi diagram.

* Calculate RT([q.sub.a]) and RT([q.sub.f]).

* Find the sequence of segments {[s.sub.1], ..., [s.sub.p]} such that RT(q) belongs to [s.sub.1] and RT([q.sub.f]) belongs to [s.sub.p].

* If it finds such a sequence, then it delivers the path. Otherwise it indicates error condition.


Application was performed in MatLab, using some techniques of basic image processing (Cuevas et al., 2010). As a first step, the image is required from a file or from a camera located on the environment. The image is pre-processed and converted to a binary matrix. When having this initial file, the obstacles within the environment are labeled and listed, the position of these obstacles are stored as well as its dimensions. From this moment the central unit has all the information about, E and the boundary [partial derivative]E of E.

The next step is the construction of the Voronoi diagram. The environment the function that calculates the Voronoi cells is applied, this function gives as a result a series of navigation solutions. With the Voronoi diagram, and with the information about the obstacles, the Voronoi diagram the starting and target points are added. Using Euclidean distance, these points are determined on where they are connected.

Finally, the optimal paths for navigation must be determined. The Delaunay triangulation to verify the robot to navigate at a distance r from obstacles is applied. This distance r is calculated as the radius of a circle that circumscribes the robot. For the selection of the final path, a recursive method that compares the different routes using the Euclidean distance is applied (figure 6).


The algorithm was tested on a total of 20 different lab environments, making a total of 40 trials. In each of these tests, the start and target points were randomly selected. In the algorithm, the robot was taken as a circle of radius r = 10.5 cm according to the geometry of the laboratory robots. The environment used was a rectangle of 7 m high and 5.5 m wide.

Some of the most significant tests are shown in figure 7. In this figure the Voronoi diagram with the path chosen by the algorithm for four different cases is shown.


This paper proposes a hybrid scheme for robot navigation combining two geometric navigation strategies. The modification and verification of Voronoi diagrams with the Delaunay triangulation algorithm avoids possible routes impending collisions, and leaves the road ready for implementing an algorithm using a single Euclidean metric. This gives as a general result that the algorithm chooses, in most cases, the obstacle peripheral roads within the scene, eventually shipping lanes are full of obstacles away with smooth curves and a reasonable distance.

This paper presents an implementation of predicting cell routes, which makes the computational cost be low and these results can be easily measured. The measured times with different scenarios are between 1 and 3 s, using an Intel Core I7 with 8 Gigabytes Ram running Windows 7 64 bits and Mat Lab R2011a. This is a time extremely low, but plotted against delivery routes are not the most optimal, often routes are entirely peripheral.

Such algorithms are based on a central unit which makes its implementation easy because it simply performed without using external sensors, only a low-resolution camera and a personal computer with basic characteristics, in this case only scenarios were applied to static, but as future work it could be implemented for dynamic applications.

The performance of the proposed algorithm was verified through several simulations.

DOI: 10.14483/udistrital.jour.tecnura.2014.SE1.a06


This work was supported by the Universidad Distrital Francisco Jose de Caldas, in part through CIDC, and partly by the Faculty of Technology. The views expressed in this paper are not necessarily endorsed by Universidad Distrital. The authors thank the research groups DIGITI and ARMOS for the evaluation carried out on prototypes of ideas and strategies.


Universidad Distrital Francisco Jose de Caldas


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.; Martinez, 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.; Zaldivar, D. & Perez, M. (2010). Procesamiento digital de imagenes con Matlab y Simulink. Mexico: 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). Planificacion de trayectorias para Robots Moviles. Espana: Universidad de Malaga.

Ortega, L. (2010). El Diagrama de Voronoi. Espana: 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.

Fecha de recepcion: 31 de marzo de 2013, Fecha de aceptacion: 16 de mayo de 2014

Fernando Martinez Santa, Ingeniero en Control Electronico e Instrumentacion, magister en Ingenieria Electronica y de Computador. Docente, Universidad Distrital Francisco Jose de caldas. Bogota, Colombia. Contacto:

Fredy Hernan Martinez Sarmiento, Ingeniero Electricista, especialista en Gestion de Proyectos de Ingenieria, candidato a doctor en Ingenieria. Docente, Universidad Distrital Francisco Jose de Caldas. Bogota, Colombia. Contacto:

Edwar Jacinto Gomez, Ingeniero en Control Electronico e Instrumentacion, magister (C) en Ciencias de la Informacion y Comunicaciones. Docente, Universidad Distrital Francisco Jose de Caldas. Bogota, Colombia. Contacto:

Caption: Figure 1. Voronoi diagram, cell division stage (Dong et al., 2010).

Caption: Figure 2. Camera as environment sensor.

Caption: Figure 3. Voronoi diagram and properties (Ortega, 2010).

Caption: Figure 4. Retraction of free space E on Voronoi diagram (Ollero, 1995).

Caption: Figure 5. A configuration q in the Voronoi diagram (Ollero, 1995).

Caption: Figure 6. Steps in the proposed algorithm.

Caption: Figure 7. These are four different environments with the navigational paths calculated by the proposed algorithm.
COPYRIGHT 2014 Universidad Distrital Francisco Jose de Caldas
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Investigacion
Author:Martinez Santa, Fernando; Martinez Sarmiento, Fredy Hernan; Jacinto Gomez, Edwar
Publication:Revista Tecnura
Date:Sep 1, 2014
Previous Article:Modelo para identificacion de cargas perturbadoras de la calidad de potencia electrica en cuanto al fenomeno armonico en una s/e.
Next Article:Identificacion de lesiones cerebrales de esclerosis multiple en imagenes de resonancia magnetica mediante analisis de textura.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters