Path planning in a dynamic environment for autonomous robots is one of the most important tasks in robotics and is considered a core problem in modern robotics [1–4]. It aims to determine a collision-free or distance-efficient path for a robot to reach its target location. These conflicting characteristics are defined as clearance and optimality. Focusing on clearance, the Voronoi diagram is one of the most well-known methods because it guarantees a maximum clearance [4].

A Voronoi diagram is a partition of a plane, and each partition is called a Voronoi polygon and is associated with a unique point [4]. These convex polygons are called Voronoi polygons [5]. In local areas, obstacles are represented by polygons or line segments. The Voronoi diagram, which is generated using points, is inappropriate for these situations. A generalized Voronoi diagram (GVD) is generated using polygons [6]. Because a GVD is generated using polygons, it is suitable in obstacle contained environments. Similar to the Voronoi diagram, in which each Voronoi polygon is associated with a unique point, the Voronoi polygons in the GVD are associated with unique polygons. Because the Voronoi diagram maximizes the distance to the points, the GVD maximizes the distance to the polygons. This feature makes the GVD appropriate for clearance-based path planning in obstacle-contained environments.

Unlike the Voronoi diagram, which has straight line segments, the Voronoi polygons in the GVD consist of parabolic curved segments [7]. This requires many vertices to be represented and renders path planning inefficient. To overcome this inefficiency, utilization is required. Simplifying the line segments requires a diagram because it reduces the number of vertices. However, excessive line simplification may result in a non-original deformity, and the path can intersect with obstacles. This can lead to a path planning failure because the path that intersects with obstacles is unreachable. The Douglas-Peucker line-simplification (DP) algorithm provides the best perceptual representation of the original lines [8]. This approach is suitable for path planning because it results in the smallest changes in terms of the diagram shape.

The A-star (A*) algorithm is the best-first search algorithm and is widely used in path planning. This algorithm guarantees the optimal path in a static environment and improves the efficiency using a heuristic function [9]. In two-dimensional (2D) node-based maps, the A* algorithm uses an evaluation function to identify the next node. The evaluation function can be defined as

where g(n) refers to the actual cost from the start node to the current node, and h(n) refers to the estimated cost from the current node to the goal node, which is also known as a heuristic function [10]. On a grid-based map, the Manhattan and Euclidean distances are widely used to define a heuristic function. However, on a node-based map, the Manhattan distance cannot satisfy the underestimation because the actual distance can be less than the Manhattan distance. Calculating the shortest path between two points, that is, the Euclidean distance, is suitable for node-based maps.

In this study, we constructed a GVD and simplified its diagram using the DP algorithm. The results of the simplified GVD are represented by nodes and their connections. To obtain the shortest path based on the simplified GVD (S-GVD), we used the A* algorithm, whose heuristic function is defined as the Euclidean distance. Because the DP algorithm requires a tolerance value, we simulated multiple situations to determine a moderate value. The S-GVD and GVD were compared to show differences in the clearance and performance. The minimum distance from obstacles was measured to represent the clearance of the diagram. The execution time was measured to represent the performance. To measure the efficiency, their visibility graph were compared.

2.1 Generalized Voronoi Diagram

A GVD can be constructed using multiple methods [1, 6, 7, 11]. However, to preserve the details and remain capable of producing any polygon, we decided to adopt a different perspective. The main idea of our method involves representing polygons using points, which is accomplished by following four steps:

• 1. Triangulate polygons.

• 2. Generate points at regular interval along the line segments in each triangle.

• 3. Create Voronoi diagram with the generated points.

• 4. Delete the nodes that exist inside the polygons.

We triangulated the polygons using Seidel’s algorithm, which triangulates polygons regardless of their concaveness and convexity [12]. We then generate points at regular intervals along the line segments of each triangle. For the polygon vertices shown in Figure 1, Figure 2 presents their conversion results.

