MA-INF 1314 Online Motion Planning


Tuesday lecture now starts at 10:30! Beginning from May 9th!

Lecturing will start at Tuesday April 18th at 10:15 at LBH, Seminarroom E08!


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.

Important Dates

Oral Exams I15.8 LBH, Room E01 Appointments by secretary Langetepe, NN
Oral Exams II 26.9 LBH, Room E01 Appointments by secretary Langetepe, NN
Lecture Tuesday 10:30 to 12:00 LBH, E08 Start: April 18th 2017 Langetepe
Lecture Thursday 10:15 to 11:45 LBH, E08 Langetepe
Tutorials Tuesday/Thursday 12-14 LBH, E08 Start: April 27th 2017 Langetepe/Wiemker

List of sample questions for oral exams

Sample Questions (update July 18th)

Current Full Manuscript

Current Full Script (Update July 10th, escape path sections)

Tutorials and Exercises

Starting tutorial TBA: Prepare Exercise 1-3 of the manuscript
Exercise Sheet 1 (Due 26.04)
Exercise Sheet 2 (Due 02.05)
Exercise Sheet 3 (Due 09.05)
Exercise Sheet 4 (Due 16.05)
Exercise Sheet 5 (Due 23.05)
Exercise Sheet 6 (Due 30.05)
Exercise Sheet 7 (Due 13.06)
Exercise Sheet 8 (Due 20.06)
Exercise Sheet 9 (Due 27.06)
Exercise Sheet 10 (Due 04.07)
Exercise Sheet 11 (Due 11.07)
Exercise Sheet 12 (Due 18.07)


1. Introduction: April 18th
2. Grid-Graph-Exploration: April 20th
3. SmartDFS Analysis: April 25th
4.1 SmartDFS Comp. ratio: April 27th
4.2 General grid graphs: April 27th
5. Restricted Graph Exploration: May 2nd
6. Restricted Graph Exploration, Analysis: May 4th
7. Restr. Graph exploration and Marker variants/Pledge: May 8th
8. Online TSP, Shortcut Algorithm: May 10th
9. Pledge with sensor errors: May 16th
10. Bug Algorithms/Navigation: May 18th
11. Searching for a target: May 23rd
12. Searching for a point or ray: May 30th
13. Window shopper, searching for a ray: June 1st
14. Searching for a ray, UB/LB: June 13th
15. Searching in a street polygon: June 20th
16. Searching in a street polygon, Alternative cost measure: June 22th
17. Alternative cost measure and its applications: June 27th
18. Search path approximations with vision: June 29th
19. Search path approximations with vision, online/offline/arbitrary polygons: July 4th
20. Search path, online, arbitrary polygons, corner problem: July 6th
21. Online escape paths: July 11th
22. Online escape paths/alternative measure: July 13th
23. Online escape path for polygons/certificate approximation: July 18th
24. Exam preparation and overview: July 20th


Some of the applets shown during the lecture can be found in our geometry lab .