Expanded Douglas–Peucker Polygonal Approximation and Opposite Angle-Based Exact Cell Decomposition for Path Planning with Curvilinear Obstacles

Abstract

The Expanded Douglas–Peucker (EDP) polygonal approximation algorithm and its application method for the Opposite Angle-Based Exact Cell Decomposition (OAECD) are proposed for the mobile robot path-planning problem with curvilinear obstacles. The performance of the proposed algorithm is compared with the existing Douglas–Peucker (DP) polygonal approximation and vertical cell decomposition algorithm. The experimental results show that the path generated by the OAECD algorithm with EDP approximation appears much more natural and efficient than the path generated by the vertical cell decomposition algorithm with DP approximation.

1. Introduction

The path-planning process of a mobile robot aims at finding a collision-free path to move the robot from the current posture to the goal posture [1,2,3]. If there are multiple available paths, the optimal path in the sense of an objective function, such as the minimum distance, can be chosen. The algorithms for mobile-robot path planning can be grouped into four categories: roadmap approaches, such as the visibility graph or generalized Voronoi graph; cell decomposition approaches, such as the vertical cell decomposition (VCD) or approximate cell decomposition; sampling-based planning methods, such as the rapidly exploring random tree (RRT) or probabilistic roadmap (PRM), and potential field methods [2,3,4,5]. Among these methods, roadmap approaches are generally fast and easy to implement, but an intrinsic way to describe environmental information is not provided [1,2,3]. Sampling-based planning methods are more practical, but they do not provide completeness so we cannot recognize the non-existence of a path [2,3]. Potential field methods are useful to control the robot by generating a differentiable smooth path, but they cannot give explicit information on the roadmap and easily fall into a local minimum [1,2,3]. There are also some hybrid approaches, such as a potential field with RRT [6] or potential field with cell decomposition [7].

Cell decomposition, which is a classical and representative method for mobile-robot path planning, decomposes the given environment into several cells and finds a collision-free path based on the connectivity graph of these cells [2,3,4,5,6,7,8,9,10]. Here, each node of a connectivity graph is made by the representative point of each cell or its border line. Each link of the connectivity graph between the nodes indicates that the corresponding cell is adjacent to each other [11]. In various cell decomposition algorithms [12,13,14,15,16,17], one of the most widely known algorithms is vertical cell decomposition (VCD), but it does not generate an efficient path because it uses too many cells [8]. Figure 1 shows an example of the previous exact cell decomposition using VCD. VCD makes vertical lines from the convex vertices to decompose the environment into cells. The adjacency relationship among the cells is represented by the connectivity graph and used to find a path using graph search algorithms. VCD does not guarantee the optimality of the number of decomposed cells since there is no consideration of the shape of the obstacle. Reducing the number of decomposed cells directly increases the efficiency in path planning, but finding the optimal decomposition case is known as an NP-hard problem [1,2,3].

To supplement this drawback, the Opposite Angle-based Exact Cell Decomposition (OAECD) [18] was proposed by using a type of greedy approach to minimize the number of cells and increase efficiency. However, the OAECD can only be applied for polygonal obstacles, since it is operated based on the relationship among the vertices of the obstacles. In other words, path planning in an environment with curvilinear obstacles is impossible by itself. Therefore, in this paper, a novel expanded polygonal approximation method based on Douglas–Peucker (DP) algorithm is proposed to apply OAECD path planning to the cases with curvilinear obstacles.

In Chapter 2, a novel polygonal approximation algorithm for curvilinear obstacles is addressed. Then, the algorithm is applied to a modified OAECD algorithm in Chapter 3. The experimental results are shown in Chapter 4, and the paper is concluded in Chapter 5.

2. Polygonal Approximation Algorithm of Curvilinear Obstacle

In this chapter, the Douglas–Peucker (DP) algorithm [19], which is one of the most popular algorithms for polygonal approximation, is reviewed. An Expanded Douglas–Peucker (EDP) algorithm for the application with curvilinear obstacles is proposed with mathematical validation on the circumscription of the EDP Algorithm.

2.1. Douglas-Peucker Algorithm

The DP algorithm is a representative method of polygonal approximation. The purpose of a DP algorithm is to find a similar piecewise linear curve with fewer points given a closed curve. The algorithm uses the concept of dissimilarity based on the maximum distance between the original curve points and their simplified piecewise linear curve [17,18].

