Course hours: Monday, 16:00-19:00 mandatory in-person attendance!
Recitations: Monday, 19:00-20:00
Location: Multi-disciplinary center 315 Link to map
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.
Link to bibliography
- Ken Goldberg, UC Berkeley
- Steven M. LaValle, Oulu University, Finland
- Kiril Solovey, Technion