Von modernen Robotern erwarten wir, dass sie sich in ihrer Umgebung kollisionsfrei und effizient bewegen. In dieser Vorlesung werden einige der algorithmischen Probleme behandelt, die hierbei auftreten; sie alle haben mit der Geometrie der Umgebung und des Roboters zu tun. Wir betrachten zunächst die Aufgabe, kürzeste Wege für kreisförmige Roboter in Anwesenheit von Hindernissen zu berechnen. Dann betrachten wir die Planung kollisionsfreier Bahnen für Agenten mit mehreren Freiheitsgraden. Die in der Algorithmik typischen Komplexitäts- und Berechnungsprobleme bei der Bahnplanung von Agenten werden in der Vorlesung untersucht! Ein gut ausgearbeitetes Vorlesungsskript wird zur Verfügung gestellt.

Die erste Vorlesung beinhaltet eine kleine Einführung in das Thema.

Das Skript zur Vorlesung wird vor Veranstaltungsbeginn zur Verfügung gestellt.

Die Folien zur Vorlesung werden vor der Vorlesung bereitgestellt.

Die Vorlesung wendet sich an alle Bachelor-Studierenden als Wahlpflichtveranstaltung.

Prüfungen werden voraussichtlich mündlich erfolgen. Termine: 11.2.2015 und 12.2.2015.
Vereinbaren Sie einen Termin mit unserem Sekretariat (Frau Bertram).

Die Vorlesungen finden jeweils

• Montags 14:30-16:00 Uhr AVZ III/ A207, (Dozent: Elmar Langetepe)
• Mittwochs 14:30-16:00 Uhr AVZ III/ A207, (Dozent: Elmar Langetepe)

statt. Vorlesungsbeginn ist am Mittwoch 08.10.2014 !

Die erste Übung findet in der zweiten Vorlesungswoche statt. Die Übungen werden Mittwochs oder Donnerstags ausgegeben und Mittwochs von Ihnen abgegeben (bis 14:30 in unserem Briefkasten im Foyer des AVZ III). Eine Anwesenheitspflicht für die Übungsgruppen gibt es nicht. Beachten Sie aber, dass Sie zum Erreichen des Übungserfolges wenigstens einmal (nach Tutorenwunsch aber ggfs. auch öfter) eine Übungsaufgabe vorgerechnet haben müssen, wofür man natürlich anwesend sein muss. Nach aktueller Planung werden 10 Übungszettel ausgegeben.

Der aktuelle Übungstermin:

• Mittwochs, 16 bis 18 Uhr, Raum A6c im AVZIII.

Für die Zulassung zur Prüfung müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von Aufgaben müssen im Laufe des Semesters erfolgreich in den Übungen präsentiert werden. Eine Abgabe der Übungsaufgaben in Zweiergruppen ist möglich, sofern jeder der Teilnehmer die Aufgabe auch so präsentieren kann, dass daraus das Verständnis ablesbar ist.

Ansprechpartner ist Simone Lehmann [EMail: lehmann(at)cs.uni-bonn.de]

• Präsenzblatt
• Aufgabenblatt01
• Aufgabenblatt02
• Aufgabenblatt03
• Aufgabenblatt04
• Aufgabenblatt05
• Aufgabenblatt06
• Aufgabenblatt07
• Aufgabenblatt08
• Aufgabenblatt09
• Aufgabenblatt10
• Aufgabenblatt11
• Aufgabenblatt12

Hier finden Sie zunächst einen Auszug des Skriptes, der elektronische Zugang zum vollständigen Skript wird in der ersten Vorlesung bekannt gegeben. Das Skript ist für den persönlichen Gebrauch in der Vorlesung gedacht, eine beliebige Weitergabe ist nicht erlaubt.

Skript erster Auszug.
Skript zum Download mit Zugangsberechtigung

Vorlesung am 8.10.2014: Einführung in das Thema
Vorlesung am 13.10.2014: Der simultane Sweep
Vorlesung am 15.10.2014: Horizontbäume und Shortest Path
Vorlesung am 20.10.2014: Kürzeste Wege in Polygonen
Vorlesung am 22.10.2014: Kürzeste Wege Anfragen mittels Preprocessing
Vorlesung am 27.10.2014: Durchmesser Berechnung, monotone Matrizen
Vorlesung am 29.10.2014: Shortest Watchman Routes und TPP
Vorlesung am 03.11.2014: TPP und Wege in 3D
Vorlesung am 05.11.2014: 3D Wege: Raum und Polyeder
Vorlesung am 10.11.2014: Kürzeste Wege auf einem Polyeder
Vorlesung am 12.11.2014: Kürzester Wege Polyeder, Bewegung von Objekten
Vorlesung am 17.11.2014: Bewegung von Objekten, Translation
Vorlesung am 19.11.2014: Translationsbewegung und Minkowskisummen
Vorlesung am 24.11.2014: Translationsbewegungen und Konturen
Vorlesung am 26.11.2014: Zellenkomplexität für Konfliktbögen
Vorlesung am 1.12.2014: Zellenberechnung und Red/Blue Merge
Vorlesung am 8.12.2014: Zellenberechnung, allgemeine Systeme, Part Feeding
Vorlesung am 10.12.2014: Part Feeding, Algorithmus
Vorlesung am 15.12.2014: Part Feeding, Korrektheit, Vollständigkeit
Vorlesung am 17.12.2014: Zusammenfassung
Vorlesung am 6.1.2015: Translation und Rotation
Vorlesung am 12.1.2015: Translation und Rotation, Kritische Platzierungen, Anzahl
Vorlesung am 14.1.2015: Translation und Rotation, Kritische Platzierungen, Berechnung
Vorlesung am 19.1.2015: Translation und Rotation, Knotengraph, Kritische Orientierungen, Berechnung
Vorlesung am 21.1.2015: Translation und Rotation, Kantengraph, Bahnplanung
Vorlesung am 28.1.2015: Trapezzerlegung, Bachelorthemen
Vorlesung am 4.2.2015: Konkrete Fragen

Bitte melden Sie sich alle auf der Mailingliste vl-offline@lists.iai.uni-bonn.de an. Nutzt dafür diesen Link. Das ist wichtig, denn über diese Mailingliste erhaltet ihr die relevanten Organisationsinformationen!

Mündliche Prüfungen am 11.2.2015 und 12.2.2015.
Vereinbaren Sie einen Termin mit unserem Sekretariat (Frau Bertram).

Eine Liste repräsentativer Prüfungsfragen wird rechtzeitig zusammengestellt.

Fragenkatalog zur Prüfungsvorbereitung