Introduction

In this paper, we discuss the trajectory planning of a robot manipulator with computer algebra. A manipulator is a robot with links, which correspond to human arms, and joints, which correspond to human joints, connected alternately. The end effector is the component located at the tip of the link that is farthest from the base of the manipulator. The inverse kinematics problem examines whether it is possible to place the end effector at a given point and orientation, and if it is possible, the problem is to find the joint configuration for that placement. The trajectory planning problem is to find a path for the end effector to move from the start point to the endpoint without colliding with obstacles.

There are numerous methods for solving the inverse kinematics problem of manipulators using computer algebra proposed to date [1,2,3,4,5,6]. Among them, we have proposed one that enhances computation efficiency with the use of Comprehensive Gröbner Systems (CGS) [7], and certifies the existence of solutions to inverse kinematics problems using the Quantifier Elimination (QE) which is based on the CGS, so-called the CGS-QE [8] method [9]. Furthermore, we have extended the method to trajectory planning using a straight-line path [10].

By using the straight-line path, the trajectory may interfere with obstacles. Therefore, it is possible to design the trajectory to avoid obstacles using a polyline, but doing so may result in discontinuities in velocity and acceleration of the manipulator at the vertices of the polyline, which could destabilize the operation. To achieve smooth movement of the end effector, we have proposed trajectory planning using a spline curve [11]. However, the spline curve may not be included in the feasible region of the manipulator, thus an extra test for the inclusion of the curve is needed.

In this paper, we propose methods for trajectory planning using Bézier curves. The shape of a Bézier curve is determined by the placement of control points, and the curve has the property of always being contained within the convex hull formed by the control points as vertices. Utilizing this property, the goal is to generate trajectories that avoid obstacles without deviating from the feasible region. Although several proposals have been made for the use of Bézier curves in general trajectory planning [12,13,14], to the best of the authors' knowledge, the utilization of Bézier curves in trajectory planning using computer algebra is considered to be almost nonexistent.

This paper is organized as follows. In Section 2, we introduce the feasible region of the manipulator and define the radius of the region. In Section 3, we introduce the Bézier curve and its properties. In Section 4, we propose two methods for trajectory planning using Bézier curves. In Section 5, we conclude and discuss future research direction.

Preliminaries

In this paper, the manipulator to be used is placed on the real space ℝ 3 with the global coordinate system, whose origin is located at the base of the manipulator. Assume that the end effector can be placed anywhere in the feasible region except the origin (see fig. 1).

The feasible region refers to the range that the end-effector of the manipulator can reach. Here, we assume that the feasible region of the manipulator is given as the surface and the interior of a hemisphere with the origin as the center and positive 𝑧 coordinates.

As for the radius of the region, we define a value different from the radius that the actual manipulator can execute. In this case, we will define the radius by comparing the distances between the origin and the start and the endpoints of the end effector, and the farthest of the passing points, as described below.

An example is shown in fig. 2. Let us consider a trajectory with the start point 𝑆 and the endpoint 𝐺 that passes through two predetermined points 𝐶 1 and 𝐶 2 . Assume that we have verified the end-effector can reach all the points except for the origin 𝑂 by, for example, the method we have previously proposed [10]. 𝑆, 𝐶 1 , 𝐶 2 , and 𝐺 are located as in fig. 2 with respect to the origin 𝑂. In this case, the point farthest from 𝑂 among these is 𝐶 2 . Therefore, the distance 𝑟 between 𝑂 and 𝐶 2 is defined as the 𝑟, radius of the feasible region. We see that, by the radius 𝑟 in this way, the end-effector will of course be able to reach a point closer than the point where the end-effector is already determined to be placed.

The Bézier Curve

The Bézier curve [15] is a parametric curve on which the point is expressed as a polynomial function of the parameter 𝑡, defined as follows. Definition 1. Let 𝑃 0 , 𝑃 1 , … , 𝑃 𝑛 be different points. Then, the 𝑁-degree Bézier Curve 𝑃(𝑡) is defined as

𝑃(𝑡) = 𝑛 ∑ 𝑖=0 ( 𝑛 𝑖 )𝑡 𝑖 (1 − 𝑡) 𝑛−𝑖 𝑃 𝑖 , 0 ≤ 𝑡 ≤ 1,

where 𝑃 0 , 𝑃 1 , … , 𝑃 𝑛 are the control points. Note that the curve starts at 𝑃 0 and ends at 𝑃 𝑛 .

