Embed Size (px)
Citation preview
HTWK Leipzig
Fachbereich Informatik,
Mathematik und Naturwissenschaften
Bachelorarbeit
Steuerung virtueller Verkehrsteilnehmer
durch gewichtete Beraterstimmen
Betreuung:
Prof. Dr. S. Schönherr
Dipl. Kfm. S. Kleinke
vorgelegt von
Marcus Frenkel
Leipzig, August 2007
2
Inhaltsverzeichnis
1. DAS PROJEKT ............................................................................................ 4
1.1. MOTIVATION ................................................................................................................4
1.2. ZIELSTELLUNG ..............................................................................................................5
1.3. ZUSÄTZLICHE BEMERKUNGEN .......................................................................................5
2. EINLEITUNG .............................................................................................. 7
2.1. KI IM ALLGEMEINEN .....................................................................................................7
2.2. EINSATZGEBIETE FÜR KI ...............................................................................................8
2.3. ARTEN VON KI..............................................................................................................9
2.3.1. Entscheidungsbäume/werkzeugbasierte Entscheidungsarchitekturen .................................9 2.3.2. Automaten/Finite State Machines .................................................................................... 10 2.3.3. Künstliche neuronale Netze ............................................................................................. 11 2.3.4. Regelbasierte Systeme/Agentensysteme .......................................................................... 12 2.3.5. Abstimmungsarchitekturen/Beratersysteme ..................................................................... 12
3. BERATERSYSTEME ................................................................................ 13
3.1. DAS BERATER-KONZEPT ............................................................................................. 13
3.1.1. Funktionsweise von Berater-Systemen ............................................................................ 15 3.1.2. Genereller Aufbau von Berater-Systemen........................................................................ 16
3.1.2.1. Der Controller ....................................................................................................................... 16 3.1.2.2. Die Berater ........................................................................................................................... 16 3.1.2.3. Der Mode-Manager ............................................................................................................... 17
3.1.3. Möglichkeiten der Befehlsbildung ................................................................................... 17 3.1.4. Analoge Befehlsbildung aus diskreten Abstimmungen .................................................... 20
3.2. BERATER IM VERGLEICH MIT ANDEREN SYSTEMEN ...................................................... 22
3.3. UNTERSCHIEDE ZWISCHEN BERATERN FÜR SOFTWARE- UND HARDWAREPRODUKTE ..... 22
3.3.1. Mögliche Funktionsweise einer Hardware-Berater-Struktur ............................................. 23 3.3.2. Mögliche Funktionsweise einer Software-Berater-Struktur .............................................. 23
3.4. DIE BERATER UND DIE FAHRSCHULE ........................................................................... 24
4. EIN BERATERSYSTEM FÜR DIE FAHRSCHULE.............................. 25
4.1. ANFORDERUNGEN AN DAS SYSTEM .............................................................................. 25
4.2. ERWEITERUNG DES URSPRÜNGLICHEN BERATER-KONZEPTES ....................................... 25
4.2.1. Die Aktionsbasis ............................................................................................................. 26 4.2.2. Der Zustandsspeicher ...................................................................................................... 27 4.2.3. Der Intentionenspeicher .................................................................................................. 27 4.2.4. Der Zielspeicher.............................................................................................................. 28 4.2.5. Die Charakterbeschreibung ............................................................................................. 28 4.2.6. Der Zustandsmanager ..................................................................................................... 28
3
4.2.7. Der Zielmanager ............................................................................................................. 29 4.2.8. Der Intentionenmanager innerhalb der Berater ................................................................ 29
4.3. GENERELLER AUFBAU DES SYSTEMS ........................................................................... 29
4.4. HAUPTMODULE ........................................................................................................... 30
4.4.1. Der Controller ................................................................................................................. 30 4.4.2. Die Berater ..................................................................................................................... 31
4.4.2.1. Sicherheitsberater ................................................................................................................. 31 4.4.2.2. Pfadhaltungsberater .............................................................................................................. 32 4.4.2.3. StVO-Berater ........................................................................................................................ 32 4.4.2.4. Wegfindungsberater .............................................................................................................. 33 4.4.2.5. Zielverfolgungs-Berater ........................................................................................................ 33
4.4.3. Der Mode-Manager ......................................................................................................... 33
4.5. HILFSMODULE ............................................................................................................ 34
4.5.1. Die Aktionsbasis ............................................................................................................. 34 4.5.2. Der Zustandsspeicher ...................................................................................................... 35 4.5.3. Der Intentionenspeicher .................................................................................................. 36 4.5.4. Der Zielspeicher.............................................................................................................. 36 4.5.5. Die Charakterbeschreibung ............................................................................................. 36 4.5.6. Die Manager ................................................................................................................... 36
4.6. BEFEHLSBILDUNG ....................................................................................................... 37
5. IMPLEMENTIERUNG............................................................................... 38
5.1. GENERELLES ............................................................................................................... 38
5.2. DIE CONTROLLER-KLASSE .......................................................................................... 38
5.3. DAS BERATER-INTERFACE .......................................................................................... 39
5.4. STRUKTUREN .............................................................................................................. 39
5.4.1. Aktionsbasis ................................................................................................................... 39 5.4.2. Die Speicher ................................................................................................................... 39 5.4.3. Charakterbeschreibung .................................................................................................... 40
5.5. DER ZUSTANDSMANAGER ........................................................................................... 40
5.6. DIE BERATER .............................................................................................................. 41
5.6.1. Sicherheitsberater............................................................................................................ 41 5.6.2. Pfadhaltungsberater......................................................................................................... 41 5.6.3. StVO-Berater .................................................................................................................. 42 5.6.4. Wegfindungsberater ........................................................................................................ 42 5.6.5. Zielverfolgungsberater .................................................................................................... 43
5.7. KI-VISUALISIERUNG ................................................................................................... 43
6. ZUSAMMENFASSUNG/AUSBLICK ...................................................... 46
6.1. ZUSAMMENFASSUNG ................................................................................................... 46
6.2. AUSBLICK ................................................................................................................... 46
7. QUELLENVERZEICHNIS ....................................................................... 47
4
1. Das Projekt
1.1. Motivation
Mit der Dartmouth Conference am 13. Juli 1956 (korrekterweise: mit dem Förderantrag von
John McCarthy 1955 an die Rockefeller Foundation für das Thema der Konferenz) wurde der
Begriff AI – „artificial intelligence“ („künstliche Intelligenz“) geprägt und erstmals in einer
Konferenz behandelt. Seitdem hat sich auf dem Gebiet der künstlichen Intelligenz viel getan
und es wurde viel erreicht; dennoch ist die KI als ein Forschungsbereich mit viel Potential zu
sehen, da noch eine Menge Fragen ungeklärt sind und die Entwicklung nicht ganz so rasant
fortschritt wie auf anderen Gebieten der Informatik, wie etwa der Grafikdarstellung oder der
Prozessorleistung. Dennoch – oder gerade deswegen – bietet die KI vielfältige Möglichkeiten
der Forschung, des Experimentierens und Ausprobierens sowie des Philosophierens.
Da künstliche Intelligenz etwas ist, was in allen möglichen Bereichen des Lebens eingesetzt
werden kann, ist dieses Fachgebiet auch entsprechend breit gefächert und teilweise ebenso
unbestimmt. Dies macht sich schon allein bei der Definition von KI bemerkbar – nicht nur in
der verbalen Definition sondern auch darin, was als KI gezählt wird (weitere Ausführungen
dazu in Kapitel 2). Gerade diese Vielfältigkeit macht aber den besonderen Reiz der
„denkenden Maschinen“ aus.
In viele Bereiche unseres Lebens hat die KI schon Einzug gehalten, auch wenn sie nicht
immer als solche erkennbar ist – man denke dabei nur an Navigationssysteme oder moderne
Auto-Computer, die selbstständig die Scheinwerfer einschalten und den Reifendruck prüfen.
Die aus der Science-Fiction bekannten Roboter allerdings gibt es in ihrer bekanntesten Form
als denkende, sprechende und laufende Droiden in der realen Welt noch nicht, auch wenn
fleißig an deren Erschaffung geforscht wird. Im digitalen Kosmos dagegen haben sie schon
festen Fuß gefasst: Computerspiele beherbergen jetzt schon komplexe Denkstrukturen, die
dank fehlender physikalischer Zwänge bereits dazu in der Lage sind, was echte Roboter wohl
erst in einigen Jahren können werden.
Die verwendeten Methoden zum Simulieren von Intelligenz sind dabei unterschiedlichster
Natur und erstrecken sich von simplen Entscheidungs-Bäumen über Algorithmen,
Wegfindungs-Routinen, Automaten, regelbasierten Agentensystemen und Beratersystemen
bis hin zu neuronalen Netzen. Aber nicht nur die Ansätze zum Realisieren der Intelligenz sind
unterschiedlich, auch die Ziele divergieren mitunter stark: wird da ein System entwickelt,
welches bestimmte Aufgaben automatisiert und fehlerfrei erledigen kann, soll dort dagegen
menschliches Verhalten mit all seinen Fehlern entstehen.
Im Rahmen dieser Arbeit soll eine Struktur vorgestellt werden, die das Simulieren
menschlichen Verhaltens ermöglichen soll, ohne dabei auf umfangreiche Regelwerke
angewiesen zu sein. Da bei regelbasierten Systemen das Problem auftritt, dass niemals alle
möglichen Situationen erkannt und mit entsprechenden Regeln abgedeckt werden können,
wird ein anderer Ansatz gewählt: der Einsatz von mehreren Beratern, die für eine gegebene
Situation verschiedene Aktionen bewerten und daraus dann einen resultierenden Befehl
bilden. Ziel ist es, das entwickelte System in dem unter 1.2. vorgestellten Projekt zur
Steuerung von Fahrzeugen im Straßenverkehr einzusetzen.
5
1.2. Zielstellung
Im Rahmen des Praktikums bei der Media Seasons GmbH wurde ein Projekt begonnen, das
als Ziel eine virtuelle Fahrschule hatte. Der Nutzer des Programms soll dabei ein Fahrzeug
durch eine digitale Stadt steuern können und dabei verschiedene aus dem realen Leben
entnommene Fahrsituationen bewältigen müssen.
Da ein wichtiger Bestandteil des Straßenverkehrs die „anderen“ Verkehrsteilnehmer sind,
wird dabei Wert auf eine dynamische und möglichst realistische KI gelegt. Die Fahrzeuge
sollen entweder zufällig umherfahren oder einem vorher festgelegten Pfad folgen können und
dabei die Verkehrsregeln einhalten. Wichtig hierbei ist das Simulieren menschlicher
Eigenschaften (Ungeduld, Zögern, …) und Charaktere – auf keinen Fall sollen sich alle
Verkehrsteilnehmer auf exakt die gleiche Art verhalten.
Als negatives Vorbild gilt hier das deutsche Konkurrenzprodukt auf dem Markt, die „3D
Fahrschule“, welche besonders durch das geskriptete Verhalten der Fahrzeuge auffällt – es ist
genau vorhersagbar, wie sich die Autos verhalten.
Als Vorgabe für die Programmierung wurde vor allem eine große Flexibilität gefordert, um
den Einsatz des Programms in vielen Ländern und mit unterschiedlichen
Straßenverkehrsordnungen zu gewährleisten.
Folgende Ziele sind mit der KI zu erreichen:
Dynamisches, nicht exakt vorhersagbares Fahrzeugverhalten
Unterschiedliche Verhaltensweisen der Verkehrsteilnehmer
Korrektes Verhalten, Einhaltung der „Regeln“ (Straßenverkehrsordnung), Umgang mit
den unterschiedlichsten Verkehrssituationen, ohne dass diese vorher formal
beschrieben werden müssen
Performantes System – da die Fahrschule als kommerzielles Projekt vertrieben werden
soll, muss eine guter Performance gewährleistet sein
Erweiterbarkeit – die KI muss einfach änderbar und erweiterbar sein
1.3. Zusätzliche Bemerkungen Die ursprüngliche Idee für das in der Fahrschule eingesetzte Berater-Konzept stammt aus
einem Bericht von Julio K. Rosenblatt, veröffentlicht im Journal of Experimental &
Theoretical Artificial Intelligence (Vol. 9, Numbers 2-3/April 1, 1997, Seiten 339 – 360) mit
dem Thema „DAMN – a distributed architecture for mobile navigation“ sowie dem davon
inspirierten Artikel „Eine Abstimmungsarchitektur für verteiltes Schließen“ von John
Hancock im Buch „Spieleprogrammierung Gems 4“ (Seiten 367 – 377). Aus den genannten
Artikeln wurden nur die theoretischen Basisgrundlagen benutzt. Jegliche Erweiterungen des
Konzeptes sowie die Implementierung sind eigene Entwicklungen.
Da der Begriff „Künstliche Intelligenz“ keiner scharf umrissenen Definition genügt und es die
unterschiedlichsten Meinungen darüber gibt, was unter künstlicher Intelligenz zu verstehen
sei, ist es angebracht, das Thema dieser Arbeit klarer zu definieren: im Rahmen dieser
Bachelor-Arbeit soll sich vor allem auf die Bereiche künstlicher Intelligenz bezogen werden,
6
die mit der Bewegung eines Objektes durch eine virtuelle oder reale Welt zu tun haben.
Genannt sei hierzu vor allem die Steuerung von Akteuren in Computersoftware (Spiele,
Simulationen und ähnliches) oder von Robotern in der physischen Welt.
Mit Objekt bzw. KI-Objekt ist demzufolge im Zuge dieser Arbeit in der Regel eine Entität
gemeint, die durch ein spezifisches KI-Konstrukt gesteuert wird, etwa eine Maschine oder
eine virtuelle Figur.
Als KI-Takt wird der Vorgang bezeichnet, in dem das KI-System seine Berechnungen
durchführt und Einfluss auf das von ihm gesteuerte Objekt nimmt.
Sämtliche in dieser Arbeit verwendeten Abbildungen sind selbst angefertigt worden.
7
2. Einleitung
In diesem Kapitel sollen grundlegende Dinge zum Begriff „künstliche Intelligenz“ geklärt
sowie häufig eingesetzte KI-Systeme vorgestellt werden.
2.1. KI im Allgemeinen
Der Begriff KI – Künstliche Intelligenz – wird heutzutage recht schnell und leichtfertig für
viele Dinge benutzt, die den Anschein erwecken, etwas mit Computern und Denken zu tun zu
haben. Dabei ist sich nicht einmal die Fachwelt richtig einig, was denn nun unter KI genau zu
verstehen ist und wie man den Begriff definiert.
Alan Turing zum Beispiel beschrieb 1950 den Begriff auf folgende Art:
Es werden eine Maschine und ein menschlicher Gegenspieler in Räumen
untergebracht, die jeweils getrennt von einem zweiten Menschen sind, der als Befrager
bezeichnet wird. Sowohl die Maschine als auch der Gegenspieler können nicht vom
Befrager gesehen oder direkt angesprochen werden. Die Kommunikation erfolgt über
ein Texteingabegerät, wobei der Befrager nicht weiß, wer die Maschine und wer der
Mensch ist. Ist es dem Befrager nun unmöglich, durch das Stellen von Fragen die
Maschine vom Menschen zu unterscheiden, so gilt die Maschine laut Turing als
„intelligent“. [Luger01]
Dieser Test wurde als Turing-Test bekannt und beeinflusste die Entwicklung der künstlichen
Intelligenz maßgeblich. So kann etwa ein Programm, dass in einem bestimmten Fachgebiet
potenziell Intelligenz erworben hat, durch den Vergleich mit einem menschlichen Experten
bewertet werden – eine Methode, die zu einem wichtigen Werkzeug in der Entwicklung von
Expertensystemen geworden ist. [Luger01]
Eine formalere und viel allgemeinere Definition für künstliche Intelligenz lautet:
Künstliche Intelligenz (KI) bzw. Artificial Intelligence (AI) ist ein Teilgebiet der
Informatik mit interdisziplinärem Charakter. Ziel der KI-Forschung ist die
Entwicklung von Maschinen mit intelligentem Verhalten. [Wiki06]
Betrachtet man aber alle Themengebiete, die sich heutzutage unter dem Stichwort „KI“
finden, so ist deren Umfang bei weitem größer als das, was durch obige Definition
beschrieben wird. So gehört zum Beispiel auch die Steuerung von Figuren in
Computerspielen zum Fachgebiet der KI, ebenso wie Muster- und Spracherkennung, mitunter
sogar Pfadfindungsalgorithmen.
Weitere Definitionen von künstlicher Intelligenz sind treffender, verdeutlichen aber auch
recht gut, dass es schwer ist, dieses Fachgebiet scharf zu umreißen.
8
Artificial Intelligence is the study of ideas which enable computers to do things, that
make people seem intelligent. [...] The central goals of Artificial Intelligence are to
make computers more useful and to understand the principles which make intelligence
possible. [Winston93]
Artificial Intelligence is the study of how to make computers do things at which, at the
moment, people are better. [Rich86]
KI studiert die Mechanismen, die intelligentem Verhalten zu Grunde liegen, durch die
Konstruktion und Evaluierung von Artefakten, die diese Mechanismen imitieren.
[Luger01]
Aus den Definitionen ist zu erkennen, dass das Gebiet der künstlichen Intelligenz schwer
abzugrenzen ist. Allen gemein ist folgendes: Gegenstand der KI ist die Erforschung von
Möglichkeiten, intelligentes Verhalten – im Besonderen von Menschen – zu simulieren.
2.2. Einsatzgebiete für KI
Die Einsatzgebiete für KI sind vielfältig und weitaus verbreiteter, als der Durchschnittsbürger
heutzutage annehmen mag, obwohl die künstliche Intelligenz in all ihren Ausprägungen
mittlerweile einen wichtigen Platz im Leben eines jeden hat. So findet sich KI in Robotern, in
der Steuerung von Fertigungsanlagen, in Computerspielen und Lernsoftware, in Autopiloten
und Navigationssystemen.
Künstliche Intelligenz kann dabei auf unterschiedlichste Art und Weise kategorisiert werden.
Im Rahmen dieser Arbeit und im Hinblick auf die Berater-Systeme sei hier die grobe
Unterscheidung in KI für Hardware-Produkte und KI für Software-Produkte angenommen.
Als Hardware-Produkte gelten alle Systeme, die direkt in der physikalischen Welt operieren
und deren Implementation ohne PCs auskommt. Software-Produkte sind diejenigen Systeme,
die eine virtuelle Welt auf einem PC simulieren oder deren KI-Berechnungen durch eine
Software auf einem PC durchgeführt wird.
Die Anforderungen an eine simulierte Intelligenz unterscheiden sich in diesen Bereichen zum
Teil erheblich.
In Hardware-Produkten, zum Beispiel Fertigungsanlagen, Autopiloten und ähnlichen
mechanischen Objekten steht in der Regel ein fehlerfreies Verhalten im Vordergrund. Oft
müssen dabei Sensor-Daten in vom Rechner verwertbare Formate mit einigem Zeitaufwand
umgerechnet werden, so dass es unter Umständen mehrere KI-Module mit unterschiedlicher
Taktung geben kann.
An KI in Software-Produkten, vornehmlich Computerspielen und Lernsoftware, werden
andere Anforderungen gestellt. So ist zum Beispiel nicht immer das fehlerfreie Verhalten
erwünscht, ab und zu soll sogar gezielt ein menschlicher Charakter mit allen Schwächen und
Fehlern simuliert werden.
9
In [Luger01] werden einige der wichtigsten Anwendungsgebiete für künstliche Intelligenz
aufgeführt. Die Kategorisierung erfolgt hier nach dem Anwendungsgebiet des Systems. Die
folgenden Gebiete werden genannt (ausführliche Beschreibung der Gebiete in [Luger01]):
- Spiele spielen
- Maschinelles Schließen und Theorembeweise
- Expertensysteme
- Verstehen natürlicher Sprache und semantische Modellierung
- Modellierung menschlichen Verhaltens
- Planung und Robotik
- Sprachen und Umgebungen für KI
- Maschinelles Lernen
- Parallele Verarbeitung und emergentes Rechnen
- KI und Philosophie
2.3. Arten von KI
Es gibt die unterschiedlichsten Arten, eine künstliche Intelligenz mit Hilfe von Soft- oder
Hardware zu implementieren. Nachfolgend sollen einige gängige Methoden vorgestellt
werden, welche so auch zum Einsatz kommen. Dabei werden jedoch nur KI-Systeme
berücksichtigt, die menschliches Denken und Handeln simulieren – Wegfindungsalgorithmen,
Mustererkennung und ähnliche Algorithmen werden also nicht mit aufgeführt. Zu beachten
ist, dass hier längst nicht alle Modelle aufgezählt werden, welche im Gebiet der künstlichen
Intelligenz zum Einsatz kommen – dazu sind es zu viele.
2.3.1. Entscheidungsbäume/werkzeugbasierte Entscheidungsarchitekturen
Entscheidungsarchitekturen sind die wohl ursprünglichste und einfachste Form von
künstlicher Intelligenz. Dabei lässt sich zwischen expliziten und impliziten Strukturen
unterscheiden (beides beschrieben in [Gems4]).
Explizite Entscheidungsarchitekturen oder Entscheidungsbäume sind dabei sozusagen der
Klassiker unter den KI-Systemen: mit Hilfe großer If-Else-Blöcke wird versucht, eine Anzahl
von möglichen Situationen durch Bedingungen zu beschreiben und mit bestimmten Aktionen
zu überdecken, um somit ein quasi-intelligentes Verhalten zu simulieren. Vorteil der Methode
ist, dass sie einfach zu implementieren und leicht in der Funktionsweise nachzuvollziehen ist.
Als Nachteil ergibt sich allerdings, dass mit wachsender Projektgröße die Bedingungs-
Strukturen immer unübersichtlicher werden. Zudem sind sie schwer wartbar, eine neu zu
beachtende Größe zieht oft weit reichende Änderungen in der Baumstruktur nach sich.
Implizite Entscheidungsarchitekturen bzw. werkzeugbasierte Entscheidungsarchitekturen
verstecken die Bedingungen mit den entsprechenden Aktionen hinter Objekten, welche
jeweils eine gewisse Priorität besitzen. Für eine bestimmte Situation wird einfach das Objekt
mit der für die Situation höchsten Priorität ausgewählt und die zugeordnete Aktion ausgeführt.
10
Durch das Hinzufügen neuer Aktions-Objekte kann der Umfang und das Leistungsvermögen
dieser KI-Architektur auf schnelle Art erweitert werden. Nachteilig ist allerdings anzumerken,
dass das spätere Verhalten der künstlichen Intelligenz aus dem Programmcode kaum noch
abgelesen werden kann und damit die Fehlersuche unter Umständen erschwert wird.
Unabhängig von der Wahl einer expliziten oder impliziten Implementierung ergeben sich für
beide Architekturen einige Charakteristika, die es zu beachten gilt. So sind
Entscheidungsarchitekturen in der Regel nicht in der Lage, ein oder mehrere längerfristige
Ziele zu verfolgen; sie eignen sich eher dafür, das intuitive, spontane Verhalten eines durch
die KI gesteuerten Objektes zu simulieren. Zudem ist es solchen bedingungsorientierten
Systemen – im speziellen den expliziten Strukturen – nicht möglich, auf unbekannte
Situationen zu reagieren, ihr Verhalten wird damit schnell vorhersehbar.
2.3.2. Automaten/Finite State Machines
Finite State Machines (Zustandsautomaten) stellen eine Erweiterung der
Entscheidungsarchitekturen da, bei denen jedoch weniger einzelne Aktionen als vielmehr das
gewünschte Verhalten (der Zustand) eines KI-Objektes beschrieben wird.
Zustandsgesteuerte Intelligenzen wechseln ihren internen Status je nach
Umgebungsbedingung in den einen oder anderen Zustand und führen die damit assoziierten
Aktionen aus. Dabei kann die Implementierung als Moore- oder Mealy-Automat erfolgen,
wobei ein Folgezustand eines Moore-Automaten nur vom aktuellen internen Zustand abhängt,
beim Mealy-Automaten aber auch noch von eventuellen externen Eingaben. [Huss07]
Eine weitere Möglichkeit der Implementierung wären die so genannten Fuzzy State
Machines, bei denen den Zustandsübergängen Fuzzy Werte zugeordnet werden, die Steuerung
also nicht mehr über harte Bedingungen erfolgt.
Ein Beispiel für einen einfachen Zustandsautomaten, der sich um das Fahrverhalten eines
elektrisch betriebenen Fahrzeuges kümmert, sähe zum Beispiel so aus:
Abbildung 1: einfache Finite State Machine (Mealy-Automat)
11
2.3.3. Künstliche neuronale Netze
Künstliche neuronale Netze sind zweifelsohne die „natürlichste“ Implementierung von
künstlicher Intelligenz, bei der versucht wird, die Funktionsweise des Gehirns auf einer
abstrakten Ebene zu simulieren. Das folgende Kapitel basiert auf den Beschreibungen von
[Patterson97].
Ein neuronales Netz besteht für gewöhnlich aus einer Menge von Eingangszellen (der
Eingabeschicht), einer Menge von Ausgabezellen (der Ausgabeschicht) sowie eventuell
verborgenen Zellen, die in dazwischen liegenden verdeckten Schichten (hidden layers)
angeordnet sind. Die Zellen simulieren die Neuronen eines Gehirns und sind über gewichtete
Kanten (Synapsen) miteinander verbunden. Die Art der Verbindung variiert dabei von Netz
zu Netz; so können etwa nur die Neuronen aufeinander folgender Schichten verbunden sein
(Feedforward-Netze), aber auch Verbindungen innerhalb der Schichten oder sogar
Verbindungen mit vorherigen Schichten (rekurrente neuronale Netze) sind möglich.
Soll das Netz Eingabedaten verarbeiten, müssen diese in Signale umgewandelt und an die
Eingangszellen geleitet werden. Von dort werden die Signale über die gewichteten Kanten an
die jeweilig verbundenen Zellen weitergeleitet, dort aufsummiert und nach einer definierten
Verarbeitungsfunktion transformiert. Anschließend erfolgt die Weiterleitung an die folgenden
Zellen, bis hin zur Ausgabeschicht. Das dort ankommende Signal kann schließlich
ausgewertet werden.
Die Verarbeitungslogik eines künstlichen neuronalen Netzes kann nicht in dem Sinne
programmiert, sondern muss dem Netz antrainiert werden. Auch hierfür gibt es viele
Möglichkeiten. Ein möglicher Ansatz wäre zum Beispiel: zu gegebenen Eingabedaten wird
die Ausgabe vom Netz berechnet und mit den zum Eingabesatz gehörenden Ausgabedaten
verglichen. Im Anschluss daran wird die Kantengewichtung innerhalb des Netzes zufällig
leicht variiert und der Test erneut durchgeführt. Bei verbessertem Ergebnis kann das neue
Netz „übernommen“ und weiter variiert werden, ansonsten müssen die vorhergehenden
Kantengewichte wieder hergestellt werden. Einen besseren Lernansatz stellt das
Backpropagation-Verfahren dar, bei dem die Variation der Kantengewichte nach einem
Algorithmus erfolgt, der gezielt eine Verbesserung des Netzverhaltens berechnet.
Ein Beispiel für ein einfaches Feedforward-Netz mit vier Eingabeneuronen, zwei
Ausgabeneuronen und einer verdeckten Schicht:
Abbildung 2: einfaches Feedforward-Netz mit drei Schichten
12
2.3.4. Regelbasierte Systeme/Agentensysteme
Regelbasierte Systeme können als moderne, verbesserte Entscheidungsarchitekturen
aufgefasst werden, bei denen die Bedingungen und durchzuführenden Aktionen nicht mehr in
einem klassischen Entscheidungsbaum festgehalten, sondern mit Hilfe einer Regelbasis
definiert werden. Die Regeln können auf unterschiedliche Arten hinterlegt sein, etwa in einer
XML-Struktur oder in einer Datenbank gespeichert. Durch Hinzufügen von Einträgen kann
die Basis auf einfachste Art erweitert werden, ohne am Programmcode etwas ändern zu
müssen.
Ein regelbasiertes System besteht im Wesentlichen aus zwei Komponenten [Winston92]: der
Datenbasis („working memory“), in welcher gültige Fakten des Systems gespeichert sind,
sowie einer Menge von Produktionsregeln (Regelbasis, „rule base“), welche zur Herleitung
neuer Fakten dient.
Die nächste Entwicklungsstufe regelbasierter Systeme sind die Agentensysteme, welche über
das bedingte Ausführen von Aktionen hinaus auch in der Lage sind, längerfristig Ziele zu
verfolgen, wobei das aktuell zu verfolgende Ziel wiederum durch die Auswertung gegebener
Regeln bestimmt wird.
Im Agentenkonzept werden vor allem drei Aspekte berücksichtigt [Beierle06]:
- Interaktivität mit der Umgebung: ein Agent interagiert kontinuierlich mit seiner
Umgebung durch Wahrnehmungen und Aktionen
- Zielgerichtetes Handeln: ein Agent hat eine Aufgabe zu erfüllen und verfolgt dazu
gewisse Ziele, die er selber generiert oder die ihm vorgegeben werden
- Autonomie: ein Agent arbeitet in gewissem Umfang selbstständig, das heißt er trifft
selber Entscheidungen ohne äußerliche Beeinflussung
2.3.5. Abstimmungsarchitekturen/Beratersysteme
Abstimmungsarchitekturen bilden einen alternativen Weg der künstlichen Intelligenz, der von
der menschlichen Neigung ausgeht, für eine Situation verschiedene Aktionen zu bewerten und
die Beste auszuwählen.
Anders als Menschen, die solch ein Verhalten in der Regel bewusst nur bei größeren
Entscheidungen mit genügend Zeit zum Nachdenken an den Tag legen, kann ein Computer
die Aktionen wesentlich schneller bewerten und somit auch einfachste Entscheidungen auf
diese Art treffen.
Die Bewertung einer Aktion erfolgt gewöhnlich mehrfach, und zwar von unterschiedlich
spezialisierten Beratern. Somit können zur Entscheidungsfindung mehrere Stimmen
herangezogen und aus allen Bewertungen die bestmögliche Aktion bestimmt werden
(basierend auf [Rosenblatt97]).
Im folgenden Kapitel soll auf diese Art der künstlichen Intelligenz genauer eingegangen
werden.
13
3. Beratersysteme
In diesem Kapitel wird die grundlegende Idee des Berater-Systems sowie die Bedeutung und
Funktionsweise der Hauptmodule des Systems geklärt.
3.1. Das Berater-Konzept
Ein großes Problem vieler KI-Konzepte ist der Umstand, dass sie meist zu einem Zeitpunkt
nur genau ein Ziel verfolgen können. Einige Systeme, etwa der Agenten-Ansatz, sind zwar in
der Lage, längerfristig mehrere Ziele verfolgen zu können, die Entscheidungsfindung für
auszuführende Aktionen berücksichtigt allerdings meist nur ein im Augenblick gewähltes
Ziel. Die Folge davon ist, dass für die aktuelle Situation möglicherweise die „beste“ Aktion in
Hinblick auf das gewählte Ziel durchgeführt, dabei aber entgegen mehrerer anderer zu
erreichender Ziele gehandelt wird.
Als Beispiel hierfür folgende Situation:
Ein KI-gesteuertes Fahrzeug soll sich von Punkt A nach Punkt B bewegen und dabei
eventuellen statischen und dynamischen Hindernissen ausweichen. Abbildung 3
skizziert dabei eine denkbare Situation.
Das KI-System wird eine mögliche Kollision mit dem statischen Hindernis feststellen
und einen Ausweichvorgang einleiten wollen. Dabei stehen zwei Möglichkeiten zur
Auswahl – links (Pfad A) oder rechts (Pfad B) am Hindernis vorbei. Klassische KI-
Systeme werden sich mit hoher Wahrscheinlichkeit für Pfad A entscheiden, da er
näher ans Ziel führt als Pfad B, welcher sich sogar vom Endpunkt entfernt. Das
dynamische Hindernis wird dabei unter Umständen gar nicht berücksichtigt, obwohl
abzusehen ist, dass es Pfad A schneiden wird und so zu einem möglichen
Zusammenstoß führen kann. Somit wäre zwar dem Ziel gedient, dass der Endpunkt
erreicht werden soll, die Vermeidung von Kollisionen aber wird in diesem Szenario
nicht berücksichtigt.
Alternative Systeme, welche aus allen möglichen Lösungsvektoren den Durchschnitt
bilden, führen in dieser Situation sogar zu einem noch katastrophaleren Ergebnis, da
der „neue“ Pfad direkt auf das statische Hindernis führen wird.
14
Abbildung 3: Situation für Pfadauswahl
Ohne eine größere, umständliche Abfrage-Struktur ist eine solche Situation von den meisten
KI-Systemen nicht ohne weiteres zu bewältigen, da unzählige Faktoren berücksichtigt werden
müssen.
Eine Lösung für das Problem bieten die Berater-Systeme, die durch eine Art von
„Aufgabenteilung“ ein weitaus größeres Spektrum an Situationen ideal abdecken können. Die
Idee dabei ist, die aktuelle Situation des KI-gesteuerten Objektes (konkreter: verschiedene
durch das Objekt durchführbare Aktionen) von mehreren unabhängigen Beratern bewerten zu
lassen, um aus diesen Bewertungen im Anschluss die durchzuführende Aktion zu bestimmen.
Die einzelnen Berater selbst können aufgrund ihrer Unabhängigkeit auf unterschiedliche
Arten implementiert werden, zum Beispiel als künstliches Neuronales Netz oder als
Agentenstruktur. Zusätzlich ist es möglich, Berater hinzuzufügen oder zu entfernen, um die
Funktionalität des Systems zu beeinflussen. So kann es beispielsweise Berater für
längerfristig zu erreichende Ziele geben, Berater, die für die Sicherheit des Objektes
verantwortlich sind, solche für kurzzeitig zu erreichende Ziele oder auch welche für das
forsche Erreichen der Ziele – die Möglichkeiten sind vielfältig (Grundkonzept der Berater
erstmals beschrieben in [Rosenblatt97], Berater-Begriff eingeführt in [Gems4]).
Abschließend ein Vergleich zwischen klassischen KI-Systemen und dem Beratersystem:
Klassisches System:
Die Situation eines Objektes wird von einer KI-Einheit bewertet und aus der
Bewertung die beste durchzuführende Aktion bestimmt.
Berater-System:
Es werden verschiedene mögliche Aktionen in Relation zur aktuellen Situation des
Objektes durch mehrere KI-Einheiten bewertet und aus der Gesamtheit der
Bewertungen die bestmögliche Aktion berechnet.
15
3.1.1. Funktionsweise von Berater-Systemen
Die Grundlage für das Funktionieren von Berater-Systemen bildet wie bei fast allen KI-
Konzepten das Sammeln der Daten über das Objekt, in der Regel durch Auswertung von
Sensoren bei Hardware-Objekten (dazu gehören zum Beispiel auch Mustererkennung oder
bild- und audioverarbeitende Maßnahmen) beziehungsweise durch Auswertung von im
Programm gespeicherten Strukturen (Listen, Netzen, Bäumen und ähnliches) bei Software-
Objekten. Die Daten müssen dabei in einer Form gespeichert werden, welche die effiziente
Verarbeitung durch die Berater ermöglicht.
Bei der Erstellung eines KI-Objektes wird ihm ein Controller zugewiesen, welcher
verschiedene Berater verwaltet. Im laufenden Betrieb werden dann durch den Controller
nacheinander die Berater zu den verfügbaren Aktionen befragt. [Gems4]
Eine Aktion1 besteht hierbei aus folgenden Teilen:
- Identifizierung der zur Aktion gehörenden Tätigkeit (etwa der Lenkeinschlag)
- Intervall von Werten, in dem die Tätigkeit ausgeführt werden kann (zum Beispiel der
maximal mögliche Lenkeinschlag nach links und rechts)
- Schrittweite für das Wertintervall
Durch Ablaufen des Werteintervalls mit der spezifizierten Schrittweite ergeben sich mehrere
diskrete Aktions-Konfigurationen, im Weiteren als Befehl bezeichnet. Ein möglicher Befehl
mit der Bedeutung, dass leicht nach rechts gelenkt werden soll, wäre etwa:
Tätigkeit: Lenken
Wert: 0.2
Die Berater liefern zu allen Befehlen einer Tätigkeit eine Bewertung zurück, welche sich in
der Regel im Intervall -1 (stark dagegen) bis 1 (stark dafür) befindet. Ausnahmen können hier
durch Berater gemacht werden, die durch stark überhöhte Werte ein Veto gegen
sicherheitskritische Befehle einlegen oder sicherheitsrelevante Befehle bevorzugen. So
entsteht für jeden Berater ein diskretes Signal aufeinander folgender Bewertungen [Gems4].
Im letzten Schritt, der Befehlsbildung, wird aus allen Berater-Signalen der auszuführende
Befehl ausgewählt. Die Befehlsbildung kann dabei auf unterschiedliche Art erfolgen und wird
unter 3.1.3. Möglichkeiten der Befehlsbildung näher erläutert. Zu beachten ist dabei, dass die
Berater unterschiedlich gewichtet sein können, um so bestimmten Beratern Vorrang vor
anderen zu geben. Die Gewichtung der Berater kann durchaus auch dynamisch sein, um so
situationsbedingt verschiedenen Beratern eine wichtigere Rolle zuzuweisen. [Rosenblatt97]
Der Befehl schließlich wird durch den Controller an das KI-Objekt weitergeleitet und von
diesem dann ausgeführt.
Abbildung 4: Schema eines Berater-Systems
1 Aktion und Befehl sind selbst eingeführte Begriffe/Strukturen und werden nicht in [Rosenblatt97]/[Gems4] erwähnt.
16
3.1.2. Genereller Aufbau von Berater-Systemen
3.1.2.1. Der Controller
Der Controller (im Dokument von Rosenblatt „Arbiter“ genannt) bildet das organisatorische
Zentrum eines Berater-Systems. Er verwaltet die Berater, sendet die Anfragen zu den
Aktionen an diese und bildet aus den erhaltenen Signalen schließlich den auszuführenden
Befehl. Außerdem ist er für die Beachtung der vom Mode-Manager bestimmten
Gewichtungen (siehe unten) und die Weiterleitung der Befehle an das KI-Objekt
verantwortlich. Der Controller bestimmt zudem auch das allgemeine Verhalten des Systems
(vorsichtig, optimistisch) durch die Wahl der Auswertungsfunktion zur Befehlsbildung (siehe
dazu auch 3.1.3. Möglichkeiten der Befehlsbildung).
Controller können in zwei unterschiedliche Kategorien gefasst werden, je nach dem ob sie frei
von Wissen über das kontrollierte Objekt sind (bereichsunabhängig) oder nicht
(bereichsabhängig) [Gems4].
Ein Controller wird dann bereichsunabhängig genannt, wenn er die gebildeten Befehle direkt
an das KI-Objekt weiterleiten kann und nicht erst eine Transformation durchführen muss.
Bereichsabhängig dagegen wird er genannt, wenn die Befehle nicht vom KI-Objekt direkt
interpretiert werden müssen, sondern vorher eine Umrechnung stattfindet.
Als Beispiel:
Gegeben sei ein Controller, der die Steuerung eines Kranarmes zur Aufnahme von
Objekten für bestimmte Aufgaben übernimmt. Ein bereichsunabhängiger Controller
würde die Berater (welche selbst immer bereichsabhängig sind) nach den Werten der
möglichen Einstellwinkel des Kranarmes befragen, die zur Aufnahme des aktuell
geeignetsten Objektes führen würden. Er selbst müsste keine Informationen über die
Objekte in seiner Umgebung haben. Ein bereichsabhängiger Controller dagegen würde
die Berater direkt nach den möglichen Objekten in der Umgebung fragen und die
Einstellwinkel des Kranarmes für das beste Objekt selber berechnen.
3.1.2.2. Die Berater
Die Berater (bei Rosenblatt „Verhalten“ beziehungsweise „Behaviors“ genannt) sind die
Herzstücke des Systems. Ihre Aufgabe ist es, die vom Controller gesendeten Aktions-
Anfragen zu bewerten und zu beantworten. Zur Bewertung betrachtet ein Berater die aktuelle
Situation des zugehörigen KI-Objektes und gibt für jeden Wert der Aktion eine Stimme ab
(Idealerweise im Intervall von -1 bis 1). Die Bewertung erfolgt dabei in Abhängigkeit des
Aufgabenbereichs eines Beraters. Sollen bestimmte Befehle bevorzugt oder auf keinen Fall
ausgeführt werden, kann die Bewertung mit einer weit außerhalb des Intervalls [-1,1]
liegenden Stimme erfolgen [Gems4].
Die Art der Bewertung – konkret: die Implementation des Beraters – kann dabei auf
unterschiedlichste Arten erfolgen; es sind sogar verschiedene Umsetzungen innerhalb eines
17
Controllers möglich. So wäre es beispielsweise denkbar, dass ein Berater eines Systems als
Entscheidungsbaum programmiert wird, ein weiterer als künstliches neuronales Netz, ein
dritter dagegen als Agent und ein letzter gar wieder als eigenes Berater-System.
Die günstigste Art der Implementation ist abhängig von der Aufgabe des Beraters sowie der
Umgebung des KI-Objektes.
Berater sind im Gegensatz zu Controllern immer bereichsabhängig, da sie die Situation des
KI-Objektes für die Signalbildung bewerten müssen. Um eine möglichst optimale
Befehlsbildung durch den Controller zu ermöglichen, ist es für die Berater wünschenswert,
wenn die Bewertungen der Werte einer Aktion durch eine stetige Funktion erfolgt (siehe dazu
auch 3.1.3. Möglichkeiten der Befehlsbildung und [Gems4]).
3.1.2.3. Der Mode-Manager
Die Aufgabe des Mode-Managers ist es, die Gewichtungen der dem Controller zugeordneten
Berater zu steuern. Die Gewichtung dient zum Steuern der Prioritäten eines Berater-Systems.
Abhängig von der aktuellen Situation kann es dabei nötig sein, die Gewichtung der Berater zu
variieren [Rosenblatt97] [Gems4].
Ein Beispiel:
In einem strategischen Computerspiel gibt es mehrere Berater mit Aufgabengebieten
wie Stadtausbau, Verkehr, Militärverwaltung, Finanzen, Bevölkerungszufriedenheit
oder Forschung. Ein Computerspieler wird je nach gewähltem Charakter ein anderes
Teilgebiet bevorzugen. Populistische Spieler konzentrieren sich bevorzugt auf die
Zufriedenheit der Bevölkerung, technokratisch angehauchte favorisieren dagegen eher
das Gebiet der Forschung. In Abhängigkeit der befürworteten Teilgebiete setzt der
Mode-Manager die Gewichtungen der Berater.
Ändert der Computerspieler jetzt aber seine Gesinnung, müssen die Gewichtungen neu
verteilt werden. Zusätzlich kann eine akute Bedrohung ein Umdisponieren erfordern;
so muss etwa dem Militärberater zeitweise eine höhere Priorität gegeben werden,
wenn das Gebiet des Computerspielers durch eine fremde Armee bedroht wird.
3.1.3. Möglichkeiten der Befehlsbildung
Die in diesem Kapitel beschriebenen Methoden und Techniken zur Befehlsbildung beruhen
auf der in [Gems4] beschriebenen Funktionsweise, die Formeln sind selbst aufgestellt.
Um aus allen Berater-Signalen geBeratermenibbbS iii
i },,,{ 321 ( i
jb ist die Bewertung
des Befehls mit dem Wert jteSchrittwei * durch den Berater i ) einer Tätigkeit den tatsächlich
auszuführenden Befehl zu bestimmen, werden die einzelnen Befehls-Bewertungen i
jb der
Signale mittels einer Auswertungsfunktion f verknüpft.
18
Das neue Signal },,{ 321 neuneuneu
neu bbbS ergibt sich dann folgendermaßen:
),,,(: 321 jjj
neu
j bbbfbgeBefehlsmenj
Aus dem neuen Signal wird das Maximum )(maxmax neu
jj
k bb extrahiert und der zugehörige
Wert kteSchrittwei * als Wert für den auszuführenden Befehl benutzt.
Für die Auswertungsfunktionen f kann es unterschiedliche Ansätze geben. Abhängig vom
Ansatz wird das Verhalten des Systems (sein Charakter) variieren.
Im Folgenden sollen drei Auswertungskriterien näher erläutert werden:
Maximax-Kriterium
Aus allen eingehenden Beraterstimmen werden die mit dem höchsten Wert als relevant
ausgewählt. Das Maximax-Kriterium ist dem Charakter nach ein optimistisches
beziehungsweise risikofreudiges Kriterium, da immer der Befehl mit der besten
Bewertung benutzt wird.
)(max),,,( 321 i
ji
jjj
neu
j bbbbfb
Maximin-Kriterium
Aus allen eingehenden Beraterstimmen werden die mit dem niedrigsten Wert als
relevant ausgewählt. Das Kriterium ist dem Charakter nach eher risikoscheu, da der
Befehl mit der am wenigsten schlechten Bewertung genutzt wird.
)(min),,,( 321 i
ji
jjj
neu
j bbbbfb
Maxsum-Kriterium
Das Maxsum-Kriterium summiert alle Beraterstimmen für einen Wert auf, das
entstehende Signal ist also die Summe der Beraterstimmen. Da bei diesem Kriterium
alle Stimmen in die Bewertung eingehen, ist es besonders für sicherheitskritische
Anwendungen geeignet, da nicht geeignete Befehle durch Sicherheitsberater mit
einem Veto belegt werden können und bei der Aufsummierung dann nur eine sehr
geringe Bewertung erhalten.
i
i
jjjj
neu
j bbbbfb )(),,,( 321
Da eine gleichmäßige Stimmverteilung zu einer besseren Auswahl des Befehls führt (ähnliche
Befehle einer Aktion sollten ähnliche Bewertungen durch einen Berater erhalten), werden
entweder die Beraterstimmen durch eine stetige Funktion generiert oder die Signale vor ihrer
Verknüpfung mit einem Tiefpassfilter (zum Beispiel einem Gauß-Filter) behandelt, um sie zu
glätten.
Zusätzlich gehen die einzelnen Berater-Signale mit unterschiedlicher Gewichtung in die
Verknüpfung ein, um so zum Beispiel sicherheitsrelevanten Beratern höheres Stimmrecht
einzuräumen. [Gems4]
Im Folgenden soll beispielhaft ein System gezeigt werden, welches aus drei
gleichgewichteten Beratern besteht und eine Aktion bearbeitet, deren Intervall [-1,1] ist und
eine Schrittweite von 0.1 besitzt.
19
Die erste Abbildung zeigt die von den drei Beratern generierten Signale, die Abszisse
bezeichnet das Intervall der Aktion mit der zugehörigen Schrittweite, die Ordinate entspricht
den zugehörigen Bewertungen durch den Berater. Jeder diskrete Wert auf der Abszisse (mit
dem Abstand der Schrittweite) entspricht einem möglichen Befehl.
Die drei nachfolgenden Abbildungen zeigen jeweils das Ergebnis unterschiedlicher
Auswertungsfunktionen.
Abbildung 5: mögliche Beraterstimmen
Der Controller, der das Minimum der Stimmen maximiert (Maximin-Kriterium) wird sich für
einen Befehl mit dem Wert -0.4 entscheiden, da dort das Signal sein Maximum erreicht.
Abbildung 6: Maximin-Kriterium
20
Der Maximax-Koordinator wird sich dementsprechend für einen Befehl mit dem Wert von 0.5
oder 0.6 entscheiden. Welcher von beiden ausgewählt wird, hängt dabei von der
Implementation des Controllers ab.
Abbildung 7: Maximax-Kriterium
Der Maxsum-Koordinator kann zwischen den Befehlen mit den Werten -0.3 und 0.4 wählen.
Abbildung 8: Maxsum-Kriterium
3.1.4. Analoge Befehlsbildung aus diskreten Abstimmungen
Dieses Kapitel beruht auf den Aussagen in [Rosenblatt97] und [Gems4], welche die
Genauigkeit diskreter Befehle sowie die analoge Befehlsbildung aus diskreten Signalen
betreffen.
Die von den Beratern generierten Stimmen sind strukturbedingt diskrete Signale mit einer
endlichen Auflösung. Als Resultat dessen kann es passieren, dass der vom Controller
berechnete auszuführender Befehl nur bedingt dem eigentlich besten Befehl entspricht.
21
Eine Lösung des Problems wäre es, die Auflösung der generierten Signale zu erhöhen, in dem
man die Schrittweite der zugehörigen Aktion verringert. Unweigerliche Folge dessen wäre
aber ein erhöhter Rechenaufwand.
Einen besseren Ansatz bietet die Befehlsfindung mit Hilfe der quadratischen Interpolation.
Dazu muss zuerst wieder das Maximum kb der verknüpften Beraterstimmen an der Stelle k
gefunden werden (siehe vorheriges Kapitel). Zusätzlich wird noch der jeweils links und rechts
des Maximums liegende Stimmwert (1kb und
1kb ) mit der zugehörigen Stelle )1,1( kk
benötigt (am Anfang und Ende des Signals muss deren Vorhandensein durch geeignete
Formalismen gewährleistet werden, etwa durch Spiegelung des vorhandenen komplementären
Wertes 1kb bzw.
1kb ). Durch die drei erhaltenen Punkte wird eine quadratische Gleichung
der folgenden Form beschrieben, die ihr Maximum im Intervall ]1,1[ kk hat:
xxxf **)( 2
Durch Einsetzen der Werte 1k , k und 1k sowie der zugehörigen Funktionswerte )(xf
können die Parameter und bestimmt werden (Anmerkung: Auf die Herleitung der beiden
Parameter wird aufgrund der Länge und Unübersichtlichkeit der Formeln im Zuge dieser
Arbeit verzichtet.). Das Maximum der dadurch gegebenen Parabel befindet sich an der Stelle
0*2)'()(
xxfx
xf
Der optimale Wert für den auszuführenden Befehl ergibt sich somit zu
2
optimalx
Sind alle drei Werte 1kb , kb und 1kb gleich, muss der Wert des Befehls auf ein
]1,1[ kkk festgelegt werden.
Abbildung 9: Quadratische Interpolation
22
3.2. Berater im Vergleich mit anderen Systemen
Berater-Systeme beschränken sich im Gegensatz zu anderen KI-Systemen nicht auf eine
einzige Art der Implementierung sondern gestatten für jedes ihrer Teilsysteme eine eigene Art
der Einbindung. Dadurch kann je nach zu lösender Aufgabe eine optimale
Problemlösungsstrategie verfolgt werden, deren Effektivität durch das Zusammenspiel mit
anderen Implementierungsmethoden sogar noch erhöht werden kann.
Durch die Aufteilung der Situationsbewertung auf mehrere untergeordnete Module ist es dem
Berater-System möglich, ohne eine komplizierte Abfragelogik mehrere Ziele zur gleichen
Zeit zu verfolgen. Da jeder Berater eigene Ziele verwirklichen will und die Befehlsbildung
aus der Verknüpfung mehrerer Beraterstimmen erfolgt, ist die Beachtung mehrerer
Zielstellungen implizit gewährleistet. Der große Vorteil gegenüber anderen Systemen (etwa
dem Agenten-Ansatz, welcher auch mehrere Absichten verfolgen kann) ist die gleichzeitige
Berücksichtigung der Ziele.
Ein weiterer Unterschied zu gängigen Systemen ist die Herangehensweise an die
Befehlsbildung. Gewöhnlicherweise wird die Situation des Objektes bewertet und aus dieser
Bewertung eine optimale Aktion bestimmt. Berater-Systeme wählen den umgekehrten Weg:
verschiedene mögliche Befehle werden erwogen und bewertet; aus allen möglichen
Bewertungen wird dann der beste auszuführende Befehl bestimmt, wobei die eigentliche
Befehlsbildung selbst völlig unabhängig von der Situation ist und nur von den abgegebenen
Stimmen der Berater beeinflusst wird.
Durch den modularen Aufbau ist es zudem möglich, ohne Strukturänderungen neue Aktionen
und Berater in das System zu integrieren. Komplizierte Anpassungen des Programmcodes,
wie sie zum Beispiel beim Erweitern eines Entscheidungsbaumes zwangsläufig nötig sind,
entfallen hierbei komplett.
Einen gravierenden Nachteil gibt es trotzdem: die vielfache Bewertung der Objekt-Situation
zieht bei ungünstiger Implementation der Berater unweigerlich Performanceeinbußen nach
sich. Aus diesem Grund muss die Implementation mit äußerster Sorgfalt und im Hinblick auf
bestmöglichste Performance erfolgen.
3.3. Unterschiede zwischen Beratern für Software- und Hardwareprodukte
Berater-Systeme eignen sich sowohl für Hard- als auch für Softwareprodukte, jedoch sind je
nach Einsatzgebiet bestimmte Rahmenbedingungen für die Implementation zu beachten. Vor
allem die benötigte Zeitdauer zum Umrechnen von Sensordaten in durch die Berater
auswertbare Informationen bei Hardwareimplementationen zieht gewisse Unterschiede in der
Arbeitsweise der Controller nach sich.
Gemeinsam bleibt beiden Systemen die Befehlsbildung aus verschiedenen Berater-Signalen
sowie die Implementation und Arbeitsweise der Berater. Nachfolgend sollen kurz die
wesentlichsten Unterschiede zwischen Soft- und Hardwareimplementationen aufgezeigt
werden.
23
3.3.1. Mögliche Funktionsweise einer Hardware-Berater-Struktur
Hardware-Systeme erhalten in der Regel ihre Informationen über die Umgebung aus der
Umrechnung von gesammelten Sensordaten, etwa von Videokameras, Mikrophonen, Laser-
Sensoren zur Abstandsmessung und ähnlichem. Da zum einen die Auswertung der von den
Sensoren gelieferten Daten nicht mit gleicher Geschwindigkeit vonstatten geht und zum
anderen auch nicht jeder Berater unbedingt alle Daten benötigt, würde ein Synchronschalten
der Berater unweigerlich zur Verlangsamung des Systems führen, hervorgerufen durch einen
Engpass bei der Informationsbeschaffung.
Um diesem Problem zu entgehen, können die Berater asynchron getaktet werden. Die
Befehlsbildung durch den Controller erfolgt dabei kontinuierlich mit den zuletzt von den
Beratern produzierten Signalen, welche zu diesem Zweck zwischengespeichert werden
müssen. Die Berater aktualisieren ihre Signale selbstständig, wenn neue Sensorinformationen
vorliegen (vlg. [Rosenblatt97], asynchrone Arbeitsweise von Behaviors).
Um eine möglichst große Performance zu gewährleisten, kann die Implementation mehrerer
parallel zueinander arbeitender Controller erwogen werden. Dabei werden jedem Controller
eine oder mehrere Aktion(en) zugeteilt, die von ihm bearbeitet werden, anstatt einen
Controller alle Aktionen abarbeiten zu lassen. Die maximale Anzahl der parallel arbeitenden
Module hängt dabei von der Zahl der Berechnungseinheiten und der möglichen Aktionen des
Objektes ab.
3.3.2. Mögliche Funktionsweise einer Software-Berater-Struktur
Software-Berater-Systeme sehen sich in der Regel nicht mit dem Problem der
Sensordatenumrechnung konfrontiert. Durch die digitale Bereitstellung der Informationen
kann gewährleistet werden, dass alle Berater bei Anfrage ein aktuelles Signal produzieren
können. Aus diesem Grund bietet es sich an, die Module alle synchron zu takten, um so einen
kontinuierlichen Signalfluss zu gewährleisten. Dabei würde auch das Zwischenspeichern von
Signalen entfallen. Allerdings kann es auch hier Ausnahmen geben, etwa wenn ein Berater
nur mit niedriger Frequenz relevante Signale produziert oder die Bewertung von Aktionen
eine lange Rechenzeit erfordert, so dass der Berater nur in größeren Abständen aktiviert
werden sollte.
Da für eine Softwareimplementation gewöhnlich nur eine Recheneinheit zur Verfügung steht,
ist der Einsatz mehrerer Controller für ein Objekt nicht anzuraten. Verschiedene Controller
könnten ohnehin nur sequentiell abgearbeitet werden, so dass sich auch ein einziger
Controller um alle Aktionen des Objektes kümmern kann. Auch hier gibt es Ausnahmen,
wenn etwa mehrere Recheneinheiten zur Verfügung stehen und eine Parallelverarbeitung
durch den Rechner unterstützt wird.
24
3.4. Die Berater und die Fahrschule
Für das Fahrschul-Projekt musste als erstes entschieden werden, was für ein KI-System zum
Einsatz kommen soll.
Von Anfang an ausgeschlossen werden konnten Automaten wegen ihrer fehlenden
Komplexität sowie künstliche neuronale Netze wegen ihres Übermaßes an Komplexität und
benötigter Vorarbeit (hauptsächlich das Trainieren des Netzes würde viel zu umständlich
werden).
Gegen eine einfache Entscheidungsstruktur sprach der Umstand, dass es auf den Straßen zu
viele mögliche Situationen gibt, um sie alle in einem Baum zu beschreiben. Das entstehende
Konstrukt wäre zudem stark unübersichtlich und schwer zu verwalten gewesen.
Damit blieben als Möglichkeiten der Einsatz eines regelbasierten Agentensystems oder einer
Berater-Struktur. Im direkten Vergleich haben sich einige Nachteile der Agentenstruktur
gezeigt, welche von deren Nutzung abrieten.
So müssen – ähnlich zu den Entscheidungsbäumen – die möglichen Situationen der KI-
Objekte in einer Regelbasis abgelegt werden. Dadurch würde sich wieder das Problem einer
großen, undurchsichtigen Struktur ergeben, die nur schlecht erweitert werden kann. Zudem
sehen Agentensysteme vor, dass einer bestimmten Regel auch eine spezifische Aktion
zugeordnet wird. Die Fahrzeuge verfügen jedoch im Allgemeinen über nur sehr wenige
Aktionen (Beschleunigen, Lenken, …), die aber mit sehr vielen unterschiedlichen Werten
ausgeführt werden können. Somit wird eine Zuordnung von Aktionen zu Situationen deutlich
erschwert. Ein weiteres Problem ist, dass Agentensysteme zwar über längere Zeit mehrere
Ziele verfolgen, für die Befehlsfindung aber jeweils nur das am höchsten priorisierte Ziel
beachten können. Da aber das Führen eines Fahrzeuges die gleichzeitige Verfolgung mehrerer
Absichten erfordert (nächste Straße anvisieren, Kollisionen mit anderen Autos vermeiden,
StVO beachten usw.), schien ein Agentensystem ungeeignet für die Problemstellung.
Der Berater-Ansatz ist hingegen geradezu ideal dafür, um für die Fahrschule eingesetzt zu
werden. Die Aufteilung der Situationsbewertung in mehrere Module ermöglicht eine
getrennte und nur das notwenigste enthaltende Berechnung und Bewertung der Situation.
Somit ist es nicht mehr nötig, alle möglichen Verkehrssituationen vorauszuahnen, sondern es
reicht, jeden Berater nur einen Teilaspekt des aktuellen Zustandes betrachten zu lassen. Da
jeder Berater für andere Ziele verantwortlich ist, ist durch die Art der Befehlsbildung auch die
Verfolgung mehrerer Absichten gleichzeitig gewährleistet.
Einen Nachteil des Systems gibt es trotzdem. Da für jeden Verkehrsteilnehmer eigene Berater
implementiert werden müssen, könnte eine schlechte Programmierung dieser zu erheblichen
Performanceeinbußen führen. Die Tatsache, dass verschiedene Berater unter Umständen die
gleichen Daten benötigten, macht es erforderlich, das System in einer Weise zu organisieren,
die Mehrfachberechnungen ausschließt.
25
4. Ein Beratersystem für die Fahrschule
In diesem Kapitel sollen die theoretischen Grundlagen für das in der digitalen Fahrschule
eingesetzte Berater-System diskutiert werden.
4.1. Anforderungen an das System
Die Anforderungen des Systems entsprechen im Wesentlichen dem, was auch an jeden
Verkehrsteilnehmer in der realen Welt an Forderungen gestellt wird. Das bedeutet konkret die
Einhaltung der Verkehrsregeln, das Reagieren auch auf unvorhersehbare und neue Situationen
sowie das Gewährleisten der eigenen Sicherheit und der Sicherheit der anderen
Verkehrsteilnehmer. Hinzu kommt eine möglichst flexible Implementierung, die gut mit
Änderungen der Verkehrsregeln (etwa zur Portierung in andere Länder) klar kommt.
Weiterhin ist zu beachten, dass es unterschiedliche Verkehrsteilnehmer mit jeweils eigenem
Verhalten geben kann, so etwa Autos, Straßenbahnen, Züge, Fußgänger und weitere. Jede
dieser Gruppen sollte nach Möglichkeit das gleiche System benutzen können, ohne das große
Änderungen vonnöten sind.
Gleichzeitig muss das System so performant wie möglich sein, um nicht nur auf den neuesten
Rechnern ausgeführt werden zu können.
Als weitere Vorgabe fand sich der Wunsch, den KI-Objekten einen eigenen Charakter zu
geben, damit das Verkehrsverhalten möglichst originalgetreu simuliert werden kann.
Schließlich fahren auf der Straße auch nicht alle Autos gleich.
Ein wichtiger Punkt ist, dass es sich um eine reine Software-Lösung handelt. Dadurch
entfallen Strategien wie das asynchrone Takten der Berater oder der Einsatz mehrerer
Controller.
4.2. Erweiterung des ursprünglichen Berater-Konzeptes
Damit alle gestellten Anforderungen erfüllt werden können, muss das ursprüngliche, von
Rosenblatt beschriebene Konzept erweitert werden. Um etwa ein wiederholtes Berechnen von
häufig benötigten Informationen zu vermeiden, sind Strukturen notwendig, welche die
längerfristige Speicherung von Daten zulassen. Die hier beschriebenen Erweiterungen des
Berater-Konzeptes sind eine Eigenentwicklung und finden sich nicht in der benutzten
Literatur.
26
Die hinzugefügten Module lassen sich in vier Kategorien einteilen:
Aktionsbasis:
Die Aktionsbasis enthält eine Liste aller verfügbaren Aktionen, die der zugeordnete
Verkehrsteilnehmer ausführen kann.
Speicher:
Die Speicher enthalten Daten über eine spezifische Gruppe von Informationen, um
diese allen Beratern verfügbar zu machen.
Charakter:
Der Charakter dient zum Beschreiben der persönlichen Eigenschaften des KI-
Objektes.
Manager:
Die Manager sind für das Füllen der Speicher verantwortlich und werden zu Beginn
jedes KI-Taktes einmal aufgerufen.
Die hinzugefügten Module sind dabei nicht auf eine Verwendung innerhalb der Fahrschule
beschränkt, sondern können auch außerhalb dieser benutzt werden (näheres dazu im Kapitel
5. Implementierung). Im Folgenden soll die allgemeine Verwendung der zusätzlichen Module
erklärt werden.
4.2.1. Die Aktionsbasis
Die Aktionsbasis dient zum Festhalten der möglichen Aktionen des KI-Objektes. Eine Aktion
besteht dabei aus den im Kapitel 3.1.1.Funktionsweise von Berater-Systemen genannten
Bestandteilen (Identifizierung der Aktion, minimaler und maximaler Wert, Schrittweite)
sowie einem Indikator, ob der zugehörige Aktionswert ein analoger Wert sein kann oder sich
streng diskret aus den Grenzen und der Schrittweite ergibt. Analoge Werte können im Verlauf
der Befehlsbildung mit Hilfe der quadratischen Interpolation (siehe 3.1.4. Analoge
Befehlsbildung aus diskreten Abstimmungen) gebildet werden.
Durch Modifizieren der Liste können so dem KI-Objekt auf einfache Art neue Aktionen
hinzugefügt werden. Der Controller greift im Zuge eines KI-Taktes auf diese Liste zurück und
befragt die Berater zu den darin enthaltenen Aktionen.
Durch die Aktionsbasis-Struktur ist es damit möglich, verschiedene KI-Objektgruppen mit ein
und denselben Beratern zu erstellen und ihnen lediglich eine leicht veränderte Aktionsbasis
zuzuweisen.
Am Beispiel des Straßenverkehrs: es werden die Gruppen „Personenkraftwagen“,
„Schienenfahrzeuge“ und „Busse“ erstellt, welche die gleichen Berater und die gleiche
Aktionsbasis benutzen. Lediglich die Aktion „Fahrgäste aufnehmen“ würde in der Liste der
Busse und Schienenfahrzeuge hinzugefügt werden, um ihnen das Mitnehmen von Passagieren
zu ermöglichen. Gleichzeitig wird den Schienenfahrzeugen die Aktion „Steuern“ aberkannt,
da ihre Strecke durch die Schienen vorgegeben ist. Die Möglichkeit zum Wechseln der Gleise
an einer Weiche wäre dagegen eine exklusive Aktion der Schienenfahrzeuge.
27
4.2.2. Der Zustandsspeicher
Aufgabe des Zustandsspeichers ist es, in einer eigens dafür angelegten Struktur den aktuellen
Weltzustand des Objektes festzuhalten, damit er von den einzelnen Beratern ausgewertet
werden kann.
Der Zustandsspeicher ist jeweils nur für einen KI-Takt gültig, danach hat sich in der Regel die
Welt um das Objekt geändert und der Speicher muss für gewöhnlich neu befüllt werden.
Der Zustandsspeicher trägt einen wesentlichen Teil zum Performancegewinn bei, da
aufwandsintensive Daten nur einmal pro KI-Takt berechnet werden müssen und dann allen
Beratern zur Verfügung stehen.
4.2.3. Der Intentionenspeicher
Der Intentionenspeicher hat eine ähnliche Aufgabe wie der Zustandsspeicher, ist aber für das
Aufbewahren von Intentionen der Berater zuständig. Intentionen sind Absichten oder
temporäre Ziele der Berater, die nur für den aktuellen KI-Takt Gültigkeit besitzen.
Auch der Intentionenspeicher wird in der Regel zu Beginn jedes Taktes geleert, um dann von
den Beratern neu befüllt zu werden.
Die Notwendigkeit des Intentionenspeichers ergab sich aus folgender Überlegung:
Da die Berater mit einer Gewichtung versehen sind und zusätzlich noch gegen ungünstige
Befehle ein Veto einlegen können, werden mitunter in einer Situation manche Befehle durch
sicherheitsrelevante Berater überhaupt nicht zugelassen, etwa das Nach-Links-Steuern, wenn
eigentlich die Spur gehalten werden sollte. Unter gewissen Umständen wäre es ab und zu
jedoch wünschenswert, die Meinung eines höher priorisierten Beraters zu missachten und
einen eigentlich ungünstigen Befehl auszuführen, als Beispiel das „Links überholen“ auf einer
einspurigen Straße.
Eine mögliche Lösung wäre natürlich gewesen, den Beratern eine Möglichkeit zum
Unterdrücken anderer Berater zu geben, was jedoch zu fatalen Fehlern der KI führen könnte
(wenn zum Beispiel links überholt werden möchte, aber sich neben dem eigenen Fahrzeug
bereits ein anderes befindet). Ein sicherheitsrelevanter Berater darf demzufolge nicht einfach
unterdrückt werden.
Eine andere, bessere Lösung bietet der Intentionenspeicher. In ihm werden zu Beginn des KI-
Taktes die Wünsche und Absichten aller Berater zum Durchführen einer bestimmten
Handlung vermerkt. Im weiteren Verlauf des Taktes steht es den einzelnen Beratern jetzt frei,
ob sie den Wünschen der anderen Berater Beachtung schenken (etwa, in dem ein
Sicherheitsberater nicht gegen das Nach-Links-Steuern votiert, obwohl es eigentlich nötig
wäre) oder nicht.
Der Intentionenspeicher stellt also in dem Sinne die einzige Möglichkeit dar, mit Hilfe derer
die einzelnen Berater miteinander kommunizieren können.
28
4.2.4. Der Zielspeicher
Die Entstehung des Zielspeichers ergab sich aus der Absicht, das KI-System so stark wie
möglich vom eigentlichen KI-Objekt zu trennen. Um also längerfristig zu verfolgende Ziele
nicht im eigentlichen KI-Objekt ablegen zu müssen, wurde der Zielspeicher eingeführt. Auch
er wird einmal zu Beginn jedes KI-Taktes aktualisiert, muss jedoch nicht zwangsläufig vorher
geleert werden, schließlich können Ziele über längere Zeit hinweg bestehen.
Im weiteren Verlauf des Taktes können die Berater dann die Informationen des Speichers
abrufen, um ihre Situationsbewertung daran auszurichten.
4.2.5. Die Charakterbeschreibung
Die Charakterbeschreibung stellt im Grunde auch nichts weiter als einen Speicher dar, der
jedoch im Verlauf der Programmausführung relativ konstant bleibt und nur selten verändert
wird. Die Charakterbeschreibung soll es dem KI-System ermöglichen, seine Aktionen etwas
individueller zu gestalten, um so mehr Abwechslung in den Programmablauf zu bringen. Die
Berater können während eines KI-Taktes auf die in der Beschreibung gespeicherten Daten
zurückgreifen, und anhand der dortigen Informationen ihre Situationsbewertung anpassen.
Ein Beispiel hierfür wäre, wenn die Charakterbeschreibung ein Feld „Aggressivität“ hätte und
der Berater, welcher für die Einhaltung der StVO verantwortlich ist, die maximal zulässige
Geschwindigkeit des Fahrzeuges abhängig von der Aggressivität des KI-Objektes macht.
Zusätzlich ist in der Charakterbeschreibung die Auswertungsfunktion (zum Beispiel Maxsum
oder Maximax) gespeichert, welche vom Controller zur Auswertung der Beratersignale
genutzt wird. Die Funktion wird innerhalb der Charakter-Daten gespeichert, da sie das
grundlegende Verhalten des Systems (optimistisch, vorsichtig, …) beschreibt.
4.2.6. Der Zustandsmanager
Der Zustandsmanager ist dafür verantwortlich, den Zustandsspeicher des KI-Objektes aktuell
zu halten. Da hier ein Großteil der rechenintensiven Aktionen durchgeführt wird
(insbesondere die mathematischen Vorgänge zum Bestimmen der Positionen und
Entfernungen zu anderen Welt-Objekten), ist auf eine performancegünstige Implementierung
des Managers zu achten. Der Zustandsmanager benötigt direkten Zugriff auf das zugeordnete
KI-Objekt, um die Situation des Objektes geeignet beschreiben zu können.
29
4.2.7. Der Zielmanager
Aufgabe des Zielmanagers ist es, den Zielspeicher aktuell zu halten. Zu Beginn jedes KI-
Taktes wird der Manager aufgerufen, um die bisher gesetzten Ziele auf ihre Erfüllung hin zu
testen und um eventuell neue Ziele festzulegen.
Der Zielmanager benötigt dazu vollen Zugriff auf das KI-Objekt, da er nicht auf den aktuellen
Zustandsspeicher zurückgreifen kann. Ursache dafür ist, dass strukturbedingt der Zielmanager
vor dem Zustandsmanager aufgerufen wird. Da die Ziele und der Weltzustand eines Objektes
in gegenseitiger Wechselwirkung stehen, musste einem von beiden Managern der Vorrang
gegeben werden. Die Entscheidung fiel schließlich auf den Zielmanager, da die Ziele eines
Objektes dessen Weltzustand stärker beeinflussen als umgekehrt.
Als Beispiel sei hier der Weltzustand „Entfernung zum Ende der Straße“ der Fahrschul-KI
genannt, welcher vom Zustandsmanager berechnet wird. Würde der Zustandsmanager vor
dem Zielmanager aktiv werden, könnte der Zielmanager diesen Wert theoretisch für die
Bestimmung benutzen, ob sich das Fahrzeug noch auf der aktuellen Straße befindet oder
schon die nächste erreicht hat. Im letzteren Fall wüsste der Manager dann, dass er das Attribut
„aktuelle Straße“ des KI-Objektes aktualisieren muss. Als Folge davon aber wäre das Attribut
„Entfernung zum Ende der Straße“ für diesen KI-Takt nicht mehr aktuell und würde unter
Umständen zu fehlerhaftem Verhalten führen. Wird dagegen zuerst der Zielmanager aktiv,
erfordert das möglicherweise doppelte Berechnungen von gewissen Werten, vermeidet aber
definitiv interne Logik-Fehler.
4.2.8. Der Intentionenmanager innerhalb der Berater
Da Intentionen an die einzelnen Berater gebunden sind, kann es keinen zentralen
Intentionenmanager geben, welcher den Intentionenspeicher befüllt. Stattdessen wird jeder
Berater vor der eigentlichen Befehlsbildung nach seinen Intentionen (Wünschen, Absichten)
befragt, die er dann im Speicher hinterlegen kann. Die Intentionen sind in der Regel vom
Berater, dem aktuellen Weltzustand und von den gegenwärtigen Zielen abhängig.
4.3. Genereller Aufbau des Systems
Das eigentliche Berater-System soll so aufgebaut werden, dass es auch unabhängig von der
Fahrschule für andere KI-Projekte eingesetzt werden kann. Um das zu erreichen, werden nur
Module mit projektunabhängiger Aufgabe fest implementiert, die restlichen Module liegen
lediglich als Interfaces vor und müssen projektabhängig programmiert werden.
Komplett projektunabhängige Module sind allerdings nur die Aktionsbasis (bestehend aus
einem Speicher für durchführbare Aktionen und der Definition der Aktions-Struktur) sowie
der Controller. Da aber der Controller die gesamte Funktionsweise des KI-Systems steuert,
beschränkt sich die Implementierung der restlichen Module auf wenige, stark gekapselte
Methoden pro Interface.
30
Damit umfasst diese Arbeit eigentlich sogar zwei Projekte: das Berater-System an sich als
unabhängige Engine sowie eine konkrete Implementierung für die Fahrschule. Der
Einfachheit halber soll aber in den folgenden Kapiteln diese Unterscheidung nicht explizit
getroffen werden. Bei der Beschreibung der einzelnen Module kann davon ausgegangen
werden, dass die Methoden durch das Interface der Engine vorgegeben werden, die
Implementierung aber der Fahrschule entsprechend getätigt wurde. Eine Ausnahme ist
lediglich der bereits genannte Controller, da dieser generell vom Projekt unabhängig agiert.
4.4. Hauptmodule
In diesem Kapitel sollen die Hauptmodule der Fahrschul-KI besprochen werden. Als
Hauptmodule gelten alle ursprünglich zum Berater-Konzept gehörenden Module (nach
[Rosenblatt97] bzw. [Gems4]), sprich Controller, Berater und Mode-Manager.
Nachfolgend sollen die Aufgaben der einzelnen Module, ihre Funktionsweise und ihre
Variationen vorgestellt werden. Da sich weder in [Rosenblatt97] noch in [Gems4] genauere
Details zur Umsetzung und Implementierung für die Module finden, sind alle folgenden
Ansätze und Techniken auf eigenen Überlegungen begründet.
4.4.1. Der Controller
Die Controller an sich sind eine fest implementierte Klasse, können jedoch durch ihre
Zusammensetzung aus verschiedenen Beratern, Managern und Speichern voneinander
unterschieden werden. Für jede Gruppe von Verkehrsteilnehmern wird es einen separaten
Controller geben.
Im Einzelnen werden folgende Gruppen unterschieden:
- Fahrzeuge (Pkws, Lkws, Busse und ähnliches )
- Fußgänger
- Straßenbahnen
- Züge/andere Schienenfahrzeuge
Die Unterscheidung der Controller wird dabei hauptsächlich über die eingesetzten Berater
getroffen, da für jede Gruppe teilweise eigene Berater implementiert werden müssen (andere
Berater, etwa jene, die für das Beschleunigen verantwortlich sind, können in weitgehend allen
Gruppen gleichermaßen eingesetzt werden).
Um die KI-Objekte durch den fest implementierten Controller steuerbar zu machen, müssen
beide Objekte durch ein AIObject-Interface verbunden werden. Das Interface stellt eine
Methode zum Versenden einer Aktions-Nachricht zur Verfügung und wird an das KI-Objekt
angehangen. Die Aktions-Nachricht wiederum besteht aus einem die Aktion identifizierenden
Wert und dem durch den Controller bestimmten Befehls-Wert. Die Auswertung der
durchzuführenden Aktion kann dann normal in der Art einer switch-Struktur im eigentlichen
KI-Objekt erfolgen.
31
Der Abstimmungsraum des Berater-Systems besteht aus Fließkommazahlen, das heißt jede
auszuführende Aktion kann durch eine ID und einen Fließkommawert beschrieben werden
(für eine Liste der möglichen Aktionen siehe 4.5.1. Die Aktionsbasis).
4.4.2. Die Berater
Die Berater bilden den umfangreichsten Teil des KI-Systems, da sie für die Bewertung der
aktuellen Situation eines KI-Objektes sowie den daraus resultierenden Vorschlag für die
durchzuführende Aktion verantwortlich sind.
Da für jede Gruppe von Verkehrsteilnehmern einige Berater teilweise neu implementiert
werden müssen und es somit innerhalb der Fahrschule sehr viele Berater mit zum Teil
ähnlicher Funktion gibt, werden im Folgenden lediglich die Berater der Gruppe „Cars“, also
Fahrzeuge, vorgestellt.
Neben den eigentlichen Aufgaben soll dabei auch die Funktion des dem Berater eigenen
Intentionenmanagers aufgezeigt werden.
4.4.2.1. Sicherheitsberater
Der Sicherheitsberater hat innerhalb des Systems die höchste Priorität, da er für die Sicherheit
des Fahrzeuges verantwortlich ist. Zu seinen Aufgaben gehören die Vermeidung des
Umkippens und Schlitterns sowie die Verhinderung von Auffahrunfällen.
Um diese Ziele möglichst optimal zu erreichen, führt der beratereigene Intentionenmanager
eine „Voranalyse“ der Situation durch. Dabei werden alle sich in der Nähe befindenden
Verkehrsteilnehmer auf ihre Position hinsichtlich des KI-Objektes geprüft. Befinden sich die
gegnerischen Teilnehmer unmittelbar rechts oder links neben dem Objekt, so wird die
Intention „Rechtssteuern nicht erlaubt“ bzw. „Linkssteuern nicht erlaubt“ aktiviert. Befindet
sich ein Fahrzeug direkt vor dem Objekt und unterschreitet die Distanz zu ihm den minimalen
Bremsweg, so wird im Intentionenspeicher ein Wert für einen Lenkeinschlag zu einem
möglichen Ausweichkurs hinterlegt. Wird die Bremsdistanz nicht unterschritten, kann der
Sicherheitsberater im weiteren Verlauf der Signalbildung mit einem einfachen Brems-Signal
auf das gegnerische Fahrzeug reagieren.
Diese Maßnahmen ersparen das spätere, erneute Prüfen der Positionen von Gegnerfahrzeugen
bei der Bewertung der Verkehrssituation und ermöglichen anderen Beratern, eine der
aktuellen Situation entsprechende Aktion zu favorisieren. So möchte der Wegfindungsberater
etwa nur dann einen Spurwechsel nach Links oder Rechts ausführen, wenn die Intentionen
„Linkssteuern nicht erlaubt“ bzw. „Rechtssteuern nicht erlaubt“ nicht gesetzt sind.
Dieses Verfahren mag zwar etwas umständlich und die oben aufgeführten Intentionen nicht
als echte Wünsche oder Absichten erscheinen, jedoch ergab sich dieser Weg als der
Bestmöglichste, um das folgend geschilderte Problem zu umgehen:
Um ein generelles Linkslenken oder Rechtslenken des Objektes zu unterbinden, hätte
der Sicherheitsberater die entsprechenden Lenkeinschläge mit einer sehr stark
negativen Stimme belegen können. Das hätte zwar den Wegfindungsberater davon
abgehalten, die Spur zu wechseln, gleichzeitig aber auch leichte Kurskorrekturen des
32
Pfadhaltungsberaters verhindert. Wäre die Negativ-Stimme dagegen nicht hoch genug
gewesen, hätte sie leicht durch die aufsummierten Stimmen der Wegfindungs- und
Pfadhaltungsberater überstimmt werden können. Es war also eine Lösung zu finden,
die gleichzeitig den Spurwechseln unterbinden kann, wenn sich gegnerische
Fahrzeuge unmittelbar links oder rechts des KI-Objektes befinden, trotzdem aber
leichte Kurskorrekturen durch den Pfadhaltungsberater ermöglicht.
Die eben genannte Problematik verdeutlicht recht gut die Schwierigkeit, die in der
Implementation der einzelnen Berater liegt. Auf der einen Seite sollen sie möglichst
unabhängig voneinander agieren können, um eine günstige Bewertung der Situation zu
erreichen und die Sicherheit des KI-Objektes zu gewährleisten. Auf der anderen Seite ist eine
vollständig wissensfreie Bewertung (d.h. ohne Kommunikation der Berater untereinander)
ohne die Generierung von Fehlern schwer möglich.
4.4.2.2. Pfadhaltungsberater
Der Pfadhaltungsberater ist für die Ausrichtung des Fahrzeuges entlang der Straßenlinie
verantwortlich. Da der Berater damit für das Abbiegen an Kreuzungen und Kurven
verantwortlich ist, muss er mit besonderer Sorgfalt implementiert werden.
Folgendem Problem galt dabei besondere Aufmerksamkeit:
Angenommen, dass KI-Fahrzeug hat gegenüber der optimalen Spur eine leichte
Neigung nach links. Der Pfadhaltungsberater hat die Aufgabe, diese Abweichung
durch Steuern nach rechts zu korrigieren. Sollte der Steuer-Impuls allerdings zu stark
ausfallen, könnte es in Verbindung mit der Steuerträgheit des Fahrzeuges leicht zu
einem Übersteuern kommen, das heißt als Endergebnis der Spurkorrektur hat das KI-
Fahrzeug nun eine leichte Abweichung nach rechts, welche wiederum korrigiert
werden muss. Durch ständige Wiederholung dieses Vorgangs wird eine zittrige Fahrt
des Fahrzeuges verursacht.
Es ist also nötig, bei der Bestimmung der Steuersignale einen dämpfenden Faktor mit
einzubauen, welcher die Fahrt des Fahrzeuges stabilisiert.
Der Pfadhaltungsberater hat nur in geringem Umfang sicherheitsrelevante Funktionen und ist
damit von relativ niedriger Priorität. Auch der Intentionenmanager des Pfadhaltungsberaters
hat keine Funktion.
4.4.2.3. StVO-Berater
Aufgabe des StVO-Beraters ist die Einhaltung der Verkehrsregeln. Im Kontext der Fahrschule
ist das vor allem die Beachtung von Ampeln, der Vorfahrtsregelung auf Vorfahrtsstraßen und
gleichrangigen Kreuzungen sowie die Rücksichtnahme auf Fußgänger und andere
Verkehrsteilnehmer beim Abbiegen.
Der StVO-Berater ist nach dem Sicherheitsberater der sicherheitsrelevanteste Berater und hat
eine dementsprechend hohe Priorität. Der Intentionenmanager hat keine Funktion.
33
4.4.2.4. Wegfindungsberater
Der Wegfindungsberater ist zum einen für das Einhalten der Straßengrenzen verantwortlich
und sorgt zum anderen dafür, dass die Fahrzeuge einen Spurwechsel vollziehen können. Als
drittes ist er Hauptverantwortlicher für das Blinkverhalten des Fahrzeuges und sorgt außerdem
noch dafür, dass das KI-Objekt beim Abbiegen an einer Kreuzung nicht zu schnell fährt.
Der Spurwechsel besteht dabei aus zwei Bestandteilen: dem eigentlichen Lenken auf eine
andere Spur und dem Abbremsen oder Beschleunigen, wenn sich neben dem Fahrzeug auf der
Zielspur schon andere Fahrzeuge befinden. Der Wegfindungsberater nutzt für diese
Auswertung benachbarter Fahrzeuge die Angaben aus dem Intentionenspeicher.
Aufgabe des beratereigenen Intentionenmanagers ist es, das Erfordernis eines Spurwechsels
sowie die Richtung des Wechsels festzustellen.
Der Berater hat, wie der Pfadhaltungsberater, eine niedrige Priorität aufgrund der geringen
sicherheitsrelevanten Funktionen. Dennoch ist die Priorität etwas höher als die des
letztgenannten Beraters, da das Einhalten der Straßengrenzen wichtiger ist als das Ausrichten
an der Spur. Gleiche oder niedrigere Priorität als der Pfadhaltungsberater würde sogar dazu
führen, dass bei zu großer Entfernung zur Spurmitte diese Distanz nicht mehr verkleinert
werden könnte, da jeder Lenkversuch durch den Wegfindungsberater durch das Bestreben
blockiert werden würde, das Fahrzeug an der Spur auszurichten.
4.4.2.5. Zielverfolgungs-Berater
Die Aufgabe des Zielverfolgungs-Beraters ist es, das Fahrzeug auf schnellstmöglichem Weg
ans Ziel zu bringen. Dazu gehört unter anderem das Beschleunigen des KI-Objektes auf die
maximal zulässige (und vom Charakter abhängige) Geschwindigkeit sowie das Überholen
langsamerer Fahrzeuge. Auch der Einsatz von Hupe oder Lichthupe unterliegen der Kontrolle
des Zielverfolgungsberaters. Der Intentionenmanager hat die Aufgabe, einen eventuellen
Wunsch des Überholens zu kennzeichnen.
Der Zielverfolgungs-Berater hat die niedrigste Priorität aller Berater, ist aber durch das
Bestreben zur Beschleunigung des Fahrzeuges integraler Bestandteil des Systems.
4.4.3. Der Mode-Manager
Dem Mode-Manager kommt innerhalb des Berater-Systems für die Fahrschule keine
Bedeutung zu, da die Prioritäten der einzelnen Berater festgelegt sind und sich im Laufe der
Zeit auch nicht ändern. Trotz der vielen unterschiedlichen Situationen im Straßenverkehr ist
das Fahren an sich ein relativ statischer Vorgang, der als Ziel in der Regel nur die
Fortbewegung von A nach B unter der Prämisse maximaler Sicherheit für das Fahrzeug kennt.
Infolgedessen ist es auch nicht nötig, die Prioritäten innerhalb des Systems an neue Ziele
anzupassen.
34
4.5. Hilfsmodule
In diesem Kapitel sollen die Hilfsmodule der Fahrschul-KI besprochen werden. Als
Hilfsmodule gelten alle nachträglich dem ursprünglichen Berater-Konzept von Rosenblatt
hinzugefügten Module, also die Speicher, die Manager, die Aktionsbasis und die
Charakterbeschreibung.
4.5.1. Die Aktionsbasis
In diesem Kapitel sollen die Aktionen vorgestellt werden, welche durch die KI-Objekte
ausgeführt werden können. Die Aktionen werden dabei in die verschiedenen Gruppen von
Verkehrsteilnehmern untergliedert. Es wird jeweils ihre Bedeutung, das Wertintervall sowie
die Schrittweite aufgeführt.
Die Gruppe der Fahrzeuge verfügt über folgende Aktionen:
- Steuern:
Mit Hilfe dieser Aktion wird der Lenkeinschlag der Fahrzeuge bestimmt. Der
Wertebereich reicht dabei von -1 (starker Linkseinschlag) über 0 (kein
Einschlag) bis zu 1 (starker Rechtseinschlag). Die Schrittweite wurde zu 0.2
gewählt, um einen brauchbaren Mittelweg zwischen günstiger Auflösung und
gute Performance zu gewährleisten.
- Beschleunigen:
Die Bezeichnung dieser Aktion ist nicht vollständig korrekt, da mit ihr sowohl
das Beschleunigungs- als auch das Bremsverhalten der Fahrzeuge gesteuert
wird. Der Wertebereich liegt zwischen -1 und 1, wobei negative Werte für
Bremsen, positive Werte für Beschleunigung und 0 für Geschwindigkeit halten
steht. Die Schrittweite liegt wieder bei 0.2, könnte aber unter Umständen noch
vergrößert werden, da durch die Berater häufig Extremwerte (-1, 0 oder 1)
favorisiert werden.
- Blinken:
Diese Aktion steuert das Blinkverhalten der Fahrzeuge. Es werden lediglich
drei Werte unterschieden: -1 (links Blinken), 0 (nicht blinken), 1 (rechts
blinken). Demzufolge ist die Schrittweite auch 1.
- Hupe:
Die Hupe soll es der KI ermöglichen, akustisch auf eventuelles Fehlverhalten
anderer Verkehrsteilnehmer hinzuweisen. Es müssen lediglich zwei Werte
unterschieden werden, 0 für nicht Hupen und 1 für Hupen.
- Lichthupe:
Für die Aktion Lichthupe gelten die gleichen Aussagen wie für die Hupe: sie
dient der visuellen Kommunikation mit der Umwelt und unterscheidet die
Werte 0 (Lichthupe aus) und 1 (Lichthupe an).
35
- Licht:
Das Licht des Fahrzeuges muss von den Beratern entsprechend der aktuellen
Lichtverhältnisse (Tageszeit, Tunnel, Gewitter) entweder an- (1) oder
ausgeschalten (0) werden.
Für die Fußgänger gelten folgende Aktionen:
- Drehen:
Die Person dreht sich in die angegebene Richtung. Negative Werte bedeuten
nach links drehen, positive bedeuten nach rechts drehen. Die Schrittweite ist
mit 0.2 genau wie bei den Fahrzeugen gewählt, das Intervall reicht wiederum
von -1 bis 1.
- Gehen:
Die Person wird sich fortbewegen. Hierbei werden nur die Werte 0 (nicht
gehen), 0.5 (gehen) und 1 (rennen) unterschieden, da die
Fortbewegungsgeschwindigkeit auf einen konstanten, personenabhängigen
Wert gesetzt wird.
Straßenbahnen, Züge und andere Schienenfahrzeuge verfügen über die folgenden Aktionen:
- Beschleunigen:
Für die Aktion des Beschleunigens von Schienenfahrzeugen gelten die
gleichen Vorgaben wie für normale Fahrzeuge (Autos, Busse und ähnliche).
Das Intervall reicht von -1 bis 1, die Schrittweite beträgt 0.2.
- Lenken:
Schienenfahrzeuge können in der Regel lediglich an Weichen eine
Entscheidung über ihre Richtung treffen. Demzufolge gelten auch nur die
Werte -1 (der Weiche nach links folgen), 0 (geradeaus fahren) und 1 (der
Weiche nach rechts folgen).
- Blinken, Licht, „Hupe“ (Klingel, Horn):
Auch hier gelten die gleichen Vorgaben wie für die entsprechenden Aktionen
der normalen Fahrzeuge.
4.5.2. Der Zustandsspeicher
Im Zustandsspeicher für die Fahrzeuge sind hauptsächlich Werte hinterlegt, welche die
Position des Fahrzeuges in Bezug auf seine Umwelt beschreiben. Dazu gehören unter
anderem die Entfernungen zum Anfang und Ende der aktuellen Straße sowie zur
Straßenmitte, die Winkel zur momentanen und nächsten Straße oder eine Liste aller sich in
der näheren Umgebung befindlichen Fahrzeuge. Auch die Angabe des minimalen
Bremsweges, den das Fahrzeug bis zum vollständigen Stillstand benötigt, ist hier gespeichert.
Die Zustandsspeicher der anderen Verkehrsteilnehmer sind ähnlich aufgebaut und benötigen
daher keine weitere Beschreibung.
36
4.5.3. Der Intentionenspeicher
Der Umfang des Intentionenspeichers ist weitaus kleiner als der des Zustandsspeichers.
Lediglich die Fahrzeuge verfügen über einen solchen Speicher, für Fußgänger und
Schienenfahrzeuge wird er auf Grund des geringen Funktionsumfanges nicht benötigt.
Im Intentionenspeicher ist hinterlegt, ob das Fahrzeug die Spur wechseln oder überholen
möchte, ob diese Aktionen überhaupt erlaubt sind (ein Spurwechsel ist zum Beispiel nicht
gestattet, wenn sich auf der Zielspur schon Fahrzeuge befinden) oder ob ein scharfes Links-
/Rechtslenken erforderlich ist, um einem Hindernis auszuweichen.
Der Intentionenspeicher wird damit nicht allein als Liste von Wünschen, sondern auch für die
Kommunikation der Berater untereinander genutzt, da einige Angaben für die
Entscheidungsfindung aller Berater nötig sind. Welche Intention durch welchen Berater
vorgegeben wird, findet sich im Kapitel 4.2.2. Die Berater.
4.5.4. Der Zielspeicher
Der Zielspeicher enthält den Pfad, dem der Verkehrsteilnehmer zu seinem Ziel folgen soll
sowie einige zusätzliche Angaben, die auf dem Weg dorthin zu beachten sind. Ist dem Objekt
kein Pfad zugeteilt, sind hier auch die Angaben für das zufällige Umherwandern hinterlegt.
4.5.5. Die Charakterbeschreibung
Die Charakterbeschreibung für ein Fahrzeug hat zum Ziel, den einzelnen Fahrzeugen ein
individuelles Verhalten zu geben, um somit für mehr Abwechslung im Straßenverkehr zu
sorgen. Wenige Charakter-Werte reichen schon aus, um eine große Vielfalt auf den Straßen
der Fahrschule zu gewährleisten.
Jedes Fahrzeug verfügt über die Charaktereigenschaften „Aggressivität“ und „Voraussicht“.
Auswirkung hat der Charakter zum Beispiel auf die Einhaltung der gebotenen
Maximalgeschwindigkeit. Sehr aggressive und wenig vorausschauende Fahrer werden eher
die Höchstgeschwindigkeit überschreiten; vorausschauende, aber wenig aggressive Fahrer
dafür eher darunter bleiben. Ebenso werden aggressiv agierende Verkehrsteilnehmer später
bremsen oder schneller durch die Kurven fahren.
4.5.6. Die Manager
Die Manager der Fahrschule (Zustandsmanager, Zielmanager und die Intentionenmanager)
haben die Aufgabe, die oben beschriebenen Speicher zu füllen. Dabei werden verschiedene
Attribute des Fahrzeuges im Zusammenhang mit der Fahrzeugumgebung mathematisch
ausgewertet und im Speicher hinterlegt. Genauere Beschreibungen der zu berechnenden
Werte finden sich in den Kapiteln zu den einzelnen Speichern.
37
4.6. Befehlsbildung
Als Auswahlkriterium für die Fahrschule wurde das Maxsum-Kriterium gewählt. Begründung
für diese Wahl ist, dass dieses Kriterium am ehesten der realen Entscheidungsfindung durch
mehrere Berater entspricht, da alle Stimmen Beachtung finden. Das Maximax-Kriterium hat
sich im Test als nicht brauchbar erwiesen, da starke Negativ-Stimmen von
sicherheitsrelevanten Beratern bei der Befehlsbildung nicht beachtet werden.
Ergeben sich bei der Suche nach dem Maximum der kombinierten Signale mehrere mögliche
Positionen, die als beste Werte in Frage kommen, so wird strukturbedingt der letzte
ausgewählt.
38
5. Implementierung
In diesem Kapitel soll auf einige Feinheiten der Implementierung des Berater-Systems und
der Fahrschul-KI eingegangen werden. Vor allem sollen dabei die Strukturen beschrieben
werden, die zur Implementation genutzt wurden.
5.1. Generelles
Als Programmiersprache wurde durch die benutzte Engine für das Fahrschulprojekt die
Sprache C++ vorgegeben. Die hohe Flexibilität der Sprache bildet zudem eine gute
Ausgangsbasis für eine günstige und möglichst allgemeine Implementation des Systems.
Entwickelt wurde mit dem Microsoft Visual Studio 2005, alle benutzten Hilfsklassen (z.B.
Listen und Arrays) wurden selbst entwickelt.
Neben den Strukturen für das Berater-System und die Fahrschul-KI umfasst das Projekt auch
ein Werkzeug zur Visualisierung der Berater-Stimmen.
Die Implementierungen sind vollständig in Eigenregie entstanden, weder [Rosenblatt97] noch
[Gems4] lieferten Ansätze hierfür.
5.2. Die Controller-Klasse Neben der Klasse für die Aktionsbasis ist die Controller-Klasse die einzige vollständig
ausprogrammierte Klasse innerhalb des Berater-Systems, welche unabhängig von einem
konkreten Projekt ist. Der Controller enthält die für das Arbeiten des Systems notwendigen
Interfaces (also die Manager, die Speicher, die Charakterbeschreibung sowie eine Liste der
verfügbaren Berater). Mit Hilfe von Set- und Get-Methoden können diese Attribute bei der
Initialisierung gesetzt und später wieder abgerufen werden. Zusätzlich enthält der Controller
eine Liste, in der die zuletzt gebildeten Befehle hinterlegt werden.
Um den Controller zu aktivieren, das heißt ihn die Berater nach ihren Stimmen abfragen zu
lassen, wird die Methode Activate zur Verfügung gestellt. Einziger Parameter dieser
Funktion ist die Anzahl der Millisekunden, die seit dem letzten Aufruf vergangen sind.
Da der Controller für ein fehlerfreies Arbeiten allerdings nicht in jedem Takt die
Befehlsbildung durchführen muss, wurde ein Timer eingefügt. Erst wenn der Timer
abgelaufen ist, werden die Berater erneut befragt. Bei zwischenzeitlichen Aufrufen der
Activate-Methode werden die zuletzt gebildeten Befehle einfach wiederholt.
39
5.3. Das Berater-Interface
Das Berater-Interface erfordert bei der Implementation als Berater zwei Methoden:
QueryAdvisor fragt den Berater zu der übergebenen Aktion ab und erwartet eine
Liste von Stimmen als Rückgabewert.
StoreIntentionsToController ist die Aktivierungsmethode für den
beratereigenen Intentionenmanager und ist für das partielle Befüllen des
Intentionenspeichers verantwortlich.
5.4. Strukturen
Im Folgenden wird die Implementation der in der Fahrschule eingesetzten Strukturen näher
beschrieben.
5.4.1. Aktionsbasis
Die Aktionsbasis besteht aus einer Liste von Aktionen, welche bei der Initialisierung des
Controllers durch den Programmierer durch den mehrfachen Aufruf von AddAction befüllt
werden muss. Eine einzelne Aktion besteht aus einem Identifier, dem Werteintervall und der
Schrittweite sowie einer Angabe, ob das Intervall der Aktion als diskret oder analog
interpretiert werden soll. Bei einer analogen Aktion wird die Befehlsbildung nach dem unter
3.1.4. Analoge Befehlsbildung aus diskreten Abstimmungen beschriebenen Verfahren
durchgeführt. Als diskret sollten all jene Aktionen markiert werden, die nur eine bestimmte
Anzahl von Werten zulassen (z.B. die Aktion „Blinken“ der Fahrzeuge mit den Werten -1, 0
und 1). Analoge Aktionen sind in der Regel Steueraktionen mit kontinuierlichem
Wertebereich.
5.4.2. Die Speicher
Das Interface für die einzelnen Speicher verlangt lediglich nach den Methoden Reset und
Release zum Rücksetzen beziehungsweise Freigeben der Speicher sowie nach der Methode
GetWorldstate/GetIntention/GetGoal zum Erhalten spezifischer Werte
unabhängig von der eigentlichen Implementation.
Zusammen mit dem Berater-System wurde für jeden Speicher eine projektunabhängige
Implementation angefertigt, welche die Werte intern in einer Liste verwaltet.
Für die Fahrschule dagegen wurden spezielle Speicher implementiert, welche die benötigten
Werte fest als Attribute einprogrammiert haben. Der Zugriff erfolgt damit unmittelbar und
nicht über den Umweg über eine Suche in der Liste.
40
5.4.3. Charakterbeschreibung
Das Interface für die Charakterbeschreibung ist ähnlich dem der Speicher aufgebaut, es fehlt
lediglich die Reset-Methode, da der Charakter nicht in regelmäßigen Abständen
zurückgesetzt werden muss.
Auch für die Charakterbeschreibung wurde mit dem ursprünglichen Berater-System eine
Implementation als Liste beigefügt, für die Fahrschule wurde allerdings wieder die
Ausprogrammierung als Set von Attributen gewählt.
5.5. Der Zustandsmanager
Der Zustandsmanager hat von allen Managern die komplexesten und zeitintensivsten
Aufgaben. Stellvertretend soll hier die Auswertung der eigenen Fahrzeugposition in Hinblick
auf die anderen Verkehrsteilnehmer erläutert werden, da diese Berechnung bei weitem am
längsten dauert.
Die Positionsbestimmung gegnerischer Verkehrsteilnehmer wird im Vorfeld durch einfache
Distanzberechnung der Objekt-Mittelpunkt „Eigenes Fahrzeug – Gegnerfahrzeug“
durchgeführt. Im Anschluss erfolgt die detaillierte Positionsauswertung über einen Bounding-
Box-Kollisions-Test. Von Interesse sind dabei vor allem Verkehrsteilnehmer, deren
Entfernung zum KI-Objekt geringer als der minimale Bremsweg desselben ist (der minimale
Bremsweg ist auch abhängig vom Charakter – vorausschauende Fahrer bremsen eher). Die
beiden auf Kollision zu testenden Bounding-Boxen sind zum einen die umgebende Box des
gegnerischen Fahrzeuges, zum anderen der durch die seitlichen Fahrzeugabmessungen, die
aktuelle Ausrichtung und den Bremsweg definierte Bereich vor dem eigenen Fahrzeug. Um
vorausschauendes Fahren zu simulieren, wird zusätzlich noch der Bereich auf Kollision
getestet, der durch den Einschlagwinkel der Räder vorgegeben wird und somit das Ziel des
KI-Objektes in nächster Zukunft verdeutlicht.
Zur Verdeutlichung des Sachverhaltes zwei Abbildungen. Die schraffierten Flächen
kennzeichnen dabei die Bounding-Boxen.
Abbildung 10: Bounding-Box-Test in Richtung der Fahrzeugfront
und des Rad-Einschlages (blau) mit festgestellter Kollision (rot)
41
Alle Objekte in unmittelbarer Umgebung des eigenen Fahrzeuges werden dabei im
Zustandsspeicher in einer Liste hinterlegt, bei gefundener Kollision zwischen den Bounding-
Boxen wird noch ein zusätzlicher Vermerk angelegt.
5.6. Die Berater
Die Berater bilden das Herzstück für das Funktionieren der KI und ihre Implementation
entscheidet über Güte und auch Geschwindigkeit des Systems. Eine ineffiziente
Programmierung kann das ganze Programm unbrauchbar oder durch zu hohe Hardware-
Anforderungen uninteressant machen. Zudem muss gerade bei einer Fahrschule Wert darauf
gelegt werden, dass sich die computergesteuerten Verkehrsteilnehmer realistisch und vor
allem entsprechend der Straßenverkehrsordnung verhalten.
Bei der Implementierung der Berater wurde vor allem Wert darauf gelegt, keinen einfachen
Entscheidungsbaum zu Grunde zu legen, da ein solcher wieder zu relativ starrem Verhalten
bei der Entscheidungsfindung führen würde. Vielmehr sollen die optimalen Werte für die
gebildeten Signale durch Benutzung von Formeln errechnet werden.
Nachfolgend soll kurz dargestellt werden, auf welche Art die Berater ihre Entscheidungen
„berechnen“. Da lediglich die Steuer- und Beschleunigungs-Aktionen analoge Signale
benötigen, wird auch nur auf diese beiden Aktionen eingegangen.
5.6.1. Sicherheitsberater
Der Sicherheitsberater ist für den nötigen Abstand zu anderen Verkehrsteilnehmern sowie für
eventuelle Ausweich-Reaktionen verantwortlich und muss daher alle dynamischen Objekte in
der näheren Umgebung einer genaueren Prüfung unterziehen.
Die Positionen gegnerischer Fahrzeuge und Fußgänger sowie mögliche Kollisionen wurden
bereits durch den Zustandsmanager errechnet, im Sicherheitsberater erfolgt nun die
Auswertung dieser Daten. Bei einer gefundenen drohenden Kollision übernimmt der Sicherheitsberater die
Geschwindigkeit des betroffenen Objektes, sofern sie geringer ist als die eigene. Sollte die
Distanz zum gegnerischen Fahrzeug zu gering sein, um noch abbremsen zu können, wird
zudem ein möglicher Ausweichkurs bestimmt, um der Kollision zu entgehen.
5.6.2. Pfadhaltungsberater
Der Pfadhaltungsberater führt die mathematisch einfachsten Berechnungen zur Bestimmung
seiner Signale durch. Da er nur für Steuer-Aktionen zuständig ist, wird die Beschleunigungs-
Aktion ignoriert. Für die Bestimmung des idealen Lenkeinschlages wird der aktuelle Winkel
zur Straße aus dem Zustandsspeicher herangezogen. Abhängig vom bereits bestehenden
Einschlag der Räder und der momentanen Fahrsituation (Geradeausfahren auf einer Straße
42
oder Abbiegen auf einer Kreuzung) wird über einfache Multiplikation mit einem
Korrekturfaktor der beste Einschlagwinkel berechnet. Der Korrekturfaktor ermöglicht dabei
ein annähernd naturgetreues Fahren einer Kurve.
Um ein periodisches Schwanken des Lenkeinschlages um den optimalen Wert zu verhindern,
wird zum einen keine absolut exakte Anpassung an den besten Winkel verlangt und zum
anderen der berechnete Einschlagwinkel mit einem Dämpfungsfaktor multipliziert, der umso
größer ist, je näher die aktuelle Fahrzeugausrichtung an die optimale heranreicht.
5.6.3. StVO-Berater
Bei dem StVO-Berater konnte, trotz aller Vorgaben, ein Entscheidungsbaum hinter der
Implementierung nicht ganz verhindert werden. Grund dafür ist, dass der Berater vor allem
für das Einhalten der Vorfahrtsregelung verantwortlich ist, welche sich lediglich über das
Abarbeiten mehrerer Fallunterscheidungen realisieren lässt.
Zur Entscheidungsfindung wird die Liste aller in der Nähe befindlichen Verkehrsteilnehmer
durchlaufen, und für jedes Fahrzeug dessen Position und Ziel relativ zum eigenen Fahrzeug
bestimmt. Anschließend kann über einen Vergleich der Straßenprioritäten (Vorfahrtsstraßen
haben höhere Priorität) entschieden werden, ob das eigene Fahrzeug warten muss oder fahren
darf.
Eine Besonderheit stellt die Handhabung von gleichrangigen Kreuzungen dar. An solchen
Straßenverbindungen kann es vorkommen, dass aus jeder Richtung ein Fahrzeug kommt und
somit im Grunde keines von ihnen Vorrang hat. Theoretisch wäre diese Situation durch die KI
leicht zu handhaben, da einfach der zuerst Angekommene fahren könnte – lediglich die
Erkennung einer solchen Situation stellt die Schwierigkeit dar, da es keine Struktur im
Programm gibt, welche die Kreuzungen an sich überwacht. Damit der Verkehr bei so einer
Konstellation nicht zum Erliegen kommt, wurde folgendes System implementiert:
Jede Kreuzung verfügt über ein Signalflag. Kommt ein Fahrzeug an einer Kreuzung mit
aktiviertem Flag an (was bedeutet, dass es das erste Fahrzeug an dieser Kreuzung ist), so
deaktiviert es das Kreuzungssignal und speichert es intern selber ab. Wird durch den StVO-
Berater nun ein gegnerischer Verkehrsteilnehmer mit Vorfahrt bestimmt, wird an diesen das
Signal weitergesendet. Das Weitersenden des Signals erfolgt nun so lange, bis entweder ein
Fahrzeug nicht durch ein anderes, von rechts kommendes blockiert wird (und somit fahren
darf) oder das Signal wieder am Ursprung ankommt. In diesem Fall weiß der StVO-Berater,
dass die Kreuzung blockiert ist und das eigene KI-Objekt als erstes ankam und somit fahren
darf.
5.6.4. Wegfindungsberater
Die Berechnungs-Routinen des Wegfindungsberaters sind ähnlich denen des
Pfadhaltungsberaters recht einfach gehalten. Zum Spurwechsel wird einfach der Winkel zur
nächsten Straße verwendet, multipliziert mit einem Korrekturfaktor um übermäßiges Steuern
zu verhindern.
43
Die Einhaltung der Straßengrenzen erfordert dagegen etwas mehr Logik (was aber nicht
unbedingt eine komplexere Rechnung bedeutet). Es darf nur dann zur Straßenmitte hin
gelenkt werden, wenn das Fahrzeug nicht ohnehin schon auf diesem Kurs ist oder das
Lenkrad nicht bereits Richtung Mitte eingeschlagen wurde.
Das Abbremsen oder Beschleunigen zum Zweck des Spurwechsels hingegen folgt einfachen
Entscheidungen: ist das Ende der Straße weit genug entfernt und die erlaubte
Höchstgeschwindigkeit noch nicht ausgereizt, dann wird beschleunigt. Ansonsten wird
gebremst, um einen Spurwechsel durchführen zu können.
5.6.5. Zielverfolgungsberater
Auch der Zielverfolgungs-Berater zeichnet sich durch Einfachheit aus. Ist die maximal
erlaubte Geschwindigkeit noch nicht erreicht, so wird beschleunigt. Die Stärke der
Beschleunigung hängt dabei vom Charakter des KI-Objektes ab. Auch zum Überholen
beschleunigt der Berater, mitunter sogar über die Höchstgeschwindigkeit hinaus. In allen
anderen Fällen behält der Berater die aktuelle Geschwindigkeit bei.
Die Berechnung des nötigen Einschlagwinkels zum Überholen erfolgt über die Auswertung
der Fahrzeuge vor dem KI-Objekt. Ist ein Ausweichen nötig, so wird ein entsprechender
Lenkeinschlag nach rechts oder links angegeben, ansonsten wird das Fahrzeug möglichst
gerade an der Straße ausgerichtet. Ist der Überholvorgang abgeschlossen, wird zurück in die
Spur gelenkt, die genaue Ausrichtung an der Straße übernimmt dann der Pfadhaltungsberater.
5.7. KI-Visualisierung Um die Entscheidungsfindung der KI nachvollziehen und eventuelle Fehler entdecken zu
können, wurde parallel zum eigentlichen Berater-System ein Programm entwickelt, welches
die Berater-Signale anzeigen kann. Das Programm ist unabhängig von einer konkreten
Implementierung des Berater-Systems und kann aus dem eigentlichen KI-Projekt gestartet
und aktualisiert werden. Zu Programmstart muss dem Visualisierer mitgeteilt werden, welche
Controller, Berater und Aktionen es gibt. Im Verlauf der KI-Simulation werden die einzelnen
Stimmen zu den möglichen Befehlen an den Visualisierer gesendet, welcher aus ihnen ein
Diagramm erstellt und dieses anzeigt.
Einige Bilder des Programms am Beispiel der Fahrschule (die schwarze Linie symbolisiert
das durch das Maxsum-Kriterium definierte Signal, der dickere senkrechte Strich markiert das
Optimum des Signals, nachdem die quadratische Interpolation durchgeführt wurde):
44
45
46
6. Zusammenfassung/Ausblick
6.1. Zusammenfassung Hauptthema dieser Arbeit war die Diskussion eines auf Beratern basierenden KI-Systems im
Vergleich mit anderen Systemen sowie die Erörterung einer Implementation für eine
Fahrschul-Software. Es wurde dabei auf verschiedene Arten von Berater-Systemen
eingegangen und einige Punkte erläutert, die bei der Ausprogrammierung der Berater
beachtet werden müssen. Als letztes wurden noch einige konkrete Implementationen von
Beratern für die Fahrschule näher vorgestellt.
Es ließ sich dabei feststellen, dass Berater-Systeme gegenüber herkömmlichen Systemen vor
allem den Vorteil haben, dass sie durch ihren modularen Aufbau extrem flexibel sind sowie
gleichzeitig mehrere Ziele verfolgen können. Vor allem der letzte Punkt machte sie für den
Einsatz in der Fahrschule interessant, da das Verhalten im Straßenverkehr ständigen
Änderungen und Anpassungen an unterschiedlichste Ziele unterworfen ist.
6.2. Ausblick
Eine Eigenschaft von Berater-Systemen macht sie für den zukünftigen Einsatz in Soft- und
Hardware-Lösungen besonders interessant: ihre Möglichkeit, parallel zu arbeiten. Da die
Bewertung der aktuellen Situation durch alle Berater unabhängig voneinander erfolgt, kann
durch den Einsatz mehrerer Recheneinheiten ein immenser Geschwindigkeitszuwachs bei der
Entscheidungsfindung erreicht werden.
Auch die starke Modularität sowie die implizite Verfolgung mehrerer Ziele zur gleichen Zeit
sind große Vorteile von Berater-Systemen.
47
7. Quellenverzeichnis
Beierle06 Beierle, Christoph und Kern-Isberner, Gabriele
„Methoden wissensbasierter Systeme“
Vieweg & Sohn Verlagsgesellschaft, 3. Auflage, 2006
Gems4 Hancock, John
„Eine Abstimmungsarchitektur für verteiltes Schließen“ in
Spieleprogrammierung Gems 4 (Seiten 367 – 377)
Carl Hasser Verlag München Wien, 2004, deutsche Ausgabe
Huss07 Huss, Sorin (Prof. Dr.-Ing.), TU Darmstadt
Folien zur Vorlesung „Technische Grundlagen der Informatik I“
http://www.vlsi.informatik.tu-
darmstadt.de/student_area/tgdi/folien/tgdi1-WS0506-Kap7x6.pdf
Stand: 1.8.2007
Luger01 Luger, George F.
„Künstliche Intelligenz – Strategien zur Lösung komplexer Probleme“
Pearson Education Limited, 2002
Patterson97 Patterson, Dan
Künstliche neuronale Netze : das Lehrbuch
Prentice Hall Verlag GmbH, 1997, deutsche Ausgabe
Rich86 Rich, Elaine
“Artificial intelligence”
McGraw-Hill Verlag New York, 1983
Rosenblatt97 Rosenblatt, Julio K.
„DAMN – a distributed architecture for mobile navigation“
Journal of Experimental & Theoretical Artificial Intelligence
(Vol. 9, Numbers 2-3/April 1, 1997, Seiten 339 – 360)
Wiki06 Wikipedia (Stand: Dezember 2006), www.wikipedia.de
Winston92 Winston, Patrick Henry
“Artificial intelligence”
Addison-Wesley Verlag Reading, 1992
Winston93 Winston, Patrick Henry
“Artificial intelligence”
Addison-Wesley Verlag Reading, 1993
