What is meant by collision free path

Automated collision-free task sequencing for industrial robots


1 Otto von Guericke University Magdeburg Faculty of Computer Science Master thesis Automated Collision-free Tasksequencing for Industrial Robots Author: Maximilian Kühne Supervisor: Prof. Dr. rer. nat. Frank Ortmeier Jun.-Prof. Dr. Michael Kuhn M.Sc. Nadia Schillreff M.Sc. Tim Gonschorek Institute for Intelligent Cooperating Systems November 18, 2020

2 Kühne, Maximilian: Automated Collision-free Tasksequencing for Industrial Robots Master's thesis, Otto von Guericke University Magdeburg, 2020.

3 Summary The robot manipulators used in industry usually offer a certain degree of freedom due to the number of their joints, which gives them the opportunity to reach any point in their workspace. You can even approach points behind obstacles. However, if a work area is free from such obstacles, there can be many different positions (configurations) for the manipulator for one point. If you consider the task that is to be performed by the robot on a workpiece, this usually results in an additional degree of freedom. A large number of possible solutions follow from this. This means that an enormous calculation time can arise for an automated optimization of the task planning. If you want to make sure that the robot does not collide with itself or with the workpiece or other objects during this optimization, this increases the time required again. Therefore, in most cases the search space is simplified and the collision check is only carried out at the end. In this master's thesis, a sequence optimization is to be carried out purely in the configuration room of the robot. It should be possible to determine all paths offline and collision-free with the help of random path planners such as RRT. The problems that arise with regard to the calculation times should be reduced with the help of parallelization. The following questions arise from this approach: (i) How can parallelization be integrated? (ii) What influence does the shape of the workpiece have on the optimization? (iii) Can the planning of the machining of a workpiece be implemented better automatically than planning by humans?



6 Table of contents Appendix 79 References 85 ii

7 1 Introduction In modern industry, the path has been going for many years to replace humans with simple, repeatable tasks with human-like machines. Such a machine can be a robot manipulator. It is designed to resemble a human's arm. A work area is spanned by a different number of joints. In this workspace, the robot can perform various tasks with the help of a wide variety of tools. For example, he could carry out welding, cutting or painting tasks on a workpiece placed in the work area. So that the robot knows what to do, it is trained by a human. There are two different options for a learning process [7]. The program sequence is either created separately from the real robot and is tested in a simulation environment (offline programming). The second possibility is that the manipulator is guided by the human hand or that the desired points are specified by the person (online programming). This process is also known as teaching-in or playback [6]. Regardless of which learning process is chosen, the person carrying out it needs an appropriate experience. This experience is not only required to be able to program the robot at all, but also to specify an efficient sequence of tasks. This efficient sequence would in turn save energy and time and counteract wear and tear on the robot joints. The programming of the machining of a workpiece is associated with a lot of effort, which means that robots are mostly only used in large-scale industry and mass production. There the respective number of pieces justifies the necessary effort. The idea for the master's thesis and the project came from Sergey Alatartsev's doctoral thesis [3]. In his approach to solving the problem to determine optimal processing, a sequence was first determined with the aid of the Cartesian distance before suitable entry configurations could be determined in the configuration space of a robot. A collision-free path planning between the individual tasks was only carried out at the end of the calculations. This was possible because it was assumed that there were no other objects in the work space. The movements should also run collision-free when performing the tasks on the workpiece. This work refers to the similar concept. However, from the outset, collision-free planning is carried out in the configuration room of the robot. Various approaches could be chosen as a collision-free path planner. In 1

8 1 Introduction In this context, the algorithm of the Rapidly Exploring Random Tree and the Probalistic Road-Map should be used. It should be evaluated whether such an implementation is possible and how long offline planning can take compared to the implementation of the doctoral thesis. In addition, a comparison should be made between the resulting automated optimization solution with solutions from a survey of test persons. Structure of the master's thesis The master's thesis is divided into five further chapters. Starting in Chapter 2 about the theoretical basics, Chapter 3 introduces the concept of the previous doctoral thesis [3] and the current concept. Chapter 4 explains the implementation of the concept presented. The test setup and the evaluation of the results from the tests can be found in Chapter 5. Finally, reference is made to the results obtained and the questions asked. 2

9 2 Theoretical Basics The interaction between robot and workpiece is created in the work cell. As with human editing, this work area should be designed according to the two most important components, offer enough space and provide good positioning for these two components. Examples of such structures can be seen in the appendix. A table that holds the workpiece in the right place, one or more conveyor belts that bring the workpiece into the cell, and walls that separate the work space for safety reasons would have to be added to the surroundings. That would create a functional work cell. For the current problem, it is sufficient to consider the two most important components with their positions and orientations to one another. All definitions and formulas described in this chapter are based on the definitions from the doctoral thesis [3]. 2.1 Differences between the configuration and work space When processing a workpiece and using a robot manipulator with a certain number of joints, two different spaces are created in which an interaction takes place. The first is the Cartesian space or also known as the work space. This describes the position of objects in three-dimensional space [19]. Definition 1. The T-Space SE (3) describes the space that is spanned by the Cartesian coordinate axes. The positioning in R 3 is linked to a possible orientation SO (3), so that SE (3) = R 3 SO (3) applies. The basic representation of a point p SO (3) is a homogeneous transformation matrix. The point p can also be embodied as a 6-dimensional vector: p = (x, y, z, α, β, γ). On the basis of this description, a point or an object that has its center at this point has its own local coordinate system, which is based on the specified translation 1 and rotation 2 from 1 displacement in an original coordinate system based on the values ​​of the X, Y and Z Axis 2 Rotation around the axes of a coordinate system, which depends on the convention and is indicated by the angles α, β, and γ. 3

