The robot systems movement optimization by genetic algorithms.

Schreiber, Peter ; Tanuska, Pavol

Abstract: Using of genetic algorithms for optimal trajectory estimation between two points of robot's working space is described in this article. Genetic algorithm used in the space without constraints is discussed in the first part of contribution. Necessary supplements of algorithm for solution of collisions with constraints are given in the second part of article, too.

Key words: Genetic algorithms, robot systems, trajectory, optimization.

1. INTRODUCTION

The motion of robotic arm can be optimized considering various criteria: travel time, energy consumption, length of trajectory end/or other. Let us use the trajectory length as criterion.

In the next text we do not consider the construction and the architecture of robots. We only suppose, that every point of robot's working space is reachable (that is there are minimal 3 degrees of freedom). Each desired position can be reached thru joints rotation and/or translation movement.

The trajectory between two points [X.sub.start] = [X.sub.0] a [X.sub.goal] = [X.sub.n] of robot's working space is a sequence of abscises [X.sub.0][X.sub.1], [X.sub.1][X.sub.2], ..., [X.sub.n-1][X.sub.n].

2. TASK DEFINITION

2.1 Working space M without constraints

The sequence of points [X.sub.start] = [X.sub.0], [X.sub.1], [X.sub.2], ..., [X.sub.n-1], [X.sub.n]=[X.sub.goal] should be found. The points number can be chosen according to accuracy of computation. The given open polygon represents the trajectory from starting point [X.sub.0] to goal [X.sub.n]. The number of trajectories is unlimited. The trajectory may be optimized considering the travel time, energy consumption and/or another criteria Let us use as criterion the length of the polygon. The shortest trajectory between two points in the space without constraints is direct line.

The trajectory length is a sum of Euclidean distances between neighboring points. This length should be minimal.

[n.summation over (i=1)] [square root of [([X.sub.i] - [X.sub.i-1]).sup.2]] [right arrow] min (1)

2.2 Working space with constraints

The pointed line [X.sub.start] = [X.sub.0], [X.sub.1], [X.sub.2], ..., [X.sub.n-1], [X.sub.n]=[X.sub.goal]. should be found in this case, too. Unlike the first case there are constraints [P.sub.i] in the robot's working space M. [P.sub.i] are geometrical objects (points sets) given by analytical description:

[P.sub.i] = {X; [g.sub.ji](X) [less than or equal to] 0}, where i = 1 ... k, [j.sub.i] = 1...[m.sub.i] (2) The number of objects is k and the object i is described by [j.sub.i] inequalities.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is then the union of all constraints. Points from P represent collision points, or, by another words, the sought trajectory can consist only of points X, where X[member of] M\P.

3. POSSIBLE WAYS OF OPTIMISATION

There are more optimum trajectories planning ways described in literature. Dynamical models using minimum-time criterion, graph-search scheme, exhaustive search methods, full dynamic models etc. However, only a two-joint arm was considered. The authors have reported a vast increase in a computation time with task increasing in size. The computations are made in C-space (configuration space), which represents the space of all possible configurations of working space.

All reported solution ways need complicated mathematical apparatus. However, they have advantages, too: Also joints and arms moving and dimensions are considered and secondly, the C-space allows to unify all kinds of trajectory searching and optimizing.

For all that a genetic algorithm can be used for the estimation of optimal trajectory. The genetic algorithm can be used in base form and the computations can be done in 3D-working space without transformation into C-space. (Karr & Freeman, 1999), (Man et al., 2000), (Zalzala & Fleming, 1997)

4. GENETIC ALGORITHM

We start with the working space without constraints. The next form of genetic algorithm can be used for estimation of optimal (shortest) trajectory points:

I. An initial population of n individuals or chromosomes (trajectories given by points) is generated.

II. The objective function (1) of each chromosome is evaluated.

III. Terminal conditions achievement (required objective function value, computation time or the iterations number) is tested. If the conditions are satisfied, the most successful chromosome is the asked solution.

IV. If the conditions are not satisfied, two groups of chromosome should be chosen for the next generation. There are "a" chromosomes in the first group, which go directly into the next generation. If the best chromosome is there, the new solution cannot be worse than the present one (elitism). The second group (work group) consists of n-a chromosomes for the genetic operations (crossover, mutation).

V. The genetic operations are performed with the chromosomes of the work group.