The algorithm (Algorithm 1) measures the distance between each point of a curve and the base line, which is the line segment with the same first and last points with the curve, to find the farthest point from the line segment with the maximum perpendicular distance.

Here, C is the set of obstacle contours, which is the set of point lists of the obstacle; ε is the threshold value for the maximum dissimilarity tolerance; R is the final result of the polygonal approximation of all obstacles; c is a point list of the obstacle contour, which is arranged in counter-clockwise order; pl is a point list; r₁ and r₂ indicate each result of the recursiveDP procedure; r indicates the final result of the polygonal approximation of an obstacle by DP algorithm.

Algorithm 1. Pseudo Code of the Initial DP.
Input: C ← Set of point lists of the obstacle ε ← Threshold value for maximum dissimilarity tolerance Output: R ← Final result of polygonal approximation of all obstacles represented as a set of point lists
Begin DP Procedure
1	for each c in C do
2	find two points in c, p1 and p2, which have the maximum distance from each other and p1 is in front of p2
3	r1 ← recursiveDP(pl[p1 … p2], ε) // pl: point list of a segment of obstacle contour
4	r2 ← recursiveDP(pl[p2 … starting point of c … p1], ε)
5	r ← point list[r1[0]… r1[end1 − 1] r2[0]… r2[end2 − 1]] // endi: number of points in ri
6	insert r to R
7	end for
End DP Procedure

In the recursive procedure of DP algorithm (Algorithm 2), the line segment is further divided into two sub-line segments using the farthest point as the via-point whenever the maximum perpendicular distance is greater than or equal to the threshold value for maximum dissimilarity tolerance, ε. This process is recursively repeated until the maximum perpendicular distance is less than ε.

Here, r₁ and r₂ are each the result of the recursiveDP procedure, and r is the result of the polygonal approximation of the given curve.

Algorithm 2. Pseudo Code of the Recursive DP.
Input: pl ← Point list of the given curve ε ← Threshold value for maximum dissimilarity tolerance Output: r ← Result of the polygonal approximation of the given curve represented as a point list Initialization: linebase ← line segment connected from pl[0] to pl[end] // end: number of points in pl distmax ← −1 imax ← −1
Begin recursiveDP Procedure
1	for each point p in pl[1…end−1] do
2	dist ← perpendicular distance between linebase and p
3	if dist > distmax
4	distmax ← dist
5	imax ← index of p
6	end if
7	end for
8	if distmax >= ε then
9	r1 ← recursiveDP(pl[0…imax], ε) // pl: point list of a segment of the given curve
10	r2 ← recursiveDP(pl[imax…end], ε)
11	r ← point list[r1[0]… r1[end1 − 1] r2[0]… r2[end2]] // endi: # of points in ri
12	else
13	insert pl[0] to r
14	insert pl[end] to r
15	end if
End recursiveDP Procedure

Figure 2 shows the process of the DP algorithm. l_b is the base line, which is identical to line_base in Algorithm 2. l_b1 is determined with the starting point P₁ and ending point P₂, which makes the widest width of the given obstacle. Then, we check whether dist_max is less than ε. If dist_max is less than ε, two vertices of l_b1 are inserted into the point list of the polygonal approximation. If dist_max is greater than or equal to ε, a new base line l_b2 with P₁ and P₃ is made, new dist_max is found again based on l_b2, and the above procedures are repeated.

The obstacle approximation result by DP algorithm does not guarantee the circumscription of the original obstacle. In other words, some interior points of the obstacle region may not be included inside the polygon by the DP algorithm. Similarly, some exterior points of the obstacle region may be included inside the polygon by the DP algorithm.

Thus, if the result of the DP algorithm on a curvilinear obstacle is directly used for path planning, the generated path may penetrate inside the real obstacle region, and the robot may easily collide with the obstacle. To overcome this problem, a modified DP algorithm is proposed in this paper.

2.2. Proposed Expanded Douglas-Peucker (EDP) Algorithm

The path planning for curvilinear obstacles using DP algorithm may not be collision-free. The basic philosophy of the EDP algorithm is to guarantee the circumscription of obstacles by expanding the polygon of the DP algorithm with the maximum dissimilarity tolerance. In addition, by appending additional points near the convex corner, the convex corner clearance is considered, where the robot control may become more difficult during path following.

