Auto-Pilot

Inhaltsverzeichnis

Autobahn-Cruiser wünschen sich schon lange eine Software, der sie auf Langstrecken das Steuer in die Hand geben können. Verstärkungslernen (Reinforcement Learning) ist ein ebenso interessanter wie viel versprechender Ansatz, Computer das Fahren zu lehren.

Langweilige Kolonnenfahrten und drögen Stadtverkehr könnte man wie andere stupide Tätigkeiten an eine Maschine delegieren, wenn es nur intelligente Systeme gäbe, die zuverlässig zwischen Fußgängern und Asphalt unterscheiden. Dem Computer das Autofahren beizubringen, gestaltet sich deutlich schwieriger als Fahrstunden für Menschen, dennoch funktioniert Verstärkungslernen für Computer auf demselben bewährten Prinzip von Belohnung und Strafe, das sich in jeglicher Form von Dressur bewährt hat.

Bild 1 von 10

Auto-Pilot (10 Bilder)

Bis zum autofahrenden Computer ist es noch ein langer Weg. Die Uni Siegen befasst sich schon seit längerem damit, ein autonomes Fahrsystem zu bauen.

Simulation mit „Need for Speed“

Die Uni Siegen, Institut für Echtzeit Lernsysteme unter Leitung von Prof. Klaus-Dieter Kuhnert, beschäftigt sich schon seit längerem damit, ein autonomes Fahrsystem zu bauen; ein System also, das letztendlich eigenständig Auto fahren soll. In der jetzigen Phase fährt es nur auf einem Simulator. Das hat nicht nur finanzielle Vorteile, auch die Lernsituationen lassen sich leichter anpassen und die Ergebnisse besser kontrollieren. Selbst die Simulatorsoftware stammt vom Discounter: Es ist „Need for Speed“. Das bekannte Rennspiel erwies sich aufgrund seines realistischen Fahrverhaltens als besonders geeignet.

Ein zweiter Rechner sitzt jetzt quasi an diesem ersten und spielt Autorennen. Nein, wirklich: Eine Kamera filmt das Bildschirmgeschehen für das Lernsystem ab; dieses wiederum gibt per Parallelport Joystick-Kommandos an den Spielerechner. Im Unterschied zu sonst oft unbezahlbarem Equipment kann diese Aufstellung jeder Garagenforscher nachbauen. Die anfangs eingesetzte Kamera ist mittlerweile einem SVHS-Kabel gewichen.

Straße im Blick

Computersteuerungen für Fahrzeuge haben zunächst alle ein gemeinsames Problem: Sie müssen ihre Umwelt korrekt aufnehmen und interpretieren. Menschliche Fahrer nutzen vorwiegend die Augen, für den künstlichen Chauffeur liegt also die Kamera nahe. Gemäß dem chinesischen Sprichwort „Ein Bild sagt mehr als 1000 Worte“ kann aus Videoinformationen eine Fülle an Informationen zur Umwelt entnommen werden; dabei ist aber auch die sinnvolle Extraktion dieser Daten aus einem Videobild diffiziler als etwa das direkte Abfragen von Positions- oder Distanzsensoren. Die meisten Fahrsysteme nutzen das Video als primäre Informationsquelle; die wichtigsten Werte sind dabei die Fahrbahnränder (siehe Kasten „Extraktion der Fahrbahnmarkierungen“) am Ende des Beitrags.

Anhand der nachgebildeten Fahrbahnmarkierungen soll ein Algorithmus nun ein der Situation angemessenes Verhalten produzieren. Dabei gibt es unterschiedliche Ansätze, die meistens auf Regelungstechnik oder neuronalen Netzen basieren. Zu diesen Verfahren gesellt sich seit einiger Zeit die Methode des Verstärkungslernens (Reinforcement Learning).

Belohnung und Bestrafung

