A New Path Generation Algorithm Based on Accurate NURBS Curves

Abstract

The process of finding an optimum, smooth and feasible global path for mobile robot navigation usually involves determining the shortest polyline path, which will be subsequently smoothed to satisfy the requirements. Within this context, this paper deals with a novel roadmap algorithm for generating an optimal path in terms of Non-Uniform Rational B-Splines (NURBS) curves. The generated path is well constrained within the curvature limit by exploiting the influence of the weight parameter of NURBS and/or the control points' locations. The novelty of this paper lies in the fact that NURBS curves are not used only as a means of smoothing, but they are also involved in meeting the system's constraints via a suitable parameterization of the weights and locations of control points. The accurate parameterization of weights allows for a greater benefit to be derived from the influence and geometrical effect of this factor, which has not been well investigated in previous works. The effectiveness of the proposed algorithm is demonstrated through extensive MATLAB computer simulations.

Keywords

Global Path Planning Obstacle Avoidance NURBS Curve Parameterization Curvature Constraint Skeletonization Continuous Path

1. Introduction

Since the 1980s, path planning has been a hot issue in robotic and automation fields. The solution should not only guarantee a collision-free path with minimum travelling distance, but also provide a smooth and feasible path from the initial location to a goal location in an environment cluttered with obstacles. The path planning environment can be either static or dynamic. For the static environment, the whole solution can be found before starting execution. However, for dynamic or partially observable environments, replanning is required frequently and more update time is needed. There are many studies on robot path planning using various approaches, which can be broadly classified into local and global methods.

Global or deliberative approaches include classic strategies that rely on capturing the topology of the environment and synthesizing it, either in a graph (visibility graph, Voronoi diagram, cell decomposition,…), or in a tree connecting the start to the goal position (Rapidly-exploring Random Trees (RRT),…). They also include heuristic strategies (genetic algorithms, neural networks,…). Local or reactive approaches, on the other hand, can operate online, exploiting local sensor information. These approaches include, likewise, classic strategies (potential fields, dynamic window,…) and intelligent methods (fuzzy logics,…). Although the fact that local approaches can be applied in any type of environment, whether static or dynamic, the convergence towards the final position is not guaranteed. For a broader review of past research, we refer the reader to [1, 2].

The review of research works on robotic path planning shows that most of them provide a piecewise linear solution. Thus, the robot following this path has to stop and restart frequently, which causes the waste of energy. To obtain a smooth path, many curves have been introduced as path primitives. The focus is on turning a sequence of configurations into a smooth curve that is then passed to the control system of the robot. The used curves fall into two categories: those whose coordinates have a closed-form expression (B-spline, quintic polynomials, polar splines, etc.) and parametric curves whose curvature is a function of their arc length (clothoids, cubic spirals, intrinsic splines, etc.) [3].

Dubins paths, which are made by joining straight lines and circular arcs of maximum curvature, were proposed to generate feasible paths for car-like robots [4]. However, as highlighted by Fraichard and Scheuer [3], the curvature of this type of path is discontinuous. In fact, discontinuities arise at the transitions between segments and arcs, and between arcs with opposite directions of rotation. Following that, they proposed the first steering method that computes paths with continuous curvatures, upper bounded curvatures and upper bounded curvature derivatives. This method, called CC Steer, computes paths made up of line segments, circular arcs and clothoid arcs. Nevertheless, as mentioned in [5, 6], clothoids have no closed form and have to be approximated by high-order polynomials and splines, which limits their use for real-time robotic applications.

Meanwhile, Li et al. [7] have introduced a technique to derive a smooth, obstacle-avoiding curve from a given obstacle-avoiding polyline path. In fact, supposing that a planar region that contains some obstacles is given, and assuming that a polyline path that does not touch any of the obstacles is also given, the guiding polyline will be replaced by a $G^{2}$ cubic spline curve, which has the same number of inflection points as would be suggested by this guiding polyline and which, in its turn, controls the curve's shape. Also, Ho et al. [8] have presented an obstacle avoiding smooth-path planning method based on a Voronoi diagram and a composite Bézier curve algorithm, which allows them to obtain the curvature bounded path with a small length. In their approach, a diagram is constructed according to the global environment. Then, the piecewise linear rough path in the Voronoi diagram, which maintains a distance from the obstacles, is obtained by performing Dijkstra's shortest path algorithm. Dynamic programming is employed to subdivide the nodes on the piecewise linear path into control point subsequences, in order to generate a collision-free composite Bézier curve that satisfies the curvature constraint and approaches minimal path length.

As a continuing work on $G^{3}$ -continuous path planning for mobile robots in the predefined static environment, Ho et al. [9] proposed a method that simultaneously minimizes the total length and the maximum curvature along the trajectory by using the easily customized variable-length Island-based Parallel Genetic Algorithm (IPGA) as a path-computing framework and $η^{3}$ -splines as the path primitive for waypoints' interpolation. A multi-objective genetic algorithm is implemented to find and optimize multiple collision-free paths, in order to obtain a $G^{3}$ -continuous composite $η^{3}$ -spline path with each $η^{3}$ -spline segment being shorter and a larger minimum-turning radius along the whole path. In [10], Yang et al. have proposed a Spline-based Rapidly exploring Random Tree (SRRT) method for robot path planning, which guarantees continuity of curvature and satisfies any upper-bounded curvature constraints.

