Avoidance⋆

Abstract

This paper discusses the trajectory planning of a robot manipulator with computer algebra. In the operation of robot manipulators, it is important to make the trajectory of the end efector so that it does not collide with obstacles. For this purpose, we have proposed a method of generating a method of trajectory planning using cubic spline curves. However, the method has the disadvantage that the trajectory 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 a new method of generating a trajectory using Bézier curves, which is guaranteed to be included in the feasible region.

Keywords

• Trajectory planning
• Quantifier elimination
• Inverse kinematics
• Bézier curves

1. 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 efector 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 efector 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 efector 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 eficiency 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 efector, we have LGOBE ∗Corresponding author. (CC BY 4.0).

CEUR Workshop Proceedings

ceur-ws.org ISSN1613-0073 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.

2. 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 efector can be placed anywhere in the feasible region except the origin (see fig. 1).

The feasible region refers to the range that the end-efector 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 diferent 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 efector, 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-efector 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-efector will of course be able to reach a point closer than the point where the end-efector is already determined to be placed.

3. 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 diferent 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. of is 0

() for 0 ≤ ≤ 1 constructs the Bézier 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 0 , 1( 1 ), … , −1 ( 1 ) ( 1 ) that divide the line segment 0 1, 1 2, … , −1 internally into ∶ 1 − , respectively. Next, take points 0 , 1( 2 ), … , −(22) that divide the line segments 0 1 , 1 2( 1 ), … , −2 −(11) , internally ( 2 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) into ∶ 1 − , respectively. Repeat the same operation for times to obtain 0() , then the locus

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.

4. 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.

4.1. 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 =0

() = ∑ ( ) (1 − )− , () = ∑ ( ) (1 − )− , () = ∑ ( ) (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. =0 ℎ +1 … … +1

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 +

. () = (1 − ) 0 + .

= − 0 − 0 .

Substituting into () in eq. ( 1 ) gives 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

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:

=+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 efector.

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.

4.2. 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 efective 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 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 suficient conditions for ′( 1 ) = ′(0)and ′( 1 ) = ′(0)to hold are 2 0 = 2 + 1, 2 0 = 2 + 1, respectively. Similarly, the necessary and suficient conditions for ″( 1 ) = ″(0)and ″( 1 ) = ″(0)to hold are 2( 1 − 2) = 2 − 1, 2( 1 − 2) = 2 − 1, respectively [16]. So far, we see that the control points 1, 2, 1, 2 depend on 1 and 2 as 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 efector 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. 4.2.1. Using 2-degree Bézier curves In the alternative method, we create a path using three 2-degree Bèzier Curves (̂ ) = 2 ∑ ( 2 ) (1 − )2− ̂ , =0 (̂) = 2 ∑ ( 2 ) (1 − )2− ̂ , =0 (̂) = 2 ∑ ( 2 ) (1 − )2− ̂ , =0 in place of (), (), () in eq. (5), respectively, whose first-order diferentials are identical at the connection points, together with 2̂ = ̂0, ̂2 = ̂0. Now we determine the other control points using only the predefined 0̂ = 0, ̂0 = 0, ̂0 = 0, ̂2 = 3. Since the first derivatives at the connection points are the same for two adjacent curves, we have 2 ̂0 = 1̂ + ̂1, 2 ̂0 = ̂1 + ̂1. For ∶= max{‖ 0̂‖, ‖ ̂0‖, ‖ ̂0‖, ‖ ̂3‖}, we require all remaining control points to be included in the hemisphere centered at the origin with radius , i.e., ‖ 1̂‖ ≤ , ‖ ̂1‖ ≤ , ‖ ̂1‖ ≤ . Then, the problem is reduced to eliminate quantified variables in a quantified formula ∃ 1̂∃ ̂1( ( 1̂ = 2 ̂0 − ̂1) ∧ ( ̂1 = 2 ̂0 − ̂1) ∧ (‖ 1̂‖ ≤ ) ∧ (‖ ̂1‖ ≤ ) ∧ (‖ ̂1‖ ≤ )). (8) Fortunately, by quantifier elimination, we have obtained the possible region of ̂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.3.1 in approximately 15.4 [s]. The computing environment is as follows: Intel Core i3-8130U 2.20GHz, 8GB RAM, Windows 11 Home.)