Figure 3 shows the operation of EDP based on the counter-clockwise traversal. The first step is to perform the DP algorithm. If the half angle between line segments l₀ and l₁ is 0–90°, i.e., the corner of DP polygon is convex, the perpendicular half-lined to l₀ and l₁ are v₀ and v₁ at the corner point, respectively. Then, the points on the arc, with the center point as the convex corner and the radius of ε, are appended starting from v₀ and rotating with angle θ_rot until they meet v₁ in the counter-clockwise direction. These points are added for the convex corner clearance. If the half angle between line segments l₀ and l₁ is 90° or more, i.e., the corner of DP polygon is concave, the point far from the cross point of l₀ and l₁ with distance ε to the outer direction of the obstacle is appended. The above procedures are repeated for the remaining corner points of the DP polygon.

Algorithm 3 shows the abstract version of the pseudo code of the EDP algorithm.

Algorithm 3. Pseudo Code of EDP (Abstract version).
Input: RDP ← Result of DP polygonal approximation of all obstacles represented as a set of point lists ε ← Threshold value for maximum dissimilarity tolerance θrot ← Constant angle for obstacle corner clearance Output: R ← Final result of the EDP polygonal approximation represented as a set of point lists
Begin Expanded-DP Procedure
1	for each rDP in RDP do
2	R ← null
3	for each point p in rDP do
4	if p is convex vertex then
5	θ ← half inner angle of p
6	dist ← ε
7	l0 ← line segment connected from the previous point of p to p
8	l1 ← line segment connected from p to the next point of p
9	v0 ← perpendicular half-line to l1 started from p
10	v1 ← perpendicular half-line to l2 started from p
11	loop
12	insert points pcv on the arc with center point p and radius ε, which is consisted of the points according to θrot angle from v0 to v1, to R
13	end loop
14	else
15	θ ← half outer angle of p
16	dist ← ε/sinθ
17	insert point pcc far from p with distance dist to the outer direction of the obstacle to R
18	end if
19	end for
20	end for
End Expanded-DP Procedure

Here, R_DP is the set of point lists of the polygonal approximation of the obstacles by the DP algorithm; ε is the threshold value for maximum dissimilarity tolerance; θ_rot is a constant angle for obstacle corner clearance; R is the final result of the polygonal approximation of all obstacles by the EDP algorithm, and r_DP is a point list of the obstacle polygonal approximation by the DP algorithm, which is arranged in counter-clockwise order.

Figure 4 illustrates the detailed version of the EDP algorithm (Algorithm 4).

Since $\overrightarrow{P_{n-1}{P}_n}=\left(x_n-x_{n-1},y_n-y_{n-1}\right)$ and $\overrightarrow{P_{n-1}{P}_n}\perp \overrightarrow{P_n{Q}_0}$,

unit vector of

$$\overrightarrow{P_n{Q}_0}=\frac{1}{\sqrt{{\left(y_n-y_{n-1}\right)}^2+{\left(x_n-x_{n-1}\right)}^2 }}{\left(y_n-y_{n-1}, -\left(x_n-x_{n-1}\right)\right)}^T$$

(1)

Therefore,

$$Q_0=\frac{\epsilon }{\sqrt{{\left(y_n-y_{n-1}\right)}^2+{\left(x_n-x_{n-1}\right)}^2 }}{\left(y_n-y_{n-1}, -\left(x_n-x_{n-1}\right)\right)}^T$$

(2)

In addition, since $Q_i$ (i = 1, 2, …, m − 1) are on the arc with center point P_n and radius ε, rotating $Q_i$ with angle ${\theta }_{rot}$ in the counter-clockwise direction yields

$$Q_i=\left(\begin{array}{cc}\cos {\theta }_{rot}& -\sin {\theta }_{rot}\\ \sin {\theta }_{rot}& \cos {\theta }_{rot}\end{array}\right)\left(Q_{i-1}-P_n\right)+P_n$$

(3)

Similarly, in the case of a concave corner,

$$\overrightarrow{O{P}_n}+\overrightarrow{P_n{Q}_s}={\left(x_n,y_n\right)}^T+\left(\begin{array}{cc}\cos \left(\pi -\theta \right)& -\sin \left(\pi -\theta \right)\\ \sin \left(\pi -\theta \right)& \cos \left(\pi -\theta \right)\end{array}\right){\left(x_{n-1}-x_n,y_{n-1}-y_n\right)}^T$$

