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

Path Planning for a Six DOF Arm in a Dynamic Environment


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:

  1. 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 tex2html_wrap_inline1416 to tex2html_wrap_inline1462 without collision.
  2. 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].
  3. 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].

Parallel Genetic Algorithm

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.

Principle of Genetic Algorithm

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, tex2html_wrap_inline1568 of S. tex2html_wrap_inline1568 contains tex2html_wrap_inline1574 elements. In practice, the cardinality of tex2html_wrap_inline1568 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 tex2html_wrap_inline1568 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.

  1. Evaluation: Rank the population according to the value of F for each element of tex2html_wrap_inline1568 . Decide if the best element can serve as an acceptable solution; if yes, exit.
  2. Selection: Use the function F to define a probability distribution over the population. Select a pair of elements randomly according to this probability distribution.
  3. Reproduction: Produce a new element from each pair using ``genetic'' operators.
  4. 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.

Principle of the Parallel Genetic Algorithm (PGA)

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.

  1. Evaluation: Evaluate in parallel all the individuals.
  2. Selection: Select in parallel, among the neighbors, the mate with the best evaluation.
  3. Reproduction: Reproduce in parallel with the chosen mate.
  4. 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.

Parallel Evaluation of the Cost Function

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 tex2html_wrap_inline1606 : tex2html_wrap_inline1608 and the argument of the cost function used for EXPLORE is a vector in tex2html_wrap_inline1610 : tex2html_wrap_inline1612 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 tex2html_wrap_inline1606 and tex2html_wrap_inline1610 , 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 tex2html_wrap_inline1620 is discretized with 9 bits and the number of landmarks is limited to 256. Thus, given a binary string of tex2html_wrap_inline1626 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  tex2html_wrap_inline1620  in

Compute the limits on the motion for joint i.

Compute tex2html_wrap_inline1634 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.

Parallel Implementation of the Ariadne's Clew Algorithm

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

  1. 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.
  2. 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.
  3. 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:

  1. Generate and execute a legal random motion for robot B.
  2. Send the new configuration of robot B to the Meganode as well as the desired final configuration for robot A.
  3. Get the planned path for robot A from the Meganode and execute it.
  4. Wait for a random time and stop robot A.
  5. 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

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

Emmanuel Mazer
Tue Nov 10 17:28:31 MET 1998