BewegungsplanungModulbeschreibung #41049 / Version 2
- 6 LP
- Portfolioprüfung
- Benotet
- Unregelmässig
- Englisch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
Zur aktuellen Version (v4)
| Modul / Version | #41049 / #2 |
|---|---|
| Gültigkeit | SoSe 2023 – WiSe 2024/25 |
| Verfügbare Sprache(n) | Englisch, Deutsch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Hönig, Wolfgang |
| Benotung | Benotet |
| Prüfungsform | Portfolioprüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Technische Informatik und Mikroelektronik |
| Fachgebiet | 34342100 FG Lernende intelligente Systeme |
Kontakt
| Sekretariat | MAR 4-5 |
|---|---|
| Ansprechpartner*in | Hönig, Wolfgang |
| E-Mail-Adresse | hoenig@tu-berlin.de |
| Webseite | https://imrclab.github.io/teaching.html |
Lernergebnisse
Bewegungsplanung ist eine wichtige Grundlage für autonome Systeme mit Anwendungsfeldern in der Robotik, industriellen Automatisierung und selbstfahrenden Autos.
Nach dem Kursabschluss haben Student*innen detailliertes Verständnis über folgende Themen:
• Formalisierung von geometrischer, kinodynamischer und optimaler Bewegungsplanung;
• Stichproben-basierte Verfahren: Schnell-erkundende Zufallsbäume (RRT), Wahrscheinlichkeitskarten (PRM) sowie Varianten;
• Such-basierte Verfahren: A* auf Zustandsgittern sowie Varianten;
• Optimierungs-basierte Verfahren: Differentielle Flachheit und Sequentielle Konvexe Programmierung;
• Die relevanten theoretischen Eigenschaften dieser Algorithmen (Vollständigkeit, Optimalität, Komplexität).
Student*innen werden imstande sein:
• Zu entscheiden (theoretisch und empirisch) welche Verfahren für ein gegebenes Problem erfolgversprechend sind;
• Einfache Versionen der Algorithmen selbst zu programmieren;
• Aktuelle akademische und industrielle Werkzeuge der Bewegungsplanung (z.B.: Open Motion Planning Library (OMPL)) zu nutzen.
Nach dem Kursabschluss haben Student*innen detailliertes Verständnis über folgende Themen:
• Formalisierung von geometrischer, kinodynamischer und optimaler Bewegungsplanung;
• Stichproben-basierte Verfahren: Schnell-erkundende Zufallsbäume (RRT), Wahrscheinlichkeitskarten (PRM) sowie Varianten;
• Such-basierte Verfahren: A* auf Zustandsgittern sowie Varianten;
• Optimierungs-basierte Verfahren: Differentielle Flachheit und Sequentielle Konvexe Programmierung;
• Die relevanten theoretischen Eigenschaften dieser Algorithmen (Vollständigkeit, Optimalität, Komplexität).
Student*innen werden imstande sein:
• Zu entscheiden (theoretisch und empirisch) welche Verfahren für ein gegebenes Problem erfolgversprechend sind;
• Einfache Versionen der Algorithmen selbst zu programmieren;
• Aktuelle akademische und industrielle Werkzeuge der Bewegungsplanung (z.B.: Open Motion Planning Library (OMPL)) zu nutzen.
Lehrinhalte
Diese Lehrveranstaltung wird gemeinsam von Dr. Andreas Orthey (Realtime Robotics) und Dr. Wolfgang Hönig (TU Berlin) entwickelt und gehalten. Dieser Kurs bietet eine einheitliche Perspektive auf die Bewegungsplanung und beinhaltet Themen von verschiedenen Forschungs- und Industrie-gemeinden. Das Ziel ist sowohl die theoretischen und praktischen Grundlagen der verschiedenen Ansätze zu lehren, als auch die verschiedenen Methoden bezüglich der Anwendungsanfordungen zu unterscheiden.
Ein wichtiger Schwerpunkt ist die Betrachtung der geometrischen und kinodynamischen Planung für die wichtigen Algorithmusarten.
Teil 1: Grundlagen
• Einführung, Motivation und Problemstellung
• Konfigurationsraum, Transformationen, Rotationsbeschreibungen, Metriken
• Effiziente Kollisionsprüfung
Teil 2: Such-basierte Verfahren
• A* und relevante Varianten mit ihren theoretischen Eigenschaften
• Bewegungsprimitive, Planung auf Zustandsgittern
• Search-based Planning Library (SBPL)
Teil 3: Stichproben-basierte Verfahren
• Baum-basierte Planung: RRT, EST
• Graph-basierte Planung: PRM
• Asymptotisch-optimale Planung: RRT*; PRM*
• Stichprobentheorie (Dispersion, Diskrepanz)
• Open Motion Planning Library (OMPL)
Teil 4: Optimierungs-basierte Verfahren
• Überblick über kontinuierliche eingeschränkte Optimierungsformulierung
• Parametrische Trajektorienrepresentationen und differentielle Flachheit
• Mathematische Kodierung für Bewegungsplanung: SCP und KOMO
Teil 5: Aktuelle und Fortgeschrittene Themen, z.B.
• Echtzeitplanung
• Hybride Such-, Stichproben-, oder Optimierungs-basierte Bewegungsplanung
• Maschinelles Lernen für die Bewegungsplanung
• Bewegungsplanung für mehrere Roboter: dRRT, M*
Ein wichtiger Schwerpunkt ist die Betrachtung der geometrischen und kinodynamischen Planung für die wichtigen Algorithmusarten.
Teil 1: Grundlagen
• Einführung, Motivation und Problemstellung
• Konfigurationsraum, Transformationen, Rotationsbeschreibungen, Metriken
• Effiziente Kollisionsprüfung
Teil 2: Such-basierte Verfahren
• A* und relevante Varianten mit ihren theoretischen Eigenschaften
• Bewegungsprimitive, Planung auf Zustandsgittern
• Search-based Planning Library (SBPL)
Teil 3: Stichproben-basierte Verfahren
• Baum-basierte Planung: RRT, EST
• Graph-basierte Planung: PRM
• Asymptotisch-optimale Planung: RRT*; PRM*
• Stichprobentheorie (Dispersion, Diskrepanz)
• Open Motion Planning Library (OMPL)
Teil 4: Optimierungs-basierte Verfahren
• Überblick über kontinuierliche eingeschränkte Optimierungsformulierung
• Parametrische Trajektorienrepresentationen und differentielle Flachheit
• Mathematische Kodierung für Bewegungsplanung: SCP und KOMO
Teil 5: Aktuelle und Fortgeschrittene Themen, z.B.
• Echtzeitplanung
• Hybride Such-, Stichproben-, oder Optimierungs-basierte Bewegungsplanung
• Maschinelles Lernen für die Bewegungsplanung
• Bewegungsplanung für mehrere Roboter: dRRT, M*
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Motion Planning | Integrierte Veranstaltung | Sommersemester | [de] | 4 | ISIS |
Arbeitsaufwand und Leistungspunkte
Motion Planning (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 8 h | 120 h |
| 180 h | |||
Der Aufwand des Moduls summiert sich zu 180 Stunden. Damit umfasst das Modul 6 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
• Wöchentliche Vorlesung
• Wöchentliche Hausaufgaben und dazughörige Diskussionen
• 4 Programmieraufgaben
• Wöchentliche Hausaufgaben und dazughörige Diskussionen
• 4 Programmieraufgaben
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
• Programmierkenntnisse in C++ oder Python
• Wissen über Lineare Algebra und Calculus
• Wissen über Lineare Algebra und Calculus
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Portfolioprüfung |
| Art der Portfolioprüfung | 100 Punkte insgesamt |
| Sprache | Englisch |
Prüfungselemente
| Name | Punkte/Gewicht | Kategorie | Dauer/Umfang |
|---|---|---|---|
| Hausaufgaben oder Diskussion jede Woche (bis zu 1 Punkt pro Woche; bis zu 10 Punkte insgesamt) | 10 | flexibel | Präsentation der Hausaufgaben während der Diskussion oder schriftliche Abgabe der Hausaufgaben |
| 4 Programmieraufgaben (je 10 Punkte) | 40 | praktisch | Programmcode (Zeilananzahl von der Programmiersprache abhängig) |
| Schriftliche Prüfung | 50 | schriftlich | 60 min |
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Unregelmässig.
Maximale teilnehmende Personen
Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.
Anmeldeformalitäten
Aktuelle Informationen sind in dem dazugehörigen ISIS Kurs.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
- Steven M. LaValle, Planning Algorithms, Cambridge University Press, 2006. Available for free at http://lavalle.pl/planning/.
- Kevin M. Lynch and Frank C. Park, Modern Robotics, Cambridge University Press, 2017
- Howie Choset et al., Principles of Robot Motion: Theory, Algorithms, and Implementations, A Bradford Book, 2005
- Francesco Bullo and Stephen L. Smith, Lectures on Robotic Planning and Kinematics, 2022. Available for free at http://motion.me.ucsb.edu/book-lrpk.
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
Geeignet für Master- und Promotionsstudenten in Studienrichtungen welche autonome Systeme betrachten, einschließlich, aber nicht beschränkt auf Informatik, Elektrotechnik, Maschinenbau und Luft- und Raumfahrttechnik.