10 2 Theoretical fundamentals of the original coordinate system. The specified angles represent the three independent Euler angles. The order of these angles depends on a convention. Conventions define the axis via which a rotation of the object or the associated coordinate system is to be carried out. In addition, these conventions define whether it is rotated around its own coordinate system (intrinsic) or in another coordinate system (extrinsic). In this context, the ZYZ Convention and the Roll-Pitch-Yaw Convention are used. Figure 2.1: Exemplary representation of a possible point in the working space given by (x 0, y 0, z 0, α, β, γ) and two possible configurations c 1 = (Θ 1, Θ 2, Θ 3, Θ 4, Θ 5 , Θ 6) and c 2 = (Φ 1, Φ 2, Φ 3, Φ 4, Φ 5, Φ 6) 3 The configuration space should be mentioned as the second space that plays a role in this work. It depends on the number and type of joints in the robot. Definition 2. The C-Space C describes the space that is spanned by the independent axes of a robot. Thus, C = R n, where n stands for the number of independent joints of the manipulator. For a robot with the degree of freedom of six independent axes, this means C = R 6. Thus, a possible configuration c C can be represented as follows: c = (Θ 1, Θ 2, Θ 3, Θ 4, Θ 5, Θ 6) . Each entered value Θ i stands for an angle that the respective joint has in one position of the robot. Both rooms are connected to each other (see Figure 2.1). So there are 3 [3] 4

11 2.2 Transformation matrices of bodies for each point in space a configuration of the robot with which it can reach it. However, there are certain requirements that must be met for this. These are explained further in the following sections. The variable R in the graphic represents the length of a tool used. 2.2 Transformation matrices of bodies In addition to the embodiment of a point p SE (3) as a vector, there is another possibility of representation. The rotation of a point can be described in a so-called rotation matrix independently of a convention. This 3x3 matrix contains the rotations in radians via predefined coordinate axes of a reference coordinate system and looks as follows: r 11 r 12 r 13 Rotation 3x3 = r 21 r 22 r 23 r 31 r 32 r 33 There are three values ​​in this matrix that are for the independent rotations about the coordinate axes. These are also known as Euler angles and can be read from the rotation matrix using the respective convention. The entire rotation matrix is ​​also created from the product of all three independently executed rotations according to a convention. For example: R x (α) = 0 cos (α) sin (α) 0 sin (α) cos (α) cos (β) 0 sin (β) R y (β) = sin (β) 0 cos (β ) cos (γ) sin (γ) 0 R z (γ) = sin (γ) cos (γ) rotation 3x3 = R x (α) ry (β) rz (γ) Since this is not sufficient for the representation of the point, the translation is required in the same reference coordinate system. This vector describes the shift over the respective axes of this coordinate system. It is structured as follows: x translation 3x1 = y z 5

12 2 Theoretical basics The homogeneous transformation matrix is ​​formed from the combination of rotation and translation. This sets a local coordinate system in the point, which is firmly anchored to a world coordinate system. This allows it to be transferred to other reference systems via matrix multiplication. () Rotation3x3 T ranslation T ransformation 4x4 = 3x Via matrix multiplication with other transformation matrices, a point can be represented in different coordinate systems. This makes it possible to carry out further calculations with the help of this transformation matrix. In this way, these matrices can be used as the basis for determining the solutions of an inverse kinematics. Figure 2.2: Representation of a scenario and associated coordinate systems So that there are no errors in later calculations, these Cartesian coordinates should be in a common reference system. Predefined formats such as the world or robot coordinate system are available for this. These make it possible to use predefined and fixed transformation matrices. The mentioned world coordinate system thus describes the origin 6

13 2.3 Structure of a robot and the various kinematics according to which all other coordinate systems are aligned. The whole is shown as an example in Figure 2.2. The coordinate system marked in white is the world coordinate system (usually in the origin). The other three coordinate systems are freely definable. At the bottom left you can see the robot coordinate system, which shows the positioning and orientation of the robot. At the end of the robot (EOA) there is a coordinate system for the tool. This can be used for better positioning of the tool. The third coordinate system, in this example, is a workpiece coordinate system. The paths for the tasks to be performed on the workpiece can be anchored in this. These paths are automatically shifted when the workpiece is moved in space. 2.3 Structure of a robot and the different kinematics The robots used in industry differ in two types, which in turn stand for a specific type of movement and design of the manipulator. On the one hand, there are industrial robots that are built on the principle of serial kinematics. This principle is also known as an open kinematic chain. Each segment is connected to a next segment via a joint. The structure is similar to that of a human arm (see Figure 2.3 (a)). At the end of the robot (EOA) there is a holder for a tool to be able to carry out a selected task. On the other hand, there are robots that are built on the principle of a closed kinematic chain (parallel kinematics). Several joints are connected to the base of the robot. There are also segments on these joints. A tool platform is attached to these segments. Both types have their advantages and disadvantages. A deployment should be carefully weighed against the task to be performed. Since robots with serial kinematics offer greater flexibility and a larger workspace with an increasing number of joints, these are considered in this work. It is possible for a robot to reach different points in Cartesian space. Certain properties of the manipulator play a role here. These have an influence on the size of the possible work space. A description of the properties can be found in the manufacturer's data sheet (see Figure 2.3). On the one hand, the properties relate to the number and type of joints. On the other hand, the sizes of the individual segments that are located between the joints are described. The segments can be of the most varied of shapes and thus form the static size for the definition of the work area. Different robots have different types of joints, which can also be present in different numbers. This also restricts the working space. The joints have an influence on the achievable points 7

14 2 Theoretical Basics in Space. As a result, a robot can have swivel joints which rotate the assembled segment about a defined axis. Since the assembled segment can be connected to other subsequent segments, this rotation affects all parts. Another type of joint is the sliding joint. These also have an influence on a segment and the connected subsequent segments by either extending or retracting them. In addition, the joints of the robot have, in most cases, a certain limited mobility (see Figure 2.3 (b)). Otherwise there is a risk of self-collision or overloading the specified payload of the robot. (a) Data for the work area (b) Data for the respective axes Figure 2.3: Excerpts from the data sheet for the KR forward kinematics The information about a robot can be summarized in the Denavit-Hartenberg parameters (D-H parameters) [19]. With the help of these parameters, the individual transformations are defined for each joint. A chain of transformation matrices is created. These matrices are used to shimmy through the kinematic chain of the robot [13]. This makes it possible to make explicit statements about the positioning of the robot. The aim of the whole is to create a simplified model of the robot. Table 2.1 shows the parameters for the robot used. Here, θ i stands for the rotation about the axis z i 1, so that the axes X i 1 and X i are aligned in the same way. The distance d i is the shift of the coordinate system K i in K i 1 on the Z-axis. The value of a i is also a shift in the coordinate system K i in K i 1 on the X axis of K i. The angle value α i indicates the rotation of the new X i axis, so that the Z axis has the same axis of rotation as the actual joint. The values ​​from the table can be taken over directly into the determination of the transformation matrices. A transformation matrix T i 1 i SE (3) 4 [2] 8

