Algorithmic Robotics and Motion Planning Fall 2006-7 (0368.4010.01) Instructor: Dan Halperin Monday 16-19, Schreiber 8 Office hours: Monday 19-20, Schreiber 219 Teaching assistant: Ophir Setter Meeting by appointment

The course will cover computational and algorithmic aspects of robotics with an emphasis on the algorithmics of motion.

The topics that will be covered include (as time permits):
a brief tour of algorithmic problems in robotics
the configuration space approach and the connection between motion planning and geometric arrangements
Minkowski sums; exact and efficient solution to translational motion planning in the plane
translation and rotation in the plane; translational motion of polyhedra in space
collision detection
probabilistic solutions: probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT)
hybrid motion planning: combining probabilistic methods and exact arrangements
assembly planning and movable separability problems
the motion-space approach to assembly planning; objects that can(not) be taken apart with two hands
path quality: shortest paths, high clearance paths
tradeoff between path length and clearance I: the Voronoi-visibility diagram
tradeoff between path length and clearance II: corridor planning
direct and inverse kinematics: from industrial manipulators to proteins
dynamic maintenance of large kinematics structures
sensorless manipulation design

Prerequisites: Computational Geometry. Knowledge of C++ or willingness to learn the language.

The final grade will be determined by homework assignments including one large-scale assignment, and a final oral exam on the contents of the course and the assignments. It is possible to work and submit the assignments in pairs.
Click here to read more on the course's requirement.

Assignment no. 1: pdf file, and more information on Exercise~1.1 (the TA's site)

Assignment no. 2, the complete version: pdf file and more information on Exercise~2.3 (the TA's site)

Assignment no. 3: pdf file and more information on Exercise~3.3 (the TA's site)

Course summary

A brief summary of the material covered in class will appear here after the lesson. This should not be taken as the complete course syllabus, but is meant to give students who missed a class what were the main topics discussed.

23.10.2006
Review of the topics to be covered in the course. Terminology. C-obstacles in planar translation. Computing the Minkowski sum of two convex polygons. The basic motion planning problem and its variants. Assembly planning problems. Basic problems in robot kinematics.
ppt slides of the overview, the abridged version

30.10.2006
Basic terminology and general results in motion planning: ppt slides
Introduction to arrangements and their relation to motion planning pdf slides
The discussion of arrangements of lines and their construction appears in Chapter 8 of the Computational Geometry book by de Berg et al--- see the course's bibiliograhy
The complexity of the free space of a disc moving among discs in the plane: a note in pdf

6.11.2006
The complexity of the free space of a convex polygon translating among polygonal obstacles in the plane---can be found in Section 13.3 in the Computational Geometry book by de Berg et al--- see the course's bibiliograhy
The practice of computing exact Minkowski sums in the plane: ppt slides .This part is based on two papers: (1) .K. Agarwal, E. Flato and D. Halperin, Polygon decomposition for efficient construction of Minkowski sums, Computational Geometry: Theory and Applications, vol. 21 (2002), 39-61, and (2) R. Wein, Robust and efficient construction of planar Minkowski sums and offset polygons, a manuscript, 2006.

13.11.2006
Offsetting polygons; see the last part of the ppt slides presented by Ron Wein last week.
Motion planning for a rod translating and rotating among polygonal obstacles in the plane. We will see the solution by Schwartz and Sharir from their famous 1983 paper "On the piano movers' problem I". Latombe gives a friendly presentation of the algorithm in Section 5.2 of his book--- see the course's bibiliograhy.
Exact Minkowski Sums and Applications, the video, mpg file

20.11.2006
The plan:
Continuing with the presentation of the Piano Movers I algorithm for a rod moving among polygonal obstacles in the plane.
A survey by Efi Fogel: Part I, on generic programming and the STL, , and Part II, CGAL.

27.11.2006
Completing (at last) the presentation of the Piano Movers I algorithm for a rod moving among polygonal obstacles in the plane. A lower bound of $\Omega(n^5)$ on the size of the connectivity graph.
Minkowski sums of convex polyhedra: structure, complexity, and algorithms; presentation by Efi Fogel. More details can be found in the following paper: E. Fogel and D. Halperin Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications , ALENEX 2006, Miami, Florida, 2006.
Click here to see also the accompanying video.
Brief presentation of the paper: C. Detweiler, J. Leonard, D. Rus, and S. Teller Passive Mobile Robot Localization within a Fixed Beacon Field , The Seventh WAFR (International Workshop on the Algorithmic Foundations of Robotics) 2006, NY, NY.

4.12.2006
Sampling-based motion planning. The lesson was mostly dedicated to covering the material of Chapter 7 in the book by Choset et al--- see the course's bibiliograhy.
We also followed parts of Latombe's presentation Sampling and Connection Strategies for PRM Planners (ppt).
For more information on collision detection, see the survey by Lin and Manocha. The reference is in the course's bibiliograhy.
For more information on single-query planners, sampling and distance functions, see the book Planning Algorithms by LaValle.

11.12.2006
Assembly planning, moveable separability, and motion space.
Section 8.7, separability , of J. O'Rourke's book "Computational Geometry in C"
And material from the papers:
(1) D. Halperin,J.-C. Latombe and R.H. Wilson
A general framework for assembly planning: The motion space approach
Algorithmica , 26 (2000), 577--601, and
We also started with (2) 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.

18.12.2006
Completing the assembly planning algorithm for infinitesimal motions. The paper in pdf format can now be conveniently downloaded and printed; thanks to Boris Kozo for that.

25.12.2006
Path quality.
The visibility diagram and shortest paths. Chapter 15 in the Computational Geometry book by de Berg et al--- see the course's bibiliograhy.
An extensive review of shortest paths can be found in the Chapter by Mitchell in the Handbook of Discrete and Computational Geometry--- see the course's bibiliograhy.
Tradeoffs between path length and clearance. Ron Wein presented results from the following two papers (and here are also ppt slides of Ron's talk) :
(1) R. Wein, J.P. van den Berg, and D. Halperin
The visibility-Voronoi complex and its applications
Computational Geometry: Theory and Applications, 36 (1) 2007, pp. 66-87.
(2) R. Wein, J.P. van den Berg, and D. Halperin
Planning near-optimal corridors amidst obstacles
Proc. 7th International Workshop on the Algorithmic Foundations of Robotics, New York City, July 2006.

1.1.2007 Happy new year!
Kinematics: from robot manipulators to proteins. Talks by Denis Sieradzki.
A good introduction to manipulator kinematics can be found in Chapters 3 and 4 of Craig's book--- see the course's bibiliograhy.

8.1.2007
Kinematics continued.
A kinematic view of loop closure. From the paper: E. A. Coutsias, C. Seok, M. P. Jacobson and K. E. Dill, A kinematic view of loop closure, J. Comput. Chem. 25 (2004) 510-528.

17.1.2007 The plan:
Dynamic maintenance of large kinematics structures.
Mostly material from the following paper: I. Lotan, F. Schwarzer, D. Halperin and J.-C. Latombe
Algorithm and data structures for efficient energy maintenance during Monte Carlo simulation of proteins
Journal of Computational Biology 11 (5), 2004, 902-932.

THE END