# Path Planning with Obstacle Avoidance Based on NormalizedR-Functions

Authors: Songqiao Tao; Juan Tan
Journal: Journal of Robotics
 (2018)

---

## Abstract

Existing methods for path planning with obstacle avoidance need to check having the interference between a moving part and an obstacle at iteration and even to calculate their shortest distance in the case of given motion parameters. Besides, the tasks like collision-checking and minimum-distance calculating themselves are complicated and time-consuming. Rigorous mathematical analysis might be a practical way for dealing with the above-mentioned problems. AnR-function is a real-valued function whose properties are fully determined by corresponding attributes of their parameters, which is usually applied to express a geometrical object. Thus, a signed distance function based onR-functions is created to represent whether two objects intervene and their level of intervention or separation. As the signed function is continuous and differentiable, the gradient information of the objective function guides a moving part to avoid its obstacles and to approach its target position rapidly. Therefore, a path planning approach with obstacle avoidance based on normalizedR-functions is proposed in this paper. A discrete convex hull approach is adopted to solve the problem thatR-function is inappropriate to represent a geometric object with some curves or surfaces, and pendent points and edges are generated in Boolean operations. Besides, a normalized approach ensures accuracy calculation of signed distance function. Experimental results have shown that the presented approach is a feasible way for path planning with obstacle avoidance.


---

## Body

## 1. Introduction

In recent years, technologies of path planning with obstacle avoidance have received extensive attention in the fields of robotics, computer simulation, and game animation. In the product design process, path planning with obstacle avoidance is an essential element of the simulations of product assemblies and disassemblies. Path planning with obstacle avoidance is in essence an optimization problem, which usually introduces the evaluation criteria (such as the shortest path or the shortest planning time) to plan an optimal path with obstacle avoidance from a given initial position to the destination in high-interference environments [1].To avoid obstacles, existing approaches for path planning are necessary to frequently detect whether two objects intervene or to estimate the shortest path between a moving part and an obstacle at the given location. Therefore, there is not a unified form for planning path with obstacle avoidance. Moreover, collision-checking and minimum-distance estimating themselves are complex and time-consuming tasks. To deal with the above-mentioned problems, rigorous mathematical analysis might be a practical way for path planning with obstacle avoidance.The attributes of anR-function are fully determined by corresponding attributes of their argument. Thus, the sign of a real function is fully determined by the sign of its argument.R-function is usually applied to represent a geometric object [2]. Ifg is anR-function that expresses a geometric object, we can use a signed distance functiong(x)≤0 to describe interference constraints between this geometric object and a space point x. Thus,g(x) <0,g(x) =0, org(x)>0, respectively, represents that space point x is the internal, the boundary, or the external of the geometric object.Based on the above-mentioned analysis, a path planning method with obstacle avoidance based on normalized R-functions is presented in this paper. Firstly, Boolean operations based onR-functions are introduced to generate an implicit function for expressing a geometric object. Secondly, a discrete convex hull method is adopted to solve problems that R-function is inappropriate to represent a geometric object with some curves or surfaces, and there are some pendent points and edges in Boolean operations. Then, a normalized method is introduced to transform the implicit function into them-th order normalization function so that the calculation of signed distance function is accurate. Finally, planning paths with obstacle avoidance for a single-point and a polygonal region are conducted to validate the presented approach. Experimental results have shown that the proposed method is a feasible way for path planning with obstacle avoidance.The rest of this paper is organized as follows. First, related works are introduced in Section2. Then, the theory of R-function is presented in detail in Section 3. In Section 4, a discrete-convex hull method for generatingCSG models of geometric objects is introduced. Section 5 adopts the normalization method to transformg into them-th order normalization function. And path planning with obstacle avoidance based on the normalization function is given in Section 6. Following this section, experimental results applying the proposed method are presented in Section 7. Finally, the paper ends up with some conclusions in Section 8.


## 2. Related Works

