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.
- 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
Introduction [handouts pdf]Recitation 1: Intersection of half-planes
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.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 researchSampling-based motion planning I: PRMRecitation 5: Nearest-neighbor search using kd-trees, an example of a C-space of a telescopic arm
15.11.21Sampling-based motion planning I: PRM, cont’dGetting started with DiscoPygal – presentation by Nir GorenSampling-based 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 RoboticsSampling-based motion planning II: The RRT family, cont’dRecitation 7: DiscoPygal
29.11.21Sampling-based 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 Minimally-Invasive Robotic SurgeryRecitation 10
20.12.21Multi robot mtoion planning: ReviewRecitation 11
27.12.21Near-Optimal Multi-Robot Motion Planning with Finite Sampling (lecture by Dror Dayan)Collision detection
03.01.22The plan:Collision detection, cont’dMotion Planning for Multiple Unit-Ball Robots in R^d