5. 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 eficiency by deriving more appropriate constraints, making the algorithm more eficient, 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]. [4] S. Ricardo Xavier da Silva, L. Schnitman, V. Cesca Filho, A Solution of the Inverse Kinematics Problem for a 7-Degrees-of-Freedom Serial Redundant Manipulator Using Gröbner Bases Theory, Mathematical Problems in Engineering 2021 (2021) 6680687. doi:10.1155/2021/6680687. [5] T. Uchida, J. McPhee, Triangularizing kinematic constraint equations using Gröbner bases for real-time dynamic simulation, Multibody System Dynamics 25 (2011) 335–356. doi:10.1007/s11044-010-9241-8. [6] T. Uchida, J. McPhee, Using Gröbner bases to generate eficient kinematic solutions for the dynamic simulation of multi-loop mechanisms, Mech. Mach. Theory 52 (2012) 144–157. doi:10.1016/j.mechmachtheory.2012.01.015. [7] V. Weispfenning, Comprehensive Gröbner Bases, J. Symbolic Comput. 14 (1992) 1–29.

doi:10.1016/0747-7171(92)90023-W. [8] R. Fukasaku, H. Iwane, Y. Sato, Real Quantifier Elimination by Computation of Comprehensive Gröbner Systems, in: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’15, Association for Computing Machinery, New York, NY, USA, 2015, pp. 173–180. doi:10.1145/2755996.2756646. [9] S. Otaki, A. Terui, M. Mikawa, A Design and an Implementation of an Inverse Kinematics Computation in Robotics Using Real Quantifier Elimination based on Comprehensive Gröbner Systems, Preprint, 2021. doi:10.48550/arXiv.2111.00384, arXiv:2111.00384. [10] M. Yoshizawa, A. Terui, M. Mikawa, Inverse Kinematics and Path Planning of Manipulator Using Real Quantifier Elimination Based on Comprehensive Gröbner Systems, in: Computer Algebra in Scientific Computing: CASC 2023, volume 14139 of Lecture Notes in Computer Science, Springer, 2023, pp. 393–419. doi:10.1007/978-3-031-41724-5_21. [11] Y. Shirato, N. Oka, A. Terui, M. Mikawa, An Optimized Path Planning of Manipulator with Spline Curves Using Real Quantifier Elimination Based on Comprehensive Gröbner Systems, in: SCSS 2024 Work-in-progress Proceedings, Open Publishing Association, 2024.

To appear. [12] U. Dincer, M. Cevik, Improved trajectory planning of an industrial parallel mechanism by a composite polynomial consisting of bëzier curves and cubic polynomials, Mechanism and Machine Theory 132 (2019) 248–263. doi:10.1016/j.mechmachtheory.2018.11.009. [13] Y.-L. Kuo, C.-C. Lin, Z.-T. Lin, Dual-optimization trajectory planning based on parametric curves for a robot manipulator, International Journal of Advanced Robotic Systems 17 (2020) 1729881420920046. doi:10.1177/1729881420920046. [14] Z. Xu, S. Wei, N. Wang, X. Zhang, Trajectory planning with bezier curve in cartesian space for industrial gluing robot, in: X. Zhang, H. Liu, Z. Chen, N. Wang (Eds.), Intelligent Robotics and Applications, Springer International Publishing, Cham, 2014, pp. 146–154. doi:10.1007/978-3-319-13963-0_15. [15] P. Bézier, The Mathematical Basis of the UNIURF CAD System, Elsevier, 1986. doi:10.

1016/C2013-0-01005-5. [16] T. Tsuchihashi, Trajectory Generation and Control for Manipulator Using the Bezier Curve (in Japansese), Transactions of the Japan Society of Mechanical Engineers Series C 55 (1989) 124–128. doi:10.1299/kikaic.55.124.

References

[1] J. Capco , M. S. E. Din , J. Schicho , Robots, computer algebra and eight connected components , in: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation , ISSAC '20 , ACM , 2020 . doi: 10 .1145/3373207.3404048.

[2] J.-C. Faugère , J.-P. Merlet , F. Rouillier , On solving the direct kinematics problem for parallel robots , Research Report RR-5923 , INRIA, 2006 . URL: https://hal.inria.fr/inria-00072366.

[3] C. M. Kalker-Kalkman , An implementation of Buchbergers' algorithm with applications to robotics , Mech. Mach. Theory 28 ( 1993 ) 523 - 537 . doi: 10 .1016/ 0094 - 114X ( 93 ) 90033 - R .