Genetic algorithms for workspace optimization of planar medical parallel robot
Sergiu-Dan Stan, Member, IEEE, Milos Manic, Senior Member, IEEE, Radu B?lan, Vistrian M?tie?
has been specified via the data that considers three types of workspace definition: via a set of points, via a trajectory and via a volume. The purpose of this paper is to first, describe the kinematics and workspace of the parallel robot and second, to demonstrate the benefits of applying genetic algorithms in the workspace maximization. The paper goes as follows. The structure and the kinematic scheme of the parallel robot are described in the second section, while the workspace analysis is presented in the third section. Based on the genetic algorithms optimization method, the optimal design of parallel robots developed is presented in the fourth section. Fifth section presents the optimization results illustrated by the developed algorithm with a numerical example.
Abstract— The aim of this paper is to demonstrate the usefulness of the Genetic Algorithms (GA) optimization approach to optimize the 2-DOF planar medical parallel robot (PR). Variations of the kinematic performances index do not remain constant throughout the robot’s workspace. Parallel robots potentials are fully exploited only when their structure is optimally dimensioned from geometric point of view. In other words, their performances heavily depend on their geometry. Thus, optimization of the geometric parameters or optimal dimensioning became an important issue in the process of parallel robots performance improvement. In this paper, motivated by the advantages of GA techniques, we apply them to the 2-DOF parallel robot optimization problem. Genetic algorithms are in general the most robust type of evolutionary algorithms. The obtained results have demonstrated the use of GA in previously described type optimization problems improve the quality of the optimization outcome, resulting in a better and more realistic support for the decision maker.
II. KINEMATICS ANALYSIS FOR 2 DOF PARALLEL ROBOT A planar two degree of freedom parallel robot is presented in the following text. Robot kinematics deals with the study of the robot motion as constrained by the geometry of the links. Typically, the study of the robot kinematics is divided into two parts, inverse kinematics and forward (or direct) kinematics. Closed-form solutions are developed for both the inverse and the direct kinematics. A. Two degree of freedom parallel robot One possible configuration of the parallel robot with 2 DOF is shown in Fig.1. It has a large workspace and highspeed point-to-point motion. This configuration will be further analyzed in this paper.
HE parallel robots have a number of advantages over the traditional serial robots due to their particular architecture . There are several examples of parallel robots, especially in the fields of assembly and medical applications. However, there are also some notable disadvantages associated with the parallel robots, which have impeded their wide application. The uppermost drawback is that its particular architecture leads to smaller and irregular-shaped workspace and poorer dexterity. To achieve a parallel robot with such good workspace properties, the design parameters with regards to the geometric parameters must be optimized. Based on the design goal, the optimal design of general parallel robots’ kinematic parameters is classified into two categories. The first type of optimal design is where a set of parameters of a parallel robot whose workspace is a maximized one, is found. The second type of optimal design is concerned with the dimensional synthesis of parallel robots and tries to fit a prescribed working region as closely as possible. Merlet  in his work focused on the optimal problem of design parameters of the Gough-type PR, when prescribed
Manuscript received August 28, 2008. Financial support for this work was supported in part by the CNMP under Grant PARTENERIATE no. 3280 and CNCSIS IDEI_1072. Dr. Sergiu-Dan Stan is with the Technical University of Cluj-Napoca, Dept. of Mechatronics, 103-105, B-dul Muncii, 400641, Cluj-Napoca, Romania (+40-264-401755; e-mail: firstname.lastname@example.org). Email contacts of other authors are: email@example.com, firstname.lastname@example.org, and email@example.com.
Fig. 1. Singular configuration of type I
The parallel robot includes the translation actuators M and N (of slider type), link MP, link NP and the endeffector TCP mounted on one link (NP). The distances from the TCP centre to the point P are c, and d, respectively. It can be noticed that when two actuators move along the horizontal guide, the TCP realizes two degrees of freedom. The angle between the links MP and NP, and the horizontal ox - axis are φ2, and φ1, respectively. The parameters used for dimensional design of this parallel robot are therefore: a, b, c and d (Fig.1) B. Inverse kinematics The inverse kinematics problem of the parallel robot is presented by the following equations:
presented 2-DOF parallel robot are easy and may be described as closed-form solutions. D. Equation of velocity The inverse kinematics model establishes a relationship between the articular velocity and the operational velocity. The inverse Jacobian matrix establishes the relation between cartesian and angular velocity and articular velocity. The velocity equations can be obtained through differentiation of the Eq.(1) with respect to time. This can be seen in the equation of the following form, Eq. (7): (7) where is the vector of output velocities which can be
defined as: where (2) and . (3) and where defined as: C. Direct kinematics The Direct Kinematic Problem (DKP) of a parallel robot is an important research direction of mechanics, which is also the most basic task of mechanic movement analysis and the base studies such are mechanism velocity, mechanism acceleration, force analysis, error analysis, workspace analysis, dynamical analysis and mechanical integration. From Eq. (1), the direct kinematics of the 2-DOF parallel robot can be obtained as: (10) The obtained inverse Jacobian matrix can be used for the study of the singular positions of the constrained parallel manipulator, for the evaluation of its maneuverability, and also for the optimization of its architecture. Now, the inverse and forward Jacobian matrices of the parallel robot can be determined, and expressed as in the following equations: (11) is the vector of input velocities which can be where (9) (8)
where (5) where ; . (6) ; ; The inverse and direct kinematics problems of the
; ; . E. Singularity analysis It is well known that parallel manipulators may encounter singular configurations that can result in a loss of full constraint. The nature of the kinematic deficiency for such singular configuration can be analyzed by calculating the null space of the Jacobian matrix for that configuration. Singularities correspond to certain configurations of parallel manipulators which have to be avoided, because they lead to an abrupt loss of manipulator rigidity. In the vicinity of these configurations, the parallel robot can become uncontrollable and the articular forces can increase considerably with the risk of even damaging the manipulator mechanisms. We also discuss the physical significance of each of the two types of singularities. Singularities of type 1 or parallel singularities, correspond to the condition where det(Jq) = 0. The kinematics analysis of our manipulator reveals that there are no singularities inside the workspace: (13) This kind of singularity corresponds to the limit of the workspace of our parallel robot. For this robot this kind of singularity is encountered when one of the diagonal entries of Jq vanishes, as in the following equation: (14) Eq. (14) yields or . Eq. For these singular positions, in presence of the articular movements, the mobile platform will remain fixed and the manipulator will benefit of a great rigidity. The singular configuration of type 2 is presented in the Fig. 3.
Fig. 2. Singular configuration of type I
Singularities of type 2 (or serial singularities) correspond to the condition where det(J) = 0. If this situation arises, this means that the matrix J is degenerated and there is an infinity of solutions for the inverse geometrical model in the vicinity of these points: (17) If Eq. 15 is verified, one can obtain the following equation: (18)
(14) is verified and the following obtained: (15)
Fig. 3. Singular configuration of type II
(16) The singular configuration of type 1 is presented in the Fig. 2.
III. WORKSPACE ANALYSIS One of the most important issues in the process of design of the parallel robots is to determine their workspace. For parallel robots, this issue may be even more critical since parallel robots will sometimes have a rather limited workspace. The approaches where optimization methods are used for the workspace boundary determination can be
also found in the literature. Various numerical methods for determination of the workspace of the parallel robots have been developed in the recent years. Stan  presented a genetic algorithm approach for multi-criteria optimization of PKM (Parallel Kinematics Machines). The majority of numerical methods used for parallel manipulator workspace boundary determination typically rely on manipulator’s pose parameter discretization. With the discretization approach, the workspace is envisioned as the uniform grid of nodes in a Cartesian or polar coordinate system. Each node is then examined in order to determine whether it belongs to the workspace or not. The accuracy of the workspace boundary in this case depends on the sampling step, used to create the grid. However, the computation time grows exponentially with the sampling step, therefore limiting the accuracy. Furthermore, various problems may occur in case of singular configurations of the workspace. The workspace of the planar 2-DOF parallel robot is represented as a region of the plane. The constrained parallel robot workspace under consideration can be determined numerically according to the direct geometrical model given by equations (4). By varying systematically the active segment lengths between their minimal values qimin and their maximum values qimax, (i=1, 2) reachable positions of the mobile platform center (Px, Py) can be computed. The set of these positions provides the possibility to visualize the robot workspace. The following figure visualizes the 2D robot workspace.
Fig. 4. Workspace of the 2 DOF parallel robot
The parallel robot realizes a wide workspace. Analysis, i.e. visualization of the workspace is an important aspect of performance analysis. In order to generate a reachable workspace of parallel manipulators, a numerical algorithm was introduced. IV. GENETIC ALGORITHM BASED OPTIMIZATION The Genetic Algorithms optimization method has been growing in popularity over the recent years as more and more researchers discovered the benefits of its adaptive search. Genetic algorithms (GAs) were invented by John Holland in the 1960s and developed by Holland and his students and colleagues at the University of Michigan in the
1960s and the 1970s. Holland's original goal, in contrast to the evolution strategies and evolutionary programming, was not to design algorithms to solve specific problems, but rather to formally study the phenomenon of adaptation as it occurs in nature, and to develop ways in which the mechanisms of natural adaptation might be imported into computer systems. The GA of Holland is a method for moving from one population of "chromosomes" (e.g., strings of ones and zeros, or "bits") to a new population by using a kind of "natural selection" together with the genetics?inspired operators of crossover, mutation, and inversion. Each chromosome consists of "genes" (e.g., bits), each gene being an instance of a particular "allele" (e.g., 0 or 1). The selection operator chooses those chromosomes in the population that will be allowed to reproduce, and on average the fitter chromosomes produce more offspring than the less fit ones. Crossover exchanges subparts of two chromosomes, roughly mimicking biological recombination between two single?chromosome ("haploid") organisms; mutation randomly changes the allele values of some locations in the chromosome; and inversion reverses the order of a contiguous section of the chromosome, thus rearranging the order in which genes are arrayed. (Here, as in most of the GA literature, "crossover" and "recombination" will mean the same thing.). In a broader usage of the term, a genetic algorithm is any population-based model that uses the selection and recombination operators to generate new sample points in a search space. Many genetic algorithm models have been introduced by researchers largely working from an experimental perspective. Many of these researchers are application oriented and are typically interested in genetic algorithms as optimization tools. Some of the advantages of a GAs are their abilities to: ? optimize with continuous or discrete variables, ? do not require derivative information, ? simultaneously search from a wide sampling of the cost surface, ? deal with a large number of variables, ? be well suited for parallel computers, ? optimize variables with extremely complex cost surfaces (they can jump out of a local minimum), ? provide a list of optimum variables, not just a single solution, ? may encode the variables so that the optimization is done with the encoded variables, ? work with numerically generated data, experimental data, or analytical functions. These advantages are intriguing and produce stunning results when traditional optimization approaches fail
miserably . V. OPTIMIZATION RESULTS In this section we present the mathematical/kinematic
tools that were used to formulate the workspace optimization problems.
Fig. 5. Flowchart of the optimization Algorithm with GAOT (Genetic Algorithm Optimization Toolbox)
These tools include the direct and inverse kinematics and the workspace area. The workspace of the robot is parameterized using several design parameters that span over a large range of values In this work, three performance indices will be used to characterize a robotic system’s workspace as as it is described in details in Sec. 3, the workspace area. Objective_function= (19)
0.3 m<a<0.6 m 0.3 m<b<0.6 m
During the optimization process, a following GA parameters were used (Table 1): Table 1. GA Parameters 1 2 3 4 Population Generations Crossover rate Mutation rate 50 100 0,08 0,005
Obviously, using this performance index as the objective function, optimal designs correspond to maximum workspace area. Based on the direct kinematics of the 2-DOF parallel robot shown in Eq. (4), the robot’s workspace depends on two geometric parameters: the magnitudes a and b of link lengths as well as actuator’s strokes qi, i=1, 2. Optimization problem is formulated as follows: the objective is to evaluate optimal link lengths which maximize (9). The design variables or the optimization factor is the link length a, and the link length b. Constraints to the design variables are:
A genetic algorithm (GA) was used because its robustness convergence properties. The GA approach has the clear advantage over conventional optimization approaches in that it allows a number of solutions to be examined in a single design cycle. The traditional methods search through optimal points, and easily get trapped in local optimal points. Using a population size of 50, the GA was run for 100 generations. A list of the best 50 individuals was continually maintained during the execution of the GA,
allowing the final selection of solution to be made from the best structures found by the GA over all generations. We performed a kinematic optimization in such a way to maximize the workspace index W. It is noticed that optimization result for the planar parallel robot is when the maximum workspace is obtained for a=0.6m and b=0.6m. The used dimensions for the 2 DOF parallel robot were: a=0.6 m, b=0.6 m, q1min=0 m, q1max=1.5 m, q2min=0 m, q2max=1.5 m. Maximum workspace of the parallel robot was found to be W= 0.3345133m2. In practice, however, optimization of the parallel robot geometrical parameters should not be performed only in terms of workspace maximization. Some parts of the workspace are more useful considering a specific application. Indeed, the advantage of a bigger workspace can be completely lost if it leads to new collision in parts of it which are absolutely needed in the application. However, this is not the case in the presented structure. VI. CONCLUSION In this paper the workspace optimization of a 2-DOF planar medical parallel robot is performed. Closed-form solutions for both inverse and direct kinematics were developed. The equation of the parallel robot is also given. Two kinds of singularities are analyzed, and two types of singularity were obtained. A description of the workspace of the parallel robot is provided based on the analysis of the robot. The kinematics, velocity, singularity and workspace analyses presented in this paper can greatly benefit the design, trajectory planning and control of such a parallel robot. ACKNOWLEDGMENT This work was financial supported by CNMP through grants no. 3280 (PARTENERIATE type), title of the project ‘Complex mechatronics systems for medical applications’ and CNCSIS 1072 (IDEI type), title of the project ‘Researches regarding the advanced control with applications in mechatronics’. REFERENCES
      C. Gosselin. “Determination of the workspace of 6-d.o.f. parallel manipulators”. ASME Journal of Mechanical Design, 112:331–336, 1990. J. P. Merlet. “Determination of the orientation workspace of parallel manipulators”. Journal of intelligent and robotic systems, 13:143– 160, 1995. A. Kumar, KJ. Waldron. “The workspace of mechanical manipulators”. ASME J. Mech. Des. 1981; 103:665-672. YC. Tsai, AH. Soni. “Accessible region and synthesis of robot arm”. ASME J. Mech Des. 1981, 103: 803-811. KG. Gupta, Roth B., “Design considerations for manipulator workspace”. ASME J. Mech. Des. 1982, 104(4), 704-711. K. Sugimoto, Duffy J, Hunt KH, “Special configurations of spatial mechanisms and robot arms”. Mech Mach Theory 1982, 117(2); 119132.
      
  