The method employs control points for producing the curve. Note that the curve does not pass through the control points except for the start and the endpoint but is attracted by them. It is as if the points exert a pull on the curve.

An 𝑛-degree Bézier Curve is constructed as follows (for an example of a 3-degree Bézier curve, see Figure 3). First, place 𝑛 + 1 control points 𝑃 0 , 𝑃 1 , … , 𝑃 𝑛 , and take points 𝑄

(1) 0 , 𝑄 (1) 1 , … , 𝑄 (1) 𝑛−1 that divide the line segment 𝑃 0 𝑃 1 , 𝑃 1 𝑃 2 , … , 𝑃 𝑛−1 𝑃 𝑛 internally into 𝑡 ∶ 1 − 𝑡, respectively. Next, take points 𝑄 (2) 0 , 𝑄 (2) 1 , … , 𝑄(2)

𝑛−2 that divide the line segments 𝑄

(1) 0 𝑄 (1) 1 , 𝑄 (1) 1 𝑄 (1) 2 , … , 𝑄 (1) 𝑛−2 𝑄 (1)

𝑛−1 , internally into 𝑡 ∶ 1 − 𝑡, respectively. Repeat the same operation for 𝑛 times to obtain 𝑄 (𝑛) 0 , then the locus of is 𝑄 (𝑛) 0 for 0 ≤ 𝑡 ≤ 1 constructs the Bézier Curve. One of the advantages of using Bézier Curves is the convex hull property of the curves [13]. For the convex hull 𝐴 = {∑

𝑛 𝑖=0 𝑐 𝑖 𝑃 𝑖 | ∑ 𝑛 𝑖=0 𝑐 𝑖 = 1, 0 ≦ 𝑐 𝑖 ≦ 1} of the control points 𝑃 0 , 𝑃 1 , … , 𝑃 𝑛 ,

we see that any point on the Bézier Curve 𝑃(𝑡) is included in 𝐴. In other words, if a polyhedron with each control point as a vertex is included in the feasible region, the Bézier Curve obtained from those control points is also included in the region. This idea will be used in our second method proposed below.

Path planning using Bézier curves

We propose two methods for trajectory planning using Bézier curves. In the methods, we settle the following assumptions: In addition to the start and the endpoints, two points that the curve must pass through are given. Those points have the same 𝑦 and 𝑧 coordinates, respectively.

Method 1: path planning with single Bézier curve

In the first method, we construct a path with a single Bézier curve. We give the 𝑥 coordinates of the control points equally distributed and select the control points using equality and inequality evaluation. Furthermore, we consider only the case where the curve is curved in the positive direction in both 𝑦 and 𝑧 coordinates.

If an 𝑛-degree Bézier Curve in ℝ 3 is represented as 𝑃(𝑡) = (𝑃 𝑥 (𝑡), 𝑃 𝑦 (𝑡), 𝑃 𝑧 (𝑡)), each component is expressed as

𝑃 𝑥 (𝑡) = 𝑛 ∑ 𝑖=0 ( 𝑛 𝑖 )𝑡 𝑖 (1 − 𝑡) 𝑛−𝑖 𝑥 𝑖 , 𝑃 𝑦 (𝑡) = 𝑛 ∑ 𝑖=0 ( 𝑛 𝑖 )𝑡 𝑖 (1 − 𝑡) 𝑛−𝑖 𝑦 𝑖 , 𝑃 𝑧 (𝑡) = 𝑛 ∑ 𝑖=0 ( 𝑛 𝑖 )𝑡 𝑖 (1 − 𝑡) 𝑛−𝑖 𝑧 𝑖 ,(1)

using the control points 𝑃 𝑖 (𝑥 𝑖 , 𝑦 𝑖 , 𝑧 𝑖 ) (𝑖 = 0, 1, … 𝑛). Here, we define the 𝑥 coordinates of each control point satisfying that 𝑃 𝑥 (𝑡) is a linear polynomial in 𝑡. This approach has the advantage that it not only reduces the amount of calculation required to create the trajectory but also makes the operation of "finding the value of 𝑡 from the 𝑥 coordinate of a point on the curve" easier. To achieve this objective, simply place the 𝑥 coordinates 𝑥 0 , 𝑥 1 , … , 𝑥 𝑛 of each control point in order at equal intervals, i.e., for 𝑖 = 0, 1, … , 𝑛, let

𝑥 𝑖 = (𝑛 − 𝑖)𝑥 0 + 𝑖𝑥 𝑛 𝑛 .