Path planning with obstacle avoidance has been extensively applied for the robot navigation. For a robot, path planning carries out a series of translational motions and rotational motions from an initial position to the target position while obstacles are avoided in its working environment [3]. Most of path planning methods with obstacle avoidance can be classified into three categories: potential field method (PFM), sampling-based method, and heuristic-based algorithm.Artificial PFM appeared earlier in [4], which is simple and highly efficient. However, disadvantages like local minima, nonsmooth movement, and oscillations also appear in artificial PFM. To escape from the location of the local minima, Kim [5] presented a new artificial potential function for path planning. Lee et al. [6] proposed new potential function with random force algorithm using PFM for solving the risks of a robot-obstacle collision and local minima trap. To overcome artificial PFM with slow progress and system instability in the presence of obstacles and narrow passages, a modified Newton’s approach was applied to potential field [7]. Sfei et al. [8] proposed a new formula of repelling potential for reducing oscillations and avoiding collisions when the target approaches obstacles. To solve problems where a robot only follows the destination while obstacles are rejected in conventional artificial PFMs, Cosio et al. [9] proposed a path planning method with obstacle avoidance based on improved artificial PFM and genetic algorithm. Yin et al. [10] and Zhang et al. [11] adopted modified PFMs to solve path planning problem in dynamic environments.The advantage of sampling-based path planning methods (SPPMs) has abilities to deal with planning problems in complex and/or time critical real world. At present, most influential SPPMs are probabilistic road-maps (PRMs) and rapidly exploring random trees (RRTs) [12]. Although PRMs and RRTs both randomly sample connecting points from their state space, their graphs connecting points are generated in different ways [13]. More work related to SPPMs can be found in [14]. PRMs have better performance for path planning in high-dimensional state space. As curves or straight lines are used for constructing PRMs, a robot may go anywhere in its free space. Visibility graph [15–17] and Voronoi diagram [18–20] are two typical road-map approaches, which have achieved better results with dramatically various types of roads. RRT algorithms randomly build a space-filling tree to efficiently handle problems with obstacles and differential constraints by searching nonconvex and high-dimensional spaces [21]. Kothari et al. [22] proposed a RRT method to handle path planning problem of unmanned aerial vehicles with uncertainty. The probability of constraint violation and uncertain dynamic obstacles are, respectively, limited by a chance constraint and its extended framework. To further improve search efficiency, Bi-RRT algorithms with bidirectional search have appeared [23, 24]. Two RRTs, respectively, root at the initial and the target state, and algorithms seek states that are “common” for two trees. In [24], a Bi-RRT∗ approach with the intelligence is adopted to handle path planning problem with complex cluttered environments.A complete overview to heuristic-based algorithms for path planning, which can be found in [3].


## 3. Theory ofR-Functions

### 3.1. Terminology Definition

The sign of anR-function is completely determined by the sign of its variable and has nothing to do with the value of its variable. For example, a functiong1=x1x2x3 is negative, if the number of its negative variables is odd or positive otherwise. In general, the domain of variable not just has positive or negative but has the form ≥a or <a(a is a real number). In a practical application, the real domain is usually divided into (-∞, -0] and [+0, +∞). Then, the definition of anR-function can be expressed as follows.Definition 1 (R- function y).
Give a functionS(x) with real parameterx, which has the forms(1)Sx=0ifx≤-01ifx≥+0.A real function y=g(x1,…,xn) is anR-function, if there is a logic function Y=G(X1,…,Xn) which makes the equation S[f(x1,…,xn)]=G[S(x1),…,S(xn)] true. Here, the function Y is calledg’sadjoint function. SomeR-functions have the same adjoint function, such as functions(2)g1=x1x2x3,g2=x1+x2+x1x2+x12+x22.A group ofR-functions with the same adjoint function is called anR-function branch. Key characteristics of anR-function are given in the following section (more characteristics can be found in [2]). (1)
The set ofR-functions has closure properties under a composition operator. Thus, a function can be obtained by compositing someR-functions, and it is also anR-function.(2)
Ifg1 and g2 areR-functions from the same branch, then the function g1 +g2 is anR-function belonging to the same branch.


### 3.2. Sufficiency Completeness

