Danksagung

Ich bedanke mich recht herzlich bei Dr. Herbert Hörtlehner, der während meines Studium an der University of Derby durch seinen unkonventionellen Unterricht mein Interesse an Robotik und den Methoden der künstlichen Intelligenz geweckt hat.

2

Inhaltsverzeichnis

1  Einleitung  8

2  Methoden der künstlichen Intelligenz  12

2.1  Fuzzy Logic  12

2.1.1  Fuzzy-Sets und Membership-Funktionen  13

2.1.2  Logische Operatoren auf Fuzzy-Sets  15

2.1.3  Linguistische Variable und Linguistische Terme  16

2.1.4  Fuzzy Regeln  17

2.1.5  Fuzzy Inferenz System  18

2.2  Kohonen Self-Organizing-Feature-Map  23

2.2.1  Trainieren einer SOFM  24

3  Implementierung  27

3.1  Wege der Signalverarbeitung  28

3.2  Hardware  29

3.3  Kommunikation  31

3.3.1  Device Communication Protocol (DCP)  31

4  Navigation entlang einer Linie  34

4.1  Identizieren der Linie  34

4.1.1  Schritt 1: Aufnahme eines Bildes  35

4.1.2  Schritt 2: Transformation in das HSB-Farbmodell  35

4.1.3  Schritt 3: Sliding Window Analyse  38

4.2  Fuzzy Logic für die Roboternavigation  39

4.2.1  Input Fuzzy Sets  40

3

4.2.2  Output Fuzzy Sets  41

4.2.3  Fuzzy Regeln  41

4.2.4  Navigationsfunktion  41

4.2.5  Ergebnistransformation  42

5  Erkennung von Verkehrszeichen  44

5.1  Finden des Verkehrszeichen und Bildtransformation  44

5.1.1  Schritt 1: Drehen  44

5.1.2  Schritt 2: Ausschneiden des Verkehrszeichens  45

5.1.3  Schritt 3: Gröÿe normieren  46

5.1.4  Schritt 4: Entfärben  47

5.2  Klassizierung der Verkehrszeichen mittels neuronalem Netz  48

6  Schlussfolgerungen  50

A  Source Code  52

A.1  robot.m  52

A.2  getlinepos.m  57

A.3  ndsign.m  59

4

Abbildungsverzeichnis   

1.1  Roboter mit Kamera und Mikrocontroller  10

2.1  Boolean versus Fuzzy  14

2.2  Anwendung logischer Operatoren auf Fuzzy-Sets  16

2.3  Linguistische Variable und Terme  17

2.4  Fuzzy Inferenz System 24  19

2.5  Fuzzikation  20

2.6  Implikation  21

2.7  Akkumulation  22

2.8  CoG Defuzzikation  23

2.9  Aufbau einer SOFM 9  24

2.10  Winner-Neuron und Nachbarschaft  25

3.1  Wege der Signalverarbeitung  28

3.2  Radanzahl und Bodenkontakt 20  29

3.3  Bewegung eines dreirädrigen Roboters 6  30

3.4  Motorbrückenschaltung 12  30

3.5  DCP Paketaufbau  32

3.6  DCP Beispielpaket  32

3.7  DCP Programmstruktur  33

4.1  RGB-Farben  36

4.2  HSB-Farbenkreis  37

4.3  Umwandlung von RGB nach HSB (HSV) 7  38

4.4  Sliding Window  39

4.5  Winkel und Oset der Linie  40

5

4.6  Fuzzy Input Variable: Winkel and Oset  40

4.7  Fuzzy Output Variable: Richtung  41

4.8  Navigationsfunktion  42

5.1  Originalbild  45

5.2  Bild nach der Drehung  45

5.3  Extremstellen des Verkehrszeichens  46

5.4  Ausgeschnittenes Verkehrszeichen  46

5.5  Gröÿennormiertes Verkehrszeichen  46

5.6  Input für das neuronale Netz  47

6

Tabellenverzeichnis   

2.1  Boolsche Wahrheitstabelle  15

2.2  t- und s-Normen  16

2.3  Aggregation  20

7

Kapitel 1

Einleitung

Die Vision eines völlig selbständig navigierenden Autos ist wohl so alt wie das Auto selbst. Viele technische Hilfsmittel, angefangen vom Rückspiegel über automatische Gangschaltung bis zu elektronischen Einparkhilfen, erleichtern zwar das fahren, trotzdem ist es nach wie vor der Mensch, der das Fahrzeug steuert und kontrolliert. Erst in den letzten Jahren kommt man dem autonomen Vehikel durch Verwendung neuester Technologien der Künstlichen Intelligenz (KI) gepaart mit der Rechenleistung moderner Computer schrittweise näher.

