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

Forgot your password?

Algorithmic Robotics and Motion Planning

Multi Robot Multi Robot Configuration Space

Spring 2013


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)


No need to solve Ex 4.5 (we did not cover the necessary material).
In preparation for the lesson on June 3rd read the following chpaters in Craig's book, Introduction to Robotics/Mechanics and Control (3rd Edition, Pearson, Prentrice Hall):  Chapters 2 (spatial descritpion and transformations), 3 (forward kinematics, Denait-Hartenberg representation) and 4 (inverse kinematics). 

Extra lesson on Thursday, March 21st, 2013, 16:10 - 19:00, Schreiber 008

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: 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

Every week one or two students will present one robotics project or topic of their choice between 18:45 and 19:00.
11.3 Shahar Ilan: Robot-assisted laparoscopic surgery - The da Vinci System [slides]
18.3 Noam Gat: Physics Based Locomotion Using Low Dimensional Planning [slides] [video]
8.4   Ran Ahituv and Or Kamara: Robocup
22.4 (18:30) Sergey Dorodnicov: Evolving artificial robots [slides] (18:45) Michael Seltzer: IOIO - build your own low-cost robot
29.4 Aviel Atias, Omri Ben Eliezer and Yaniv Sabo: Space robots [slides]
13.5 Miki Shifman and Chai Ozeri: QinetiQ's "Dragon Runner" robot [slides]
20.5 Sivan Keret and Itzik Malkiel
27.5 (18:30) Anna Itin and Tal Saiag: Swarm robotics [slides] (18:45) Lior Teller: Modular Snake Robots [link]
3.6   Shevah Marants and Yitzhak Elboher: Big Dog [slides]
10.6 Alexey Pechorin: Nanorobotics [slides]


Assignments weight distribution: 0.1*ex1 + 0.2*ex2 + 0.2*ex3 + 0.5*ex4.
Assignment no.3: pdf and more information on Ex3.3.
Assignment no.4: pdf and more information on Ex4.2 and Ex4.3. No need to solve Ex 4.5 (we did not cover the necessary material).
Exercise should be submitted to Kiril's analog mailbox no.301 in Schreiber, first floor or via email.

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.

 4/3/13 - Introduction, basic terminology, topics and course mechanics [pdf
Minkowski sums, preliminaries [pdf]

  11/3/13 - Motion planning and arangements [pdf
The combinatorial complexity of a disc moving among discs [pdf]

  18/3/13 - Computational Geometry Algorithm Library, Convex Hull [pdf], handouts [pdf]
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
  21/3/13 - Sampling-based planning I: PRM [pdf]
Guest lecture by Vadim Indleman, GeorgiaTech: Introduction to SLAM and Incremental Light 
Bundle Adjustment [pdf]
  8/4/13 - Sampling-based planning continued: probabilstic completeness of PRM (see Chapter 7 in Choset et al)
2D Minkowski sums (slides 1-24) [pdf]
envelopes in the plane [pdf]
  22/4/13 - Motion planning for a polygonal robot - Analytic techniques and Motion-planning via Manifold Samples (MMS) [pdf]
  29/4/13 - Path quality [pdf] (new version, May 13th, 2013)
  06/5/13 - Multi-robot motion planning [pdf]
  13/5/13 - Path quality, continued [pdf] (new version, May 13th, 2013)

  20/5/13 - Path comparison and HGraphs (end of Path quality, see slides of last week)
Guest lecture by Guy Hoffman of IDC, Herzlia on Designing Human-Robot Performances [abstract and bio]
Intorduction to collision detection: the case of two convex polytopes (see slides of the following week)
  27/5/13 - Collision detection [pdf]
In preparation for next week read the following chapters in Craig's book, Introduction to Robotics/Mechanics and Control (3rd Edition, Pearson, Prentrice Hall):  Chapters 2 (spatial descritpion and transformations; you can skip Section 2.8), 3 (forward kinematics, Denait-Hartenberg representation) and 4 (inverse kinematics). 
  3/6/13 - Collision detection completed (see slides of last week)
Kinematics [pdf]: we skimmed through slides 24 to 68
Document Actions