An Evolutionary and Local Search Algorithm for Motion Planning of Two Manipulators

An Evolutionary and Local Search Algorithm for Motion Planning of Two Manipulators M. A. Ridao*, E. F. Camacho Departamento Ingenierıa ´ de Sistemas y automática.Escuela Superior de Ingenieros Universidad de Sevilla, Spain J. Riquelme, M. Toro Departamento Lenguajes y Sistemas, Facultad de Informática y Estadística. Universidad de Sevilla, Spain A method for obtaining coordinated motion plans of robot manipulators is presented. A decoupled planning approach has been used; that is, the problem has been decomposed into two subproblems: path planning, where a collision-free path is found for each robot independently only considering fixed obstacles, and trajectory planning, where the paths are timed and synchronized to avoid collisions with other robots. This article focuses on the second problem. The proposed plan can easily be implemented by programs written in most industrial robot programming languages. The generated programs minimize the total motion time of the robots along their paths. The method does not require accurate dynamic models of the robots and uses an evolutionary algorithm followed by a local search which produces near optimal solutions with a relatively small computational cost. sion-free motion plans.These motion plans have to take into account environment obstacles and other robots.Finding collision-free motion planning algorithms in multirobot systems has been the focus of research in many works.1These algorithms can be classified into three categories: centralized, prioritized, and decoupled planning. In centralized planning all robots are considered simultaneously and the problem is solved by find- 1. INTRODUCTION One of the main problems encountered when operating a multirobot system is that of obtaining colli- *To whom correspondence should be addressed; e-mail: [email protected]. Contract grant sponsor: CICYT. Contract grant numbers: QUI199-0663, TAP-98-0541, 1FD97-0836, and TIC-99-0351. ing a collision-free path in a space with dimension equal to the sum of the degrees of freedom of each of the robots.Algorithms based on centralized planning require a large amount of computation because of the size of the search space and only methods for solving specific problems have been proposed.2᎐4 In prioritized planning, an order is established among the robots.The motion of the robots is planned in this order, only one robot at a time.The motion of the robot is computed as if the robot were moving among stationary obstacles and the previous robots are considered as moving obstacles.5 This is one way of reducing the computational complexity, but this approach may fail to find a solution, even if there is one. In the third category, decoupled planning, the path of each robot is planned independently of the others, and afterwards the paths are synchronized to avoid collisions among the robots.These algorithms reduce the computational complexity considerably, but this gain results in a loss of completeness.Different methods have been presented to solve the interactions among the paths.Kant and Zucker6,7 and Fujimura8used the technique for mobile robots. Lee and Lee9applied the technique to two manipulators by fixing the speed of one of the robots and modifying the other robot to find an obstacle-free plan.The collisions are studied using a bidimen- Ž. sional graph collision map where the path of the second robot is represented versus time and collision regions are included and approximated by rectangles.The robots are modeled with spheres and the movement of the robots was restricted to straight-line paths.Chang et al.10 proposed an extension of this method using robots approximated by polyhedra and determining the minimal delay time value needed for collision avoidance. O’Donnell and Lozano-Perez11 used the coordi- ´ nation diagram, where all the possible collisions between both robots appear.Applying the concept of SW-closure, they proposed an algorithm which did not require searching to find a solution.Bien and Lee12 proposed a method to plan a trajectory that ensures collision-free and time-optimal motions.The main drawback of the method is that it can only be used when there is a single collision region in the coordination space.Lee13 extended this procedure to situations in which there are more than one collision region. Fraile et al.14 presented a distributed planning and control architecture for multi-manipulator systems.A distributed trajectory planning approach based on artificial potential fields was used.Finally, Perez-Francisco et al.15 presented a method for the ´ coordination of two robots when they are grasping objects of unknown shape and position from a conveyor belt, under time constraints. The solution obtained by most of these algorithms is a robot trajectory; that is, they associate a time component with the points of the paths.These trajectories are very difficult to implement in most industrial robots, because they require the internal controller of each articulation to be fully available to the user to synchronize their movement with the movements of other robots’ joints.Also, the selection of an accurate robot dynamic model is critical, because a discrepancy with the robot behavior can cause collisions between robots. In this article, a method is presented to minimize the total motion time of two manipulators along their paths, avoiding collision regardless of the accuracy of the dynamic model used.The method uses the coordination diagram concept and provides trajectories that can easily be implemented in most industrial robot programming languages. Selection of the dynamical model is not a critical aspect, because a collision will never occur, even with an inaccurate dynamic model.However, since the algorithm tries to minimize the total motion time, precise models are required to obtain optimal results.This method is based on defining synchronization points16 as spots on the path of each robot where it will stop until the other robot arrives at its respective point.Once both robots are at these points, motion can continue.This problem can be solved by an A*algorithm.16,17 Additionally, the problem complexity is considerably reduced by using decoupled planning and the concept of the synchronization point.However the computational bur- Ž den in terms of memory needed and time required . to solve it can be prohibitive in some complex cases. This article shows how evolutionary algorithms can be used to obtain collision-free motion plans in a multi-robot environment.Global optimization algorithms imitating certain principles of nature such as simulated annealing and the field of evolutionary Ž. algorithms EAs have proved to be useful tools for the optimization of high-dimensional and highly nonlinear problems.The EA is based on biological observations18,19: the means of natural evolution Ž. natural selection and natural genetics and the survival of the fittest. The evolutionary algorithm maintains a population of problem solutions.First, the best individuals are selected to form the offspring using crossover and mutation.Finally, the worse individuals of the population are replaced by the new offspring to form a new population. The fundamental intuition of genetic algorithms20 explains why the EA performs an effective search. The EA presents a continual improvement using the pair selectionqmutation, working as a local search where the mutation operator slightly modifies a solution.If this new solution is better than previous ones, it will be accepted with a high probability by the selection mechanism.On the other hand, the pair selectionqcrossover avoids the process being trapped in a local minima, executing an intelligent jump to another search space region. The realization of fast search in wide space is the main quality of genetics algorithms as function optimizers.However, their capability for complete local search is limited.Holland21 suggested that genetic algorithms should be used as a preprocessor to perform the initial search, before tuning the search with local methods.Likewise, Grefensette22 pointed out that genetic algorithms are qualified to identify high performance regions of the search space and he recommends: ‘‘it may be useful to invoke a local search routine to optimize the members of the final population.’’ A local search using a hill-climbing strategy is proposed by Syrjakow and Szczerbicka.23 If the local search does not obtain a optimum value, the authors apply a backtracking process to execute a new genetic simulation. The article is organized as follows: Section 2 states the problem and describes the coordination diagram concept.Section 3 introduces the evolutionary algorithms and defines individual structures, genetic operators, and other parameters used in the algorithms.In Section 4 some results are presented to demonstrate the feasibility of the method.Finally, concluding remarks are given. 2. PROBLEM STATEMENT The problem can be stated as: Given two robots R1 and R, a set of known fixed obstacles, and the 2 initial and final configurations of Rand R, find a 12 coordinated motion plan for the robots from their initial configuration to their final configuration avoiding collisions with environment obstacles and themselves. To use the decoupled planning approach, it is necessary that a fixed obstacle collision-free path for each of the robots was previously obtained.These paths are obtained by considering only the fixed obstacles and not taking into account the other robot.There are many algorithms described in the literature1,8 which can solve this problem.The proposed algorithm is independent of the algorithm used for obtaining the fixed obstacle collision-free path for each robot, although some details of the method used for the applications presented are given in Section 4.The paths which the robots are expected to follow are assumed to be given as a parameterized curve in the joint space Ž. n Ps⌽ ␭ ,0F ␭ F ␭ with ⌽:RªR max where nis the number of degrees of freedom of the robot and ␭ is the distance along the path.Let P1 and P2denote the two collision-free paths generated for each of the manipulators.Let ␭ 1and max ␭ 2denote the length of both paths.The P1P2-space max is defined as the following R2region: P1P2yspace Ž12 .11 22 s ␭ , ␭ r0F ␭ F ␭ and 0F ␭ F ␭ 4 max max Ž12 .12 A point ␭ , ␭ in the PP-space represents a w snapshot of the robot’s configurations robot iartic- Ži.x ulation positions are ⌽ ␭ .Any continuous path i Ž. Ž 12 . from 0, 0 to ␭ , ␭ determines a coordinated max max execution of the two paths and is called a coordination path. Ž. Let the collision region CR be defined as the set of points in the P1P2-space where a collision between the two manipulators occurs.Normally, the CR consists of several connected subsets, with complex shapes.If a coordination path does not cross through the collision region, it is called a collision-free coordination path. To reduce the search space in the P1P2-space, a discretization of each path has to be made, so the path is divided into several equal-length intervals. Let the intervals of both paths be numbered from 1 to max and 1 to max , respectively.Let ␦ ibe the 12 k kth interval along the path of the manipulator i. Now, a path can be defined as an ordered set of intervals; that is,  i 4 ⍀s ␦ r1FkFmax ik i Ž12 .1 A cell is defined as a pair ␦ , ␦ where ␦ g⍀ mm m 1 and ␦ 2g⍀.For simplicity, a cell will be repren2 Ž. 4 sented as m,nand ⍀skr1FkFmax .With ii these discretized paths, the P1P2-space is transformed into an array of cells.This array of cells is Ž. the coordination diagram.Cell 1, 1 corresponds to the first interval of each path, that is, the lower left-hand cell of the coordination diagram, and Ž. max , max is the upper right-hand corner, the 12 Ž.12 last interval of each path.A cell m,ns ␦ = ␦ is mn considered as a free cell if it satisfies the following condition: 1122 Ž12 . ᭙ ␭ g ␦ , ␭ g ␦ « ␭ , ␭ fCR mn If the cell does not satisfy the above condition, it is considered as a collision cell.A correspondence between a path interval and robot configuration has to be established.A point ␭ , which is normally the k middle point, is associated to each interval k. Obtaining the coordination diagram is not a trivial problem.To evaluate whether the robots in a particular configuration are going to collide, it is necessary to determine if any link of one of the robot collides with any of the other robot’s links.A main aspect of this problem is the geometrical forms used in links modeling.Many types of geometrical shapes, such as convex polyhedra, spheres, or convex spherical polyhedra have been proposed in the literature to facilitate the task of detecting robot collisions.24 To determine the collision state of each cell is a more complex problem because the collision problem should be solved for each point in the cell. Only approximate solutions can be found.The technique used here was proposed by Lozano-Perez25 ´ and consists of determining the maximum displacement for each of the robot’s joints in the interval and increasing the size of the corresponding links accordingly.By using this technique, the resulting solid will include the volume swept by the moving link.Finally, in this article, a sweep-line algorithm11 has been used to obtain the coordination diagram. The size of the cells is an important factor.On the one hand, if the size of the cells chosen is too small, the computational time required by the algorithm may be prohibitive.On the other hand, the Ž. cell size has to be kept small because 1 the collision region will be oversized by the somewhat conservative sweep-line method if big cells are used Ž. and 2 the synchronization points are chosen to be the middle point of each cell.Large cells will decrease the size of the solution space and the optimality of the solution. A collision-free coordination path will be composed of a sequence of free cells.To implement a trajectory in the coordination diagram, the motion of both robots must be synchronized; that is, both robots have to be simultaneously on points of the path corresponding to free cell coordinates.This synchronization can be implemented in an open Ž loop manner defining timed trajectories for both robots and assuming that the trajectories will be . executed in the prescribed time .The open loop synchronization strategy is not very realistic, because collisions may be produced if one of the robots is not able to move at the programmed speed in one part of the trajectory; so to ensure that all robots are able to follow the trajectories, slow speeds have to be prescribed.Furthermore, timed trajectories cannot be implemented in many industrial robot programming languages. Robots can be synchronized by a closed loop strategy based on synchronization points.17 A synchronization point is a point in the coordination diagram which the robots have to reach; that is, any coordination path will necessarily pass through it. So, when a robot reaches a synchronization point, it waits for the other robot to reach the synchronization point before prosecuting its planned motion. This requires some sort of communication between robots.This type of synchronization has been used here and it is easy to implement because it is only necessary to connect a digital input with a digital output signal on each one of the controllers.Figure 1 shows a general structure of the system. To avoid a collision it is possible to alter the coordination path defining the number and position Trajectories Robot 1 Controller Controller Robot 2 Planner Figure 1. A general structure of the trajectory planner system. of the synchronization points.Figure 2 shows a coordination diagram, where the dark regions are the collision regions, and it illustrates how a collision-free coordination path can be found by using synchronization points for the case where robot 1 moves along its associated path faster than robot 2. A collision-free coordinated motion of two robots can be found by searching for a synchronization point sequence that minimizes the total coordinated motion time.The object of this article is to determine this synchronization point sequence. Let us consider a rectangle formed by free cells in the coordination diagram and let us consider the motion of the robots from the lower left corner cell to the upper right corner cell.Any trajectory defined for each robot between these two points in the coordination diagram will be a collision-free coordination path; that is, the robots may move from the starting point to the end point at any speed and a collision between them will never occur.This class of rectangles is going to be called free rectangles. Let us now consider a set of free rectangles, connected in such a way that the upper right corner of one rectangle is the lower left corner of the next. Furthermore, the lower left corner of the first one is the lower left corner of the whole coordination diagram, and the upper right corner of the last rectangle is the upper right corner of the coordination diagram, as can be seen in Figure 3.This set of rectangles is a free rectangle sequence, and the intersection points between two rectangles will be the synchronization points. Given a free rectangle sequence, any coordination path constrained to pass over every synchronization point of the sequence will be a collision-free Ω Ω2 1 Figure 2. Free coordination path using synchronization points. Ω2 Ω1 Figure 3. A free rectangle sequence. coordination path.This constraint is very easy to implement using most robot programming languages.The set of synchronization points will divide the path of each robot into several sections. Any section of the path between two synchronization points will be followed by every robot independently of the other, but a synchronization operation must be implemented at the end of the section, that is, at a synchronization point.The following is part of a program with the synchronization instructions written in VAL II, for the case of two robots. ROBOT 1 PROGRAM FOR is0TON wx MOVE 噛pts i END SIGNAL 1 Ž. WAIT SIG 1001 SIGNAL y1 With this program, it is possible to execute the coordinated motion of the robots from an initial position to a goal position, without collision, either with fixed obstacles in the environment or with the other robot. The problem now is to find a free rectangle sequence, that is, a synchronization point sequence that minimizes the total execution time necessary for the robots to complete their whole paths.The main variables used to find this sequence are the number of synchronization points, which depend on the collision region shape, and the position of these points in the coordination diagram.Notice that a delay is produced by adding a new synchronization point, because one of the robots has to stop to wait for the other robot. This optimization problem can be solved by an A*algorithm as shown by Ridao and Camacho17 although the great number of successors of each cell makes the searching tree too big, even with the pruning techniques suggested in ref.17.To give an idea of the complexity of the problem, let us consider a coordination diagram of m=ncells and pq2 synchronization points, with two of them fixed Ž. Ž . at positions 1, 1 and m,n.The number of potential solutions of this problem can be defined as the number of sequences with a number of synchronization points less than or equal to pq2 and can be computed as follows: Each solution of this problem can be obtained as two nondecreasing successions of pcoordinates 44 x,...,xand y,...,yin such a way that a 1p1pŽ. synchronization point is the pair x,y.Taking ii into account that coordinates xand yare indepenii dently chosen, the dimension of the search space is Ž. Ž. Ž. tm=tn, where tkis the number of different pp p 4 sequences of pintegers i,i,...,isuch that 1Fi 12 p1 Ž. FiF⭈⭈⭈ FiFk.Clearly, tkis the number of 2pp combinations with repetition taken in a group of p elements kqpy1 Ž. tks p ž/ p and the number of different synchronization point sequences is clearly given by mqpy1nqpy1 Ž. Ž. tm=tns= pp ž/ž/ pp For the case of a coordination diagram of 100= 100 and ps10, there are around 1023 possible solutions, while for a coordination diagram of 150=150 cells and ps20 there are around 1047 possible solutions. 3. THE PROPOSED ALGORITHM EAs are basically search algorithms that start with some population of structures, called individuals, that are initial solutions to the problem and repeatedly perform the following cycle of operations until a termination condition is satisfied: 䢇 Evaluation: Evaluate each individual in the population. 䢇 Selection: Depending on the fitness of the individuals, select some of them for reproduction. These individuals are called parents. 䢇 Reproduction: With some reproductive strategies, called genetic operators, generate some Ž. number of new individuals offspring from selected parents. 䢇 Replacement: Replace some or all of the original population with the offspring, forming a new generation of individuals. EAs usually have two different ending condi- Ž. tions: 1 the maximum number of generation and Ž. 2 a fixed number of generations without changes in the best individual.The first one is applied in this article.Some possible reproductive strategies are combinations of replicate or copies of some parents, crossover or recombination, where each new individual is constructed with inherited characteristics from its parents and mutation or change of an Ž. attribute or characteristic gene of an individual. The main aspects that define the application of evolutionary algorithms for global optimization problems are chromosomic structures undergoing adaptation, ways to create an initial population, a fitness measure that evaluates the structures, genetic operators to modify the structures, constraints on offspring, and parameters to control the process. 3.1. Chromosomic Representation of the Individual Each individual will represent a nondecreasing synchronization point sequence.Most of the problems solved using EAs represent individuals using fixed length chromosomes, because it is easier to implement genetic operators in this way.However, the number of synchronization points is a variable parameter in this application. The solution adopted here is to consider variable-length chromosomes.The length of the chromosome defines the number of synchronization points of the sequence.Let nbe the length of the chromosome.The initial point of the sequence is the Ž. path origin of each one of the robots 1, 1 and the Ž. last point is max , max .Between these two ver- 12 tices, an individual will be a set of synchronization 4 Ž. points Pwith 1FiFnwhere Psx,yand iiii x,yare points corresponding to the paths of the ii first and second robots, respectively.A robot is not allowed to move back along its path, so the codification of an individual is therefore constrained by this fact.This constraint is that the coordinates of successive synchronization points should be monotonically increasing; that is, xFxand yFy, for iiq1iiq1 all i.Finally, all the points should be in the coordi- nation diagram; i.e.,xG1, yG1, xFmax , and 11n1 yFmax .Considering that the coordination dian2 gram is a discretized space, every synchronization point can be represented by a pair of integer numbers, so every individual must verify  Ž. < 4 x,yg⍀=⍀᭙i,xFxand yFy ii 12 iiq1iiq1 1FiFn A synchronization point sequence will be considered to be determined by nq2 points, where Ž.Ž.Ž .Ž . x,ys1, 1 and x,ysmax , max . 00 nq1nq112 An individual has been defined as an acceptable individual if it is a monotonically increasing succession of synchronization points.However, two classes of acceptable individuals can be distinguished: 䢇 Valid individuals: An individual is valid if it forms an increasing sequence of free rectangles, and therefore defines a collision-free coordination path. 䢇 Nonvalid individuals: An individual is nonvalid if there is at least one nonfree rectangle in the sequence.Then it is possible that a collision between the robots may take place.These individuals are not considered as a solution to the problem. Finally, when a genetic operator is applied, it is possible for a decreasing synchronization point sequence to be obtained.It is not strictly an individual, but in this article, it will be called a nonacceptable individual. 3.2. Individuals in the Initial Population The initial population is selected randomly.The following procedure was proposed to obtain a initial population with a wide diversity of solutions in a first approach, taking into account that the number of synchronization points of individuals is variable: A maximum number of points NMAX is estab- Ž. lished only for the initial population , and the number of synchronization points of the individuals of the initial population is distributed in a random uniform way between 1 and NMAX. In this way, a similar number of individuals with one, two, and so on until NMAX synchronization points are generated. However, this uniform distribution of the number of points between 1 and NMAX was proved to be inappropriate in the tests.The reason is that Ž. nonoptimal solutions with few points can constitute local minima, and the population quickly converges toward them, losing genetic information. Therefore, the method improves when the individuals of the initial population have available a greater quantity of information, i.e., more points in the coordination diagram.For this, a increasing proba- Ž. bility distribution from 1 minimum to NMAX Ž. maximum was selected. Once the number of points nof an individual is selected, its coordinates are obtained as follows: two wx sets of nrandom values in 0, 1 are generated; then they are ordered in a increasing way and projected wxwx on 1, max and 1, max intervals, respectively. 12 3.3. Fitness Measure Ž. The objective is to minimize the cost function f,so that the fitness function must increase as the cost function decreases.There are many ways in which this can be accomplished, for example, by making the fitness function equal to a constant minus the cost function19 or by making the fitness function Ž. 26 equal to 1r1qf, which has been used here.The probability of selection of each individual has been made proportional to the fitness function, which has been normalized by dividing it by the sum of the fitness functions of all individuals in the population. The selected fitness function guarantees that the probability of selection of an individual with a low cost in relation to the rest of the individuals will not be too great at the beginning, whereas in a more advance phase of the process, the difference between individuals with similar values of the cost function will be enlarged. The evaluation of the cost function will consider the two different kinds of individuals: valid and nonvalid ones.In fact, two different cost functions will be used.For valid individuals, the cost function measures the total execution time needed by the robots to complete their paths when the synchronization points are placed at the positions defined by the individual specifications.Thus, to define the cost function for these individuals, it is necessary to use a model describing the robot motion.Dynamic models of the robot of different levels of complexity can be used for this purpose.That is, trajectory time can be computed from a simple model characterized by maximum acceleration and velocities of each joint, to a full dynamical model of the robot consid- ering inertia, Coriolis force, friction, load, and other nonlinearities such as saturation or back slashes. The paths used for the examples described in the article are composed of straight lines in the configuration space.This type of path has been chosen because it can easily be implemented on most industrial robots, although this is not an inherent feature of the method which can be used with other types of paths.The model used for this type of path is based on the works of Paul,27 Luh and Lin,28 and Tondu and El-Zorkany.29 The following assumptions are made for each joint: 䢇 The motion in each segment is made with constant speed, smooth transitions between segments, and a continuous acceleration profile.Maximum acceleration is reached in each transition. 䢇 The transition is carried out symmetrically. Maximum acceleration is produced at the middle point of the transition. 䢇 At each segment, the motion of each joint is synchronized with the movement of the rest of the joints.That is, the speed of each joint is computed to ensure that all joints finish their movements simultaneously. Therefore, for each joint, during the constant speed phase, the joint position grows linearly with time.A fourth degree polynomial is used to ensure continuity in the position, speed, and acceleration during the transition phases.29 The trajectory is specified with two parameters: the desired speed for each segment and maximum acceleration.These parameters can be obtained from the robot manufacturer or experimentally.In the case of the PUMA robot, the parameters given by Tondu and El- Zorkany29 were considered, while for the applications presented with other robots, these parameters were obtained experimentally in our laboratory. The cost function for nonvalid individuals is completely different.The execution time cannot be used as a cost measure, because this individual is not a solution of the problem.The function must measure how far it is from a valid individual.Obviously, the cost value for this kind of individual must be higher than any value for a valid individual.The function used is Ž. fNsKqnco where Kis a high value with respect to the value associated with the valid individuals, and nco is the number of collision cells inside the rectangle sequence.This cost function makes sense when finding initial valid solutions is difficult because of the complexity of the collision regions.By using a cost function such as the one we suggest, the algorithm is able to find valid solutions. 3.4. Genetic Operators Bearing in mind the special configuration of the individuals in this problem, modifications to the basic genetic operators are needed.The different genetic operators used in the algorithm are presented in this section.This includes the crossover and mutation operators.There have been many types of crossover and mutation operators proposed in the literature.Some of the genetic operators used here are extensions or modifications of previously proposed operators. 3.4.1. Crossover Operator Given two individuals S1and S2formed by sequences of nand msynchronization points, respectively, the idea is to obtain another sequence, through genetic information exchange from parents S1and S2.The following method is proposed Ž. Fig.4. A synchronization point of S1called Pis randomly selected.Then, Q, another synchronization point of S2, is selected.Qis the first randomly obtained point with the values of both coordinates xand ygreater than the respective coordinates of P, so the resulting child will be always an increasing sequence.It is possible that no point of S2 verifies this limitation, then the child is returned as Ω2 Ω1 P Q Child S parent 1 2 S parent Figure 4. Crossover operator. a copy of S1.If any point Qexists, a new individual 1Ž. is formed with the first points of SPinclusive , 2Ž. followed by the points of Sfrom Qinclusive to the end of S2.The number of SP of the child goes from two, when Pis the first SP of S1and Qthe last of S2,tonqmwhen Pis the last point of S1 and Qthe first one of S2. Afterward, all the synchronization points of the resulting individual with the same coordinate values are reduced to a single synchronization point, that is, the same individual but with a more simplified structure. 3.4.2. Mutation Operators A mutation produces a change in a gene of an individual.The proposed mutation types are described in the following paragraphs. 䢇 Slight mutation: Given an individual Ss  Ž. 4 x,yr1FiFn, two integer values are ranii domly chosen; the first one kso that 1FkFn and the second one mwith yMUTMAXFm FMUTMAX, where MUTMAX is the maximum permitted mutation.Then, this muta- Ž. tion consists of substituting point Psx,y kkk Ž. by xqm,yqm.This mutation has three kk variations: — Double mutation: This is the result of selecting two different values of mfor each coordinate. — Single mutation: This second possibility is the result of applying the mutation to only Ž. one of the coordinates of PFig.5. k — Nonuniform mutation: The third variant is obtained when MUTMAX varies as a function of the number of the executed generations. Ω2 Ω1 Before mutation After mutation mPk Ž. Figure 5. Slight mutation single mutation . Ω2 Ω1 P P P k-1 k k+1 Figure 6. Proportional mutation. The individuals obtained through these mutations can be nonacceptable ones, and so, some action must be taken to obtain acceptable individuals. 䢇 Strong mutation: Several strong mutations have been implemented and tested with satisfactory results.The following mutations are considered in this article: —Proportional mutation: Given an individual  Ž. 4 Ssx,yr1FiFn, an integer value k ii is randomly chosen so that 1FkFn.Then, Ž. the coordinates of the point Psx,y kkk will be changed by new values in such a way that they will be randomly distributed over the rectangle defined by the lower left Ž. vertex x,yand the upper right ky1ky1 Ž. vertex x,y; that is, Pwill be subkq1kq1k stituted by a new point inside the gray area in Figure 6.Every individual generated by this mutation is an acceptable one. This mutation has a variation consisting of modifying only one of the coordinates of the point, chosen randomly.This variation has been called the single proportional mutation. —Synchronization point elimination: This mutation eliminates a randomly selected synchronization point of S; that is, the new individual is identical to S, but with one SP less. —Segment mutation: This mutation chooses two consecutive synchronization points Ž. Ž . Psx,yand Psx,y, and kkk kq1kq1kq1 a slight mutation is applied to them with a probability.Thereafter, this mutation adds a new point between both of them.For this purpose, the differences dsxyxand xkq1k