Ziel dieser Arbeit ist es, ein völlig autonomes Vehikel zu entwickeln, das in der Lage ist, auf einem ihm unbekannten Parkour situationsgerecht zu navigieren. Unter situationsgerecht wird hier verstanden, dass zum einen ein durch eine farbige Linie gekennzeichneter Kurs verfolgt wird und während dessen Verkehrszeichen befolgt werden, die an der Linie positioniert sind. Bei den Verkehrszeichen handelt es sich hier um Geschwindigkeitsbeschränkungen, da auf diese einfach und wirklichkeitsnah reagiert werden kann. Der Roboter verändert also während der Fahrt entlang der Linie seine Geschwindigkeit in Abhängigkeit von den Verkehrszeichen. Die Idee zu diesem Projekt entstand bereits während meines Studiums an der University of Derby. Dort hatte ich die Möglichkeit, mich eingehend mit Fuzzy Logic (FL) zu beschäftigen. Besonders spannend erschien mir immer die praktische Anwendung dieser Methoden. Also entwickelte ich im

8

Rahmen meiner Diplomarbeit and der University of Derby eine web-basierte Fuzzy-Shell, über die seit Anfang 2003 unter anderem die Heizung in einem Projektraum in der HTL Spengergasse in Wien gesteuert wird. Eine Fuzzy-Shell ist ein Tool, mit dem FL-Systeme sehr einfach, meist grasch, designed werden können. Das Heizverhalten kann via Web konguriert und mitverfolgt werden. Während diese Heizung mit Innen- und Auÿentemperaturfühler zwar eine hübsche Anwendung ist, sich mit Fuzzy-Steuerungen auseinander zu setzen, sollte die nächste Herausforderung ein System sein, bei dem sich richtig was rührt, also ein etwas schnelleres Echtzeitsystem. So entstand die Idee des autonomen Fahrzeuges.

Erstes Ziel war es nur, ein Fahrzeug mittels FL-Steuerung eine Linie entlang zu schicken. Ich zog dafür verschiedene Möglichkeiten in Betracht. Eine war, eine dunkle Linie von hellem Untergrund über die Reektion eines Lichtstrahls zu unterscheiden. Doch wesentlich spannender fand ich, in das Projekt auch Bilderkennungsmechanismen zu integrieren. Für diesen Zweck wurde an der Front des Roboters eine Kamera montiert. Aus der Überlegung heraus, welche Erweiterungsmöglichkeiten sich durch die Kamera ergeben, entstand die Idee zum zweiten groÿen Teil dieses Projekts, nämlich die Identikation von Verkehrszeichen.

Abbildung 1.1 zeigt den verwendeten Versuchsaufbau. Die Straÿe wird durch eine grüne Linie auf weiÿem Untergrund dargestellt. Die Verkehrszeichen (in diesem Fall ein Stopp-Schild) werden direkt auf die Linie positioniert. Der Schwerpunkt dieses Projekts liegt in der Entwicklung der Steuerungssoftware unter Verwendung von KI-Methoden und nicht im Bereich von Mechanik oder Elektronik, obwohl mich dieses Projekt auch in diesen Gebieten neue Erfahrungen sammeln lieÿ. Um möglichst rasch zur Implementierung der KI-Methoden am Roboter zu kommen, entschied ich mich, das Chassis inklusive Getriebe und Motoren aus einem Bausatz des Magazins Real [20] zu verwenden. Robots r

Schwierigkeiten während der Implementierung machte die Bilderkennung unter wechselnden Lichtverhältnissen. Die Umwandlung des Bildes vom RGBin das HSV-Farbmodell (Farbmodelle werden später detaillierter beschrieben) brachte schlieÿlich die Lösung des Problems und machte die weitere

9

Abbildung 1.1: Roboter mit Kamera und Mikrocontroller

Bildverarbeitung weitgehend beleuchtungsunabhängig. Ein anderes Problem war die schlechte Qualität der Elektromotoren. Obwohl die Steuerung in der Simulation funktionierte, gab es in der Praxis anfänglich Schwierigkeiten, da die Motoren stark verzögert anliefen und nicht sofort stoppten, wenn das entsprechende Signal gesendet wurde. Dieses Problem wurde durch entsprechendes Tuning des Fuzzy-Systems behoben.

Im folgenden Kapitel wird der theoretische Hintergrund der in diesem Projekt verwendeten Methoden beleuchtet. Im wesentlichen sind das Fuzzy-Logic und eine spezielle Form der künstlichen neuronalen Netze, nämlich die Self-Organizing-Feature-Map nach Tuevo Kohonen. Die Theorie zur Fuzzy Logic wurde in ähnlicher Form auch in meiner Diplomarbeit an der University of Derby mit dem Titel FuzzyWeb - A Web-Based Approach to Fuzzy System Design [22] publiziert.

Das Kapitel Implementierung geht auf die einzelnen Hardwarekomponenten des Systems und deren Kommunikation untereinander ein. Für die Kommunikation habe ich ein eigenes Protokoll entwickelt, um möglichst einfach und ezient Daten zwischen den beteiligten Komponenten auszutauschen.

10

