An overview and the time optimal cruising trajectory planning.pdf (Robot motion planning)

Journal of Computer Science and Cybernetics, V.30, N.4 (2014), 291–312 DOI: 10.15625/1813-9663/30/4/5767 REVIEW PAPER AN OVERVIEW AND THE TIME-OPTIMAL CRUISING TRAJECTORY PLANNING SOMLÓ JÁNOS Obuda University, Budapest Hungary; somlo@uni-obuda.hu Abstract. In the practical application of robots, the part processing time has a key role. The part processing time is an idea borrowed from manufacturing technology. Industrial robots usually are made to cover a very wide field of applications. So, their abilities, for example, in providing high speeds are outstanding. In most of the applications the very high speed applications are not used. The reasons are: technological (physical), organizational, etc., even psychological. Nevertheless, it is reasonable to know the robot’s abilities. In this paper, a method which intends to provide the motion in every point of the path with possible maximum velocity is described. In fact, the path is divided to transient and cruising parts and the maximum velocities are required only for the latter. The given motion is called “Time-optimal cruising motion”. Using the parametric method of motion planning, the equations for determining the motions are given. Not only the translation motions of tool-center points, but also the orientation motions of tools are discussed. The time-optimal cruising motion planning is also possible for free paths (PTP motions). A general approach to this problem is proposed too. Keywords. Robot motion planning, path planning, trajectory planning, parametric method, path length, time-optimal, cruising motions, translation of tool-center points, orientation changes of tools, PTP motions, free paths 1. INTRODUCTION Robot motions may be described by the Lagrange’s equation H (q) q̈ + h (q, q̇) = τ (1) where H (q) is the inertia matrix of the robot, the quantity q is the vector of joint displacements: q = (q1 , q2 , ..., qn )T The components of the joint displacement of the joint coordinates, h (q, q̇, t) is the nonlinear term containing Centrifugal, Coriolis, gravitational forces, frictions and also the external forces affecting the robot joints (including the forces (moments) acting at the end-effectors, too), τ is the vector of joint torques. The components of τ torques (force, torque restricted by the torque characteristics of T the driving motors. The vector of joint accelerations is: q̈ = (q̈1 , q̈2 , ..., q̈n ) T The q̇ = (q̇1 , q̇2 . . . q̇n ) components of the joint velocity vector are constrained by the possible maximum number of rotations (in time units) of the motors. As it is well known, the maximums of torques (forces) are the decisive factors to determine optimal (dynamical) processes. As it will c 2014 Vietnam Academy of Science & Technology 292 SOMLÓ JÁNOS be clear from what is detailed below, the constraints of joint velocities determine the time-optimal cruising motions. Formulating an optimization problem (for example: to move the robot end-effector center-point from one point to another in the space in minimum time), it can be solved by using the mathematical theory of optimal processes: the Pontriagin’s maximum principle, or Dynamic programming of R. Bellman, or by other methods. It is back to the Lagrange’s equation. In the extended form it is ui = n X Iij q̈j + j=1 n X n X Cijk q̇j q̇k + j=1 k=1 n X Rij q̇j + gi (2) j=1 i = 1, 2, . . . , n; ui min 6 ui 6 ui max In (2): • Iij are the components of the inertia matrix, • Cijk are coefficients for the Coriolis and Centrifugal forces. (These terms are (usually) also nonlinear functions of joint displacements) • Rij is the viscous damping coefficient • gi is the gravitational term, • ui is the force or torque given by the actuator of the i-th joint. In (2) the external forces are not indicated (when needed, they can be included). It is not indicated in the above equations either that the components of joint velocity vectors are constrained, too. Solving the optimal control problem, one may have the solution in the form u = τ = uopt (q̇, q, t). (3) It can be realized in the computed torque manner. But in control practice it is desirable to solve the synthesis problem and generate the control signals depending on the error signals. The error signals are: εi = qid − qi i=1,2,. . . . . . n. The qid signals are the desired values (functions) of the joint coordinates. Their derivatives are: ε̇i , ε̈i etc. Looking at Equation (2) (having in mind that the coefficients are also highly nonlinear) it can be imagined that to solve optimization task is not an easy task. But if the nonlinear effects can be neglected, in principle, for individual robot arms, the well-known optimal “bang-bang” control principles could be applied. As far as we know, it is not very frequently applied in robotics. The reason is: a robot is not an artillery gun, or a spacecraft, or any similar. The effort to solve the optimization problems is too high comparing the benefits. Following this introduction, in the second part of the paper the motion planning problems will be specified and analyzed. Also a state-of-the-art summarization will be provided. The third part outlines the basic results concerning time-optimal cruising motions. In this part the basics of parametric method of motion planning are given, too. In part 4, time-optimal PTP motion is analyzed and solution method presented. In part 5, realization aspects are outlined. In part 6 trajectory tailoring methods will be outlined. In part 7 some conclusions will be given. AN OVERVIEW AND THE TIME-OPTIMAL CRUISING TRAJECTORY PLANNING 2. 293 ROBOT MOTION PLANNING Now, let us return to the rather exact formulation of the robot motion planning problems. The following tasks should be solved: • Path planning • Trajectory planning • Trajectory tracking 2.1. Paths planning Given a robot and its environment, the task is to plan a path which results in a transition of the end-effector center point: a) from one position to another position; b) through a series of positions; c) along a continuous path. During these actions, it may also be required that the orientation of the grippers, or working tools attached to the end-effector should have the given values. Sometimes, the path planning can be approached as a pure geometry problem, but in many cases, the path, trajectory planning and tracking problem are deeply interconnected. In cases when these levels can be considered separately, the optimization problems, with geometric criteria, can be formulated for path planning. For example, the goal may be to get the shortest path to walk over a series of points, or avoid obstacles, or avoid obstacles by volumetric bodies, etc. The powerful apparatus of computational geometry can be used to great extent to solve these problems. 2.2. Trajectory planning Given a path to be followed by the working point (end-effector center-point) of a robot, and the corresponding orientations of tools attached to it. The dynamic characteristics of robot joints are known, including the constraints on torques, forces available at the actuators. The limit values of the joint speeds, the limit values of speeds in Cartesian coordinate system are also given. Possibly, the same is given for accelerations. Complex knowledge is available about the technological process characteristics (requirements, forces, etc.). The most general and practical requirement is to find the motion, giving minimum time for performing the task. Another goal may be to find the motion requiring minimum energy. 2.3. Trajectory tracking The task of the trajectory tracking, as it was mentioned above, is to plan the control action that guarantees the realization of the desired trajectories with the necessary accuracies. 294 2.4. SOMLÓ JÁNOS Optimal trajectory planning. State-of-the-art In the introduction, the minimum time motions are reviewed. Bellow, more details is given. The time optimal control problems can be classified into three categories: 1. Motion on constrained path between two endpoints; 2. Motion in free workspace between two endpoints; 3. Motion in a free workspace containing obstacles. Concerning the robot motion in free workspace, a number of results are available. In Geering, Guzzella, Hepner, Onder (1986) [3], it has been shown that the time optimal controls of motion in free workspace, are regularly that of switching nature. The maximum torques (forces) are switched for accelerating and decelerating in an appropriate manner. A huge number of papers were dealing with different aspects of the above problem. An overview can be found in S. K. Singh (1991). In Singh’s paper a general numerical method to the solution of similar optimization tasks was proposed, too. Discretion and the use of nonlinear programming method form the essence of this approach. In many of the application problems the motion is constrained to a given path. Examples include arc welding, milling, grinding, painting, debarring using robots. Several researchers have addressed the problem of this constrained motion of robots. Recently, it has turned out that the parametric description of the robot motion is one of the most promising ways of the investigation of constrained motion. The most detailed outline of this method can be found in K. G. Shin, N.D.McKay (1991) [7]. When using the parametric method, the differential equations characterizing the motion of the joints of an n-degree of freedom robot can be transformed to a form where instead of n joint coordinates (q1 , q2 , . . . , qn ) only the one path parameter (λ(t)) is present. The n non-linear, coupled (second order) differential equation of joint motion is transformed to a second order nonlinear differential equation formulated for one parameter. Shin, McKay, and others, based on the parametric description, proposed an approach to the solution of the time-optimal control of constrained motion of robots. Shin and McKay also used the parametric description method to the determination of other than the time-optimal motion. An example is the solution of optimal control problem using minimum energy criterion. When using the method of parametric description, usually, the parameter is the length (λ(t)) along the path. In the present paper this approach will be used to a high extent, with the goal of investigating cruising motion rather than investigating dynamics. In Paragraph 3 of the paper, some introduction to this method is given. For those who are unfamiliar with the parametric method, they should be asked (among other literature) to read the third Paragraph. J. Podurajev and J. Somlo (1993) [8] used a parameter the time derivative of which is proportional to the square root of the entire kinetic energy of the robot mechanism. Using this parameter, the equation of motion becomes extremely simple. This approach made possible to develop optimal robot control, according to energy criterion in a straightforward manner. Dynamic optimization problem may be solved using the parametric description of the dynamics of robots (see: Somló, Lantos, P.T. Cat [2]). Then Equation (2) may be transformed to ui = Mi µ̇ + Ni µ2 + Ri µ + Si , i = 1, 2, ..., n (4) AN OVERVIEW AND THE TIME-OPTIMAL CRUISING TRAJECTORY PLANNING 295 dµ where µ = dλ dt = λ̇, µ̇ = dt = λ̈ Taking into account Equation (2) results in Mi =Mi (λ) = n X Iij dfj dλ Iij d2 fj X X dfi dfk + Cijk 2 dλ dλ λ j=1 Ni =Ni (λ) = Ri =Ri (λ) = n X j=1 n X j=1 n n j=1 k=1 Rij (5) dfj dλ Si =Si (λ) = gi The above relations are obtained taking into attention that q̇j = d2 f dfj dλ dfj dfj = λ̇ = µ dλ dt dλ dλ df and q̈j = dλ2j µ2 + dλj µ̇ Having the system differential Equation in the form (2) or (5) the processes in the system may be investigated. The constraints of the quantities have decisive effects on the performances. The optimal systems theories devote special attention to the limit values of the torques (forces) which determine the best values of performance characteristics (motion times, energy consumptions, etc.). Our opinion is that in robotics the constraints of joint velocities have a role much more important than theirs when considered. Furthermore, these effects may be fully investigated during the more complicated optimization approaches. So, the investigation and use of velocity constrained motions have a bright future in robot motion planning. The above demonstrated parametric equation of dynamics of robot motion was used in Somló, Podurajev (1993), [11] (see also: Somló, Lantos, P.T. Cat (1997), [2]) for the determination of timeoptimal motions. It was also shown that the motion with minimum energy consumption may also be solved. Recently, the parametric equation of robot motion dynamics was applied to develop effective approaches to the determination of optimal robot motions. By Verscheure, Demeulenaere, Swevers, Schutter, Diehl (2008) [16] a complex optimization criterion was proposed. This contains components representing the time, energy, etc. aspects. Detailed investigation of the state-of-the-art was also given in the above paper (38 items for reference). Freely available computer program is provided by the authors (Verscheure “Time-optimal trajectory planning. . . ” [Online]. . . ) [17], too. In the paper, the time-optimal cruising trajectory planning problem is introduced and its basic relations presented. Shortly, the cruising motion is described when a robot end-effector performs some application tasks and during that moves with velocity slowly changing absolute value. These changes are so slow that the times of transient motions from one state to another may be neglected. That is the motion times, which may be estimated by the sum of times of motions of small constant velocity sections. It seems that the above regime is very close to the working processes for the most of the industrial robots. Of course, the validity should be investigated. For that the theoretical apparatus (as it was mentioned) exists. Practical experience and measurements may also be clear whether the planning assumption is valid or not. have the importance. In Somló J. and Poduraiev J. (1993) [11], as it was mentioned, a method is presented where, the parametric method, it is solved that both acceleration and deceleration of the robot motion their limit values in the transient motions (see also Somló J., Lantos B., P.T. Cat (1997) [2]). 296 The proposals for trajectory planning in technical literature are based on rather simple appro Below, the method proposed in K.S. Fu, R.C. Gonzalez, C.S.G. Lee (1987) [12] is discussed. (S Ó Jin ÁNOS approach isSOML outlined L. Sciavicco and B. Siciliano [13].) Later, in this paper, it is shown that a cruising motion is time-optimal when at least one of the joint velocity values is at its limit value. In Figure 1, transient and cruising motions are shown together. Of course, on the cruising part shown in the Figure sections may exist which can be considered as transients. Taking into account that the above ideas (namely: cruising and transient) are provisional the exploitation characteristics have the importance. vB A0 B0 A Run in Initial point B Cruising part vA B B0 Run out A A0 Final point Transient part Figure 1. The cruising and transient parts of a path In J. Somló and J. Poduraiev (1993) [9], as it Figure 1: The cruising and transient parts of In this approach, the coordinates of a series of points in Cartesian coordinate system are given was mentioned, a method is presented where, using a path corresponding joint coordinates values are determined by inverse transformation. If the the parametric method, it is solvedpositions, that both accelspeeds and possibly accelerations (deceleration) are known in the given points (and the motion desired time from point to point), paths for motions joints satisfying eration and deceleration of the robot are of atmotion their limit values in thethe transient (see the given conditio be determined using proper-order splines. also Somló J., Lantos B., P.T. Cat (1997) [2]). i (t i ), qion (t i ), qbased (t i +1rather ), q i (ti +1simple ) joint coordinates and speed val For example, if in two points the qi are The proposals for trajectory planning in technical literature apare given, a third-order spline proaches. Below, the method proposed in K.S. Fu, R.C. Gonzalez, C.S.G. Lee (1987) [10] is discussed. (Similar approach is outlined in L. Sciavicco and B. Siciliano [11].)qi (t ) = a0 i + a1i t + a 2 i t 2 + a3i t 3 In this approach, the coordinates ofbea used series points in Cartesian system are given. may forofpath determination of the coordinate motion. Because The corresponding joint coordinates values are determined by inverse transformation. qi (t ) = a1i + 2a2i t + 3a3i tIf2 ; the joint positions, speeds and possibly accelerations (deceleration) are known in the given points (and, also, the to a0i point), , a1i , a2i , athe be determined from conditions the 4 equations obtained at t= the desired time of motion from point paths forvalues jointscan satisfying the given 3i parameter t=ti+1splines. . When the accelerations are also specified, fifth-order spline with six adjustable paramete can be determined using proper-order be used. This method may also be used if N points are specified along the paths (see [13]. For example, if in two points the qi (ti ), q̇i (ti ), qi (ti+1 ), q̇i (ti+1 ) joint coordinates and speed values These approaches are rather simple, but need some justification. Sometimes it may turn out th are given, a third-order spline trapezoidal speed profile is the adequately solution. This can be the case, for example, whe technological process constrains the speed. But, it can turn out only after the motion featur analyzed general, the speeds, the time of motion between the point qi (t) = a0i in + detail. a1i t +Indeed, a2i t2 +ina3i t3 acceleration, deceleration relations are unknown. In fact (see later) these quantities (among factors) depend on the configuration of the paths. So, the proper order of investigations is to may be used for path determinationdetermine, of the motion. Because in a systematic way, the above quantities, and then goes on with the solution of pla q̇i (t) = a1i + 2a2i t + 3a3i t2 ; the a0i , a1i , a2i , a3i parameter values can be determined from the 4 equations obtained at t = ti and t = ti+1 . When the accelerations are also specified, fifth-order spline with six adjustable parameters can be used. This method may also be used if N points are specified along the paths (see [13]).. These approaches are rather simple, but need some justification. Sometimes it may turn out that the trapezoidal speed profile is the adequately solution. This can be the case, for example, when the technological process constrains the speed. But, it can turn out only after the motion features are analyzed in detail. Indeed, in general, the speeds, the time of motion between the points, the acceleration, deceleration relations are unknown. In fact (see later) these quantities (among other factors) depend on the configuration of the paths. So, the proper order of investigations is to try to determine, in a systematic way, the above quantities, and then goes on with the solution of planning problems. The time-optimal cruising trajectory planning method outlined below solves these problems. 297 AN OVERVIEW AND THE TIME-OPTIMAL CRUISING TRAJECTORY PLANNING 3. 3.1. TIME-OPTIMAL CRUISING TRAJECTORY PLANNING Motion on a given path First, the case is analyzed when the path to move on is given. Assumed that the acceleration, deceleration abilities of the robot are so high, and that the transient motion part (see Figure 1) may be neglected. This condition, usually, is valid for most of the industrial robots and applications. In the next paragraph of the paper, one of the simplest cases to demonstrate the basic ideas is under discussion. 3.1.1. Time-optimal cruising motion planning for polar manipulator Figure 2, aplanning 3-degrees of freedom cylindrical robot are shown. In Figure 3 the rotational and 3.1.1 Time-optimalIn cruising motion for polar manipulator. horizontal translation degrees areshown. given.In This is and named as polar manipulator. In Figure 2, a 3-degrees of freedom cylindrical robot are Figuremechanism 3 the rotational Figure 2: Cylindrical robot horizontal translation degrees are given. This mechanism is named as polar manipulator. y A r z C B q2 ϕ q1 x Figure 2: Cylindrical robot Figure 2: Cylindrical robot Figure 3: Polar manipulator y For time-optimal cruising trajectory planning, a general method in [2, 11] is proposed and its C B A below. The basic idea outlined authors want to move the end-effector working point (point C) from point A to point B along the path indicated in the Figure. The equations of the direct geometry are: x =q2 · cos q1 , y =q2 · sin q1 (6) To realize the motion, the equations of the inverse geometry are needful. These are: y q1 =arc tan x p 2 q2 = x + y 2 (7) At any given point, the velocity is directed tangentially to the path. The absolute value of the velocity is determined by the components given by the joints. Namely, the rotational joint results in a component |v|1 = q2 q̇1 (8) The translation joint motion results in a component |v|2 = q̇2 (9) 298 SOMLÓ JÁNOS The absolute value of the velocity is |v| = q |v|21 + |v|22 (10) Now, let us try to determine the possible maximum absolute value of velocity. Let q̇1 max and q̇2 max be the maximum value of joint velocities. Clearly, in order to increase the absolute value of the velocity, the joint velocities should increase.x Letq us consider the case demonstrated in Figure 4. q Increasing q̇2 to his maximum value q̇2 max y qp q |v|2 max = (q2 q̇1 )2 + (q̇2 max )2 (11) y q are arc interconnected because the motion should be directed The components of the velocity vector x along the tangent to the path. So, to get |v|2 max is very easy as demonstrated on Figure 4. q2 x y ∆λ C λ1 y q2 max v2 max v1 max C1 B C2 A q2 q2 q1max q1 x B xb,yb λ xi+1,yi+1 α ǻȜi A Įi xi,yi xa,ya Figure 4: Time-optimal motion Figure 4: Time-optimal motion At any given point, the velocity is directed tangentially to the path. The absolute value of the velocity is determined by the components given by the joints. Namely, the rotational joint results in a (If analytical form is required, the following relation can be used to determine the required component quantities |v|v1 q q = |tan(αc − q1 )| |v|2 (12) Here αc is the angle of the path relating to axis x (see, α on Figure 4). It will be shown below that v q this step is unnecessary to perform.) Increasing the absolute value of velocity more the maximum of other component may be reached v |v|1 max = q2 q1 max v v (13) It is clear that this value may not be realized because at that the other component would exceed q1max q2 max its limit value. So, the optimal velocity value is q |v|optq2 = M in [|v|1 max ; |v|2 max ] max (14) AN OVERVIEW AND THE TIME-OPTIMAL CRUISING TRAJECTORY PLANNING 299 In the given case this is |v|2 max . Let us now try to get an analytical expression for the realization of the above. By the derivation of (6) we get ẋ = −q2 [sin(q1 )] q̇1 + [cos(q1 )] q̇2 and ẏ = q2 [cos(q1 )] q̇1 + [sin(q1 )] q̇2 (15) Solving (15) for q̇1 and q̇2 yields xẋ + y ẏ xẏ − y ẋ q̇1 = p and q̇2 = 2 x + y2 x2 + y 2 (16) Let in a point (for example, in C) world coordinates of which are xi and yi the angle of the tangent of the path with axis x be αi (earlier we used for the same αc ). Then ẋ = |v| cos αi and ẏ = |v| sin αi (17) Substituting the quantities into (16) results in q̇1 = S1 (xı́ , yi , αi ) |v| and q̇2 = S2 (xi , yi , αi ) |v| (18) where S1 and S2 are the quantities obtained by the substitutions. So q̇1 = S1 (xı́ , yi , αi ) |v| and q̇2 = S2 (xi , yi , αi ) |v| (19) And for the maximum values we get q̇1 max = S1 (...) |v|1 max and q̇2 max = S2 (...) |v|2 max (20) Accordingly, |v|1 max = q̇1 max q̇2 max and |v|2 max = S1 (....) S2 (....) (21) For the determination of the optimal velocity value Equation (14) is valid. According to the above, in every point of the paths the time-optimal cruising velocity can be determined. This velocity depends on the geometry of the paths (world coordinates of the points and direction of the tangents to the paths) and on the maximum possible values of the joint velocities. We name dominant the joint the maximum velocity of which determines the optimum. The dominancy may change in some points. In these points both joints result in the same maximum velocity (for the given example in these points |v|1 max and |v|2 max are equal). In fact, Equations (15) and (16) are the rows of the Jacobian matrices. So, all the above can be interpreted from the point of view of using Jacobian matrices. This has been done in Somló, Lantos, P.T.Cat [2]. In this case, it is to use ẋ = J(x)q̇, x = (x, y)T , q̇ = J−1 (q)ẋ, and q = (q1 , q2 )T where J and J−1 are the Jacobian and inverse Jacobian matrices respectively. (22) 300 SOMLÓ JÁNOS 3.1.2. Parametric method of trajectory planning As mentioned above, it is proposed to solve the time-optimal cruising trajectory planning for the whole path, but how doing that is not outlined in a systematic way. In the followings, this task is trying to be settled. In the introduction of the paper the differential equations of the robot motions are described using a parametric approach. The following introduces this approach. Shin and McKay in [7, 8] proposed to use a parametric approach for robot planning problem. They proposed as a parameter the path length. It is clear that at any form of description of any path the world coordinates may easily be expressed as functions of path lengths. Indeed, the distance of any two points in a plane or in 3D space may be easily computed. Representing the world coordinates of a robot as a function of the determined path lengths, the parametric description problem is solved. The inverse transformations connect the joint coordinate values with the world coordinates values. So, if the last ones are expressed by the parameter, it leads straight to the opportunity to express also the joint coordinates as functions of the parameter. This is the essence of the parametric approach. In fact, the parameter is an independent variable for the planning. Just back to the above analyzed example, let the world coordinates in a point of the path be xi and yi Let in the next (nearest) point of the path the coordinates be xi+1 and yi+1 . The distance between the two points is p ∆λi+1 = (xi+1 − xi )2 + (yi+1 − yi )2 ; yi+1 − yi αi = arctan xi+1 − xi (23) (24) For the point with index (i − 1) we have ∆λi = p (xi − xi−1 )2 + (yi − yi−1 )2 (25) Let us assign to every point which we consider a serial number. This numbers are: i=1,2, . . . N, and are also used as indices of the points. The last index value is N. The length of the path until point with index k is indicated asλk . Clearly λ1 =0. For others λk = k X ∆λi (26) i=2 In the last point of the path k = N and λN is the overall length of the path for which we will simply use λ. In any point of the path the λk value can be computed. λk belongs to the xk and yk world coordinates values. By inverse transformation the q1k and q2k values may be computed. In such a way the following functions may be determined: q1 = f1 (λ) andq2 = f2 (λ) (27) Of course, in this way the functions determined on discrete points are obtained. This is very much suitable for robot control tasks where, usually, similar representations are used. But, if necessary, sometimes, analytical relations may also be developed. The above example, and motion along a straight line are under consideration (from A to B; Figure 4). cos α In this case x = xA + λ · cos(α) and y = yA + λ · sin(α); arc tan yxA +λ +λ sin α ; and q2 = f2 (λ) = A p (xA + λ cos α)2 + (yA + λ sin α)2 ;

An overview and the time optimal cruising trajectory planning

Nội dung