Fall 2021/2022, 0368401001
Course hours: Monday, 16:0019:00 mandatory attendance!
Recitations: Monday, 19:0020:00
Location: PhysicsShenkar 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 motionplanning 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 motionplanning problem is not restricted to robotics, and it arises naturally in different and diverse domains, including molecular biology, computer graphics, computeraided design and industrial automation. Moreover, techniques that were originally developed to solve motionplanning 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
 Samplingbased motion planning
 Collision detection and nearestneighbor search
 Path quality: shortest paths, high clearance paths, other quality measures, multiobjective optimization
 Multirobot motion planning: Exact motion planning for large fleets of robots—the labeled vs. unlabeled case; sampling based planners for multirobot motion planning and the tensor product—dRRT, dRRT*
Prerequisites
The course is geared towards graduate students in computer science. Thirdyear 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 minitalk in class on a topic of your choice (subject to approval) then:
40% Homework assignments + 10% minitalk + 50% final project.
Assignments
 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 MinimallyInvasive 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 halfplanes
 18.10.21
Introduction, cont’d [handouts pdf] (Slides 2738)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.21Translational motion planning and Minkowski sums, cont’dRecitation 3: DCEL and map overlay, Rotational sweep

From this point on, the slides will be uploaded to the Moodle page

01.11.21Motion planning and arrangements, generalPiano Movers I, translating and rotating a segment in the planeGuset lecture by David Zarrouk, Ben Gurion University: Minimally actuated reconfigurable robotsRecitation 4: Computing the arrangement of the union of triangles vs. discs

08.11.21Piano Movers I, cont’dGuset lecture by Yuval Tassa, DeepMind: MuJoCo – a physics simulator for robotics researchSamplingbased motion planning I: PRMRecitation 5: Nearestneighbor search using kdtrees, an example of a Cspace of a telescopic arm

15.11.21Samplingbased motion planning I: PRM, cont’dGetting started with DiscoPygal – presentation by Nir GorenSamplingbased motion planning II: The RRT familyRecitation 6: Voronoi diagrams, Collision detection for the rod in DiscoPygal

22.11.21Guest lecture by Aviv Tamar, Technion: Reinforcement Learning in RoboticsSamplingbased motion planning II: The RRT family, cont’dRecitation 7: DiscoPygal

29.11.21Samplingbased motion planning II: The RRT family, cont’dPath qualityRecitation 8

06.12.21Guest lecture by Kiril Solovey, Technion: Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward PropagationPath quality, cont’dRecitation 9

13.12.21Guest lecture by Oren Salzman, Technion, 13.12.21 16:10: Algorithmic Motion Planning Meets MinimallyInvasive Robotic SurgeryRecitation 10

20.12.21Multi robot mtoion planning: ReviewRecitation 11

27.12.21NearOptimal MultiRobot Motion Planning with Finite Sampling (lecture by Dror Dayan)Collision detection

03.01.22The plan:Collision detection, cont’dMotion Planning for Multiple UnitBall Robots in R^d