Kapitel 4 geht im Detail auf die Algorithmen ein, die für die Identikation einer Linie aus einem Bild und die Navigation entlang derselben verwendet wurden. Dieser Teil gliedert sich grob in die Bildanalyse, die als Ergebnis die Lagekoordinaten der Linie liefert, und ein Fuzzy Logic System, das die entsprechenden Schlüsse bezüglich der Navigation zieht. In Kapitel 5 der genau beschrieben, wie einerseits erkannt wird, dass sich ein Verkehrszeichen im Blickfeld des Roboters bendet, und andererseits dieses Verkehrszeichen dann identiziert und befolgt wird. Hier wird zuerst das Bild analysiert und dann so transformiert, dass es von einem neuronalen Netz weiterverarbeitet werden kann. Das hier verwendete neuronale Netzwerk ist - nachdem es ausreichend trainiert wurde - in der Lage festzustellen, um welches Verkehrszeichen es sich im Einzelfall handelt. Den Abschluss bilden ein paar Überlegungen zu möglichen Einsatzgebieten und Erweiterungen dieses Projekts.

11

Kapitel 2

Methoden der künstlichen

Intelligenz

Für die Steuerung des Roboters werden zwei wesentliche Methoden der künstlichen Intelligenz (KI) eingesetzt. Zum einen Fuzzy Logic (FL) und zum anderen eine spezielle Form der künstlichen neuronalen Netze, die Self-Organising-Feature-Map (SOFM). Die beiden Methoden werden in diesem Kapitel eingehend behandelt.

2.1 Fuzzy Logic

Lot Zadeh, Professor an der University of California in Berkeley, entwickelte Mitte der 1960er-Jahre das Konzept der Fuzzy Logic (FL). Grundsätzlich ist die FL eine Erweiterung der klassischen Logik, die auch Wahrheitswerte zwischen den Boolschen Werten wahr und falsch erlaubt. [13] FL ermöglicht uns, Systeme mittels in natürlicher Sprache formulierter Regeln zu beschreiben. Das FL System konvertiert diese Regeln in deren mathematische Interpretation. Auf diese Weise können beispielsweise Steuerungsmechanismen auf Basis von Expertenwissen und Erfahrungen erstellt werden, ohne die genauen technischen Hintergründe und Zusammenhänge zu kennen. In vielen Fällen wird dadurch die Systementwicklung erheblich vereinfacht und beschleunigt.

12

Zu Beginn hielt sich die Anerkennung dieser Theorie sehr stark in Grenzen. Erst als 1974 Professor Mamdani mit seinem Studenten Assilian eine Dampfmaschine mittels FL steuerte, erweckte sie groÿe Aufmerksamkeit. Es handelte sich um die erste praktische Anwendung der FL. Ein weiterer Schritt, der FL zum Durchbruch verhalf war die Entwicklung des ersten FL-Chips im Jahr 1975 durch die Bell Laboratories. Der Chip wurde in der Folge in einer groÿen Anzahl von Anwendungen, wie etwa Kameras oder Reis-Kochern verwendet. Heute ist FL einer der am schnellsten wachsenden Bereiche der künstlichen Intelligenz. [16]

2.1.1 Fuzzy-Sets und Membership-Funktionen

Das klassische logische Denken basiert auf einer zweiwertigen Aussagenlogik, auch Boolsche Logik genannt. Sie geht davon aus, dass jede Aussage entweder exakt wahr oder exakt falsch ist. Auf die Mengenlehre umgelegt heiÿt das, dass ein Element einer Menge entweder zugehörig ist, oder nicht; eine und genau eine der beiden Aussagen ist wahr. Mengen mit diesen strengen Grenzen im Sinne der klassischen Mengenlehre werden in der FL als Crisp-Sets bezeichnet.

Die FL basiert auf unscharfen Mengen, so genannten Fuzzy-Sets. Die Fuzzy-Set-Theorie ist über weite Strecken eine Generalisierung der klassischen Mengenlehre. [5] Eine klassische Menge A ist entweder durch ihre Elemente deniert, z.B. in der Form

A = {a, b, c, ...}

oder als Teil einer Obermenge X, für den eine bestimmte Bedingung zutrit, z.B. in der Form

A = {x ∈ X | x erfüllt die Bedingung cond}

Die Aussage x ∈ Xgehört zur TeilmengeA kann mathematisch äquivalent

13

über die sogenannte charakteristische Funktion µ

µ A : X → {0, 1}

beschrieben werden.

In der Fuzzy Logic werden - anstatt jedem Element der Obermenge X nur entweder 0 oder 1 zuzuordnen - den Elementen aus X verlaufende Werte zwischen 0 und 1 zugeordnet. Der jeweilige Wert beschreibt den Grad der Zugehörigkeit (Membership Value) eines jeden Elements aus X zur jeweiligen Teilmenge A. So eine Funktion

µ A : X → [0, 1]

