Close this search box.

Motion Planning, Seminar, Fall 2003–2004



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.)

  1. Basic terminology and tools in motion planning, and
  2. a demonstration of a PRM implementation for a multi-link planar robot arm moving among polygonal obstacles


  • 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]

  • 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]

  • 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
  • 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
  • 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

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)
  • 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]

  • 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]

  • 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


  • 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,
  • 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)

Yair Oz - Webcreator


Skip to content