**Next:** Conclusion:
ContributionsDifficulties, and **Up:** No
Title **Previous:** Principle
of the Ariadne's

In order to demonstrate the feasibility and qualities of the Ariadne's clew algorithm, we have developed a realistic application of the algorithm. We selected a problem where we want to have a path planner for a six DOF robot arm in a dynamic environment where another arm is used as a mobile obstacle. The robot (robot A) is under the control of the Ariadne's clew algorithm. It shares its workspace with a second robot (robot B) that is moving under the control of a random motion generator. The Ariadne's clew algorithm must be able to compute paths for A in ``real time'' (here, real time means fast enough to ensure that robot A will never collide with robot B).

In order to reach such a level of performance, we chose to implement the Ariadne's clew algorithm on a massively parallel machine (Meganode with 128 T800 Transputers). Furthermore, we selected a genetic algorithm as our optimization technique. The reasons for this choice are:

- Genetic algorithms are well suited for problems where the search space is huge but where there are many acceptable solutions. This is exactly the case here. The trajectory space is huge but there are, barring exceptional cases, numerous acceptable paths going from to without collision.
- Genetic algorithms, unlike a number of the other optimization techniques [Bessière, Talbi, Ahuactzin, Mazer 1996], are very easy to implement on parallel architectures. We have previously developed a parallel genetic algorithm (PGA) and we have already had significant experience using it [Talbi 1993].
- PGA, unlike most parallel programs, shows linear speed-up (when you double the number of processors you reduce the computation time by half) and even super-linear speed-up under certain circumstances [Talbi Bessière 1996].

Genetic algorithms are stochastic optimization techniques introduced by Holland [Holland 1975] twenty years ago. They are used in a large variety of domains including robotics [Ahuactzin, Mazer, Bessière, Talbi 1992, Lawrence 1991, Falkenauer Bouffouix 1991, Falkenauer Delchambre 1992, Meygret Levine 1992] because they are easy to implement and do not require algebraic expression for the function to be optimized.

The goal of the algorithm is to find a point reaching a ``good'' value
of a given function *F* over a search space *S*. First, a quantization
step is defined for S and the search is conducted over a discrete subset,
of *S*.
contains
elements. In practice, the cardinality of
can be *extremely* large. For example, in our implementation of EXPLORE,
*N* = 116. Thus, a continuous domain is discretized with a given resolution.

During an initialization phase a small subset of
is drawn at random. This subset is called a *population*. Each element
of this population is coded by a string of *N* bits.

The genetic algorithm iterates the following four steps until a solution is found.

**Evaluation**: Rank the population according to the value of*F*for each element of . Decide if the best element can serve as an acceptable solution; if yes, exit.-
**Selection**: Use the function*F*to define a probability distribution over the population. Select a pair of elements randomly according to this probability distribution. -
**Reproduction**: Produce a new element from each pair using ``genetic'' operators. -
**Replacement**: Replace the elements of the starting population by better new elements produced in step 3.

Many genetic operators [Davidor
1989] are available. However, the more commonly used are the *mutation*
and the *cross-over* operators. The mutation operator consists of
randomly flipping some bits of an element of the population. The cross-over
operator consists of first randomly choosing a place where to cut the two
strings of bits, and then building two new elements from this pair by simply
gluing the right and the left parts of the initial pair of strings (see
Figure 9).

**Figure 9:** The cross-over operation.

We use both operators to produce new elements. First, we use the cross-over operator to get an intermediate string. Then, the mutation operator is used on this intermediate string to get the final string.

There are many parallel versions of genetic algorithms: the standard parallel version [Robertson 1987], the decomposition version [Tanese 1987] and the massively parallel version [Talbi 1993]. We chose this last method. The main idea is to allocate one element of the population for each processor so that steps 1, 3, and 4 can be executed in parallel. Furthermore, the selection step (step 2) is carried out locally, in that each individual may mate only with the individuals placed on processors physically connected to it. This ensures that the communication overhead does not increase as the number of processors increases. This is the reason why PGA shows linear speed-up.

The parallel genetic algorithm iterates the following four steps until a solution is found.

**Evaluation**: Evaluate*in parallel*all the individuals.-
**Selection**: Select*in parallel*, among the neighbors, the mate with the best evaluation. -
**Reproduction**: Reproduce*in parallel*with the chosen mate. -
**Replacement**: Replace*in parallel*the parents by the offspring.