wird als Zugehörigkeitesfunktion (Membership Function) bezeichnet. Die Boolsche Aussagenlogik birgt groÿe Einschränkungen im Hinblick auf die Darstellung von unscharfen Konzepten in sich. Man kann beispielsweise versuchen die Raumtemperatur im Sinne der Boolschen Logik mit den Begrien warm und kalt zu denieren. Es wird keinen Zweifel geben, dass 35 ◦ C warm, und nicht kalt ist. Ebenso wird man sich darauf verständigen, dass 5 ◦ C kalt, und folglich nicht warm ist. Für eine Raumtemperatur von 18 ◦ C allerdings wird es schon wesentlich schwieriger, sie mit den Begrien kalt und warm zu klassizieren. Die Boolsche Logik bietet keine Möglichkeit, Werte zwischen wahr und falsch (in den Abbildungen auf der Ordinate durch die Werte 1 und 0 dargestellt) zu identizieren.

Die Fuzzy Logic hingegen erlaubt jedem Element einer Grundmenge einen gewissen Grad an Zugehörigkeit zu einer anderen Menge. Dieser Grad der Zugehörigkeit, auch Membership-Value genannt, ist über eine Membership-Funktion deniert. Der Membership-Value liegt im Intervall [0, 1]. Der blaue Graph in Abbildung 2.1 repräsentiert die Membership-Funktion für kalt, der rote steht für warm. Der Wert 18 ◦ C gehört in der Boolschen Logik (linkes Bild in Abbildung 2.1) gar nicht zur Menge kalt, und ganz zur Menge warm. In der FL (rechtes Bild) sieht man, dass 18 ◦ C Teil von beiden Mengen (Fuzzy-Sets) ist, und zwar jeweils zu einem gewissen Grad an Zugehörigkeit. Dieser Grad an Zugehörigkeit (Membership-Value) ist über die Membership-Funktion deniert. In der Skizze sehen wir, dass der Wert 18 ◦ C zu etwa 0,4 dem Fuzzy-Set kalt und zu etwa 0,6 dem Fuzzy-Set warm zugehörig ist.

2.1.2 Logische Operatoren auf Fuzzy-Sets

Aussagen können mittels der logischen Operatoren UND und ODER kombiniert werden. Für die klassische zweiwertige Logik gilt die in Tabelle 2.1 dargestellte Wahrheitstabelle.

A B A und B A oder B nicht A

Entsprechend dieser Boolschen Wahrheitstabelle wurde für das Fuzzy-UND das Konzept der t-Normen (triangular Norms) entwickelt. Das Fuzzy-ODER wird entsprechend durch t-Conormen (auch s-Normen genannt) abgebildet. Die am häugsten verwendete t-Norm ist der Minimum-Operator, die dazugehörige s-Norm der Maximum-Operator. Tabelle 2.2 zeigt weitere gängige Kombinationen.

Die Anwendung der logischen Operatoren UND und ODER auf Fuzzy-Sets ist in Abbildung 2.2 grasch dargestellt. Die für das UND verwendete

15

Abbildung 2.2: Anwendung logischer Operatoren auf Fuzzy-Sets

s-Norm ist der Minimum-Operator. Für das ODER wird die dazugehörige t-Norm, der Maximum-Operator, verwendet.

2.1.3 Linguistische Variable und Linguistische Terme

Bei Fuzzy-Steuerungen oder Fuzzy-Entscheidungssystemen hat man in der Regel eine bestimmte Anzahl von Eingangswerten, die über linguistische Variablen, wie etwa Temperatur, Alter, Druck, Gröÿe, etc. angesprochen werden.

Am Beispiel eines Heizungssystems könnte eine der linguistischen Input-Variablen temperature heiÿen und einen exakten Wert (crisp Value) aus dem Bereich der reellen Zahlen beinhalten:

temperature = 22 ◦ C

Eine linguistische Variable hat einen Namen und und beinhaltet einen Wert aus dem Bereich der ihr zugeordneten linguistischen Terme. Die linguistischen Terme sind durch Fuzzy-Sets deniert.

Alle linguistischen Terme einer linguistischen Variable bilden gemeinsam ein Term-Set. Im Falle der Temperatur könnte das Term-Set folgendermaÿen aussehen:

Andere Beispiele für Linguistische Variable und dazugehörigem Term-Set sind:

Alter : jung, jugendlich, mittel, alt, sehr alt Gröÿe : sehr klein, klein, normal groÿ, riesig Auf die gleiche Art und Weise wie die Eingänge, werden auch die Ausgänge einer Fuzzy-Steuerung über linguistische Variable und Terme beschrieben.

2.1.4 Fuzzy Regeln

Fuzzy Logic bietet dem Entwickler die Möglichkeit, komplexe Systeme auf Basis seines Wissens und seiner Erfahrung, mittels natürlichsprachlich formulierter Regeln zu beschreiben. Es sind dabei keine Systemmodellierungen oder komplexe mathematische Gleichungssysteme notwendig um den Zusammenhang zwischen Inputs und Outputs herzustellen. Fuzzy-Regeln sind auch für technisch weniger versierte Personen leicht zu lesen und zu verstehen.

