GPU Based Tactical Motion Planning – Das Fundament für hochintegrierte Fahrerassistenz

1. Einleitung

Die Weiterentwicklung von Fahrerassistenzsystemen (FAS) zum hochautomatisierten Fahren stellt einen dominanten Schwerpunkt in Industrie und Forschung dar; besonderes Augenmerk wird dabei zumeist auf die Entwicklung neuer sowie die Verbesserung bestehender Funktionalität gelegt. Doch hochautomatisiertes Fahren ist mehr als die Summe orthogonaler Einzelfunktionen – es wird erst durch deren koordiniertes Zusammenspiel ermöglicht. Durch diesen Umstand motiviert entwickelt die Forschungsgesellschaft Kraftfahrwesen mbH Aachen (fka) in Zusammenarbeit mit dem Institut für Kraftfahrzeuge RWTH der Aachen University (ika) eine Funktionsarchitektur, welche eine Emergenz der Einzelsysteme bei gleichzeitiger Verringerung der Entwicklungszeit sowie ein einheitliches Fahrgefühl über Funktionsgrenzen hinweg ermöglicht.

Einen zentralen Bestandteil dieser Architektur stellt das Modul zur Abstraktion der Bewegungsplanung des Fahrzeugs dar: der Tactical Motion Planner (TMP). Der TMP sammelt die Angaben sämtlicher FAS-Funktionen, um darauf basierend die unter einer gegebenen Kostenfunktion und ggf. weiteren Referenzwerten optimale Steuertrajektorie zu berechnen. Dabei müssen sämtliche Szenarien – vom Parkieren über das Fahren in der Stadt, auf dem Land und auf der Autobahn bis hin zum hochdynamischen Ausweichmanöver – mit ihren jeweiligen spezifischen Anforderungen abgedeckt werden. Weiterhin soll sich der TMP auch für den zukünftigen Einsatz in hochautomatisierten Fahrzeugen eignen.

Stand der Technik

In den vergangenen Jahren wurde eine Vielzahl verschiedener Ansätze zur Berechnung von Fahrtrajektorien entwickelt. Da es hierfür im Allgemeinen keine geschlossene Lösung gibt, nutzen die meisten Planer numerische Optimierungsverfahren, um die beste Trajektorie zu bestimmen. Die Bewertung ist dabei abhängig von der gewählten Metrik, welche häufig die Komfort- und Sicherheitsaspekte wie etwa resultierende Querbeschleunigung, den Ruck sowie Abweichungen von einer Sollvorgabe, etwa der Spurmitte und Richtgeschwindigkeit, berücksichtigt.

Der prinzipielle Ablauf der Planer ähnelt sich stark: Basierend auf einem zu erreichenden Zielzustand werden meist Zwischenzustände ermittelt, die entlang einer Referenzkurve vom Start- in den Zielzustand führen und hierüber implizit die Steuertrajektorie bestimmt. Die Suche nach dem Optimum hängt dabei vom verwendeten Optimierungsalgorithmus ab. Eine

Variante ist die Diskretisierung des Zustandsraumes [1,2]. Hierbei wird zunächst der Zustandsraum zwischen Start- und Zielposition diskretisiert, anschließend für sämtliche Übergänge die Steuerfunktion ermittelt und die resultierenden Kosten berechnet. Über eine vollständige Suche wird dann die beste Steuertrajektorie aus den vorhandenen Einzelstücken zusammengesetzt. Im Gegensatz hierzu wird im Fall gradientenbasierter Verfahren [3] auf Basis einer initialen Schätzung der Zwischenzustände über Parametervariationen das (lokale) Minimum bestimmt. Als weitere Variante finden sich Kombinationen beider Verfahren [4].

Um die Fahrbarkeit sicherzustellen, müssen bei beiden Varianten die Zustandsübergänge berechnet werden. Neben rein geometrischen Ansätzen kommen hier je nach Abstand der Stützstellen vor allem regelungstechnische Verfahren [1,5,6,7] oder einfache Linearisierungen [3,4] zum Einsatz.

2. Anforderungen und Forschungsansatz

Die zentrale Anforderung an den TMP ist seine generische Anwendbarkeit. Zusammengefasst sind daraus die folgenden Forderungen ableitbar:

  1. Die Einhaltung von Zustands- und Steuerbeschränkungen muss auf dem gesamten Zeitintervall garantiert werden. Hierzu zählen z. B. Kollisionsfreiheit, das Nichtverlassen des Fahrkorridors sowie die Berücksichtigung kinematischer und fahrdynamischer Grenzen.
  2. Die resultierende Trajektorie muss einen intuitiven, ruckfreien Verlauf besitzen.
  3. Der gesamte Fahrdynamikbereich muss abgedeckt werden können.
  4. Der Planer muss echtzeitfähig1 und robust eine Lösung für das aufgestellte Problem berechnen.
  5.  Es müssen sämtliche Referenzvorgaben in den Planer integrierbar sein.

