\documentclass[twoside,11pt]{article}

\usepackage{jair}
\usepackage{theapa}
\usepackage{psfrag,epsfig}      % to include psfrag and postscript figures

%%% ------------------------------- original tex start here

%\documentclass[a4paper,12pt]{article}
%\usepackage{fullpage}
%\usepackage{psfrag,epsfig}      % to include psfrag and postscript figures

%%% maximum fraction of the page that can be occupied by floats at the top or
%%% bottom of the page.
\renewcommand{\topfraction}{.9}
\renewcommand{\bottomfraction}{.9}
%%% minimum fraction of a float page that must be occupied by floats.
\renewcommand{\floatpagefraction}{.9}
%%% minimum fraction of a text page that must be devoted to text.
\renewcommand{\textfraction}{.1}

\input{jma-mar-96/THESE/TEXTE/commandes1}
\newcommand{\alfa}{\alfa}
\def\dtheta{\Delta\theta}
\newcommand{\Medskip }{ \vspace {.8 cm}}
\newcommand{\Bigskip }{ \vspace {1 cm}}
\newcommand{\hlambda}{{\hat{\lambda}}}
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\CO}{{\C \mbox{\it -obstacles}}}
\newcommand{\Cl}{\C_{free}}
\newcommand{\E}{{\cal {E}}}
\newcommand{\F}{{\cal {F}}}
\newcommand{\EC}{{\cal {EC}}}
\newcommand{\EE}{{\cal {EE}}}
\newcommand{\K}{{\cal {K}}}
\newcommand{\ER}{ensemble repre'sentatif}
\newcommand{\EL}{{\Lambda}}
\newcommand{\EM}{{\cal {EM}}}
\newcommand{\G}{{\cal G}}
\newcommand{\HP}{I\!\!P}
\newcommand{\LL}{{\cal L}}
\newcommand{\PP}{{\cal P}}
\newcommand{\W}{{\cal W}}
\newcommand{\T}{{\cal T}}
\newcommand{\TM}{\hat{\gamma}}
\newcommand{\TN}{\hat{\varphi}}
\newcommand{\TT}{\hat{\tau}}
\newcommand{\M}{{\cal M}}
\newcommand{\SP}{{\hspace {3 mm}}}
\newcommand{\VSP}{{\vspace {4 mm}}}
\newcommand{\CB}{{\cal {CB}}}
\newcommand{\NI}{n_{\circ}}
\newcommand{\NF}{n_{\bullet}}
\newcommand{\QI}{\hat{q}_{\circ}}
\newcommand{\XI}{\hat{x}_{\circ}}
\newcommand{\QF}{\hat{q}_{\bullet}}
\newcommand{\hq}{\hat{q}}
\newcommand{\hp}{\hat{q}}
\newcommand{\hx}{\hat{x}}
\newcommand{\hy}{\hat{y}}
\newcommand{\hc}{\hat{c}}

\newcommand{\confdim}{k}
\newcommand{\mandim}{l}


\newcommand{\pathdim}{{\confdim * \mandim}}
\newcommand{\Cfree}{\C_{free}}


\newtheorem{my_def}{\hspace{-1cm}Definition}
\newtheorem{my_theo}{\hspace{-1cm}Theorem}
\newtheorem{my_prop}{\hspace{-1cm}Proposition}
\newenvironment{our_def}[1]{\begin{quote}\begin{my_def}{(\bf
#1)}\\}{\end{my_def}\end{quote}}
\newenvironment{our_theo}[1]{\begin{quote}\begin{my_theo}{(\bf
#1)} \\}{\end{my_theo} \end{quote}}
\newenvironment{our_prop}[1]{\begin{quote}\begin{my_prop}{(\bf#1)}\\
}{\end{my_prop} \end{quote}\bigskip}


%style of the page
%\pagestyle{plain}		%head empty, foot with page number
%\pagestyle{empty}		%head and foot empty
%\pagestyle{headings}		%head wth document specific info., foot empty



\jairheading{9}{1998}{295-316}{9/97}{11/98}
\ShortHeadings{The Ariadne's clew algorithm}
{Mazer, Ahuactzin, \& Bessi\`{e}re}
\firstpageno{295}

\begin{document}
\title{The Ariadne's Clew Algorithm}

\author{\name Emmanuel Mazer  \email Emmanuel.Mazer@imag.fr \\
	\addr Laboratoire GRAVIR,\\ INRIA 665 Avenue de L'Europe \\
	 38330 Montbonnot, France \\ \AND \name Juan Manuel Ahuactzin
	 \email jmal@mail.udlap.mx \\ \addr Depto. de Ing. en Sistemas
	 Computationales \\ Unversidad de las Americas\\ Puebla,
	 Cholula, Puebla 72820, Mexico\\ \AND \name Pierre
	 Bessi\`{e}re \email Pierre.Bessiere@imag.fr \\ \addr
	 Laboratoire LEIBNIZ, \\ 46 Avenue Felix Viallet \\ 38000
	 Grenoble, France}

\maketitle

\begin{abstract}
We present a new approach to path planning, called the ``Ariadne's
clew algorithm''. It is designed to find paths in high-dimensional
continuous spaces and applies to robots with many degrees of freedom
in static, as well as dynamic environments --- ones where obstacles
may move. The Ariadne's clew algorithm comprises two sub-algorithms,
called {\sc search} and {\sc explore}, applied in an interleaved
manner. {\sc explore} builds a representation of the accessible space
while {\sc search} looks for the target. Both are posed as
optimization problems. We describe a real implementation of the
algorithm to plan paths for a six degrees of freedom arm in a dynamic
environment where another six degrees of freedom arm is used as a
moving obstacle. Experimental results show that a path is found in
about one second without any pre-processing.

\end{abstract}

\section{Introduction}

The path planning problem is of major interest for industrial
robotics. A basic version of this problem consists of finding a
sequence of motions for a robot from a start configuration to a given
goal configuration while avoiding collisions with any obstacles in the
environment.

A simple version of the problem, that of planning the motion of a
point robot among 3-dimensional polyhedral obstacles, has been proved
to be {\sc np}-complete~\cite{canny}. Generally speaking, the complexity of
the problem is exponential in the number of degrees of freedom ({\sc
dof}) of the robot, and polynomial in the number of
obstacles in the environment. Consequently, finding a path for a
robot with many {\sc dof} (more than five) in an environment with
several obstacles is, indeed, a very difficult problem. Unfortunately,
many realistic industrial problems deal with robots of at least six
{\sc dof} and hundreds of obstacles. Even worse, often the environment
is dynamic in the sense that some of the obstacles may move, thereby
further requiring that new paths be found in very short computing
times.

In this paper, we present a new approach to path planning, called the
``Ariadne's clew algorithm~\footnote{According to Greek legend,
Ariadne, the daughter of Minos, King of Crete, helped Theseus kill the
Minotaur, a monster living in the Labyrinth, a huge maze built by
Daedalus. The main difficulty faced by Theseus was to find his way
through the Labyrinth. Ariadne brilliantly solved the problem by
giving him a thread (or a clew) that he could unwind in order to find
his path back.}''. The approach is completely general and applies to a
broad range of path planning problems. However, it is particularly
designed to find paths for robots with many {\sc dof} in dynamic
environments.

The ultimate goal of a planner is to find a path from the initial
position to the target. However, while  searching for this path, the
algorithm may consider collecting information about the free space and
about the set of possible paths that lie in that free space. The
Ariadne's clew algorithm tries to do both at the same time: a
sub-algorithm called {\sc explore} collects information about the free space
with increasingly fine resolution, while, in parallel, an algorithm
called {\sc search} opportunistically checks whether the target can be
reached.

The {\sc explore} algorithm works by placing landmarks in the searched space
in such a way that a path from the initial position to any landmark is
known. In order to learn as much as possible about the free space,
the {\sc explore} algorithm tries to spread the landmarks uniformly all over
the space. To do this, it places the landmarks as far as possible from
one another. For each new landmark produced by the {\sc explore} algorithm,
the {\sc search} algorithm checks (with a local method) whether the target
can be reached from that landmark. Both the {\sc explore} and {\sc search}
algorithms are posed as optimization problems.

The Ariadne's clew algorithm is {\em efficient} and {\em general}:
\begin{enumerate}
\item
The algorithm is efficient in two senses:
\begin{enumerate}
\item
Experiments show that the algorithm is able to solve path planning
problems fast enough to move a six {\sc dof} arm in a realistic and
dynamic environment where another six {\sc dof} robot is used as a
moving obstacle.
\item
It is well suited for parallel implementation and shows significant
speed-up when the number of processors increases.
\end{enumerate}
\item
The algorithm is general in two senses:
\begin{enumerate}
\item
It may be used for a wide range of applications in robotics with
little additional effort to adapt it.
\item
Finally, the algorithm is general in that it may be adapted for a
large range of search problems in continuous spaces that arise in
fields that are not related to robotics.
\end{enumerate}
\end{enumerate}

The paper is organized as follows. Section~\ref{problem} presents the
path planning problem and discusses related
work. Section~\ref{principle} presents the principle of the Ariadne's
clew algorithm. Section~\ref{application} describes the
application of the algorithm to a six {\sc dof} arm in a dynamic
environment. Finally, Section~\ref{conclusion} concludes the paper
with a discussion of the contributions of our approach, the main
difficulties involved, and possible improvements of our method.

\section{The Path Planning Problem}
\label{problem}
Many versions of the path planning problem exist. An exhaustive
classification of these problems and of the methods developed to solve
them can be found in a survey by Hwang and Ahuja~\citeyear{Hwang}.
We choose to illustrate our discussion with a particular case. A robot
arm is placed among a set of obstacles. Given an initial and a final
position of the robot arm, the problem is to find a set of motions
that will lead the robot to move between the two positions without
colliding with the obstacles.

To drive the robot amidst the obstacles, early methods~\cite{brooks}
directly used the 3{\sc d} {\sc cad} models of the robot and of the obstacles to
find a solution, i.e., they considered the ``operational 3{\sc d}
space''. In this space, the path planning problem consists of finding
the movements of a complex 3{\sc d} structure (the robot) in a cluttered 3{\sc d}
space.

A major advance was to express the problem in another space known as
the configuration space, denoted by $\C$~\cite{Lozano87}. In this
space, the position (or configuration) of a robot is completely
determined by a single point having $n$ independent parameters as
coordinates. The positions that are not physically legal (because of a
collision) are represented by particular regions of $\C$, and are
called $\CO$. In the configuration space, the path planning problem
consists of finding a continuous curve (representing a path for a
single geometrical point) that (i) connects the points representing
the initial and the final configuration of the robot, and (ii) does
not intersect any $\CO$. This method trades a simplification of the
path planning problem (it searches a path for a single point) against
a higher-dimensional search space (the dimension of $\C$ is the number
{\sc dof} of the robot) and against more complex shapes of obstacles
(very simple physical obstacles may result in very complex $\CO$).

For example, let us consider the planar arm of
Figure~\ref{fig:work_sp}. Its position among the obstacles is totally
known once the values of the angles between its links $(q_0,q_1)$ are
known. Thus, for each pair $(q_0,q_1)$, it is possible to decide
whether the robot collides with the surrounding obstacles. This is
what we did in Figure~\ref{fig:CB_obst} to represent the mapping
between the physical obstacles in the operational space and the
$\CO$. Now, by moving a point along the curve joining $\hq_a$ and
$\hq_f$ one will also define a collision-free motion for the planar
arm between the corresponding positions $P(\hq_a)$ and $P(\hq_f)$ in
the operational space. This curve is one solution to this particular
path planning problem.

A recent trend in the field is to consider the ``trajectory
space''~\cite{ferbach} where a whole path is represented by a single
point. The coordinates of this point are the values of the parameters
defining the successive movements of the robot. For instance, the list
of successive commands sent to the robot controller indeed encode an
entire path of the robot. In this space, the path planning problem is
reduced to the search for a single point. Once again, we trade a
simplification of the path planning problem (searching for a point)
against a higher dimension of the search space (the dimension of the
trajectory space is the number of parameters needed to specify
completely a whole path). For example, in Figure~\ref{fig:CB_obst},
the path between $\hq_b$ and
$\hq_d$ can be represented by a
point in a seven-dimensional space simply by considering the length of
its seven segments.

\begin{figure}
\begin{center}
\psfrag{B0}[ll][][.75]{$\B_0$}
\psfrag{B1}[ll][][.75]{$\B_1$}
\psfrag{B2}[ll][][.75]{$\B_2$}
\psfrag{B3}[ll][][.75]{$\B_3$}
\psfrag{Aa}[ll][][.75]{$P(\hq_a)$}
\psfrag{Ab}[ll][][.75]{$P(\hq_b)$}
\psfrag{Ac}[ll][][.75]{$P(\hq_f)$}
\psfrag{x0}[ll][][.75]{$q_0$}
\psfrag{x1}[ll][][.75]{$q_1$}
\includegraphics[width=6.5cm]{planar.eps}
\end{center}
\caption{A two {\sc dof} arm placed among obstacles in the operational space }
\label{fig:work_sp}
\end{figure}

\begin{figure}
\begin{center}
\psfrag{C0}[cl][][.75]{$\C_{free_{\hq_a}}$}
\psfrag{C1}[cl][][.75]{$\C_{free_{\hq_b}}$}
\psfrag{qa}[cl][][.75]{$\hq_a$}
\psfrag{qb}[cl][][.75]{$\hq_b$}
\psfrag{qc}[cl][][.75]{$\hq_f$}
\psfrag{qd}[cl][][.75]{$\hq_d$}
\psfrag{CB0}[cl][][.75]{$\CB_0$}
\psfrag{CB2}[cl][][.75]{$\CB_2$}
\psfrag{CB3}[cl][][.75]{$\CB_3$}
\psfrag{x0}[cl][][.75]{$q_0$}
\psfrag{x1}[cl][][.75]{$q_1$}
\psfrag{2pi}[cl][][.75]{$2\pi$}
\psfrag{o}[cl][][.75]{$o$}
\includegraphics[width=6.5cm]{cs.eps}
\caption{The configuration space corresponding to Figure~\ref{fig:work_sp}.
Note: (1) $\C$ is a torus, (2) it is divided into two regions
{$\C_{free_{\hq_a}}$} and {$\C_{free_{\hq_b}}$} that cannot be
connected by a continuous path, and (3) there is not a $\C$-obstacle
for $\B_1$ because it does not interfere with the arm.}
\label{fig:CB_obst}
\end{center}
\end{figure}

\subsection{Global Approaches}

Global approaches are classically divided into two main classes:
(i) retraction methods, and (ii) decomposition methods. In the
retraction methods, one tries to reduce the dimension of the initial
problem by recursively considering sub-manifolds of the configuration
space. In the decomposition methods, one tries to characterize the
regions of the configuration space that are free of obstacles. Both
methods end up with a classical graph search over a discrete space. In
principle, these methods are {\em complete} because they will find a
path if one exists and will still terminate in a finite time if a path
does not exist. Unfortunately, computing the retraction or the
decomposition graph is an {\sc np}-complete problem: the complexity of this
task grows exponentially as the number of {\sc dof}
increases~\cite{canny}. Consequently, these planners are used only for
robots having a limited number (three or four) of {\sc dof}. In
addition, they are slow and can only be used off-line: the planner is
invoked with a model of the environment, it produces a plan that is
passed to the robot controller which, in turn, executes it. In
general, the time necessary to achieve this is not short enough to
allow the robot to move in a dynamic environment.

\subsection{Path Planning with Local Planners}

One way to combat the complexity of the problem is to trade
completeness against performance. To do this, the local planners are
guided by the gradient of a cost function (usually the Euclidean
distance to the goal) and take into account the constraints introduced
by the obstacles to avoid them~\cite{Fav87}. Since the path planning
problem is {\sc np}-complete, knowing the cost function, it is always
possible to design a deceptive environment where the method will get
trapped in a local minimum. However, these methods are useful in many
industrial applications because they can deal with complex robots and
environment models having thousands of faces, that are often too
time-consuming for global methods.

\subsection{Path Planning with Randomized Techniques and Landmarks}

The stochastic or random approach was first introduced by Barraquand
and Latombe~\citeyear{Barraquand90}, and later used by
Overmars~\citeyear{Overmars92}, and more recently by
Kavraki~\citeyear{kavraki}. The main idea behind these algorithms is to
build a graph in the configuration space. The graph is obtained
incrementally as follows: a local planner is used to try to reach the
goal. Should the motion stop at a local minimum, a new node (or
landmark) is created by generating a random motion starting from that
local minimum. The method iterates these two steps until the goal
configuration has been reached from one of these intermediary
positions by a gradient descent motion. These algorithms work with a
discretized representation of the configuration space. They are known
to be {\em probabilistically complete} because the probability of
terminating with a solution (a path has been found or no path exists)
converges to one as the allowed time increase towards infinity. As in
the previous section, it is also possible to design simple deceptive
environments that will make this kind of algorithm slower than a pure
random approach. However, they have been tested for robots with a high
number of {\sc dof} and they have been shown to work quickly in
relatively complex and natural environments.

Other methods using landmarks have been devised. For example,
{\sc sandros}, introduced by Chen and Hwang\citeyear{Hwang}, makes use of
landmarks to approximate the free space. This approach is similar to
the ``hierarchical planning'' approach used in {\sc ai}: should the method
fail to reach a goal, new subgoals are generated until the problem is
easy enough to be solved. In their approach, first a local planner is
used to reach the final position: should the local planner fail, the
configuration space is divided into two subspaces, one containing the
goal and the other a new sub-goal. The problem is therefore divided
into two sub-problems: (i) going from the initial position to the
subgoal, and (ii) going from the subgoal to the final
position. {\sc sandros} has been shown to be particularly well adapted to
find paths for manipulators. It has been implemented and tested for
planning paths for Puma and Adept robots.

\subsection{Path Planning in the Trajectory Space}

The previous methods were essentially based on the configuration
space: the retraction, the decomposition, or the optimization is made
in this space. An alternative is to consider the ``trajectory
space''. For example, in his method {\sc vdp},
Ferbach~\citeyear{ferbach} starts by considering the straight line
segment joining the initial and the final configuration in $\C$. This
path is progressively modified in such a manner that the forbidden
regions it crosses are reduced. At each iteration, a sub-manifold of
$\C$ containing the current path is randomly generated. It is then
discretized and explored using a dynamic programming method that uses
the length across the forbidden region as the cost function in order
to minimize. The search results in a new trajectory whose intersection
with the forbidden regions is smaller than the original
trajectory. The process is repeated until an admissible trajectory is
found. As in the previous sections, it is also possible to design
simple deceptive environments that will make this kind of algorithm
slower than a pure random approach.

The work of Lin, Xiao, and Michalewicz~\citeyear{xiao94} is similar to
our approach. As in an early version of our algorithm~\cite{jma92},
genetic algorithms are used to carry out optimization in the
trajectory space. Trajectories are parameterized using the coordinates
of intermediary via-points. An evolutionary algorithm is used to
optimize a cost function based on the length of the trajectory and the
forbidden region crossed. The standard operators of the genetic
algorithms have been modified and later extended to produce a large
variety of paths~\cite{xiao96}. The number of intermediary via-points
is fixed and chosen using an heuristic. Given this number, nothing
prevents to design a deceptive problem which solution will require
more intermediary points, leading the algorithm to fail while one
solution exists.



\section{Principle of the Ariadne's Clew Algorithm}
\label{principle}

As we have seen in the previous section, the computation of the
configuration space $\C$ is a very time-consuming task. The main idea
behind the Ariadne's clew algorithm is to avoid this computation. In
order to do this, the algorithm searches directly for a feasible path
in the trajectory space. The configuration space $\C$ is never
explicitly computed.

As will be shown, in the trajectory space, path planning may be seen
as an optimization problem and solved as such by an algorithm called
{\sc search}. It is possible to build an approximation of free space
by another algorithm called
{\sc explore} that is also posed as an optimization problem. The Ariadne's
clew algorithm is the result of the interleaved execution of {\sc search}
and {\sc explore}.

\subsection{Path Planning as an Optimization Problem: {\sc search}}

Given a robot with $k$ {\sc dof}, a trajectory of length $l$ may be
parameterized as a sequence of $n=k*l$ successive movements. A
starting point $\QI$ along with such a parameterized trajectory
implicitly define a path and a final configuration $\hq_l$ in the
configuration space. For example, for a holonomic mobile robot the
trajectory ($\theta^1,d^1,\theta^2,d^2,...\theta^l,d^l$) can be
interpreted as making a $\theta^1$ degree turn, moving straight $d^1$,
making a $\theta^2$ degree turn and so on. Given the starting
configuration $\QI$, this trajectory leads to the final configuration
$\hq_l$ (see Figure~\ref{fig:exe_vector}).


\begin{figure}
\begin{center}
\psfrag{t1}[ll][][.75]{$\theta^1$}
\psfrag{t2}[ll][][.75]{$\theta^2$}
\psfrag{t3}[ll][][.75]{$\theta^3$}
\psfrag{l1}[ll][][.75]{$d^1$}
\psfrag{l2}[ll][][.75]{$d^2$}
\psfrag{l3}[ll][][.75]{$d^3$}
\psfrag{QI}[ll][][.75]{$\QI$}
\psfrag{QF}[ll][][.75]{$\QF=(x_f,y_f)$}
\psfrag{x}[ll][][.75]{$x$}
\psfrag{y}[ll][][.75]{$y$}
\psfrag{ql}[ll][][.75]{$\hq_{\ell}$}
\includegraphics[width=8.5cm]{jma-mar-96/THESE/DRAWS/exe_vector.eps}
\end{center}
\caption{A parameterized trajectory
($\theta^1,d^1,\theta^2,d^2,...\theta^l,d^l$) and a starting point
$\hq_0$ implicitly define a path (in the operational space) for a
holonomic mobile robot.}
\label{fig:exe_vector}
\end{figure}

Given a distance function $d$ on the configuration space, if we find a
trajectory such that it does not collide with any obstacles and such
that the distance between $\hq_l$ and the goal $\QF$ is zero, then we
have a solution to our path planning problem. Therefore, the path
planning problem may be seen as a minimization problem where:
\begin{enumerate}
\item
The search space is a space of suitably parameterized trajectories,
the trajectory space.
\item
The function to minimize is $d(\hq_l,\QF)$ if the path is
collision-free, and $d(\hq_{i},\QF)$ otherwise
($\hq_{i}$ being the first collision point).\footnote{Another
possible choice would be to give the $+\infty$ value to the distance
when a collision occurs. However, this is less informative than the
chosen function because the first part of a colliding path could be a
good start toward the goal and should not be discarded. Note that the
cost function does not include any optimality criteria such as the
length of the trajectory or the amount of energy used.}
\end{enumerate}


The algorithm {\sc search}, based on this very simple technique and a
randomized optimization method, is already able to solve quite complex
problems of robot motion planning. For example,
Figure~\ref{fig:dyna_mob} represents the two paths found for the
holonomic mobile robot. Each path was computed on a standard
workstation ({\sc sparc 5}) in less than 0.5 second without using any
pre-computation of the configuration space. Thus, it is possible,
albeit slowly, to get a planner that can be used in a dynamic
environment (where the obstacles may move) by ``dropping'' a new world
into the system every 0.5 second. {\sc search} is very efficient but it is
not complete, since it may fail to find a path even if one exists for
two different reasons:
\begin{enumerate}
\item
Due to the optimization-based formulation, {\sc search} can get trapped by
local minima of the objective function, which in turn may place the
robot far away from the goal (see Figure~\ref{fig:exe_mini}).
\item The length $l$ of the trajectories considered may be too short to
reach all the accessible regions of the configuration space.
\end{enumerate}


\begin {figure} [htb]
\centerline{\frame{\psfig{figure=jma-mar-96/THESE/DRAWS/porte1.pss,width=6.5cm}}
\frame{\psfig{figure=jma-mar-96/THESE/DRAWS/porte2.pss,width=6.5cm}}}
\caption{Reactive replanning in a changing environment}
\label{fig:dyna_mob}
\end{figure}

\begin {figure}[htb]
\begin{center}
\psfrag{A}[ll][]{$\QI$}
\psfrag{B}[ll][]{$\QF$}
\includegraphics[width=3.5cm]{jma-mar-96/draws/HONOLOLU/minima.idw}
\end{center}
\caption{A problem leading to a local minimum. In such a case, a solution
path has first to move away from the goal. The goal's ``attraction''
based on the minimization of the Euclidean distance prevents {\sc search}
from finding such a path.}
\label{fig:exe_mini}
\end{figure}

\subsection{Exploring as an Optimization Problem: {\sc explore}}

In order to build a complete planner, we propose a second algorithm
called {\sc explore}. While the purpose of {\sc search} was to look directly for a
path from $\QI$ to $\QF$, the purpose of {\sc explore} is to compute an
approximation of the region of the configuration space accessible from
$\QI$.

The {\sc explore} algorithm builds an approximation of the accessible space
by placing landmarks in the configuration space $\C$ in such a way
that a path from the initial position $\QI$ to any landmark is
known. In order to learn as much as possible about the free space, the
{\sc explore} algorithm tries to spread the landmarks uniformly over the
space (see Figure~\ref{fig:spread}). To do this, it tries to put the
landmarks as far as possible from one another by maximizing the
distances between them.\\

\begin{figure}
\centerline{\frame{\psfig{figure=jma-mar-96/draws/HONOLOLU/seq1.idwps,width=
5.2 cm}}
\frame{\psfig{figure=jma-mar-96/draws/HONOLOLU/seq6.idwps,width=5.2cm}}
\frame{\psfig{figure=jma-mar-96/draws/HONOLOLU/seq8.idwps,width=5.2cm}}}
\caption{The first picture represents the initial position and the first
landmark. The subsequent landmarks are then uniformly spread over the
search space while the method keeps track of all paths joining the
landmarks to the initial position. The algorithm is named after
Ariadne because by placing landmarks, {\sc explore} unwinds as if it were
using a thread as Theseus did.}
\label{fig:spread}
\end{figure}

Therefore, {\sc explore} may be seen as a maximization problem where:
\begin{enumerate}
\item
The search space is the set of all paths starting from one of the
previously placed landmarks.
\item
The function to maximize is $d(\hq_l,\Lambda)$, where $\Lambda$ is the
set of landmarks already placed.
\end{enumerate}

\subsection{The Ariadne's Clew Algorithm: {\sc explore} + {\sc search}}

In order to have a planner that is both complete and efficient, we
combined the two previous algorithms {\sc search} and {\sc explore} to obtain the
Ariadne's clew algorithm.

The principle of the Ariadne's clew algorithm is very simple:
\begin{enumerate}
\item
Use the {\sc search} algorithm to find whether a ``simple'' path exists
between $\QI$ and $\QF$.
\item
If no ``simple'' path is found by step 1, then continue until a path
is found.
\begin{enumerate}
\item
Use {\sc explore} to generate a new landmark.
\item
Use {\sc search} to look for a ``simple'' path from that landmark to $\QF$.
\end{enumerate}
\end{enumerate}

The Ariadne's clew algorithm will find a path if one exists. In an
overwhelming number of cases, just a few landmarks are necessary for the
Ariadne's clew algorithm to reach the target and stop.

\subsection{A Major Improvement: Bouncing on $\C$-Obstacles}
\label{para:bounce}

A typical difficulty for a path planning algorithm is to find a
collision-free path through a small corridor in the configuration
space. This is also the case for the basic version of the Ariadne's
clew algorithm, presented above. The problem is that very few
trajectories encode such paths and therefore they are very difficult
to find. Most trajectories collide with the obstacles. We propose a
very simple idea to deal with this problem: going backwards at each
collision point. If, for a given trajectory, a collision is detected
along the corresponding path, then we simply consider transforming
that trajectory so that it encodes a new path, one that is found by
bouncing off the obstacle at the collision point (see
Figure~\ref{fig:bounce}). Note that this construction is applied
recursively until the entire trajectory corresponds to a
collision-free path.


\begin {figure}
\begin{center}
\includegraphics[width=6.5cm]{bounce1.eps}
\end{center}
\caption{Bouncing against $\C$-obstacles. Figure (a) presents the original path
in the configuration space. Figure (b) shows the same path after two
bounces along the second segment on obstacle 2 and on obstacle
1. Figure (c) is the result obtained after a bounce of segment 3
against obstacle 2. Finally, Figure (d) presents a valid path obtained
after a final bounce of segment 4 against obstacle 2.}
\label{fig:bounce}
\end{figure}

Using this technique, all trajectories are so transformed that they
encode valid paths. This improved version of the Ariadne's clew
algorithm no longer cares about obstacles. From the point of view of a
search in the trajectory space, it is as if the obstacles have simply
vanished. This method is especially efficient for narrow corridors in
the configuration space. Without bouncing, the mapping of a corridor
in the configuration space to the trajectory space is a set of very
few points. With bouncing, every single trajectory going through a
part of the corridor is ``folded'' into the corridor (see
Figure~\ref{fig:bounce}). The resultant mapping of the corridor in the
trajectory space is consequently a much larger set of points, and
therefore it is much easier to find a member of this set. This
empirical improvement has a major practical impact because it makes
the proposed algorithm faster (fifteen times) in the problem
considered below.


\subsection{The Algorithm}
We can now give a final version of the Ariadne's clew algorithm. It
has three inputs: $\QI$ (the initial position), $\QF$ (the goal
position), and $\rho$ (the maximum allowed distance for a path to the
$\CO$). It returns a legal path or terminates if no path exists at the
given resolution. \\

\begin{figure}[h]
\begin{center}
\fbox{
\begin{minipage}[t]{0.96\textwidth}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\= \kill $ALGORITHM\_ARIADNE(\QI,\QF,\rho)$ \\ begin
\\
\>$i := 1; \hlambda_1 := \QI$; \\
\>/* Initialize the set of landmarks with the initial position \\
\>$\EL_1:= \{\hlambda_1\}$; ${\varepsilon_1 = +\infty}$; \\
\>do while ($\varepsilon_i > \rho$); \\
\>\>/* run {\sc search} : look for the goal with a local method \\
\>\>if $(\min_{l \in \R^{\ell}}
                            d(\QF,\hq(l)) == 0$)\\
\>\>\>return; /*  A path has been found ! \\
\>\>else \\
\>\>/* run {\sc explore} : place a new landmark  \\
\>\>\>$i\ :=\ i+1$;\\
\>\>\>$\hlambda_{i} := \hq :\sup_{l \in \R^{\ell}}
                            d(\EL_{i-1},\hq(l)) $; \\
\>\>\>$\EL_{i} := \EL_{i-1} \cup \{\hlambda_{i}\}$; \\
\>\>\>$\varepsilon_i := d(\EL_{i-1},\hlambda_{i})$;  \\
\>\>endif\\
\>enddo \\
\>$\EL=\EL_i$; \\
\>$\varepsilon = \varepsilon_i$;\\
\>return($\varepsilon$); /* No path ! \\ 
end
\end{tabbing}
\end{minipage}}
\end{center}
\caption{The Ariadne's Clew Algorithm}
\end{figure}

\newpage

The algorithm is based on the following optimization problems:

$$EXPLORE: \left \{ \begin {array}{ll} \mbox{sup }
                d(\EL_{i-1},\hq(l))\\ l \in \R^\ell \\ \end {array}
                \right. $$

$$SEARCH: \left \{ \begin {array}{ll} \mbox{min } d(\hq(l),\QF) \\ l
                \in \R^\ell\\ \end{array} \right. $$

$\hq(l)$ denotes the extremity of a legal path parameterized with
$\ell$ real parameters and starting either from each of the previously
placed landmarks ({\sc explore}) or from the latest placed landmark
({\sc search}).

The algorithm is resolution-complete under the following assumptions:

\begin{itemize}
\item ``Space filling completeness'': The global maximum distance can be
found by the optimization algorithm used in {\sc explore}; the configuration
space is a compact set.
\item ``$\rho$ completeness'':  The optimization procedure used in {\sc search}
always find a complete path (or returns 0) when the starting and the
goal positions are located within a ball of radius $\rho$ of the free
space.
\end{itemize}

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.

\section{Path Planning for a Six {\sc dof} Arm in a Dynamic Environment}
\label{application}

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 {\sc 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:
\begin{enumerate}
\item
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 $\QI$
to $\QF$ without collision.
\item
Genetic algorithms, unlike a number of the other optimization
techniques~\cite{bessiere96a}, are very easy to implement on parallel
architectures. We have previously developed a parallel genetic
algorithm ({\sc pga}) and we have already had significant experience
using it~\cite{talbi93a}.
\item {\sc 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~\cite{bessiere96b}.
\end{enumerate}

\subsection{Parallel Genetic Algorithm}

Genetic algorithms are stochastic optimization techniques introduced
by Holland~\citeyear{Holland75} twenty years ago. They are used in a
large variety of domains including robotics
\cite{jma92,Lawrence91,Falkenauer91,Falkenauer92,Meygret}
because they are easy to implement and do not require algebraic
expression for the function to be optimized.

\subsubsection{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, $S_d$ of $S$. $S_d$ contains $2^N$ elements. In practice, the
cardinality of $S_d$ can be {\em extremely} large. For example, in our
implementation of {\sc explore}, $N = 116$. Thus, a continuous domain is
discretized with a given resolution.

During an initialization phase a small subset of $S_d$ is drawn at
random. This subset is called a {\em 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.

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

Many genetic operators~\cite{Davidor89b} are available. However, the
more commonly used are the {\em mutation} and the {\em 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~\ref{fig:crossover}).


\begin {figure} [htb]
\centerline{\psfig{figure=crossover.idw,width=8cm}}
\caption{The cross-over operation.}
\label{fig:crossover}
\end {figure}

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.

\subsubsection{Principle of the Parallel Genetic Algorithm ({\sc pga})}

There are many parallel versions of genetic algorithms: the standard
parallel version \cite{Robertson87}, the decomposition version
\cite{Tanese87} and the massively parallel
version~\cite{talbi93a}. 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 {\sc pga} shows linear speed-up.

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

\begin{enumerate}

\item {\bf Evaluation}: Evaluate {\em in parallel} all the individuals.

\item {\bf Selection}: Select {\em in parallel}, among the neighbors, the
mate with the best evaluation.

\item {\bf Reproduction}: Reproduce {\em in parallel} with the chosen mate.

\item {\bf Replacement}: Replace {\em in parallel} the parents by the offspring.

\end{enumerate}

On the Meganode, we implemented the {\sc pga} on a torus of processors
where each individual has four neighbors (see Figure~\ref{fig:torus})

\begin {figure}[htb]
\centerline{\psfig{figure=torus.idw,width=10cm}}
\caption{A torus with sixteen processors. One individual is placed on each
processor. Each individual has four neighbors.}
\label{fig:torus}
\end {figure}

\subsection{Parallel Evaluation of the Cost Function}

The evaluation functions used in {\sc search} and {\sc 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 {\sc
dof}, the argument of the cost function in {\sc search} is a vector in
$R^{12}$:
$(\Delta_1^1,\Delta_2^1,...,\Delta_6^1,\ldots,\Delta_{1}^2,\ldots,\Delta_6^2
)$ and the argument of the cost function used for {\sc explore} is a vector
in $\N \times \R^{12}$ : $(i,\Delta_1^1,\Delta_2^1,...,
\Delta_6^1,\ldots,\Delta_{1}^2,\ldots,\Delta_6^2)$ 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 $\R^{12}$ and $\N \times
\R^{12}$, 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 $\Delta_i^j$ is
discretized with $9$ bits and the number of landmarks is limited to
$256$. Thus, given a binary string of $116=8 + 12 \times 9$ bits, we can
convert it into a vector (as an argument) for the cost function of
{\sc search}, or {\sc 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:
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\= \kill For each $\Delta_{i}^j$ in
$(\Delta_1^1,\Delta_2^1,...,
\Delta_6^1,\ldots,\Delta_{1}^2,\ldots,\Delta_6^2 )$ \\
\> Compute the limits on the motion for joint $i$. \\
\> Compute ${\Delta_{i}^j}'$ by bouncing on these limits
(see Section~\ref{para:bounce}). \\
\> Update the position of the robot.
\end{tabbing}

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~\cite{Lozano87}.

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.

\subsection{Parallel Implementation of the Ariadne's Clew Algorithm}

Finally, the Ariadne's clew algorithm is implemented in parallel with
three levels of parallelism.
\begin{enumerate}
\item
Obviously, a first level of parallelization can be obtained by running
{\sc search} and {\sc explore} at the same time on two sets of processors. While
{\sc search} is checking whether a path exists between the last
placed landmark and the goal, {\sc explore} is generating the next landmark.
\item
The second level of parallelism corresponds to a parallel
implementation of both genetic algorithms employed by {\sc search} and
{\sc explore} to treat their respective optimization problems.
\item
The third level corresponds to a parallelization of the collision
checking function and range computation.
\end{enumerate}

We completed a full implementation of these three levels on a Meganode with
128 {\sc t}800 transputers. Figure~\ref{fig:parallel_archi} represents
our parallel implementation of the Ariadne's clew algorithm and
Figure~\ref{fig:archi} shows how we have embedded this architecture
into our experimental setup. A {\sc cad} system {\sc (act)} is used to
model the scene with the two robots. The robots are under the control
of {\sc kali}~\cite{kali}. 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:

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

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
({\sc t}9000) would reduce this time by a factor of ten. The same
computation on a single processor ({\sc sparc 5}) 
would take three times longer than the current implementation.

{\em 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 {\sc dof} in a dynamic
realistic environment}.

%\begin {figure}[htb]
%\centerline{\psfig
%{figure=3{\sc d}/home/alcyone2/mazer/journals/ijrr/jma-mar-96/THESE/DRAWS/site.pss,width=3D3D10 cm}}
%\caption{real experimental setup.}
%\label{fig:reel}
%\end{figure}

%\begin {figure}[htb]
%\centerline{\psfig
%{figure=3D/home/alcyone2/mazer/journals/ijrr/jma-mar-96/THESE/DRAWS/scene_actg2.pss,width=3D3D13 cm}}
%\caption{CAD model of the real scene}
%\label{fig:scene_act}
%\end{figure}


\begin{figure}
\begin{center}
\psfrag{1}[cc][][.60]{{\small Ariadne's clew algorithm}}
\psfrag{2}[cc][][.60]{{\small {\sc pga}}}
\psfrag{3}[cc][][.60]{{\small Range computation}}
\psfrag{4}[cc][][.5]{{\small type A et B}}
\psfrag{5}[cc][][.5]{{\small type C}}
\psfrag{H}[cc][][.60]{{\small {\bf Master}}}
\psfrag{S}[cc][][.60]{{\small {\bf Search}}}
\psfrag{E}[cc][][.60]{{\small {\bf Explore}}}
\psfrag{GA}[cc][][.60]{{\small {\bf AG}}}
\psfrag{G}[cc][][.60]{{\small {\bf Gamma}}}
\psfrag{PAB}[cc][][.60]{{\small {\bf Psi\_AB}}}
\psfrag{PC}[cc][][.60]{{\small {\bf Psi\_C}}}
\psfrag{psab}[cc][][.60]{{\small {\bf psi\_ab}}}
\psfrag{psc}[cc][][.60]{{\small {\bf psi\_c}}}
\includegraphics[width=12cm]{jma-mar-96/THESE/DRAWS/parallel_archi.eps}
\end{center}
\caption{A parallel implementation of the Ariadne's clew algorithm}
\label{fig:parallel_archi}
\end{figure}

\begin {figure}[htb]
\centerline{\psfig{figure=archi.idw,width=12cm}}
\caption{The experimental setup}
\label{fig:archi}
\end{figure}

\section{Conclusion: Contributions, Difficulties, and Perspectives}
\label{conclusion}

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

\subsection{Performance}

Comparing the performance of this kind of algorithm is a very delicate
subject. Performance may be a matter of computing time, efforts needed
to program, or ease of application to
different problems (see Section~\ref{lab:generi}). Evaluating the performance
in terms of computing time is very difficult for one fundamental and
three practical reasons:
\begin{enumerate}
\item
The fundamental reason is, once again, the {\sc np}-completeness of the path
planning problem. As deceptive cases may always be designed, the only
performance results one may reasonably present are always specific.
\item
The three practical reasons are:
\begin{enumerate}
\item
Obviously, the first requirement for such a comparison is that
different algorithms run on the same machines with the same available
memory. This may seem simple but it is a main difficulty in our case
because our algorithm has been designed to run on rather specific
kinds of machines, namely, massively parallel ones. It could also be
implemented on non-parallel machines, but then it may lose part of its
interest. A fair comparison would be to compare the algorithms on both
types of machines. This would imply programming other algorithms in
parallel, which is very difficult in practice.
\item
Many known path planning algorithms first compute the configuration
space (or an approximation of it) off-line, and then efficiently solve
the path planning problem on-line. As we saw, in order to deal with a
dynamic environment, the Ariadne's clew algorithm adopts a completely
different approach.
\item
For practical reasons, many test problems are toy problems (2{\sc d}, few
obstacles, few faces, simulated robots) and the performance results
using these kinds of problems are very difficult to generalize to
realistic industrial problems (3{\sc d}, tens of obstacles, hundreds of
faces, real robots).
\end{enumerate}
\end{enumerate}

Considering all these reasons, we tested our algorithm by implementing
a realistic robotic application to the very end. To achieve this goal,
we assembled a complex experimental setup including six different
machines (1 {\sc meganode}, 2 68030, 2 {\sc sun} 4, and 1 {\sc silicon
graphics}), two mechanical arms, and running seven different
cooperative programs (2 {\sc kali}, 1 {\sc act}, 2 {\sc vxworks}, 1
{\sc parx}, and 1 Ariadne's clew algorithm).

Our challenge was to be able to solve the path planning problem fast
enough to drive a real six {\sc dof} arm in a dynamic environment. The
Ariadne's clew algorithm indeed achieved this goal in our experiments
where the environment is composed of five fixed obstacles and a six
{\sc dof} arm moving independently.

We are not aware of any other methods capable of such performance. To
the best of our knowledge, currently implemented planners would take a
number of seconds (ten) to place a set of landmarks on a 2{\sc d} example
for a robot with five {\sc dof}~\cite{kavraki}. Despite the fact that
finding a general purpose planning technique for real industrial
application is a very difficult problem, we believe that the Ariadne's
clew algorithm provides an effective approach to such problems.

The number of range computations for a Manhattan motion of order $1$
is $C \frac{k^2+k}{2} * n$ where $n$ is the number of faces, $k$ the
number of {\sc dof}, and $C$ a constant factor, depending on the
number of parts used to model the robot. Obviously, such a number of
faces may be a severe difficulty for the implementation of the
Ariadne's clew algorithm described so far. To speed up the computation
we use a number of geometric filters that reduce the number of pairs
of entities to be analyzed.

However, it was possible to follow two research tracks in
combination. First, we could use collision checking methods that allow
access to the pairs in collision in a logarithmic time
~\cite{Fav87}. Second, we could preserve part of the landmark graph
when the environment is changing ~\cite{McLean96}.

\subsection{Generality}
\label{lab:generi}

The Ariadne's clew algorithm is general in the sense that it may be
used for numerous and very different applications in
robotics. Basically, the main thing that needs to be changed in the
algorithm is the distance $d$ used in the evaluation functions of the
two optimization problems.

Several planners have been implemented in this way: a fine motion
planner~\cite{Rosa96}, two motion planners for holonomic and
non-holonomic mobile robots~\cite{Scheuer97}, a reorientation planner
for an articulated hand\cite{Gupta95}, a planner for grasping and
regrasping
\cite{JuanGupta98}, and a planner for a robotic arm placed in the steam
generator of a nuclear plant~\cite{McLean96}. Adapting the algorithm
to a new application is, therefore, clearly a very easy task. For
instance, the application to path planning for the non-holonomic
trailer was developed in three days.

The Ariadne's clew algorithm is also general in the sense that it may
be used for any kind of path planning problem in a continuous space,
in fields other than robotics. Although it may be sufficient to change
the distance function $d$, one may also consider changing the form of
the function $d$, or even the nature of the searched spaces. For
instance, the concept of obstacles may be reconsidered. Instead of
``hard'' obstacles, one could replace them by zones of constraints. In
that case, the path planning problem does not consist of finding a
path without collisions but rather finding a path best satisfying the
different constraints. Such a planner has been developed for a naval
application where the problem was to find a path for a boat with
various constraints on the trajectory. This opens numerous
perspectives of applications for applying the Ariadne's clew algorithm
in a broader field than pure robotics.

\subsection*{Acknowledgments}
The authors are greatly indebted to Dr. Kamal Gupta from Simon Fraser
University who carefully read the paper and suggested valuable
corrections that greatly improve the quality of the final paper.

This work has been made possible by: Le Centre National de la
Recherche Scientifique (France), Consejo Nacional de Ciencia y
Tecnologia (Mexico) and {\sc esprit} 2, P2528 ({\sc eec}). 

\vskip 0.2in
\bibliography{ariane} 
\bibliographystyle{theapa} 
\end{document}