17

Es sind meist nur einige wenige Regeln vonnöten um ein System zu denieren. Die gängigste Form der Fuzzy-basierten Wissensdarstellung ist die IF-THEN-Regel, auch Fuzzy-Rule genannt. Die allgemeine Form einer Fuzzy-Rule ist

IF X IS A T HEN Y IS B

wobei A und B linguistische Terme (durch Fuzzy-Sets deniert), und X und Y linguistische Variable sind. Der linke Teil der Regel (X IS A) wird Bedingung (engl. condition, antecedent oder premise), der rechte Teil (Y IS B) Schlussfolgerung (engl. conclusion oder consequence) genannt. Die meisten Fuzzy-Steuerungen haben mehrere Eingangswerte (Input Values). Es ist daher auch möglich, dass die Bedingung einer Fuzzy-Rule eine Kombination mehrerer Eingänge beinhaltet, die durch logische Operatoren wie UND und ODER verbunden ist. Ein Beispiel dafür könnte folgendermaÿen aussehen:

IF room temperature IS ok AN D outside temperature IS cool

T HEN turn heating on a little

2.1.5 Fuzzy Inferenz System

Fuzzy Inferenz Systeme (FIS) sind ein praktikabler Ansatz für die Lösung verschiedenartiger Probleme. Haupteinsatzgebiete sind Steuerungsautomatisation, Klassizierung von Daten oder Entscheidungsndung. Die Grundidee ist immer, Expertenwissen und Erfahrung einieÿen zu lassen, wenn das erstellen eines exakten mathematischen Modells sehr aufwändig oder aufgrund der Komplexität des Systems praktisch unmöglich ist. Es gibt verschiedene Arten von FIS. Die am häugsten verwendete ist die Mamdani-Inferenz . Abbildung 2.4 zeigt das Grundschema eines Mamdani-FIS. In den folgenden Kapiteln werden die Einzelschritte im Detail erläutert. Nachdem alle Fuzzy-Sets und die Fuzzy-Rules deniert worden sind, arbeitet

18

ein FIS nach einem in fünf Schritte gegliederten Algorithmus. Die einzelnen Schritte werden in den folgenden Abschnitten anhand von Beispielen im Detail erklärt.

Schritt 1: Fuzzikation

Im ersten Schritt wird evaluiert welchen Grad an Zugehörigkeit (membership value) jeder Input-Value zu den entsprechenden Fuzzy-Sets hat. Abbildung 2.5 zeigt wie ein exakter Input-Value von 2, 2 ft zu 53 % near und 15 % good fuzziziert wird.

Schritt 2: Aggregation

Die Aggregation ermittelt den Wahrheitswert der gesamten Bedingung einer Fuzzy-Rule. Falls eine Bedingung aus eine Kombination (UND-, ODER-Verknüpfung) mehrerer Inputs besteht, so werden die Wahrheitswerte der Teilbedingungen (siehe Schritt 1: Fuzzikation) in diesem Schritt so kombiniert, dass man genau einen Wahrheitswert aus dem Intervall [0, 1] für die gesamte Bedingung erhält. Für UND-Verknüpfungen wird eine t-Norm, für ODER-Verknüpfungen eine s-Norm verwendet.

19

In Tabelle 2.3 ist dargestellt, wie man die beiden Teilbedingungen distance is near und distance is good in der Aggregation kombiniert. In diesem Beispiel wird als t-Norm der Minimum-Operator und als s-Norm der Maximum-Operator verwendet.

Bedingung Fuzzikation Fuzzikation Aggregierter

Tabelle 2.3: Aggregation

Schritt 3: Implikation

Die Implikation überträgt den durch die Aggregation ermittelten Wahrheitswert der Bedingung einer Fuzzy-Rule auf das Output-Fuzzy-Set der Schlussfolgerung der Regel. Es wird eine t-Norm (z.B. der Minimum-Operator) verwendet um den Wahrheitswert auf das Output-Fuzzy-Set anzuwenden. Abbildung 2.6 zeigt das anhand eines Fuzzy-Systems mit zwei Regeln. Bei Verwendung des Minimum-Operators, wie in diesem Beispiel, wird das Output-Fuzzy-Set einfach in der Höhe abgeschnitten, die als Ergebnis aus der Aggregation hervorgeht.

20

Schritt 4: Akkumulation

Falls mehrere Fuzzy-Rules auf die gleiche Output-Variable schlieÿen, wird eine Methode benötigt, welche die Implikationsergebnisse der betroenen Regeln kombiniert. Die abgeschnittenen Fuzzy-Sets werden unter Verwendung einer s-Norm kombiniert. Im Beispiel in Abbildung 2.7 wird der Maximum-Operator verwendet.

Schritt 5: Defuzzikation