Analyse bisheriger Planer

Bisherige Planungsalgorithmen sind nicht in der Lage, alle Anforderungen gleichzeitig zu erfüllen – sie sind z. B. meist auf spezielle Anwendungsszenarien maßgeschneidert. Daneben bestehen die folgenden umsetzungsspezifischen Probleme:

Im Fall der Diskretisierung der Zwischenzustände müssen in Abhängigkeit von der Anzahl an Zustandsgrößen relativ große Diskretisierungsschritte genutzt werden, um eine echtzeitfähige Abtastung zu ermöglichen. Hierdurch kann es zu großen Abweichungen der gefundenen von der optimalen Steuerungsfunktion kommen. Weiterhin kann es vorkommen, dass Lösungen existieren, jedoch nicht gefunden werden.

Bei einigen Verfahren ist die Steuertrajektorie vollständig durch Start- und Zielzustand beschrieben. Variationen entstehen daher lediglich durch die Anpassung des Zielzustands. Hindernisse und der Straßenverlauf haben bei dieser Variante also keinen direkten Einfluss auf die Gestaltung der einzelnen Primitiven, wodurch die gleichen Probleme wie bei der Diskretisierung auftreten.

Eine letzte Gruppe von Verfahren berücksichtigt Hindernisse, den Straßenverlauf und kinematische Restriktionen direkt bei der Ermittlung der Steuerungsfunktion (vgl. [3]). Diese werden in Form von Nebenbedingungen in ein nichtlineares Programm (NLP) codiert, über welches die Parametrierung der Steuerungsfunktion oder die Wahl der Zwischenzustände ermittelt wird. Dadurch, dass jede Bedingung einzeln eingebettet wird, ist die Dimension des resultierenden Gleichungssystems abhängig von der Distanz zwischen den Überprüfungen. Um die Komplexität der Lösungsfindung zu minimieren wird daher in der Regel eine recht grobe Überprüfung vorgenommen, so dass kurze Überschreitungen zulässiger Werte nicht erkannt werden. Gleichzeitig wird die Lösung des großen Gleichungssystems komplexer und anfälliger für Nichtkonvergenz.

Forschungsansatz

Die Problemstellung stellt ein klassisches Optimalsteuerungsproblem (Optimal Control Problem - OCP) dar [8]: die Suche nach einer unter einem gegebenem Kostenfunktional optimalen Steuertrajektorie, die das Fahrzeug unter Einhaltung von Steuer- und Zustandsbeschränkungen vom Start- in den gewünschten Endzustand überführt.

Im Gegensatz zu den meisten Planern fiel die Entscheidung beim TMP darauf, die Steuerfunktion zwischen Start- und Zielzustand direkt zu bestimmen und keine Zwischenzustände einzuführen. Neben der Unabhängigkeit von einer Referenztrajektorie muss das Problem auf diese Weise nicht zusätzlich diskretisiert und in ggf. voneinander abhängige Teilprobleme zerlegt werden. Ebenfalls ist es somit nicht nötig, eine separate Steuerungsfunktion für jeden Zustandsübergang zu berechnen.

Zur Überprüfung kontinuierlich geltender Randbedingungen wurde für den TMP ein Mechanismus implementiert, welcher sich an Barrier Functions aus der beschränkten Optimierung orientiert [9]. Statt der separaten Betrachtung dedizierter Stellen gewichtet eine Filterfunktion alle unzulässigen Zustandsgrößen mit einem hohen Strafwert und vernachlässigt alle anderen. Anschließend werden die gefilterten Werte integriert (siehe auch [10]). Das aufgestellte NLP wird um die Forderung der Einhaltung eines Grenzwertes für dieses Integral erweitert, wodurch Lösungen ungültig werden, sobald innerhalb dieser ein unzulässiger Zustand eintritt.

Sind die verwendeten Metriken und Zustandsbeschreibungen zweifach stetig differenzierbar, kann das derart aufgestellte NLP über einen gradientenbasierten Solver gelöst werden. Aktuell wird hierfür Knitro [11] verwendet, wobei aufgrund seiner Geschwindigkeit und Stabilität dessen Interior Point Algorithmus Anwendung findet.

In den folgenden Kapiteln wird der TMP genauer beschrieben. Hierbei wird zunächst auf seine zentrale Architektur und die beinhalteten Komponenten und Funktionen eingegangen. Anschließend werden Details der für die Echtzeitfähigkeit notwendigen Implementierung auf einem heterogenen System aus GPU und CPU beschrieben sowie Simulationsergebnisse des Planers erläutert. Der Beitrag schließt mit einem Ausblick auf ausstehende Arbeiten.

3. Aufbau und Struktur des Tactical Motion Planners

