Algorithmic Robotics and Motion Planning, Fall 2023/2024

Fall 2023/2024

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

Instructor: Dan Halperin, [email protected]
Office hours by appointment

Teaching assistant: Michal Kleinbort, [email protected]
Office hours by appointment

Grader and software helpdesk: Michael Bilevich, [email protected]

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




Guest Lectures

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

Mini talks by students

Course summary


  • S.M. LaValle,
    Planning Algorithms
    Cambridge University Press, 2006
    Available on-line, link
  • J.-C. Latombe,
    Robot Motion Planning 
    Kluwer Academic Publishers, 1991 (then Springer)
  • Kevin Lynch and Frank Park,
    Modern Robotics
    Cambridge University Press, 2017
    Available on-line, link
  • H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, and S. Thrun,
    Principles of Robot Motion: Theory, Algorithms, and Implementations The MIT Press, 2005
    in particular Chapter 7
  • M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
    Computational Geometry: Algorithms and Applications 
    3rd Edition, Springer, 2008


Survey papers:

Yair Oz - Webcreator


Skip to content