(4)

Around the convex vertex of DP polygon, the concept of θ_rot is used for the convex corner clearance. When θ_rot ≥ $\angle Q_0{P}_n{Q}_m$, there is no additionally appending vertex, and Q_m = Q₁; when θ_rot < $\angle Q_0{P}_n{Q}_m$, there are additionally appending vertices Q₁, Q₂, …, which makes the effect of securing additional free space near the obstacle corner relatively difficult to path following.

Algorithm 4 shows the detailed version of the pseudo code of the EDP algorithm.

Algorithm 4. Pseudo Code of EDP (Detailed version).
Input: RDP ← Result of DP polygonal approximation of all obstacles represented as a set of point lists ε ← Threshold value for maximum dissimilarity tolerance θrot ← Constant angle for obstacle corner clearance Output: R ← Final result of the EDP polygonal approximation represented as a set of point lists
Begin Expanded-DP Procedure
1	for each rDP in RDP do
2	for each point Pn(xn, yn) in point list rDP do
3	if ∠Pn+1PnPn+1 < π then
4	θ ← $\frac{1}{2}$∠Pn+1PnPn+1
5	dist ← ε
6	$Q_0$ ← ${\left(x_n,y_n\right)}^T+\frac{\epsilon }{\sqrt{{\left(y_n-y_{n-1}\right)}^2+{\left(x_n-x_{n-1}\right)}^2 }}{\left(y_n-y_{n-1}, -\left(x_n-x_{n-1}\right)\right)}^T$
7	$Q_m$ ← ${\left(x_{n+1},y_{n+1}\right)}^T+\frac{\epsilon }{\sqrt{{\left(y_{n+1}-y_n\right)}^2+{\left(x_{n+1}-x_n\right)}^2 }}{\left(y_{n+1}-y_n, -\left(x_{n+1}-x_n\right)\right)}^T$
8	loop until i $\le \frac{\pi -2\theta }{{\theta }_{rot}}$
9	$Q_i$ ← $\left(\begin{array}{cc}\cos {\theta }_{rot}& -\sin {\theta }_{rot}\\ \sin {\theta }_{rot}& \cos {\theta }_{rot}\end{array}\right)\left(Q_{i-1}-P_n\right)+P_n$
10	insert$Q_i$ to R
11	i ← i + 1
12	end loop
13	else
14	θ ← $\frac{1}{2}$∠Pn+1PnPn+1
15	dist ← ε/sinθ
16	$Q_s\leftarrow \overrightarrow{O{P}_n}+\overrightarrow{P_n{Q}_s}={\left(x_n,y_n\right)}^T+\left(\begin{array}{cc}-\cos \left(\theta \right)& -\sin \left(\theta \right)\\ \sin \left(\theta \right)& -\cos \left(\theta \right)\end{array}\right){\left(x_{n-1}-x_n,y_{n-1}-y_n\right)}^T$
18	insert $Q_s$ to R
19	end if
20	end for
21	end for
End Expanded-DP Procedure

2.3. Mathematical Validation on the Circumscription of the EDP Algorithm

[Theorem] The polygon that consists of the resulting points from the expanded DP (EDP) algorithm on an obstacle includes all points of the original obstacle, i.e., no point of the obstacle region is outside of the polygon that consists of the resulting points from EDP on that obstacle.

(Proof) Let P_n be the n-th point from the DP polygonal approximation of an obstacle. Then, the following propositions are always true by the DP algorithm.

[P1] P_n−1, P_n, P_n+1 are points included in the boundary line of the obstacle.

[P2] P_n is the farthest point from the line segment $\overline{P_{n-1}{P}_{n+1}}$ among the boundary points of the obstacle in [P_n−1, P_n+1].

[P3] Every boundary point of the obstacle in [P_n−1, P_n] has a shorter distance than ε from the line segment $\overline{P_{n-1}{P}_n}$.

[P4] Every boundary point of the obstacle in [P_n, P_n+1] has a shorter distance than ε from the line segment $\overline{P_n{P}_{n+1}}$

If P_n is a convex point.