The characteristics of anR-function show that a complexR-function may be generated from simpleR-functions. If there is a group ofR-functions, which can generateR-functions belonging to any branch by using composition operators, we define this group ofR-functions as a function system with sufficiency completeness.Rvachev [25] presented some usefulR-functions with sufficiency completeness. Here, we give a Ra-function system for basic logic operation, such as “negation” (¬), “conjunction” (∧), or “disjunction” (∨).(3)¬x=-x;x1∧ax2=11+ax1+x2-x12+x22-2ax1x2;x1∨ax2=11+ax1+x2+x12+x22-2ax1x2.Here,a(x1,x2) ∈[-1, 1]. Ifa=0 ora=1, we call a Ra system an R0 system or an R1 system. For function systems Ram and Rp, their logical operations can be defined as follows:(4)x1∧amx2=x1∧ax2x12+x22m/2;x1∨ax2=x1∨ax2x12+x22m/2;x1∧px2=x1+x2-x12p+x22p1/2p;x1∨px2=x1+x2+x12p+x22p1/2p.And their “¬” operations have the same handling rule with Ra-function system.Although the above-mentionedR0-function system and R1-function system have the same logic function, their differential characteristics are various. For instance, R0-function system is nondifferentiable at the origin of coordinate while other points are differentiable; but R1-function system is nondifferentiable at the point x1=x2 or x1=-x2; and Ram-function system hasm-order differential operators at the origin of coordinate while other points have infinite differential operators. Differential characteristics of Ra-function system have great influence in practical applications. Ram-function system has better differential characteristics while the calculation of R0-function system is simple.


### 3.3.R-Function Representation for a Geometric Object

Boolean operations (such as “intersection” and “union”) between basic primitives can be used to express aCSG model [26]. Then, a geometric object B has the following form: (5)B=GB1,B2,…,Bm.Here, Bi (i=1, 2, …,m) is a basic primitive; and G is a regular Boolean function whose operations have forms ∩∗, ∪∗, and —∗. If we use logical operators ∧, ∨, and ¬ to displace Boolean operations,Gwill become a logical function. Combined with the definition ofR-function, a geometric object B can be expressed as follows: (6)GSB1,SB2,…,SBm=1If we define the signed distance functiongi(x) for a basic primitive Bi as(7)Bi:gix≥0i=1,2,…,m, (6) can be rewritten as follows:(8)GSg1,Sg2,…,Sgm=1.Given a continuous functiong(x) and its adjoint functionG(X1,…,Xn), a geometric object B in (6) can be expressed as the following form [16]:(9)gg1,g2,…,gm≥0.In the above formula, gi (i=1, 2, …,m) is a real continuous function while g is an implicit function of a geometric object. In the following, we give an example to illustrate the definition of implicit function g. In Figure 1(a), basic regions B1 and B2, respectively, have the following equations:(10)B1:g1x,y=4-x2≥0;(11)B2:g2x,y=1–y2≥0.It can be seen from Figure 1(a), rectangular region B has logic functionB=B1∧B2. Then, using R0-function system to represent region B has the following implicit function g:(12)g=g1∧0g2=g1+g2-g12+g22.If g1 in (10) and g2 in (11) are plugged into (12), (2) has(13)g=5-x2-y2-x4+y4-8x2-2y2+17.Figure 1
The rectangular regionB and its logic function g.
(a)
B=B1∧B2 (b)
B=B1∨B2


## 3.1. Terminology Definition

The sign of anR-function is completely determined by the sign of its variable and has nothing to do with the value of its variable. For example, a functiong1=x1x2x3 is negative, if the number of its negative variables is odd or positive otherwise. In general, the domain of variable not just has positive or negative but has the form ≥a or <a(a is a real number). In a practical application, the real domain is usually divided into (-∞, -0] and [+0, +∞). Then, the definition of anR-function can be expressed as follows.Definition 1 (R- function y).
Give a functionS(x) with real parameterx, which has the forms(1)Sx=0ifx≤-01ifx≥+0.A real function y=g(x1,…,xn) is anR-function, if there is a logic function Y=G(X1,…,Xn) which makes the equation S[f(x1,…,xn)]=G[S(x1),…,S(xn)] true. Here, the function Y is calledg’sadjoint function. SomeR-functions have the same adjoint function, such as functions(2)g1=x1x2x3,g2=x1+x2+x1x2+x12+x22.A group ofR-functions with the same adjoint function is called anR-function branch. Key characteristics of anR-function are given in the following section (more characteristics can be found in [2]). (1)
The set ofR-functions has closure properties under a composition operator. Thus, a function can be obtained by compositing someR-functions, and it is also anR-function.(2)
Ifg1 and g2 areR-functions from the same branch, then the function g1 +g2 is anR-function belonging to the same branch.


## 3.2. Sufficiency Completeness

