Forgot your password?
Algorithmic Robotics and Motion Planning
  |
|
 |
|
Fall 2019/2020
0368-4010-01
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
Prerequisites
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
Assignments
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
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]