KC. Gupta. “On the nature of robot workspaces”, Int. J. Rob. Res. 1986; 5(2): 112-121 JK. Davidson, KH. Hunt, “Rigid body location and robot workspace: some alternative manipulator forms”. ASME J. Mech. Transmissions Automat Des 1987, 109(2); 224-232. SK. Agrawal, “Workspace boundaries of in-parallel manipulator systems”. Int. J. Robotics Automat 1990, 6(3) 281-290. C. Gosselin, Angeles J. “Singularities analysis of closed loop kinematic chains”.IEEE-T.Robotics Automat 1990; 6(3) 281-290. M. Cecarelli, “A synthesis algorithm for three-revolute manipulators by using an algebraic formulation of workspace boundary”. ASME J. Mech. Des. 1995; 117(2(A)): 298-302. S. K. Agrawal. “Workspace boundaries of in-parallel manipulator systems”. IEEE Transactions on Robotics and Automation, 7(2):94– 99, 1991. F. Pernkopf and M. Husty, ”Reachable Workspace and Manufacturing Errors of Stewart-Gough Manipulators”, Proc. of MUSME 2005, the Int. Sym. on Multibody Systems and Mechatronics Brazil, 2005, p. 293-304. S. Stan, Diplomarbeit, Analyse und Optimierung der strukturellen Abmessungen von Werkzeugmaschinen mit Parallelstruktur, IWFTU Braunschweig, 2003, Germany. K. Cleary and T. Arai. “A prototype parallel manipulator: Kinematics, construction, software, workspace results, and singularity analysis”. In Proceedings of International Conference on Robotics and Automation, pages 566–571, Sacramento, California, April 1991. C. Ferraresi, G. Montacchini, and M. Sorli. “Workspace and dexterity evaluation of 6 d.o.f. spatial mechanisms”. In Proceedings of the ninth World Congress on the theory of Machines and Mechanism, pages 57–61, Milan, August 1995. M. Ceccarelli, G. Carbone, E. Ottaviano, “An Optimization Problem Approach For Designing Both Serial And Parallel Manipulators”, Proc. of MUSME 2005, the Int. Sym. on Multibody Systems and Mechatronics Uberlandia, Brazil, 6-9 March 2005 M. Ceccarelli, Fundamentals of Mechanics of Robotic Manipulation, Dordrecht, Kluwer/Springer, 2004. Company, O.: Machines-outils rapides à structure parallèle. Méthodologie de conception, applications et nouveaux concepts. Dissertation. Universite Montpellier II, Sciences et Techniques du Languedoc, 2000. L.J. Du Plessis, J.A. Snyman. “A numerical method for the determination of dextrous workspaces of Gough-Stewart platforms”. Methods in Engineering,52:345–369, 2001. Xin-Jun Liu, Optimal kinematic design of a three translational DoFs parallel manipulator, Robotica, Vol.24, No.2, pp 239-250, 2006. (SCI, EI) J. Hesselbach, H. Kerle, M. Krefft, N. Plitea, “The Assesment of Parallel Mechanical Structures for Machines Taking Account of their Operational Purposes”. In: Proc. of the 11th World Congress in Mechanism and Machine Science-IFToMM 11, Tianjin, China, 2004. Stan, S.-D, Manic, M., M?tie?, M., B?lan, R., “Evolutionary Approach to Optimal Design of 3 DOF Translation Exoskeleton and Medical Parallel Robots”, HSI 2008, IEEE Conference on Human System Interaction, Krakow, Poland, May 25-27, 2008. Stan, S.-D, Manic, M., M?tie?, M., B?lan, R., “Kinematics Analysis, Design, and Control of an Isoglide3 Parallel Robot (IG3PR)”, IECON 2008, The 34th Annual Conference of the IEEE Industrial Electronics Society, Orlando, USA, November 10-13, 2008.
 Haupt, R. and Haupt, S.E. (2004) Practical Genetic
Algorithms, Willey-IEEE, New Jersey, USA.