The characteristics of anR-function show that a complexR-function may be generated from simpleR-functions. If there is a group ofR-functions, which can generateR-functions belonging to any branch by using composition operators, we define this group ofR-functions as a function system with sufficiency completeness.Rvachev [25] presented some usefulR-functions with sufficiency completeness. Here, we give a Ra-function system for basic logic operation, such as “negation” (¬), “conjunction” (∧), or “disjunction” (∨).(3)¬x=-x;x1∧ax2=11+ax1+x2-x12+x22-2ax1x2;x1∨ax2=11+ax1+x2+x12+x22-2ax1x2.Here,a(x1,x2) ∈[-1, 1]. Ifa=0 ora=1, we call a Ra system an R0 system or an R1 system. For function systems Ram and Rp, their logical operations can be defined as follows:(4)x1∧amx2=x1∧ax2x12+x22m/2;x1∨ax2=x1∨ax2x12+x22m/2;x1∧px2=x1+x2-x12p+x22p1/2p;x1∨px2=x1+x2+x12p+x22p1/2p.And their “¬” operations have the same handling rule with Ra-function system.Although the above-mentionedR0-function system and R1-function system have the same logic function, their differential characteristics are various. For instance, R0-function system is nondifferentiable at the origin of coordinate while other points are differentiable; but R1-function system is nondifferentiable at the point x1=x2 or x1=-x2; and Ram-function system hasm-order differential operators at the origin of coordinate while other points have infinite differential operators. Differential characteristics of Ra-function system have great influence in practical applications. Ram-function system has better differential characteristics while the calculation of R0-function system is simple.


## 3.3.R-Function Representation for a Geometric Object

Boolean operations (such as “intersection” and “union”) between basic primitives can be used to express aCSG model [26]. Then, a geometric object B has the following form: (5)B=GB1,B2,…,Bm.Here, Bi (i=1, 2, …,m) is a basic primitive; and G is a regular Boolean function whose operations have forms ∩∗, ∪∗, and —∗. If we use logical operators ∧, ∨, and ¬ to displace Boolean operations,Gwill become a logical function. Combined with the definition ofR-function, a geometric object B can be expressed as follows: (6)GSB1,SB2,…,SBm=1If we define the signed distance functiongi(x) for a basic primitive Bi as(7)Bi:gix≥0i=1,2,…,m, (6) can be rewritten as follows:(8)GSg1,Sg2,…,Sgm=1.Given a continuous functiong(x) and its adjoint functionG(X1,…,Xn), a geometric object B in (6) can be expressed as the following form [16]:(9)gg1,g2,…,gm≥0.In the above formula, gi (i=1, 2, …,m) is a real continuous function while g is an implicit function of a geometric object. In the following, we give an example to illustrate the definition of implicit function g. In Figure 1(a), basic regions B1 and B2, respectively, have the following equations:(10)B1:g1x,y=4-x2≥0;(11)B2:g2x,y=1–y2≥0.It can be seen from Figure 1(a), rectangular region B has logic functionB=B1∧B2. Then, using R0-function system to represent region B has the following implicit function g:(12)g=g1∧0g2=g1+g2-g12+g22.If g1 in (10) and g2 in (11) are plugged into (12), (2) has(13)g=5-x2-y2-x4+y4-8x2-2y2+17.Figure 1
The rectangular regionB and its logic function g.
(a)
B=B1∧B2 (b)
B=B1∨B2


## 4. Discrete-Convex Hull Method