Verstärkungslernen beruht auf dem Ansatz, dass Verhalten durch Belohnungen und Bestrafungen gelernt werden kann, selbst wenn diese nicht unmittelbar, sondern zeitlich versetzt erfolgen. Auch erlaubt Verstärkungslernen die permanente Verbesserung von Verhalten, es erlaubt also anders als klassische Verfahren das weitere Lernen im Fahrmodus. Verstärkungslernen zeigt deutliche Ähnlichkeiten zum Lernverhalten beim Menschen, und dieses wiederum wird in der „Triune-Brain“-Theorie gut erklärt.

Drei-Einigkeit im Geiste

Dr. Paul MacLean, Senior Research Scientist am National Institute of Mental Health in den USA, hat deutlich zum Verständnis des menschlichen Gehirns beigetragen. Seine „Triune-Brain“-Theorie [1] legt ein evolutionäres Modell zugrunde und beschreibt das menschliche Gehirn als Kombination von drei einzelnen Subgehirnen, dem Stammhirn (archipallium brain), dem Zwischenhirn (palleomammalian brain) und schließlich dem Großhirn (neopallium brain).

Auto-Pilot

Das Stammhirn ähnelt den Gehirnen einfacher Reptilien und kontrolliert grundlegende, instinktive und überlebensnotwendige Verhalten. Das Zwischenhirn ähnelt dem Gehirn einfacher Säugetiere und repräsentiert die Quelle von Gefühlen, emotionalem Verhalten, persönlicher Identität sowie Gedächtnisfunktionen für zeitkritische Verhalten. Das dritte und fast all-umgebende Gehirn ist das Großhirn - das Gehirn von weit entwickelten Säugetieren - und ermöglicht komplexe Gedankenvorgänge, gezielte Lernvorgänge, verbale Aussprache, rationales Denken, Kreativität und alles andere, auf das wir so stolz sind, seit wir uns nicht mehr von Ast zu Ast schwingen.

Stammhirn für die Grundbedürfnisse

Dr. MacLeans Forschung ergab, dass jedes der drei Gehirne die Kommunikation zum jeweils höheren Gehirn unterbinden kann. So ist das Stammhirn für die Grundbedürfnisse (Hunger, Schlaf, Überleben ...) verantwortlich. In extremen Situationen, in denen eines dieser Grundbedürfnisse nicht gedeckt ist, prägt ausschließlich das Stammhirn unser Verhalten. Es schaltet jegliche Weiterleitung der ankommenden Reize an das Zwischenhirn ab und übernimmt selbst die Kontrolle. In anderen Worten: Kurz vorm Verhungern lässt sich schlecht über Kants Vernunftkritik diskutieren.

Zwischenhirn entscheidet spontan

Das Zwischenhirn hat die Funktion, alle ankommenden Reize tendenziell positiv oder negativ zu bewerten und unmittelbare Reaktionen zu veranlassen. Im Verlauf der Evolution war dies entscheidend für das Überleben. Begegnete man plötzlich einem Raubtier, waren keine zeitintensiven Überlegungen durch das Großhirn gefragt, sondern eine spontane Entscheidung: Flucht oder Angriff. Auch in heutigen Situationen wird vom Menschen oft eine unmittelbare Entscheidung ohne lange Überlegensphase erwartet, etwa im Straßenverkehr, wo manchmal Bruchteile einer Sekunde über Leben oder Tod entscheiden.

In Ruhe denkt das Großhirn

Das Großhirn, das laut allgemeinem Verständnis eigentliche Gehirn des Menschen, kommt immer zum Einsatz, wenn keine lebensbedrohlichen oder zeitkritischen Umgebungsbedingungen vorliegen. Dann besteht die Möglichkeit, Verhalten zu analysieren und spontan falsche Reaktionen hinterher als schlecht zu vermerken. Diese Bewertungen werden im Zwischenhirn gespeichert und bewirken bei der nächsten Verhaltensbestimmung ein leicht korrigiertes Verhalten.