On the Meganode, we implemented the PGA on a torus of processors where each individual has four neighbors (see Figure 10)

**Figure 10:** A torus with sixteen processors. One individual is placed
on each processor. Each individual has four neighbors.

The evaluation functions used in SEARCH and EXPLORE
are very similar: they both compute the final position of the arm given
a Manhattan path of a fixed order. In our implementation, based on experience,
we chose to use Manhattan paths of order 2. Order 2 appeared to be a good
compromise between the number of landmarks needed (increases as order decreases)
and the computing time necessary for the optimization functions (increases
as order increases). Since our robot has six DOF,
the argument of the cost function in SEARCH is a vector
in
:
and the argument of the cost function used for EXPLORE
is a vector in
:
where *i* codes the landmark used as a starting point for the path.
In both cases the functions are defined only on a bounded subset of
and
, whose limits are fixed by the mechanical stops of the robot and the maximum
number of landmarks. A discretization step is chosen for these two subsets
by defining the resolution at which each elementary motion is discretized.
In our case, each
is discretized with 9 bits and the number of landmarks is limited to 256.
Thus, given a binary string of
bits, we can convert it into a vector (as an argument) for the cost function
of SEARCH, or EXPLORE, respectively.

Manhattan paths are evaluated in a simplified model of the environment. This model is obtained by enclosing each element of the scene into a bounding rectangular box.

The evaluation of a vector is performed as follows:

xxxxxxxxxxxx¯For each in

`Compute the limits on the motion for joint i. `

`Compute
by bouncing on these limits (see Section 3.4).
`

`Update the position of the robot. `

The limits on the motion of joint *i* are obtained by merging the
legal ranges of motion of all the links that move when joint *i* moves,
and all the obstacles. To obtain a legal range of motion between a link
and an obstacle, we consider the two enclosing parallelepipeds and express
their coordinates in the joint frame. Then, we use a classical method to
compute the range [Lozano-Pérez
1987].

In our parallel implementation, we distributed the geometric computations among several processors. Each processor is dedicated to the computation of a single type of interaction.

Finally, the Ariadne's clew algorithm is implemented in parallel with three levels of parallelism.

- Obviously, a first level of parallelization can be obtained by running SEARCH and EXPLORE at the same time on two sets of processors. While SEARCH is checking whether a path exists between the last placed landmark and the goal, EXPLORE is generating the next landmark.
- The second level of parallelism corresponds to a parallel implementation of both genetic algorithms employed by SEARCH and EXPLORE to treat their respective optimization problems.
- The third level corresponds to a parallelization of the collision checking function and range computation.

We completed a full implementation of these three levels on a Meganode with 128 T800 transputers. Figure 11 represents our parallel implementation of the Ariadne's clew algorithm and Figure 12 shows how we have embedded this architecture into our experimental setup. A CAD system (ACT) is used to model the scene with the two robots. The robots are under the control of KALI [Hayward, Daneshmend, Hayati 1988]. First, a simplified geometric model of the scene is downloaded into the memory of the transputers. Then, a Silicon Graphics workstation works as a global controller and loops over the following steps:

- Generate and execute a legal random motion for robot B.
- Send the new configuration of robot B to the Meganode as well as the desired final configuration for robot A.
- Get the planned path for robot A from the Meganode and execute it.
- Wait for a random time and stop robot A.
- Go to 1.

This sequence allows us to test our algorithm extensively in real situations by having to deal with many different environments. Of course, the most interesting figure we can obtain from this experiment is the mean time necessary to compute one path given a new environment. For this experimental setup this mean time is 1.421 seconds. Using the same architecture with more up-to-date processors (T9000) would reduce this time by a factor of ten. The same computation on a single processor (SPARC 5) would take three times longer than the current implementation.

*In summary, we have achieved our main goal by proving that it is
indeed possible (with the Ariadne's clew algorithm) to plan collision-free
paths for a real robot with many DOF in a dynamic
realistic environment*.

**Figure 11:** A parallel implementation of the Ariadne's clew algorithm

**Figure 12:** The experimental setup

Tue Nov 10 17:28:31 MET 1998