Das Ergebnis der Akkumulation ist ein Fuzzy-Set bzw. eine Membership-Funktion, die das Fuzzy-Set beschreibt. Ein Gerät, das über das Fuzzy-

21

System gesteuert werden soll, kann üblicherweise mit einem Fuzzy-Set nichts anfangen, sondern benötigt einen exakten Wert. Die Aufgabe der Defuzzikation ist es nun, das Fuzzy-Set auf einen einzelnen Wert (crisp Value) zu reduzieren, der es am besten repräsentiert.

Es gibt viele verschiedene Defuzzikationsmethoden. Die meistverwendete ist die Schwerpunkt-Methode (Center of Gravity Method, CoG ). Bei dieser Methode wird der Ausgabewert bestimmt, indem zuerst der Schwerpunkt unter dem Graphen der Membership-Funktion ermittelt wird, und dieser dann auf die Abszisse projiziert wird (siehe Abbildung 2.8). Der Ausgabewert x crisp kann rechnerisch mittels folgender Formel ermittelt werden:

max

mit X als Ergebnis der Defuzzikation, x als Ausgabewert, µ als Membership-

22

Funktion nach der Akkumulation und min, max als untere und obere Grenzen für die betroenen Output-Variable.

2.2 Kohonen Self-Organizing-Feature-Map

Die im Jahr 1982 von Tuevo Kohonen entwickelte Self-Organizing-Feature-Map (SOFM) gehört zur Klasse der selbstorganisierenden Netze [14]. Man spricht in diesem Zusammenhang auch von unüberwachtem Lernen (unsupervised learning). Das überwachte Lernen basiert darauf, dass dem Netz den ermittelten Output mit dem durch einen Lehrer mitgeteilten richtigen Ergebnis vergleicht, und versucht, den Fehler zu minimieren. Ein Beispiel für ein neuronales Netz mit überwachtem Lernen ist das Multilayer-Perceptron mit Backpropagation-Algorithmus. Das hier verwendete Kohonen-Netzwerk hat im Gegensatz dazu keinen Lehrer . Es weiÿ also nicht, welches Ergebnis das richtige wäre. Die Aufgabe dieses Netzes ist vielmehr die verschiedenen Inputs zu kategorisieren. Es werden also - vereinfacht gesagt - ähnliche Inputs als gleichartig erkannt. Oder, etwas technischer ausgedrückt, die Aufgabe des Netzes besteht darin, allein durch Eingabe von zufällig ausgewählten Vektoren eine innere Repräsentation des Eingaberaums zu bilden. Die SOFM verfügt über eine bestimmte Anzahl von Eingabeeinheiten, deren Anzahl der Dimension der Trainingsvektoren entspricht. Zusätzlich besteht sie aus einer ein- oder zweidimensionalen Schicht von gitterförmig

23

angeordneten Neuronen (die eigentliche Feature-Map), die jeweils mit allen Eingabeeinheiten verbunden sind.[1][9] Die Aktivitäten werden von der Eingabeschicht hin zur Ausgabeschicht ausgebreitet. Abbildung 2.9 zeigt den Grundaufbau einer SOFM. Alle Neuronen der Eingabeschicht sind mit jedem anderen Neuron der Ausgabeschicht (Kartenschicht) verbunden. Jedes Neuron in der Ausgabeschicht ist eindeutig durch seine x und y Koordinaten bestimmt.[1]

Die Eingabeneuronen nehmen das externe Eingabesignal auf und leiten es weiter zur Ausgabeschicht. Das Hauptziel beim Lernen ist es die zu lernenden Muster auf die SOFM abzubilden, das heiÿt, es muss für jedes Muster ein Zentrum geben welches einem gelernten Muster entspricht. Um dieses Zentrum herum benden sich Neuronen welche diesem Muster ähnlich sind. Daraus ergibt sich, dass ähnliche Eingabemuster auf die selbe Region in der SOFM abgebildet werden.

2.2.1 Trainieren einer SOFM

Beim Lernalgorithmus des Kohonen-Netzwerks handelt es sich um kompetetives Lernen. Der Name kommt daher, dass die Neuronen in einem Wettbewerb stehen. Nur genau ein Neuron - das sogenannte Winner-Neuron - wird bei der Eingabe aktiviert. Es werden bei jedem Trainingsschritt die Gewichte w ij (siehe dazu Abbildung 2.9) in einer denierten Umgebung rund um das Winner-Neuron angepasst. Diese denierte Umgebung wird auch Nachbar-

24

schaft genannt und ist über den Radius r deniert (siehe Abbildung 2.10).

Ziel des Lernalgorithmus ist es, jedes Neuron der Ausgabeschicht auf einen bestimmten Bereich des Eingaberaums zu spezialisieren. Die Erregung des betroenen Neurons ist bei Eingaben aus eben diesem bestimmten Bereich des Eingaberaums maximal. Dabei sollen benachbarte Bereiche des Eingaberaums auch benachbarten Neuronen zugeordnet werden. Diese Strukturierung wird dadurch erreicht, dass nicht nur das Gewicht des Winner-Neurons angepasst wird, sondern auch die Nachbarschaft des Winner-Neurons an jedem Lernschritt teilnimmt.