Verhaltensänderung braucht viele Impulse

Informationen im Zwischenhirn sind aber recht persistent, sodass erst die Masse der Lernimpulse zu einer echten Verhaltensänderung führt. Teilweise ist das Zwischenhirn bereits so stark geprägt, dass selbst eine Vielzahl an Impulsen keine Verhaltensänderung mehr einhämmern kann - ein Zustand, der mit Zunahme des Lebensalters verstärkt auftritt.

Für das autonome Automobil folgt aus dieser Theorie: Wenn insbesondere die (zeit)kritischen Verhalten beim Menschen durch das Zwischenhirn gesteuert werden, sollte dieses erst recht in nicht-kritischen Situationen über die Fähigkeit des Autofahrens verfügen. Im Lernsystem bewertet ein separates Modul ähnlich dem Großhirn die Aktionen. Die Logik hier stuft es als besser ein, in der Mitte der Fahrbahn zu bleiben; je mehr sich das Fahrzeug dem Rand nähert, umso schlechter wird die Bewertung. Gleichzeitig honoriert das Modul kurze Wegzeiten, um zu einem guten Mittelweg zwischen Geschwindigkeit und Spurtreue zu gelangen. Früher spielte ein Mensch dieses Äquivalent der Freundin auf dem Beifahrersitz und gab manuelles Feedback („Du fährst wie ein Idiot!“).

Situation und Verhalten

Den Kern des Verstärkungslernens bilden zwei Begriffe: Situation und Verhalten. Statt die Umwelt im Detail verstehen und analysieren zu wollen, werden beim Verstärkungslernen Situationen ermittelt. Um deren Anzahl nicht beliebig groß werden zu lassen, werden dabei ähnliche Elemente zu einer Referenzsituation zusammengefasst. Im Einsatz bei Fahrsystemen sind dies zum Beispiel die unterschiedlichen Streckenabschnitte (Geradenstück, Kurvenstück, Abzweigungen ...). Jeder Referenzsituation können nun beliebig viele Verhalten zugeordnet werden (Lenkung nach links, Lenkung nach rechts, Beschleunigung, Bremsen ...). Dies können eindimensionale Aktionen sein (wie lediglich Lenkung), zweidimensionale (Lenkung und gleichzeitige Geschwindigkeitsänderung), oder Verhalten höherer Dimension.

Auto-Pilot

Angenommen, ein Fahrzeug fährt mit hoher Geschwindigkeit in eine Linkskurve (Situation) und lenkt weiterhin geradeaus (Verhalten). Es kommt von der Fahrbahn ab prallt gegen die Leitplanke. Bei einem anderen Versuch in der gleichen Situation lenkt das System nach rechts und prallt ebenso gegen die Leitplanke. Schließlich versucht das System, in einem weiteren Versuch nach links zu lenken. Durch die hohe Geschwindigkeit kommt das Fahrzeug aber ins Schleudern und gerät ebenso an die Leitplanke. Ergo: man fährt mit hoher Geschwindigkeit nicht in Kurven - solch eine Situation ist immer schlecht. Damit kann das System aber auch die Verhalten vor der Kurve bewerten. Jede Beschleunigung vor einer Kurve führt damit in eine als schlecht bekannte Situation, daher wird ein solches Verhalten gleichfalls negativ gewertet. Verhalten, die vor einer Kurve eine hohe Geschwindigkeit vermindern, werden positiv bewertet.

Häufigkeit und Qualität

Im vorliegenden Fall wird also für eine aktuelle Situation die Gesamtmenge ähnlicher Situationen gesucht, die jemals vorher durchfahren wurden. Deren Verhalten (Aktion: Beschleunigung a und Lenkrad-Steuerwinkel φ) wurden bereits früher gespeichert und stehen nun als potenzielle Aktionen für die aktuelle Situation zur Verfügung. Jede dieser Aktionen verfügt aber zudem über einen Wert q(a_n,φ_n), der synonym für die Qualität (Angemessenheit) dieser Aktion für die gegebene Situation steht. Daher wird im Fahrmodus diejenige Aktion ausgewählt, deren q-Wert am höchsten ist.