15 2.3 Structure of a robot and the different kinematics Joint d i a i α i θ i π π π π π Table 2.1: Table of the D-H parameters from a coordinate system K i 1 to the coordinate system K i always consists of two translations and two rotations. The result provides information about the position and orientation of the new coordinate system.cos (θ i) sin (θ i) 0 0 red zi 1 (θ i) = sin (θ i) cos (θ i) T rans zi 1 (di) = diai T rans xi (ai) = red xi (α i) = 0 cos (α i) sin (α i) 0 0 sin (α i) cos (α i) T i 1 i = Rot zi 1 (θ i) T rans zi 1 (di) T rans xi (di ) Rot xi (α i) If you multiply several transformation matrices you can get information about the position and the orientation of the respective joint. By multiplying all the individual transformation matrices, the position of the tool center point (TCP) or the point at the end of the robot arm (EOA) can be determined using a given robot configuration. This procedure is known as forward kinematics. T 0 n = T 0 1 T 1 2 T n 1 n 9

16 2 Theoretical Basics Definition 3. The forward kinematics F K enables a position and orientation of the end effector of the robot p SE (3) to be calculated from a configuration of a robot c C. So F K: C SE (3) applies. Inverse kinematics Opposite the forward kinematics is the inverse kinematics (IK). Based on a given point in Cartesian space, it tries to determine a possible configuration according to the given D-H parameters of the robot. Depending on the position of the point, it can be reached from several possible positions of the robot [20]. The selected reference point (TCP or EOA) has exactly the same position and orientation as the given point. Definition 4. The inverse kinematics IK makes it possible to calculate a set of possible solutions for the configurations of the robot C C from a position and orientation of the end effector of a robot p SE (3). So IK: SE (3) C with C C. (a) Θ 1 (b) Θ 2 and Θ 3 Figure 2.4: Determination of solutions of the IK according to the geometric method To determine a set C of possible solutions of the inverse kinematics , the geometric method can be used. This is one of three possible methods for determining the inverse kinematics. A transformation matrix that is representative of a target point p SE (3) is used as input for these methods. The geometric method applies knowledge of the structure of the robot. The law of sines and cosines are used to determine the individual joint angles. Due to the special construction of a 6-DOF 5 manipulator, the determination of possible configurations can be reduced to two different calculations. Due to the specific structure of the robot, the last three axes intersect at one point. This point is also called the wrist or wrist 5 Degrees of Freedom = the robot's degree of freedom from 6 independent joints. 10

17 2.3 Structure of a robot and the various kinematics called Center Point. You can use this point first to determine the first three joints and thus the positioning of the robot. The first possible solution to the joint angle of the first axis (Θ 1) is obtained by pointing the arm directly at the point of the wrist in the X-Y plane. The angle is determined using the cosine or sine theorem from the X or Y values ​​and the distance D to the point (see Figure 2.4 (a)). A second possible solution to the first joint value is obtained by rotating the arm another 180. The values ​​for joints 2 and 3 (Θ 2 and Θ 3) are searched for in the plane that results from the combination of the X-Y plane and the Z axis. Similar to before, the cosine and sine theorem are used, this time in relation to the previously determined value D from the X-Y plane and the Z value of the point of the wrist. In addition, the length that results from the two values ​​(see Figure 2.4 (b)) must be calculated. As with the previous calculation, there is not always a clear solution for the two joints. So the third joint can be either up or down, which leads to different values ​​of Θ 2 and Θ 3. After you have determined the first three joints and thus the position of the robot, you can use these values ​​to calculate the last three joints and thus an orientation of the hand and the tool [20]. This results in up to eight possible and different positions of the robot. These positions, according to which the IK solutions are divided, can look as follows: ˆ ˆ ˆ forwards or backwards - alignment of the arm based on the tower axis (joint 1) directly to the point or rotated by 180 elbows up or down - joint angle selected so, that the first arm segment points upwards or downwards (joint 2) and accordingly the other arm segment is directed downwards or upwards (joint 3) wrist front or back - similar to the tower axis, alignment of the fourth joint directly to the point or at 180 degrees turned. The joints mentioned are related to a 6-DOF industrial robot. If there are more joints, it is important to note which joints lead to rotation and which to kink a segment. If fewer joints are available, the possible positions of the robot are limited. The following figure 2.5 shows examples of the positions described. The robot, which was used here as an example, has limited mobility in some joints. If you use a different robot model that allows even more mobility in the joints, you could get further solutions for certain points. In the individual captions, the first mentioned directional designation refers to the tower axis, the second to the elbow and the third to the wrist. 11

18 2 Theoretical basics (a) forward, up, front (b) forward, up, back (c) forward, down, front (d) forward, down, back (e) backward, up, front (f) backward, up , at the back Figure 2.5: Possible positions of a robot manipulator for a Cartesian position 12

19 Movement of a robot 2.3 Structure of a robot and the different kinematics In order to be able to make a movement from the individual points or the configurations of the robot, a sequence of these should first be described. Definition 5. A continuous sequence of points (p 1 ,, p n) in three-dimensional space is called P ath EE (k). The parameter k [0, 1] maps onto a point p i SE (3). This path is representative of the robot's end effector. This end effector can be either the TCP or the EOA. Hence P ath EE: [0, 1] SE (3). Definition 6. A continuous sequence of configurations (c 1 ,, c n) in the configuration space of the robot is called P ath R (k). The parameter k [0, 1] maps to a configuration c i C. This path describes the movement of the axes of the robot. Thus P ath R: [0, 1] C. Theorem 1. With the help of inverse kinematics, a P ath EE can be converted into a P ath R. It is true that the solution for P ath R is not unique. There are therefore different solutions. A path P ath R can also be converted into a P ath EE using forward kinematics. Here the solution is clear. As for the forward and inverse kinematics, the limitations of the individual joints play an important role in the movement of the robot. Also described in the characteristics of a manipulator are the maximum possible speeds of the joints and, associated with this, also the maximum possible accelerations. There is still the alternative of defining these properties yourself. However, you should only limit it and not exceed it, otherwise the robot will be affected. In order for the robot to move from one configuration to the next, it should know which movement pattern it should use to perform this movement. A distinction is made between the patterns in two types, for which there are again different profiles, regardless of the type. In both types, all joints start moving at the same time. There is the asynchronous movement in which all joints rotate until they have reached their target position. Since each joint has different maximum possible speeds and different distances to be covered, each joint will be in motion for a different length of time. This can make the robot's movement difficult to predict as it tries to get all of the joints to rotate at a relatively high speed. The second type is synchronous movement. Here the movements of each joint are adapted to the joint that has been in motion the longest. Thus, all joints start moving at the same time and they all stop at the same time. This means that the speeds of the joints are usually significantly reduced. Regarding the possible profiles, it should be mentioned that these can be freely defined 13

20 2 Theoretical basics (a) Triangular profile (b) Trapezoidal profile Figure 2.6: Examples of the most basic movement profiles can. Only the maximum values ​​for speed and acceleration should be observed. The simplest profiles are on the one hand the triangle and on the other hand the trapezoidal profile. With the triangular profile (see Figure 2.6 (a)), the speed is continuously increased up to a certain value and then steadily decelerated again. In the second profile (see Figure 2.6 (b)), the speed is continuously increased up to a certain value, then held for a calculated period of time and then steadily decreased again. Here, too, the rule applies that the speed should not exceed the maximum specified. Definition 7. The movement of the robot is stored in the movement profile BP (t). There is a time variable t [0, T], which describes a continuous course of an executed movement. T is the total duration of the movement. A parameter k is mapped from BP, so that BP: [0, T] [0, 1] applies. A distinction can be made between different movement profiles. In this context, on the one hand, there is BP EE which interprets the movement based on the requirements of the work order to be completed. On the other hand, BP R, which is restricted by the given robot. If an end effector is used as a reference for the movement of the robot, an attempt is made to adjust the configuration accordingly so that a continuous movement is created for the robot [21]. For this purpose, the joints must perform a rotation in the case of swivel joints or an advance in the case of translational joints at a certain point in time. This is called a trajectory. Definition 8. Using a motion profile BP, a given path becomes a trajectory. So T raj EE (t) = P ath EE (BP EE (t)) with a t [0, T] is the trajectory of the end effector. 14th

21 2.3 Structure of a robot and the different kinematics Definition 9. The trajectory T raj R is created using the BP R. Thus, T raj R (t) = P ath R (BP R (t)) with a t [0, T applies ] for the movement of the robot. Theorem 2. The application of the inverse kinematics and the forward kinematics to the two trajectories Traj EE and Traj R converts these into the other. It must be ensured that different solutions are possible when using inverse kinematics. A robot can be moved with the aid of the reference points or given configurations for the robot. But this movement can also be differentiated in different ways: ˆ ˆ ˆ Point-to-Point (PTP) line (LIN) Spline The PTP movement refers to a movement in C-Space. The configurations c 1, c 2 C serve as a start and as a destination. From the perspective of the robot and its axes, the movement is carried out directly using a movement profile BP. If you follow the end effector while the robot is moving, there is not always a direct line to the target point in Cartesian space. The LIN movement behaves differently. The robot should move from a starting point to a target point in T-Space. One P ath EE should be covered. The linked configurations for the robot must be selected in such a way that a flowing movement is created for it too and continuous progress is guaranteed. Singularities 6 can occur in certain border areas. The spline movement behaves in a similar way, in which it is also intended to travel from a start to a target point in T-Space. There are support points that also define the path. However, these should not be approached directly. Such a definition of the movement does not restrict the robot in its movement flow. Optimization of motion sequences Since it is difficult to represent the multidimensional space that is spanned by the number of axes of a robot, humans try to use a simpler representation. The creation of paths that are used to machine a workpiece is therefore carried out in T-Space SE (3). Possible configurations of the robot must be determined using the inverse kinematics. To get 6 points in space for which there are many different positions of the robot. When driving through it can happen that joints move at high speeds. 15th

22 2 Theoretical Basics To determine the trajectory, the calculated possible solutions should be compared with one another using certain parameters. They should be adjusted accordingly so that there is little wear and tear on the robot. This can guarantee a long service life for the manipulator. One speaks of an optimization. For this purpose, the robot's sequence of movements should be designed in such a way that it corresponds to a selection from the following conditions: ˆ Length of the movement in Cartesian space or in the configuration space of the robot ˆ ˆ der ˆ Duration of the machining of a workpiece Minimization of jerks when moving the robot Minimization of energy consumption during the Movement of the robot Minimizing the wear and tear of the robot 2.4 Determining a sequence as the underlying problem The number of tasks to be performed on a workpiece can be represented in simplified form as points. These should all be visited. The movement that the robot performs between two tasks can be interpreted as a connection between two points. Since there is no defined direction for the movements, it is an undirected connection. Thus, the machining of a workpiece can be viewed as a graph G = (V, E). In this context, the tasks to be performed stand for the set of possible points V and the movements between them as a set of edges E. The movement from one point to the next is associated with corresponding costs. The term cost can include the length of the movement, the time required or the like. Using the mentioned evaluation criteria and a given list of tasks that are to be carried out, certain problems can arise in the automated determination of a sequence of these tasks. One of these is the Traveling Salesman Problem (TSP) [5]. This is an N P-hard combinatorial optimization problem [26]. It is represented as follows: Definition 10. Given is an undirected graph G = (V, E). Where V is a set of points to be visited and E is the set of edges connecting them. The aim is to find an ordered tour T through all points so that the costs for T are minimal. T = (v 1 ,, v n + 1) and v 1 = v n + 1. 16

