\input{psfig}

\input amssym.def
\input amssym.tex

\documentstyle[11pt]{article}

\textwidth=6.5in
\textheight=8.5in
\topmargin=-0.25in
\oddsidemargin=-0.05in
\evensidemargin=-0.05in
\parskip = 0.05in
\parindent = 0.0in

\newtheorem{definition}{Definition}
\newtheorem{property}{Property}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}

% \renewcommand{\baselinestretch}[1]{1.4cm}

\sloppy

\begin{document}
\renewcommand{\topfraction}[1]{7.25in}
\renewcommand{\textfraction}[1]{0.25in}

\newcommand{\bm}[1]{\mbox{\boldmath$#1$}}
\newcommand{\cfree}{${\cal C}_{free}$}

\newcommand{\Abs}[1]{{\left|{#1}\right|}}
\newcommand{\Prob}[1]{{\Pr\left[{#1}\right]}}
\newcommand{\RR}{{\Bbb R}}

\newcommand{\denselist}{\itemsep 0pt}

\newcommand{\qed}{\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\Box$}}
%\rule{0.7em}{0.7em}$}}
\newenvironment{proof}{\par{\bf Proof:}}{\(\qed\) \par}

\title{A Random Sampling Scheme\\
for Path Planning}

\date{}


\author{J\'er\^ome Barraquand\thanks{Salomon Brothers Int.~Ltd., 
Victoria Plaza, 111 Buckingham Palace Road, London SW1W 0SB, UK.
Email: {\tt jerome.barraquand@sbil.co.uk}.} \and Lydia
Kavraki\thanks{Department~of ~Computer~Science, Stanford University,
Stanford, CA 94305, USA. Email: {\tt \{kavraki, latombe,
motwani\}@cs.stanford.edu}.}
\and Jean-Claude Latombe$^\dagger$ \and
Tsai-Yen Li\thanks{Department~of~Computer~Science,~National Chengchi
University, Wenshan, Taipei, Taiwan. Email: {\tt li@cs.nccu.edu.tw}.}
\and Rajeev Motwani$^\dagger$
\and Prabhakar Raghavan\thanks{IBM Almaden Research Center,
San Jose, CA 95120, USA. Email: {\tt pragh@almaden.ibm.com}.}}


\maketitle

%\thispagestyle{myheadings}
%\thispagestyle{empty}
%\pagestyle{empty}

{\small
\begin{abstract}
{\em Several randomized path planners have been proposed during the last
few years. Their attractiveness stems from their applicability to
virtually any type of robots, and their empirically observed success.
In this paper we attempt to present a unifying view of these planners
and to theoretically explain their success. First, we introduce a
general planning scheme that consists of randomly sampling the robot's
configuration space. We then describe two previously developed
planners as instances of planners based on this scheme, but applying
very different sampling strategies. These planners are
probabilistically complete: if a path exists, they will find one with
high probability, if we let them run long enough.  Next, for one of
the planners, we analyze the relation between the probability of
failure and the running time.  Under assumptions characterizing the
``goodness'' of the robot's free space, we show that the running time
only grows as the absolute value of the logarithm of the probability
of failure that we are willing to tolerate. We also show that it
increases at a reasonable rate as the space goodness degrades. In the
last section we suggest directions for future research.}
\end{abstract}
}

\vspace*{0.5in}

{\tt This paper has been accepted for publication 
in the International Journal of Robotics Research.}

\newpage


\section{Introduction}
\label{sec:introduction}

Robot path planning has been proven a hard problem~(Reif 1979).  There
is strong evidence that its solution requires exponential time in the
number of dimensions of the configuration space, i.e., the number of
degrees of freedom (dofs) of the robot. This result is remarkably
stable: it still holds for rather specific robots, e.g., planar
linkages consisting of links serially connected by revolute
joints~(Joseph and Plantiga 1985) and sets of rectangles executing
axis-parallel translations in a rectangular workspace~(Hopcroft,
Schwartz, and Sharir 1984; Hopcroft and Wilfong 1986). Though general
and complete algorithms have been proposed~(Canny 1988; Schwartz and
Sharir 1983), their high complexity precludes any useful
application. This negative result has led some researchers to seek
heuristic algorithms.  While several such planners solve difficult
problems, they also often fail or take prohibitive time on seemingly
simpler ones. The fact that their behavior is not well characterized
is a major drawback: they cannot be used as blackboxes in larger robot
control systems.

The number of dofs beyond which existing complete algorithms become
practically useless is low, somewhere between 3 and 5.  This means
that they cannot be used to compute paths for rigid objects
translating and rotating in three dimensions, nor for six-dof
manipulator arms, two important cases in practice. On the other hand,
robot applications tend to involve more degrees of freedom than ever
before. For example, an increasing number of manufacturing workcells
use several cooperating robots to augment throughput and flexibility.
Cells with more than twenty dofs are no longer exceptions. As costs
and time for designing and deploying them become more critical, path
planners integrated with CAD systems will be in higher demand to
facilitate robot programming. Eventually, planners will run online to
allow for non-deterministic sequences of goals and events~(Li and
Latombe 1995).  Robots in domains other than manufacturing (e.g.,
medical surgery, space exploration) will also require efficient and
reliable path planners. Some non-robotics domains raise a similar need
as well.  In computer graphics, animation of synthetic actors to
produce digital movies or video games requires dealing with several
dozen dofs.  Here, motion planning may drastically reduce the work of
human animators who currently input large numbers of key frames.  In
molecular biology, motion planning can help compute plausible docking
motions of molecules modeled as spatial linkages with many dofs.

Collision-free path planning, which assumes perfect knowledge of the
world and stationary obstacles, is only the most basic motion planning
problem in robotics. Clearly, we would ultimately like robot planners
to also deal with issues such as uncertainties, moving obstacles,
movable objects, and dynamic constraints~(Latombe 1991; Latombe
1995). But every extension of the basic problem adds in computational
complexity. For instance, allowing moving obstacles makes the problem
exponential in the number of moving obstacles~(Canny 1988; Reif and
Sharir 1985); uncertainties in control and sensing make the problem
exponential in the complexity of the robot environment~(Canny
1988). Before we can effectively investigate such extensions in large
configuration spaces, it seems that we must better understand how to
practically solve basic path planning.

Path-planning applications are so diverse that it is infeasible to
design a tailor-made algorithm for every possible robot.\footnote{In
any case, very few tailor-made planners have been successfully
designed for specific robots with more than four dofs.} Instead, we
need general path planning algorithms not bound to the specifics of
any particular robot. We believe that between the two extreme types of
planners suggested above -- complete and heuristic -- there is place
for practically efficient general planners achieving a weaker form of
completeness. In other words, we may perhaps trade a limited amount of
completeness against a major gain in computing efficiency.  Full
completeness requires the planner to always answer a path-planning
query correctly, in asymptotically bounded time. A weaker, but still
interesting form of completeness is the following: if a solution path
exists, the planner will find one in bounded time, with high
probability. We call it {\em probabilistic completeness}.  This weaker
completeness becomes particularly interesting if we can show that the
planner's running time grows slowly with the inverse of the failure
probability that we are willing to tolerate.

With this philosophy in mind, we have designed new path planners and
experimented with them in large configuration spaces.  One of them,
described in~(Barraquand and Latombe 1991; Barraquand, Langlois, and
Latombe 1992; Latombe 1991), is a potential-field-based planner that
escapes local minima by performing random walks; in the following, we
will refer to it as the {\em potential-field planner}. Another
planner, presented in~(Kavraki 1995; Kavraki and Latombe 1994a;
Kavraki and Latombe 1994b; Kavraki, \v{S}vestka, Latombe, and Overmars
1996), precomputes a ``roadmap'' (network) of simple paths connecting
randomly selected configurations and tries to construct a path between
any two input configurations by connecting them to this roadmap; we
will refer to this planner as the {\em roadmap planner}.  Both these
planners have been successfully applied to complex problems. For
example, in~(Koga, Kondo, Kuffner, and Latombe 1994), the
potential-field planner was used to automatically synthesize a video
clip with graphically simulated human and robot characters entailing a
78-dimension configuration space.  Both the potential-field and the
roadmap planners have been used to check that parts can be removed
from an aircraft engine for inspection and maintenance~(Chang and Li
1995); here, paths are generated in configuration spaces having only
six dimensions, but the parts have particularly complex geometry.

These two planners achieve probabilistic completeness. For the
potential-field planner, this property remains qualitative: if there
exists a path, the probability that the planner finds one tends toward
one as the running time increases; but the convergence speed is
unknown. But, for the roadmap planner, we have proven stronger results
that relate the probability that it finds a path, when one exists, to
its running time~(Kavraki 1995; Kavraki, Kolountzakis, and Latombe
1996; Kavraki, Latombe, Motwani, and Raghavan 1994; Kavraki, Latombe,
Motwani, and Raghavan 1995). In turn, these theoretical results
suggest improvements of the planner.

Other work investigating similar or related randomized planning
approaches include~(Ahuactzin Larios 1994; Bessi\`ere, Mazer, and
Ahuactzin 1995; Horsch, Schwarz, and Tolle 1994; Hwang and Chen 1995;
Overmars 1992; Overmars and \v{S}vestka 1995).  Formal attempts to
predict the behavior of specific random planners are proposed in very
few papers~(Chen 1995; Lamiraux and Laumond 1995).

This paper proposes a consistent framework to describe and study the
randomized planners cited above, with the goal to eventually build
more powerful planners. In the planners cited above, the robot's free
space is not explicitly represented, but randomly sampled. We believe
that this is the central concept underlying their success. In
Section~2 we capture this concept into a general computational scheme
for path planning in large configuration spaces.\footnote{This scheme
can also be applied to configuration spaces having few dimensions; but
it is less interesting in that case, since complete algorithms are
then available.} In Section~3 we make our discussion more precise by
presenting our potential-field and roadmap planners as two instances
of planners using this scheme, but applying two different sampling
strategies. In Section~4 we give two formal analyses of the
probabilistic completeness of variants of the roadmap planner. These
analyses provide a theoretical explanation for the empirically
observed success of the roadmap planner. They are the crux of this
paper. Indeed, as it has become relatively easy to design new
randomized path planners that outperform previous ones on some
well-selected problems, it is increasingly important to formally
explain their strengths and weaknesses.  This paper does not present
experimental results obtained with our planners.  Many such results
were previously reported in~(Barraquand and Latombe 1991; Chang and Li
1995; Kavraki 1995; Kavraki and Latombe 1994a; Kavraki and Latombe
1994b; Kavraki, \v{S}vestka, Latombe, and Overmars 1996; Koga, Kondo,
Kuffner, and Latombe 1994; Koga and Latombe 1994) and in papers by
other authors~(Challou and Gini 1995; Graux, Millies, Kociemba, and
Langlois 1992; Zhu and Gupta 1993).  The reader is referred
to~(Motwani and Raghavan 1995) for a textbook on randomized algorithms
and sampling techniques.

\section{General Scheme}
\label{sec:scheme}

We consider the problem of planning collision-free paths for an
arbitrary $n$-degree-of-freedom holonomic\footnote{Our presentation
can be extended to nonholonomic robots. See~(Overmars and \v{S}vestka
1995; Sekhavat, \v{S}vestka, Laumond, and Overmars 1995; \v{S}vestka
1993).}  robot ${\cal A}$. We let ${\cal C}$ denote the configuration
space of ${\cal A}$ and ${\cal C}_{free}$ stand for the open subset of
the collision-free configurations in ${\cal C}$. We also refer to
${\cal C}_{free}$ as the {\em free space} and to configurations in
${\cal C}_{free}$ as {\em free configurations}. A planning problem is
specified by two free configurations, ${\bm q}_{init}$ and ${\bm
q}_{goal}$, called the {\em initial} and the {\em goal}
configurations, respectively.  Any path lying in ${\cal C}_{free}$
that joins these two configurations is a solution of this problem.

We assume for simplificity that ${\cal C}$ is the cube $[0,1]^n$, so
that each configuration ${\bm q}$ is described by an $n$-tuple
$(q_1,\dots,q_n)$. However, it is straightforward to extend our
presentation to cases where ${\cal C}$ is multiply connected, i.e.,
one or more dimensions can ``wrap around''.  The only requirement is
that ${\cal C}$ be measurable (in the Lebesgue sense), which is always
achieved in practice.

Although there exist algorithms to construct an explicit
representation of ${\cal C}_{free}$ given the geometry of ${\cal A}$
and the obstacles in semi-algebraic form, their time complexity makes
them impractical for any sufficiently large value of $n$.  On the
other hand, reasonably efficient algorithms are available to compute
the Euclidean distance between two objects in three-dimensional space
(Gilbert, Johnson, and Keerthi 1988; Lin and Canny 1991; Ponamgi,
Manocha, and Lin 1995; Quinlan 1994; Thomas and Torras 1994). This
leads us to assume that ${\cal C}_{free}$ is implicitly given by a
function, {\sc clearance}: ${\cal C} \rightarrow \RR$, that maps any
configuration {\bm q} to the distance (in the workspace) between the
robot placed according to {\bm q} and the obstacles, or between two
bodies of the robot, whichever is smaller. In the case where the robot
collides with an obstacle or with itself, {\sc clearance}({\bm q})
returns 0 or a negative number. Thus, whenever {\sc clearance}({\bm
q}) is positive, {\bm q} belongs to ${\cal C}_{free}$. We refer to
{\sc clearance}({\bm q}) as the {\em clearance} of {\bm q}.

For any bounded robot ${\cal A}$, there exists a positive constant
$\rho$ such that when ${\cal A}$ moves along a straight path in ${\cal
C}$ between any two configurations ${\bm q} = (q_1,\dots,q_n)$ and
${\bm q}^\prime = (q_1^\prime,\dots,q_n^\prime)$, no point of ${\cal
A}$ traces a curve segment longer than $\rho \max_{i \in
[1,n]}|q_i - q_i^\prime|$. We assume here that $\rho$ is given, though
for most usual robots its computation is straightforward and can be
included in the planner. Rather than using a single $\rho$, we may
also partition ${\cal C}$ into several regions and have a distinct
constant $\rho_i$ for each region. If the $\rho_i$'s differ by large
amounts, this could substantially reduce the running time of a planner
based on the scheme presented below, but we will not go into such
detail in this paper.

\begin{definition} Let ${\bm q} = (q_1,\dots,q_n)$ and 
${\bm q}^\prime = (q_1^\prime,\dots,q_n^\prime)$ be two free
configurations whose respective clearances are $\eta$ and
$\eta^\prime$. They are said to be adjacent if $\rho \max_{i \in
[1,n]}|q_i - q_i^\prime| < \max\{\eta,\eta^\prime\}/2$.
\end{definition}

Clearly, if two configurations are adjacent the straight-line segment
joining them lies entirely in ${\cal C}_{free}$. In fact, the
coefficient $1/2$ appearing on the right-hand side of the above
inequality is intended to make sure that the robot cannot collide with
itself, since two bodies might then move simultaneously toward each
other. This coefficient can be removed if self-collisions are known in
advance to be impossible.  Note also that the map:
\[ ({\bm q},{\bm q}^\prime) \in {\cal C}^2 \mapsto 
\max_{i \in [1,n]}|q_i - q_i^\prime| \in \RR^+ \cup \{0\} \]
is the $L^\infty$ distance in ${\cal C}$.  We could choose other
distances in ${\cal C}$ to define adjacency. Of course, the constant
$\rho$ depends on this choice. 

%\vspace*{0.05in}

Now we can state our {\bf general planning scheme} as follows:

\begin{quote}

Pick configurations in ${\cal C}$ at random; retain those
configurations which lie in ${\cal C}_{free}$ (along with ${\bm
q}_{init}$ and ${\bm q}_{goal}$) as the nodes of a graph $G$; and
connect adjacent configurations by links of $G$.

Return {\sc yes} if ${\bm q}_{init}$ and ${\bm q}_{goal}$
belong to the same connected component of $G$.

Return {\sc no} if no path has been found after having generated $c$
configurations, where $c$ is an input parameter.

\end{quote}


The answer {\sc yes} is always correct, that is, whenever the planner
returns {\sc yes}, there actually exists a collision-free path
connecting ${\bm q}_{init}$ to ${\bm q}_{goal}$; moreover such a path
can easily be extracted from the graph $G$. But the answer {\sc no} is
not necessarily correct. Indeed, after a finite amount of computation
(defined by the parameter $c$), the planner may still not have found a
path between ${\bm q}_{init}$ and ${\bm q}_{goal}$, even if one
exists.

The key component of this planning scheme is the {\em sampling
strategy} applied to generate the nodes of $G$.  Different strategies
are possible. For example, if multiple planning queries are to be made
with the same robot and obstacles ({\em multi-query case}), then it
may be suitable to invest preprocessing time to construct a network of
configurations (which we call a {\em roadmap}). Processing each query
then only requires connecting the input initial and goal
configurations to the roadmap.  If the queries are not known in
advance, it seems reasonable to construct the roadmap by choosing
configurations uniformly at random from $[0,1]^n$ since the resulting
free configurations are then uniformly distributed over ${\cal
C}_{free}$. However, we will see in Section~3.2 that, while the
roadmap is being generated, it is possible to derive heuristic
information from it and bias the selection of the new configurations.

Instead, if a single or very few queries are to be made with the same
robot and obstacles ({\em single-query case}), the planner may be more
successful by using a sampling strategy that picks new configurations,
first in neighborhoods of the initial and goal configurations and
then, iteratively, in neighborhoods of the newly generated
configurations, until the two ``sampling waves'' meet. A similar
strategy could also be used in the multi-query case to connect the
initial and goal configurations to the roadmap.

Although the efficiency of any planner may be evaluated through
experimentation, formal analysis is desirable to compare planners and
stress their strengths and weaknesses. Ideally a planner's outcome
should be {\sc yes} with the highest probability whenever a free path
exists and this outcome should be generated in minimal time. Hence,
the analysis should relate the probability that the planner produces
an incorrect answer to its running time. Given a small positive number
$\alpha$ (the acceptable probability that the planner's output is {\sc
no} while a free path exists), we would like to bound the running time
of the planner by a function of $\alpha$. If this function grows
slowly with $1/\alpha$, then the planner is particularly
interesting since we can get arbitrarily close to full completeness at
a reasonable cost.

Let us assume for simplificity that {\sc clearance} takes constant
time to evaluate.  Then the planner's running time mainly depends on
two numbers: the number of sample configurations and the number of
pairs of free configurations checked for adjacency. The number of
sample configurations is at most $c$. But only a fraction of them,
$f$, are in ${\cal C}_{free}$, hence in the constructed graph $G$. In
practice, it is often the case that $f \ll c$.  The planner should
thus strive to get the greatest ratio $f/c$, but the distribution of
the generated free configurations is also crucial to eventually find a
path. The number of adjacency checks is at most proportional to $f^2$;
however, the planner may choose not to test all pairs of free
configurations for adjacency.\footnote{Checking the sample
configurations for adjacency is an instance of the orthogonal
range-searching problem~(Arya and Mount 1995; Preparata and Shamos
1985). Using the range-tree technique, the pairs of adjacent
configurations can be computed in $O(f
\log^{n-1} f)$ time, or slightly faster. This is better than $O(f^2)$
when $f$ is large enough.}

It seems likely that no strong property can be proven for any given
planner, if we do not make some assumption about ${\cal
C}_{free}$. Moreover, no single planner is likely to be the most
efficient for all possible problems. This suggests that planners
should be analyzed under some well-specified assumptions. In
Section~\ref{sec:analysis}, we will study the work carried out by a
two-phase planner under two distinct assumptions. In one, the {\em
visibility volume assumption}, ${\cal C}_{free}$ is such that every
free configuration ``sees'' a subset of ${\cal C}_{free}$ whose volume
is at least an $\epsilon$ fraction of the total volume of ${\cal
C}_{free}$ (we then say that ${\cal C}_{free}$ is $\epsilon$-good).
In the second assumption, the {\em path clearance assumption}, there
exists a collision-free path between ${\bm q}_{init}$ and ${\bm
q}_{goal}$ that has some given clearance $\xi$.
Assumptions must be carefully crafted. Indeed, if these are too
specific or unrealistic, the analysis will not yield useful results;
on the other hand, if they are too general, the results will be too
weak.


\section{Specific Planners}
\label{sec:specific}

We now present two planners that make use of the
above scheme with different sampling strategies.

\subsection{Potential-Field Planner}
\label{ssec:potential}

This planner was originally described in~(Barraquand and Latombe 1991;
Barraquand, Langlois, and Latombe 1992; Latombe 1991), along with
experimental results.\footnote{The planner is available by anonymous
ftp from {\tt flamingo.stanford.edu:/pub/li/rpp3d.tar.gz}.}
Extensions and additional experimental results were presented
in~(Chang and Li 1995; Graux, Millies, Kociemba, and Langlois 1992;
Koga, Kondo, Kuffner, and Latombe 1994; Koga and Latombe 1994) Here,
we focus on its relation to the general scheme presented above.

The planner is given a function ${\bm U} : {\cal C}_{free} 
\rightarrow \RR^+ \cup \{0\}$, the {\em potential field}, 
with a single global minimum (0) at the goal
configuration.\footnote{Techniques to automatically construct this
function are proposed in~(Barraquand and Latombe 1991; Latombe 1991).}
It then attempts to connect ${\bm q}_{init}$ to ${\bm q}_{goal}$ by
alternating {\em down motions} and {\em escape motions}. Each down
motion ``descends'' along {\bm U} until it reaches a local minimum,
while escape motions attempt to flee from local minima.

The following algorithm, in which $h$ is an input parameter,
constructs a down motion starting at configuration ${\bm q}_s$:

\vspace{0.1in}

\noindent
\hspace*{0.07in} 
{\tt Down-Motion}(${\bm q}_s$):

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item ${\bm q} \leftarrow {\bm q}_s$.

\item While {\bm q} is not labelled as a local minimum do:

\begin{enumerate} \denselist

\item Pick at random up to $h$ configurations adjacent to 
{\bm q}, until one of them, ${\bm q}^\prime$, satisfies ${\bm U}({\bm
q}^\prime) < {\bm U}({\bm q})$.

\item If the previous step succeeded in generating ${\bm q}^\prime$,
then reset ${\bm q}$ to ${\bm q}^\prime$; else label {\bm q}
as a local minimum.

\end{enumerate}

\item Return {\bm q}. 

\end{enumerate}

At Step 2(a) let ${\bm q} = (q_1,\ldots,q_n)$ and $\eta =$ {\sc
clearance}({\bm q}).  Configurations are picked at random from the
volume defined by $\Pi_{i=1,\dots,n} [q_i - \eta/\rho,q_i + \eta/\rho]
\cap [0,1]^n$. According to Definition~1, all configurations
in this volume are adjacent to {\bm q}.  To guarantee that Step 2 does
not loop for ever, {\bm U} must have no local minimum in the boundary
of ${\cal C}_{free}$. This can easily be obtained by including in the
definition of {\bm U}({\bm q}) a term proportional to 1/{\sc
clearance}({\bm q}).

The following algorithm constructs an escape motion starting at
a local minimum ${\bm q}_l$:

\vspace{0.1in}

\noindent
\hspace*{0.07in} 
{\tt Escape-Motion}(${\bm q}_l$):

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item Pick at random the length, $\ell$, of the 
motion.\footnote{In~(Barraquand and Latombe 1991), we note that, on
the average, a random walk of length $\ell$ ends $\sqrt{\ell}$ away
from its starting point. This leads us to suggest choosing
$\sqrt{\ell}$ according to a truncated Laplace distribution with mean
value equal to the ``radius'' of the configuration space. Here, this
radius is 1.}

\item ${\bm q} \leftarrow {\bm q}_l$; $l \leftarrow 0$.

\item While $l < \ell$ do:

\begin{enumerate} \denselist

\item Pick at random a free configuration ${\bm q}^\prime$ adjacent to
{\bm q}.

\item $l \leftarrow l + \max_i|q_i - q_i^\prime|$.

\item ${\bm q} \leftarrow {\bm q}^\prime$.

\end{enumerate}

\item Return {\bm q}.

\end{enumerate}

The overall planning algorithm is the following:

\vspace{0.1in}

\noindent
\hspace*{0.07in} 
{\tt Potential-Field-Planner}(${\bm q}_{init},{\bm q}_{goal}$):

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item ${\bm q}_l \leftarrow$ {\tt Down-Motion}(${\bm q}_{init}$).

\item While ${\bm q}_l \neq {\bm q}_{goal}$ do:

\begin{enumerate} \denselist

\item Do:

\begin{enumerate} \denselist

\item If the total number of configurations generated so far
exceeds $c$ then return {\sc no} and halt.

\item ${\bm q}_s \leftarrow$ {\tt Escape-Motion}(${\bm q}_l$);

\item ${\bm q}_l^\prime \leftarrow$ {\tt Down-Motion}(${\bm q}_s$);

\end{enumerate}

until ${\bm U}({\bm q}_l^\prime) < {\bm U}({\bm q}_l)$.

\item ${\bm q}_l \leftarrow {\bm q}_l^\prime$.

\end{enumerate}

\item Return {\sc yes}.

\end{enumerate}

The graph $G$ constructed by the planner is a tree of paths rooted at
${\bm q}_{init}$. Each configuration ${\bm q}^\prime$ entered as a
node of $G$ has been picked so that it is adjacent to a configuration
${\bm q}$ already in $G$ (Steps 2(a) and 3(a) of {\tt Down-Motion} and
{\tt Escape-Motion}, respectively). Moreover, ${\bm q}^\prime$ is only
linked to ${\bm q}$ in $G$. Hence, the planner does not test pairs of
configurations for adjacency, avoiding the cost of this test. During a
down motion, the potential ${\bm U}$ introduces a bias in the choice
of the tree path that will be followed by the planner. Although the
global geometry of ${\cal C}_{free}$ is unknown, {\bm U} can be seen
as a {\em specialist} that gives some heuristic indications about this
geometry, i.e.: which directions are promising and which aren't. The
techniques in~(Barraquand and Latombe 1991; Latombe 1991) compute {\bm
U} by combining local-minima functions computed over the robot's
workspace. Although the resulting {\bm U} often prevents the planner
from getting trapped into big obstacle cavities, it still has local
minima and therefore is an imperfect characterization of the free
space's geometry. On the other hand, computing local-minima-free
potentials in large dimensional spaces is a difficult
problem~(Koditschek 1987) that is at least as hard as path planning
itself.

Using well-known properties of random motions, the potential-field
planner can be shown probabilistically complete~(Barraquand and
Latombe 1991; Lamiraux and Laumond 1995).  Moreover, a calculation of
the finite expected number of invocations of {\tt Escape-Motion} is
given in~(Lamiraux and Laumond 1995).  The idea underlying this
calculation is the following. The basins of attraction of the local
minima of {\bm U} which have non-zero measure (the goal basin is
assumed to be one of them) form a partition of the free space. For any
two such basins $B_i$ and $B_j$, one can define the finite transition
probability $p_{ij}$ that a random walk generated by {\tt
Escape-Motion} from the minimum in $B_i$ terminates into $B_j$. The
expected number of invocations of {\tt Escape-Motion} before entering
the goal basin is then expressed as a function of the $p_{ij}$'s. In
theory, this result gives some indication of the expected complexity
of the potential-field planner.  But, in practice, the $p_{ij}$'s are
unknown. In fact, a key issue in analyzing a planner based on random
sampling is to translate some geometric property of the free space
into probabilistic terms.

The potential-field planner has successfully solved many difficult
problems; see~(Barraquand and Latombe 1991; Chang and Li 1995; Graux,
Millies, Kociemba, and Langlois 1992; Koga, Kondo, Kuffner, and
Latombe 1994). However, it is easy to create problems that it fails to
solve in a reasonable amount of time, though they admit rather obvious
solutions. Not surprisingly, most failures are due to {\em traps},
which cause some transition probabilities $p_{ij}$ to be very small
(in particular, the probabilities to enter the goal basin from some
other basins). A trap is a basin of attraction of a local minimum of
{\bm U} that is almost completely surrounded by forbidden
configurations (i.e., ${\cal C}
\backslash {\cal C}_{free}$). Hence, a trap admits only narrow exits
and the potential function inside the trap guides the robot away from
these exits.  If the robot's path starts within a trap or is guided
into one by {\bm U}, each escape motion executed then has a tiny
probability of escaping the local minimum. One could imagine a variant
of the planner where the potential field is randomly guessed among a
collection of several functions and changed several times during
planning, hoping that the various potentials would entail different
traps. We did some experiments with this idea, but we only got limited
results.

\subsection{Roadmap Planner}
\label{ssec:roadmap}

The problems encountered with the potential-field planner led us to
develop another planner, the roadmap planner\footnote{The planner is
available by anonymous ftp from {\tt
flamingo.stanford.edu:/pub/kavraki/prm.tar.gz}.}  described
in~(Kavraki 1995; Kavraki and Latombe 1994a; Kavraki and Latombe
1994b; Kavraki, \v{S}vestka, Latombe, and Overmars 1996). Several
variants of this planner have been implemented; we present one
below. Unlike the potential-field planner, this new planner uses no
problem-specific heuristics.

The roadmap planner operates in two phases, preprocessing and query
processing: The preprocessing phase consists of constructing a network
$R$ of configurations, the roadmap. The configurations in $R$ are
called {\em milestones}. They only form a subset of all the sample
configurations generated by the planner; hence, the roadmap
is not exactly the graph $G$ mentioned in the general scheme.
Every query specifies two configurations, ${\bm q}_{init}$ and ${\bm
q}_{goal}$, in ${\cal C}_{free}$. Processing the query consists of
connecting these configurations to two milestones and checking that
these two milestones are in the same connected component of $R$.

The planner uses a simple algorithm, {\tt Connect} (also called the
{\em connector}), to construct the links of $R$. Given any two
milestones, ${\bm m}_1$ and ${\bm m}_2$, the connector checks if the
straight-line segment connecting them lies in ${\cal C}_{free}$. It
does so by dichotomically breaking the segment into shorter segments
and checking the endpoints of each segment for adjacency. It stops
breaking a segment whenever its two endpoints are adjacent or one of
them is not in free space. In the second case, {\tt Connect} halts,
without generating a link between ${\bm m}_1$ and ${\bm m}_2$ in the
roadmap. Instead, if the connector eventually succeeds in partitioning
the segment ${\bm m}_1{\bm m}_2$ into segments (possibly, of unequal
lengths) such that the endpoints of each segment are adjacent, it
establishes a link between ${\bm m}_1$ and ${\bm m}_2$ in the
roadmap. The work done by the connector is part of the sampling work
done by the roadmap planner, but the sample configurations it
generates are not permanently stored; they are not part of the roadmap
$R$. In other words, the planner does not attempt to find additional
connections among sample configurations generated between
milestones. To keep our presentation simple, we assume that {\tt
Connect} only tries straight paths, but it could try other canonical
paths as well.  We say that a configuration {\em sees} another
configuration if the straight-line segment joining them lies entirely
in ${\cal C}_{free}$.

In the following algorithm we could limit the total number of sample
configurations to $c$, as in the general scheme of Section~2.
However, putting the limit on the number of generated milestones
instead is more convenient; it will also facilitate the analyses of
Section~4. The preprocessing phase constructs an initial roadmap
containing $r$ milestones (Steps 2 and 3 in the algorithm shown
below).  Then it expands this initial roadmap into a final one
containing $s > r$ milestones. Both $r$ and $s$ are input parameters.
The first $r$ milestones are chosen uniformly over ${\cal
C}_{free}$. The remaining $s-r$ milestones are selected in small
regions considered as ``difficult'' parts of ${\cal C}_{free}$. The
preprocessing algorithm is the following:

\vspace{0.1in}

\noindent
\hspace*{0.07in} {\tt Preprocessing}:

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item $i \leftarrow 0$.

\item While $i < r$ do:

\begin{enumerate} \denselist

\item Pick a configuration {\bm q} in ${\cal C}$ at random.

\item If {\sc clearance}({\bm q}) $> 0$ then

\begin{enumerate} \denselist

\item Store {\bm q} as a milestone of the roadmap.

\item $i \leftarrow i+1$.

\end{enumerate}

\end{enumerate}

\item For every pair of milestones ${\bm m}_1$ and ${\bm m}_2$ 
whose distance is less than $d$, do: {\tt Con\-nect}(${\bm m}_1,{\bm
m}_2$).

\item Invoke {\tt Resample} to expand the roadmap by $s-r$ 
milestones (see below).

\end{enumerate}

The threshold $d$ at Step 3 is an input parameter. It is used to limit
the number of pairs of milestones that are tested by {\tt Connect},
since in most spaces two milestones that are far apart are unlikely to
see each other. Step 3 takes time at most quadratic in $r$, which is
usually much smaller than the total number of sample configurations
generated by the roadmap planner.\footnote{Footnote 4 applies here
too.}

{\tt Resample} selects milestones with probability inversely
proportional to their degrees in the roadmap (i.e., their number of
connections to other milestones). Intuitively, a milestone with few or
no connections lies in a difficult region of the free space.  For each
milestone {\bm m} that it selects, {\tt Resample} picks a number of
new milestones at random in a neigborhood of {\bm m} and invokes {\tt
Connect} to try to link each of these new milestones to other
milestones. This expansion of the roadmap terminates when the total
number of milestones is $s$.
Experiments have been done with and without the roadmap expansion step
(Step 4). Roadmaps containing the same total number of milestones have
been constructed both ways. The roadmaps generated using the expansion
step have been consistently better, i.e., subsequent queries were
processed more quickly with less incorrect {\sc no} answers. Over a
large range of problems, generating 2/3 of the milestones at Step 2
and 1/3 at Step 4 gave good results.

After preprocessing, each query is handled as follows ($g$ is an
input parameter):

\vspace{0.1in}

\noindent
\hspace*{0.07in} {\tt Query-Processing}$({\bm q}_{init},{\bm q}_{goal})$:

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item For $i = \{init,goal\}$ do:

\begin{enumerate} \denselist

\item If there exists a milestone {\bm m} that sees ${\bm q}_i$
then ${\bm m}_i \leftarrow {\bm m}$.

\item Else

\begin{enumerate} \denselist

\item Repeat $g$ times:

\vspace{0.05in}

Pick a configuration {\bm q} at random in the
neighborhood of ${\bm q}_i$

\vspace{0.05in}

until {\bm q} sees both ${\bm q}_i$ and a milestone {\bm m}.

\item If all $g$ trials failed then return {\sc no} and halt,
else ${\bm m}_i \leftarrow {\bm m}$.

\end{enumerate}

\end{enumerate}

\item If ${\bm m}_{init}$ and ${\bm m}_{goal}$ are in the same 
component of the roadmap then return {\sc yes}; else return {\sc no}.

\end{enumerate}

\section{Analysis}
\label{sec:analysis}

We now give formal analyses of two variants of the roadmap planner. We
characterize the amount of computation that the planner must do in
order to give correct answers with high probability.

The intuitive reason for the experimental success of the above
planners is that there usually exist many collision-free paths joining
two configurations. Hence, to bound the running time of the roadmap
planner, we assume that ${\cal C}_{free}$ satisfies some geometric
property capturing the above intuition. We propose two such
properties. Our thesis is that the success of any sampling strategy
will stem from a similar property.

In both analyses, we consider that the key number affecting the
planner's running time is the number of milestones in the constructed
roadmap. Since to generate a single milestone it might be necessary to
randomly pick several (possibly, many) configurations in ${\cal C}$,
we implicitly assume that the volume of ${\cal C}_{free}$ relative to
the volume of ${\cal C}$ is not too small. If this assumption is not
satisfied, any variant of the roadmap algorithm presented in
Section~\ref{ssec:roadmap} will behave poorly. In this case, we
should probably make the additional assumption that a few free
configurations are given (after all, every query will give two such
configurations); then, a possible sampling strategy could be to build
a roadmap by generating milestones in small regions centered at the
given configurations, first, and at the newly generated milestones,
next. 

Note that bounding the number of milestones is not sufficient to bound
the running time of the planner, because it does not account for the
running time of {\tt Connect}. If two milestones passed to {\tt
Connect} see each other, but the line segment connecting them is
arbitrarily close to the free space boundary, then the connector will
have to break it into arbitrarily many small segments.  This problem
could be eliminated by extending the general scheme of Section~2 with
a primitive computing the volume swept out by the robot when it moves
between two configurations along a straight path in configuration
space.

Here, we only state the main results of our analyses.  We give formal
proofs of the three main theorems (Theorems~1, 2, and 7) in the
appendix. The proofs of two other theorems (Theorems~3 and 4) are
straighforward and short; they appear in the text below. For the
proofs of Theorems~5 and 6, we refer the reader to~(Kavraki, Latombe,
Motwani, and Raghavan 1994; Kavraki, Latombe, Motwani, and Raghavan
1995). Indeed, these proofs are longer and more technical, while the
theorems themselves are less important to a robotics
audience. Finally, Theorem 8 is essentially a refinement of
Theorem~7. Its proof can be found in~(Kavraki 1995; Kavraki,
Kolountzakis, and Latombe 1996).

In the rest of this section we denote the volume of a subset ${\cal
X}$ of ${\cal C}$ by $\mu({\cal X})$.  

\subsection{Visibility Volume Assumption}

\subsubsection{Definition and algorithms}

For any configuration ${\bm q} \in {\cal C}_{free}$, let ${\cal
S}({\bm q})$ consist of all those configurations ${\bm q}^\prime \in
{\cal C}_{free}$ that {\bm q} sees.

\begin{definition}
Let $\epsilon$ be a positive real. A configuration ${\bm q} \in {\cal
C}_{free}$ is $\epsilon$-good if $\mu({\cal S}({\bm q})) \geq \epsilon
\mu({\cal C}_{free})$. Furthermore, ${\cal C}_{free}$ is $\epsilon$-good
if all the configurations it contains are $\epsilon$-good.
\end{definition}

The visibility volume assumption made here is that ${\cal C}_{free}$
is $\epsilon$-good, that is, each configuration in it sees a
significant portion of ${\cal C}_{free}$. The underlying intuition is
that it is then relatively easy to pick a set of milestones that,
collectively, can see most of ${\cal C}_{free}$. But the assumption
fails to prevent ${\cal C}_{free}$ from containing narrow passages
through which it might be difficult to connect milestones. For
example, consider the case where ${\cal C}$ is two-dimensional and
${\cal C}_{free}$ consists of two disks of equal size that overlap by
a very small amount.  Then ${\cal C}_{free}$ is $\epsilon$-good for
$\epsilon \approx 0.5$. But the probability that any milestone in one
disk sees a milestone in the other disk is very small. For this
reason, we use a variant of the roadmap algorithm that embeds a
``complex planner''. We assume that this complex planner is error-free
in that it discovers a path between two given configurations whenever
one exists, and reports failure when there is none. But of necessity
such a complete planner must be expensive to run, and so we seek to
use it sparingly. In particular, to keep query processing fast, we
restrict the use of the complex planner to the preprocessing stage.

The preprocessing algorithm is similar to the one given in Section
3.2. The main difference is that Step 4 invokes {\tt Permeation},
instead of {\tt Resample}. {\tt Permeation} uses the complex planner
to improve the roadmap connectivity; unlike {\tt Resample}, it does
not add new milestones to the roadmap.  The constructed roadmap
contains $s$ milestones; these are all generated at Step 2.

\vspace{0.1in}

\noindent
\hspace*{0.07in} {\tt Preprocessing}:

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item $i \leftarrow 0$.

\item While $i < s$ do:

\begin{enumerate} \denselist

\item Pick a configuration {\bm q} in ${\cal C}$ at random.

\item If {\sc clearance}({\bm q}) $> 0$ then

\begin{enumerate} \denselist

\item Store {\bm q} as a milestone of the roadmap.

\item $i \leftarrow i+1$.

\end{enumerate}

\end{enumerate}

\item For every pair of milestones ${\bm m}_1$ and ${\bm m}_2$, do:
{\tt Connect}(${\bm m}_1,{\bm m}_2$).

\item Pick one representative milestone from each component of 
the current roadmap.  Let $V$ be the set of these representative
milestones.  Invoke {\tt Permeation}$(V)$ to improve the connectivity
of the milestones (see below).

\end{enumerate}

The result of this preprocessing is a roadmap such that any two nodes
are in the same component if and only if the corresponding milestones
are in the same component of ${\cal C}_{free}$. Step 3 may fail to
find all possible links between the milestones due to the
incompleteness of the connector. {\tt Permeation} invoked in Step 4
fixes this problem by using the complex planner to discover additional
connections between milestones.  Note that {\tt Permeation} is a last
resort; hopefully, much if not all of the connectivity information
should have been discovered before this step.

It is worth noticing that the algorithms of the implemented planner
presented in~(Kavraki 1995; Kavraki and Latombe 1994a; Kavraki and
Latombe 1994b) are similar to those described here, except that it
uses the potential-field planner of Section~\ref{ssec:potential}
instead of the complex planner.  The potential-field planner is not
complete, but it is quite rare in practice that two milestones in the
same component of the free space can be connected neither by invoking
{\tt Connect} at Step 3 of the proprocessing, nor by the
potential-field planner. The planner of~(Kavraki 1995; Kavraki and
Latombe 1994a; Kavraki and Latombe 1994b) seems a good approximation
of the algorithms given here, and the analysis proposed below is
relevant to this planner.

The query processing is handled by the following algorithm, which is
similar to the query-processing algorithm of Section~3.2:

\vspace{0.1in}

\noindent
\hspace*{0.07in} {\tt Query-Processing}$({\bm q}_{init},{\bm q}_{goal})$:

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item For $i = \{init,goal\}$ do:

\begin{enumerate} \denselist

\item If there exists a milestone {\bm m} that sees ${\bm q}_i$
then ${\bm m}_i \leftarrow {\bm m}$.

\item Else

\begin{enumerate} \denselist

\item Repeat $g$ times:

\vspace{0.05in}

Pick a configuration {\bm q} at random in ${\cal S}({\bm q}_i)$

\vspace{0.05in}

until {\bm q} sees both ${\bm q}_i$ and a milestone {\bm m}.

\item If all $g$ trials failed then return {\sc failure} and halt,
else ${\bm m}_i \leftarrow {\bm m}$.

\end{enumerate}

\end{enumerate}

\item If ${\bm m}_{init}$ and ${\bm m}_{goal}$ are in the same 
component of the roadmap then return {\sc yes}; else return {\sc no}.

\end{enumerate}

Step 1(b)i differs slightly from the corresponding step in the
query-processing algorithm of Section~3.2. Since in general we do not
know how to compute ${\cal S}({\bm q}_i)$, picking configurations in
this set requires guessing configurations in configuration space and
retaining only those that are seen by ${\bm q}_i$. This means that
each of the $g$ iterations performed at Step 1(b)i may require several
trials to obtain a configuration visible from ${\bm q}_i$. The
analysis proposed below ignores these trials and focuses only on the
number $g$.

Another difference between the above algorithm and the one of
Section~3.2 is that it returns {\sc failure} (instead of {\sc no}) at
Step 1(b)ii. Due to the use of the {\tt Permeation} in the
preprocessing, both the answers {\sc yes} and {\sc no} are now always
correct.  With some probability though, the query-processing algorithm
may fail to give an answer.

\subsubsection{Performance guarantees}

Let us first present some performance guarantee for the preprocessing
phase.  Call a set of milestones {\em adequate} if the volume of the
subset of ${\cal C}_{free}$ not visible from any of these milestones
is at most $(\epsilon/2)\mu(\mbox{\cfree})$. Intuitively, if we were
to place a point source of light at each milestone, we would like a
fraction at least $1-\epsilon/2$ of \cfree\ to be illuminated.

Let $C$ be a positive constant large enough that for any $x\in(0,1]$,
$(1-x)^{(C/x)(\log 1/x + \log 2/\beta)}\leq x\beta/2$. Clearly, there
exists such a constant.

\begin{theorem} \label{thm:preproc1} Let $\beta\in(0,1]$ be a positive
real constant.  If $s \geq (C/\epsilon)(\log 1/\epsilon + \log
2/\beta)$, then preprocessing generates an adequate set of milestones
with probability at least $1-\beta$.
\end{theorem}

Note that as $\epsilon$ increases, the requirement for adequacy grows
weaker, i.e., the portion of the free space that has to be visible by
at least one milestone gets smaller. Intuitively, this comes from the
fact that a greater $\epsilon$ will make it easier to connect query
configurations to the roadmap. Naturally, the number of milestones
needed becomes smaller.

Theorem~\ref{thm:preproc1} only says that most of
\cfree\ is likely to be visible from some milestone in the roadmap;
using this property alone, we can show that queries can be answered
quickly. But the adequacy of the milestones is not sufficient to imply
that the roadmap is a good representation of the connectivity of
${\cal C}_{free}$. The use of the complex planner in the permeation
algorithm is inevitable to ensure a good probability that the query
processing outcomes {\sc yes} or {\sc no}.

Let us choose $g = \log (2/\gamma)$ at Step 2 of {\tt
Query-Processing}, where $\gamma\in(0,1]$ is the failure probability
we are willing to tolerate during a query.  We can show the following
performance guarantee for the query processing phase:

\begin{theorem}
\label{thm:query}
If the set of milestones chosen during preprocessing is adequate, then
the probability that the query-processing algorithm outputs {\sc
failure} is at most $\gamma$.
\end{theorem}

In fact, our analysis (in the Appendix, Section B) implies that the
expected number of executions of Step 1(b)i in the query-processing
algorithm is at most 2.

Theorems 1 and 2 give performance guarantees for the preprocessing
phase and the query-processing phase, respectively. This is
appropriate, since many queries will be made using the same roadmap.
However, we can easily blend the two theorems to bound the probability
that the planner returns {\sc failure} for a single query by
$(1-\beta) \gamma + \beta$ (this is obtained by bounding by one the
probability that the planner returns {\sc failure} when the set of
milestones is not adequate). Then, let $\alpha \in (0,1]$ be the
probability of a {\sc failure} outcome which we are willing to
tolerate.  Neither the number $s$ of milestones, nor the number $g$ of
trials at Step 2 of {\tt Query-Processing} grow faster than
$\log(1/\alpha)$, when $\alpha \rightarrow 0$.

\subsubsection{Number of calls to complex planner}

We now turn to the description of {\tt Permeation} and its
analysis. Our goal is to evaluate how many times the complex planner
must be invoked at Step 4 for the preprocessing algorithm.

{\tt Permeation} must determine which milestones in $V$ are reachable
from each other, i.e., it must partition $V$ into subsets such that all
milestones in the same subset belong to the same component of ${\cal
C}_{free}$ and no two milestones in two different subsets are in the
same component of ${\cal C}_{free}$.  If $p$ is the size of $V$, it
can do so with $O(p^2)$ invocations of the complex planner by trying
it on every pair of milestones in $V$, but we show below that far
fewer invocations may suffice.

We work with the following abstract version of the permeation problem.
The input is a graph $N$ with $p$ vertices, consisting of $k$ disjoint
cliques. The goal is to determine this clique partition of $N$. The
graph is presented as an adjacency matrix and the cost of an algorithm
is measured by the number of entries it examines in the adjacency
matrix of $N$. This is the {\em edge probe model} used in the study of
evasive graph properties~(Lov\'asz and Young 1991).  The vertices of
$N$ correspond to the milestones in $V$, and an edge is present
between two vertices if the corresponding milestones lie in the same
component of \cfree. The milestones from any particular component of
\cfree\ will form a clique in $N$, and there are no edges between two
distinct cliques. A probe into the adjacency matrix corresponds to an
invocation of the complex planner.

Let $NC(p,k)$ denote the non-deterministic complexity of this problem.
A non-deterministic algorithm is only required to verify that some
partition into $k$ cliques is the right partition. It must make at
least one probe on each of the $p$ vertices. It must also have
verified that each pair of cliques is in fact disconnected. Hence:

\begin{theorem}
For $1 \leq k \leq p$, $NC(p,k) = \Theta(p + k^2)$.
\end{theorem}

The non-deterministic complexity of the problem is clearly a lower
bound on its deterministic and even randomized complexity.

We now characterize the worst-case deterministic complexity of this
problem, denoted $T(p,k)$. Consider the following deterministic
algorithm: by probing all edge slots incident on an arbitrary vertex
$x$, determine the neighborhood of $x$, say $\Gamma(x)$; let $C_x =
\{x\} \cup \Gamma(x)$, and output $C_x$; then, recur on the 
vertex-induced subgraph $N[V \setminus C_x]$. The number of levels in
the recursion is $k$, since one of the $k$ cliques is removed from $N$
prior to each recursive call. The number of probes made in the process
of determining each such clique is at most $p$. The total number of
probes is $O(pk)$.  The following permeation algorithm is an iterative
version of the recursive algorithm (the nodes of $N$ are named
$1,2,\dots,p$):

\vspace{0.1in}

\noindent
\hspace*{0.07in} {\tt Deterministic-Permeation}$(V)$:

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item
Mark all vertices of $N$ as being {\sc live}.
\item
Initialize $x \leftarrow 1$.
\item
While $x \leq p$ do:
\begin{enumerate} \denselist
\item
$\Gamma(x) \leftarrow \emptyset$.
\item
For $y = x+1$ to $p$ do:
\begin{enumerate} \denselist
\item
If vertex $y$ is marked {\sc live} then probe the edge $(x,y)$ in $N$.
\item
If edge $(x,y)$ is probed and found present then mark $y$ as {\sc
dead} and add $y$ to $\Gamma(x)$.
\end{enumerate}
\item
Output $\{x\} \cup \Gamma(x)$ as being a clique.
\item
Mark $x$ as being {\sc dead}.
\item
Set $x$ to the smallest numbered {\sc live} vertex, or $p+1$ if there
are no {\sc live} vertices left.
\end{enumerate}
\end{enumerate}

By the preceding discussion, we have:

\begin{theorem}~{\tt Deterministic-Permeation} cor\-rectly solves the permeation problem
using $O(pk)$ probes.
\end{theorem}

The following lower bound establishes that {\tt
Deterministic-Permeation} is optimal.  The proof uses a non-trivial
adversary argument~(Kavraki, Latombe, Motwani, and Raghavan 1995).

\begin{theorem}
\label{thm:detlb}
For $1 \leq k \leq p$, $T(p,k) = \Omega(pk)$.
\end{theorem}

We now give a randomized algorithm that beats the lower bound of
Theorem~\ref{thm:detlb} when the sizes of the $k$ cliques differ
significantly, which is often the case in practice (when $k > 1$).
{\tt Randomized-Permeation} labels the vertices in a random order and
then invokes {\tt Deterministic-Permeation}.

\vspace{0.1in}

\noindent
\hspace*{0.07in} {\tt Randomized-Permeation}$(V)$:

\vspace*{-0.1in}

\begin{enumerate} \denselist

\item
Permute the vertices randomly. Rename the nodes by $1, \ldots, n$,
in the order of the generated list.
\item
Invoke {\tt Deterministic-Permeation}$(V)$.
\end{enumerate}

Let $w_1 \geq w_2 \geq \cdots \geq w_k$ be the sizes of the cliques
in an instance $N$ arranged in a non-increasing order, where
$p = \sum_{i=1}^k w_i$. Denote by $C_i$ the $i$th largest
clique in $N$. Define a function $u()$ on
an ordered $k$-tuple of positive integers $n_1,n_2,\dots,n_k$
by $u(n_1,n_2,\dots,n_k)=\sum_{i=1}^kin_i$.

\begin{theorem}
\label{thm:randperm}
{\tt Randomized-Permeation} correctly determines the clique structure
and incurs an expected cost that is at most $$ 2u(w_1,w_2,\dots,w_k) -
p-k.$$ Furthermore, with high probability, the cost is at most
$$O(u(w_1,w_2,\dots,w_k)\log p).$$
\end{theorem}

Observe that the worst case is when all $w_i$ are equal to $p/k$,
in which case the expected cost is $O(pk)$. On the other hand when
there is one giant clique and $k-1$ cliques of size $O(1)$
the expected cost is $\Theta(p + k^2)$, which is essentially the
non-deterministic lower bound.

\subsection{Path Clearance Assumption}

The visibility volume assumption does not prevent the existence of
narrow passages in ${\cal C}_{free}$. To remove the need for the
``complex planner'' and get closer to the roadmap planner of
Section~3.2, we now consider a seemingly stronger assumption: between
the two configurations given by a query, there exists a collision-free
path $\tau$ that achieves some clearance $\xi$ between the robot and
the obstacles. More formally, let us parametrize $\tau$ by the arc
length $\ell$ from the initial configuration and let $L$ designate the
path's total length, i.e., $\tau : \ell \in [0,L]
\rightarrow \tau(\ell) \in {\cal C}_{free}$. We define $\xi(\ell)$
to be the Euclidean distance between $\tau(\ell)$ and the free space
boundary, and $\xi_{inf}$ to be $\inf_{\ell \in
[0,L]} \xi(\ell)$.

We consider a variant of the roadmap planner in which the
preprocessing algorithm consists of the first three steps of the
algorithm given in Section~4.1. Unlike the planner of Section~3.2, it
does not include the resampling step. The query-processing algorithm
is also simpler than in Section~3.2, in that it only checks that the
initial and goal configurations see milestones in the roadmap. If any
one of these connections fails, the query-processing algorithm returns
{\sc no}.  Hence, this query-processing algorithm is deterministic.

Under the path clearance assumption, any {\sc no} outcome is
incorrect.  Let $\alpha$ be the probability that we are willing to
tolerate for this event. The following two theorems relate the size of
the roadmap to this probability, as well as to the two parameters of
the assumption, that is, the length $L$ of the hypothesized path and
its clearance.  They give a performance guarantee for the whole
planner.

\begin{theorem}
\label{th:unif}
Let $\alpha \in (0,1]$ be a positive real constant.  Let $a$ be the
constant $2^{-n} \mu({\cal B}_1) / \mu({\cal C}_{free})$ where ${\cal
B}_1$ denotes the unit ball in $\RR^n$.  If $s$ is chosen such that:
\begin{equation}\label{eq:failure}
{2 L\over \xi_{inf}}(1- a \xi_{inf}^n)^s \leq \alpha,
\end{equation}
then the planner outputs {\sc yes} with probability at least $1-\alpha$.
\end{theorem}

Note that, for any given $L$ and $\xi_{inf}$, the quantity on the left
side of the above inequality tends toward zero when $s \rightarrow
\infty$. It is even more important to remark that it
depends exponentially on $s$, so that the number of milestones $s$
needed grows no faster than the logarithm of $1/\alpha$.

The following theorem is similar to the previous one, but makes use of
the clearance distribution $\xi(\ell)$ rather than just its infimum:

\begin{theorem}
\label{th:non-unif}
Let $\alpha \in (0,1]$ be a positive real constant.  Let $a$ be the
same constant as in Theorem~\ref{th:unif}.  If $s$ is chosen such that:
\begin{equation}
\label{eq:non-unif}
6 \int_0^L { \left(1-{(a / 2^n)}\xi^n(\ell)\right)^s \over \xi(\ell)}
d\ell \leq \alpha,
\end{equation}
then the planner outputs {\sc yes} with probability at least $1-\alpha$.
\end{theorem}

Using the inequality $1-x \le e^{-x}$, for $x\ge0$,
we get the following easier-to-use relations:

\begin{itemize}
\item
The bound of Theorem~\ref{th:unif} becomes:
\begin{equation}\label{eq:unif-simple-high}
{2L\over \xi_{inf}} \exp(-a \xi_{inf}^n s) \leq \alpha.
\end{equation}
\item
The bound of Theorem~\ref{th:non-unif} becomes:
\begin{equation}\label{eq:non-unif-simple-high}
6 \int_0^L {\exp(- a 2^{-n} \xi^n(\ell) s)\over \xi(\ell)} d\ell \leq
\alpha.
\end{equation}
\end{itemize}

Relation~\ref{eq:unif-simple-high} implies that the number of
milestones that the planner must generate to output {\sc yes} with
probability at least $1-\alpha$ is polynomial in $1/\xi_{inf}$ and
logarithmic in $L$.

Remark that $\xi(\ell) \geq (1/2\rho)$ {\sc clearance}($\tau(\ell)$),
where $\rho$ is the constant introduced in Section~2. Indeed, for any
${\bm q} \in {\cal C}_{free}$, let ${\bm q}^c$ be the configuration in
the free space boundary that achieves minimum distance with {\bm q}
and let $\xi({\bm q})$ be this distance. We have: $\xi({\bm q}) \geq
\max_i |q_i-q^c_i|$. By the definition of $\rho$, all configurations
${\bm q}^\prime$ such that $\max_i|q_i - q^\prime_i| \leq$ {\sc
clearance}({\bm q})$/2\rho$ are in the free space. Hence, {\sc
clearance}({\bm q})$/2\rho < \max_i |q_i-q^c_i| \leq \xi({\bm q})$.
Therefore, the bounds given above remain valid if we choose to define
$\xi(\ell)$ as $(1/2\rho)$ {\sc clearance}($\tau(\ell)$), rather than
as the distance between $\tau(\ell)$ and the free space
boundary.

\subsection{Example}

\begin{figure}[t]
\centerline{\psfig{figure=example.ps,height=6cm}}
\caption{Illustrative example}
\label{fig:example}
\end{figure}
 
Consider the two-dimensional problem ($n = 2$) shown in
Figure~\ref{fig:example}.  This problem is parametrized by $\omega$.
The walls are obstacles, but have zero thickness; hence, $\mu({\cal
C}_{free}) = 1$. We are interested in the order of magnitude of $s$
when $\omega$ is small.  Let $x \asymp y$ mean that $x/K \le y
\le K x$ for some constant $K > 0$. In particular, we have $L \asymp
1$ and $\xi_{inf} \asymp \omega$.

\vspace{0.1in}

\noindent{\bf Estimate of $s$ using Theorem~\ref{thm:preproc1}:}
The space in Figure \ref{fig:example} is $\epsilon$-good for $\epsilon
= 2 \omega^2$ (clearly, because of the ``box'' on the left).  In order
to bound the probability that the query-processing algorithm of
section~4.1 outputs {\sc failure}, while a collision-free path exists
(Theorem~\ref{thm:query}), the roadmap must be adequate. According to
Theorem~\ref{thm:preproc1}, this is achieved with high probability if:
\begin{equation}\label{eq:STOC-res}
s \asymp {1\over\omega^2}\log{1\over\omega}.
\end{equation}

\noindent{\bf Estimate of $s$ using Theorem~\ref{th:unif}:}
Using (\ref{eq:unif-simple-high}) we can derive the following order of
magnitude for $s$ that will make the planning algorithm of Section~4.2
to return {\sc yes} with high probability~(Kavraki, Kolountzakis, and
Latombe 1996):
\begin{equation}\label{eq:unif-res}
s \asymp {1\over \omega^2} \log{1\over\omega}.
\end{equation}

\noindent{\bf Estimate of $s$ using  Theorem~\ref{th:non-unif}:}
The bound given by~(\ref{eq:non-unif-simple-high}) leads to
choosing~(Kavraki, Kolountzakis, and Latombe 1996):
\begin{equation}\label{eq:non-unif-res}
s \asymp {1\over\omega^2}\log\log{1\over\omega}.
\end{equation}

\vspace{0.1in}

\noindent{\bf Comparison:}
Note that to answer queries with high probability
it is necessary and sufficient in this example to
pick a bounded number of milestones in the box,
which happens with probability $\asymp \omega^2$.
Hence, a tight estimate of $s$ is
\[ s \asymp {1\over\omega^2}. \]
The estimates~(\ref{eq:STOC-res}),~(\ref{eq:unif-res}),
and~(\ref{eq:non-unif-res}) can be seen as the unavoidable quantity
$1/\omega^2$ times some factor.  By exploiting the fact that
$\xi(\ell)$ is small only briefly, we get a smaller factor
in~(\ref{eq:non-unif-res}) than in~(\ref{eq:unif-res}).


\section{Discussion}

Between complete planners, which take prohibitive time to run in large
dimensional configuration spaces, and ad hoc planners, which are too
unreliable, there exist planners that are reasonably efficient while
achieving some form of completeness. In this paper we have discussed a
class of such planners. These are based on a general computational
scheme presented in Section~2, which consists of randomly sampling the
free space and checking pairs of sample configurations for
adjacency. By choosing an appropriate sampling strategy, this scheme
can be turned into a concrete planner that achieves probabilistic
completeness.  In Section~3 we have presented two examples of
probabilistically complete planners: the potential-field and the
roadmap planners. In Section~4 we have analyzed in more detail the
probabilistic completeness of variants of the roadmap planner, under
two different assumptions: the visibility volume assumption and the
path clearance assumption.  In each case, we have established a
relation between the probability that the planner finds a path, when
one exists, and its running time (measured in that case by the number
of milestones in the roadmap).  Both analyses show that the number of
milestones needed grows only as the absolute value of the logarithm of
the probability of an incorrect answer that we are willing
tolerate. Moreover, this number is polynomial in the inverse of the
parameter used to measure the goodness of free space ($\epsilon$ in
the first analysis, $\xi_{inf}$ in the second). 
%However, our analysis
%does not evaluate the total number of sample configurations generated
%by the roadmap planner. To get a more complete analysis of the
%probabilistic completeness of the planner, it would also be necessary
%to bound the work done by the connector.

How realistic and useful are our assumptions? Clearly, in most cases,
there is no pratical way to verify that they are
satisfied. Furthermore, it is easy to create spaces that are
$\epsilon$-good for very small values of $\epsilon$, as well as spaces
that are not $\epsilon$-good for any positive value of $\epsilon$. For
instance, this is the case of the space comprised between two circles
$C_1$ and $C_2$ tangent at some point $P$, with $C_2$ contained in
$C_1$.  On the other hand, in many applications, we are willing to
discard collision-free paths if their clearance is too small, due to
uncertainties in robot control and sensing. In those cases, a planner
that would return a path with high probability, whenever there exists
one that has enough clearance, would be quite
satisfactory.\footnote{Note that the roadmap planner may nevertheless
return a path with a smaller clearance.}  Remark also that, if there
exists a collision-free path with a clearance greater than some given
$\xi_{inf}$, this path must lie in a subset of ${\cal C}_{free}$ that
is at least $\epsilon$-good for an $\epsilon$ that can be
derived\footnote{However, the bound derived from $\xi_{inf}$ may be
much smaller than the actual $\epsilon$. E.g., if the free
space is a rectangle having very small width $\xi$, then $\xi_{inf}
\leq \xi$, but $\epsilon = 1$.} from $\xi_{inf}$. Hence, the 
assumption of $\epsilon$-goodness is realistic as well: for any given
value of $\epsilon$, our analysis characterizes the probability that
the planner finds a path in the subset of ${\cal C}_{free}$ that is
$\epsilon$-good.

\begin{figure}[t]
\centerline{\psfig{figure=robot.ps,bbllx=10mm,bblly=20mm,bburx=60mm,bbury=70mm}}
\caption{Robot arm example}
\label{config}
\end{figure}

But we think that much more could be done. In particular, neither of the
two analyses we have given considers the resampling step (Step 4) in
the preprocessing algorithm of Section~3.2. On the other hand, our
experiments have shown that adding this step yields a much better
roadmap planner. In relation to this observation, we have empirically
tested the free space corresponding to the setting of
Figure~\ref{config} (a seven-revolute-dof planar arm among several
barriers forming multiple gates) for $\epsilon$-goodness.  To do so we
have picked 9,000 milestones at random and we have computed how many
other milestones each milestone can see. The milestones with the
``most'' visibility could only see about $0.06$ (i.e., 6\%) of the
remaining milestones, suggesting that they are $0.06$-good. As many as
$3.3$\% of the milestones could see no other milestones, and fully
$22$\% could see $0.001$ (i.e., $0.1$\%) or less; in other words, only
about $78$\% of the configuration space is $0.001$-good or better. On
the other hand, the implemented planner, which includes the resampling
step, handles queries in this setting with quasi-perfect reliability,
after having constructed a roadmap containing 5,000 to 10,000
milestones. Other experiments confirm that the use of {\tt Resampling}
improves the coverage of the free space by the milestones.

\newcommand{\egk}[1]{($\epsilon, #1)$-good}
To explain the role of {\tt Resampling} we introduce a generalization
of the notion of $\epsilon$-goodness. We say that a free configuration
${\bm q}$ is \egk{1}\ if $\mu({\cal S}({\bm q}))\geq\epsilon\mu({\cal
C}_{free})$, corresponding to our original definition of
$\epsilon$-goodness for a configuration.  Next, we say a free
configuration ${\bm q}$ is \egk{t}\ if $\mu(\{{\bm q}^\prime \in {\cal
S}({\bm q})\mid {\bm q}^\prime \mbox{ is \egk{t-1}}\}) \geq
\mu({\cal S}({\bm q}))/2$.  For $t >1$, we say that \cfree\ is
\egk{t}\ if $\mu(\{{\bm q} \in \mbox{\cfree}| {\bm q} \mbox{ is
\egk{1}}\})\geq
\mu(\mbox{\cfree})/2$ and every free configuration is \egk{i}\ for
$i\leq t$.  If \cfree\ is \egk{t}\ for a small value of $t$, we can
give a theoretical basis for the resampling strategy.  The main idea
is that single links discovered by the connector in the algorithms are
now simulated using $t$-link paths found by resampling and connecting
using the connector.  This leads to a generalized definition of an
adequate set of milestones, and eventually to a version of
Theorem~\ref{thm:query} in which the number of invocations of the
connector is larger by a factor of $2^t$. See~(Kavraki, Latombe,
Motwani, and Raghavan 1996) for more detail.

We believe   that  future  research  should  develop  and  analyze new
sampling  strategies, as well  as   combinations of strategies,  under
various assumptions. In particular, it would be of particular interest
to investigate strategies suitable for single-query planning problems.
In this case, instead of spreading milestones all over the free space,
one could expand a ``cloud'' of sample configurations from the initial
configuration  toward the goal,   or in both  directions concurrently.
This could  be  achieved by  iteratively generating  configurations in
small neighborhoods  of  previously  generated configurations,   while
keeping  only those configurations  which  are in the  same free space
component as the  initial configuration.   This  strategy could  use a
function similar to a potential field as a probability distribution to
randomly    choose which  configurations   to expand    from at  every
iteration.   In the multi-query case,    it would also  be useful   to
consider the case where all queries are made  in the same component of
${\cal C}_{free}$ and the preprocessing  is given one configuration in
that component. The case where  the volume of  the free space is  very
small relative  to the total  volume of the configuration space should
also be investigated.  We envision that ultimately randomized planners
will  automatically  select and   combine  sampling strategies from  a
library of basic strategies  to  closely match the characteristics  of
the input problems.  This sort  of combination has already given  good
results in another area, graphic rendering~(Veach and Guibas 1995).

We did not discuss distance calculation in this paper, but it is a key
computation in the context of our sampling scheme.  Indeed, our
planners spend most of their time evaluating {\sc clearance}. So, any
improvement of the time efficiency of the algorithm implementing {\sc
clearance} would translate into a planning improvement of the same
order of magnitude.  One could also try to match the distance
calculation algorithm and the sampling strategy, to get the best
global result. For example, a sampling strategy generating
configurations in small neighborhoods of previously generated
configurations could be combined with an incremental distance
calculation algorithm such as the one proposed in~(Lin and Canny
1991). Such an algorithm uses the nearest points computed at the
previous configuration to quickly find the nearest points at the new
configuration. As another example, the distance calculation algorithm
proposed in~(Quinlan 1994), and used in our planners, precomputes data
structures to later accelerate the processing of distance calculation
queries. Each such data structure is a binary tree of spheres
approximating a single rigid body. Given two bodies, a simple
traversal of their respective trees allows us to quickly detect
collision or identify the nearest points between the two bodies.  A
perhaps more efficient solution would be to create a single data
structure for all the rigid bodies forming the robot and to
efficiently update this data structure when configuration parameters
vary, as proposed in~(Halperin, Latombe, and Motwani 1996). Then the
sampling strategy should try to generate configurations in a sequence
that minimizes update costs.

The random sampling scheme for path planning proposed in this paper
offers many opportunities for further research.  We are confident that
it can ultimately produce very fast planners able to correctly handle
a wide range of problems with high probability.

\vspace*{0.1in}

\noindent {\small {\bf Acknowledgments:} The development of the
potential-field and roadmap planners has been supported by ARPA
contracts DAAA21-89-C0002, N00014-92-J-1809, and N00014-94-1-0721.
The formal analysis of these planners and the design of the general
random sampling scheme was supported by MURI grant DAAH04-96-1-0007
(Army).  The experimental part of this research has also benefited
from gifts by General Electric, General Motors, Renault, and Rockwell.
Lydia Kavraki and Jean-Claude Latombe are partially supported by ARPA
contract N00014-94-1-0721 and a MURI grant of the Army.  Rajeev
Motwani is supported by an Alfred P.~Sloan Research Fellowship, an IBM
Faculty Partnership Award, and NSF Young Investigator Award
CCR-9357849, with matching funds from IBM, Schlumberger Foundation,
Shell Foundation, and Xerox Corporation. This paper has benefited from
useful comments by Leo Guibas, Dan Halperin, and Jean-Paul Laumond.}

{\small

\section*{References}

Ahuactzin Larios, J.M. 1994. Le Fil d'Ariane: Une M\'ethode de
Planification G\'en\'erale. Application \`a la Planification
Automatique de Trajectoires. Th\`esis Dissertation. Grenoble, France:
Institut National Polytechnique.

Arya, S. and Mount, D.M. 1995. Approximate Range Searching. {\em Proc.~ACM
Symp.~on Computational Geometry}. pp. 172-181.

Barraquand, J. and Latombe, J.C. 1991. Robot Motion Planning: A
Distributed Representation Approach. {\em Int.~J.~Robotics Res.}
10(6):628-649.

Barraquand, J., Langlois, B. and Latombe, J.C. 1992. Numerical potential
Field Techniques for Robot Path Planning. {\em IEEE Tr.~on Syst., Man,
and Cyb.}, 22(2):224-241.

Bessi\`ere, P., Mazer, E., and Ahuactzin, J.M. 1995. Planning in a
Continuous Space with Forbidden Regions: The Ariadne's Clew Algorithm.
{\em Algorithmic Foundations of Robotics}, ed. K.~Goldberg et al.
Wellesley:A.K. Peters, pp. 39-47.

Canny, J.F. 1988. {\em The Complexity of Robot Motion Planning},
Cambridge:MIT Press.

Challou, D. and Gini, M. 1995. Parallel Formulation of Informed
Randomized Search for Robot Motion Planning Problems. {\em Proc.~IEEE
Int.~Conf.~on Robotics and Automation}. Nagoya: IEEE, pp. 709-714.

Chang, H. and Li, T.Y. 1995. Assembly Maintainability Study with
Motion Planning, {\em Proc.~IEEE Int.~Conf.~on Robotics and
Automation}. Nagoya: IEEE, pp. 1012-1019.

Chen, P.C. 1995. Adaptive Path Planning: Algorithm and Analysis.  {\em
Proc.~IEEE Int.~Conf.~on Robotics and Automation}. Nagoya: IEEE.
pp. 721-728.

Gilbert, E.G, Johnson, D.W., and Keerthi, S.S. 1988. A Fast Procedure
for Computing the Distance Between Complex Objects in
Three-Dimensional Space. {\em IEEE J.~of Robotics and Automation}.
4(2):193-203.

Graux, L., Millies, P., Kociemba, P.L., and Langlois,
B. 1992. Integration of a Path Generation Algorithm into Off-Line
Programming of AIRBUS Panels. {\em Aerospace Automated Fastening
Conf.~and Exp.}, SAE Tech.~Paper 922404.

Halperin, D., Latombe, J.C., and Motwani, R. 1996 Dynamic Maintenance
of Kinematic Structures. {\em Algorithmic Foundations of Robotics},
ed. J.P. Laumond and M. Overmars.  Wellesley:A.K. Peters, to appear.

Hopcroft, J.E., Schwartz, J.T., and Sharir, M. 1984. On the Complexity
of Motion Planning for Multiple Independent Objects: PSPACE-Hardness
of the `Warehouseman's Problem'. {\em Int.~J.~of Robotics Res.}
3(4):76-88.

Hopcroft, J.E. and Wilfong, G.T. 1986. Reducing Multiple Object Motion
Planning to Graph Searching. {\em SIAM J.~on Computing}.
15(3):768-785.

Horsch, T., Schwarz, F., and Tolle, H. 1994. Motion Planning for Many
Degrees of Freedom - Random Reflections at C-Space Obstacles, {\em
Proc.~IEEE Int.~Conf.~on Robotics and Automation}, San Diego: IEEE,
pp. 3318-3323.

Hwang, Y.K. and Chen, P.C. 1995. A Heuristic and Complete Planner for
the Classical Mover's Problem. {\em Proc.~IEEE Int.~Conf.~on Robotics
and Automation}, Nagoya: IEEE, pp. 729-736.

Joseph, D.A. and Plantiga, W.H. 1985.  On the Complexity of
Reachability and Motion Planning Questions.  {\em Proc.~1st
ACM Symp.~on Computational Geometry}, pp. 62-66.

Kavraki, L. Random Networks in Configuration Space for Fast Path
Planning. STAN-CS-TR-95-1535. Stanford, Calif.: Computer Science Dept.

Kavraki, L., Kolountzakis, M., and Latombe, J.C. 1996. Analysis of
Probabilistic Roadmaps for Path Planning, {\em Proc.~IEEE
Int.~Conf.~on Robotics and Automation}, Minneapolis: IEEE,
pp. 3020--3025.

Kavraki, L. and Latombe, J.C. 1994a. Randomized Preprocessing of
Configuration Space for Fast Path Planning, {\em Proc.~IEEE
Int.~Conf.~on Robotics and Automation}, San Diego: IEEE,
pp. 2138-2145.

Kavraki, L. and Latombe, J.C. 1994b. Randomized Preprocessing of
Configuration Space for Path Planning: Articulated Robots, {\em
Proc.~IEEE Conf.~on Intell. Robots and Systems}, M\"unchen: IEEE,
pp. 1764-1771.

Kavraki, L., Latombe, J.C., Motwani, R., and Raghavan, P. 1994.
Randomized Query Processing in Robot Motion Planning.
STAN-CS-TR-94-1533, Stanford, Calif.: Computer Science Dept.

Kavraki, L., Latombe, J.C., Motwani, R., and Raghavan,
P. 1995. Randomized Query Processing in Robot Path Planning, {\em
Proc.~27th Annual ACM Symp.~on Theory of Computing}, Las Vegas: ACM,
pp. 353-362. (A journal version of this paper will appear in {\em
Journal of Computer and System Sciences}.)

Kavraki, L., \v{S}vestka, P., Latombe, J.C., and Overmars, M. 1996.
Probabilistic Roadmaps for Fast Path Planning in High Dimensional
Configuration Spaces. {\em IEEE Tr.~on Robotics and Automation},
12(4):566-580.

Koditschek, D.E. 1987. Exact Robot Navigation by Means of Potential
Functions: Some Topological Considerations, {\em Proc.~IEEE
Int.~Conf.~on Robotics and Automation}, Raleigh: IEEE, pp. 1-6.

Koga, Y., Kondo, K., Kuffner, J., and Lat\-ombe, J.C. 1994.  Planning
Motions with Intentions. {\em Proc.~of SIGGRAPH'94}, ACM, pp. 395-408.

Koga Y. and Latombe, J.C. 1994. On Multi-Arm Manipulation Planning,
{\em Proc.~IEEE Int.~Conf.~on Robotics and Automation}, San Diego:
IEEE, pp. 945-952.

Lamiraux, F. and Laumond, J.P. {\em On the Expected Complexity of
Random Path Planning}. Rep.~No.~95087. Toulouse, France: LAAS/CNRS.

Latombe, J.C. 1991. {\em Robot Motion Planning}, Boston:Kluwer.

Latombe, J.C. 1995. Controllability, Recognizability, and Complexity
Issues in Robot Motion Planning. {\em Proc.~36th Annual Symp.~on
Foundations of Computer Science}, Milwaukee: IEEE, pp. 484-500.

Li, T.Y. and Latombe, J.C. 1995. On-Line Motion Planning for Two Robot
Arms in a Dynamic Environment, {\em Proc.~IEEE Int.~Conf.~on Robotics
and Automation}, Nagoya: IEEE, pp. 1048-1055.

Lin, M.C. and Canny, J.F. 1991. A Fast Algorithm f0r Incremental
Distance Calculation, {\em Proc.~IEEE Int.~Conf.~on Robotics and
Automation}, Sacramento: IEEE, pp. 1008-1014.

Lov\'asz, L. and Young, N. 1991. Lecture Notes on Evasiveness of Graph
Properties. CS-TR-317-91. Princeton: Computer Science Dept.

Motwani, R. and Raghavan, P. 1995. {\em Randomized
Algorithms}. Cambridge, UK:Cambridge University Press.

Overmars, M. 1992. A Random Approach to Motion Planning.
RUU-CS-92-32. Utrecht, The Netherlands: Computer Science Dept.

Overmars, M. and \v{S}vestka, P. 1995. A Probabilistic Learning Approach to
Motion Planning, {\em Algorithmic Foundations of Robotics}, ed.
K.~Goldberg et al. Wellesley: A.K. Peters, pp. 19-37.

Ponamgi, M., Manocha, D., and Lin, M.C. 1995. Incremental Algorithms
for Collision Detection Between Solid Models, {\em Proc.~3rd ACM
Symp.~on Solid Modeling and Applications}, Salt Lake City: ACM,
pp. 293-304.

Preparata, F.P. and Shamos, M.I. 1985. {\em Computational Geometry: An
Introduction}, New York:Springer-Verlag.

Quinlan, S. 1994. Efficient Distance Computation Between Non-Convex
Objects. {\em Proc.~IEEE Int.~Conf.~on Robotics and Automation}, San
Diego: IEEE, pp. 3324-3330.

Reif, J. 1979. Complexity of the Mover's Problem and Generalizations.
{\em Proc.~IEEE Symp.~on Foundations of Computer Science}. IEEE,
pp. 421-4127.

Reif, J. and Sharir, M. 1985. Motion Planning in the Presence of
Moving Obstacles, {\em Proc.~25th IEEE Symp.~on Foundations of
Computer Science}. IEEE, pp. 144-154.

Schwartz, J.T. and Sharir, M. 1983. On the `Piano Movers' Problem:
II.~General Techniques for Computing Topological Properties of Real
Algebraic Manifolds. {\em Advances in Applied Mathematics}. 4:298-351.

Sekhavat, S., \v{S}vestka, P., Laumond, J.P., and Overmars, M. 1995.
Probabilistic Path Planning for Tractor-Trailer Robots.
Tech.~Rep. Toulouse, France: LAAS/CNRS.

\v{S}vestka, P. 1993. A Probabilistic Approach to Motion Planning for
Car-Like Robots. RUU-CS-93-18. Utrecht, The Netherlands: Computer
Science Dept.

Thomas, F. and Torras, C. 1994. Interference Detection Between
Non-Convex Polyhedra Revisited with a Practical Aim. {\em Proc.~IEEE
Int.~Conf.~on Robotics and Automation}, San Diego: IEEE, pp. 587-590.

Veach, E. and Guibas, L.J. 1995. Optimally Combining Sampling
Techniques for Monte Carlo Rendering. {\em Proc.~of SIGGRAPH'95}. ACM,
pp. 419-428.

Zhu, X. and Gupta, K. 1993. On Local Minima and Random Search in
Robot Motion Planning. Tech.~Rep. Vancouver, Canada: Simon Fraser Univ.
}

\section*{Appendix: Selected Proofs}

\subsubsection*{A.~~Proof of Theorem 1}

Let $M$ denote the set of the $s$ randomly chosen milestones.
The volume $H$ of configurations not visible from any
of these milestones is:
\[ \mu(\{{\bm q} \in {\cal C}_{free} \, | \, {\bm q} \not \in 
\cup_{{\bm m} \in M} {\cal S}({\bm m})\}). \]
Its expected value is:
\[ E[H] = \int_{{\bm q} \in {\cal C}_{free}} {\rm Pr}[{\bm q} \not \in 
\cup_{{\bm m} \in M} {\cal S}({\bm m})] d{\bm q}. \]
The $\epsilon$-goodness of the free space entails that the probability
that any given configuration is not visible from any of the $s$
milestones is at most $(1-\epsilon)^s$. Thus:
\begin{equation}\label{eq:vol}
E[H] \leq \mu({\cal C}_{free}) (1-\epsilon)^s \leq \mu({\cal C}_{free})
\epsilon \beta/2.
\end{equation}
Given a random variable $X$ assuming only non-negative values, the
Markov inequality~(Motwani and Raghavan 1995):
\[ {\rm Pr}[X \geq x] \leq E[X]/x \] 
holds for all $x \in \RR^+$. Using this inequality and the
relation~(\ref{eq:vol}), we get:
\[ {\rm Pr}[H \geq (\epsilon/2) \mu({\cal C}_{free})] \leq \beta. \]
Hence, with probability $1-\beta$, $H$ is at most
$(\epsilon/2)\mu({\cal C}_{free})$, in which case $M$ is adequate.

\subsubsection*{B.~~Proof of Theorem 2}

Assume an adequate set of milestones.  For any ${\bm q} \in {\cal
C}_{free}$, the volume of the subset of ${\cal S}({\bm q})$ visible
from some milestone is at least:
\[ \mu({\cal S}({\bm q})) - (\epsilon/2)
\mu({\cal C}_{free}) \geq (\epsilon/2) \mu({\cal
C}_{free}). \]
Therefore, for either query configuration ${\bm q}_i$ ($i
\in \{{\rm init},{\rm goal}\}$), the probability that a random
configuration chosen from ${\cal S}({\bm q}_i)$ is not visible from
any milestone is at most $1/2$. The probability that {\tt
query-processing} fails to connect ${\bm q}_i$ to a milestone on
$\log(2/\gamma)$ trials at Step 1(b)i is thus less than
$\gamma/2$. Since Step1(b)i is performed for both query
configurations, the overall failure probability is at most $\gamma$.

\subsubsection*{C.~~Proof of Theorem 7}

We assume the existence of a path $\tau : \ell \in [0,L] \mapsto
\tau(\ell) \in {\cal C}_{free}$ connecting ${\bm q}_{init}$ to ${\bm
q}_{goal}$, where $\ell$ stands for the arc length from ${\bm
q}_{init}$. For simplicity, let $\xi$ (instead of $\xi_{inf}$)
designate the infimum of the Euclidean distance between $\tau(\ell)$
and the free space boundary, when $\ell$ spans the interval $[0,1]$.
Given any two configurations ${\bm q} = \tau(\ell)$ and ${\bm
q}^\prime = \tau(\ell^\prime)$ on $\tau$, let $l({\bm q},{\bm
q}^\prime)$ denote the path length $|\ell - \ell^\prime|$.  

Let ${\cal B}_r(x)$ designate the ball of radius $r$ centered at $x
\in \RR^n$.  We pick $k = \lceil 2 L / \xi \rceil$ configurations on
$\tau$, denoted by ${\bm q}_0 = {\bm q}_{init}, {\bm q}_1,\dots,{\bm
q}_k = {\bm q}_{goal}$, such that $l({\bm q}_i,{\bm q}_{i+1}) \leq
\xi/2$, for all $i \in [0,k-1]$. We have that:
\[ {\cal B}_{\xi/2}({\bm q}_{i+1}) \subset 
{\cal B}_\xi({\bm q}_i). \] For any two points $p_i \in {\cal
B}_{\xi/2}({\bm q}_i)$ and $p_{i+1} \in {\cal B}_{\xi/2}({\bm
q}_{i+1})$, the straight-line segment connecting $p_i$ and $p_{i+1}$
lies entirely in ${\cal C}_{free}$; indeed, the above relation implies
that $p_{i+1}$ also lies in ${\cal B}_\xi({\bm q}_i)$. So, a
sufficient condition for the query-processing algorithm to find a path
is that each ball ${\cal B}_{\xi/2}({\bm q}_i)$, $i = 1,\dots,k-1$
contains at least one milestone. The probability that a ball of radius
$r$ lying entirely in the free space contains none of the $s$
milestones is $(1 - \mu({\cal B}_r)/\mu({\cal C}_{free}))^s$.  In
$\RR^n$ we have $\mu({\cal B}_r) = r^n \mu({\cal B}_1)$.  Therefore,
the probability that the planner does not find a path is at most:
\[ \left(\lceil \frac{2 L}{\xi} \rceil - 1
\right) \left(1 - \frac{\mu({\cal B}_{\xi/2})}{\mu({\cal C}_{free})}
\right)^s, \]
which is itself no greater than:
\[ \frac{2L}{\xi}\left(1 - 2^{-n}\frac{\mu({\cal B}_1)}{\mu({\cal
C}_{free})} \xi^n \right)^s. \]
Hence, choosing $s$ such that the above quantity is at most
$\alpha \in (0,1]$ guarantees that the planner will find a
path with probability at least $1-\alpha$.

\newpage

\vspace*{0.3in}

\begin{center}

{\bf \LARGE Figure Captions}

\end{center}

\vspace*{0.5in}

Figure 1: Illustrative example

\vspace{0.5in}

Figure 2: Robot arm example

\end{document}