Selbstbewertung

Verhalten und Situationen werden bewertet, und somit lernt das System, was wann wie angebracht ist. Ähnlich dem Lernprozess beim Menschen kann dies nur für Verhaltensweisen erfolgen, die auch tatsächlich ausgeübt wurden. Außerdem kann eine Bewertung oft nur mit einiger zeitlicher Verzögerung durchgeführt werden, denn eine Belohnung oder Bestrafung folgt nur selten unmittelbar auf ein Verhalten. Schwierig wird es immer dann, wenn nicht nur ein einzelnes Verhalten bewertet werden darf.

Im Beispiel, dass ein Fahrzeug in einer Kurve ins Schleudern gerät, gilt es also zu klären: Ist nur die letzte Lenkbewegung der Grund für das Scheitern oder nicht auch ein eventuelles Beschleunigen vor dem Eintritt in die Kurve? Beim Verstärkungslernen werden deshalb alle zurückliegenden Verhalten bewertet, allerdings umso schwächer, je länger sie zurückliegen. Bewertungen erfolgen immer kumulativ, das heißt, eine Gesamtbewertung wird weiter erhöht oder erniedrigt. Der Gesamtwert eines Verhaltens entscheidet dann über die Wahrscheinlichkeit, dieses in einer Situation wieder anzuwenden, denn das System lokalisiert lediglich das Verhalten mit dem höchsten Gesamtwert. Dies begründet den Namen der Methode. Gute Verhalten (positiver Gesamtwert) werden weiter positiv bewertet, und der Gesamtwert wird erhöht; der Gesamtwert schlechter Verhalten (negativer Gesamtwert) wird weiter erniedrigt. Es tritt also eine Verstärkung der Bewertungen ein, bis nach genügend Bewertungsdurchläufen die Gesamtwerte konvergieren (Linkslenken in einer Linkskurve wird sich als gutes Verhalten bewähren, Rechtslenken dagegen als schlechtes gebrandmarkt).

Mathematische Umsetzung

Diese Bewertungen erfolgen für jede mögliche Aktion in einer Situation und der Parameter der kumulierten Bewertungen wurde bereits vorher als q(a_n,φ_n) bezeichnet. Betrachtet man alle Parameter q aller Situationen, ergibt sich die Gesamtheit als q(Situation_m,a_n,φ_n) für m mögliche Situationen und n mögliche Aktionen pro Situation.

Laut Theorie des Verstärkungslernens repräsentiert der Parameter q die Summe aller zukünftigen Belohnungen r, wobei zukünftige Belohnungen durch den Faktor γ reduziert werden, um nahe Belohnungen stärker zu gewichten als ferne, Gleichung (1).

Die allgemeine Formel für Verstärkungslernen kann umgestellt werden in eine Beziehungsfunktion zwischen zwei Situationen, Gleichung (2).

Dies gilt genau genommen allerdings nur für den eingeschwungenen Zustand nach einer genügend hohen Anzahl von Bewertungen, damit die q-Werte jeder Aktion konvergiert sind. Im unkonvergierten Zustand enthält die Gleichung noch einen Fehlerwert TDerr, Gleichung (3).

Wenn man nun nach TDerr auflöst, erhält man einen Wert, der für das Update des q-Werts der Situationen zum Zeitpunkt t verwendet werden kann, um langfristig Konvergenz der q-Werte zu erreichen. Je besser die Konvergenz des Gesamtsystems, desto kleiner übrigens TDerr - am Verlauf dieses Fehlerwerts kann man daher den Status des Gesamtfortschritts beurteilen, Gleichung (4).

