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

**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 7*, January 2003, pages 240–251^{th}Pacific Symposium on Biocomputing (PSB)**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 6*(RECOMB), April 2002, pages 2–11^{th}International Conference on Computational Molecular Biology

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

### 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 9*, San Diego, pages 395–396 (1993)^{th}ACM Symposium on Computational Geometry (SoCG)

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