23 2.4 Determination of a sequence as the underlying problem Figure 2.7: Traveling salesman problem The traveling salesman problem is illustrated in Figure 2.7 with a minimally expensive tour T. The black points in the TSP represent the vertices vi V and the edges represent the associated connections E. As can be seen in the figure, a sequence between the individual points V is determined from the undirected graph G. If one accepts this definition of TSP and of the possible solutions of V, then a point from V stands for a task. But since you don't have just one possible solution to a task that needs to be done, that leads to another problem. This specific N P-hard optimization problem is called the touring-asequence-of-polygons problem (TPP) [9]. This problem can be defined as follows: Definition 11. Given is an ordered set of n polygons A. Where A = (A 1 ,, A n). The aim is to find a tour T through all polygons so that the costs for T are minimal. Here T = (p 1 ,, p n + 1) and p 1 = p n + 1. The polygon A i is thus visited at point p i. Figure 2.8: Touring-a-sequence-of-polygons problem 17

24 2 Theoretical Basics As can be seen in Figure 2.8, a defined sequence of polygons serves as the starting point for determining a point representative of one polygon. The blue shapes are the polygons A i A, the black dots are the points p i P and the edges are again the connections e i E. The costs that are addressed in both definitions are based on a selected heuristic. This results from the choice of one or more optimization parameters. The two problems can be summarized in the Traveling Salesman Problem with Neighborhoods (TSPN). Thus, not only must an entry point be determined for each polygon, but a sequence must also be determined. Definition 12. Given is a set of n polygons A = (A 1 ,, A n). The aim is to find an ordered tour T through all polygons so that the costs for T are minimal. T = (p 1 ,, p n + 1) and p 1 = p n + 1. The polygon A i is thus visited at point p i. 2.5 Random-based path planning The specified set of points P SE (3) or the set of specific solutions of the inverse kinematics C C can form the basis for performing collision-free path planning. For this there are certain random-based state path planners that fill a predefined search space with valid states in certain calculation periods or until certain conditions are reached. Valid states are those that are not in a collision and are within the specified limits.All algorithms presented in this section are taken from [8]. Figure 2.9: Example of planning with a random path planner. Blue represents the start, orange the goal and gray are the randomly generated states. 18th

25 2.5 Random-based path planning Creation of new states These states are connected to one another via an undirected graph (see Figure 2.9). Using this graph and certain weightings, a path from a starting point to a target point (or configuration) can be calculated. With the aid of a specified cost metric or an optimization target, an optimal path is determined from these calculated paths. The planners who try to find such a collision-free path create new states based on a certain scheme. For example, new states can be created evenly in the room. Other approaches distribute the new states normally according to the Gaussian distribution. Still others involve the robot or the obstacles in the creation of new states in order to create collision-free states in relation to the environment [4]. A check of whether there is a collision in a calculated robot configuration requires information from the forward kinematics. In this way it can be determined how the robot is positioned and what the position of the tool is. Polygon structures should be available for the robot and for the objects located in the work area. These structures can be used to check whether they intersect. If this is the case, a determined state is in collision. Based on the different generation of new states, there are also various strategies to integrate these into a search space that has already been created. By connecting a certain number of valid states, an attempt is made to create a path from a given starting point to a destination. PRM An example of such a planner is the Probabilistic Road-Map (PRM) [14]. In the course of the program, a kind of map of the environment is created and randomly filled with valid states. After a map has been generated, an attempt is made to find an inexpensive path from a start to a destination state. The sequence of PRM can be seen in algorithms 1 and 2. One or more start and target states are required as input. As already mentioned, a card is created in the first phase (algorithm 1). For this it is important to know how many new states n should be created and how many other states k should be connected to [8]. At the beginning, new states are generated randomly and checked for collisions. If a state is valid, it is added to the set V G. This step is repeated until the number of points V corresponds to the value of n. In the next step, the connections between the valid states are to be linked. For this purpose, the set N q of k next states is determined for each state. This set N q is used to check whether a connection 19

26 2 Theoretical Foundations is possible. This stands for any path and movement planner that can be used. This checks whether a direct connection between two states q and q is possible or whether an object is in the way. If a movement between the states q and q is possible, the connection of the two is added to the set E G. Input: n: number of new states k: number of connections to neighbors Output: filled graph G = (V, E) 1 V 2 E 3 while V

27 2.5 Finding random path planning between the two states. Should a path be found, it is the cheapest and can be returned as a solution. If it is the case that one of the two states q start and q goal was not connected to the graph G, no path can be found. Thus an error is returned. Then new states will probably have to be found with the help of the first phase or another combination of q start and q goal must be chosen. Input: q start: starting state q goal: target state k: number of connections to neighbors G = (V, E): generated graph from the previous part Output: path P ath or an error 1 V {q start} {q goal} V 2 N qstart k next neighbor of q start V 3 N qgoal k next neighbor of q goal V 4 repeat 5 q N qstart \ q 6 if (q start, q) NIL then 7 E {(q start, q)} E 8 end 9 until {(q start, q)} E or N qstart =; 10 repeat 11 q N qgoal \ q 12 if (q goal, q) NIL then 13 E {(q goal, q)} E 14 end 15 until {(q goal, q)} E or N qgoal =; 16 P ath shortestpath (q start, q goal, G) 17 if P ath then 18 return P ath 19 else 20 return error 21 end Algorithm 2: Path finding in PRM The algorithms shown in pseudocode represent only the most basic procedure of a PRM algorithm There are other versions based on this one. One example is PRM * [12]. This limits the number of neighbors k in question in the graph G for a state q according to a specified distance parameter. In this way, jumps that are too large in the map created can be avoided or unsuitable start or target states can be excluded from the outset. 21