Konkret besteht der Kohonen-Lernalgorithmus aus folgenden Schritten[ 9]: 1. Initialisierung: Die Gewichtsvektoren w i aller Neuronen i werden mit kleinen Werten initialisiert.

2. Stimuluswahl: Aus dem Eingaberaum X ⊆ R n wird ein Vektor x gemäÿ einer gegebenen Wahrscheinlichkeitsverteilung zufällig ausgewählt. 3. Bestimmung des Erregungszentrums: Das Erregungszentrum ist dasjenige Neuron k, dessen Gewichtsvektor w k dem Eingabevektor x ^{am nächsten liegt:} w k − x = min w i − x

4. Anpassung der Gewichte: Die Gewichtsvektoren aller Neuronen i in der Nachbarschaft des Erregungszentrums k mit Radius r werden um die

25

Dierenz

∆w i = α(x − w i )

verändert, wobei α > 0 die Lernrate ist. Dies bedeutet, dass die Ge-wichtsvektoren in Richtung des Eingabevektors gezogen werden.

5. Wiederholung: Die Schritte 2 bis 4 werden wiederholt und dabei die

Lernrate α sowie der Nachbarschaftsradius r sukzessive verkleinert, bis sich das Netz stabilisiert.

26

Kapitel 3

Implementierung

Die wesentlichen Bestandteile des Systems sind

• ein Roboter mit zwei unabhängig voneinander betriebenen Elektromo-toren für Geschwindigkeitsregulierung und Navigation, • eine handelsübliche Webcam mit USB-Anschluÿ, • ein PC (Notebook) zur Bildverarbeitung und zur Anwendung der KI-

Methoden. Beide Aufgaben übernimmt MATLAB r , ein Softwarepa-

ket, das von der Herstellerrma The Mathworks r wie folgt beschrie-

ben wird: MATLAB ist eine intuitive Sprache und eine Oberäche für technische Berechnungen. Es besteht aus einem mathematischen Kern und modernen Grak-Werkzeugen für Datenanalyse, Visualisierung sowie die Entwicklung von Algorithmen und Anwendungen. Weltweit verlassen sich eine groÿe Zahl von Wissenschaftlern und Ingenieuren auf MATLAB als strategische Entwicklungsplattform mit ihren über 600 mathematischen, statistischen und ingenieurwissenschaftlichen Funktionen. [25] PIC16F877 r • und ein Mikrocontroller (Microchip r ) zur Kommunika-

tion mit dem PC und zur Ansteuerung der Motoren.

27

3.1 Wege der Signalverarbeitung

Abbildung 3.1 gibt einen schematischen Überblick über Aufbau und Zusammenspiel der wesentlichen Komponenten des Systems.

1. Die Webcam nimmt Bilder auf und sendet diese an MATLAB r , das

am Laptop läuft.

2. MATLAB r analysiert die Bilder, erkennt eine Linie und sendet die

Lagedaten der Linie als Eingangsparameter an ein Fuzzy Inferenz System, welches als Ausgabe die Daten für die Ansteuerung der beiden Motoren liefert. Weiters wird im Bild nach Verkehrszeichen gesucht, die auf der Linie angebracht sind und dem Roboter die Fahrtgeschwindigkeit vorgeben. Die Motorsteuerungsdaten - ermittelt aus der Richtung der Linie und der Art des Verkehrszeichens - werden über eine seriel-

le Schnittstelle an den PIC16F877 r Mikrocontroller übermittelt. Die

dafür notwendigen Routinen hab ich in M r , der MATLAB r -eigenen

Programmiersprache implementiert. Die wesentlichen Teile des Source-Codes sind im Anhang beigefügt.

3. Der Mikrocontroller übernimmt die Ansteuerung der Motorbrücke. Die

Geschwindigkeit jedes einzelnen der beiden Motoren wird über Pulsweitenmodulation (PWM) reguliert. Diesen Teil der Software habe ich

in PIC-C, einer reduzierten C-Implementierung speziell für PIC r Mi-

krocontroller, geschrieben.

28

3.2 Hardware

Ein Chassis auf Rädern ist eines der einfachsten Konstruktionen eines fahrenden Roboters. Die Anzahl der Räder spielt dabei eine bedeutende Rolle. Die gängigsten Radroboter haben drei oder vier Räder. Im Bezug auf die Bodenhaftung kann die Anzahl der Räder sehr wesentlich sein. Ein Vehikel mit sehr vielen (angetriebenen) Rädern verhält sich ähnlich einem Kettenfahrzeug. Obwohl auf unebenem Terrain nicht alle Räder zu jedem Zeitpunkt Bodenkontakt haben ist ein Fortkommen möglich. Schwieriger gestaltet sich allerdings die Steuerung der Fahrtrichtung.

