Sage Journals: Discover world-class research

Abstract

The trajectory planning and obstacle avoidance of serial robot is an important area of research and efficient optimization algorithms are needed. This article proposes an intermediate point obstacle avoidance algorithm to ensure smooth trajectory and efficient movement during the obstacle avoidance process. Using the intermediate point obstacle avoidance algorithm, the robotic arm can steer obstacle around with the minimum joint space variations and the shortest end motion trajectory. We also design a novel collision detection strategy and fitness evaluation function based on genetic algorithm to optimize the intermediate point parameters. In order to evaluate the performance of the intermediate point obstacle avoidance algorithm, we have conducted three typical experiments: single obstacle, multiple obstacles, and no obstacle. The experimental results demonstrate that the proposed method can not only effectively realize the obstacle avoidance, but also efficiently improve the movement performance of the robotic arm.

Keywords

Intermediate point obstacle avoidance trajectory planning collision detection strategy genetic algorithm

Introduction

The past decades have witnessed the extensive applications of serial robot in industrial production, space exploration, and daily life. Nowadays, with different end effectors, serial robot can realize various tasks such as packaging, palletizing, polishing, painting, and medical treatment. In general case, the working environment of serial robot is artificially designed, which means that there are also many assignments that cannot be scheduled in advance. In this condition, the operator uses the remote controller to control the end of manipulator directly. But there are many defects, for example, (1) in order to avoid interference and ensure safety, the movement of manipulator is slow; (2) through monitoring devices, the operator has a limited view of environment; and (3) the operator is prone to fatigue after a period of work (during the working time). Therefore, the trajectory planning of manipulator is a key problem for auxiliary control.

This field has attracted many researchers. MS Huang et al.¹ used real-coded genetic algorithm (RGA) and proposed a novel minimum-energy point-to-point (PTP) trajectory planning method for a motor-toggle servomechanism. H Liu et al.² proposed a high smooth trajectory planning method to improve the practical performance of the manipulator with multi-degree splines in Cartesian space and multi-degree B splines in joint space. YT Zhao et al.³ used quaternion interpolation method to solve the multiple solution problems. AT Hasan et al.⁴ developed a method using artificial neural network (ANN) to pass the serial manipulator through singularity configurations. A Gasparetto and V Zanotto⁵ presented a smooth trajectory method with the constraint of robot motion, expressed as upper bounds on the absolute values of velocity, acceleration, and jerk. These studies mainly focus on the trajectory generation method of the manipulator.

In recent years, many scholars have also studied the obstacle avoidance algorithm for serial robot. H Dong and Z Du⁶ used the workspace density of the manipulator to calculate collision-free paths in complex environments with multiple obstacles. And he demonstrated the effectiveness of the method using simulation results. M Ismail et al.⁷ proposed a dynamic path planning algorithm and applied it to a hybrid cable–serial manipulator to find the shortest and the fastest path while ensuring bounded tensions in the actuator cables. RS Novin et al.⁸ focused on the optimal motion planning of redundant planar serial robot, by avoiding obstacles within its workspace. He presented a synergy-based algorithm between convex optimization, disjunctive programming, and receding horizon to realize the global optimum solution and low computational time. MP Mann et al.⁹ put forward a novel type of serial robot with minimal actuation, through its unique modular structure design, to get pass a confined space and reach the target. In addition, some other methods, such as the artificial potential field,¹⁰ rapidly exploring random tree (RRT),^11,12 and probabilistic road map (PRM)¹³ have also been used in the obstacle avoidance trajectory planning of the manipulator. These methods transform the Cartesian coordinate space into the configuration space to solve the three-dimensional optimization problems. However, there is little research on the connection between kinematic performance, dynamic performance, and obstacle avoidance.

The trajectory planning of the manipulator should be based on safety, stability, and energy conservation.¹⁴ We transform these aspects into performance indicators, that is, the obstacle avoidance of the manipulator in the course of movement, the minimum joint space variations, and the shortest end motion trajectory. The above indicators are difficult to achieve simultaneously, and our research focuses on optimizing these indicators.

The major contributions of this article can be summarized as follows:

We present an intermediate point obstacle avoidance (IPOA) algorithm to steer the robotic arm around obstacle with the minimum joint space variations and the shortest end motion trajectory, which means that the robotic arm can work in a state of safety, stability, and energy conservation. Through the proposed algorithm, it can be ensured the smooth trajectory and efficient movement during the obstacle avoidance.

In IPOA algorithm, a novel collision detection strategy is put forward to prevent the robotic arm from being disabled. Through matrix transformation method, the mathematical model of connecting rod line segment will be represented. In this way, the collision problem of the manipulator can be transformed into the distance changes between the obstacle point and the connecting rod.

We also design a new fitness evaluation function based on genetic algorithm to optimize the intermediate point parameters. The abundant experimental results have demonstrated the effectiveness of our method.

In the following chapters, the IPOA algorithm is proposed to meet the requirement of obstacle avoidance trajectory planning of serial robot. First, the mathematical model of the serial robot is established in section “Model simplification.” Then, in section “IPOA algorithm,” we have described the IPOA algorithm in detail, including the motion trajectory planning and the collision detection strategy. In order to obtain the intermediate point, we designed the fitness function by genetic algorithm to optimize the target in section “Gene optimization scheme.” Experiments are conducted under different situations to verify the safety and reliability of IPOA algorithm in section “Experimental verification.” Finally, section “Conclusion” extends the algorithm and presents the conclusion.

Model simplification

