Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Spring 2011
« March 2017 »
Log in

Forgot your password?

Algorithmic Robotics and Motion Planning

Multi Robot Multi Robot Configuration Space

Spring 2011


Course hours: Monday, 16:00-19:00
Location: Schreiber 06

Instructor: Dan Halperin, danha AT post tau ac il

Office hours: Monday, 19:00-20:00

Teaching Assistant: Kiril Solovey
Meeting by appointment


The last decade has seen an outburst of new robotic applications and robot designs in medicine, entertainment, security and manufacturing to mention just a few areas. Novel applications require ever more sophisticated algorithms. In the course, we shall cover computational and algorithmic aspects of robotics with an emphasis on motion planning.

The motion-planning problem is a key problem in robotics. The goal is to plan a valid motion path for a robot (or any other mobile object for that matter) within a given environment, while avoiding collision with obstacles. The scope of the motion-planning problem is not restricted to robotics, and it arises naturally in different and diverse domains, including molecular biology, computer graphics, computer-aided design and industrial automation. Moreover, techniques that were originally developed to solve motion-planning problems have often found manifold applications.

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
 Sampling-based motion planning
 Coordinating the motion of multiple robots
 Path quality: shortest paths, high clearance paths, and other quality measures
 Direct and inverse kinematics: from industrial manipulators to proteins
 Dynamic maintenance of large kinematics structures
 Algorithmic automation I: sensorless manipulation design
 Algorithmic automation II: assembly planning

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

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 multiple-choice exam on the contents of the course and the assignments.


Assignment no.1: pdf and more information on Exercise 1.1,3.

Assignment no.2: pdf and more information on Exercise 2.3,4.

Assignment no.3: pdf and more information on Exercise 3.2,3.
Hint for Exercise 3.1.

Assignment no.4 (fully optional): pdf.

Assignment E (fully optional): pdf

A short bibliography: books and surveys

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 an idea about the main topics discussed.
Review of the topics to be covered in the course.
Terminology. C-obstacles in planar translation.  The basic
motion planning problem and its variants. Assembly planning
problems. Basic problems in robot kinematics. A separation
sequence for convex polygons in the always exist and in any
Basic terminology and general results in motion planning.
Introduction to arrangements and their relation to motion
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 bibliography. Lecture slides [pdf]
The complexity of the free space of a disc moving among 
discs in the plane, a note [pdf].
A brief introduction to Generic programming and CGAL [generic programming, CGAL, handouts].
Minkowski sum definition, complexity, construction, and application [slides, handouts].
The structure and complexity of the problem of
moving and L-shaped robot among point obstacles.
Very briefly we give an overview of the single-cell
complexity result of arrangements of well-behaved curves
and surfaces and its implication to motion planning.
The main part of the lesson:
Motion planning for a rod translating and rotating among
polygonal obstacles in the plane. We started presenting 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 bibiliography.
Motion planning for a rod translating and rotating among
polygonal obstacles in the plane.
We completed the descirption and anlysis of the algorithm.
Collision detection and proximity queries [handouts]

Collision detection and proximity queries, till the end of the presentation
(see previous week)
Introduction to sampling-based planning, PRM.
Based on Chapter 7 in he book by Choset et al--see the course bibliography.

  29/04/11 (instead of 2/5)

Introduction to sampling-based planning, continued:
PRM, probabilistic completeness, BiRRT [handout_prm, handout_birrt].


Introduction to robot arm kinematics. Craig's book, Chaoters 2 (spatial descritpion and transformations), 3 (forward kinematics, Denait-Hartenberg representation) and 4 (inverse kinematics). 


The ChainTree structure for handling long kinematic chains. Lecture by Itay Lotan [handouts].


Path quality [handouts].


Motion planning via manifold samples. Lecture by Oren Salzman [handouts].



Document Actions