28 2 Theoretical Basics RRT Another example of a random-based path planner is the Rapidly Exploring Random Tree (RRT) [17]. Similar to the aforementioned planner PRM, one or more start and target states serve as starting values ​​for the algorithm 3. A tree T = (V, E) is to be built which connects the states q start and q goal. To begin with, q start is added to the tree T. After that, new states q rand are generated at random and attempts are made to integrate them into the tree. Input: q start: selected starting state q goal: selected target state Output: filled tree T = (V, E) from q start to q goal 1 V {q start} 2 E 3 d max maximum distance for a movement 4 repeat 5 q rand Randomly newly selected collision-free state 6 q near closest neighboring state to q rand in T 7 d distance between q rand and q near 8 if d

29 2.5 Random-based path planning Figure 2.10: Process of path finding with RRT 23

30 2 Theoretical Basics Version RRT-Connect [16] to create a tree T 1 from the start to the finish and a tree T 2 from the finish to the start. Between the calculation steps, a check is made as to whether the two trees can be linked to one another. Other versions, such as RRT *, [12], with the help of a cost metric, simplify the existing paths on the basis of the received new state. The tree is reconnected to simplify it. It is also possible, based on an introduced target weighting or a restriction of the search space by a form that is placed around the combination of start and target states, to steer the random generation of new states in one direction. An example of this would be InformedRRT * [10]. Single vs. Multi-Query In addition to the different approaches, there are also different implementations of the planner. These can be initialized either as a single or as a multi-query [15]. Single-query planners are structured in such a way that they build a path between a fixed pairing of start and target configurations. You can adaptively carry out further calculations in the same search space and try to improve the path that has already been obtained. However, the states that are marked as the start or end point cannot be changed. This means that the configurations and paths created can only be used for this specific combination. (a) first combination (b) second combination Figure 2.11: Example of planning with a multi-query planner using different start and destination combinations In the multi-query process, a search space between start and destination configurations is also filled and a path is found sought between the two. Here, however, the already filled search area can be used again for a different combination of start and destination points (see Figure 2.11). Thus you can possibly save calculation time. You also have the option to expand the space that is already filled. This means that you can either come to a solution more quickly or find a more optimal path. 24

31 2.6 Background and similar work 2.6 Background and similar work In the field of robotics, there are already some works that deal with the topics of path finding, collision checking, path optimization, parallel computation and automation of the aforementioned areas. There is also constant change due to technical progress. The constant change means that some problems that exist in the research areas are reduced or no longer exist. The work described below is only a selection of those who deal with similar problems. So Saha et al. deal with the collision-free path planning in the configuration space [23]. The path planning carried out here considers a selection of several possible configurations of the robot manipulator. The order for the tasks to be completed has not yet been determined. This must therefore be determined in addition to the determination of the minimally costly path. The Probabilistic Road-Map is used as a route planner. This method is implemented with the single query process and thus creates a separate search area for each combination of a start and target configuration. This is reused in further calculation steps. This shows that such planners can be used to plan a collision-free path. In order to solve the sequence of tasks, an evaluation of the closest neighbor is also made. The attempt is made to implement this with a minimal spanning tree. With the assumption that several solutions of the inverse kinematics can stand for one target region, the previous work was extended again [24]. A closed path is to be determined between the given target regions. A calculated configuration is representative for the entire region. Thus, in this approach, not only a solution for determining a sequence was presented, but also one for determining an optimal configuration for a set of possible configurations. As can already be seen from the work, finding a solution using the configuration space as a search space is computationally intensive and takes a lot of time. For this reason, it would make sense to parallelize some processes during the calculation. The following work [11] tries to parallelize the process of finding the way in a search area over several computer systems. A configuration is randomly generated in the search area for each separate process. Then the configuration tries to connect to the start and target configuration via a path. As a result of the work, a significant reduction in the calculation time is shown. This means that the use of parallelization is useful for implementing the calculation of new random states. The whole thing was expanded in the next work [27]. In addition to the parallelization of the creation of new states, an attempt is made to implement a bidirectional search. The order of several tasks should be determined by provision 25

32 2 Theoretical foundations of an optimal path can be established. Furthermore, a problem has been addressed with regard to the pairing of start and destination points. With this problem, it may happen that no solution can be found for a specific combination of the two. The selection of and the handling of certain entry and exit points therefore play a role in the optimization. In the worst case, this has a strong influence on the calculation time. 26

33 3 Concept of the work This chapter deals with the concept and the idea on which the entire work is based. Reference is made directly to a previous work. At the end, the actual problem and the solution is discussed. In order to understand the various concepts, it must first be clarified how the processing of an object can be described. The machining of a workpiece can be divided into individual tasks. Each of these tasks must be approached and the underlying work order must be completed. Definition 13. A task that needs to be completed is called a T ask. A distinction can be made between different types of tasks. One type of task can be a T ask Rest T ask. This represents an initial configuration of a robot, which is approached between the processing of two workpieces. T ask remainder = c remainder C. A second type of task should be T ask EF T ask. This represents an underlying work order on a workpiece. This task can also be referred to as an effective task. T ask EF = P ath EE applies. A workpiece has a finite set of effective tasks. A third type of task should be T ask S T ask. This represents the movement between two different effective movements T ask EF A to T ask EF B or from T ask rest to a T ask EF and vice versa. This task is also referred to as a support task. T ask S = P ath R. The number of support tasks depends on the number of effective tasks. The entirety of all tasks and the associated movements of the robot are referred to as a job in this context. Parts of it form the collections T L for all effective tasks and T L S for all support tasks. Definition 14. The complete machining of a workpiece is called a job. This job represents a closed, orderly sequence of tasks from T ask. A job starts with a T ask Rest and alternates through a T ask S and a T ask EF, to end with a T ask S again at the T ask Rest to be. Since when executing the work orders, which are represented here as effective tasks, the underlying continuous path is usually carried out with a coordinated movement of the robot, there is no scope for optimization in an effective task. It is different when looking at 27