Substituting 𝑥 𝑖 into 𝑃 𝑥 (𝑡) in eq. ( 1) gives

𝑃 𝑥 (𝑡) = (1 − 𝑡)𝑥 0 + 𝑡𝑥 𝑛 .(2)

Next, we define the 𝑦 and 𝑧 coordinates of each control point. In eq. ( 2), denote the 𝑥 coordinate of a point on the curve simply as 𝑃 𝑥 (𝑡) = 𝑥, and solve eq. ( 2) for 𝑡, then we have

𝑡 = 𝑥 − 𝑥 0 𝑥 𝑛 − 𝑥 0 .(3)

Now, assume that there is an obstacle in the feasible region, and to avoid it, the 𝑦 and 𝑧 coordinates of the path must always exceed a certain value ℎ 𝑦 > 0 and ℎ 𝑧 > 0, respectively, in the interval [𝑎, 𝑏] in the 𝑥 coordinate, where 𝑥 𝑝 < 𝑎 ≤ 𝑥 𝑝+1 ≤ 𝑥 𝑞 ≤ 𝑏 < 𝑥 𝑞+1 for 1 ≤ 𝑝 < 𝑞 + 1 ≤ 𝑛 (see Figure 4). Substituting 𝑥 = 𝑎 and 𝑏 for eq. ( 3) and denoting them as 𝑡 𝑎 and 𝑡 𝑏 , respectively, we obtain

𝑡 𝑎 = 𝑎 − 𝑥 0 𝑥 𝑛 − 𝑥 0 , 𝑡 𝑏 = 𝑏 − 𝑥 0 𝑥 𝑛 − 𝑥 0 .

For the 𝑦 coordinate of the curve, among the tuples of 𝑦 1 , 𝑦 2 , … 𝑦 𝑛−1 that satisfy the following equalities and inequalities:

𝑃 𝑦 (𝑡 𝑎 ) = 𝑃 𝑦 (𝑡 𝑏 ) = ℎ 𝑦 , 𝑦 0 ≤ 𝑦 1 , … , 𝑦 𝑝 , ℎ 𝑦 ≤ 𝑦 𝑝+1 , … , 𝑦 𝑞 , 𝑦 𝑛 ≤ 𝑦 𝑞+1 , … , 𝑦 𝑛−1 ,(4)

select the one with the smallest sum ∑ 𝑞 𝑘=𝑝+1 𝑦 𝑘 . The reason for selecting the tuple with the smallest sum is to minimize the bulge in the positive direction of the 𝑦 coordinate of the curve. Furthermore, to prevent each 𝑦 𝑖 value from becoming too small, a lower limit is set as constraints in eq. ( 4) so that it does not fall below the coordinate of the starting point before crossing the obstacle, and the coordinate of the endpoint after crossing the obstacle.

For the 𝑧 coordinate of the curve, 𝑧 1 , 𝑧 2 , … , 𝑧 𝑛−1 can be calculated in the same way as 𝑦 1 , 𝑦 2 , … 𝑦 𝑛−1 are calculated in above, simply by replacing 𝑦 𝑖 with 𝑧 𝑖 . After obtaining 𝑦 1 , 𝑦 2 , … 𝑦 𝑛−1 and 𝑧 1 , 𝑧 2 , … , 𝑧 𝑛−1 , put these values into 𝑃 𝑦 (𝑡) and 𝑃 𝑧 (𝑡) in eq. ( 1), respectively, which gives the coordinates of all control points, thus the curve becomes the trajectory of the end effector.

The advantage of this method is that the 𝑥 coordinate of a point on the curve is expressed as a linear polynomial 𝑡, thus the value of 𝑡 can easily obtained from 𝑥 as in eq. ( 3), and the curve can be flexibly designed according to the position and the size of the obstacles. However, at present, it is not guaranteed that the curve will be included in the feasible region, thus improvements of the method are required, such as not only suppressing the bulge of the curve but also adding new constraints so that the curve will be included in the feasible region.

Method 2: path planning with multiple Bézier curves

The second method is to construct a path connecting multiple 3-degree Bézier curves calculated under certain conditions. We use a Bézier curve of degree 3 because it is the curve of the smallest degree whose curvature can be controlled. This method makes effective use of the convex hull property mentioned above since it is guaranteed that the created curves do not go outside the feasible region.

We consider the connection of three cubic Bézier Curves 𝑃(𝑡), 𝑄(𝑡), and 𝑅(𝑡), where

