Robotics and Motion Planning

Spring 2002

Instructor: Dan Halperin
Tuesday 16--19, Schreiber 008
Office hours: Wednesday, 16--17, Schreiber 219

Teaching Assistant: Eran Leiserowitz (~leiserow)

Office hours: Monday, 16--17, Geometry lab, Schreiber (please mail in advance)

The course will cover computational and algorithmic aspects of robotics with an emphasis on the algorithmics of motion. It will consist of the following three sections:

I. Robot arms
The basics of classical robotics: object representation and spatial transformations, the Denavit-Hartenberg kinematic model, direct and inverse kinematics, trajectory planning

II. Motion planning
The fundamental motion planning problem, configuration space and obstacle representation, exact solutions (Minkowski sums, cell decomposition, roadmaps), practical methods (potential field, probabilistic roadmaps), applications, variants and extensions

III. Additional topics
As time permits: manipulation of kinematic chains with many degrees of freedom (applicable to modular robots and to molecular simulation), assembly planning, part orienting

The course is geared towards graduate students in computer science. Third-year undergrads are welcome.

Prerequisites: data structures, a course on algorithms.
Having taken an advanced programming course or the course Computational Geometry is an advantage but not a requirement.
If you haven't studied Computational Geometry, click here for helpful material.


The final grade will be determined by homework assignments and a final exam.

Demonstration of rotating frames


Assignment no. 1: ps file, pdf file, and information on input/output and frame programs (the TA's site)


Assignment no. 2: ps file, pdf file, and information on input/output and frame program (the TA's site)

Assignment no. 3: ps file, pdf file; and information on input/output and frame program (the TA's site)

Assignment no. 4: ps file, pdf file; and information on input/output and frame program (the TA's site)

Course outline

Introduction (Latombe, Chapter 1 and more)

Introduction cont'd
Spatial descriptions and transformations (Craig, Chapter 2)
Demonstration of rotating frames

Kinematic modeling, the DH parameters, and inverse kinematic solving (Craig, Chapters 3,4)

Motion planning with 2 DOFs: a general solution; the arrangement of constraint curves
Minkowski sums; the case of a convex polygon translating among polygonal obstacles (de Berg et al, Chapter 13)

Minkowski sums, cont'd (de Berg et al, Chapter 13)
Davenport-Schinzel sequences, introduction (Sharir-Agarwal, see bibliography , Chapter 1)

Davenport-Schinzel sequences, cont'd
the complexity of a single face (Sharir-Agarwal, Section 5.2)
The Piano Movers I (Schwartz-Sharir): a segment translating and rotating among polygonal obstacles (Latombe, Chapter 5)

The Piano Movers I, cont'd
The general motion planning problem with 3 DOFs, introduction

The Piano Movers II (speaker: Micha Sharir)
Solving the general motion planning problem using cell decomposition
Schwartz and Sharir, On the Piano movers Problem II: General techniques for computing topological properties of algebraic manifolds, Advances in Applied Mathematics, vol 4, pp. 298-351, 1983.
A brief summary appears in Latombe's book, Chapter 5, Section 3.

Probabilistic Road Maps (speaker: Shai Hirsch)
Slides of Shai's presentation (some borrowed from Latombe)

Assembly planning and separability
A few separation problems and their solution/hardness (Section 8.7 in Computational Geometry in C, J. O'Rourke, Cambridge, 2nd Edition).
Monotone 2-handed assembly planning (D. Halperin, J.-C. Latombe and R.H. Wilson, A general framework for assembly planning: The motion space approach, Algorithmica 26 (2000), 577--601).

Assembly planning cont'd
Infinitessimal partitioning (L.J. Guibas, D. Halperin, H. Hirukawa, J.-C. Latombe and R.H. Wilson Polyhedral assembly partitioning using maximally covered cells in arrangements of convex polytopes Int. J. of Computational Geometry and its applications, 8(2), 1998, 179--199.)

Solution to selected exercises: Ex 2.1 - the 2nd arm, Ex 2.5, Ex 3.1


Solution to Ex 2.5 cont'd

Dynamic maintenance and self-collision testing for large kinematic chains
Paper (Lotan, Schwarzer, Halperin, Latombe), gzipped ps file

Last update: July 22, 2002