Personal tools
|
|
Algorithmic Robotics and Motion Planning
Spring 2018 0368-4010-01 Course hours: Monday, 16:00-19:00 Instructor: Dan Halperin, danha AT post tau ac il 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):
Prerequisites In 2019 these prerequisites will be removed/modified (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.
AssignmentsAssignment 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.
Assignment no. 4 file , due: May 21st, 2018
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
23.04.18 Theory of Sampling-based motion planning [slides]
- PRM* paper by Karaman and Frazzoli (2011)
- Connection with random geometric graphs
- Bottleneck pathfinding
- Critical radius analysis
30.04.18 More on sampling-based planning (see updated slides from previous lecture):
- Critical-radius analysis for bottleneck cost
- RRT, bidirectional RRT, RRG, RRT*
- Lazy PRM, A*, A*-based search on PRM
07.05.18 Introduction to collision detection and proximity queries
Review by Lin et al, Chapter 39 of the Handbook on Discrete and Computational Geometry
Logarithmic-time intersection detection for two convex polygons, from
Optimal detection of intersections between convex polyhedra by Barba and Langerman
14.05.18 Multi-robot motion planning [slides]:
- Pebble motion on graphs
- Exact solution for two discs
- Reducing degrees of freedom for two discs
- Hardness for multiple robots
- Polynomial-time (and cost optimizing) algorithm for the unlabeled case with separation
- Hardness of the unlabeled case [slides]
21.05.18 Collision detection continued, Bounding Volume Hierarchies [slides]
The HGraphs paper [link]
Unlabeled motion planning [link]
Document Actions |
||||
Forgot your password?
A brief tour of algorithmic problems in robotics