Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Fall 2019/2020 Algorithmic Robotics and Motion Planning
« November 2019 »
Log in

Forgot your password?

Algorithmic Robotics and Motion Planning


Fall 2019/2020


Course hours: Monday, 16:00-19:00

Recitations: Monday, 19:00-20:00

Location: Sherman 003

Instructor: Dan Halperin, danha AT post tau ac il
Office hours by appointment

Teaching assistant: Michal Kleinbort, balasmic at post tau ac il

Grader: Yair Karin, yair dot krn at gmail com

Software helpdesk: Nir Goren, nirgoren at mail tau ac il, Sunday, 14:15-15:15

The recent years have 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

  Collision detection and nearest-neighbor search

  Path quality: shortest paths, high clearance paths, other quality measures, multi-objective optimization

  Direct and inverse kinematics: from industrial manipulators to proteins

  Multi-robot motion planning


The course is geared towards graduate students in computer science. Third-year undergrads are welcome; in particular, the following courses are assumed: Algorithms, Data structures, Software1.

The final grade

Homework assignments (40%), brief talk in class on a topic of the student's choice (subject to approval) (10%), final project (50%).

A short bibliography:  books and surveys


Assignment no. 1 file , due: November 11th, 2019, additional information.
Assignment no. 2 file , due: December 2nd, 2019, additional information.

Guest Lectures

  • Guy Hoffmnan, Cornell, 23.12.19: Designing Robots and Designing with Robots: New Strategies for an Automated Workplace
  • Ilana  Nisky, BGU, 6.1.20: Haptics for the Benefit of Human Health
  • Oren Salzman, Technion, 30.12.19: Asymptotically-Optimal Inspection Planning with Application to Minimally-Invasive Robotic Surgery
  • Aviv Tamar, Technion, 2.12.19: Machine Learning in Robotics
  • Lior Zalmanson, TAU, 25.11.19: Trekking the Uncanny Valley --- Why Robots Should Look Like Robots?

Mini talks by student

  • Golan Levy, 4.11.19: How Do Robots See? On Lidar and Other Detection Systems [slides]
  • Itay Yehuda, 11.11.19:  Minimizing Radioactive Influence, or How to Balance Length and Clearance [slides]
  • Tom Verbin, 18.11.19:  Rotations in Space with Quaternions [slides]
  • Dror Dayan and Nir Goren, 18.11.19: Efficient Algorithms for Optimal Perimeter Guarding [slides]
  • Adar Gutman, 9.12.19: Complexity of the Minimum Constraint Removal Problem
  • Yossi Khayet, 9.12.19: Robots and Chess: from The Turk to beating Grandmasters
  • Or Perel, 16.12.19

    Course summary

    • 28.10.19 
      Introduction [pdf]
      Recitation 1: Intersection of half-planes [pdf]
    • 4.11.19 
      Robots with 2 dofs and two-dimensional state spaces
      Disc among discs [slides], proof of the combinatorial bound [pdf]
      Minkowski sums and transnational motion planning [slides, up till Slide #15]
      Recitation 2: Plane sweep for line segment intersection. [pdf, the slides are by Marc van Kreveld]
    • 11.11.19 
      Minkowski sums, continued [slides, #15-39]
      Motion planning and geometric arrangements, general exposition [slides, up till Slide #13]
      Recitation 3: DCEL and map overlay. [pdf, the slides are by Marc van Kreveld]
                         Python code demonstrating Minkowski sum computation and Map overlay (developed by Nir Goren), requires the Python bindings for CGAL 
    • 18.11.19 
      Motion planning and geometric arrangements, continued: general algorithms [slides]
      Piano Movers I, translating and rotating a segment in the plane [slides, up till Slide #12]
      Recitation 4: Convex hull. [pdf, the slides are by Marc van Kreveld]
    Document Actions