Next: Conclusion: ContributionsDifficulties, and Up: No Title Previous: Principle of the Ariadne's
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:
to 
without collision.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.
. Decide if the best element can serve as an acceptable solution; if yes,
exit.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.
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
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.
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:
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