MA-INF 1314 Online Motion Planning


Date for the second exam: Wednesday Sept. 14th or Wednesday Sept. 28th. Please make an appointment by our secretary.

Lecturing will start at Tuesday April 12th at 12:30 at LBH, Seminarroom E08,

Important Dates

Oral Exams II Sept. 14th/28th LBH, Room E01 Appointments by secretary Langetepe, NN
Oral Exams August 2nd/3rd LBH, Room E01 Appointments by secretary Langetepe, NN
Lecture Tuesday 12:30 to 14:00 LBH, E08 Start: April 12th 2016 Langetepe
Lecture Thursday 12:30 to 14:00 LBH, E08 Langetepe
Tutorials Tuesday 10-12 and Wednesday 14-16LBH, E08 Start: April 19th 2016 Langetepe/Wiemker


In this lecture we consider algorithmic aspects of motion planning, i.e. efficient Algorithms for motion planning problems for autonomous agents will be presented.

In contrast to other motion planning tasks we will consider motion planning under incomplete information: At the beginning, we do not have at hand all the information necessary to find an optimal or a correct path. Therefore our topic belongs to the realm of Online algorithms. We will compare online strategies to optimal offline strategies to measure their quality.

List of sample questions

July 19th: Sample Questions


April 12th: Introduction/Shannon/Graph-exploration
April 14th: Simple gridpolygons/exploration
April 19th: SmartDFS Analysis
April 21st: General grids/STC Alg.
April 26st: Constrained graph-exporation/CFS Algorithm
April 28st/May 3rd: CFS Algorithm unknown depth/Marker Alg.
May 3rd/May 10th: Pledge Algorithm with sensor errors
May 12th: Navigation by Bug Algorithms
May 24th: Searching for objects/2-ray and m-ray search
May 31th/June 2nd: Searching with bound distance/Window Shopper and searching for rays
June 9th/June 14th: Searching for a target in a street
June 21st: Hyperbolic dovetailing by Kirkpatrick
June 23rd: An optimal online escape path
June 16th/July 5th: Optimal search path and its approximations
July 5th/July 7th: Online exploration, simple, rectilinear polygons
July 12th: Online exploration, general polygons
July 14th (finished at July 12th): Looking around a corner optimally

Current Full Manuscript

Current Full Script (will be updated) last update July 15th

Tutorials and Exercises

Starting tutorial April 19th: Prepare Exercise 1-3 of the manuscript
Exercise Sheet 1 (Due April 20th)
Exercise Sheet 2 (Due April 27th)
Exercise Sheet 3 (Due May 4th)
Exercise Sheet 4 (Due May 11th)
Exercise Sheet 5 (Due May 25th)
Exercise Sheet 6 (Due June 1st)
Exercise Sheet 7 (Due June 8th)
Exercise Sheet 8 (Due June 15th)
Exercise Sheet 9 (Due June 22nd)
Exercise Sheet 10 (Due June 29th)
Exercise Sheet 11 (Due July 13th) last sheet, may be used for extra points


Introduction: April 12th
Exploration Graphs/gridpolygons: April 14th
SmartDFS Analysis: April 19th
General Gridpolygons: April 21th
Restricted Graphexploration: April 26th
Restricted Graphexploration/Analysis: April 28th
Marker algorithm/pledge algorithm: May 3rd
Pledge algorithm with sensor errors: May 10th
Bug Algorithms: May 12th
Searching for a goal: May 24th
Searching for points and rays: May 31th
Window Shopper Problem: June 1st
Searching for general rays: June 7th
Ray search LB and Searching in streets: June 9th
Optimal street searching strategy: June 14th
Alternative cost measures: June 16th
Multi-list traversal strategies: June 21st
Escape paths for polygons: June 23rd
Application Search Path Approximation: July 5th
Application Search Path Approximation with Vision: July 7th
Polygon exploration and looking around a corner: July 12th
Special questions and exam preparation: July 19th