Abbildung 3.2 illustriert die stabilere Lage eines dreirädrigen gegenüber einem vierrädrigen Roboter auf unebenem Untergrund. Bei vier Rädern kann es passieren, dass ein Antriebsrad keine Bodenhaftung mehr hat. Ein Chassis mit drei Rädern dagegen hat immer mit allen Rädern Bodenkontakt, da durch beliebige drei Punkte im Raum eine Ebene gelegt werden kann. Ein weiterer Vorteil dieser Bauart ist die einfache und eektive Steuerung. Zwei voneinander unabhängig angetriebene Räder am Heck und ein frei bewegliches Stützrad vorne ermöglichen sehr enge Radien in jede Richtung. Für den hier beschriebenen Roboter wird das dreirädrige Chassis aus der Zeitschrift Real Robots r [20] inklusive Getriebe, zwei Elektromotoren und

einer Motorbrücke zum voneinander unabhängigen Betrieb der beiden Hinterräder verwendet.

Die Hauptbestandteile der Motorbrücke sind vier im Stromkreis angeord-

29

Abbildung 3.3: Bewegung eines dreirädrigen Roboters [6]

nete Transistoren, die wie simple Schalter funktionieren. Jeweils zwei Schalter werden, wie in Abbildung 3.4 dargestellt, gemeinsam geschalten. Aus den beiden Kombinationen SW1 + SW4 (Abbildung 3.4(b)) bzw. SW2 + SW3 (Abbildung 3.4(c)) ergibt sich die Laufrichtung des Motors, der in der Abbildung 3.3 durch den Buchstaben m gekennzeichnet ist.

Die Motorbrücke besitzt Pins sowohl für eine +6V als auch für eine +9V Stromversorgung und weitere vier Pins für die Ansteuerung der Motoren. Zur Regelung der Laufgeschwindigkeit der Motoren wird Pulsweitenmodulation (PWM) eingesetzt. PWM wird sowohl von der Motorbrücke als auch unterstützt. Der PWM-Ausgang des Mivom Mikrocontroller PIC16F877 r

krocontrollers ermöglicht das einfache Erzeugen von Impulsen mit einem ein-

30

stellbaren Taktverhältnis.[21]

3.3 Kommunikation

Für die Kommunikation zwischen dem Notebook und dem Mikrocontroller

am Roboter habe ich DCP (Device Communication Protocol ), ein speziell für den einfachen Datenaustausch zwischen verschiedenen Devices optimiertes Protokoll, entwickelt und implementiert.

Ein für diese Anwendung geeignetes Kommunikationsprotokoll muss meiner Meinung nach folgende Bedingungen erfüllen:

Einfachheit: Das Protokoll muss einfach implementierbar sein. Eine Implementierung auf einem Mikrocontrollers mit sehr beschränkten RAM-und CPU-Ressourcen muss möglich sein.

Ezienz: Der Kommunikationsoverhead soll möglichst gering sein, um nicht unnötig Bandbreite zu verschwenden.

Mehrere Devices: ^{Über ein und dieselbe Verbindung müssen mittels des Protokolls Daten für mehrere Devices übertragen werden können.} Symmetrie: Die Implementierung auf Sender- und Empfängerseite muss ident sein.

Variable Datengröÿe: Die Länge des Datenpakets per Device muss variabel sein, da die Daten unterschiedliche Devices auch unterschiedliche Datentypen haben können.

Flexibilität: Nicht jedes Device muss zu jedem Zeitpunkt einen Wert liefern.

3.3.1 Device Communication Protocol (DCP)

Abbildung 3.5 beschreibt die Struktur eines DCP-Paketes. Es besteht aus Daten für mehrere Devices. Für jedes dieser Devices enthält es ein Header

31

Byte, bestehend aus Device Identier (DID) und Länge der folgenden Daten (LoD). Durch ein Null-Byte wird das Paket abgeschlossen. Im Detail setzt sich ein DCP Paket aus folgenden Elementen zusammen: Device Identier (DID): 6 bit -> bis zu 64 Devices (000000 bin ..111111 bin ) Länge der Daten (LoD): 2 bit -> Variable Datenlänge für jedes Device, bis zu 4 Bytes:

01 bin ... byte (8 bit)

10 bin ... word (16 bit)

11 bin ... double (32 bit)

00 bin ... Ende der Daten (falls DID = 0)

Daten: 8, 16 or 32 bit (siehe "Länge der Daten") -> bis zu 2 ³² ≈ 4.3 ∗ 10 ⁹ verschiedene Werte

Während der Kommunikation zweier Kommunikationspartner unter Verwendung von DCP ist zu einem bestimmten Zeitpunkt immer einer der beiden Partner Sender, der andere Empfänger. Nach Übertragung eines vollständigen DCP-Pakets tauschen die Kommunikationspartner die Rollen und ein Paket wird in die andere Richtung übertragen. Der genaue Ablauf des Algorithmus ist in Abbildung 3.7 ersichtlich.