Maekawa et al. [11] have introduced a roadmap algorithm for generating collision-free paths in terms of cubic B-spline curves. The method employs the visibility graph technique. In fact, once the reduced visibility graph is obtained, a weighted graph is generated by considering the Euclidean distances between the endpoints as weights. Then, the shortest path is found using Dijkstra's algorithm. Since the obstacles and the boundaries of the configuration space are assumed to be polygonal, the resulting path consists of straight line segments. Therefore, in order to generate a curvature continuous path, the intersection points of the resulting line segments are interpolated using a cubic B-spline curve. However, the interpolated curve may collide with both obstacles and the boundary segments. Also, the curvature may exceed the maximum allowable value. To solve these problems, a simulated annealing method has been used. Lobaton et al. [12] have presented a method for planning curvature-constrained paths to multiple goals using circle sampling. In fact, a roadmap is constructed by sampling circles of constant curvature and then generating feasible transitions between them by providing a closed-form formula. Then, the multi-goal planning problem is formulated as finding a minimum directed Steiner tree over this generated roadmap. Greedy heuristics are introduced to reduce the exponential complexity of the problem.

Among these different curves, Non-Uniform Rational B-Spline (NURBS) curves are more intuitive due to their important properties, which will be dealt with in more detail in the next section. NURBS have a broad range of applications in various domains, but a limited use in robotics. Recently, Siddavatam et al. [13] have developed a new method of robot motion planning in a dynamic environment using offset NURBS. Their methodology, used to obtain the optimal shortest path, can be further subdivided into levels. The first level consists in obtaining the mathematical dynamic polygonal environment that models the obstacles. The second one aims to identify the obstacles found along the ideal path. The next level consists in a mathematical model that constructs a new set of optimal points to form the shortest path from the initial to the end point. The purpose of the subsequent stage represents the plotting of a newer set of points, along with taking vector additions into consideration if the two points to be joined are from different obstacles, as well as avoiding any intersecting point, if encountered. Finally, the NURBS technique is applied to plot the shortest path using the computed set of points. NURBS offset is generated for the computed shortest path in order to avoid any collision. Xidias and Aspragathos [14] have presented a new algorithm for finding the shortest continuous curvature-constrained path for a car-like robot using S-Roadmaps. Indeed, in the beginning, random samples from the 2D environment are taken and, using Delaunay triangulation, a graph is constructed. Then, after adding start and goal positions to this graph, a B-Surface concept is employed to represent the robot's environment. The second step consists in building a roadmap onto the B-Surface, one that does not incorporate any kinematical constraints. The paths encoded in the roadmap consist of poly-geodesic segments. Optimization and smoothing of these paths are provided by using NURBS curves.

As will be detailed in the next section, a NURBS curve is defined by its order, a set of weighted control points and a knot vector. Seeing that they are a weighted extension of Non-Uniform Rational B-splines, a high level of flexibility and a great capacity to produce natural smooth curves is guaranteed. Therefore, accurate parameterization is needed to meet the desirable result. This was not well-considered in previous path planning algorithms, mainly the parameterization of the weight factor that has interesting geometric and analytical interpretations.

In this paper, we address two key issues in robot path planning: path continuity and maximum curvature constraint for nonholonomic robots. Its main contributions are the following. First, the adaptivity of the proposed method, which provides the optimal or near-optimal path in terms of length and obstacle avoidance, and respects the curvature constraint related to the robot's characteristics, irrespective of the number, size and location of obstacles. Second, NURBS curves are not used only as a means of smoothing but are also involved in meeting the system's constraints via a suitable parameterization of control points' weights as well as their location. Through rigorous computer simulations, the proposed method is shown to perform excellently and gave satisfactory results.

The remaining part of this paper is organized as follows. Section 2 introduces NURBS curves. In Section 3, the problem is formulated. The details of the proposed approach are introduced in Section 4. Computer simulations are given in Section 5. In Section 6, we present a brief discussion. Finally, in Section 7, we summarize the main findings of the article.

2. Non-Uniform Rational B-Splines (NURBS) Curves' Approximation

In this section, we briefly introduce the mathematical definition of NURBS curves. In addition, we present their important characteristics that have contributed to their wide acceptance as standard tools for geometric representation and design. Then, we investigate the geometric meaning of the weight parameter.

2.1. Definition

A $p^{t h}$ degree NURBS curve is a vector valued, piecewise rational polynomial function of the form:

C (u) = \sum_{i = 0}^{n} R_{i, p} (u) P_{i} a \leq u \leq b

(1)

where ${P_{i}}$ are the n control points ( $n > 2$ ). The ${R_{i, p} (u)}$ are the rational basis functions and are defined by:

R_{i, p} (u) = \frac{N_{i, p} (u) w_{i}}{\sum_{j = 0}^{n} N_{j, p} (u) w_{j}}

(2)

The ${w_{i}}$ are the weights of control points and the ${N_{i, p} (u)}$ are the $p^{t h}$ B-spline basis functions defined on the non-uniform knot vector U, by the DeBoor-Cox Calculation, as follows:

