Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Fall 2021/2022 Algorithmic Robotics and Motion Planning
« February 2023 »
Log in

Forgot your password?

Algorithmic Robotics and Motion Planning


Fall 2021/2022


Course hours: Monday, 16:00-19:00 mandatory attendance!

Recitations: Monday, 19:00-20:00

Location: Physics-Shenkar 104

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

Teaching assistant: Michal Kleinbort, balasmic at post tau ac il
Office hours by appointment

Software helpdesk: Michael Bilevich, michaelmoshe at mail dot tau dot ac dot il

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

  Multi-robot motion planning: Exact motion planning for large fleets of robots---the labeled vs. unlabeled case; sampling based planners for multi-robot motion planning and the tensor product---dRRT, dRRT*


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

50% Homework assignments + 50% final project;

or if you give a mini-talk in class on a topic of your choice (subject to approval) then:

40% Homework assignments + 10% mini-talk + 50% final project.

A short bibliography:  books and surveys


Assignment no. 1 file, due: Nov 1st, 2021, additional information
Assignment no. 2 file, due: Nov 15th, 2021
Assignment no. 3 file, new due date: Dec 2nd, 2021, see the Moodle page for additional information
Assignment no. 4 file, due: Dec 23rd, 2021
The final project file, due: Feb 10th, 2022

Guest Lectures

  • David Zarrouk, Ben Gurion University, 1.11.21 18:00: Minimally Actuated Reconfigurable Robots
  • Yuval Tassa, DeepMind, 8.11.21 17:10: MuJoCo – a Physics Simulator for Robotics Research
  • Aviv Tamar,  Technion, 22.11.21 16:10: Reinforcement Learning in Robotics
  • Kiril Solovey,  Technion, 06.12.21 16:10: Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation
  • Oren Salzman, Technion, 13.12.21 16:10: Algorithmic Motion Planning Meets Minimally-Invasive Robotic Surgery

Mini talks by students

  • Tommy Karkay Afik, 27.10.21: Introduction to Control
  • Dror Livant, 15.11.21: Modern Applications in Robotics
  • Shaked Dovrat, 29.11.21: Introduction to Visual SLAM
  • Adi Album and Tomer Eppstein, 13.12.21: How Can Robots See in 3D?
  • Dana Arad, 20.12.21: Collaborative Robotics

    Course summary

    • 11.10.21 
      Introduction [handouts pdf]
      Disc among discs [handouts pdf], writeup of the proof [pdf]
      Recitation 1: Intersection of half-planes 
    • 18.10.21 
      Introduction, cont'd [handouts pdf] (Slides 27-38)
      Disc among discs, cont'd [handouts pdf, a few new slides]
      Translational motion planning and Minkowski sums [handouts pdf] (up till Slide 25)
      Recitation 2: Plane sweep for line segment intersection.
    • 25.10.21
      Translational motion planning and Minkowski sums, cont'd
      Recitation 3: DCEL and map overlay,  Rotational sweep 
    • From this point on, the slides will be uploaded to the Moodle page
    • 01.11.21
      Motion planning and arrangements, general 
      Piano Movers I, translating and rotating a segment in the plane
      Guset lecture by David Zarrouk, Ben Gurion University: Minimally actuated reconfigurable robots
      Recitation 4: Computing the arrangement of the union of triangles vs. discs
    • 08.11.21
      Piano Movers I, cont'd
      Guset lecture by Yuval Tassa, DeepMind: MuJoCo – a physics simulator for robotics research
      Sampling-based motion planning I: PRM
      Recitation 5: Nearest-neighbor search using kd-trees, an example of a C-space of a telescopic arm
    • 15.11.21
      Sampling-based motion planning I: PRM, cont'd
      Getting started with DiscoPygal - presentation by Nir Goren
      Sampling-based motion planning II: The RRT family
      Recitation 6: Voronoi diagrams, Collision detection for the rod in DiscoPygal
    • 22.11.21
      Guest lecture by Aviv Tamar, Technion: Reinforcement Learning in Robotics
      Sampling-based motion planning II: The RRT family, cont'd
      Recitation 7: DiscoPygal
    • 29.11.21
      Sampling-based motion planning II: The RRT family, cont'd
      Path quality
      Recitation 8
    • 06.12.21
      Guest lecture by Kiril Solovey, Technion: Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation
      Path quality, cont'd
      Recitation 9
    • 13.12.21
      Guest lecture by Oren Salzman, Technion, 13.12.21 16:10: Algorithmic Motion Planning Meets Minimally-Invasive Robotic Surgery
      Recitation 10
    • 20.12.21
      Multi robot mtoion planning: Review
      Recitation 11
    • 27.12.21
      Near-Optimal Multi-Robot Motion Planning with Finite Sampling (lecture by Dror Dayan)
      Collision detection
    • 03.01.22
      The plan:
      Collision detection, cont'd
      Motion Planning for Multiple Unit-Ball Robots in R^d
    Document Actions