Let us assume that there is a boundary point c ∈ [P_n−1, P_n+1] of the obstacle such that c is located outside the polygon Q_m, Q’₀, Q’₁, …, Q’_m, Q’’₀ such as Figure 5a, which consists of the resulting points from the EDP algorithm on the obstacle. Since P_n−1, P_n, and P_n+1 are points on the boundary line of the obstacle by proposition [P1], boundary point c should be identical to P_n or included in the range of [P_n−1, P_n] or (P_n, P_n+1).

If point c is identical to P_n, it is trivial that c cannot be located outside of the polygon with vertices Q_m, Q’₀, Q’₁, …, Q’_m, and Q’’₀, since P_n is inside the polygon.

If point c is included in the range of [P_n−1, P_n), the distance from point c to the line segment $\overline{P_{n-1}{P}_n}$ should be less than ε by proposition [P3]. Therefore, c cannot be located outside of the polygon with vertices Q_m ~ Q’₀.

If point c is included in the range of (P_n, P_n+1], the distance from point c to the line segment $\overline{P_n{P}_{n+1}}$ should be less than ε by proposition [P4]. Therefore, c cannot be located outside of the polygon with vertices Q’_m ~ Q’’₀.

Therefore, no boundary point of the obstacle region is outside of the polygon with vertices Q_m, Q’₀, Q’₁, …, Q’_m, and Q’’₀ in the case of convex P_n.

If P_n is a concave point,

Let us assume that there is a boundary point c ∈ [P_n−1, P_n+1] of the obstacle such that c is located outside of the polygon Q_m, Q’_s, Q’’₀ such as Figure 5b, which consists of the resulting points from the EDP algorithm on the obstacle. Since P_n−1, P_n, and P_n+1 are points on the boundary line of the obstacle by proposition [P1], boundary point c should be identical to P_n or included in the range of [P_n−1, P_n] or (P_n, P_n+1).

If point c is identical to P_n, it is trivial that c cannot be located outside of the polygon with vertices Q_m, Q’_s, and Q’’₀, since P_n is inside the polygon.

If point c is included in the range of [P_n−1, P_n), the distance from point c to the line segment $\overline{P_{n-1}{P}_n}$ should be less than ε by proposition [P3]. Therefore, c cannot be located outside of the polygon with vertices Q_m and Q’_s.

If point c is included in the range of (P_n, P_n+1], the distance from point c to the line segment $\overline{P_n{P}_{n+1}}$ should be less than ε by proposition [P4]. Therefore, c cannot be located outside of the polygon with vertices Q’_s and Q’’₀.

Therefore, no boundary point of the obstacle region is outside the polygon with vertices Q_m, Q’_s, and Q’’₀ in the case of concave P_n (Q.E.D.).

Once the polygonal approximation with the EDP algorithm is completed, it is possible to solve the obstacle collision problem that may occur when DP algorithm is used for the polygonal approximation of a curvilinear obstacle. Since the polygon created by the EDP algorithm can guarantee the circumscription of obstacles, this result of EDP can be used to apply OAECD in path planning with curvilinear obstacles.

3. Modified Opposite Angle-Based Exact Cell Decomposition (OAECD) Algorithm for Path Planning with Curvilinear Obstacles

The basic concept of the modified OAECD algorithm is to reduce as possible as many cells after the execution of the EDP algorithm and increase the calculation efficiency. Using the concept of inclusion of an opposite angle, OAECD first tries to connect the closest neighboring cell in the opposite angle region. OAECD does not randomly or sequentially process the points but processes in the order from a close pair to a far pair through three consecutive steps, which are similar to the human method. In addition, OAECD does not try to make an additional decomposition if the shape of the generating cell is convex.

The detailed algorithm for the modified OAECD consists of three steps [18]. Figure 6 shows how the decomposing lines are formed between the obstacles for each step of the modified OAECD algorithm. In the first step, the modified OAECD finds the closest neighboring vertex in the set of all vertices of other obstacles for every convex vertex (CV) of each obstacle. For every CV of each obstacle and its closest neighboring vertex (NV) in other obstacles, a new decomposing line is drawn if there is no existing decomposing line with the current CV, its closest NV is inside the region of the opposite angle of the current CV, and no intersection is made with other obstacles or other decomposing lines.

In the second step, for every CV among the remaining vertices and a vertex (AV) in another obstacle inside the region of the opposite angle of the current CV, a new decomposing line is drawn if there is no decomposing line with the current CV, the AV in another obstacle is the shortest one from the current CV among all available AVs, and there is no intersection with other obstacles or other decomposing lines.

