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, Office hours by appointment
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 [slides]
- 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] - 25.11.19
Piano Movers I, cont'd [slides]
Trekking the Uncanny Valley --- Why Robots Should Look Like Robots?, guest lecture by Lior ZalmansonRecitation 5: Rotational sweep, Kd-trees [pdf, the slides are by Marc van Kreveld] -
2.12.19
Sampling-based motion planning I: PRM [slides, up till Slide #29]
Machine Learning in Robotics, guest lecture by Aviv Tamar -
9.12.19
Sampling-based motion planning I: PRM, cont'd [slides, till the end]Recitation 7: Voronoi diagrams [pdf, the slides are by Marc van Kreveld]
-
16.12.19
Collision detection [slides, new version: Dec 23rd, 2019]
-
23.12.19
Sampling-based motion planning II: Single query planners and the RRT family [slides]Recitation 9: Sampling-based motion planning under kinodynamic constraints [pdf]
-
30.12.19
Path quality [slides , up till Slide #29]
-
6.1.20
Path quality, cont'd [slides, new version: Jan 5th. 2020]Recitation 10: RRT, RRT* [pdf]
-
13.1.20Multi robot motion planning: Extended review [slides]