Gröbner Systems⋆

Abstract

This paper presents an advanced method for addressing the inverse kinematics and optimal path planning challenges in robot manipulators. The inverse kinematics problem involves determining the joint angles for a given position and orientation of the end-efector. Furthermore, the path planning problem seeks a trajectory between two points. Traditional approaches in computer algebra have utilized Gröbner basis computations to solve these problems, ofering a global solution but at a high computational cost. To overcome the issue, the present authors have proposed a novel approach that employs the Comprehensive Gröbner System (CGS) and CGS-based quantifier elimination (CGS-QE) methods to eficiently solve the inverse kinematics problem and certify the existence of solutions for trajectory planning. This paper extends these methods by incorporating smooth curves via cubic spline interpolation for path planning and optimizing joint configurations using shortest path algorithms to minimize the sum of joint configurations along a trajectory. This approach significantly enhances the manipulator's ability to navigate complex paths and optimize movement sequences.

1. Introduction

This paper discusses a method for solving the inverse kinematics problem and the optimal path planning problem for a robot manipulator. A manipulator is a robot with links corresponding to human arms and joints corresponding to human joints, and the tip is called the end-efector. The inverse kinematics problem for manipulators is to find the angle of each joint, given the position and orientation of the end-efector. The path planning problem is to find a path to move the end-efector between two specified positions [ 1 ]. tively).