In Section3.3, usingR-function to express a geometric object is based on itsCSG model. However, a geometric object usually has variousCSG representations. For example, rectangular region B in Figure 1(a) has logic functionB=B1∨B2 in Figure 1(b).CSGrepresentations usually have various logic functions and implicit functions, but they have the same logic functionality. In fact, it is an intractable task to automatically generate aCSG representation for a complex object. Even so, existing algorithms can automatically generateCSG representation for polygon regions and polyhedrons. In [27], a polygon region is automatically divided into some Sidechains with the intersection of convex hull vertices. Then, the intersection of the half-space defined by Sidechains can be adopted to express a polygon region while the half-space is represented by the intersection or the union of the edges. If the intersection of two edges is a concave, the half-space is the union; otherwise, the half-space is the intersection. For instance, polygonal region P in Figure 2 has logic functionP=C1∧C2∧C3∧C4. Here, C1= e1∧e2∨e3, C2= e4, C3= e5∨e6, and C4=e7∧e8. Besides, convex hull method has been applied to polyhedrons in a three-dimensional space [28, 29].Figure 2
Convex hull method for a polygon region.
(a)
A polygon regionP and its convex hull (b)
A Sidechain graph for polygon regionPHowever, the above-mentioned method is unsuitable for a geometric object with some curves or surfaces. Then, the surface is approximately discretized into planes while the curve is approximately discretized into straight lines. Thus, plane regionP in Figure 3(a) has logic functionP=e1∧e2∧e3∧e4 (see Figure 3(b)) and P=e1∧(e21∧e22∧e23∧e24)∧e3∧e4 (see Figure 3(c)). In Figure 3(c), the curve e2 is discretized into straight lines e21, e22, e23, and e24.Figure 3
Plane regionP with a curve is discretized.
(a)
Plane regionP (b)
P = e1∧e2∧e3∧e4 (c)
P = e1∧(e21∧e22∧e23∧e24)∧e3∧e4The above-mentioned approach for dealing with a geometric object is called a discrete-convex hull method. If the geometric object is a polygon without a curve or a polyhedron without a surface, the implicit function is accurate; otherwise, the implicit function approximately expresses the geometric object.Discrete-convex hull method not only automatically generatesCSG representation for a geometric object but also solves the problem of Point Membership Classification (PMC) [30].PMC problem might lead to the implicit function with 0 value for a nongeometric object on its boundary. There are the following two aspects. First, irregular Boolean intersection ∩ for a basic primitive might produce pendent points, pendent edges, or pendent planes (see Figure 4). As the operation ∧ for anR-function is irregular, the implicit function of a geometric object may has pendent points on its outside part. Second, rectangular region B has logic functionB= B1∨B2 in geometry (see Figure 1(b)). But for mathematical analysis, the operation ∨ of anR-function cannot ensure that the implicit function has 0 value onB’s boundary. AsPMC exists, the implicit function cannot define the interference constraint between a geometric object and a space point. Fortunately, a discrete-convex hull method avoids the above-mentioned problems. The reasons are that two adjacent lines (planes) of a polygon (polyhedron) just intersect in one point (straight line), and this point (straight line) must belong to the boundary of this polygon (polyhedron). For the operation Boolean union, the discrete-convex hull method will not produce thePMC problem.Figure 4
Irregular intersectionB1∩B2 causes pendent edgel.Therefore, the implicit function of a geometric object based on discrete-convex hull method has 0 value on the object’s boundary. And the internal point and external point, respectively, have a value < 0 or > 0. Then, the sign of the function determines whether a space point and a geometric object have the interference. Ifg(x) represents an implicit function of a geometric object,g(x)≤0 shows that there is no interference between the space point x and the object.


## 5. Normalized R-Function

The implicit function based on the above-mentioned approach cannot accurately calculate the signed distance between a space point and an object’s boundary. For instance, the function has value of -0.84 at the point (1, 0) for the rectangular region given by the implicit function equation (13) in Section 3. But the minimum signed distance between the point (1, 0) and the boundary of the rectangular region is -1.0 in practices.LetL be the boundary of a geometric object and p be a space point; the signed distance ρ(p,L) between the point p and the boundary L can be expressed as follows:(14)ρp,L≡inf⁡ρp,q,q∈L.where ρ(p,q) is the signed distance between the point p and the pointq; if p∈G, the signed distance ρ(p,L) is “+” (there is the interference between the point p and the pointq); otherwise, it is “-”. If all space points satisfy the condition g(p)=ρ(p,L), the function g is calledG’s normal function. For example, let (a,b) and r, respectively, be the centre and radius of a circle; the normal function g of this circular region has the following form:(15)g=r-x-a2+y-b2.As most of geometric objects have some nonsmooth adjacent surfaces, their normal functions usually do not exist. Thus, we introduce the concept of normalized function for a geometric object. A similar normal functiong- with essential differential attributes for a complex object is introduced, which satisfies the following conditions:(16)g-q=0,∂g-∂vq=1,∂kg-∂vkq=0k=1,2,…,m,where q is a regular point on the boundaryL and v is the normal unit vector of the point q. Then, g- is them-order normalized function of a geometric object. There are very small differences between normalized function near the boundary and signed distance function. And normalized function far from the boundary is gradually, continuously, and smoothly similar to signed distance function. In general, manyR-functions have the above-mentioned normalized properties. For anR-function without normalized properties, the following method can be adopted to normalize.If the functiong∈Cm, a point q on the boundary L satisfies the following conditions:(17)gq=0,∂g∂vq>0.Then,g can use the following formula to normalize into the first-order form.(18)g-≡gg2+∇g2-1/2∈Cm-1.Moreover, higher-order normalized method for the function g can be found in [31].M-order normalized functions g1 and g2 have the same logical operations g1∨g2 and g1∧g2 with R function. Figure 5 lists the distribution of first-order normalized function (it is also called similar signed distanced field; Rp-function (p=2) system is adopted) for the polygonal region in Figure 2.Figure 5
The normalized function and its similar signed distanced field.The generation of normalized function of a geometric object can be summarized below.Firstly, a discrete-convex hull method is adopted to generate the implicit functiong using the following three steps:(1)
A geometric object is transformed into a polygon (polyhedral). Then, a half-space implicit function that points to the interior of a geometric object is created based on its polygon (polyhedral) and edges (planes).(2)
A convex hull method is introduced to generateCSG representation and logic function for this geometric object.(3)
The logic function, the implicit function of an edge (plane), and appropriateR-function system are adopted to construct the implicit function g for whole geometric object.Secondly, the implicit functiong is normalized into g-.