34 3 Concept of the work of the entire machining of the workpiece, the job. Here, the choice of entry and exit points for the effective tasks and the support tasks between these have an influence on the duration and length of the entire processing. Thus, by rearranging a given list of effective tasks and coordinating the entry and exit points based on the support movement, optimization can be achieved. Figure 3.1 shows two tasks. The purple path is a support task T ask S. The blue paths represent effective tasks T ask EF. Figure 3.1: Representation of a support task T ask S 3.1 Previous implementation of an optimization problem This master's thesis is mainly shaped by the work of Alatartsev. In the published doctoral thesis [3], some ideas were presented that are also used in the following master's thesis. Basically, the described optimization of a given list of effective tasks proceeds as follows. First, a determination of an order of FIG

35 3.1 Previous implementation of an optimization problem done effectively. This is done according to the location of the tasks in T-Space SE (3). With the help of the determined sequence, a determination and adaptation of an input orExit point made for each individual effective task. The adaptation is made on the basis of the Euclidean distance between possible configurations in configuration space C of the robot. These two configurations are representative of two adjacent effective tasks. The result is an ordered list of effective tasks with a representative entry or exit point for each task. Using this list, after the automated optimization, a collision-free path planning can be made between all effective tasks. A configuration should also be determined that functions as the initial task T ask Rest and enters the ordered list of effective tasks. Only then would a job be determined. Starting point for the algorithm The input of a list of tasks T L = (T ask EF 1 ,, T ask EF n) serves as the output of an optimization to be applied. This list is assumed to be unsorted. Each individual T ask EF i is represented by its underlying continuous path P ath EEi. This path creates a point p i SE (3) at the point k [0, 1]. In addition, a degree of freedom is introduced for such a point p i in T-space (see Figure 3.2). This degree of freedom allows a deviation in position and orientation in SE (3) from the actual value of p i. Applied to all points on the path, a kind of quality tolerance can arise. This describes the deviation up to which a path and thus the underlying effective task counts as validly completed or processed. Definition 15. There is a so-called tolerance range T B (p), so that it determines a set P T B SE (3) of possible neighboring points for a point p SE (3). T B: SE (3) P T B with P T B SE (3) applies. Definition 16. For an effective task T ask EF there is an effective task with tolerances T askef T B B, so that T askt EF (k) points to a set of neighboring points of the point of T ask EF (k) using all k [0, 1]. Here T askef T B = T B T ask EF: [0, 1] P T B with P T B SE (3). In addition, T ask EF T ask T B EF applies. a job also refers to the effective task 3. Since T ask EF T askef T B task with tolerance range. Definition 17. A point p SE (3) belongs to an effective task with tolerances T askef T B B, if k [0, 1] and p T askt EF (k). Definition 18. An end effector path P ath EE belongs to an effective task with tolerances T askef T B if k [0, 1] maps to points of the effective task with tolerances, so that P ath EE (k) T askef T B (k). 29

36 3 Concept of the work Figure 3.2: Representation of the degree of freedom of a point p i Figure 3.2 shows an example for the tolerance range P T B of a point p i P T B. The blue circle p is after P T B. Due to the transformation matrix of the point p i, there is a local coordinate system in this. Depending on this coordinate system, tolerances can also be specified in the orientation. For this tolerance, the local coordinate system is viewed as a spherical coordinate system. The radius of the sphere, which has its center at the origin from p to, is determined by the length of a tool used. This creates the three angles a, b and c, each with two boundaries. Here, al and au represent the lower and upper limits of a vertical angle in the range from 0 to 180. The values ​​bl and bu represent the lower and upper limits of a horizontal angle in the range from 0 to 360. This creates a plane of possible points on the sphere stretched. Thus, different orientations of the tool can be made possible for a point p to. The values ​​c l and c u therefore stand for a rotation around the tool axis in the range from 0 to 360. Using such a degree of freedom or tolerance range, it can be guaranteed that the robot has performed the work correctly. However, it also offers the possibility of determining a better movement for the robot in the event of an optimization. The respective work order and the tool selected for it should support such a tolerance range. Different types of effective tasks In addition to the list of effective tasks T L given, the type of effective task T askef T B i should be defined. For this purpose, the doctoral thesis distinguishes between three different types of effective tasks. Accordingly, there is a difference in the definition, the interpretation of the degree of freedom and the handling of an optimization to be carried out for each species. The 30

37 3.1 Previous implementation of an optimization problem se types in Figure 3.3. The possible tolerance range is also mapped. Figure 3.3: Types of effective tasks from doctoral thesis 1 The first type of effective tasks relates to work orders, such as drilling or spot welding, which only process the workpiece at individual points in the T-Space. In such a work order, the path maps EE (k) k [0, 1] to a point p i. Accordingly, a tolerance range T B can be applied to the associated task T askef T B i. Should such a work order be in a list T L, the quantity P T B represents the possible entry and exit volume. Cutting or welding a line represents the second type of effective task. There is a continuous course, so that P ath EE (k) k [0, 1] provides different points. Each point p i, which arises from all values ​​of k, has a tolerance range P T B. Possible entry and exit points can be a pairing of the points p in = P ath EE (0) and p out = P ath EE (1) or p in = P ath EE (1) and p out = P ath EE (0 ) be considered. These each have a tolerance range Pin T B and Pout T B as the associated volume. The third and last type of effective task does not really differ 1 [3] 31

38 3 Concept of work from the previous one. These are closed paths, which means that the start and destination points are identical. For P ath EE (k) it applies that different points are always generated. Only the point p i = P ath EE (0) = P ath EE (1) are the same. It is thus possible to start the entire effective task T askef T B i at any point. Sample work orders can be cutting or welding a closed circle. Problem definition and solution approaches of the work The problem that is posed in the doctoral thesis is that a tour through a given task list T L is to be planned in the configuration space of the robot. The task list is not pre-sorted and contains all effective tasks that have to be processed. Thus, in addition to determining an optimal tour through all the effective tasks, a sequence of the effective tasks must also be found. The planning of the paths should be optimized according to the parameters time and jerk minimization. Since the specified problem or the associated search space is too powerful, the solution is divided into two sections. A total of three components are presented for these two sections (see Figure 3.4). The first section looks at the delivery movements associated with the actual tasks. This movement between the individual effective tasks should be adapted in such a way that they provide an optimal solution overall. The second section uses the solution of an entry point obtained for the respective effective tasks to determine an optimal path for the robot for this effective task. Determining a sequence In the first component (see Figure 3.4 Component 1) an attempt is made to determine the sequence of a task list T L = (T askef T B 1 ,, T askt EF B n). In order to be able to solve the problem, connections in Cartesian space are planned between each individual effective task. The Euclidean distance should serve as a parameter for the costs. The aim of the first component is to find a minimally costly closed tour T through the points (p 1 ,, p n). A point p i in T stands for a point of the effective task T askef T B at the point k [0, 1]. In order to save calculation time, the additional degree of freedom of the effective tasks is set to a fixed, averaged value. By using the so-called Constricting Insertion Heuristic algorithm, the positions of the effective tasks in Tour T are swapped until the distance in Cartesian space can no longer be reduced. With the help of a rubber band algorithm [18], the entry and exit points on the path P ath EE of an associated effective task T askef T B i are shifted until no further improvement is possible. 32