Finally, in the third step, for every CV of the remaining vertices, a new decomposing line is drawn in the direction of the equiangular line of the opposite angle of the current CV until it intersects with the boundary of the environment, obstacle, or another decomposing line, if no decomposing line is connected with the current CV or more than one decomposing line is already connected from another CV, and the created angle near the current CV is larger than 180°.

The OAECD can be properly applied in a static environment. Although a single-sensed map may generate noise, it can sense multiple times for the same environment in a short period and remove the noise on the map by the moving average method [20] or the median method [21]. Based on these methods, one can plan the route. However, this process is only accurate in the static environment. In the dynamic environment, it is difficult to resolve the sensor noise completely by the moving average method or the median method for the same position because the obstacle moves.

Algorithms 5–7 show the pseudo code of the modified OAECD algorithm for each step in the process. Here, v_c1 is a convex vertex of an obstacle; V_c is the set of point lists, which is the result of the EDP polygonal approximation of all obstacles; v_a1 is the closest neighboring vertex from v_c1; V is the set of all vertices of the obstacles; V_check is the point set to check for processing.

Algorithm 5. Pseudo Code of the modified OAECD (Step 1).
Input: Vc ← R // R: Result of the EDP polygonal approximation of all obstacles represented as a set of point lists M ← Environment map Output: Vchec ← Point set to check for processing M ← Environment map with decomposing lines of step 1
Begin OAECD-Algorithm Procedure
1	for every convex vertex of each obstacle in Vc do
2	find the closest vertex in the set of all vertices of other obstacles by comparing the distances between the current vertex and other vertices
3	end for
4	for each vc1 in Vc do
5	if there is no decomposing line that is already connected with vc1 then
6	if va1 is included in the region of the opposite angle of vc1 and line(vc1, va1 in V) is not intersected with other obstacles or other lines then
7	draw decomposing line from vc1 to va1 and insert vc1 to Vcheck
8	else if
9	else if all angles near vc1 are less than or equal to 180° then
10	insert vc1 to Vcheck
11	end if
12	end for
End OAECD-Algorithm Procedure

Generally, the cells created by the cell decomposition methods are shaped as a convex polygon to avoid being penetrated by obstacles. Therefore, only the convex vertices of the obstacles are considered in this step because the concave vertices of the obstacles obviously result in convex vertices of the free cell. In other words, there is no need to make an additional decomposing line from some vertices if they preserve the concaveness. In addition, the closest neighboring vertex is chosen to reduce the number of possible cells and the possibility of crossing with other decomposing lines. Here, v_c2 is a convex vertex of an obstacle in V_c-V_check, v_a2 is a vertex in the region of the opposite angle of v_c2, and V_i is the set of all vertices inside the region of the opposite angle of v_c2.

Algorithm 6. Pseudo Code of the modified OAECD (Step 2).
Input: Vc ← R//R: Result of the EDP polygonal approximation of all obstacles represented as a set of point lists M ← Environment map Vcheck ← Point set to check for processing (Result of previous step 1) Output: Vcheck ← Point set to check for processing (Result of this step) M ← Environment map with the decomposing lines of step 1 and 2
Begin OAECD-Algorithm Procedure
1	for each vc2 in Vc - Vcheck do
2	if there is no decomposing line that is already connected with vc2 then
3	if va2 has the shortest distance with vc2 compared with those in Vi - {va2} and line(vc2, va2 in Vi) is not intersected with the obstacle and other lines then
4	draw decomposing line from vc2 to va2 and insert vc2 to Vcheck
5	end if
6	else if all angles near vc2 are less than or equal to 180° then
7	insert vc2 to Vcheck
8	end if
9	end for
End OAECD-Algorithm Procedure

From Step 2, the decomposing line from v_c2 to v_a2 is drawn, and v_c2 is inserted into V_check although v_a2 is not the closest vertex in V. Here, v_c3 is an unchecked convex vertex of each obstacle.