We are committed to working on a universal robotic arm obstacle avoidance algorithm. So in this article we have chosen a common ideal robotic arm configuration, which is a six-degree-of-freedom serial robot. The robotic arm in this configuration consists of six rotating joints, including two shoulder joints, one elbow joint, and three wrist joints. The second and third joint axes are parallel, and the axes of the fourth, fifth, and sixth joints are perpendicular to each other and intersect at one point. If the joint offset is assumed to be zero, this configuration is identical to most robotic arm structures in the market.

To study obstacle avoidance strategy, a simplified mathematical description of the manipulator model and obstacle model is required. Through Denavit–Hartenberg (D-H) method, we build a model of the robotic arm, the mechanical structure of which is shown in Figure 1(a), and the schematic diagram of the connecting rod can be found in Figure 1(b). The D-H parameters can be found in Table 1. In theory, our algorithm can be extended to any other configurations of the serial robot.

Figure 1.

(a) The mechanical structure of the robotic arm and (b) the schematic diagram of the connecting rod.

Table 1.

D-H parameters of the robotic arm.

	$θ$	$a$	$α$
Link1	$θ_{1}$	0	90
Link2	$θ_{2}$	$L_{1}$	0
Link3	$θ_{3}$	$L_{2}$	0
Link4	$θ_{4}$	0	90
Link5	$θ_{5}$	0	90
Link6	$θ_{6}$	0	0

D-H: Denavit–Hartenberg.

While simplifying the obstacle model, we add the robotic arm’s radial radius to the obstacle radius. In this way, the interference calculation between the robotic arm’s connecting rod and obstacle can be transformed into the distance relationship between the line segment and the obstacle point. Although this method wastes some actual workspace of robotic arm, the advantage of reliability and simplicity makes this method widely applicable in the field of robot obstacle avoidance.¹⁵

IPOA algorithm

Principle of our IPOA algorithm

In this article, we proposed an IPOA algorithm to steer the robotic arm around the obstacle. At the same time, it is ensured the minimum joint space variations and the shortest motion trajectory of end effector. First, to avoid obstacle, an intermediate point is needed to be set. The parameter of the intermediate point is optimized by genetic algorithm. Then, the motion trajectory between the starting point and the intermediate point or the intermediate point and the target point is described through quintic polynomial segment. Finally, an ideal motion trajectory with no collision is planned. For single obstacle avoidance, the schematic diagram is shown in Figure 2. The solid line in the figure represents the trajectory when the intermediate point is set, and the dotted line represents the trajectory where the robotic arm will collide with the obstacle.

Figure 2.

The schematic diagram of single obstacle avoidance.

Moreover, the IPOA algorithm has the feature of wide expansibility. In the case of multiple obstacles, after decomposing trajectory and connecting the intermediate point in series, the robotic arm can avoid obstacles in very complex circumstances. For multiple obstacle avoidance, the schematic diagram is shown in Figure 3

Figure 3.

The schematic diagram of multiple obstacle avoidance.

For multiple obstacle avoidance, if there are N obstacles, our method has to set N intermediate points. It is the best option to balance between effectiveness and efficiency. The comparison experiment that will be presented in section “Comparison experiment on the number of intermediate points” has also proved this point.

Motion trajectory planning

The motion trajectory planning of the robotic arm usually uses the high spline curve to keep it smooth and continuous. For joint space trajectory planning, cubic polynomial, quintic polynomial, parabolic curve, and B-spline curve can be used. Since the quintic polynomial has a feature of simple calculation, there is no mutation in the velocity and acceleration curve. In this article, the quintic polynomial¹⁶ trajectory planning in the joint space is adopted.

Whether the track is between the starting point and the intermediate point or the intermediate point and the target point, we all use this trajectory planning method

θ_{t} = c_{0} + c_{1} t + c_{2} t^{2} + c_{3} t^{3} + c_{4} t^{4} + c_{5} t^{5}

(1)

Through quintic polynomial, a smooth and continuous trajectory for position, velocity, and acceleration of each joint is planned. By calculating boundary restrictions, the coefficients of the polynomial can be solved. Assume that at zero moment the joint angle is $θ_{0}$ and at the moment $t_{f}$ the joint angle is $θ_{f}$ , as shown in equation (2)