Die Struktur des TMP orientiert sich an den Komponenten einer Optimalsteuerung, also der Beschreibung der Steuerungsfunktion, des Systemmodells und der Zustandsbewertung, siehe Abbildung 1. Der grundlegende Ablauf ist wie folgt: Zunächst wird die aktuelle Situation über einen Präprozessor vorverarbeitet und an den NLP-Solver übergeben. Aus den von diesem ermittelten Parametern wird eine Steuerungsfunktion extrapoliert, auf den Istzustand des Fahrzeugmodells angewandt und die resultierenden Zustände berechnet. Schließlich wird die Lösung mit der Anforderung verglichen, auf Gültigkeit und Zulässigkeit geprüft und ggf. eine neue Iteration mit geänderten Parametern gestartet.

Im Folgenden wird sowohl näher auf die verwendete Steuerungsfunktion als auch die Zustandsbewertung eingegangen.

Steuerungsfunktion

Die Aufgabe dieses Moduls ist die Konvertierung der vom Optimierer übergebenen Parameter in entsprechende Steuerungsfunktion. Ihr zeitlicher Verlauf wird als Steuertrajektorie u(t) bezeichnet, welche im Allgemeinen eine vektorielle Größe darstellt. Im konkreten Fall besteht u dabei aus den Komponenten [δ(t),v(t)]T, also dem Lenkwinkel und der Fahrzeuggeschwindigkeit.

An den Verlauf von u werden zahlreiche Anforderungen gestellt. Zum einen optimiert die Steuertrajektorie auf mikroskopischer, reaktiver Ebene das resultierende Fahrgefühl, wobei neben einem komfortablen vor allem ein nachvollziehbares Verhalten erzeugt werden muss. Neben dieser offensichtlichen Auswirkung auf das Fahrverhalten besitzt u einen Einfluss auf die Robustheit, Stabilität und Konvergierungsgeschwindigkeit des zugrunde liegenden Optimierungsverfahrens.

Statt einer einfachen Polynominterpolation kommt beim TMP daher eine aufwändigere, jedoch auch mächtigere Splineinterpolation mit Polynomen fünfter Ordnung zum Einsatz: Aufgrund der zur Verfügung stehenden freien Parameter lässt diese bereits auf mikroskopischer Ebene die Minimierung einer Zielgröße Ju bei gleichzeitiger Einhaltung der Forderung zweifach stetiger Differenzierbarkeit zu. Die Wahl der Zielgröße hat dabei direkten Einfluss auf den Lösungsraum; bei entsprechender Auslegung können z. B. Überschwinger, ungewollte Auslenkungen und Oszillationen vermieden werden, bei Bedarf jedoch auch ein möglichst glatter, ruckminimaler Verlauf erzeugt werden. Je nach Einsatzzweck kann dies durch entsprechende Parametrierung erreicht werden.

Für Stadtfahrten implementiert der TMP die Steuergröße u als formerhaltenden Spline. Gründe für diese Designentscheidung liegen darin, dass zum einen ungewolltes Oszillieren verringert, zum anderen eine globale Stabilität bei Parametervariationen erreicht wird. Aufgrund der Notwendigkeit einer exakt zu bestimmenden Lösung sowie aus Performancegründen kommt zur Berechnung von u aus den übergebenen Parametern kein approximatives, iteratives Verfahren in Frage, wodurch gängige Algorithmen zur formerhaltenden Interpolation [12,13] nicht geeignet sind. Es wurde daher eine problemspezifische Rechenvorschrift entwickelt, welche durch ein entsprechendes Optimierungskriterium sowie adaptive Gewichtungsfaktoren die Anforderungen erfüllt. Neben der Forderung der C2-Stetigkeit, also der Gleichheit der Einzelpolynome und deren Ableitungen an den Randstellen, wird hierbei die zweite Ableitung des resultierenden Splines innerhalb eines 3 Punkte-Fensters über eine Kostenfunktion Ju minimiert. Dabei findet eine Gewichtung der beiden Intervalle abhängig von der Differenz der betrachteten Stützstellen statt, wobei zugunsten eines möglichst linearen Verlaufs benachbarte Stützstellen mit geringer Differenz mehr Beachtung finden. Somit ergeben sich mit

wobei

die Gesamtkosten innerhalb eines Fensters zu:

Auf dieser Basis wird ein Minimum Ju von in Richtung der freien Parameter bestimmt, so dass eine eindeutige Lösung für die Parameter der Splinesegmente resultiert. Die Integrationsgrenzen werden dabei zur Vereinfachung auf den Bereich zwischen 0 und 1 skaliert und sind somit unabhängig von der tatsächlichen Intervalllänge. Dies muss bei der Angabe der Ableitungen durch eine entsprechende Skalierung berücksichtigt werden.