When operating the manipulator, one needs to solve the inverse kinematics problem (or the path planning problem, respectively) for the desired end-efector position (or the series of positions, respec

Methods of solving inverse kinematics problems for manipulators by reducing the inverse kinematics problem to a system of polynomial equations and using the Gröbner basis has been proposed [ 2, 3, 4, 5, 6 ]. Solving the inverse kinematics problem using the Gröbner basis computation has an advantage that the global solution of the inverse kinematics problem can be obtained before the end-efector will actually be “moved” by simulation or other means. On the other hand, the Gröbner basis computation has the disadvantage of relatively high computational cost compared to local solution methods such as the Newton method. Furthermore, when solving a path planning problem using the Gröbner basis ⋆This work was partially supported by JKA and its promotion funds from KEIRIN RACE. https://researchmap.jp/aterui (A. Terui); https://mikawalab.org/ (M. Mikawa)

CEUR Workshop Proceedings

ceur-ws.org ISSN1613-0073 computation, it is necessary to solve the inverse kinematics problem for each point on the path, which is even more computationally expensive.

The third and fourth authors have also previously proposed methods for solving inverse kinematics problems using Gröbner basis computations [ 7, 8, 9 ]. The authors’ contributions in their previous work [ 9 ] are as follows. We have proposed a method for solving the inverse kinematics problem and the trajectory planning problem of a 3 Degree-Of-Freedom (DOF) manipulator using the Comprehensive Gröbner System (CGS) [ 10 ]. In the proposed method, the inverse kinematic problem has been expressed as a system of polynomial equations with the coordinates of the end-efector as parameters and the CGS is calculated in advance to reduce the cost of Gröbner basis computation for each point on the path. In addition, we have proposed a method for solving the inverse kinematics problems using the CGS-QE method [ 11 ], which is a quantifier elimination (QE) method based on CGS computations, to certify the existence of a (real) solution. Furthermore, we have proposed a method to certify the existence of a solution to the whole trajectory planning problem using the CGS-QE method, where the points on the trajectory are represented by parameters.

This paper proposes the following method as an extension of the previous work [ 9 ]. 1. Extension of paths used in path planning problems: while the previous work has used straight lines, this paper uses smooth curves generated by the cubic spline interpolation passing through given points. Using a curved path allows us to plan paths that avoid obstacles, for example. 2. Optimization of the joint configuration obtained as the solution to the path planning problem: when solving the path planning problem, there can be multiple solutions to the inverse kinematics problem at each point on the path. In this case, the question is which of the solutions for adjacent points can be connected to minimize the sum of the configurations of the entire sequence of the joints. In this paper, we reduce this problem to the shortest path problem of a weighted graph and propose a method to compute the optimal sequence of joint configurations using shortest path algorithms.

2. Solving path planning problems in 3-DOF manipulators

The manipulator used in this paper is myCobot 280 [ 12 ] from Elephant Robotics, Inc. (hereafter referred to simply as “myCobot”). Although myCobot is a 6-DOF manipulator, we treat it as a 3-DOF manipulator by operating only the three main joints used to move the end-efector while the remaining joints are ifxed, due to the computational costs for solving the inverse kinematic problem by using the CGS and the CGS-QE method.

2.1. Formulation of the forward and the inverse kinematics problems

equations = 0 with = { 1, … , 6}, where

Note that the system of equations = 0 has parameters , , in the coeficients.

With our previously proposed method [ 9 ], before solving = 0 , we calculate the CGS of ⟨ 1, … , 6⟩. Then, for a given end-efector coordinate (, , ) = (, , ) ∈ ℝ 3, determine the feasibility of such a configuration using the CGS-QE method. If the configuration is feasible, we solve = 0 numerically after substituting parameters , , with , , , respectively, to obtain the inverse kinematic solution.

2.2. Generating trajectories using cubic spline interpolation

In the path planning problem, a finite number of points through which the path passes are given in advance, and a trajectory is generated on the smooth path passing through these points. In our previous study, a straight line was used as the path, but in this paper, a path is generated using cubic spline interpolation [ 13 ].

Let ( 0, 0, 0), ( 1, 1, 1), ( 2, 2, 2), ( 3, 3, 3) be four diferent points given in ℝ3. For = 0, 1, 2, calculate a curve passing through ( , , ) and ( +1 , +1 , +1 ) in the form of a function ( (), (), ()) with ∈ [, + 1] as a parameter. In cubic spline interpolation, (), (), () are cubic polynomials, respectively, satisfying the following conditions.

( (), (), ()) = ( , , ), = 0, 1, 2, ( ( + 1), ( + 1), ( + 1)) = ( +1 , +1 , +1 ), = 0, 1, 2, ( ′( + 1), ′( + 1), ′( + 1)) = ( +′1 ( + 1), +′1 ( + 1), +′1 ( + 1)), = 0, 1, ( ″( + 1), ″( + 1), ″( + 1)) = ( +″1 ( + 1), +″1 ( + 1), +″1 ( + 1)), = 0, 1. (1) (2)

2.3. Solving the inverse kinematics problem

For the trajectory obtained in the previous section, we solve the inverse kinematics problem using the following procedure.

First, using the CGS-QE method, we determine the existence of solutions to the inverse kinematics problem for each curve ( = 0, 1, 2 ) that constitutes the path to move the end-efector. In eq. ( 1), replace , , in each equation by (), (), () , respectively, to obtain a system of polynomial equations with as parameter. Let ′() be the result.

Next, we apply the CGS-QE method to ′() to determine whether the system of equations ′() = 0 has real solutions within the parameter ∈ [, + 1] . If ′() = 0 has real solutions within the parameter ∈ [, + 1] (i.e., within ∈ [ 0, 3 ] throughout for ), we calculate the trajectory of the end-efector’s position for time . Let = 3 (where is a positive integer) and, for time = 0, … , , let = () where is a continuous function of [0, ] → [ 0, 3 ] . To ensure that the end-efector has no velocity and acceleration at the beginning and end of the trajectory, we obtain as a polynomial of the smallest degree possible to satisfy ′() = ″() = 0 at = 0 and . Then, we obtain () = 3 ( 18 5 5 − 4 544 + 3 033 ) [14].

Finally, we solve the inverse kinematics problem = 0, … , . For = 0, 1, 2 and = , … , ( + 1) , the configuration of the joints is obtained by solving the system of polynomial equations (3) (4) ′( ()) = 0.

Assuming that the time required to solve the inverse kinematics problem (4) at each value of is constant, then the computation time for trajectory planning is expected to be proportional to .

2.3.1. Experimental results

We have implemented the above method and conducted experiments. The implementation of the inverse kinematics computation was performed as follows: the CGS computation was performed using an algorithm by Kapur et al. [15] with the implementation by Nabeshima [16] on the computer algebra system Risa/Asir [17]. The existence of the root of the inverse kinematics problem by the CGS-QE method was verified using Risa/Asir with accompanying Wolfram Mathematica 13.1 [ 18] for simplifying the expression.

We have given the set of test points as shown in Table 1, whose unit of the coordinates is [mm]. The experiments were conducted in the following environment: Intel Xeon Silver 4210 3.2 GHz, RAM 256 GB, Linux Kernel 5.4.0, Risa/Asir Version 20230315, Wolfram Mathematica 13.1.

Table 2 shows the results of the experiments for = 10 and = 50 . The comprehensive Gröbner system for eq. (1) uses precomputed values. If any part of the generated spline for the given coordinates falls outside the feasible region of myCobot, an error is displayed. The average computation time does not consider the computation time of tests that resulted in an error. The experimental results show that the computation time is considered to be approximately proportional to . In Test 6, it appears that part of the path exceeds the feasible region, causing the computation to terminate with an error.

2.4. Solving optimal path planning problem

The system of equations (4) may have several diferent solutions at each time . For time = 0, … , , suppose that there exist , solutions to the configuration of joint ( = 1, 3, 4 ) at such that ( , ). The sum of the configuration changes of the joints from time = 1 to difers de ,( 1), … , , ( , ) at each time . In order to move each joint more pending on the choice of the solution from ,( 1), … , , smoothly, it is desirable to select a solution that minimizes the sum of the configuration changes of the joints on the path. For this purpose, for = 1, 3, 4 , we define a weighted graph = ( , ), where () ∣ ∈ {0, … , }, ∈ {1, … , = { ,

, }} is the set of vertices corresponding to the joint configuration ( 1), ,( +21) ) ∣ 1 ≤ 1, 2 ≤ , , ∈ {0, … , − 1}} is the set of edges connecting at each time , and = {( , the vertices at adjacent times. Then, in , we reduce the problem of finding the optimal path to the one of finding the shortest path from ,(0) to ,( ) . We have solved the shortest path problem using the following methods.

Method 1 For = 0, … , − 1 , find the sequence of joint configurations { ,( ) ∣ = 0, … , } satisfying the minimum distance between adjacent joint configurations such that min{| ,( 1) − ,( +21) | ∣ 1 ≤ 1 ≤ , , , 1 ≤ 2 ≤ +1, ,+1 }.

Method 2 In the graph , find the shortest path starting at ,(0) ( = 1, … , ,0 ) using the Dijkstra method [19], then find the shortest path with the minimum length among s.

The arithmetic complexity of each method above is estimated as follows. Let be the number of points in the trajectory, and assume that the number of solutions to the inverse kinematics problem at each point is constant at . The complexity of Method 1 is ( ) . On the other hand, the complexity of Method 2, using a binary heap, is estimated to be ( 2 log( )) .

2.4.1. Experimental results

We have implemented the above method and conducted experiments. The implementation of each procedure was based on an implementation [20] in the Python programming language. The experiments were conducted in the following environment: A virtual machine with RAM 13.2 GB, Ubuntu 22.04.3 LTS, Python 3.10.2 on VMware Workstation 16 Player, on the host environment with Intel Core i7-1165G7, RAM 16 GB, Windows 11 Home.

The test points are composed of a total of = 15 points, obtained by dividing each segment of the cubic spline curve passing through each point in Table 3 into 5 parts. The number of solutions to the inverse kinematics problem at each point in each test segment is = 4 .

3. Concluding remarks

We have proposed a method for trajectory planning of robot manipulators using computer algebra, where the path is provided by cubic spline interpolation. Furthermore, we have proposed a method to optimize the joint configuration of the manipulator by solving the shortest path problem in a weighted graph. The experimental results have shown that the proposed methods can be used to plan the trajectory of the manipulator and optimize the joint configuration.

Future work includes the following. 1. Regarding path planning using cubic splines, it has been pointed out that some parts of the generated path may deviate from the feasible region. In the future, it is necessary to consider methods that ensure the generated trajectory stays within the feasible region while meeting given constraints, such as avoiding obstacles. In response to this, the authors are currently proposing a path-planning method that uses Bézier curves to generate trajectories that remain within the feasible region [21]. 2. Instead of representing the trajectory on the path, it is desired to express any point on the path using parameters and ensure the solution to the inverse kinematics problem for that point. For linear paths, a method has already been proposed by the authors [ 9 ], and this will be extended to curves given by cubic splines. 3. Regarding optimal path planning using shortest path calculations on graphs, we have used an implementation of Dijkstra’s algorithm using a binary heap in this paper. However, one method to further improve computational eficiency is to use Dijkstra’s algorithm with a Fibonacci heap [22]. For example, using an implementation of Dijkstra’s algorithm with a Fibonacci heap can be considered to improve computational eficiency. 4. To extend the proposed method to a 6-DOF manipulator. Although myCobot is operated with 3 Degree-Of-Freedom in this paper, it originally had 6 Degree-Of-Freedom, so it is desirable to implement methods for motion planning and path planning with 6 Degree-Of-Freedom. [14] K. M. Lynch, F. C. Park, Modern Robotics: Mechanics, Planning, and Control, Cambridge University

Press, 2017. [15] D. Kapur, Y. Sun, D. Wang, An eficient method for computing comprehensive Gröbner bases, J.

Symbolic Comput 52 (2013) 124–142. doi:10.1016/j.jsc.2012.05.015. [16] K. Nabeshima, CGS: a program for computing comprehensive Gröbner systems in a polynomial ring [computer software], 2018. URL: https://www.rs.tus.ac.jp/~nabeshima/softwares.html, accessed 2024-05-04. [17] M. Noro, T. Takeshima, Risa/Asir — A Computer Algebra System, in: ISSAC ’92: Papers from the International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery, New York, NY, USA, 1992, pp. 387–396. doi:10.1145/143242.143362. [18] Wolfram Research, Inc., Mathematica, Version 13.1 [computer software], 2022. URL: https://www.

wolfram.com/mathematica, accessed 2024-05-04. [19] E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959) 269–271.

doi:10.1007/BF01386390. [20] simonritchie, Compute the shortest path of a graph using Dijkstra method and Python (in Japanese), 2023. URL: https://qiita.com/simonritchie/items/216eae753fc393da52af, accessed: 2024-05-04. [21] R. Hatakeyama, A. Terui, M. Mikawa, Towards Trajectory Planning of a Robot Manipulator with Computer Algebra using Bézier Curves, in: SCSS 2024 Work-in-progress Proceedings, Open Publishing Association, 2024. To appear. [22] S.-L. Guo, J. Duan, Y. Zhu, X.-C. Li, T.-W. Chen, Improved dijkstra algorithm based on fibonacci heap for solving the shortest path problem with specified nodes, in: Computer Science and Artificial Intelligence: Proceedings of the International Conference on Computer Science and Artificial Intelligence (CSAI2016), World Scientific, 2017, pp. 52–61. doi: 10.1142/9789813220294_0008.

References

[1] B. Siciliano , O. Khatib , Springer Handbook of Robotics, 2nd ed., Springer, 2016 . doi: 10 .1007/ 978-3- 319 -32552-1.

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

[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] N. Horigome , A. Terui , M. Mikawa , A Design and an Implementation of an Inverse Kinematics Computation in Robotics Using Gröbner Bases , in: A. M. Bigatti , J. Carette , J. H. Davenport , M. Joswig , T. de Wolf (Eds.), Mathematical Software - ICMS 2020 , Springer International Publishing, Cham, 2020 , pp. 3 - 13 . doi: 10 .1007/978-3- 030 -52200- 1 _ 1 .

[8] 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 .

[9] 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 .

[10] V. Weispfenning , Comprehensive Gröbner Bases, J. Symbolic Comput . 14 ( 1992 ) 1 - 29 . doi: 10 . 1016/ 0747 - 7171 ( 92 ) 90023 -W.

[11] 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.

[12] Elephant Robotics Co. , Ltd ., myCobot 280 M5 , 2023 . URL: https://www.elephantrobotics.com/ mycobot-280 - m5-2023, accessed 2024- 05 -04.

[13] G. Farin , Curves and Surfaces for CAGD: A Practical Guide , The Morgan Kaufmann Series in Computer Graphics, 5th ed., Morgan Kaufmann, 2002 . doi: 10 .1016/B978-1- 55860 -737-8. X5000 -5.