Synchronization-based cooperative trajectory planning of networked vehicles

Kloock, Maximilian Martin; Kowalewski, Stefan (Thesis advisor); Althoff, Matthias (Thesis advisor)

Aachen : RWTH Aachen University (2023)
Buch, Doktorarbeit

In: Aachener Informatik-Berichte (AIB) 2023,02
Seite(n)/Artikel-Nr.: 1 Online-Ressource : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2023

Kurzfassung

Die zentralisierte Entscheidungsfindung für ein vernetztes Regelungssystem (NCS) leidet unter einem hohen Rechenaufwand für den planenden Agenten. Eine verteilte Berechnung auf mehreren Agenten verringert die Rechenzeit. Bei der verteilten Entscheidungsfindung berücksichtigen die Agenten eine Teilmenge aller Agenten in ihrer Planung. Aufgrund des nur lokalen Systemwissens der Agenten können diese lokalen Pläne inkonsistent mit den lokalen Plänen anderer Agenten sein. Diese Inkonsistenz kann zur Ungültigkeit der lokalen Pläne führen. In dieser Arbeit wird ein Algorithmus vorgestellt, der Synchronisationsmethoden einsetzt, um die Konsistenz lokaler Pläne in verteilter Entscheidungsfindung zu erreichen. Der Algorithmus ermöglicht schnelle Berechnungen und führt zu gültigen Entscheidungen. Der parallele und iterative Algorithmus führt abwechselnd zwei Schritte aus: lokale Planung und globale Synchronisation. Im lokalen Planungsschritt berechnen die Agenten parallel lokale Pläne. Anschließend wird die Konsistenz der der lokalen Pläne zwischen den Agenten durch den globalen Synchronisationsschritt erreicht. Die global synchronisierten Pläne dienen als Referenzentscheidungen für den lokalen Planungsschritt in der nächsten Iteration. In jeder Iteration garantiert die lokale Planung lokal gültige Pläne, während die Synchronisation global konsistente Pläne garantiert. Der Algorithmus konvergiert zu global gültigen Entscheidungen, wenn die Kopplungstopologie gültig ist. In dieser Arbeit werden Anforderungen an die Kopplungstopologie eingeführt, die für die Konvergenz zu global gültigen Entscheidungen erfüllt sein müssen. Zusätzlich stellt diese Arbeit eine zentrale und eine verteilte Methode zur Generierung von Kopplungstopologien vor, die diese Anforderungen erfüllen. Die zentrale Methode zur Generierung der Kopplungstopologie nutzt ihr globales Wissen über alle Agenten, um zeitinvariante Kopplungstopologien zu erzeugen. Die Methode nutzt dafür eine "greedy"-Strategie. Die verteilte Methode zur Generierung von Kopplungstopologien generiert zeitvariante Kopplungstopologien. Sie nutzt dafür Methoden der Spieltheorie. Für die Demonstration des verteilten Entscheidungsalgorithmus in Experimenten wird in dieser Arbeit eine Architektur für NCS vorgestellt, die deterministische und reproduzierbare Experimente, auch bei nicht-deterministischen Rechen- und und Kommunikationszeiten erreicht. Das Cyber-Physical Mobility Lab (CPM Lab) ist eine "open-source" und per Fernzugriff zugängliche Plattform für vernetzte und autonome Fahrzeuge, die auf dieser Architektur basiert. Darüber hinaus bietet das CPM Lab eine geeignete Schnittstelle für "rapid prototyping" mit einer nahtlosen Nutzung von Simulationen und Experimenten. In dieser Arbeit wird die komplette Wirkkette von ungekoppelten Agenten zu global gültigen Lösungen demonstriert. Die verteilten Entscheidungen werden mittels einer modellprädiktiven Regelung erzeugt. Die Evaluation dieser Arbeit nutzt das CPM Lab als Evaluationsplattform, um den verteilten MPC-Algorithmus (DMPC) mit den Kopplungstopologien, die aus den zentralen und verteilten Erzeugungsmethoden generiert wurden, zu bewerten. Die Auswertung zeigt, dass der eingeführte DMPC-Algorithmus gültige Lösungen erzielt, sowie geringere Rechenzeiten und geringere Kommunikationsanforderungen als die zentrale MPC (CMPC) hat. Die resultierenden Trajektorien zeigen nur geringe Abweichungen von den durch CMPC erzeugten global optimalen Trajektorien.

Einrichtungen

• Fachgruppe Informatik [120000]
• Lehrstuhl für Informatik 11 (Embedded Software) [122810]