Seminar
0368445901
Lecture: Wednesday, 17:00–19:00, Kaplun 324 <- note change of room
Instructor: Dan Halperin
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.)
- Basic terminology and tools in motion planning, and
- a demonstration of a PRM implementation for a multi-link planar robot arm moving among polygonal obstacles
PRM
- 12.11.03 (PRM1) Ron Wein
- Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M., IEEE Transactions on Robotics and Automation, 12(4):566–580, 1996 - Analysis of Probabilistic Roadmaps for Path Planning
Kavraki, L. E., Kolountzakis, M., and Latombe, J.-C., In Proceedings of The 1996 International Conference on Robotics and Automation (ICRA), pp. 3020–3026, Minneapolis, MN, 1996
slides [zipped ppt]
- Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces
- 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 - Guarding galleries with no bad points
P. Valtr, Discrete Computational Geometry, 21:193–200, 1999
slides [zipped ppt]
- Path Planning in Expansive Configuration Spaces
- 26.11.03 (PRM3) Anat Rapoport
- The Gaussian Sampling Strategy for Probabilistic Roadmap Planners
Boor, V., Overmars, M.H. & Stappen, A.F. van der (1999), In Proceedings of the 1999 IEEE International Conference on Robotics & Automation, pp. 1018–1023 - On Finding Narrow Passages with Probabilistic Roadmap Planners
Hsu, D., Kavraki, L. E., Latombe, J.-C., Motwani, R., and Sorkin, S. In Robotics: The algorithmic perspective, pp. 141-D-153, A.K. Peters, Natick, MA, 1998
In 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, In Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR), March 1998, pp. 155–168 - A Comparative Study of Probabilistic Roadmap Planners
Roland Geraerts, Mark H. Overmars,, Technical Report Utrecht University, UU-CS-2002-041
- The Gaussian Sampling Strategy for Probabilistic Roadmap Planners
- 3.12.03 (PRM4) Dror Lupu
- Rapidly-exploring random trees: Progress and prospects
S. M. LaValle and J. J. Kuffner, 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 - An efficient approach to single-query path planning
J. J. Kuffner and S. M. LaValle, RRT-connect, In Proceedings of the IEEE International Conference on Robotics and Automation, pages 995–1001, 2000
- Rapidly-exploring random trees: Progress and prospects
- 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, In 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
- A Path Planning-Based Study of Protein Folding Pathways with a Case Study of Hairpin Formation in Protein
Collision detection
- 17.12.03 (CD1) Eran Eyal
- A fast algorithm for incremental distance calculation
Lin, M. C., Canny, J., In Proceedings of the IEEE ICRA, 1991: 266–275 - A hierarchical method for real-time distance computation among moving convex bodies
Leonidas J. Guibas, David Hsu, Li Zhang, Computational Geometry 15(1-3): 51–68 (2000)
- A fast algorithm for incremental distance calculation
- 24.12.03 (CD2) Efi Fogel
- A fast procedure for computing the distance between complex objects in three-dimensional space
Gilbert, E. G., Johnson, D. W., Keerthi, S. S., IEEE Journal Robotics and Automation, 1988, 4(2): 193–203 - Enhancing GJK: computing minimum and penetration distance between convex polyhedra
Cameron, S. A., In Proceedings of the IEEE ICRA, 3112–3117, 1997
slides [pdf]
- A fast procedure for computing the distance between complex objects in three-dimensional space
- 31.12.03 (CD3) Idit Haran
- Computing the Intersection-Depth of Polyhedra
David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri, Algorithmica 9(6): 518–533 (1993)
slides [zipped ppt]
- Computing the Intersection-Depth of Polyhedra
- 7.1.04 (CD4) Alan Lerner + Eitan Fitusi
- OBB-Tree: A hierarchical structure for rapid interference detection
S. Gottschalk, M. Lin, and D. Manocha, In Proceedings of Computer Graphics (SIGGRAPH), pages 171–180, 1996 - Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs
J. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan, IEEE Transactions on Visualization and Computer Graphics, March 1998, Volume 4, Number 1
- OBB-Tree: A hierarchical structure for rapid interference detection
Exact/Hybrid
- 14.1.04 no meeting
- 21.1.04 double feature (till 20:00)
(EH1) Dror Alani- Moving a Disc Between Polygons
Hans Rohnert, Algorithmica 6(2): 182–191 (1991) - A “Retraction” Method for Planning the Motion of a Disc
Colm Ó’Dúnlaing, Chee-Keng Yap, Journal Algorithms 6(1): 104–111 (1985) - Moving a disc between polygons (VIDEO)
Stefan Schirra, In Proceedings of the 9th ACM Symposium on Computational Geometry (SoCG), San Diego, pages 395–396 (1993)
(EH2) Svetlana Olonetsky + Dina Dushnik
- Polygon decomposition for efficient construction of Minkowski sums
P.K. Agarwal, E. Flato and D. Halperin, Computational Geometry: Theory and Applications, vol. 21, 39–61 (2002)
Special Issue, selected papers from the European Workshop on Computational Geometry, Eilat, 2000,
- Moving a Disc Between Polygons
- 28.1.04 (EH3) Yael Eisenthal + Eran Shalom
- Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane
S. Hirsch and D. Halperin, In Proceedings of the 5th Workshop on Algorithmic Foundations of Robotics (WAFR), Nice, 2002, 225–241 (2002)
- Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane