Algorithmic Robotics and Motion Planning


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 motionspace 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 Voronoivisibility 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 largescale 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)
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.
Cobstacles 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 planecan 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), 3961, 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
Samplingbased 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 singlequery 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), 577601, 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, 179199.
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
visibilityVoronoi complex and its applications
Computational Geometry: Theory and Applications, 36 (1) 2007, pp. 6687.
(2) R. Wein, J.P. van
den Berg, and D. Halperin
Planning nearoptimal 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) 510528.
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, 902932.
THE END