Personal tools
You are here: Home → Courses → Algorithmic Robotics and Motion Planning → Fall 2019/2020 → Algorithmic Robotics and Motion Planning
« January 2021 »
January
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
Log in


Forgot your password?
 

Algorithmic Robotics and Motion Planning


fig1
fig4
fig2

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

 
Assignment no. 1 file , due: November 11th, 2019, additional information.
 
Assignment no. 2 file , due: December 9th December 2nd, 2019, additional information.
 
Assignment no. 3 file , due: December 31st , 2019, additional information. Notice that Ex. 3.4 is a theory exercise.
 
Assignment no. 4 file , due: January 23rd, 2020, Ex. 4.4 is due January 16th 2020, additional information.
 
The final project  file , due: March 6th, 2020
 

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?
Due to shortage in teaching time for the regular course material, one invited lecture was canceled; it will be given as part of the CG seminar in the second semester.
 

Mini talks by student

 
  • Golan Levy, 4.11.19: How Do Robots See? On Lidar and Other Detection Systems [slides]
  • Itay Yehuda, 11.11.19:  Minimizing Radioactive Influence, or How to Balance Length and Clearance [slides]
  • Tom Verbin, 18.11.19:  Rotations in Space with Quaternions [slides]
  • Dror Dayan and Nir Goren, 18.11.19: Efficient Algorithms for Optimal Perimeter Guarding [slides]
  • Dor Israeli, 9.12.19: Friendly Introduction to Robotic Estimations Using Kalman Filters [slides]
  • Adar Gutman, 9.12.19: Complexity of the Minimum Constraint Removal Problem [slides]
  • Tal Eisenberg, 9.12.19: Neural Prosthetics: From Brain Activity to Robotic Motion and Back
  • Inbar Ben david, 16.12.19: A Brief Introduction to ROS
  • Or Yarinitzky and Liran Zusman, 16.12.19: Robotics StackExchange: Efficient, High-Quality Stack Rearrangement
  • Or Perel, 16.12.19: An Arm and a Leg: Humanoid Robots Design
  • Yossi Khayet, 23.12.19: Robots and Chess: from The Turk to beating Grandmasters
  • David Krongauz, 23.12.19: Foraging in Swarm Robotics: Inspired by Ants, Implemented by Robots 
  • Guy Korol, 30.12.19: Soft Robotics: Designing Robotic Actuators Made from Flexible Materials [slides]
  • Harel Oshri, 30.12.19: Computational Interlocking Furniture Assembly
  • Nadav Ostrovsky, 30.12.19: Collisions as Information Source in Multi-Robot Systems
  • Nave Tal, 30.12.19: Tabletop Rearrangements with Overhead Grasps [slides]
  • Netanel Fried, 30.12.19: Using Simple Robots in Challenging Terrains
  • Tomer Davidor, 30.12.19: Using Game Theory for Autonomous Race Cars
  • Eitan Niv, 13.1.20: Locomotion Algorithms for Snake Robots
  • Lana Salameh, 13.1.20: Nano robotics - Automatic Planning of Nanoparticles Assembly Tasks
  • Doron Kopit, 13.1.20: Controlling a Swarm: Centralized vs Decentralized
  • Dan Flomin, 13.1.20: Tasty Robots: Capsule Robotics in Gastroenterology Medicine
  • Abed Khateeb, 20.1.20: Low-cost Aggressive Off-Road Autonomous Driving 

    • 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 Zalmanson
      Recitation 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
      Recitation 6: Kd-trees, cont'd [pdf, the slides are by Marc van Kreveld], NN-search using Kd-trees [pdf, the slides are from CSE373, University of Washington]
    • 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.20
      Multi robot motion planning: Extended review [slides]
    Document Actions