39 3.1 Previous implementation of an optimization problem The output from this component is a sorted list of the effective tasks T L. This sorting depends on the Euclidean distance between the effective tasks in the T-space. Figure 3.4: Concept from doctoral thesis 2 Determination of an optimal robot configuration With the help of the output from the first component, an attempt is made in the second component (see Figure 3.4 Component 2) to determine a robot configuration suitable for the entry or exit point for each effective task. For this purpose, the movement between the robot configurations should be optimized with regard to the time and the length of the movement in the configuration space. The order of the task list T L = (T askef T B 1 ,, T askt EF B n) is not changed. Using this list, a minimally expensive closed tour CT = (c 1 ,, c n) is to be determined for the configuration space. Un- 2 [3] 33

Using the forward kinematics, a configuration c i can be traced back to the point p i = F K (c i) and, associated with this, a parameter k [0, 1] of T askef T B i. Using the designed nestedrba, an attempt is made to find new solutions for the entry and exit configurations of the robot in the respective effective tasks T askef T B i based on the specific sequence. An optimal solution for a configuration c i is iteratively searched for. It can also happen that the position and the orientation of the previously determined entry or exit point p i is shifted within the tolerance range T B (p i). A sequence of possible optimal configurations for all effective tasks is thus obtained from the task list T L. These can be approached via a PTP movement, but do not guarantee a collision-free path. Optimizing the effective movement The last component (see Figure 3.4 Component 3) is part of the second section and considers the respective effective movements per se. Here the movement of the robot is to be optimized during the execution of an effective task T askef T B on the basis of a movement profile BP EE and a predetermined time T. For this purpose, a path P ath EE T askef Rel is to be determined, which leads to a minimally costly trajectory T raj R (t). It should apply that IK (P ath EE (BP EE (t))) T raj R (t) with t [0, T]. The optimization parameters for this part depend on the chosen task. The determined optimal configuration of an effective task T askef T B serves as a starting value. With the help of this and the possible tolerance range of an effective task, further configurations along the course of P ath EE can be calculated via the inverse kinematics. In this way, an optimal path can be planned through all configurations of the effective movement in order to save even more time, movement or energy. 3.2 Current problem statement It is assumed that there is a work space in which only the robot and the object are located. This means that collision-free path planning is dispensed with when determining an optimal solution. However, it is unclear what happens when the shape of a workpiece does not prevent a collision. This master's thesis should also be about planning and optimizing the machining of a workpiece. Starting from a rest position of the robot, a list of effective tasks should be worked through. The order of the tasks should be adjusted. The planning of the path should take place purely in the configuration space of a robot C. The goal should be to obtain a path for the robot that follows a predefined optimization goal

41 3.3 Ideas for the new algorithm is right. So the problem for this work is: The determination of an optimal collision-free sequence from a given list of effective tasks. The respective entry and exit points of the effective tasks are to be determined using the parameter of the minimum movement in the joints of the robot. The algorithm that arises in this context should be independent of the robot and the workpiece. It should therefore be possible for these to be defined and used beforehand. The robot used and the respective workpiece only have an influence on the optimization of a selected example scenario. There is no analysis of the optimal position of the two components in relation to one another. The aim of this work is to test random-based path planners that already exist in a library. No planners are written by themselves. 3.3 Ideas for the new algorithm Based on the doctoral thesis, the solution to the problem should be divided into two sections. The first optimization relates to the infeed movements and the second to the effective movements. In the master's thesis, only the first optimization is adjusted. Thus, on the solution obtained, the optimization of the individual effective tasks can be made based on the implementation from the doctoral thesis. Also based on the optimization of the infeed movement from the previous algorithm, a given list of effective tasks T L = (T askef T B 1 ,, T askt EF B n) should serve as the basis of this imaginary optimization. A distinction is made between the optimization of the infeed movement in three different phases. Learning phase Since the search space, in which new collision-free configurations are searched for, is rigid and the only object that is in motion is the robot, the idea is to create a map of the environment. This can be used for further calculations. Thus, the first stage of optimization is a learning phase (see Figure 3.5 above). Based on the given list T L, possible support movements (T ask S1 ,, T ask Sn 1) from an effective task T askef T B i to all other effective tasks are to be determined. This step must be repeated for all effective tasks in the list T L. This phase has no direct influence on the order of the task list T L. It only offers the opportunity to achieve an improved result for the individual support movements. The learning phase can be carried out at any time during the calculation. 35

42 3 Concept of the work Figure 3.5: Concept of the master's thesis Phase to determine the sequence In the phase to determine the sequence of the effective tasks (see Figure 3.5 middle) an attempt is made to find a possible solution to the Traveling Salesman Problem with Neighborhoods. Using a predefined position of the robot T ask Rest, a minimally costly tour CT = (c 1 ,, c n) in the configuration space of the robot through the given list of the effective tasks T L is to be determined. This is intended to determine an ordered list T L from the list of effective tasks T L. A configuration c i can be traced back to a point p i and the associated parameter k [0, 1] of T askef T B i using the forward kinematics. The degree of freedom of the effective task is limited in this phase. This reduces the possible search space. Phase for determining an optimal configuration The phase for determining an optimal configuration is used to find an optimal solution from the set of possible 36