{\begin{matrix} θ (0) = θ_{0} = c_{0} \\ θ (t_{f}) = θ_{f} = c_{0} + c_{1} t_{f} + c_{2} {t_{f}}^{2} + c_{3} {t_{f}}^{3} + c_{4} {t_{f}}^{4} + c_{5} {t_{f}}^{5} \\ \overset{\cdot}{θ} (0) = {\overset{\cdot}{θ}}_{0} = c_{1} \\ \overset{\cdot}{θ} (t_{f}) = {\overset{\cdot}{θ}}_{f} = c_{1} + 2 c_{2} t_{f} + 3 c_{3} {t_{f}}^{2} + 4 c_{4} {t_{f}}^{3} + 5 c_{5} {t_{f}}^{4} \\ \overset{\cdot\cdot}{θ} (0) = {\overset{\cdot\cdot}{θ}}_{0} = 2 c_{2} \\ \overset{\cdot\cdot}{θ} (t_{f}) = {\overset{\cdot\cdot}{θ}}_{f} = 2 c_{2} + 6 c_{3} t_{f} + 12 c_{4} {t_{f}}^{2} + 20 c_{5} {t_{f}}^{3} \end{matrix}

(2)

After the calculation, the result is

{\begin{matrix} c_{0} = θ_{0} \\ c_{1} = {\overset{\cdot}{θ}}_{0} \\ c_{2} = \frac{{\overset{\cdot\cdot}{θ}}_{0}}{2} \\ c_{3} = \frac{20 (θ_{f} - θ_{0}) - (8 {\overset{\cdot}{θ}}_{f} + 12 {\overset{\cdot}{θ}}_{0}) t_{f} - (3 {\overset{\cdot\cdot}{θ}}_{0} - {\overset{\cdot\cdot}{θ}}_{f}) {t_{f}}^{2}}{2 {t_{f}}^{3}} \\ c_{4} = \frac{30 (θ_{0} - θ_{f}) + (16 {\overset{\cdot}{θ}}_{0} + 14 {\overset{\cdot}{θ}}_{f}) t_{f} + (3 {\overset{\cdot\cdot}{θ}}_{0} - 2 {\overset{\cdot\cdot}{θ}}_{f}) {t_{f}}^{2}}{2 {t_{f}}^{4}} \\ c_{5} = \frac{12 (θ_{f} - θ_{0}) - (6 {\overset{\cdot}{θ}}_{f} + 6 {\overset{\cdot}{θ}}_{0}) t_{f} - ({\overset{\cdot\cdot}{θ}}_{0} - {\overset{\cdot\cdot}{θ}}_{f}) {t_{f}}^{2}}{2 {t_{f}}^{5}} \end{matrix}

(3)

Normally, the velocity and acceleration initially and at the termination is 0, that is, ${\overset{\cdot}{θ}}_{0} = {\overset{\cdot}{θ}}_{f} = 0$ and ${\overset{\cdot\cdot}{θ}}_{0} = {\overset{\cdot\cdot}{θ}}_{f} = 0$ . In this way, the undetermined coefficients can be solved.

This section focuses on the generation method of point-to-point motion trajectory planning. In the following sections, we will use the quintic polynomial as the basis element to plan the movement of the manipulator in the Cartesian coordinate space.

Collision detection strategy

In the past, the collision detection strategy of robotic arm was mostly to transfer obstacles from the Cartesian coordinate space to the configuration space (C space). T Lozano-Perez^17,18 first proposed the free space method based on C space to avoid obstacle. After that, other scholars have also done a lot of research on this aspect. The method transforms the obstacle avoidance from the high-dimensional space into low-dimensional space, and uses the heuristic search algorithm to find the motion path of the manipulator in the free space. Although it can realize collision-free path planning of manipulators, the method of mapping obstacles into the C space is complicated and the expression is not intuitive enough.¹⁹

In our research, we provide a novel collision detection strategy in our proposed algorithm to prevent the robotic arm from being disabled. The method directly determines whether the robotic arm and obstacle interfere in the Cartesian coordinate space. The specific realization is that under the condition of model simplification, the position and attitude matrices of the joints are, respectively, expressed, and the pose of the connecting rod is expressed. Interference or collision is judged by the distance between the obstacle point and the straight line segment of the connecting rod.

First, the coordinate matrix representation of each joint is obtained. Through matrix transformation method, the mathematical model of the connecting rod line segment will be represented. For robotic arm discussed in this article

T_{a} = E * rotz (θ_{1}) * T_{m}

(4)

T_{b} = T_{a} * roty (90 \circ) * rotz (90 \circ) * rotz (θ_{2})

(5)

T_{c} = T_{b} * transl (l_{1}, 0, 0) * rotz (θ_{3})

(6)

T_{d} = T_{c} * transl (l_{2}, 0, 0) * rotx (180 \circ) * rotz (θ_{4})

(7)

where $E$ is a $4 \times 4$ dimensional unit matrix and $T_{m} = [\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}]$ represents a modification matrix. Since the latter three joint rotation angles only affect the attitude change of end effector, the position of the connecting rod in the Cartesian space is not affected. So we do not list it in the discussion.

Then, it is determined whether the distance between the connecting rod segment and the obstacle point exceeds the obstacle expansion radius. ${\vec{l}}_{1}$ and ${\vec{l}}_{2}$ represent the two connecting rods of the manipulator

{\vec{l}}_{1} = [T_{b} (1, 4) - T_{c} (1, 4), T_{b} (2, 4) - T_{c} (2, 4), T_{b} (3, 4) - T_{c} (3, 4)]

(8)

{\vec{l}}_{2} = [T_{c} (1, 4) - T_{d} (1, 4), T_{c} (2, 4) - T_{d} (2, 4), T_{c} (3, 4) - T_{d} (3, 4)]

(9)

R = R_{ob} + R_{link}

(10)

where $R$ represents the obstacle expansion radius, and $R_{ob}$ and $R_{link}$ represent the obstacle radius and the connecting rod’s radial radius, respectively.

Finally, it is discussed whether the intermediate point can be used to avoid obstacles both in front and back motion trajectories. Set the obstacle point $P = [p_{x}, p_{y}, p_{z}]$ and find the vector ${\vec{p}}_{l}$ of the obstacle point to the connecting rod point. In equation (11), $\vec{l}$ represents the vector of the straight line segment of the connecting rod and ${\vec{p}}_{l}$ is the vector connecting the obstacle point to any point in the straight line of the connecting rod

{\vec{v}}_{1} = {\vec{p}}_{l} \times {\vec{l}}_{1} = | {\vec{p}}_{l} | | {\vec{l}}_{1} | \sin θ_{1}, {\vec{v}}_{2} = {\vec{p}}_{l} \times {\vec{l}}_{2} = | {\vec{p}}_{l} | | {\vec{l}}_{2} | \sin θ_{2}

(11)

d_{1} = \frac{‖ {\vec{v}}_{1} ‖}{‖ {\vec{l}}_{1} ‖}, d_{2} = \frac{‖ {\vec{v}}_{2} ‖}{‖ {\vec{l}}_{2} ‖}

(12)

where $d_{1}$ and $d_{2}$ represent the distance of the two connecting rods to the obstacle point. When $d_{1} \geq R$ and $d_{2} \geq R$ , the robotic arm will not collide with the obstacle.

Compared with the previous research on collision detection, such as the method of determining the interference of obstacle and robotic arm in two vertical cross-plane projections,²⁰ or other ways of converting the Cartesian coordinate space into robot configuration space,^21,22 our method does not require the projection or transformation of obstacle, the calculation is simpler, and the expression is more intuitive. So it can be found that our method is far more simple and effective.

Through our collision detection strategy, the robot model is simplified, so that the complex space problem can be transformed into a simple distance problem. Using the distance between the obstacle point and the connecting rod, it can be determined whether the robotic arm is conflicted with obstacle.

Gene optimization scheme

In our IPOA algorithm, we need to choose a method to optimize the intermediate point parameters. There are many kinds of optimization methods to deal with a particular form of problem. The situation is quite different, depending on the objective function (linear or non-linear, mono- or multi-objective) and the nature of constraints. Here several commonly used optimization algorithms are as follows: the penalty function method,²³ relax penalty method,²⁴ particle swarm optimization,²⁵ and evolutionary algorithms.²⁶ In our case, we choose to use the genetic algorithm^27–30 to optimize the intermediate point. It has proved to be robust in highly non-linear situation. Through gene iterations, it is able to solve complex optimization problems in a reasonable computational time.

Genetic algorithm is not affected by specific areas of the problem, and it has a strong robustness to different types of problems. For multimodal problem, genetic algorithm will not stuck into local optimal solution, and it is easy to achieve parallelizing. Based on the above advantages, we choose genetic algorithm to optimize the intermediate point parameters. In addition, some other scholars have also adopted genetic algorithm to optimize the manipulator trajectory planning.^31,32

It is worth noting that the intermediate point solved by genetic algorithm is not necessarily the optimal solution. But it is one of many solutions to the domain near the optimal solution under the condition of constraints. We can further improve the optimization performance by increasing population size and changing the crossover or mutation factors. However, during the trajectory planning of the robotic arm, it is of little significance to obtain the only optimal solution at the expense of calculation time.

Genetic algorithm

Genetic algorithms begin with an initial population of potential solutions, and the chromosome characteristics are expressed through genetic coding such as binary coding. By simulating the natural evolutionary process, survival of the fittest, a better approximate solution is produced. According to the fitness function, the individual is selected and the new population is formed through the process of crossover and mutation. After iterations, the best solution of the problem is obtained by decoding the optimal individual. The theoretical basis and formula of genetic algorithm are not repeated in this article. We invoke the genetic algorithm and direct search (GADS) toolbox to implement its function.

This article focuses on the multi-objective optimization problem of the six robotic joint variables. The general mathematical model of multi-objective optimization problem can be described as shown in equation (13)

{\begin{matrix} V - min f (x) = {[f_{1} (x), f_{2} (x), \dots, f_{n} (x)]}^{T} \\ s . t . x \in X \\ X \subseteq R^{m} \end{matrix}

(13)

where $V - min$ denotes vector minimization, that is, the sub-objective functions of the objective function $f (x)$ are minimized as much as possible, and $X \subseteq R^{m}$ represents the constraint set of the optimization model. If the weight factor $ω_{i}$ is given to each sub-objective function $f (x_{i})$ , then the sum of linear weighting $u$ can be expressed in equation (14)

u = \sum_{i = 1}^{n} ω_{i} * f_{i} (x)

(14)

The ultimate optimization objective is the six joint angles at the intermediate point, which have the same degree of importance, so each of the weight factors $ω_{i} = 1$ . We use MATLAB genetic algorithm toolbox to optimize the intermediate point. Set the number of variables to 6 and add lower and upper bounds to the constraint. The population size is 200 and the selection function is Roulette. Set the crossover fraction to 0.95 and other factors with the default values.

Design of fitness function

In practical application, to realize efficient work, the robotic arm should avoid unnecessary repetitive motions. In the case of kinematic considerations only, the trajectory planning should focus on the variations of each joint angle and the length of end effector motion trajectory.

In GADS toolbox, the goal of genetic evolution is to minimize the fitness function. Using the interpolation point method, the trajectory of the quintic polynomial can be divided into several points. The joint variations $f_{Q}$ and the trajectory length $f_{L}$ can be calculated through interpolation point. And our objective function $η_{1} f_{Q} + η_{2} f_{L}$ is a problem of seeking the minimum value. But when we place the objective function on the denominator, we have to add a negative sign to turn it to a minimum problem. In this article, our fitness evaluation function is put forward in equation (15)

f_{G} = - \frac{f_{OB}}{η_{1} f_{Q} + η_{2} f_{L}}

(15)

with $f_{G}$ being the fitness evaluation function of genetic algorithm

f_{Q} = \sum_{i = 1}^{n} \sum_{j = 1}^{6} (| q_{i + 1, j} - q_{i, j} |)

(16)

with $f_{Q}$ being the sum of the variations of each joint during the trajectory interpolation

f_{L} = \sum_{i = 1}^{n} \sqrt{{(p_{i, x} - p_{x})}^{2} + {(p_{i, y} - p_{y})}^{2} + {(p_{i, z} - p_{z})}^{2}}

(17)

with $f_{L}$ being the sum of the distance length from the end effector to the intermediate point during interpolation; this value may reflect the length of the motion trajectory.

$f_{OB}$ represents collision detection evaluation, which is a binary variable. When $f_{OB} = 1$ , the robotic arm does not collide with the obstacle, and on the contrary $f_{OB} = 0$ . If $f_{OB} = 0$ , then $f_{G} = 0$ . Else if $f_{OB} = 1$ , then $f_{G} < 0$ . We design the fitness function in this way so it can have an optimization effect.

The weight factors are $η_{1} = 1$ and $η_{2} = 0.001$ , and this depends on the magnitude of $f_{Q}$ and $f_{L}$ .

Assume that if we design the fitness function as $f_{G} = f_{OB} (η_{1} f_{Q} + η_{2} f_{L})$ , which is a problem of finding the minimum value, but this formula does not work. When $f_{OB} = 0$ , $f_{G}$ will get the minimum value equal to zero, and the other fitness function values will be greater than zero, so there is no effect of individual optimization and no evolution of populations.

The pseudo code for IPOA algorithm is shown as follows:

Algorithm. Optimization of the intermediate point of trajectory using genetic algorithm.
1	Initialize robot joint and link properties using MATLAB robotic toolbox
2	Input the initial angle $q_{0}$ , target angle $q_{f}$ , and $n = 50$
3	Set interpolation points from the initial point to the target point and solve the corresponding matrix
4	Define the fitness function $f_{G}$
5	Set the population size, crossover fraction, and selection function
6	For $i = 1$ to $n$ do
7	Calculate $T_{a}$ , $T_{b}$ , $T_{c}$ , $T_{d}$ , and $l_{1}$ , $l_{2}$ , and compute $d_{1}$ , $d_{2}$ and $f_{OB}$
8	if $f_{OB} = = 1$ doMinimize $f_{Q}$ , $f_{L}$ and the fitness function $f_{G}$
9	After iteration output the result $theta = [x_{j}]_{j = 1, 2, \dots, 6}$

We set the number of interpolation points. The variable to be optimized is the intermediate point parameter, which corresponds to six joint angles $theta = [x_{j}]_{j = 1, 2, \dots, 6}$ of the robotic arm in the joint space. And before running the algorithm, we also need to set the boundary constraint. Because the six joints are all rotating joints in the plane, we add the lower bounds and upper bounds to them as shown in formula (18)

\begin{array}{l} [- \frac{π}{2}, 0, - \frac{π}{2}, - \frac{π}{2}, - \frac{π}{2}, - \frac{π}{2}] \\ \leq {[x_{j}]}_{j = 1, 2, …, 6} \leq [\frac{π}{2}, π, \frac{π}{2}, \frac{π}{2}, \frac{π}{2}, \frac{π}{2}] \end{array}

(18)

In summary, our fitness function is shown in formula (15) and our objective function is $η_{1} f_{Q} + η_{2} f_{L}$ . The optimization variable is six joint angles given by $theta = [x_{j}]_{j = 1, 2, \dots, 6}$ . And the constraints of the lower and upper bounds are given in formula (18).

Experimental verification

In order to verify that the IPOA algorithm proposed in this article is reliable, we set different experimental conditions. First we verify the effectiveness of the IPOA algorithm for single obstacle with different expansion radiuses. Then we test the reliability of the IPOA algorithm when multiple obstacles exist. Besides, the superiority of the algorithm is proved when the obstacle is not on the planned path. Finally, through the performance comparison experiment, the relationship between the number of intermediate points and obstacle avoidance performance is analyzed.

We all know that each joint angle corresponds to a position and attitude of the robotic arm in the Cartesian coordinate space. So the starting point and the target point in the Cartesian coordinate space can be represented by the joint space. In the following experiments, we set the starting point of the joint angle as $q_{0} = [0, 0, 0, 0, 0, 0]$ , the target point of the joint angle is $q_{f} = [π / 2, π / 3, - π / 2, 0, π / 2, π / 4]$ , and these two points are randomly selected.

Single obstacle avoidance with different expansion radiuses

Set the experimental conditions as follows: the obstacle point in the Cartesian coordinate space is $P = [50, 100, 50]$ and the obstacle expansion radiuses are $R_{1} = 30$ and $R_{2} = 50$ , respectively. Here $R_{1}$ and $R_{2}$ are the sum of the connecting rod radius and the obstacle radius. Through the gene optimization scheme presented in section “Design of fitness function,” an intermediate point can be found to steer the robotic arm around the obstacle with minimum joint variations and the shortest motion trajectory.

Figure 4 indicates the variation curve of the fitness function along with the genetic iteration process.

Figure 4.

The best and mean fitness variation curve along with the genetic iterations process: (a) obstacle expansion radius $R_{1} = 30$ and (b) obstacle expansion radius $R_{2} = 50$ .

In the case of $R_{1} = 30$ , after 110 iterations, the intermediate point $theta = [1.139, 1.059 . - 1.123, 0, 1.441, 0.579]$ can be found and the fitness function $f_{G} = - 0.0695$ , $f_{Q} = 6.549$ , and $f_{L} = 7733.6$ . And when the obstacle expansion radius extends to $R_{2} = 50$ , after 124 iterations, the intermediate point $theta = [1.413, 1.554, - 1.16, 0, 0.132, 0.467]$ can be found and the fitness function $f_{G} = - 0.0573$ , $f_{Q} = 7.559$ , and $f_{L} = 9903.5$ . In both cases, the motion trajectory of the robotic arm can be expressed as shown in Figures 5 and 6.

Figure 5.

Robotic arm motion trajectory when the obstacle expansion radius is $R_{1} = 30$ : (a) the first period from starting point to intermediate point and (b) the second period from intermediate point to target point.

Figure 6.

Robotic arm motion trajectory when the obstacle expansion radius is $R_{2} = 50$ : (a) the first period from starting point to intermediate point and (b) the second period from intermediate point to target point.

In Figures 5 and 6, red line represents the straight line of two points, and blue line represents the actual motion trajectory of the end effector. It can be seen that the shortest distance between the connecting rod and the obstacle during the movement of the manipulator is when the connecting rod is tangent to the obstacle.

Figure 7 illustrates the distance change curves between the two connecting rods and the obstacle point, where S₁ and S₂ represent the distance of the connecting rods 1 and 2 to the obstacle point from the starting point to the intermediate point; S₃ and S₄ represent the distance of the connecting rods 1 and 2 to the obstacle point from the intermediate point to the target point. The two motion trajectories of the robotic arm are fitted with 25 interpolation points, each of which corresponds to the distance of the two connecting rods to the obstacle point. As can be seen from the graph, the distance of all connecting rods to the obstacle point is greater than each obstacle expansion radius $R$ , which means that there is no interference in the movement of the robotic arm. It can also be indicated that S₁ and S₃ are continuous in the distance direction, so do S₂ and S₄.

Figure 7.

Distance change curves between the connecting rod and the obstacle point when (a) obstacle expansion radius $R_{1} = 30$ and (b) obstacle expansion radius $R_{2} = 50$ .

Through the above experiments, the reliability of the IPOA algorithm for single obstacle in the condition of different expansion radiuses is validated.

Experimental analysis for multiple obstacle avoidance

In the actual application scenario, the working conditions of serial robot will be more complicated and multiple obstacles must be taken into account. The multi-obstacle avoidance problem is about to be solved. In this article, we take the IPOA algorithm introduced in section “Principle of our IPOA algorithm,” expand the basis method, and connect it in series. The experiment of two obstacle points is carried out and the more complex approach is similar.

Set the experimental conditions as follows: the two obstacle points in the Cartesian coordinate space are $P_{1} = [150, 50, 30]$ , $P_{2} = [50, 100, 50]$ and the obstacle expansion radius is $R = 30$ . Through constraining the distance of the two connecting rods to the obstacle point, the two intermediate points are found using genetic algorithm.

As shown in Figure 8, after 132 iterations, the fitness function $f_{G} = - 0.068$ , $f_{Q} = 6.625$ , and $f_{L} = 8157.4$ , and the two intermediate points are $theta 1 = [0.229, 0.748, - 0.841, 0, 0.407, 0.383]$ and $theta 2 = [1.21, 1.044, - 1.133, 0.002, 1.179, 0.69]$ . The robotic arm moves over three trajectories from the starting point to the target point, each of which is planned by quintic polynomial. The robotic arm motion trajectory and the position and attitude during the movement are presented in Figure 9.

Figure 8.

The best and mean fitness variation curve when multiple obstacles exist.

Figure 9.

(a) Robotic arm motion trajectory when multiple obstacles exist; (b) the position and attitude of the robotic arm during the movement.

We can also obtain the distance change curves between the two connecting rods of the manipulator and two obstacle points in Figure 10.

Figure 10.

Distance change curves between the connecting rod and the obstacle point in different motion periods.

Among them, the curve $d_{ijk}$ represents the distance between the connecting rod $j$ and the obstacle point $k$ in the $i$ period of movement. Three motion trajectories are fitted with 25 interpolation points. It can be seen that the same color curve is continuous in the front and back movements. And the values of all curves are greater than the obstacle expansion radius $R = 30$ , which means that there is no interference in the movement of the robotic arm.

Through the above experiments, we verify that the IPOA algorithm can be used to solve the problem of multi-obstacle avoidance for serial robot.

The superiority analysis of the IPOA algorithm without obstacle

Aimed at the situations where the robotic arm does not need to consider the obstacle avoidance, that is, when the obstacle is not in the working space or on the planned path, we have also analyzed and discussed this kind of classification. In this case, an intermediate point can also be optimized by genetic algorithm, but this intermediate point will not prevent the robotic arm from avoiding the obstacle. The superiority of the IPOA algorithm is validated by comparing the motion trajectory length and the joint space variations of two experimental results.

Set the experimental conditions as follows: the obstacle point in the Cartesian coordinate space is $P = [100, 100, 200]$ and the obstacle expansion radius is $R = 30$ . The original trajectory planning between the starting point and the target point through the quintic polynomial is shown in Figure 11(a). And when setting the intermediate point, the motion trajectory is presented in Figure 11(b).

Figure 11.

(a) Motion trajectory with no obstacle and no intermediate point and (b) motion trajectory with no obstacle and one intermediate point.

It is obvious that the trajectory length will be shorter when setting the intermediate point. By calculation, the fitness function in Figure 11(a) is $f_{G} = - 0.0688$ , $f_{Q} = 6.545$ , and $f_{L} = 7999.8$ , that in Figure 11(b) is $f_{G} = - 0.0765$ , $f_{Q} = 6.547$ , and $f_{L} = 6521.5$ . We can conclude that when the intermediate point is set, the joint space variations roughly remain unchanged and the end effector motion trajectory is reduced significantly. At this time, after 85 iterations, the intermediate point is $theta = [0.139, 0.665, - 1.165, 0.001, 1.173, 0.383]$ .

Through the above experiments, the superiority of the IPOA algorithm is proved when the obstacle is not in the workspace or on the planned path.

Comparison experiment on the number of intermediate points

We set the intermediate point to steer the robotic arm around the obstacle; but is there any connections between the number of intermediate point and the optimal target? In this section, we have conducted experiment with more intermediate points or less intermediate points and discuss the performance through comparison analysis.

In section “Single obstacle avoidance with different expansion radiuses,” one intermediate point is set to move the robotic arm around one obstacle. Now we set two intermediate points to observe the fitness function, the joint space variations, and the length of end motion trajectory. The experimental conditions are set as before and the obstacle expansion radius is $R = 30$ (Figure 12).

Figure 12.

Motion trajectory with one obstacle and two intermediate points.

Through genetic algorithm, the two intermediate points are found which are $theta 1 = [0.845, 0.834, - 0.805, 0, 0.098, 0.109]$ and $theta 2 = [1.175, 1.026, - 1.076, 0, 0.588, 0.662]$ and the fitness function is $f_{G} = - 0.0708$ , $f_{Q} = 6.545$ , and $f_{L} = 7421.5$ . Comparison of these results with those presented in section “Single obstacle avoidance with different expansion radiuses” is shown in Table 2.

Table 2.

Performance comparison analysis on the number of intermediate points when one obstacle exists.

Simulation experimental conditions			Iterations	$f_{G}$	$f_{Q}$	$f_{L}$
Expansion radius	OB	IP	Iterations	$f_{G}$	$f_{Q}$	$f_{L}$
$R = 30$	1	1	110	−0.0695	6.549	7733.6
$R = 30$	1	2	168	−0.0708	6.545	7421.5

OB: obstacle; IP: intermediate point.

In Table 2, we can find that the fitness function decreases by $Δ f_{G} = 0.0013$ , the decrease percentage $Δ g = (Δ f_{G} / f_{G 1}) \times 100 % = 1.87 %$ . It can be seen that when setting two intermediate points, although $f_{Q}$ and $f_{L}$ decrease slightly, the number of iterations increase drastically, which means that the computational time will increase.

In section “Experimental analysis for multiple obstacle avoidance,” two intermediate points are set to move the robotic arm around two obstacles. Now we set one intermediate point to observe the fitness function, the joint space variations, and the length of the end motion trajectory (Figure 13).

Figure 13.

Motion trajectory with two obstacles and one intermediate point.

Through genetic algorithm, the one intermediate point is found which is $theta = [0.493, 0.996, - 0.438, 0, 0.1472, 0.716]$ and the fitness function is $f_{G} = - 0.0627$ , $f_{Q} = 6.693$ , and $f_{L} = 9406.2$ . Comparison of these results with those presented in section “Experimental analysis for multiple obstacle avoidance” is shown in Table 3.

Table 3.

Performance comparison analysis on the number of intermediate points when two obstacles exist.

Simulation experimental conditions			Iterations	$f_{G}$	$f_{Q}$	$f_{L}$
Expansion radius	OB	IP	Iterations	$f_{G}$	$f_{Q}$	$f_{L}$
$R = 30$	2	2	132	−0.0680	6.625	8157.4
$R = 30$	2	1	125	−0.0627	6.693	9406.2

OB: obstacle; IP: intermediate point.

In Table 3, we can observe that the fitness function decreases by $Δ f_{G} = 0.0053$ and the decrease percentage is $Δ g = (Δ f_{G} / f_{G 1}) \times 100 % = 7.79 %$ . It can be concluded that when setting one intermediate point, the length of the end motion trajectory $f_{L}$ increases dramatically with the number of iterations being roughly the same.

In conclusion, through the above experiments, we analyze the relationship between the number of obstacle points and the number of intermediate points. The experiment shows that when there are $N$ obstacle points, the optimal strategy is to set $N$ intermediate points. We can connect the IPOA algorithm in series to realize the multi-obstacle avoidance of robotic arm. It is the best method to balance between effectiveness and efficiency.

In terms of computational complexity, all the codes of our IPOA algorithm are implemented by robotic toolbox 9.8 versions and genetic algorithm toolbox in MATLAB, and run on a computer with Intel(R) Core(TM) i5-4590 at 3.30 GHz and 4 GB RAM in 64-bit win7 operating system. Taking the first experiment $(R_{1} = 30)$ as an example, we performed 10 experiments and the average time of the IPOA algorithm was 295 s. The main calculation comes from the iterations of genetic algorithm. In the future, we will improve this aspect to increase the efficiency of the IPOA algorithm.

The IPOA algorithm proposed in this article has an optimization time of about 300 s for intermediate point parameter, which obviously cannot meet the requirement of real-time performance. In order to solve real-time problems, we proposed possible solutions. From the changes of fitness function during the iteration, we can see that after an average of 30 iterations the algorithm tends to converge. So, from the aspect of efficiency, we can stop the iteration ahead of schedule to improve the real-time performance. Or we can choose another optimization algorithm to achieve the purpose of optimizing the intermediate point parameter. The improvement of real-time problem is one of the key tasks for our follow-up work. Through the programming language transformation from MATLAB to C and the improvement of optimization algorithm, we believe that the real-time performance of IPOA will be further enhanced.

Conclusion

In this article, an IPOA algorithm is proposed to improve the movement efficiency of robotic arm while avoiding the obstacle. Through IPOA algorithm, an ideal non-collision trajectory can be obtained, with the joint velocity and acceleration being smooth and continuous, with the minimum joint space variations and the shortest end motion trajectory. This means that the robotic arm can work in a state of safety, stability, and energy conservation. It is worth noting that the intermediate point solved by genetic algorithm is not necessarily the optimal solution, but it is one of the many solutions near the optimal solution in the case of constraint conditions. We can increase the number of population size or change the crossover and mutation fraction to further improve the performance. However, it is unnecessary to get the optimal solution at the cost of computational time.

In theory, the IPOA algorithm can be extended to arbitrary freedom of the robot’s obstacle avoidance. And through connecting the IPOA algorithm in series, it can realize the multi-obstacle avoidance of robotic arm in complex environment. The theoretical research on obstacle avoidance of this article has a propelling effect on the application of serial robot. In addition, our study can be referenced by the related research of serial robot.

Footnotes

Handling Editor: Jan Torgersen

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the Science and Technology Pillar Program, Tianjin, China, under Project 16YFZCSF00 590.

References

Huang

Hsu

Fung

. Minimum-energy point-to-point trajectory planning for a motor-toggle servomechanism. IEEE/ASME T Mech 2012; 17: 337–344.

Liu

Lai

. Time-optimal and jerk-continuous trajectory planning for robot manipulators with kinematic constraints. Robotics Cim: Int Manuf 2013; 29: 309–317.

Zhao

Zheng

. A new method of 6-DOF serial robot’s trajectory planning under multi-constraints. Appl Mech Mater 2014; 602–605: 1352–1357.

Hasan

Ismail

Hamouda

AMS

et al . Artificial neural network-based kinematics Jacobian solution for serial manipulator passing through singular configurations. Adv Eng Softw 2010; 41: 359–367.

Gasparetto

Zanotto

. A new method for smooth trajectory planning of robot manipulators. Mech Mach Theory 2007; 42: 455–471.

Dong

. Obstacle avoidance path planning of planar redundant manipulators using workspace density. Int J Adv Robot Syst 2015; 12: 9.

Ismail

Lahouar

Romdhane

. Collision-free and dynamically feasible trajectory of a hybrid cable–serial robot with two passive links. Robot Auton Syst 2016; 80: 24–33.

Novin

Masouleh

Yazdani

. Optimal motion planning of redundant planar serial robots using a synergy-based approach of convex optimization, disjunctive programming and receding horizon. Proc IMechE, Part I: J Systems and Control Engineering 2016; 230: 211–221.

Mann

Damti

Tirosh

et al . Minimally actuated serial robot. Robotica 2018; 36: 408–426.

10.

Conkur

. Path planning using potential fields for highly redundant manipulators. Robotics and Autonomous Systems 2005; 52: 209–228.

11.

Tang

et al . Obstacle space modeling and moving-window RRT for manipulator motion planning. In: Proceedings of the 2016 IEEE international conference information and automation (ICIA), Ningbo, China, 1–3 August 2016, pp.539–544. New York: IEEE.

12.

Tang

Lien

Amato

. An obstacle-based rapidly-exploring random tree. In: Proceedings of the 2006 IEEE international conference on robotics and automation(ICRA), Orlando, FL, 15–19 May 2006, pp.895–900. New York: IEEE.

13.

Baumann

Léonard

Croft

et al . Path planning for improved visibility using a probabilistic road map. IEEE T Robot 2010; 26: 195–200.

14.

Ata

. Optimal trajectory planning of manipulators: a review. J Eng Sci Technol 2007; 2: 32–54.

15.

Swevers

Verdonck

De Schutter

. Dynamic model identification for industrial robots. IEEE Contr Syst 2007; 27: 58–71.

16.

Angeles

Alivizatos

Zsombor-Murray

. The synthesis of smooth trajectories for pick-and-place operations. IEEE T Syst Man Cyb 1988; 18: 173–178.

17.

Lozano-Perez

. Automatic planning of manipulator transfer movements. IEEE T Syst Man Cyb 1981; 11: 681–698.

18.

Lozano-Perez

. Spatial planning: a configuration space approach. IEEE T Comput 1983; 32: 108–120.

19.

Hanxu

Shuangqi

. Path planning for space manipulator to avoid obstacle based on A∼* algorithm. J Mech Eng 2010; 13: 17.

20.

Müller

. An on-line Cartesian space obstacle avoidance scheme for robot arms. Math Comput Simulat 1996; 41: 627–637.

21.

Nguyen

Hoffmann

Pattacini

et al . A fast heuristic Cartesian space motion planning algorithm for many-DoF robotic manipulators in dynamic environments. In: Proceedings of the 16th international conference on humanoid robots (Humanoids), Cancun, Mexico, 15–17 November 2016, pp.884–891. New York: IEEE.

22.

Hourtash

Hingwe

Schena

et al . Systems and methods for avoiding collisions between manipulator arms using a null-space. US9675422B2 Patent, USA, 2016.

23.

Yeniay

. Penalty function methods for constrained optimization with genetic algorithms. Math Comput Appl 2005; 10: 45–56.

24.

Zhongping

Guangmin

Yibing

. A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem. Acta Math Sci 2011; 31: 652–660.

25.

Kennedy

. Particle swarm optimization, encyclopedia of machine learning. New York: Springer, 2011, pp.760–766.

26.

Coello

CAC

Lamont

Van Veldhuizen

. Evolutionary algorithms for solving multi-objective problems. New York: Springer, 2007.

27.

Graça Marcos

Machado

Azevedo-Perdicoulis

T-P

. Trajectory planning of redundant manipulators using genetic algorithms. Commun Nonlinear Sci 2009; 14: 2858–2869.

28.

Yokoyama

Suzuki

. Modified genetic algorithm for constrained trajectory optimization. J Guid Control Dynam 2005; 28: 139–144.

29.

Abo-Hammour

ZeS

Alsmadi

OMK

Bataineh

et al . Continuous genetic algorithms for collision-free Cartesian path planning of robot manipulators. Int J Adv Robot Syst 2011; 8: 74.

30.

Ata

Myo

. Optimal point-to-point trajectory tracking of redundant manipulators using generalized pattern search. Int J Adv Robot Syst 2005; 2: 239–244.

31.

Menasri

Oulhadj

Daachi

et al . A genetic algorithm designed for robot trajectory planning. In: Proceedings of the IEEE international conference on systems, man and cybernetics (SMC), San Diego, CA, 5–8 October 2014, pp.228–233. New York: IEEE.

32.

Abu-Dakka

Valero

Suñer

et al . A direct approach to solving trajectory planning problems using genetic algorithms with dynamics considerations in complex environments. Robotica 2015; 33: 669–683.