𝑃(𝑡) = 3 ∑ 𝑖=0 ( 3 𝑖 )𝑡 𝑖 (1 − 𝑡) 3−𝑖 𝑃 𝑖 , 𝑄(𝑡) = 3 ∑ 𝑖=0 ( 3 𝑖 )𝑡 𝑖 (1 − 𝑡) 3−𝑖 𝑄 𝑖 , 𝑅(𝑡) = 3 ∑ 𝑖=0 ( 3 𝑖 )𝑡 𝑖 (1 − 𝑡) 3−𝑖 𝑅 𝑖 .(5)

Assume that, in eq. ( 5), 𝑃 𝑖 , 𝑄 𝑖 , 𝑅 𝑖 ∈ ℝ 3 and we consider 𝑃(𝑡), 𝑄(𝑡), 𝑅(𝑡) as vector-valued polynomials.

As with the method in Section 4.1, we aim to draw a curve in which the 𝑦 and the 𝑧 coordinates exceed a certain value in a certain interval in the 𝑥 coordinate, by drawing the first curve 𝑃(𝑡) from the starting point to that interval, the second curve 𝑄(𝑡) avoiding the obstacles, and the third curve to the endpoint. Since the endpoint of 𝑃(𝑡) and the start point of 𝑄(𝑡), and the end point of 𝑄(𝑡) and the start point of 𝑅(𝑡) are identical, respectively, we have 𝑃(1) = 𝑄(0) and 𝑄(1) = 𝑅(0), i.e., 𝑃 3 = 𝑄 0 and 𝑄 3 = 𝑅 0 . In this path planning, we aim to express the other control points using the predefined points 𝑃 0 , 𝑄 0 , 𝑅 0 , 𝑅 3 .

To make the connection smooth, we settle a constraint that the first and second derivatives at the connection points are equal for two adjacent curves, respectively. The necessary and sufficient conditions for 𝑃 ′ (1) = 𝑄 ′ (0) and 𝑄 ′ (1) = 𝑅 ′ (0) to hold are 2𝑄 0 = 𝑃 2 +𝑄 1 , 2𝑅 0 = 𝑄 2 +𝑅 1 , respectively. Similarly, the necessary and sufficient conditions for 𝑃 ″ (1) = 𝑄 ″ (0) and [16]. So far, we see that the control points 𝑃 1 , 𝑃 2 , 𝑅 1 , 𝑅 2 depend on 𝑄 1 and 𝑄 2 as

𝑄 ″ (1) = 𝑅 ″ (0) to hold are 2(𝑄 1 − 𝑃 2 ) = 𝑄 2 − 𝑃 1 , 2(𝑅 1 − 𝑄 2 ) = 𝑅 2 − 𝑄 1 , respectively𝑃 1 = 4𝑄 0 − 4𝑄 1 + 𝑄 2 , 𝑃 2 = 2𝑄 0 − 𝑄 1 , 𝑅 1 = 2𝑅 0 − 𝑄 2 , 𝑅 2 = 𝑄 1 − 4𝑄 2 + 4𝑅 0 .(6)

Now we determine 𝑄 1 and 𝑄 2 . Let the feasible region be a hemisphere with a radius 𝑟 = max{‖𝑃 0 ‖, ‖𝑄 0 ‖, ‖𝑅 0 ‖, ‖𝑅 3 ‖} centered at the origin and with 𝑧 > 0. Here, ‖ ⋅ ‖ represents the norm of the vector. We require all remaining control points to be included in this hemisphere, i.e., ‖𝑃 𝑖 ‖ ≤ 𝑟, ‖𝑄 𝑖 ‖ ≤ 𝑟, ‖𝑅 𝑖 ‖ ≤ 𝑟 (𝑖 = 1, 2), which is reduced to solve the problem to find 𝑄 1 and 𝑄 2 that satisfy the above conditions. This problem is expressed as eliminating quantified variables in a quantified formula

∃𝑃 1 ∃𝑃 2 ∃𝑅 1 ∃𝑅 2 ((𝑃 1 = 4𝑄 0 − 4𝑄 1 + 𝑄 2 ) ∧ (𝑃 2 = 2𝑄 0 − 𝑄 1 ) ∧ (𝑅 1 = 2𝑅 0 − 𝑄 2 ) ∧ (𝑅 2 = 𝑄 1 − 4𝑄 2 + 4𝑅 0 ) ∧ (‖𝑃 1 ‖ ≦ 𝑟) ∧ (‖𝑃 2 ‖ ≦ 𝑟) ∧ (‖𝑄 1 ‖ ≦ 𝑟) ∧ (‖𝑄 2 ‖ ≦ 𝑟) ∧ (‖𝑅 1 ‖ ≦ 𝑟) ∧ (‖𝑅 2 ‖ ≦ 𝑟)).(7)