By considering only the polygons, the generation of the Voronoi diagram fails. Therefore, a boundary is required [4]. In addition, an independent space is required for each endpoint to ensure clearance at each endpoint. This can be solved by adding endpoints to the Voronoi diagram, which generates a unique Voronoi polygon that ensures that no other polygons intersect the area. After adding all required points, we generated a Voronoi diagram using the Python SciPy library. Figure 3 shows the Voronoi diagram results.

Points in the polygon are unreachable. These points must be removed to generate a passable path. To delete unreachable nodes, determining whether each node is in the polygon is necessary. This was determined by testing the order of the points. The order of three points in the same plane can be expressed as clockwise (CW) or counterclockwise (CCW). The order of points (P₁, P₂, P₃) can be determined using Eqs. (1) and (2) [13].

If a single point P and the vertices of the triangles V₁, V₂, V₃ are given, we can determine whether the point is in the triangle using Eqs. (3) and (4).

Testing only a single vertex can yield unreliable results. Therefore, every vertex in the triangle must be tested.

After specifying the nodes in the polygons, we delete them and reorganize the diagram. Consequently, the GVD can be obtained, as shown in Figure 4.

2.2 Simplifying the GVD

Because the DP algorithm relies only on the distance between points and lines, it uses a polyline and a tolerance ɛ [8]. Moreover, the GVD, which contains many diverging points, must be divided into polygonal chains to execute the DP algorithm. Therefore, we implemented a chaining algorithm based on the neighbor count.

From a neighborhood perspective, nodes can be classified into three types: dead-end, feature, and chained. Because the GVD does not contain independently existing nodes, we did not consider them. A dead-end node is at the dead end of the diagram and has a neighbor count of one. A feature node is a diverging point in the diagram, with a neighbor count greater than 2. Finally, a chained node is in the middle of the chain, and is not a dead-end or feature node, with a neighbor count of 2.

The algorithm begins by specifying the first starting node, which is a dead-end node. Subsequently, a chain is created. After creating the chain, neighbors from the end node are specified as newly discovered starting nodes, and it is pushed into the starting node queue. The entire diagram can be searched by looping the procedure from creating the chain and adding newly discovered starting nodes.

The single-chain generation algorithm is executed according to the number of neighbors. Two scenarios are possible for dead-end nodes: either at the end of the line or at the beginning of the algorithm. The first situation indicates that no newly discovered start nodes remain and that this is the end of the chain. Therefore, the algorithm exits. However, the second scenario should not result in the algorithm exiting, and it should continue searching for the end of the chain. Feature nodes have only one possible scenario at the end of the chain. The algorithm must terminate and notify unvisited neighbors. Finally, chained nodes have two possible scenarios. If the algorithm has visited every neighbor, it is at the end of the line, and the algorithm must exit. Otherwise, if the algorithm has visited only one neighbor, then the chain is incomplete, and the algorithm continues. Algorithms 1 and 2 show how chains were generated in this study.

After generating the chains in the diagram, we can now use the DP algorithm to simplify the polyline. Because the simplified polyline differs according to the index, we reorganized the GVD. Figure 5 show the results of the S-GVD.

Because the start and end nodes are included in the diagram generation, the diagram has its own Voronoi polygon. Therefore, paths containing dead-end nodes are not passed through. This renders such lines unnecessary. Therefore, we implemented a pruning procedure to eliminate such lines. Figure 6 shows the pruning procedure results.

2.3 A-Star Algorithm on S-GVD

To execute the A* algorithm, a connection must be made between the endpoints and adjacent nodes. To achieve this, the node adjacent to the endpoints must be determined. The folloing features were used to determine the corresponding nodes. We assumed that a line is created using one of the endpoints of the diagram and one of the nodes as both ends. If the node is adjacent to the endpoint, it should not intersect all lines in the diagram. Therefore, we can identify adjacent nodes by checking the intersection of line segments. The intersection of two lines (L₁(P₁, P₂), L₂(P₃, P₄)) can be determined using Eq. (5).

Figure 7 shows the connecting of all adjacent nodes to each endpoint.