TDerr ist nun also die Basis für die Updates, die letztendlich für die Fähigkeit des Lernens verantwortlich sind. Damit sich das System während des Updates nicht aufschaukelt und somit eine Konvergenz verhindert, wird TDerr beim Update mit einem Faktor α(0<α<=1) vermindert. Um nicht nur die letzte, sondern auch alle weiter zurückliegenden Aktionen zu bewerten, die mitverantwortlich für die aktuelle Lage sind, wird TDerr mittels λ gedämpft auch für Updates weiter zurückliegender Aktionen verwendet:

Die Durchführung der Update-Funktion zeigt Gleichung (4).

In C++-Code sieht das Ganze wie folgt aus (Auszug):

/* Aktion mit dem höchsten [i]q-Wert auswählen und q als fQvalue vermerken. */
...;
// TDerr berechnen
fTDerr = (float) iReward + fGamma * fQvalue -fLastQValue; /* vorher ausgeführte Aktionen aus dem Protokoll prüfen */
for (i = (stHistoryProtocol.iArrayEntries - 1); i >= 0; i-)
{
/* Zeiger auf ausgeführte Aktion ermitteln */pstTemp = ...;
/* q aktualisieren und fTDerr verkleinern */pstTemp->fQValue += fAlpha * fTDerr; fTDerr *= m_fLambda;
}

/* Aktuelles q für die nächste Berechnung merken */fLastQValue = fQvalue;[/i]

Auto-Pilot

Exploration und Exploitation

Selbst wenn sich für jede Situation gute und schlechte Verhalten herauskristallisiert haben, stellt sich die Frage, ob sich unter den guten bereits das Optimum befindet. Deshalb wird das System im Normalfall ab und zu Neues ausprobieren (Exploration). Es wird sich am besten bekannten Verhalten orientieren und dies leicht modifizieren, ausüben und dann der anschließenden Bewertung zuführen. Auch dies funktioniert wieder analog zur menschlichen Eigenschaft, selbst bei bewährten Handlungsfolgen ab und zu neue Varianten auszuprobieren oder Bekanntes weiter zu optimieren.

Das System kann aber auch in einem konservativen Modus betrieben werden, in dem es gar nichts probiert. Es wird dann lediglich das beste bekannte Verhalten ausgewählt und unmodifiziert ausgeführt. Auch hier erfolgt eine Bewertung, es werden aber zu keinem Zeitpunkt neue Varianten generiert. Dieser Exploitation-Modus kann in kritischen Momenten sinnvoll sein, in denen man sich lieber auf bekanntes (gutes) Verhalten verlässt, als mit Herumprobieren ein Risiko einzugehen. Als Dauerzustand ist dieser Modus weniger empfehlenswert. Auch diese dauernde Ausnutzung bewährter Verhaltensweisen existiert beim Menschen und auch hier kann es kritisch sein, zu lange im Exploitation-Modus zu verweilen und sich einem weiteren Lernprozess zu verweigern.

Eigenständige Optimierung

Insgesamt zeigt ein Fahrsystem nach der Methode des Verstärkungslernens also über folgende Eigenschaften:

– Eigenständige Anpassung an Umwelt und Fahrzeug (denn ein Käfer auf Schotter fährt sich anders als ein Porsche auf Asphalt), somit echte Lerneigenschaften bezüglich des Fahrstils.

– Eigenständiges Ausprobieren neuer Fahrverhalten (Exploration Mode), somit eigenständige Optimierung des Fahrverhaltens.

– Das Fahrverhalten kann jederzeit quantifizierbar analysiert werden, die Beziehungen zwischen Verhalten und Situation sind für den Menschen eindeutig nachvollziehbar.

Einsatz!