After solving eq. ( 7) and conditions on 𝑄 1 and 𝑄 2 are obtained, then choose 𝑄 1 and 𝑄 2 that makes ‖𝑄 1 − 𝑄 0 ‖ 2 + ‖𝑄 2 − 𝑄 1 ‖ 2 + ‖𝑅 0 − 𝑄 2 ‖ 2 as small as possible satisfying eq. ( 7), Then the rest of the control points 𝑃 0 , 𝑃 1 , 𝑃 2 , 𝑄 0 , 𝑅 0 , 𝑅 1 , 𝑅 2 , 𝑅 3 are determined, and the path of the end effector is obtained. This method is promising since, if eq. ( 7) is solved, it gives a path that does not go beyond the feasible region and passes two points through for obstacle avoidance. Unfortunately, quantifier elimination for eq. ( 7) is computationally expensive and, at present, has not yet been successful. Therefore, by relaxing the original problem, we propose an alternative method to define a path in practical time.

Using 2-degree Bézier curves

In the alternative method, we create a path using three 2-degree Bèzier Curves

P (𝑡) = 2 ∑ 𝑖=0 ( 2 𝑖 )𝑡 𝑖 (1 − 𝑡) 2−𝑖 P 𝑖 , Q(𝑡) = 2 ∑ 𝑖=0 ( 2 𝑖 )𝑡 𝑖 (1 − 𝑡) 2−𝑖 Q 𝑖 , R (𝑡) = 2 ∑ 𝑖=0 ( 2 𝑖 )𝑡 𝑖 (1 − 𝑡) 2−𝑖 R 𝑖 ,

in place of 𝑃(𝑡), 𝑄(𝑡), 𝑅(𝑡) in eq. ( 5), respectively, whose first-order differentials are identical at the connection points, together with P 2 = Q 0 , Q 2 = R 0 . Now we determine the other control points using only the predefined P 0 = 𝑃 0 , Q 0 = 𝑄 0 , R 0 = 𝑅 0 , R 2 = 𝑅 3 . Since the first derivatives at the connection points are the same for two adjacent curves, we have 2 Q

0 = P 1 + Q 1 , 2 R 0 = Q 1 + R 1 . For 𝑟 ∶= max{‖ P 0 ‖, ‖ Q 0 ‖, ‖ R 0 ‖, ‖ R 3 ‖}

, we require all remaining control points to be included in the hemisphere centered at the origin with radius 𝑟, i.e., ‖ P

1 ‖ ≤ 𝑟, ‖ Q 1 ‖ ≤ 𝑟, ‖ R 1 ‖ ≤ 𝑟.

Then, the problem is reduced to eliminate quantified variables in a quantified formula

∃ P 1 ∃ R 1 (( P 1 = 2 Q 0 − Q 1 ) ∧ ( R 1 = 2 R 0 − Q 1 ) ∧ (‖ P 1 ‖ ≤ 𝑟) ∧ (‖ Q 1 ‖ ≤ 𝑟) ∧ (‖ R 1 ‖ ≤ 𝑟)).(8)

Fortunately, by quantifier elimination, we have obtained the possible region of Q 1 that satisfies eq. ( 8), then three Bézier Curves were obtained in the same way as described in the cubic Bézier Curves case. (The computation was done using the computer algebra system Wolfram Mathematica 13.

Concluding Remarks

We have proposed two methods for trajectory planning of manipulators using Bézier curves so that the generated curve does not go outside the feasible region. The first method can avoid obstacles with a minimum curve that matches the position and size of the obstacle, but it does not guarantee that any point on the curve is included in the region. The second method can guarantee that the curve does not go outside the region based on the constraint conditions, but its calculation cost is high and the position of the control point has not yet been obtained. To overcome this, we have proposed an alternative method using 2-degree Bézier curves, which can be calculated in a practical time.

Our future work includes the establishment of a better method for selecting the control points of a curve that overcomes current issues. We believe that method 2 is promising since the curve generated by the method is guaranteed to be included within the feasible region. The next issue to be solved is to improve computational efficiency by deriving more appropriate constraints, making the algorithm more efficient, and so on.

Once this method is established, we will move on to the stage of calculating the sequence of joint placements for the completed trajectory, leading to improved trajectory planning as proposed in our previous work [10].