The algorithm starts at the start node. It then expands to its neighboring nodes. Each neighboring node calculates its evaluation function using the Euclidean distance as a heuristic function. After selecting the closest node, the algorithm repeats from the expansion stage. This loops until the goal node is reached. Algorithm 3 shows this procedure [14].

Figure 8 shows the results of searching the path using the A* algorithm.

2.4 Finding the Moderate Tolerance

Because the DP algorithm executes based on the ɛ value, an appropriate ɛ value must be determined: the maximum value that does not contaminate the path. The minimum distance from the obstacle was measured to ensure that the path retained its original shape. The performance was evaluated by measuring the time spent on the algorithm. This measurement was performed by varying the ɛ values on various maps and paths. Figures 9 and 10 present the distance and performance results, respectively.

We determined that the performance increases with ɛ. However, when ɛ exceeds 0.0008, paths begin to approach obstacles. Furthermore, when ɛ exceeds 0.04, some paths begin to intersect with obstacles. This explains why the distance approaches zero in certain situations. However, most situations showed no significant decrease in the distance from 0.0 to 0.0064. We selected an ɛ value of 0.0064 because of this.

To test the S-GVD in various environments, we tested seven maps of various environments. Table 1 lists the characteristics of each map, and Figure 11 shows images of the maps used for testing.

Based on Maps 1–4, we tested four paths. Paths 1 and 2 were intended to cross diagonally, whereas paths 3 and 4 were intended to cross the center. Because Maps 5–7 were mazelike environments, we tested a single path with the intended endpoints. Using a 2D coordinate system on the map, we defined the lower left corner as (0, 0) and the upper right corner as (1, 1), where the horizontal axis is x, and the vertical axis is the y. Table 2 lists the endpoints of each map. Figures 12–16 present the results of the path search based on Table 2.

3.1 Comparison

Various aspects of the GVD and S-GVD were compared. The minimum distance from the obstacle in the path was measured to determine the extent to which clearance was maintained. The execution time was measured to determine the extent of the performance improvement. Table 3 lists the minimum distances from obstacles measured in the experiment. For Maps 1–4, we averaged the values of all paths.

In the experiment, we observed that the computational time was reduced by simplifying the GVD. Moreover, the time reduction tends to be inversely proportional to the complexity. We determined it to be up to six times faster on low-complexity maps, such as Maps 1 or 5, whereas it was only two times faster on high-complexity maps, such as Map 7. We also noticed that the minimum distance, which represents the clearance, was reduced when simplifying the diagram. In the low-complexity map, this decrease was less than 3%, whereas in the high-complexity map, it was approximately 5%. On a maze-like map, the reduction reached 10%. These results indicate that clearance is affected when the complexity increases.

In terms of distance, the shortest path can be obtained using a visibility graph (V-graph) [15]. Therefore, we compared the total distances of the paths generated on the S-GVD, GVD, and V-graph. Table 4 lists the values measured during the experiments.

As the focus was on clearance, no significant difference was observed between the S-GVD and GVD methods. In addition, it was less than 1%. However, the difference between the V-graph and the other graphs indicated that the GVD-based method was approximately 23% longer. This value appears to be similar to that of Masehian’s previous work, which showed that the Voronoi diagram method was approximately 26% longer than that of the V-graph method [7].

In this study, we proposed the S-GVD method for the clearance-based path planning problem. We successfully created an SGVD and its paths. The path generated by the S-GVD is similar to that generated by the GVD, with fewer points. The comparison shows that the S-GVD has positive affects the runtime efficiency without losing clearance. This is more effective for low-complexity maps but is still useful for high-complexity maps. However, the distance inefficiency of the S-GVD is similar to that of the GVD because the paths are similar. This shows that the distance inefficiency of the S-SVD has not been overcome. Therefore, further studies are required to increase the path efficiency.

Table 1. Map characteristics.

Table 2. Endpoints of each map.

Table 3. Clearance and performance comparisons.

Table 4. Comparison in terms of the total path distance.

Algorithm 1. Generating chains.

Algorithm 2. Generating chain.

Algorithm 3. A* Algorithm.