Algorithm 7. Pseudo Code of the modified OAECD (Step 3).
Input: Vc ← R//R: Result of the EDP polygonal approximation of all obstacles represented as a set of point lists M ← Environment map Vcheck ← Point set to check for processing (Result of previous step 2) Output: M ← The final environment map with decomposing lines of steps 1, 2, and 3
Begin OAECD-Algorithm Procedure
1	for each vc3 in Vc - Vcheck do
2	if there is no decomposing line that is already connected with vc3 then
3	draw decomposing line from vc3 in the direction of half angle of the opposite angle of vc3 until it intersects with the boundary of the environment, other obstacles, or other lines and insert vc3 to Vcheck
4	else if all angles near vc3 are less than or equal to 180° then
5	insert vc3 to Vcheck
6	end if
7	end for
End OAECD-Algorithm Procedure

The time complexity of the modified OAECD is O(n²) because the sub-time complexity is basically all O(n²) for Step 1, Step 2, and Step 3. In addition, the time complexity for Step 3 can be reduced to O(nlogn) approximately when the sweep-line method [22,23] is applied.

4. Experimental Results

Two types of experiments were conducted to find the performance of the proposed EDP and modified OAECD algorithm. An additional simulation has been performed to verify the feasibility of the modified OAECD algorithm for a map with curvilinear obstacles. The first experiment is conducted to compare the approximation error and the number of vertices of the approximated polygon made by EDP and DP. In each experiment, twenty maps were chosen in the pre-created one hundred fifty random maps, each of which is assumed to be 20 × 20 m² in size and randomly have the position of the obstacle, position of the vertices of each obstacle, and area of the obstacle by using the random function in the math library of the MS Visual C++ compiler. The number of obstacles and vertices of each obstacle were fixed at fifteen. Bezier curve was used for the curvilinear obstacle representation by interconnecting the vertices of each obstacle and creating naturally curved obstacles. Each map was created by an image in bitmap format.

The second experiment was conducted to compare the performance of the OAECD algorithm and the VCD algorithm. Similar to the first experiment, the size of the map was assumed as 20 × 20 m², and the position of the obstacle, positions of the vertices of each obstacle, number of vertices of each obstacle, and number of obstacles in the map were random variables.

Table 1. Performance comparison between Expanded Douglas–Peucker (EDP) algorithm and Douglas–Peucker (DP) alogrithm for various ε values (The number of obstacles and vertices of each obstacle were fixed as 15, and θ_rot for EDP was fixed as 30°).

ε (m)	EDP (%)			DP (%)
	IA	OA	SA	IA	OA	SA
0.05	19.05	0.00	19.05	2.45	0.70	3.15
0.08	28.46	0.00	28.46	4.89	1.17	6.06
0.11	37.95	0.00	37.95	7.19	1.54	8.73
0.14	47.63	0.00	47.63	9.26	1.83	11.08
0.17	57.34	0.00	57.34	11.50	2.08	13.58
0.20	67.17	0.00	67.17	13.38	2.48	15.86
0.23	77.11	0.00	77.11	15.52	2.76	18.28
0.26	87.01	0.00	87.01	17.23	3.20	20.43
0.29	96.91	0.00	96.91	19.55	3.56	23.10
0.32	106.7	0.00	106.7	22.00	3.86	25.85
0.35	116.7	0.00	116.7	23.90	4.40	28.30
0.38	127.3	0.00	127.3	26.91	4.83	31.74
0.41	137.9	0.00	137.9	27.99	5.27	33.26
0.44	148.0	0.00	148.0	30.57	5.62	36.19
0.47	158.8	0.00	158.8	32.13	5.86	37.99
0.50	169.5	0.00	169.5	33.11	6.60	39.72
AVG	92.72	0.00	92.72	15.53	2.99	18.52

shows the experimental results by averaging the results of each experiment. Here, IA is the percentage area of the inner space of the approximated polygons outside the obstacle regions in comparison with the area of the original obstacle region. OA is the percentage area of the outer space of the approximated polygons inside the obstacle regions in comparison with the area of the original obstacle region. SA is the sum of IA and OA. AVG is the average values for various ε.

From Table 1, the average approximation error of the result of the EDP algorithm is approximately 5 times larger than that of DP algorithm to cover the entire area of the original obstacle regions.

Table 2. Average number of vertices created by EDP and DP (The numbers of obstacles and vertices of each obstacle were fixed as 15, and θ_rot for EDP was fixed as 30°).

ε (m)	Average Number of Vertices
	EDP	DP