N_{i,0} (u) = {\begin{array}{l} 1 & i f u_{i} \leq u < u_{i + 1} \\ 0 & e l s e \end{array}

\begin{array}{l} N_{i, p} (u) = \frac{u - u_{i}}{u_{i + p} - u_{i}} N_{i, p - 1} (u) + \frac{u_{i + p + 1} - u}{u_{i + p + 1} - u_{i + 1}} N_{i + 1, p - 1} (u) \end{array}

(3)

The knot vector $U = {a,…, a, u_{p + 1},…, u_{m p - 1}, b,…, b}$ is a sequence of parameter values that determines where and how the control points affect the NURBS curve. In fact, the knot vector divides the parametric space in knot spans. Each time the parameter value u enters a new knot span $[u_{i}, u_{i + 1}]$ , a new control point becomes active, while an old control point is discarded. It follows that the values in the knot vector should be in increasing order. The multiplicities of a and b are equal to the order of the curve. This constraint ensures the interpolation of the two endpoints. We also recall that the number of knots is always equal to the number of control points plus curve degree plus one ( $m = n + p + 1$ ). Throughout this paper, we assume that $u \in [0,1]$ .

Some reasons for the widespread acceptance and popularity of NURBS in the CAD/CAM and graphics community are as follows [15]:

They offer a common mathematical form for representing and designing both standard analytic shapes and free-form curves and surfaces.

By manipulating the control points as well as the weights, NURBS provide the flexibility to design a large variety of shapes.

Evaluation is reasonably and computationally stable.

NURBS have clear geometric interpretations.

Strong convex hull property: the NURBS curve is contained in the convex hull of its control points. Moreover, if $u \in [u_{i}, u_{i + 1}]$ , then $C (u)$ lies within the convex hull of control points $P_{i - p},‥, P_{i}$ .

NURBS are invariant under scaling, rotation, translation and shear as well as parallel and perspective projection.

Local modification: if a control point P_i is moved or a weight w_i is changed, it will affect the curve only in $[u_{i}, u_{i + p + 1}]$ .

2.2. Weights parameter influence on NURBS curves

As shown above, a NURBS curve is defined by its control points, weights and knots. Therefore, modifying any of these parameters changes the curve's shape. Throughout this paper, we use the influence of the weight factor on the resulting curve. The weight of a point P_k determines its influence on the associated curve. Thus, increasing (or decreasing) w_k leads to the augmentation (or diminution) of $R_{k, p} (u)$ which pulls (or pushes) the curve towards (or away from) this point. As shown in Figure 1: in the first case (a), all weights are 1s and the curve is a B-spline curve. In the second case, W₂ is increased to 3 and, subsequently, a portion of the curve moves toward $P 2$ . Finally, when it is increased to 30, the curve becomes much closer to $P 2$ .

Figure 1.

NURBS curve approximation of $P 1,‥ P 7$ with w₂ varying: (a) $w_{i} = 1, i = 1‥7$ , (b) w₂ increased to 3 and (c) w₂ increased to 30

It should also be noted that a control point with a weight of zero removes the contribution of this point on the generated curve and when all weights are of unit value, the curve behaves as a non-rational B-spline. For further detail, we refer the reader to [16].

3. Problem Formulation

The problem of path planning is usually formulated as follows. Given a mobile robot moving in an environment Ω, the objective is to find a feasible path from the start position $S (x, y)$ to the goal position $T (x, y)$ . In this work, the robot's work area Ω is represented by a two-dimensional discrete map cluttered with a set of static obstacles of arbitrary size and position $O_{j}, (j = 1,‥, M)$ , where O_j is the j -th obstacle in the robot's environment. Therefore, the forbidden space $Ω_{o b s t}$ , in which the robot cannot move, is defined as:

Ω_{o b s t} = \cup_{j = 1}^{M} O_{j}

(4)

Consequently, we denote by $Ω_{f r e e}$ , the space in which the robot can move freely:

Ω_{f r e e} = Ω \ Ω_{o b s t}

(5)

We assume a circular model of the nonholonomic robot R with a diameter d, taking into account its dimensions, and a minimum radius of curvature $ρ_{m i n}$ . Figure 2 shows the formulation of the path planning problem in terms of our approach. In this figure, the white areas are $Ω_{f r e e}$ and the dark ones are the impenetrable areas $Ω_{o b s t}$ . The goal is then to determine a path that should be smooth and of minimal length while taking into account the two following criteria: avoiding obstacles and having an allowable curvature.

Figure 2.

Formulation of the path planning problem in terms of our approach

4. Navigation Architecture

4.1. Overview

The proposed approach can be seen as the composition of two consecutive blocks: the first focuses on determining an optimal polyline path from the starting position S to the arrival T. This linear piecewise path should lie in the middle of the obstacle-free configuration, in order to increase the degree of security. It should also be of minimal length. The second focuses on the smoothing process using NURBS curves and taking into account the robot's minimum radius of curvature. An accurate parameterization of the locations of control points, as well as of their respective weights, is proposed. The final existing solution ensures the constraints of security and maximum allowable curvature. The proposed robot path-generation scheme is illustrated in Figure 3.

Figure 3.

The schematic diagram of the proposed method

4.2. Collision-free polyline path generation

In this section, we present the steps of determining an obstacle-avoiding polyline path between the start position S and the target position T. The main idea is based on capturing the topology of the search space $Ω_{f r e e}$ in order to simplify the problem into a search for the shortest path in a graph. In order to get away from obstacles, the latter is constructed from the skeleton of the obstacle-free configuration. Indeed, the safest position for a robot that can move safely in an accessible corridor (a corridor of width l greater than the diameter d of the robot) is to be positioned, over time, in the middle of the navigation space; a condition that justifies the interest in determining the skeleton of obstacle-free space.

We recall that skeletonization consists in reducing a form into a set of curves called ‘skeletons’, while respecting the topology of the considered form. This representation must be as thin as possible (at most, one pixel thick). It must also respect the connectivity and be centred within the shape it represents. The algorithm used in this approach is a metric criteria method [17] based on the calculation of a function that operates within a neighbourhood of eight points. The basic idea is the calculation for each image point $p (i, j)$ of a discriminant function $F (i, j)$ . This function operates over an eight-pixel neighbourhood (denoted $(X, Y)$ ). $F (i, j)$ is the length of the sum of the vectors joining $p (i, j)$ to all its neighbours ( $F (i, j) = | X | + | Y |$ ) and is between 0 and 4. The value of the function F for the point shown in Figure 4 is calculated as follows:

Figure 4.

p(i,j) and its neighbourhood

(X, Y) = (- 1,1) + (1,1) + (1,0) + (1, - 1) = (2,1)

F (i, j) = | X | + | Y | = 3

Intuitively, the points inside the form are associated with a small value of $F (i, j)$ and they will be conserved, while those outside the form are associated with larger values of $F (i, j)$ and they will be discarded. The used skeletonization technique selects skeleton points based on an iterative algorithm. Each iteration comprises two sweeps:

Sweep 1: Calculates local characteristics of each point: $| X |$ , $| Y |$ , F and $N V O I S$ (number of adjacent pixels).

Sweep 2: Either eliminates or does not eliminate the point, in terms of its characteristics.

In general, the start and goal points are not part of the skeleton (Fig. 5 (b)). Therefore, these two positions must be connected to the considered medial axis. This operation must provide a new ‘extended’ skeleton (Fig. 5 (c)) upon which the robot will progress.

Figure 5.

Skeletonization of an obstacle-free space: (a) the configurations space, (b) initial skeleton and (c) extended skeleton

The next step is the conversion of the extracted skeleton X into a graph, which requires the classification of pixels of X into Junction Points, End Points, Curve Points and a Critical Curve Point by using a morphological process [18]:

Definition 1: A point of one-pixel width digital curve is an End Point (EP) if it has a single pixel among its $3 \times 3$ neighbourhood.

Definition 2: A point of one-pixel width digital curve is defined as a Junction Point (JP) if it has more than two pixels among its $3 \times 3$ neighbourhood.

Definition 3: A point of one-pixel width digital curve is defined as a Curve Point (CP) if it has exactly two pixels among its $3 \times 3$ neighbourhood.

Definition 4: A point of one-pixel width digital curve is defined as a Critical Curve Point (CCP) if it is a curve point where the global direction of the curve changes.

Thereby, the detection of interest points of X is important for a structural description that captures the topological information embedded in the skeleton. In fact, the thin lines can be converted into a weighted graph $G = (V, E)$ associating the Curve Points with the edges, the End, the Junction and the Critical Curve Points with the vertices:

V = E P (X) \cup J P (X) \cup C C P (X)

(6)

E = {e = (x y) | x, y \in V; \forall p_{i} \in e \land p_{i} \neq {x, y} \Rightarrow p_{i} \in C P (X)}

(7)

The graph weights are generated by considering the Euclidean distances between vertices. As each edge corresponds to a corridor in which the robot may move, this last must be of a width l larger than the robot diameter d. If this is not the case, such an arc must be deleted; hence the need for the reduction step of the graph G to obtain a partial graph $G^{'} = (V, E^{'})$ in which all arcs are accessible by the robot:

E^{'} = {e = (x, y) \in E | d < l}

(8)

The resulting graph $G^{'}$ may be disconnected (Figure 6). If S and T belong to the same connected component $c c_{i}$ ( $i \in [1,‥, k]$ where k is the number of connected components of $G^{'}$ ), then the Bellman algorithm [19] is applied to calculate the shortest path between these two positions. Otherwise, the algorithm stops and no solution can be found for the path planning problem related to the treated case [20]. The process of shortest polyline path generation is described in Algorithm 7.

Figure 6.

Graph disconnection after the reduction step

Algorithm 1: Collision-free Polyline Path Generation

4.3. Continuous smoothing of collision-free polyline path using NURBS curves

The existing shortest path $S_{o p t}$ , between S and T in the reduced graph $G^{'}$ , is made up of connected edges (Figure 7 (a)). Hence, a mathematical model is needed to refine it. Non-Uniform Rational B-Splines were proposed to improve the smoothness of the previously determined optimal path. NURBS were chosen to model the robot's path because of their flexibility and geometric properties, combined with the fact that NURBS algorithms are fast and numerically stable. They allow representation of geometrical shapes in a compact form and they are adept at describing the position of a point in space.

Figure 7.

Collision-free shortest path: (a) linear piecewise path (S_opt)), (b) path smoothing using a NURBS curve

Generating a NURBS curve requires the specification of the set of control points to approximate. It must, likewise, parametrize the weights associated with this set, as well as the knot vector U. For our purposes, the control points are extracted from the selected skeleton $S_{o p t}$ :

P = {P_{i}}_{i = 1‥ n} = J P (S_{o p t}) \cup E P (S_{o p t}) \cup C C P (S_{o p t})

(9)

where $J P (S_{o p t})$ are the junction points of $S_{o p t}$ , $E P (S_{o p t})$ are the end points of $S_{o p t}$ and $C C P (S_{o p t})$ are the critical curve points of $S_{o p t}$ . The knot vector is generated exploiting the correlation information between the set of control points [21]. Regarding the weights of control points, they are initialized to 1:

w_{i} = 1, \forall i = 1‥ n

(10)

The single source shortest path (Figure 7 (a)) is smoothed following the steps already mentioned, giving the NURBS curve C, which models the planned path (Figure 7 (b)).