The new generation from the chromosomes of the first as well as of the work group is created. The algorithm continues with the step 2.

In our case the chromosome (individual) is a trajectory, i.e. a sequence of points. 100 random sequences (e.g. with 16 points) are generated and evaluated by objective function (1). 10 best trajectories are selected into new generation, 90 random selected ones are cross-overed with probability 0.8 and mutated with probability 0.1. (The cross-over operation means, that two trajectories exchange their parts, the mutation means, that one point of a trajectory is replaced by another one, which is random selected in an allowed space)

[FIGURE 1 OMITTED]

An example of two parent chromosomes, the better one of two children after the cross-over operation and the same chromosome after proper mutation are displayed in the next 2D-figures 2, 3 and 4 (for the transparency we used trajectories with only 6 segments (7 points)):

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

The proper trajectory similar to direct connection [X.sub.0][X.sub.6] can be found in a few hundreds generations. The computation of 600 generations takes time some seconds. The high probability of mutation (about 0.1) makes the computation time shorter.

5. WORKING SPACE WITH CONSTRAINTS

The sought trajectory can consist only of points, which do not belong to P. The points from P represent collisions.

[FIGURE 5 OMITTED]

The base genetic algorithm can be used in this case, too. The objective function (1) is the same like in the case without constraints. The constraints require next algorithm's supplements:

1. Only points from working space, which do not belong to P, can be generated in initial population. In addition, no point from the connection of two neighbouring points can be from P:

[X.sub.i] [member of] M\P for i = 1 ... k (3)

[X.sub.i-1][X.sub.i] [intersection] P = [empty set] for i = 1 ... k (4)

Condition (3) can be controlled by relation (2), the fulfilling of condition (4) is tested by computation of intersection (common points) of abscises [X.sub.i-1][X.sub.i] and space P.

2. A possible collision by cross-over operation must be predicted and eliminated: Segments [X.sub.a][X.sub.a+1] from one trajectory and the segment [Y.sub.a][Y.sub.a+1] in second trajectory are allowed, but by crossover they will be spited and the descendants will contain segments [X.sub.a][Y.sub.a+1] and [Y.sub.a][X.sub.a+1]. The new segments must be checked according to condition (4). If one of segments intersects some constraint, the crossover point in chromosomes must be moved in another position. If all cross-over positions are tested without success, the trajectories can not be cross-overed.

3. The similar situation rises by mutation: By the mutation of gene [X.sub.a] to allowed value [X.sub.a]' are the old allowed segments [X.sub.a-1][X.sub.a] and [X.sub.a][X.sub.a+1] replaced by new segments [X.sub.a-1][X.sub.a]' and [X.sub.a]'[X.sub.a+1], which maybe are not allowed. The fulfilling of condition (4) must be checked for new segments. If the condition fails, new value of mutated gene (new point of trajectory) must be generated and relevant segments must be tested again. It repeats till new segments fulfill the condition (4), i.e. they do not intersect a constraint.

Genetic algorithm with 3 given supplements works in robot's working space with constraints, too. The computation time depends on constraints analytical description (complexity of equations (2)).

6. PROBLEMS AND NEXT STEPS

An initialization of first generation can be complicated in special cases of spaces with constraints. The mathematical description of those situations should be done. The simulation and graphical visualization of described solution way is prepared. OpenGL--tool will be used. It allows to include the arms and joins dimensions and precisely calculates real collisions. (Bezak, 2007)

7. CONCLUSION

Genetic algorithms (even in the base form) are proper tool for movement of robotic arm optimization. The efficiency of algorithm depends on the number and complexity of analytical description (2) of possible constraints.

8. REFERENCES

Bezak, P. (2007). Genetic algorithms in engineering application. PhD-thesis (in Slovak). STU MTF Trnava.

Karr, C.L., Freeman, L.M. (1999). Industrial Applications of Genetic Algorithms. CRC Press, New York, London.

Man, K.F., Tang, K.S., Kwong, S. (2000). Genetic Algorithms. Concepts and Designs. Springer Verlag, London

Sekaj, I. (2001). Genetic Algorithms (in Slovak). AT&P Journal, vol. 8, no. 11, pp. 46-48.

Zalzala, A.M.S., Fleming, P.J. (1997). Genetic Algorithms in Engineering Systems. IEEE, London.