Teaching Assistant: Eran Leiserowitz (~leiserow)
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)
12.3.02
Introduction (Latombe, Chapter 1 and more)
19.3.02
Introduction cont'd
Spatial descriptions and transformations (Craig, Chapter 2)
Demonstration of rotating frames
9.4.02
Kinematic modeling, the DH parameters, and inverse kinematic solving
(Craig, Chapters 3,4)
23.4.02
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)
30.4.02
Minkowski sums, cont'd (de Berg et al, Chapter 13)
Davenport-Schinzel sequences, introduction (Sharir-Agarwal, see
bibliography , Chapter 1)
7.5.02
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)
14.5.02
The Piano Movers I, cont'd
The general motion planning problem with 3 DOFs, introduction
21.5.02
The Piano Movers II (speaker: Micha Sharir)
Solving the general motion planning problem using cell
decomposition
References:
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.
28.5.02
Probabilistic Road Maps (speaker: Shai Hirsch)
Slides of Shai's presentation (some borrowed from Latombe)
11.6.02
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).
18.6.02
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
25.6.02
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