Motion Planning

Seminar, Fall 2003-04


Instructor: Dan Halperin

Wednesday, 17:00-19:00
Kaplun 324 <- note change of room

The goal of the seminar is to get the audience acquainted with state-of-the-art practical techniques in motion planning. Let B be a robot system (a rigid body, or a collection of bodies) moving in an environment with obstacles. In the basic motion-planning problem we are given a start and goal position for B, we have to decide whether a collision-free motion for the robot from start to goal exists and if so to plan such a motion. The basic problem has numerous variants and many applications. While originally the algorithmic study of motion planning was mainly theoretical, in recent years there is an ever growing body of practical work and implemented motion-planning software systems.

The most widely used practical methods are the so-called Probabilistic Road Map (PRM) methods. These will be the topic of the first part of the seminar. The second part will deal with a crucial ingredient of PRM, which is interesting in its own right: (typically static) collision detection. We will also discuss exact methods for motion planning and their combination with PRM techniques. The seminar is in the spirit of the European MOVIE project whose goal is to improve current motion-planning techniques in solvability, efficiency and path quality.

The seminar will start with two introductory meetings, followed in subsequent weeks by student presentations.

 29.10.03 Introduction I (D.H.)
The basic motion-planning problem, a brief history of its study, variants of motion planning, and a survey of the papers that will be presented in the seminar.

 5.11.03 Introduction II (D.H.)
(i) Basic terminology and tools in motion planning, and (ii) a demonstration of a PRM implementation for a multi-link planar robot arm moving among polygonal obstacles.


 12.11.03 (PRM1) Ron Wein

slides, zipped power point

Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces. IEEE Transactions on Robotics and Automation, 12(4):566--580, 1996.

Kavraki, L. E., Kolountzakis, M., and Latombe, J.-C.. Analysis of Probabilistic Roadmaps for Path Planning. In Proceeedings of The 1996 International Conference on Robotics and Automation (ICRA 1996), pp. 3020--3026, Minneapolis, MN, 1996.

 19.11.03 (PRM2) Shimon Sofer

Path Planning in Expansive Configuration Spaces. D. Hsu, J.C. Latombe, and R. Motwani. International Journal of Computational Geometry and Applications, 9(4-5):495-512, 1999.

P. Valtr. Guarding galleries with no bad opints. Discrete Comput. Geom., 21:193--200, 1999.

slides, zipped power point

 26.11.03 (PRM3) Anat Rapoport

Boor, V., Overmars, M.H. & Stappen, A.F. van der (1999). The Gaussian Sampling Strategy for Probabilistic Roadmap Planners. In -- (Ed.), Proceedings of the 1999 IEEE International Conference on Robotics & Automation. (pp. 1018-1023).

Hsu, D., Kavraki, L. E., Latombe, J.-C., Motwani, R., and Sorkin, S. On Finding Narrow Passages with Probabilistic Roadmap Planners. In Robotics: The algorithmic perspective, pp. 141-D-153, A.K. Peters, Natick, MA, 1998. Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics, Houston, TX, 1998

OBPRM: An Obstacle-Based PRM for 3D Workspaces, Nancy M. Amato, O. Burchan Bayazit, Lucia K. Dale, Chris Jones, Daniel Vallejo, Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR'98), March 1998, pp. 155-168.

Roland Geraerts, Mark H. Overmars, A Comparative Study of Probabilistic Roadmap Planners, Technical Report Utrecht University, UU-CS-2002-041.

 3.12.03 (PRM4) Dror Lupu

S. M. LaValle and J. J. Kuffner. Rapidly-exploring random trees: Progress and prospects. In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, pages 293-308. A K Peters, Wellesley, MA, 2001.

J. J. Kuffner and S. M. LaValle. RRT-connect: An efficient approach to single-query path planning. In Proc. IEEE Int'l Conf. on Robotics and Automation, pages 995--1001, 2000.

 10.12.03 (PRM5) Angela Enosh

A Path Planning-Based Study of Protein Folding Pathways with a Case Study of Hairpin Formation in Protein G and L, Guang Song, Shawna Thomas, Ken A. Dill, J. Martin Scholtz, and Nancy M. Amato, Proceedings of 7th Pacific Symposium on Biocomputing (PSB), January 2003, pages 240-251.

Using Motion Planning to Map Protein Folding Landscapes and Analyze Folding Kinetics of Known Native Structures , Nancy M. Amato, Ken A. Dill, and Guang Song, Journal of Computational Biology, 10(3), 2003, pp. 239-255. Preliminary version appeared in Proceedings of the 6th International Conference on Computational Molecular Biology (RECOMB), April 2002, pages 2-11.

Collision detection

 17.12.03 (CD1) Eran Eyal

Lin, M. C., Canny, J., A fast algorithm for incremental distance calculation, Proceedings of IEEE ICRA, 1991: 266-275.

Leonidas J. Guibas, David Hsu, Li Zhang: A hierarchical method for real-time distance computation among moving convex bodies. Computational Geometry 15(1-3): 51-68 (2000)

 24.12.03 (CD2) Efi Fogel

Gilbert, E. G., Johnson, D. W., Keerthi, S. S., A fast procedure for computing the distance between complex objects in three-dimensional space, IEEE J. Robotics and Automation, 1988, 4(2): 193-203.

Cameron, S. A., Enhancing GJK: computing minimum and penetration distance between convex polyhedra, Proceedings of IEEE ICRA, 1997: 3112-3117.

slides, pdf

 31.12.03 (CD3) Idit Haran

David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri: Computing the Intersection-Depth of Polyhedra. Algorithmica 9(6): 518-533 (1993)

slides, zipped power point

 7.1.04 (CD4) Alan Lerner + Eitan Fitusi

S. Gottschalk, M. Lin, and D. Manocha. OBB-Tree: A hierarchical structure for rapid interference detection. In Computer Graphics (SIGGRAPH '96 Proceedings), pages 171--180, 1996.

J. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan: Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, March 1998, Volume 4, Number 1.


 14.1.04 no meeting

 21.1.04 double feature (till 20:00)

(EH1) Dror Alani

Hans Rohnert: Moving a Disc Between Polygons. Algorithmica 6(2): 182-191 (1991)

Colm Ó'Dúnlaing, Chee-Keng Yap: A "Retraction" Method for Planning the Motion of a Disc. J. Algorithms 6(1): 104-111 (1985)

Moving a disc between polygons - VIDEO, Stefan Schirra, In: Proceedings of the 9th ACM Symposium on Computational Geometry (SoCG93), San Diego, 1993, pages 395-396

(EH2) Svetlana Olonetsky + Dina Dushnik

P.K. Agarwal, E. Flato and D. Halperin, Polygon decomposition for efficient construction of Minkowski sums, Computational Geometry: Theory and Applications, Special Issue, selected papers from the European Workshop on Computational Geometry, Eilat, 2000, vol. 21 (2002), 39-61.

 28.1.04 (EH3) Yael Eisenthal + Eran Shalom

S. Hirsch and D. Halperin, Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane, Proc. 5th Workshop on Algorithmic Foundations of Robotics (WAFR), Nice, 2002, 225-241.