Der Einsatz von vollständig fahrerlosen Systemen ist bisher auf Sonderanwendungen in speziellen abgetrennten Bereichen beschränkt, doch sind Szenarien im öffentlichen Verkehr denkbar. Andere wissenschaftliche Arbeiten haben einem Auto schon beigebracht, Parklücken zu erkennen und selbstständig einzuparken - damit könnte man in Zukunft auf menschliche Parkassistenten verzichten: das Fahrzeug übernimmt eigenständig das Navigieren durch Parkhaus oder -platz, findet einen Parkplatz und parkt ein. Das Ganze geht natürlich auch wieder rückwärts (Ausparken und Vorfahren). In einer ersten Stufe könnte ein Fahrsystem aber auch erst einmal nur die Spur halten helfen und übermüdete Fahrer akustisch oder haptisch wachrütteln, wenn sie die Spur wechseln, ohne zu blinken [2].

Diese Forschungsarbeit der Universität Siegen/Echtzeit Lernsysteme bietet Interessierten nicht nur die Möglichkeit, Fragen zur Thematik zu stellen, sondern auch einen vereinfachten C++-Code zur Thematik Reinforcement Learning oder den Schaltplan der Umschaltbox von Parallelport auf Gameport zu beziehen: Als Ansprechpartner dient Martin Stommel (stommel@fb12.uni-siegen.de). Bestimmt interessieren ihn auch intelligente Fahrsysteme, die andere Rennspiele zocken. (Clemens Gleich)

Literatur

[1] MacLean, Paul D., Evolution of Three Mentalities, Brain, Culture & the Human Spirit: Essays from an Emergent Evolutionary Perspective, Ashbrook, James B. ed. (Maryland: University Press of America, Inc., 1993), Seite 24

[2] Detlef Grell, Rad am Draht, c't 14/03, Seite 170

[3] Fahrbahnmarkierungen rekonstruieren, www.mkroedel.de/pdf-files/IECON2000.pdf

Auto-Pilot

Extraktion der Fahrbahnmarkierungen

Im Falle von Fahrsystemen, die sich entlang einer Fahrbahn bewegen, wird üblicherweise versucht, die Fahrbahnränder zu lokalisieren. Dazu werden die Bilder einer in Fahrtrichtung montierten Kamera in horizontaler Richtung nach Fahrbahnmarkierungen abgesucht. Vertikale Kontrastunterschiede sind wahrscheinlich Teil von Fahrbahnmarkierungen, können aber auch von Objekten auf oder neben der Fahrbahn stammen.

Während des Suchvorganges werden die Differenzen der einzelnen Farbkomponenten (Rot, Grün, Blau) von zwei durch wenige Pixel getrennte Bildpunkten ermittelt und zu einer Gesamtdifferenz addiert. Liegt diese Gesamtdifferenz über einem festlegbaren Schwellwert, ist der untersuchte Bildpunkt potenziell Teil einer Fahrbahnmarkierung. Um trotz Bildrauschens brauchbare Daten zu erhalten, können die RGB-Werte über mehrere Zeilen gemittelt werden.

Um im Folgenden Spreu von Weizen zu trennen, werden potenzielle Elemente von Fahrbahnmarkierungen einem Plausibilitätstest unterzogen, das heißt es wird mit Hilfe statischer Informationen zum typischen Verlauf von Fahrbahnmarkierungen versucht, diese Elemente zu verbinden. Gelingt dies nicht, werden die betreffenden Elemente verworfen; lässt sich dagegen eine Fahrbahnmarkierung in gewisser Länge rekonstruieren, wird diese gebildet und gespeichert. Details dazu sind unter [3] nachzulesen.

Die beiden unten stehenden Bilder zeigen zum einen eine Aufnahme einer im Fahrzeug montierten Videokamera und das Ergebnis der Bildverarbeitung, also die Nachbildung der Fahrbahnmarkierungen mit Fokussierung auf den relevanten Fahrbahnausschnitt und teilweiser perspektivischer Entzerrung (Aufstellung des Bildes in der Vertikalen). (ggo)