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 т800 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.

## 5. Conclusion: Contributions, Difficulties, And Perspectives

As mentioned in the Introduction, the Ariadne's clew algorithm has two main qualities:
efficiency, and generality. Let us, in conclusion, explain and discuss these two qualities.