Search
Close this search box.

Algorithmic Robotics and Motion Planning, Fall 2021–2022

Fall 2021/2022, 0368-4010-01

Course hours: Monday, 16:00-19:00 mandatory attendance!

Recitations: Monday, 19:00-20:00

Location: Physics-Shenkar 104

Instructor: Dan Halperin, danha AT post tau ac il
Office hours by appointment

Teaching assistant: Michal Kleinbort, balasmic at post tau ac il
Office hours by appointment

Software helpdesk: Michael Bilevich, michaelmoshe at mail dot tau dot ac dot il

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.

Assignments

  1. Assignment no. 1 file, due: Nov 1st, 2021, additional information
  2. Assignment no. 2 file, due: Nov 15th, 2021
  3. Assignment no. 3 file, new due date: Dec 2nd, 2021, see the Moodle page for additional information
  4. Assignment no. 4 file, due: Dec 23rd, 2021
  5. The final project file, due: Feb 10th, 2022

Guest Lectures

  • David Zarrouk, Ben Gurion University, 1.11.21 18:00: Minimally Actuated Reconfigurable Robots
  • Yuval Tassa, DeepMind, 8.11.21 17:10: MuJoCo – a Physics Simulator for Robotics Research
  • Aviv Tamar,  Technion, 22.11.21 16:10: Reinforcement Learning in Robotics
  • Kiril Solovey,  Technion, 06.12.21 16:10: Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation
  • Oren Salzman, Technion, 13.12.21 16:10: Algorithmic Motion Planning Meets Minimally-Invasive Robotic Surgery

Mini talks by students

  • Tommy Karkay Afik, 27.10.21: Introduction to Control
  • Dror Livant, 15.11.21: Modern Applications in Robotics
  • Shaked Dovrat, 29.11.21: Introduction to Visual SLAM
  • Adi Album and Tomer Eppstein, 13.12.21: How Can Robots See in 3D?
  • Dana Arad, 20.12.21: Collaborative Robotics

Course summary

  • 11.10.21 
    Introduction [handouts pdf]
    Disc among discs [handouts pdf], writeup of the proof [pdf]
    Recitation 1: Intersection of half-planes
  • 18.10.21 
    Introduction, cont’d [handouts pdf] (Slides 27-38)
    Disc among discs, cont’d [handouts pdf, a few new slides]
    Translational motion planning and Minkowski sums [handouts pdf] (up till Slide 25)
    Recitation 2: Plane sweep for line segment intersection.
  • 25.10.21
    Translational motion planning and Minkowski sums, cont’d
    Recitation 3: DCEL and map overlay,  Rotational sweep
  • From this point on, the slides will be uploaded to the Moodle page
  • 01.11.21
    Motion planning and arrangements, general
    Piano Movers I, translating and rotating a segment in the plane
    Guset lecture by David Zarrouk, Ben Gurion University: Minimally actuated reconfigurable robots
    Recitation 4: Computing the arrangement of the union of triangles vs. discs
  • 08.11.21
    Piano Movers I, cont’d
    Guset lecture by Yuval Tassa, DeepMind: MuJoCo – a physics simulator for robotics research
    Sampling-based motion planning I: PRM
    Recitation 5: Nearest-neighbor search using kd-trees, an example of a C-space of a telescopic arm
  • 15.11.21
    Sampling-based motion planning I: PRM, cont’d
    Getting started with DiscoPygal – presentation by Nir Goren
    Sampling-based motion planning II: The RRT family
    Recitation 6: Voronoi diagrams, Collision detection for the rod in DiscoPygal
  • 22.11.21
    Guest lecture by Aviv Tamar, Technion: Reinforcement Learning in Robotics
    Sampling-based motion planning II: The RRT family, cont’d
    Recitation 7: DiscoPygal
  • 29.11.21
    Sampling-based motion planning II: The RRT family, cont’d
    Path quality
    Recitation 8
  • 06.12.21
    Guest lecture by Kiril Solovey, Technion: Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation
    Path quality, cont’d
    Recitation 9
  • 13.12.21
    Guest lecture by Oren Salzman, Technion, 13.12.21 16:10: Algorithmic Motion Planning Meets Minimally-Invasive Robotic Surgery
    Recitation 10
  • 20.12.21
    Multi robot mtoion planning: Review
    Recitation 11
  • 27.12.21
    Near-Optimal Multi-Robot Motion Planning with Finite Sampling (lecture by Dror Dayan)
    Collision detection
  • 03.01.22
    The plan:
    Collision detection, cont’d
    Motion Planning for Multiple Unit-Ball Robots in R^d

Assignment 1

Submission

Please submit an archive that contains all source and documentation files in a flat directory structure for each exercise (that is, place all files of a given exercise in one directory); Upload the archive to moodle, in the relevant submission box. Make sure to include in the archive a file cover.pdf , where you describe your solution and explain in detail how to run the program.

You are free to use any programming language for this exercise.

Exercise 1.1

General

Name the archive either oskar.zip or oskar.tar.gz.
Name the basename (the filename without the extension) of the program file oskar.
If you develop in C++ use a single source file called oskar.cpp.
If you develop in Python name the executable oskar.py.
If you develop in a different language, follow the same logic…

Input

sx sy sz dx dy dz filename

The program should accept 7 arguments on the command line:

  • The source location of the robot (sx sy sz), followed by the destination location of the robot (dx dy dz), followed by the name of file that contains the description of the obstacle (filename).
  • Each location is a vector of three integral values specifying the x, y, and z coordinates of the robot center.
  • A valid input file starts with the x, y, and z dimensions (in that order) of the puzzle followed by three matrices representing the xy-, yz-, and zx-faces; 0 represents a free location and 1 represents a forbidden location.
    • The entry in row i>=0 and column j>=0 in the xy-matrix represents the value for x=j and y=i. The same holds for the two other matrices.
  • The dimensions of the standard Oskar puzzle are 11, 11, 11. For a puzzle of dimensions 11,11,11 a location is defined by three integer values v_1, v_2, v_3, where  0<=v_k<=10.
  • One pair of source and destination locations is (3, 7, 7) and (5, 1, 1), respectively.
  • You can obtain the file that contains the three (11×11) matrices here.

Output

The program should export the result to the standard output. The output format must be identical to the format of the verifier (see below). It consists of three lines.
The first and second lines contain the start and end positions, respectively. Each position consists of three integral values separated by spaces.
The third line contains a sequence of commands separated by spaces. Applying these commands to the robot should move it from the source location to the destination location without passing through forbidden locations. A command is encoded as follows:

0—move one unit along the x-axis in the positive direction
1—move one unit along the x-axis in the negative direction
2—move one unit along the y-axis in the positive direction
3—move one unit along the y-axis in the negative direction
4—move one unit along the z-axis in the positive direction
5—move one unit along the z-axis in the negative direction

Oskar verifier and simulator

In the following website you can verify your solution and visualize the simulation: http://www.cs.tau.ac.il/~michaelmoshe/oskar-visualization/

You can rotate the viewport by clicking and dragging the left mouse button, and zoom in and out with the mouse scroll wheel.

On the top left corner of the simulator there are three input fields which have the following format (from top to bottom):

  • Start position (e.g. 3 7 7)
  • End position (e.g. 1 7 9)
  • Command sequence (e.g. 4 4 1 1)

After entering the input you can press the play button on the bottom of the simulator to view the simulation in action! You can also press the “Verify” button to verify your input without playing the animation (and get the result immediately).

There is a log message on the bottom left corner, which displays an error/success message or the verifier/simulation.

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content