Algorithmic Robotics and Motion Planning
Course hours: Monday, 16:00-19:00
Location: Schreiber 08
Instructor: Dan Halperin, danha AT post tau ac il
Office hours: Monday, 19:00-20:00
Teaching assistant: Kiril Solovey, kirilsol at post tau ac il
Exam: Tuesday, July 2nd, 2013 at 09:00 (see sample exam below)
Extra lesson on Thursday, March 21st, 2013, 16:10 - 19:00, Schreiber 008
- CGAL installation: Preparations
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
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: 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.
Sample exam [pdf]: the exam will have a similar structure; notice however that that year the topics covered were not exactly the same as this time around
Student presentations - 15 minutes of fame
A short bibliography: books and surveys
Course SummaryA 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.
Examples: vector_convex_hull.cpp, upper_convex_hull_1.cpp, upper_convex_hull_2.cpp, upper_convex_hull_3.cpp, upper_convex_hull_4.cpp