The algorithm is based on the following optimization problems:

$$\begin{array}{c}{{E X\,P L\,O R E:\left\{\begin{array}{l l}{{\mathrm{sup}}\,\,d(\Lambda_{i-1}\,,\,\hat{q}(l))}\\ {{l\in I\!\!R^{i}}}\end{array}\right.}}\\ {{\left.\begin{array}{l l}{{\mathrm{sup}}\,\,d(\Lambda_{i-1}\,,\,\hat{q}(l))}\\ {{l\in I\!\!R^{i}}}\end{array}\right.}}\end{array}$$

g(l) denotes the extremity of a legal path parameterized with   real parameters and starting either from each of the previously placed landmarks (EXPLORE) or from the latest placed landmark ( SEARCH ).

The algorithm is resolution-complete under the following assumptions:

- "Space filling completeness": The global maximum distance can be found by the optimization algorithm used in EXPLORE ; the configuration space is a compact set.

- " ρ completeness" :  The optimization procedure used in SEARCH always find a complete path (or returns 0) when the starting and the goal positions are located within a ball of radius ρ of the free space.
In practice, the first condition cannot be met with a randomized optimization algorithm in a bounded time, and only local maxima are found.  However, the landmarks placed according to the new algorithm are better distributed over the free space than landmarks placed randomly, leading to better performances. The goal of the next section is to justify this claim, experimentally.

## 4. 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 q o to q , without collision.