|
|
Single-Query Randomized Path Planning
Overview
Motion planning
is concerned with computing collision-free motion for moving objects
(e.g., drug molecules inside the binding cavity of a protein,
robot manipulators on an assembly line, or articulated models of human
arms) in an environment populated with obstacles.
The key difficulty of motion planning is its exponential dependence on the
number of degrees of freedom of a moving object.
The focus of this work is to use random sampling as a fundamental technique
for attacking this issue.
Path
Planning
In its
simplest form, motion planning is a purely geometric problem: given a description
of an object and a static environment, the goal is to find a collision-free
path to move the object from an initial to a goal configuration. Simple
as it may appear, a fast path-planning algorithm
is directly useful for applications
such as computer animation and virtual
prototyping.
The algorithm that
we have develped first samples in the neighborhoods of the initial and
the goal configuration and then iteratively in the neighborhoods of the
newly-sampled configurations, until a path is found. Extensive experimetal
results indicate that our algorithm is simple to implement and very efficient
in practice. The images below show the results on some of the expriments
that we have performed.
Expansive
Spaces
The analysis
of randomized motion planning algorithm
is an interesting and difficult question. If there exists
a path, does the algorithm always find it? The intuitive explanation for
the observed success of randomized motion planning algorithms
is that a small number of sampled
points can effectively capture the connectivity of the environment. We
have introduced the notion of expansiveness
to characterize the complexity of the environment. We have proven that
in an expansive space, our algorithm quickly finds a collision-free
path with high probability, if one exists.
References
- J. Basch, L.J. Guibas, D. Hsu, and A.T. Nguyen. Disconnection proofs for motion planning. In Proc. IEEE Int. Conf.
on Robotics & Automation, pp. 1765–1772, 2001.
BibTeX PDF
- D. Hsu. Randomized Single-query Motion Planning in Expansive Spaces. Ph.D. Thesis, Dept. of Computer Science, Stanford
University, Stanford, CA, 2000.
BibTeX
PDF
- D. Hsu, J.C. Latombe, R. Motwani, and L.E. Kavraki. Capturing the connectivity of high-dimensional geometric spaces by parallelizable random sampling techniques. In P.M. Pardalos and S. Rajasekaran, editors, Advances
in randomized parallel computing, pp. 159–182, Kluwer Academic Publishers, Boston, MA, 1999.
BibTeX PDF
- D. Hsu, J.C. Latombe, and R. Motwani. Path planning in expansive configuration spaces. Int. J. Computational Geometry
& Applications, 9(4-5):495–512, 1999.
BibTeX
PDF
- D. Hsu, L.E. Kavraki, J.C. Latombe, R. Motwani, and S. Sorkin. On finding narrow passages with probabilistic roadmap planners. In P.K. Agarwal and others, editors, Robotics: The Algorithmic Perspective: 1998 Workshop on
the Algorithmic Foundations of Robotics, pp. 141–154, A. K. Peters, Wellesley, MA, 1998.
BibTeX PDF
People
Acknowledgement We thank Nancy Amato at Texas A&M
University and Boris Yamrom at General Electric Corporation for providing
us the data used in some of the experiments shown above. |
