Algorithmic Robotics and Motion Planning, Fall 2023/2024

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*

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

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.

Link to bibliography

Assignments

Guest Lectures

• Ken Goldberg, UC Berkeley
• Steven M. LaValle, Oulu University, Finland
• Kiril Solovey, Technion

Mini talks by students

Course summary