0.05	31.08	15.92
0.08	27.87	11.92
0.11	25.89	10.19
0.14	24.68	9.18
0.17	23.67	8.33
0.20	22.85	7.66
0.23	22.13	7.32
0.26	21.55	6.83
0.29	20.97	6.56
0.32	20.15	6.20
0.35	19.32	5.91
0.38	18.97	5.58
0.41	18.63	5.40
0.44	18.06	5.06
0.47	17.65	5.00
0.50	17.16	4.78
AVG	21.91	7.65

shows the experimental results by averaging the results of ten experiments with 15 random obstacles and 15 random vertices for each obstacle.

From Table 2, on average, the result of the EDP algorithm has 2.88 times more vertices than the result of the DP algorithm when θ_rot for EDP is 30°.

Figure 7 shows a graphical representation of Table 1 and Table 2. The approximation performance of EDP is worse than DP in the aspects of IA, SA, and average number of vertices. Nonetheless, OA of EDP is completely zero and better than DP since the result of the EDP can cover the entire area of the original obstacle regions.

Table 3. Performance comparison between modified Opposite Angle-Based Exact Cell Decomposition (OAECD) and Vertical Cell Decomposition (VCD) (The numbers of obstacles and vertices of each obstacle were fixed as 15).

(NO, NV)	OAECD			VCD
	NV (ea)	VV (ea)	PL (m)	NV (ea)	VV (ea)	PL (m)
(1,10)	7.60	4.30	28.43	12.00	7.00	29.27
(3,10)	19.80	6.00	29.16	36.60	16.50	33.43
(5,10)	31.70	10.20	29.85	61.80	24.70	37.84
(7,10)	44.10	10.60	30.37	88.20	29.90	45.89
(9,10)	56.80	11.90	29.68	111.80	34.60	47.90
(11,10)	68.50	13.40	30.88	139.00	36.80	53.64
(13,10)	79.20	14.90	30.62	164.70	43.80	56.38
(15,10)	92.50	17.60	30.92	192.00	45.70	48.31
(15,3)	40.70	9.80	28.88	76.60	28.90	57.03
(15,5)	54.90	11.10	29.72	108.00	29.80	51.94
(15,7)	69.20	13.80	29.83	141.20	37.70	59.94
(15,9)	84.70	15.70	30.48	174.60	43.50	54.79
(15,11)	100.60	17.60	30.82	207.80	43.00	53.86
(15,13)	116.10	21.40	31.26	249.50	46.90	58.88
(15,15)	130.60	20.30	31.32	279.20	43.30	55.28
AVG	66.47	13.24	30.15	136.20	34.14	49.63

compares the performance of the modified OAECD algorithm and VCD algorithm. Here, NV is the total number of vertices in the connectivity graph, VV is the number of vertices that composes the generated path by the A* algorithm, and PL is the path length.

From Table 3, the path length by the modified OAECD algorithm is 60.7% shorter than the path length by VCD algorithm on average.

Figure 8 shows the comparison of VCD with DP and OAECD with EDP to show the feasibility of the modified OAECD algorithm for maps with static curvilinear obstacles.

The EDP shows that the polygonal approximation completely covers each obstacle. In addition, the OAECD shows a more natural-looking and efficient path than VCD in Figure 8a. The path from VCD with the DP algorithm may also easily collide with the obstacle, such as Figure 8b.

Even though the path in Figure 8a is more natural looking than that in Figure 8b, there are still some sharp corners which may occur generating an additional problem of motion control for real-world robots due to kinematic constraints. These corners can be smoothed by some additional path smoothing techniques [5,24].

5. Conclusions

In this paper, the Expanded Douglas–Peucker (EDP) polygonal approximation algorithm and its application method for the Opposite Angle-based Exact Cell Decomposition (OAECD) are proposed for the mobile-robot path-planning problem with curvilinear obstacles. In addition, mathematical analysis has been conducted to guarantee the circumscription of obstacle regions by the EDP approximation. Since OAECD is basically focused on the static environment, OAECD is not robust enough to sensor noises in the dynamic environment. Nonetheless, the proposed method is useful with both polygonal and curvilinear obstacles, since the EDP approximation can guarantee the circumscription of obstacle regions, and the modified OAECD algorithm can effectively reduce the number of decomposing cells.

The experimental results show that the path generated by the OAECD algorithm with the EDP approximation looks much more natural and is collision-free. That path is also more efficient than the path generated by the VCD algorithm with DP approximation, although on average, the EDP approximation may induce a larger approximation error and more approximation vertices than DP approximation.