Werden die Lenk- und Geschwindigkeitstrajektorie nacheinander bestimmt, die Geschwindigkeit also auf den gefahrenen Weg angepasst, resultiert im Fall der Interpolation des Geschwindigkeitsverlaufs eine topologisch nicht sortierbare Beziehung („Henne-Ei-Problem") zwischen der zu wählenden Skalierung und dem resultierenden zurückgelegten Weg, da bei der Planung der Lenktrajektorie von äquidistanten Wegstücken zwischen den Stützstellen ausgegangen wird. Soll der gefahrene Weg bei Ermittlung von uv(t) nicht mehr verändert werden, muss nun die zusätzliche Bedingung sf=∫0tfuv(t)dt eingeführt werden.

Fahrzeugmodellierung

Zur Bestimmung einer geeigneten Steuertrajektorie wird ein Fahrzeugmodell benötigt, dessen Komplexität vom jeweiligen Einsatzzweck abhängt. So können z. B. für hochdynamische Ausweichmanöver komplexere Modelle zu Lasten des Vorausschauhorizontes genutzt werden, deren Genauigkeit sich stark von einfachen geometrischen Modellen unterscheidet.

 Der Systemzustand kann beliebige Dimensionen annehmen; momentan wird dieser durch den Zustandsvektor X=[x,y,ψ,δ,w,as,js,v,av,jv] beschrieben, wobei a und j die Beschleunigung bzw. den Ruck des Lenkwinkels und des Fahrzeugs beschreiben und sicherstellen, dass Manöver konkateniert werden können.

Zur Modellierung der Systemdynamik wird für Stadtfahrten ein einfaches geometrisches Einspurmodell mit den Zustandsübergängen x=cosψ, y=sinψ und ψ=tanδ*l genutzt.

Zustandsbewertung

Das letzte Modul in der Wirkkette ordnet einem Systemzustand eine Metrik zu und bewertet darüber, ob dieser zulässig ist, bzw. weist ihm eine Maßzahl zu, die beschreibt, wie gut er ist. Dabei können Zustände sowohl an diskreten Stellen als auch kontinuierlich über den gesamten Verlauf überwacht werden. Eine besondere Herausforderung ist die kontinuierliche Formulierung eines Abstandsmaßes, welche daher im Folgenden näher erläutert wird.

Das Abstandsmaß wird für mehrere Basisfunktionen benötigt: Neben der Überprüfung von Kollisionsfreiheit und Einhaltung eines Mindestabstands kann es auch als Gütefunktion genutzt werden, etwa wenn ein fester Abstand zum vorausfahrenden Fahrzeug wie bei einem adaptiven Geschwindigkeitstempomaten eingestellt werden soll. Die Verwendung des reinen euklidischen Abstands eignet sich aufgrund fehlender C2-Stetigkeit nicht, weshalb eine Kombination aus semantischem, also euklidischem und Pseudoabstand entwickelt wurde. Außerhalb des Sicherheitsabstands von Objekten gilt dabei das semantische Maß, innerhalb das Pseudomaß, welches ausschließlich benötigt wird, damit der Optimierer einen Richtungstrend für die Parameter bestimmen kann. Folglich muss hier ein eindeutig definiertes Maximum existieren und der Abstand bis zu diesem streng monoton verlaufen.

Als Basis zur Formulierung von Objekten dienen konvexe Polygone. Um C2-Stetigkeit zu erreichen, müssen neben der Formulierung eines inneren Abstandsmaßes die naturgemäß auftretenden Unstetigkeiten des Abstands an den Eckpunkten der Polygone vermieden werden. Hierzu werden die Ecken über ein Polynom fünften Grades abgerundet, siehe Abbildung 2. Als äußerer Abstand kann somit prinzipiell das euklidische Maß herangezogen werden.

Das innere Maß definiert sich durch den relativen Abstand zum geometrischen Zentrum des Polygons. Um glatt zwischen den beiden Bereichen überblenden zu können, wird der Sicherheitsabstand genutzt. Die resultierende Zonentopologie ist in Abbildung 3, ein exemplarisches Abstandsmaß in Abbildung 4 dargestellt.

Da eine exakte analytische Bestimmung des Abstands zu den abgerundeten Eckpunkten aufgrund der Dimension der eingesetzten Polynome nicht möglich ist, wird stattdessen eine eindeutige Approximation genutzt. Der Abrundung wird dabei zunächst ein Radius r zugeordnet, wodurch sich deren Mittelpunkt C definiert. Anschließend wird der Schnittpunkt S der Geraden G, definiert durch und die Fahrzeugposition Px, bestimmt. Dieser kann durch eine Koordinatentransformation des Abrundungspolynoms analytisch berechnet werden. Durch Normierung mit r resultiert schließlich das Abstandsmaß.

Für die Kollisionsprüfung muss das berechnete Abstandsmaß noch in eine Straffunktion umgewandelt werden. Diese ist so ausgelegt, dass sie bei Unterschreiten des Sicherheitsabstands einen Wert größer 0 annimmt, für größere Abstände den Wert 0. Durch Integration der Straffunktion über den zurückgelegten Weg wird letztendlich die Kollisionsprüfung durchgeführt.

Sämtliche Berechnungen werden online durchgeführt und nicht über eine statische Belegungsmappe gegeben. Auf diese Weise geht keine Genauigkeit durch Interpolation verloren, das Maß eignet sich somit insbesondere für Manöver in begrenztem Raum, wie z. B. beim Parken. Für schnelle Fahrten können Hindernisse ggf. auch durch einfache Kreise approximiert werden.

4. Implementierung auf heterogenem System

Eine große Herausforderung bei der Realisierung einer Optimalsteuerung ist die Einhaltung der Echtzeitfähigkeit. Für die möglichst genaue Approximation der zu ermittelnden Integrale wird eine hohe Anzahl an Stützstellen mit nichttrivialen Berechnungsvorschriften benötigt. Das zugrundliegende Optimierungsverfahren zur Bestimmung der Parametrierung erfordert weiterhin die Gradienten erster und zweiter Ordnung in Richtung der einzelnen Parameter, wodurch bei n Parametern m=1+n+(n*(n+1)/2) Integrale zu lösen sind. Ein weiterer Einflussfaktor auf die Anzahl an Berechnungsschritten ist die Länge bzw. Dauer des Vorausschauhorizonts, welche vom jeweiligen Szenario abhängig ist.

In Anbetracht der Anforderungen an die Reaktionszeit von unter 20 Millisekunden kommt die Berechnung auf einer einzelnen CPU nicht in Frage. Da das Verfahren hohes Parallelisierungspotential bietet, wurden verschiedene Alternativen analysiert. Das beste Preis-/Leistungsverhältnis bei zugleich niedrigstem Energieverbrauch sowie die Nähe zur Serienreife bieten aktuell heterogene Systeme aus CPU und GPU (vgl. Audi zFAS mit Tegra K1), so dass dieser Ansatz schließlich weiterverfolgt wurde.

Programmiermodell

In der Entwicklung kommt eine GeForce GPU von Nvidia zum Einsatz, genauer eine Nvidia GTX 750Ti. Relevante Eigenschaften der Karte (siehe [14]) sind in Tabelle 1 aufgelistet. Gegenüber dem Vorgängermodell auf Basis der Kepler-Architektur ist besonders die Anzahl verfügbarer Register pro Thread hervorzuheben, welche von 63 auf 255 angehoben wurde, sowie der auf 64 kB angewachsene Shared Memory.

Im Folgenden wird auf die für das Verständnis des Kapitels notwendigen Grundlagen des Programmiermodells der Nvidia GPU mittels proprietärer CUDA C++ Erweiterung eingegangen. Für eine ausführliche Einführung wird auf die Fachliteratur verwiesen.

Grafikprozessoren besitzen eine Single Instruction Multiple Data (SIMD)-Architektur, d. h. dass sich alle Teilnehmer einer atomaren Ausführungseinheit einen Programmzähler (PC) teilen, durch separate Register jedoch auf unterschiedlichen Daten arbeiten können. Eine solche Einheit wird in CUDA als Warp bezeichnet und umfasst 32 Threads. Alle Threads innerhalb eines Warps laufen somit durch den gemeinsamen PC synchron.

Warps werden in Blöcken zusammengefasst. Ihre Ausführung ist nicht synchron, eine Ausführungsreihenfolge kann nicht festgelegt werden und ist somit als beliebig zu betrachten, was beim Datenzugriff ggf. beachtet werden muss. Innerhalb eines Blocks können Daten zwischen den Threads über den Shared Memory ausgetauscht werden; Synchronisierungen zwischen den Warps sind über entsprechende Anweisungen in Hardware möglich.

Mehrere Blöcke werden im sogenannten Grid zu einer Einheit zusammengeschlossen und können als solche die entsprechende Funktion, Kernel genannt, auf der GPU ausführen.

Einzelne Blöcke innerhalb eines Grids können auf die vorhandenen Streamingprozessoren (SMM) verteilt und die mittlere Last somit abhängig von der Anzahl an SMMs verringert werden.

Neben der geeigneten Zusammenarbeit der Ausführungseinheiten ist vor allem die effiziente Ausnutzung der Speicherarchitektur der GPU relevant für eine performante Programmausführung. Auf unterster Ebene liegen mit den schnellsten Zugriffszeiten die 32-Bit breiten Arbeitsregister, welche als Thread-lokal zu betrachten sind.

Die nächste Ebene stellt der Shared Memory dar. Der Speicher ist auf 32 Bänke mit einer Granularität von 4 Byte aufgeteilt, um potentiell alle Threads eines Warps gleichzeitig mit Daten versorgen zu können. Je nach Zugriffsmuster und Ausrichtung sind die angeforderten Daten innerhalb eines Zyklus verfügbar, wodurch sich der Shared Memory als Cache für größere Datenstrukturen eignet. Namensgebend ist die Eigenschaft, dass über diesen Speicher Daten zwischen den Threads ausgetauscht werden können; die Kommunikation ist dabei auf Blockgrenzen beschränkt.

Den größten Speicherbereich auf der GPU stellt der globale Speicher dar, dessen Zugriffszeiten deutlich über den bisher beschriebenen liegen. Durch den Einsatz verschiedener Caches und geeignete Zugriffsmuster kann die resultierende Latenz auf ein Minimum beschränkt werden, seine Verwendung resultiert jedoch in der Regel in einem starken Anstieg der Ausführungszeiten. Der globale Speicher stellt u. a. die Schnittstelle zwischen GPU und CPU dar – die CPU kann hierauf über spezielle Instruktionen zugreifen, um Daten zu senden und Berechnungsergebnisse zu erhalten. Daneben kommt globaler Speicher in zahlreichen anderen Fällen zum Einsatz, etwa bei Verwendung des Stacks, als temporärer Zwischenspeicher für Register – dem sogenannten Register Spilling – und zur Kommunikation über Blockgrenzen hinweg.

Als wichtiger Cachetyp sei zuletzt der Constant Memory genannt, in dem für die GPU nicht veränderbare Daten abgelegt werden können. Der Zugriff auf diesen Speichertyp ist schneller als auf den globalen Speicher; seine Größe beträgt 64 kB.

Programmablauf

Der Programmablauf des TMP ist in Abbildung 5 dargestellt. Während die CPU für die Ab-laufsteuerung sowie die Ausführung des Solvers zuständig ist, finden sämtliche Zustandsbe-rechnungen auf der GPU statt. Beim Design wurde darauf geachtet, die Kommunikation zwischen den beiden Partnern so schlank wie möglich zu gestalten, so dass nur ein minimaler Satz an Daten ausgetauscht werden muss.

Nachdem Start- und Zielzustand übergeben worden sind – das Ziel wird im Allgemeinen durch einen Gültigkeitsbereich beschrieben – werden die erkannten Hindernisse sowie der Streckenverlauf an den TMP gesendet. Hierauf findet auf Seiten der CPU zunächst einmalig

eine Präprozessierung statt, in der für die Berechnung der Abstandsmaße benötigte, konstante Informationen ermittelt werden. Im nächsten Schritt werden diese Daten an die GPU gesendet; um die Zugriffszeiten zu minimieren, wird hierfür der Constant Memory genutzt, auf die Daten kann somit innerhalb des Kernels nur lesend zugegriffen werden.

Sind alle Vorbereitungen getroffen, kann die eigentliche Optimierung beginnen. Der aktuelle Parametersatz, im ersten Schritt der initiale Schätzwert, in den Folgeschritten der jeweilige Lösungskandidat, wird in den Konstantenspeicher der GPU übertragen und der Kernel aufgerufen. Nach einer Initialisierungsphase wird zunächst die aus den Parametern resultierende Steuerfunktion interpoliert. Anschließend werden die direkt berechenbaren Zustandsgrößen bestimmt. Hier sind vor allem die zeitabhängigen Fahrzeugpositionen zu nennen. Ist diese höherwertige Information bekannt, können die positionsabhängigen Größen, also sämtliche Abstandsmaße, bestimmt werden. Zuletzt legt die GPU die ermittelten Resultate in den globalen Speicher, so dass sie von der CPU gelesen und an den Solver übergeben werden können. Dieser erstellt ein entsprechendes Gleichungssystem und berechnet abhängig vom Ergebnis die nächsten Lösungskandidaten.

Implementierung

Um eine performante Berechnung zu ermöglichen, ist eine effiziente Ausnutzung der vorhandenen Ressourcen der GPU essentiell. Allem voran stehen hierbei die Aufteilung auf Threads, Warps und Blöcke sowie die Verwendung des jeweils am besten geeigneten Speichers im Vordergrund. Im Folgenden wird kurz auf diese Aspekte eingegangen, für Details sei auf [15] verwiesen.

Im Fokus steht die Berechnung der einzelnen Einträge für die Hesse-Matrix, also die zweite Ableitung bezüglich der übergebenen Parameter. Aus Performancegründen empfiehlt sich auf der GPU ausschließlich die Verwendung von 32-Bit-Gleitkommaarithmetik, wodurch eine Berechnung der zweiten Ableitung mittels Differenzenquotienten aufgrund zu hoher Präzisionsverluste durch Auslöschung ausgeschlossen ist. Auch die Berechnung über die Complex-Step-Differentiation [16] stellt sich aus mehreren Gründen als ungeeignet heraus: Zum einen bedürfen abschnittsweise definierte Funktionen einer gesonderten Behandlung, zum anderen stellt auch hier der durch Subtractive-Cancellation verursachte Präzisionsverlust ein schwerwiegendes Problem dar. Diesem Sachverhalt kann durch Einsatz automatischer Differenzierung (AD) begegnet werden.

Aufgrund des erhöhten Speicherbedarfs verbietet sich die Verwendung des Rückwärtsmodus, bei dem zunächst ein vollständiger Programmdurchlauf aufgezeichnet werden muss. Stattdessen kommen hyperduale Zahlen zusammen mit entsprechenden Berechnungsvorschriften zum Einsatz [17]. Auf diese Weise müssen pro arithmetischem Operator vier Teil-berechnungen durchgeführt werden; als Nachteil gegenüber der Verwendung des Differenzenquotienten sowie des Complex-Step-Verfahrens stellt sich hierbei die fehlende Möglichkeit der Parallelisierung dar. Vorteilhaft ist, neben dem Erhalt des exakten Ergebnisses, dass neben der zweiten Ableitung zeitgleich der Funktionswert selbst sowie die erste Ableitung ohne Mehraufwand berechnet werden.

Die Implementierung stellt sich schließlich wie folgt dar: Innerhalb eines Blockes werden mehrere Warps zusammengefasst und sind für die Berechnung eines Eintrags der Hesse-Matrix verantwortlich. Je nach verwendeter GPU kann die Anzahl Blöcke sowie enthaltener Warps dabei variiert werden. Besitzt die Matrix mehr Einträge, als Blöcke vorhanden sind, werden die Berechnungen über eine Jobliste verteilt. Auf Thread-Ebene werden die einzelnen Stützstellen für die Bestimmung der Integrale berechnet. Aufgrund der Synchronität innerhalb eines Warps können diese, sofern keine Zwischenergebnisse benötigt werden, zunächst effizient reduziert werden [18], um anschließend auf Warp-Ebene nach einer Synchronisierung addiert zu werden.

Die Berechnungen finden soweit möglich auf Registerebene statt, werden Zwischenergebnisse im weiteren Verlauf benötigt, werden diese im Shared Memory abgelegt. Auf diese Weise wird der globale Speicher ausschließlich für den Datenaustausch zwischen CPU und GPU genutzt, was die Berechnungszeit zu minimieren hilft.

5. Ergebnisse

Das System wird derzeit in der Simulation getestet. Hierzu ist der TMP an einen Fahrsimulator gekoppelt und das generierte Lenkverhalten wird auf verschiedenen Straßenverläufen und Hinderniskonfigurationen untersucht. Um einen isolierten Test zu ermöglichen, wird kein spezifisches Verhalten durch eine höhere Instanz vorgegeben; Ziel ist das Abfahren einer Referenzkurve, welche durch die Mitte der Fahrspur gegeben ist.

Um die Berechnungszeiten zu minimieren, wird das System im Warmstart, d. h. mit guter Parameterschätzung gefahren. Hierfür wird der Straßenverlauf als bekannt vorausgesetzt und Werte aus dem aktuellen Optimierungszyklus auf die nächsten Positionen extrapoliert. Im Gegensatz zum Straßenverlauf werden Hindernisse erst kurzfristig erkannt und an den TMP übergeben, so dass der vorher berechnete Kurs kurzfristig angepasst werden muss. Auf diese Weise können das Verhalten realer Sensoren und die Auswirkungen auf die Berechnungszeiten nachgebildet werden. Die berechnete Steuertrajektorie beinhaltet aktuell ausschließlich den Lenkwinkel, die Geschwindigkeit wird als konstant angenommen.

Eingesetzte Kostenfunktion

Die resultierende Fahrtrajektorie ist aufgrund der Vielzahl freier Parameter stark abhängig von der gewählten Kostenfunktion. Für die Tests kommt eine Kombination aus Spurtreue und Krümmungsradius zum Einsatz. Über die Berücksichtigung des Radius kann dabei zum einen die Querbeschleunigung bei Kurvenfahrten minimiert werden, zum anderen findet eine Dämpfung des Lenkwinkels statt. Da große laterale Abweichungen wie z. B. Kurvenschneiden vom Fahrer nur bedingt toleriert werden, werden diese höher gewichtet als die resultierende Querbeschleunigung. setzt sich somit wie folgt zusammen:

Die Funktion Jdist(c)(t) verläuft in Abhängigkeit zum berechneten Abstand zur Spurmitte wie in Abbildung 6 dargestellt. Die Distanzbestimmung ist dabei analog zu den Hindernissen.

Die Toleranz um den Nullpunkt kann an das gewünschte Fahrverhalten angepasst werden; je nach Steilheit und Breite hat der Planer mehr Freiheiten zur Minimierung der mittleren Querbeschleunigung. Ist die Kurve entsprechend steil und wird in der Kostenfunktion hoch gewichtet, ergibt sich ein Curve-Fitting-Problem, so dass sich die resultierende Trajektorie so nah wie möglich an die Mitte der Spur anschmiegt.

Zielzustand

Der Zielpunkt liegt in jedem Berechnungsschritt in 67,5 m Entfernung, was 2/3 der Vorausschauweite von 90 m entspricht, der Abstand zwischen den einzelnen Stützstellen der Steuerfunktion, also den Parametern der Optimierung, liegt bei knapp unter 10 Metern. Die Integrationsschrittweite ist auf 10 cm eingestellt.

Neben der Minimierung der Zielfunktion wird das Erreichen des Zielzustands X=[x,y,ψ] unter Einhaltung der Kollisionsfreiheit gefordert. Um das Optimierungspotential zu erweitern sowie Schwingungen in der Steuerfunktion zu minimieren, wird während der Fahrt eine Abweichung der Endposition um 20 cm in Längs- und Querrichtung bzw. 3° in der Orientierung zugelassen. Soll ein fester Zielpunkt erreicht werden, kann diese Toleranz zur Laufzeit auf 0 herabgesetzt werden.

Trajektorienverlauf

Abbildung 7 zeigt die Ergebnisse der Simulation auf einem beispielhaften Kursausschnitt, welcher gerade Strecken, enge und weitere Kurven enthält. Durch die gewählte Parametrierung der Kostenfunktion fährt das Fahrzeug stets nah an der Referenzkurve, schneidet die Kurven somit nur marginal und benötigt wenig Platz zur Vorbeifahrt an Hindernissen.

Abbildung 8 zeigt den zugehörigen Lenkwinkelverlauf. Prinzipiell ist ein sehr glatter Verlauf ohne Spitzen oder starke Überschwinger zu sehen. Lediglich zu Beginn der Simulation oszilliert der Lenkwinkel leicht im Bereich von etwa 0,1°, was durch das verdrehte Aufsetzen des Ego-Fahrzeugs begründet ist. Auf der langen Gerade am Ende des Kurses bleibt die Steuertrajektorie stabil, sie schwingt hier im Bereich von wenigen hundertstel Grad um die Nulllinie.

Berechnungszeiten

Die Ermittlung der optimalen Steuertrajektorie für den obigen Kurs benötigt im Mittel 5 Iterationen, maximal, also beim plötzlichen Auftauchen von Hindernissen, bis zu 15. Die Berechnungszeit für eine Iteration hängt dabei vom jeweiligen Streckenabschnitt sowie der Anzahl zu berücksichtigender Hindernisse ab. Im Worst Case, also bei Ausfahrt aus der letzten Kurve und Berücksichtigung von 4 einzelnen Hindernissen, beträgt die Berechnungszeit für eine Iteration zwischen 950 und 1260 μs. Das Lösen des Gleichungssystems inklusive der Übertragung der Parameter von und zur GPU dauert pro Schritt knapp unter 100 μs; es ergibt sich eine Berechnungszeit von insgesamt 18,5 ms. Bei weniger komplexen Abschnitten sinkt die Ausführungszeit in den einstelligen Millisekundenbereich.

6. Zusammenfassung und Ausblick

Der Beitrag beschreibt ein neues, kontinuierliches Verfahren zur Bestimmung optimaler Steuertrajektorien auf Bahnführungsebene für Kraftfahrzeuge. Das als Tactical Motion Planner bezeichnete System ist dabei so ausgelegt, dass es in sämtlichen Anwendungs- und Dynamikbereichen eingesetzt werden kann und somit hilft, die Anzahl benötigter Planer zu reduzieren. Durch die Berücksichtigung von Hindernissen sowie des Fahrkorridors hebt der TMP das Niveau der Trajektorienplanung auf ein taktisches Niveau und trägt somit zur Re-duktion der Komplexität darauf basierender Assistenzsysteme und hochautomatisierter Fahrfunktionen bei. Die vorliegenden Ergebnisse zeigen, dass sich das resultierende Fahrverhalten dabei nachvollziehbar und komfortabel gestaltet.

Die Entwicklung des TMP ist weiterhin nicht abgeschlossen. Als nächster Schritt steht zum einen die kombinierte Optimierung der Längs- und Querdynamik an; zum anderen soll die Performance weiter gesteigert werden. Die geforderten 20 ms können in den meisten Fällen eingehalten werden, ohne die Ergebnisqualität zu verringern. Durch eine Optimierung der hinterlegten Berechnungsvorschriften soll jedoch noch ein vergrößertes Sicherheitspolster geschaffen werden.

Zusätzlich zu den Simulationstests wird der TMP bereits als informierendes System für die Platzierung eines Fahrzeugs über einer induktiven Ladespule eingesetzt [19]. Neben den oben genannten Weiterentwicklungen wird er zukünftig auch als Basiselement zur Entwicklung neuer FAS-Funktionen in das ika-eigene Forschungsfahrzeug SpeedE integriert. Als ein weiteres Entwicklungsziel steht dabei die Portierung auf automotivetaugliche Steuergeräte an.

Autor des Artikels:

Dipl.-Inform. J. Hudecek, Forschungsgesellschaft Kraftfahrwesen mbH Aachen

Ansprechpartner:

Dipl.-Ing. Axel Barkow, Forschungsgesellschaft Kraftfahrwesen mbH Aachen
http://www.fka.de