Personal tools
You are here: Home → Courses → Algorithmic Robotics and Motion Planning → Spring 2018 → Algorithmic Robotics and Motion Planning
« April 2018 »
April
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
2930
Log in


Forgot your password?
 

Algorithmic Robotics and Motion Planning


fig1
fig4
fig2

Spring 2018

0368-4010-01

Course hours: Monday, 16:00-19:00
Location: Schreiber 007

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

Teaching assistant: Kiril Solovey, kirilsol at post tau ac 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

Path quality: shortest paths, high clearance paths, and other quality measures
Direct and inverse kinematics: from industrial manipulators to proteins
Dynamic maintenance of large kinematics structures
 Multi-robot motion planning

Prerequisites 

(i) Computational Geometry and (ii) knowledge of C++ or willingness to learn the language.

The course is geared towards graduate students in computer science. Third-year undergrads are welcome.

 

Assignments

 
Assignment no. 1 file , due: March 19th, 2018, additional information.
Assignment no. 2 file , due: April 9th, 2018 , additional information.
Assignment no. 3 file , due: April 30th, 2018 , additional information.
 

Course summary

 
 07.03.18 
Intorudction [handout]
The Roomba in the cafe, moving a disc among discs. The complexity of the union of discs in the plane [proof]
 
 14.03.18 
Translational motion planning and Minkowksi sums [handout]
 
 21.03.18 
Translation and rotation in the plane, Piano Movers I
Latombe's book, Chapter 5, Section 2
 
 09.04.18 
The connection between motion planning and arrangements; general complete algorithms [handout]
The separation of algebra and topology in CGAL arrangements [pdf]
 
 16.04.18 
Introduction to path quality
Shortest paths, see Chapter 15, Visibility Graphs, of the Computational
Introduction to sampling-base motion planning: RRT, PRM, and proof of
probabilistic completeness of PRM
Chapter 7 of the book Principles of robot motion by Choset et al
Document Actions