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 developed 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 experimental results indicate that our algorithm is simple to implement and very efficient in practice. The images below show the results on some of the experiments that we have performed.
 |
 |
Quicktime movie (2.3 MB).
Download the Quicktime viewer
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.
PDF - D. Hsu. Randomized Single-query Motion Planning in Expansive Spaces. Ph.D. Thesis, Dept. of Computer Science, Stanford University, Stanford, CA, 2000.
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.
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.
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.
PDF
People
Acknowledgements
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.