SADNA in Motion Planning
Spring 2003


[Minkowski Sums]

Instructor: Dan Halperin
Tuesday 16-18, Shenkar 114
Office hours: Tuesday 15-16, Schreiber 219

Teaching Assistant: Efi Fogel

The assignment in this workshop is to plan a collision free motion for a robot moving in an environment cluttered with obstacles. Several problems will be proposed as well as different solution approaches. The project software should include an interactive graphic environment for input and simulation of the planning algorithms.

Possible projects:

 coordinating the motion of two (or more) discs moving among obstacles in the plane
 planning the motion of a multi-link planar robot moving among obstacles
 self-collision testing for robots with many degrees of freedom

The following two books contain useful material for the workshop:

 J.-C. Latombe,
Robot Motion Planning
Kluwer Academic Publishers, 1991.
 M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications

Springer, 1997. 2nd rev. edition, 2000.

The following paper is a good starting point for randomized path planning: A Random Sampling Scheme for Path Planning , by J. Barraquand, L.E. Kavraki, J.C. Latombe, T.Y. Li, R. Motwani, and P. Raghavan. International Journal of Robotics Research, 16(6):759-774, 1997

The submission of the project is in two steps:

1. July 30th, 2003: prototype and its user manual (students are strongly encouraged to submit the prototype earlier than this deadline to allow for more time toward the final submission)
2. August 30th, 2003: submission of the full project, including full user manual and programming guide

Meetings during the semester:

 18/2/2003 and 25/2: presentation of problems, techniques, and projects
 4/3: demonstration of helpful software tools; forming teams
 11/3, 17:00-18:00: the robotics lab (Schreiber floor -1): "office hours" on software tools; more details will be announced
 8/4 : presentation of project proposals (oral and in writing), each team has to give a 15 minute presentation

Last update: 17 Feb 2003