The previously generated NURBS curve is, in fact, a Non-Uniform Rational B-Splines curve, given that all the control points have the same weight value. We point out that two constraints must be ensured by the planned path: collision avoidance and the curvature limit related to the robot's minimum radius of curvature. Actually, the approximation of the set of control points extracted from the polyline path may distort the constraint of obstacle avoidance, since the approximated curve can introduce a large deviation relative to the determined shortest path $S_{o p t}$ . In addition, there is no guarantee that it does not exceed the robot's maximum curvature. To deal with this, we propose an efficient algorithm to readjust the initial generated path so that it respects the system's constraints. The idea relies on the use of the local control property of the NURBS curve by adjusting some weights and/or control points' coordinates.

4.3.1. Ensuring the non-collision constraint

To ensure the security of the planned path, we investigate the influence of the weight parameter on the curve. In fact, the increase in value of w_i attracts the curve towards the associated point P_i which, consequently, ensures the constraint of non-collision. The idea consists, in the first place, in localizing the set T of curve points that intersect obstacles:

T = {t_{j}}_{j = 1‥ n 1} = C \cap Ω_{o b s t}

(11)

To determine this set, it is sufficient to check for each point $p (i, j)$ of the curve the possibility of crossing with $Ω_{o b s t}$ . In fact, we considered that obstacles and scene margins are represented by pixels with a value of seven, while pixels with a value of one are floor pixels. Consequently, p lies in the set T if $p (i \pm {0, d / 2}, j \pm {0, d / 2}) = 7$ (where d is the diameter of the circle representing the robot). The second step, in the obstacle-avoidance process, is to determine for each point of T its closest control point. These points constitute the first set of critical points $T 1$ :

\begin{array}{l} T 1 = {P_{j} \in P | d i s t a n c e (P_{j}, t_{j}) = M i n (d i s t a n c e (P_{i}, t_{j})), i = 1‥ n, j = 1‥ n 1} \end{array}

(12)

Once the set $T 1$ is determined, the procedure consists in increasing the weights associated with these points and regenerate the curve until the cardinality of the set T converges to 0. Therefore, the final generated curve C corresponds to the optimal collision-free path for the robot. Figure 8 illustrates the collision avoidance process. In this example, after extracting the linear piecewise path (Figure 8 (a)), the approximation of the set of control points ( $P 1,‥, P 10$ ), derived from ( $S_{o p t}$ ), by a third-degree NURBS curve has produced a non-safe path in the neighbourhood of $P 8$ and $P 9$ (Figure 8 (b)). The increase in the weights of these two points has successfully ensured the non-collision constraint of the robot path, as shown in Figure 8 (c).

Figure 8.

Collision Avoidance Process: (a) linear piecewise path (S_opt)), (b) path smoothing using a NURBS curve (before the collision avoidance process), initial weights vector W=(1,1,1,1,1,1,1,1,1,1) and (c) path smoothing using a NURBS curve (after the collision-avoidance process), final weights vector W=(1,1,1,1,1,1,1,10,8,1)

4.3.2. Ensuring the curvature constraint

In the previous section, we determined a collision-free and smooth path modelled by a NURBS curve of degree p ( $C^{p - 1}$ continuous everywhere). The addition of the curvature as a parameter when generating the optimum path expresses, naturally, the curvature continuity constraint.

The curvature parameter can be matched tothe velocity and acceleration constraints. In fact, a continuous allowable curvature is of practical importance for mobile robot planning and control, because a path with a smaller variation of curvature is more appropriate for tracking and control than a path with large deviation of curvature, in order to avoid the rapid change of radial acceleration [9]. As a parametric curve, the curvature function of a NURBS curve is computed as follows [22]:

κ (u) = \frac{(C^{'} (u) \times {C^{'}}^{'} (u)) . B}{{| C^{'} (u) |}^{3}}

(13)

where $C^{'} (u)$ and ${C^{'}}^{'} (u)$ are the first and second derivatives, and B denotes the bi-normal (a vector perpendicular to the tangent and the normal of the curve). The first derivative of the NURBS curve is expressed by [23]:

C^{'} (u) = \sum_{i = 1}^{n + 1} {R^{'}}_{i, p} (u) P_{i}

(14)

where:

{R^{'}}_{i, p} (u) = \frac{w_{i} {N^{'}}_{i, p} (u)}{\sum_{i = 1}^{n + 1} w_{i} N_{i, p}} - \frac{w_{i} N_{i, k} \sum_{i = 1}^{n + 1} w_{i} {N^{'}}_{i, k}}{{(\sum_{i = 1}^{n + 1} w_{i} N_{i, p})}^{2}}

(15)

A detailed description of the calculation of derivatives of a NURBS curve is presented in [16]. Figure 9 illustrates a NURBS curve approximation of seven control points and its associated curvature variations. The goal of this section of the path planner is to refine the previously generated curve by introducing a bounded curvature constraint:

Figure 9.

(a) NURBS curve approximation of P1,‥,P7. (b) Associated curvature profile.

| κ | \leq κ_{m a x} = \frac{1}{ρ_{m i n}}

(16)

Recall that the radius of curvature is the radius absolute value of the circle tangent to the curve at the concerned point; this circle is called an osculating circle to the curve at that point. This measurement indicates the bending degree: the higher the radius of curvature, the more the path approximates a straight line and vice versa.

As shown in Section 2.2, as the weight of a control point increases, the curve comes closer and if the weight is of sufficient importance, the curve will follow closely the considered control point. We note that the weight parameter is inversely proportional to the radius of curvature. In fact, as shown in Figure 10, the gradual increase in the value of the weight of the control point P_i from 0.25 to 5 led to the progressive diminution of the radius of curvature of Q_j, the closest curve point to P_i.

Figure 10.

Variation weight vs. radius of curvature

Being the inverse of the radius of curvature, the value of the curvature increases with an increase in weight. Consider the example of the NURBS curve approximation of seven control points (Figure 1): the change in the weight value of $P 2$ from 1 to 30 generated the increase of $| κ |$ of the associated curve point (Figure 11 (a)). Consequently, the standard deviation of curvatures increases with increasing the $P 2$ weight value (Figure 11 (b)) and vice versa.

Figure 11.

(a) Curvature profiles of the NURBS curves of Figure 1. (b) Associated variation of curvature standard deviation with P2 weight's varying.

Therefore, to readjust the generated trajectory C in response to the constraint (16), the algorithm consists, firstly, in detecting the set of curve points $T^{'}$ that do not conform to the curvature constraint:

T^{'} = {t^{'}_{j}, j = 1‥ q | | κ_{{t^{'}}_{j}} | > κ_{m a x}}

(17)

The following procedure involves identifying for each component of $T^{'}$ its closest control point. These points are the second set of critical points $T 2$ . As for $T 1$ , $T 2$ is defined using the Euclidean distances.

Figure 12 (a) illustrates the NURBS curves before (blue) and after (pink) applying the procedure of curvature correction. The blue curve is a $4^{t h}$ NURBS curve approximation of 15 control points with weights equal to 1. Its associated distribution of curvatures is represented in Figure 12 (b). The two red dashed lines represent the curvature constraint ( $| κ_{m a x} | = 0.2$ ). We note that for this variation of curvatures, there exist two inflection points (marked in black) that violate the curvature constraint.

Figure 12.

(a) NURBS curves before (blue) and after (pink curve) the process of curvature correction (degree = 4, number of control points = 15). (b) Associated curvature profiles (before (blue) and after (pink curve) the process of curvature correction).

For the initial curve, the two curve points that violate the curvature constraint are marked in red. To refine this path and make it eligible, the algorithm acts upon the weights of four control points (P₅, P₆, $P_{10}$ and $P_{11}$ ). The resulting curve (pink) has a bounded curvature as shown in Figure 12(b). The final weights vector associated with the set of control points is $W = (1,1,1,1,0.5,0.8,1,1,1,0.1,0.1,1,1,1,1)$ .

For the rest of our approach, after validating the collision avoidance constraint, the algorithm checks the validity of the curvature constraint by calculating the set $T 2$ . Thus, if the set is an empty one, the generated path C is itself the optimal solution $C_{o p t}$ . Otherwise, two sub-cases are possible: the first is when $T 1$ does not intersect $T 2$ , then the algorithm proceeds by reducing the weights of the components of $T 2$ in order to reduce, therefore, the values of curvatures of corresponding NURBS' curve points. In this case, it is worth noting that this reduction should not lead to the generation of negative weights. In fact, this constraint ensures the the convex hull property of NURBS curves [15]. Therefore, after the weights' decreasing process, the curvature constraint may still be not respected. If this is the case, we propose to locally displace the concerned control points using the direct search method proposed by Hooke and Jeeves [24]. Likewise, if $T 1$ intersects $T 2$ (a second possible sub-case), the solution consists in locally displacing all control points that lie in $T 1 \cap T 2$ using the same method. The fitness function used to perform the technique of Hooke and Jeeves is the curvature standard deviation. Thus, a control point will be moved in the direction that minimizes this function. This algorithm operates iteratively until the satisfaction of the problem constraints (without exceeding a maximum number of iterations fixed in advance).

5. Simulation Results

In this section, we report on extensive experiments to evaluate the effectiveness and performance of the proposed approach for global curvature-constrained path planning using NURBS curves modelling. We considered simulations under various conditions related to the configuration's space size; the number, location and size of obstacles; the start and target positions and the robot's parameters (diameter and minimum radius of curvature). Values of used input parameters are shown in Table 1, whereas Table 2 gives the experimental results for all tested configurations.

Table 1.

Parameters used for robot path generation

Parameters	Map I-1	Map I-2	Map II	Map III (rooms)	Map IV (dense)	Map V (spiral)	Map VI (back and forth)
Space Size	70*70	70*70	80*100	120*140	100*100	100*120	100*100
Start Position	(6, 8)	(50, 19)	(8, 33)	(90, 23)	(36, 8)	(78, 102)	(87, 89)
Target Position	(66, 63)	(66, 63)	(71, 51)	(52, 115)	(17, 73)	(39, 124)	(15, 12)
Robot Diameter	1	4	3	2	2	2	4
Minimum Radius of Curvature	1	6	2	2.5	0.5	1	2

Table 2.

Experimental results

Parameters	Map I-1	Map I-2	Map II	Map III (rooms)	Map IV (dense)	Map V (spiral)	Map VI (back and forth)
Number of control points	13	7	13	16	11	23	19
Max curvature value	0.98	0.15	0.17	0.39	1.99	0.96	0.35
Standard deviation of curvatures	0.17	0.11	0.06	0.09	0.34	0.18	0.08
Path length	111.23	62.29	161.96	142.72	79.11	338.24	267.18

In Map I, after having stored the geometrical representation of the environment and after having calculated the corresponding extended skeleton (which is modelled to obtain a graph representation of all feasible paths on which a process of graph reduction is applied, keeping only those sectors that have the minimum width allowing the robot to pass through the corridor formed by the two vertices i and j), then, with the help of the Bellman Ford algorithm, a single-source shortest path, in the resulting graph, is determined. To ensure the smoothness property of the selected path, a $3 r d$ degree NURBS curve is calculated approximating 13 control points $P 1, P 2,…, P 13$ from S to T (red dots in Figure 13). The initial weights of all the coefficients are equal to one. Figure 13 shows the initial generated curve (blue curve) and its control polygon (the computed polyline path (green line segments)). As shown, this path is initially collision free. Up to this point, the algorithm ensures that the generated path is the shortest (in the generated graph) collision-free path. For the rest, it remains to be checked that it has an allowable curvature on each curve point.

Figure 13.

Initial generated path (blue curve)

The corresponding distribution of curvatures is presented in Figure 14 (b). As the constraint of minimum radius of the curvature of the robot was set at one, therefore the path must have the value of one as the maximum allowable value of curvature. This constraint was not ensured, since the corresponding curvature variations have an inflection point (the black dot in Figure 14 (b)), where the absolute curvature value exceeds the permissible value. The algorithm of curvature correction acted on the initial curve by decreasing the weight of the 4th control point and displacing P12 from the position (65,59) to (63,61).

Figure 14.

Simulation results under MapI-1: (a) generated path before the process of curvature correction, (b) associated curvature profile (σ(curvatures)=0.20), (c) generated path after the process of curvature correction, where the associated weights vector is W=1,1,1,0.8,1,1,1,1,1,1,1,1,1 and (d) associated curvature profile (σ(curvatures)=0.17)

To prove the adaptivity of our approach, Figure 15 shows a second experiment performed in the same environment as the first one and with the same target position. The start position, robot diameter and minimum radius of curvature have been changed. As illustrated, the proposed algorithm succeed in finding the desired path.

Figure 15.

Simulation results under MapI-2: (a) generated path before the process of curvature correction, (b) associated curvature profile (σ(curvatures)=0.19), (c) generated path after the process of curvature correction, where the associated weights vector is W=(1,1,0.8,1,1,0.7,1), and (d) associated curvature profile (σ(curvatures)=0.11)

In Map II, the proposed method has allowed us to provide, in the first step, a smooth and the shortest free-collision path (Figure 16 (a)). Then, in second one, the solution was refined by locally modifying the previously generated path (displacing the two control points, P7 and P10) so that it has a distribution of curvatures that respects the limit value allowable by the robot (Figure 16 (b)), which gives an optimal path from start to target points in the configuration space. Thus, the adopted path is modelled by a NURBS curve approximating 13 control points from S to T.

Figure 16.

Simulation results under MapII: (a) generated path before the process of curvature correction (σ(curvatures)=0.16), (b) generated path after the process of curvature correction (σ(curvatures)=0.06) and (c) curvature profiles before (green) and after (blue) the process of curvature correction; the dotted red lines represent the curvature limit constraint

Figure 16 (c) shows the curvature profiles before (green) and after (blue) the curvature correction procedure. The maximum absolute value of curvature equals 0.17, respecting the maximum allowable value (0.5) and the standard deviation of curvatures equal to 0.06. This low value indicates that the data points tend to be very close to the mean, proving the homogeneity of the distribution of curvatures and, consequently, the smoothness criterion. Figure 17 shows the results obtained under four further different maps. All computed paths were modelled by NURBS curves, which ensures the smoothness and the curvature limit.

Figure 17.

Simulation results under various maps: (a) back and forth, (b) dense, (c) rooms and (d) square spiral

6. Discussion

In this research, a novel path-planning algorithm was established and investigated using extensive simulation studies. Using this method, the robot seeks the best path to navigate safely with respect to its minimum radius of curvature.

To search for the shortest and most secure path, we applied the Bellman algorithm to the graph constructed from skeletonization of an obstacle-free space, which guarantees, therefore, a higher degree of security (obstacle avoidance), as the path to be calculated is always closest to the middle of corridors in which the robot moves. In addition, this method guarantees a shorter path length than RRT-based approaches, which produce suboptimal solutions due to the random sampling principle [10]. Compared with the algorithms described in [25, 26], our method not only ensures the smoothness property, which has been proven important in the process of robot navigation, but also respects the limit of allowable curvature. As for the methods [3, 7, 8, 9, 10, 11, 12], the proposed method is distinguished by the use of modelling with NURBS curves, which are much more flexible than other smoothing techniques, coupled with the fact that NURBS algorithms are fast and numerically stable. Moreover, our method uses varied values for the weight parameter, unlike many existing path planning methods that use NURBS curves, such as [13, 27], where all weights of control points are set at one. In [14], the weight factors associated with the nodes of the S-Roadmap are equal to three and, in this manner, it is possible to control the distance of the robot from the nodes. Consequently, by fine-turning these weights, either closer or more distant proximities can be achieved. Thereby, NURBS curves are used only in the smoothing process of the generated paths and no accurate parameterization of the weight parameter has been provided.

The major contributions of this paper are the following. First, the adaptivity of the proposed path-planning algorithm, which was able to drive the robot autonomously and to seek the best possible path to reach the target, even in complicated scenes. Indeed, it not only provides the near-optimal path in terms of length and obstacle avoidance but also respects the curvature constraint relating to the robot's characteristics and irrespective of the number, size and location of obstacles. Second, NURBS curves are not used only as a means of smoothing but they are also involved in meeting the system's constraints via a suitable parameterization of the weights of control points, which allows greater benefit to be derived from the influence and the geometrical effect of this parameter, which has not been exploited well in previous works. In addition, the control points' locations were used to control the curve shape locally, in order to satisfy the problem requirements.

7. Conclusion

In this study, we present a global curvature-constrained path planning method based on graph theory and NURBS curves. This method provides a deterministic approach for generating paths with a continuous curvature and a continuous derivative of curvature; hence, smooth paths are determined. It has been shown that the proposed algorithm is capable of efficiently finding the shortest, and a more secure, existing path, whatever the complexity of the configuration space. Nevertheless, the environment in which the robot moved was static and the information of the environment was known a priori. Future work will investigate the problem of path planning in an unknown dynamic environment. Furthermore, it will be interesting to adopt our algorithms in real-world applications.

Footnotes

8. Acknowledgements

The authors are grateful to the Guest Editor, Dr. Luis Merino, and the anonymous reviewers for their constructive comments and helpful suggestions that greatly improved the quality of this article.

References

LaValle

S.M.

: Planning algorithms. Cambridge University Press; 2006. 924 p.

Latombe

J.C.

: Robot motion planning. The Kluwer international series in engineering and computer science, Kluwer Academic Publishers; 1991. 651 p.

Fraichard

Scheuer

: From Reeds and Shepp's to continuous-curvature paths. IEEE Transactions on Robotics, 20; 2004. p. 1025–1035.

Dubins

L.E.

: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79; 1957. p. 497–516.

Meek

D.S.

Walton

D.J.

: An arc spline approximation to a clothoid. J. Comput. Appl. Math, 170; 2004. p. 59–77.

Montes

Herraez

Armesto

Tornero

: Realtime clothoid approximation by Rational Bezier curves. IEEE International Conference on Robotics and Automation ICRA; 2008. p. 2246–2251.

Meek

D.S.

Walton

D.J.

: A smooth, obstacle-avoiding curve. Computers and Graphics, 30; 2006. p. 581–587.

Y.J.

Liu

J.S.

: Collision-free curvature-bounded smooth path planning using composite Bezier curve based on Voronoi diagram. IEEE CIRA; 2009. p. 463–468.

Wei

J.H.

Liu

J.S.

: Generating minimax-curvature and shorter β3-spline path using multi-objective variable-length genetic algorithm. IEEE ICNSC; 2010. p. 319–324.

10.

Yang

Moon

Yoo

Kang

Lett

D.N.

Kim

H.B.

Joo

: Spline-based RRT path planner for non-holonomic robots. Journal of Intelligent and Robotic Systems, 73; 2014. p. 763–782.

11.

Maekawa

Noda

Tamura

Ozaki

Machida

K.I.

: Curvature continuous path generation for autonomous vehicle using B-spline curves. Computer-Aided Design, 42; 2010. p. 350–359.

12.

Lobaton

E.J.

Zhang

Patil

Alterovitz

: Planning curvature-constrained paths to multiple goals using circle sampling. IEEE ICRA; 2011. p. 1463–1469.

13.

Singh

A.K.

Aggarwal

Vashisht

Siddavatam

: Robot motion planning in a dynamic environment using offset Non-Uniform Rational B-Splines (NURBS). IEEE ICIT; 2011. p. 312–317.

14.

Xidias

E.K.

Aspragathos

N.A.

: Continuous curvature constrained shortest path for a car-like robot using S-Roadmaps. IEEE MED; 2013. p. 13–18.

15.

Piegl

L.A.

: On NURBS: a survey. IEEE Computer Graphics and Applications, 11; 1991. p. 55–71.

16.

Piegl

L.A.

Tiller

: The NURBS book (2. ed.). Springer, Monographs in Visual Communication; 1997. 646 p.

17.

Marthon

Bruel

Biguet

: Squelettisation par calcul d'une fonction discriminante sur un voisin-age de 8 points. 2ème Congrès AFCET-IRIA, Reconnaissance des formes et intelligence artificielle; 1979. p. 107–114.

18.

Naouai

Hamouda

Jalel

Weber

: NURBS skeleton: a new shape representation scheme using skeletonization and NURBS curves modeling. CIARP, Springer, Lecture Notes in Computer Science, 7042; 2011. p. 197–205.

19.

Goldberg

A.V.

Radzik

: A heuristic improvement of the Bellman-Ford algorithm. Applied Mathematics Letters, 6; 1993. p. 3–6.

20.

Jalel

Marthon

Hamouda

: Optimum path planning for mobile robots in static environments using graph modelling and NURBS curves. ISPRA, WSEAS; 2013. p. 216–221.

21.

Jalel

Naouai

Hamouda

Jebabli

: NURBS parameterization: a new method of parameterization using the correlation relationship between nodes. MCPR, Springer, Lecture Notes in Computer Science, 7329; 2012. p. 216–225.

22.

Piegl

L.A.

Rajab

Smarodzinava

Valavanis

K.P.

: Using a biarc filter to compute curvature extremes of NURBS curves. The NURBS book (2. ed.), Engineering with Computers, 25; 2009. p. 379–387.

23.

Rogers

D.F.

: An introduction to NURBS: with historical perspective. Morgan Kaufmann; 2000. 342 p.

24.

Hooke

Jeeves

T.A.

: “Direct search” solution of numerical and statistical problems. Journal of the Association for Computing Machinery (ACM), 8; 1961. p. 212–229.

25.

Tuncer

Yildirim

: Dynamic path planning of mobile robots with improved genetic algorithm. Computers and Electrical Engineering, 38; 2012. p. 1564–1572.

26.

Qiu

Chen

: A hybrid two-dimensional path planning model based on frothing construction algorithm and local fast marching method. Computers and Electrical Engineering, 39; 2013. p. 475–487.

27.

Elbanhawi

Simic

Jazar

R.N.

: Continuous path smoothing for car-like robots using B-Spline Curves. Journal of Intelligent and Robotic Systems, 80; 2015. p.23–56.