## 6. Path Planning with Obstacle Avoidance

In obstacle environments, path planning with obstacle avoidance is to find an obstacle avoidance path for a moving part from a given initial posture to the final target posture. It is an optimization problem with noninterference between moving parts, noninterference between a moving part and a barrier, or kinematics constraints. For simplicity, we only discuss path planning with a moving part and noninterference between a moving part and a barrier in this paper. For the environments withn obstacles, path planning with obstacle avoidance based on typical optimization can be expressed as follows:(19)minfx,s.t.gix≤0i=1,2,…,n.In the above formula,x is a motion variable and gi (x) ≤0 represents noninterference between a moving part and thei-th obstacle andf(x) is an objective function.For existing path planning approaches with obstacle avoidance based on numerical analysis, most of interference constraints cannot be explicitly defined using the above-mentioned inequality. Thus, two procedures are adopted to solve these problems. First, the interference checking is used to qualitatively determine whether there is interference between a moving part and an obstacle. Second, if it is noninterference, the minimum distance between a moving part and an obstacle and gradient direction of motion parameters are quantitatively calculated, which are used to guide next iteration. Although existing algorithms can deal with them, they usually have heavy computing burden.Fortunately, normalizedR-function of a geometric object is not only applied to represent interference constraints between two objects, but also there are essential differential properties. Then, (19) can be rewritten as the following forms: (20)minfx,s.t.g-iDPtjx≤0i=1,2,…,n;j=1,2,….Here, g-i andDPtj, respectively, express normalizedR-function of thei-th obstacle and a discrete point of moving partM’s surface.For path planning with obstacle avoidance, we must ensure that planning paths have noninterference between a moving part and a barrier. Then, it requires that each iteration point will not default for solving (20). The reason is that interference constraint conditions cannot be strictly ensured for some artificial potential field methods [11]. Therefore, a feasibleSQP method in [32] is adopted to solve (20).SQP is a local optimum algorithm based on the gradient with the superliner convergence.Based on the above analysis in Sections3.3, 4, 5, and 6, the flow diagram of the proposed method is given in Figure 6.Figure 6
The flow diagram of the proposed method.


## 7. Experimental Results

To validate the proposed approach in this paper, some experiments have been performed for path planning with obstacle avoidance on the following three conditions:(1)
The generation of the implicit function is similar in a two-dimensional space and a three-dimensional space, and the representation of the implicit function is relatively complex in a three-dimensional space. For simplicity, examples are conducted in a two-dimensional space.(2)
Compromise differential properties and the computational complexity for a normalized function; anRp-function system (p=2) is adopted to create the implicit function for an obstacle.(3)
The tests are conducted on a computer withDELL OPTIPLEX 760 and WindowsXP andMatlab (R2001a).First, a single-point moving partM is moved to the target position E from an initial position S through the translation movement in x direction and y direction, and the obstacles O1, O2, …, O5 have been avoided (see Figure 7). Besides, the obstacle O5 has an arc c. Then, it is easy to get normalized function of an obstacle and to create interference constraints for (20).Figure 7
Planning path with obstacle avoidance for a single-point moving part.
(a)
Obstacle avoidance planning environments (b)
A planning path forO5’s arcc with 4 discrete straight-line segments (c)
A planning path forO5’s arcc with 6 discrete straight-line segments (d)
Normalized functions of obstacles affect the iteration directionIn Figures7(b) and 7(c),O5’s arc c is, respectively, discretized into 4 and 6 straight-line segments, and their corresponding planning paths are listed. As there is a higher discrete approximation forO5’s arc c in Figure 7(c), its planning path is more reasonable. In general, the curve of an obstacle has more discrete straight-line segments; normalized function is more complex, which will lead to higher computational complexity. The time is spent on planning paths forO5’s arc c with various discrete approximations is given in Table 1.Table 1
The time is spent on planning paths forO5’s arc c with various discrete approximations.
The number of discrete straight-line segments for arcc 4 6 10 30 100  The time is spent onplanning paths(s) 0.6262 0.6434 0.6790 0.92846 1.9188Figure7(d) is partial enlargement of dashed boxes in Figure 7(c), which is listed to further illustrate the role of normalized function in path planning. Red and blue plots in Figure 7(d), respectively, express outer distance field of obstacles O2 and O3. At an iteration pointI, d2 and d3, respectively, express negative gradient direction of normalized function of obstacles O2 and O3, and do represents negative gradient direction of the objective function. To avoid obstacles O2 and O3, d2 and d3 make final search direction be revised to d at iteration pointI.Second, a moving partM is a polygonal region, which has three degrees of freedom (the translation movement in x and y directions, and the rotation motion in z direction), and O1, O2, O3, and O4 are obstacles (see Figure 8). To generate interference constraints between a moving part and an obstacle,M’s boundary is uniformly discretized into 142 points. AndM’ is the target posture of a moving part. The translation and rotation motions of a moving part M make bold edges of M and the obstacle O1 are aligned, and their midpoints P1 and P2 are coincident in Figure 8(a). Therefore, the objective function for (20) can be expressed as follows:(21)fx=W1cos⁡n1x,n2+W2P1x-P22,where n1(x) is a function of external normal vector n1 ofM’s bold edge for motion parameterx and n2≡(1 0 0) expresses external normal vector ofO1’s bold edge and P1(x) represents a function of the midpoint P1 ofM’s bold edge for the parameterx and W1 and W2 describe weight coefficients. As the cosine value of the vectorial angle is smaller (≥-1 and ≤1), we, respectively, set W1 =100 and W2 =1.Figure 8
Path planning with obstacle avoidance for a polygonal region moving part.
(a)
Obstacle avoidance planning environments (b)
Path planning with obstacle avoidance (c)
The partial enlargement of dashed boxes in Figure8(b)Figure8(b) has listed obstacle avoidance planning paths for a polygonal regionM, and dashed lines representM’s posture. To observe clearly, solid lines are adopted to expressM’s typical postures. And Figure 8(c) is partial enlargement of dashed boxes in Figure 8(b). It can be seen from Figure 8, moving part M successfully avoids obstacles O2 and O3 on the basis of posture adjustments. Experimental results have shown that normalized functions of the obstacles can well approximate their signed distanced fields, and their gradient information may guide obstacle avoidance planning paths.The proposed approach for path planning with obstacle avoidance is based on semianalytic geometry withR-functions, which has rigorous mathematical analysis. In general, the characteristics of the algorithm are that the results usually have higher accuracy while the processing speed of the algorithm is relatively slow. In particular, the processing time for various instances has greater diversity.


## 8. Conclusions

A path planning method with obstacle avoidance based on normalizedR-functions is presented in this paper. First, anR-function is introduced to represent a geometrical object, which ensures that normalized R-function near the boundary of a geometrical object has little difference with signed distance functions, and other parts are continuously and smoothly similar to signed distance functions. Thus, normalizedR-function can be applied to define interference constraints between a space point x and a geometrical object. As for the generation of interference constraint between two geometrical objects, this needs to plug discrete points of a geometrical object’s boundary into normalized R-function of another object. Finally, path planning with obstacle avoidance for a single-point and polygonal region is conducted to validate the presented approach. Experimental results have shown that the proposed method is a feasible way for path planning with obstacle avoidance.



---

*Source: 5868915-2018-10-04.xml*