Autonome Roboternavigation mittels Methoden der künstlichen Intelligenz - TEIL 1

Inhaltsverzeichnis

1 Einleitung

2 Methoden der kiinstlichen Intelligenz
2.1 Fuzzy Logic
2.1.1 Fuzzy-Sets und Membership-Funktionen
2.1.2 Logische Operatoren auf Fuzzy-Sets
2.1.3 Linguistisehe Variable und Linguistisehe Terme ,
2.1.4 Fuzzy Regeln
2.1.5 Fuzzy Inferenz System
2.2 Kohonen Self-Organizing-Feature-Map
2.2.1 Trainieren einer SOFM

3 Implementierung
3.1 Wege der Signalverarbeitung
3.2 Hardware
3.3 Kommunikation
3.3.1 Device Communication Protocol (DCP)

4 Navigation entlang einer Linie
4.1 Identifizieren der Linie
4.1.1 Sehritt 1: Aufnahme eines Bildes
4.1.2 Sehritt 2: Transformation in das HSB-Farbmodell
4.1.3 Sehritt 3: Sliding Window Analyse
4.2 Fuzzy Logie fiir die Roboternavigation
4.2.1 Input Fuzzy Sets
4.2.2 Output Fuzzy Sets
4.2.3 Fuzzy Eegeln
4.2.4 Navigationsfunktion
4.2.5 Ergebnistransformation

5 Erkennung von Verkehrszeichen
5.1 Finden des Verkehrszeichen und Bildtransformation
5.1.1 Sehritt 1: Drehen
5.1.2 Sehritt 2: Aussehneiden des Verkehrszeichens
5.1.3 Sehritt 3: Grofie normieren
5.1.4 Sehritt 4: Entfarben
5.2 Klassihzierung der Verkehrszeichen mittels neuronalem Netz ,

6 Schlussfolgerungen

A Source Code

A.l robot,m

A.2 getlinepos.m

A.3 hndsign.m

Abbildungsverzeichnis

1.1 Roboter mit Kamera und Mikroeontroller

2.1 Boolean versus Fuzzy

2.2 Anwendung logiseher Operatoren auf Fuzzy-Sets

2.3 Linguistisehe Variable und Terme

2.4 Fuzzy Inferenz System [24]

2.5 Fuzzifikation

2.6 Implikation

2.7 Akkumulation

2.8 CoG Defuzzifikation

2.9 Aufbau einer SOFM [9]

2.10 Winner-Neuron und Naehbarsehaft

3.1 Wege der Signalverarbeitung

3.2 Radanzahl und Bodenkontakt [20]

3.3 Bewegung eines dreiradrigen Roboters [6]

3.4 Motorbriiekensehaltung [12]

3.5 DCP Paketaufbau

3.6 DCP Beispielpaket

3.7 DCP Programmstruktur

4.1 RGB-Farben

4.2 HSB-Farbenkreis

4.3 Umwandlung von RGB naeh HSB (HSV)[7]

4.4 Sliding Window

4.5 Winkel und Offset der Linie

4.6 Fuzzy Input Variable: Winkel and Offset

4.7 Fuzzy Output Variable: Riehtung

4.8 Navigationsfunktion

5.1 Originalbild

5.2 Bild naeh der Drehung

5.3 Extremstellen des Verkehrszeichens

5.4 Ausgeschnittenes Verkehrszeichen

5.5 Grohennormiertes Verkehrszeichen

5.6 Input fur das neuronale Netz

Tabellenverzeichnis

2.1 Boolsehe Wahrheitstabelle

2.2 t- und s-Normen

2.3 Aggregation

Kurzfassung / Abstract

Deutsch

Dieses Projekt verbindet untersehiedliehe Methoden und Teehnologien zu einem autonomen Roboter, der in der Lage ist, einer Linie zu folgen und auf am Weg befindliehe Verkehrszeichen situationsgereeht zu reagieren, Ne- ben Hardwaresteuerung und Bildverarbeitung bilden die Navigation entlang einer Linie mittels Fuzzy Logie und die Interpretation der Verkehrszeichen unter Verwendung einer Self-Organizing-Feature-Map (Kohonen-Netzwerk) die wesentliehen Bestandteile der Arbeit,

English

This project combines the areas fuzzy logic, neural nets, image processing and mobile robotics. The only sensor of the system is a camera, A fuzzy logic system navigates the robot along a line. Traffic signs along the road are detected, transformed and identified using a self organising feature map (Kohonen-network),

Danksagung

Ich bedanke mieh recht herzlieh bei Dr, Herbert Hortlehner, der wahrend meines Studium an der University of Derby dureh seinen unkonventionellen Unterrieht mein Interesse an Robotik und den Methoden der kiinstliehen Intelligenz geweckt hat.

Kapitel 1 Einleitung

Die Vision eines vollig selbstandig navigierenden Autos ist wohl so alt wie das Auto selbst, Viele teehnisehe Hilfsmittel, angefangen vom Riiekspiegel iiber automatisehe Gangsehaltung bis zu elektronisehen Einparkhilfen, erleiehtern zwar das fahren, trotzdem ist es naeh wie vor der Mensch, der das Fahr- zeug steuert und kontrolliert. Erst in den letzten Jahren kommt man dem autonomen Vehikel dureh Verwendung neuester Teehnologien der Kiinstli- ehen Intelligenz (KI) gepaart mit der Reehenleistung moderner Computer schrittweise naher,

Ziel dieser Arbeit ist es, ein vollig autonomes Vehikel zu entwiekeln, das in der Lage ist, auf einem ilim unbekannten Parkour situationsgereeht zu navigieren. Unter situationsgereeht wird hier verstanden, dass zum einen ein dureh eine farbige Linie gekennzeiehneter Kurs verfolgt wird und wahrend dessen Verkehrszeiehen befolgt werden, die an der Linie positioniert sind, Bei den Verkehrszeiehen handelt es sieh hier um Geschwindigkeitsbeschran- kungen, da auf diese einfaeh und wirkliehkeitsnah reagiert werden kann, Der Roboter verandert also wahrend der Fahrt entlang der Linie seine Geschwin- digkeit in Abhangigkeit von den Verkehrszeiehen, Die Idee zu diesem Projekt entstand bereits wahrend meines Studiums an der University of Derby, Dort hatte ieh die Mogliehkeit, mieh eingehend mit Fuzzy Logie (FL) zu besehaftigen, Besonders spannend ersehien mir im- mer die praktisehe Anwendung dieser Methoden, Also entwiekelte ieh im Rahmen meiner Diplomarbeit and der University of Derby eine web-basierte Fuzzy-Shell, uber 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 einfaeh, meist grafiseh, designed werden konnen, Das Heizverhalten kann via Web konfiguriert und mitverfolgt werden, Wahrend diese Heizung mit Innen- und Aufentemperaturfiihler zwar eine hiibsehe Anwendung ist, sieh mit Fuzzy-Steuerungen auseinander zu set- zen, sollte die naehste Herausforderung ein System sein, bei dem sieh „riehtig was riihrt“, also ein etwas sehnelleres Eehtzeitsvstem, So entstand die Idee des autonomen Fahrzeuges, Erstes Ziel war es nur, ein Fahrzeug mittels FL-Steuerung eine Linie ent- lang zu sehieken, Ieh zog dafiir verschiedene Mogliehkeiten in Betraeht, Eine war, eine dunkle Linie von hellem Untergrund fiber die Reflektion eines Lieht- strahls zu unterseheiden, Doeh wesentlieh spannender fand ieh, in das Projekt aueh Bilderkennungsmeehanismen zu integrieren. Fur diesen Zweek wurde an der Front des Roboters eine Kamera montiert, Aus der Uberlegung heraus, welehe Erweiterungsmoglichkeiten sieh dureh die Kamera ergeben, entstand die Idee zum zweiten grofen Teil dieses Projekts, namlieh die Identihkation von Verkehrszeiehen,

Abbildung 1,1 zeigt den verwendeten Versuchsaufbau. Die ..Si raise" wird dureh eine griine Linie auf weifem Untergrund dargestellt. Die Verkehrszei­ehen (in diesem Fall ein Stopp-Sehild) werden direkt auf die Linie positioniert.

Der Sehwerpunkt dieses Projekts liegt in der Entwieklung der Steuerungs- software unter Verwendung von KI-Methoden und nieht im Bereieh von Me- ehanik oder Elektronik, obwohl mieh dieses Projekt aueh in diesen Gebieten neue Erfahrungen sammeln lief., Um mogliehst raseh zur Implementierung der KI-Methoden am Roboter zu kommen, entsehied ieh mieh, das Chas­sis inklusive Getriebe und Motoren aus einem Bausatz des Magazins Real Robots®[20] zu verwenden, Sehwierigkeiten wahrend der Implementierung maehte die Bilderkennung unter weehselnden Liehtverhaltnissen, Die Umwandlung des Bildes vom RGB- in das HSV-Farbmodell (Farbmodelle werden spater detaillierter besehrie- ben) braehte sehlieflieh die Losung des Problems und maehte die weitere

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1,1: Robotor mit Kamera und Microcontroller

Bildvorarboitung woitgohond beleuehtungsunabhangig, Ein anderes Problem war die sehleehte Qualitat der Elektromotoren. Obwohl die Steuerung in der Simulation funktionierte, gab es in der Praxis anfanglieh Sehwierigkeiten, da die Motoren stark verzogert anliefen und nieht sofort stoppten, wenn das entspreehende Signal gesendet wurde. Dieses Problem wurde dureh entspre- ehendes Tuning des Fuzzy-Systems behoben,

Im folgenden Kapitel wird der theoretisehe Hintergrund der in diesem Projekt verwendeten Methoden beleuehtet, Im wesentliehen sind das Fuzzv- Logic und eine spezielle Form der kiinstliehen neuronalen Xetze, namlieh die Self-Organizing-Feature-Map naeh Tuevo Kohonen, Die Theorie zur Fuzzy Logie wurde in ahnlieher Form aueh in meiner Diplomarbeit an der University of Derby mit dem Titel „ Fuzzy Web - A Web-Based Approach to Fuzzy System Design“ 1221 publiziert.

Das Kapitel „Implementierung“ geht auf die einzelnen Hardwarekompo- nenten des Systems und deren Kommunikation untereinander ein, Fiir die Kommunikation habe ieh ein eigenes Protokoll entwiekelt, um mogliehst ein- faeh und efiizient Daten zwisehen den beteiligten Komponenten auszutau- sehen.

Kapitel 4 geht im Detail auf die Algorithmen ein, die fur die Identification einer Linie aus einem Bild und die Navigation entlang derselben verwendet wurden. Dieser Teil gliedert sieh grob in die Bildanalyse, die als Ergebnis die Lagekoordinaten der Linie liefert, und ein Fuzzy Logie System, das die entspreehenden Sehlusse bezuglieh der Navigation zieht.

In Kapitel 5 der genau besehrieben, wie einerseits erkannt wird, dass sieh ein Verkehrszeichen im Bliekfeld des Roboters befindet, und andererseits dieses Verkehrszeichen dann identifiziert und befolgt wird, Hier wird zuerst das Bild analvsiert und dann so transformiert, dass es von einem neuronalen Netz weiterverarbeitet werden kann. Das hier verwendete neuronale Netzwerk ist - naehdem es ausreiehend trainiert wurde - in der Lage festzustellen, um welches Verkehrszeichen es sieh im Einzelfall handelt.

Den Absehluss bilden ein paar Uberlegungen zu mogliehen Einsatzgebie- ten und Erweiterungen dieses Projekts,

Kapitel 2

Methoden der kiinstlichen Intelligenz

Fur die Steuerung des Eoboters werden zwei wesentliche Methoden der kiinst- liehen Intelligenz (KI) eingesetzt, Zum einen Fuzzy Logie (FL) und zum ande- ren eine spezielle Form der kiinstlichen neuronalen Netze, die Self-Organising- Feature-Map (SOFM), Die beiden Methoden werden in diesem Kapitel ein- gehend behandelt,

2.1 Fuzzy Logic

Loth Zadeh, Professor an der University of California in Berkeley, entwiekelte Mitte der 1960er-Jahre das Konzept der Fuzzy Logie (FL), Grundsatzlieh ist die FL eine Erweiterung der klassisehen Logik, die aueh Wahrheitswerte zwisehen den Boolsehen Werten wahr und falsch erlaubt, [13]

FL ermoglieht uns, Svsteme mittels in natiirlieher Spraehe formulierter Regeln zu besehreiben. Das FL System konvertiert diese Regeln in deren mathematisehe Interpretation, Auf diese Weise konnen beispielsweise Steue- rungsmeehanismen auf Basis von Expertenwissen und Erfahrungen erstellt werden, ohne die genauen teehnisehen Hintergriinde und Zusammenhange zu kennen. In vielen Fallen wird dadureh die Svstementwieklung erheblieh vereinfaeht und besehleunigt.

Zu Beginn hielt sieh die Anerkennung dieser Theorie sehr stark in Gren- zen. Erst als 1974 Professor Mamdani mit seinem Studenten Assilian ei- ne Dampfmasehine mittels FL steuerte, erweckte sie grofie Aufmerksamkeit, Es handelte sieh um die erste praktisehe Anwendung der FL, Ein weiterer Schritt, der FL zum Durehbrueh verhalf war die Entwieklung des ersten FL- Chips im Jahr 1975 dureh die Bell Laboratories, Der Chip wurde in der Folge in einer grofien Anzahl von Anwendungen, wie etwa Kameras oder Reis-Koehern verwendet. Heute ist FL einer der am sehnellsten waehsenden Bereiehe der kiinstliehen Intelligenz, [16]

2.1.1 Fuzzy-Sets unci Membership-Funktionen

Das klassisehe logisehe Denken basiert auf einer zweiwertigen Aussagenlogik, aueh Boolsche Logik genannt, Sie geht davon aus, dass jede Aussage entweder exakt wahr oder exakt falseh ist, Auf die Mengenlehre umgelegt heifit das, dass ein Element einer Menge entweder zugehorig ist, oder nieht; eine und genau eine der beiden Aussagen ist wahr, Mengen mit diesen strengen Gren- zen im Sinne der klassisehen Mengenlehre werden in der FL als Crisp-Sets bezeiehnet.

Die FL basiert auf unseharfen Mengen, so genannten Fuzzy-Sets, Die Fuzzy-Set-Theorie ist uber weite Streeken eine Generalisierung der klassi­sehen Mengenlehre, [5] Eine klassisehe Menge A ist entweder dureh ihre Ele- mente dehniert, z.B. in der Form

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

oder als Teil einer Obermenge X, fiir den eine bestimmte Bedingung zutrifft, z.B, in der Form

A = {x E X | x erfullt die Bedingung cond}

Die Aussage x E Xgehort zur TeilmengeA kann mathematiseh Equivalent

Abbildung in dieser Leseprobe nicht enthalten

besehrieben 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 Zugehorigkeit (Membership Value) eines jeden Elements aus X zur jeweiligen Teilmenge A. So eine Funktion

Abbildung in dieser Leseprobe nicht enthalten

wird als Zugehorigkeitesfunktion (Membership Function) bezeiehnet.

Die Boolsche Aussagenlogik birgt grofse Einsehrankungen im Hinbliek auf die Darstellung von unseharfen Konzepten in sich, Man kann beispielsweise versuehen die Raumtemperatur im Sinne der Boolsehen Logik mit den Be- griffen warm und kail zu definieren, Es wird keinen Zweifel geben, dass 35 °C warm, und nicht kalt ist, Ebenso wird man sich darauf verstandigen, dass 5°C kalt, und folglich nicht warm ist, Fiir eine Raumtemperatur von 18 °C allerdings wird es schon wesentlich schwieriger, sie mit den Begriffen kalt und warm zu klassifizieren. Die Boolsche Logik bietet keine Moglichkeit, Werte zwischen wahr und falseh (in den Abbildungen auf der Ordinate dureh die Werte 1 und 0 dargestellt) zu

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2,1: Boolean versus Fuzzy

Die Fuzzy Logie hingegen erlaubt jedem Element einer Grundmenge einen gewissen Grad an Zugehorigkeit zu einer anderen Menge, Dieser Grad der Zugehorigkeit, aueh Membership-Value genannt, ist iiber eine Membership- Funktion definiert, Der Membership-Value liegt im Intervall [0,1],

Der blaue Graph in Abbildung 2,1 reprasentiert die Membership-Funktion fur kalt, der rote steht fur warm, Der Wert 18 °C gehort in der Boolsehen Logik (linkes Bild in Abbildung 2,1) gar nieht zur Menge kalt, und ganz zur Menge warm. In der FL (reehtes Bild) sieht man, dass 18 °C Teil von beiden Mengen (Fuzzv-Sets) ist, und zwar jeweils zu einem gewissen Grad an Zugehorigkeit, Dieser Grad an Zugehorigkeit (Membership-Value) ist iiber die Membership- Funktion dehniert. In der Skizze sehen wir, dass der Wert 18 °C zu etwa 0,4 dem Fuzzv-Set kalt und zu etwa 0,6 dem Fuzzv-Set warm zugehorig ist,

2.1.2 Logische Operatoren auf Fuzzy-Sets

Aussagen konnen mittels der logisehen Operatoren UND und ODER kom- biniert werden, Fiir die klassisehe zweiwertige Logik gilt die in Tabelle 2,1 dargestellte Wahrheitstabelle,

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2,1: Boolsehe Wahrheitstabelle

Entspreehend dieser Boolsehen Wahrheitstabelle wurde fiir das Fuzzv- UND das Konzept der t-Normen (triangular Norms) entwiekelt. Das Fuzzv- ODER wird entspreehend dureh t-Conormen (aueh s-Normen genannt) ab- gebildet. Die am hauhgsten verwendete t-Norm ist der Minimum-Operator, die dazugehorige s-Norm der Maximum-Operator. Tabelle 2,2 zeigt weitere gangige Kombinationen,

Die Anwendung der logisehen Operatoren UND und ODER auf Fuzzy- Sets ist in Abbildung 2,2 grahseh dargestellt. Die fiir das UND verwendete

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2,2: t- und s-Xormen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2,2: Anwondung logiseher Oporatoron auf Fuzzy-Sets

s-Xorm ist dor Minimum-Operator, Fiir das ODER wird die dazugehorige t-Xorm, der Maximum-Operator, verwendet.

2.1.3 Linguistische Variable und Linguistische Terme

Bei Fuzzy-Steuerungen oder Fuzzy-Entseheidungssystemen hat man in der Regel eine bestimmte Anzahl von Eingangswerten, die iiber linguistische Va- riable.n, wie etwa Temperatur, Alter, Druck, Grofle, etc. angesproehen wer- den.

Am Beispiel eines Heizungssystems konnte eine der linguistisehen Input- Variablen temperature heilseti und einen exakten Wert (crisp Value) aus dem Bereieh der reellen Zahlen beinhalten:

temperature = 22° C

Eine linguistische Variable hat einen Xamen und und beinhaltet einen Wert aus dem Bereieh der ihr zugeordneten linguistisehen Terme. Die lin­guistisehen Terme sind dureh Fuzzy-Sets definiert.

temperature is cold

Alio linguistischen Terme oinor linguistisohon Variable bilden gemeinsam ein Term-Set, Im Falle der Temperatur konnte das Term-Set folgendermafsen aussehen:

temperature = {cold, COol,ok, hot}

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2,3: Linguistisehe Variable und Terme

Andere Beispiele fiir Linguistisehe Variable und dazugehorigem Term-Set sind:

Alter : jung, jugendlieh, mittel, alt, sehr alt

Grofie : sehr klein, klein, normal grofs, riesig

Auf die gleiehe Art und Weise wie die Eingange, werden aueh die Ausgan- ge einer Fuzzy-Steuerung iiber linguistisehe Variable und Terme besehrieben,

2.1.4 Fuzzy Regeln

Fuzzy Logie bietet dem Entwiekler die Mogliehkeit, komplexe Systeme auf Basis seines Wissens und seiner Erfahrung, mittels natiirliehspraehlieh for- mulierter Regeln zu besehreiben, Es sind dabei keine Systemmodellierungen oder komplexe mathematisehe Gleiehungssysteme notwendig um den Zusam- menhang zwisehen Inputs und Outputs herzustellen, Fuzzy-Regeln sind aueh fiir teehniseh weniger versierte Personen leieht zu lesen und zu verstehen.

Es sind meist nur einige wenige Regeln vonnoten um ein System zu defi- nieren. Die gangigste Form der Fuzzy-basierten Wissensdarstellung ist die IF-THEN-Regel, aueh Fuzzy-Rule genannt.

Die allgemeine Form einer Fuzzy-Rule ist

IF X IS A THEN Y IS B

wobei A mid B linguistische Terme (durch Fuzzv-Sets definiert), und X und Y linguistisehe Variable sind. Der linke Teil der Regel (X IS A) wird Be- dingung (engl. condition, antecedent oder premise), der reehte Teil (Y IS B) Schlussfolgerung (engl, conclusion oder consequence) genannt.

Die meisten Fuzzv-Steuerungen haben mehrere Eingangswerte (Input Va­lues), Es ist daher aueh moglieh, dass die Bedingung einer Fuzzy-Rule eine Kombination mehrerer Eingange beinhaltet, die durch logisehe Operatoren wie UND und ODER verbunden ist, Ein Beispiel dafiir konnte folgenderma- 6en aussehen:

IF room temperature IS ok AND outside temperature IS cool THEN turn heating on a little

2.1.5 Fuzzy Inferenz System

Fuzzy Inferenz Systeme (FIS) sind ein praktikabler Ansatz fiir die Losung verschiedenartiger Probleme, Haupteinsatzgebiete sind Steuerungsautomati- sation, Klassihzierung von Daten oder Entseheidungshndung, Die Grundidee ist immer, Expertenwissen und Erfahrung einfliefien zu lassen, wenn das er- stellen eines exakten mathematisehen Modells sehr aufwandig oder aufgrund der Komplexitat des Systems praktiseh unmoglieh ist, Es gibt verschiedene Arten von FIS, Die am hauhgsten verwendete ist die Mamdani-Inferenz, Abbildung 2,4 zeigt das Grundsehema eines Mamdani- FIS, In den folgenden Kapiteln werden die Einzelsehritte im Detail erlautert, Naehdem alle Fuzzv-Sets und die Fuzzv-Rules dehniert worden sind, arbeitet

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Fuzzy Inforonz System |24|

ein FIS naeh einem in fiinf Sehritte gegliederten Algorithmus. Die einzel- nen Sehritte werden in den folgenden Absehnitten anhand von Beispielen im Detail erklart,

Schritt 1: Fuzzifikation

Im ersten Schritt wird evaluiert welehen Grad an Zugehorigkeit (membership value) jeder Input-Value zu den entspreehenden Fuzzy-Sets hat, Abbildung 2,5 zeigt wie ein exakter Input-Value von 2, 2 ft zu 53 % near und 15 % good fuzzifiziert wird, Schritt 2: Aggregation

Die Aggregation ermittelt den Wahrheitswert der gesamten Bedingung ei- ner Fuzzy-Rule, Falls eine Bedingung aus eine Kombination (UXD-, ODER- Verkniipfung) mehrerer Inputs besteht, so werden die Wahrheitswerte der Teilbedingungen (siehe Schritt 1: Fuzzifikation) in diesem Schritt so kombi- niert, dass man genau einen Wahrheitswert aus dem Intervall [0,1] fiir die gesamte Bedingung erha.lt. Fiir UXD-Verkniipfungen wird eine t-Xorm, fiir ODER-Verkniipfungen eine s-Xorm verwendet.

In Tabelle 2,3 ist dargestellt, wio man die beiden Teilbedingungen di­stance is near und distance is good in der Aggregation kombiniert. In die- sem Beispiel wird als t-Xorm der Minimum-Operator und als s-Xorm der Maximum-Operator verwendet,

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2,3: Aggregation

Abbildung in dieser Leseprobe nicht enthalten

Schritt 3: Implikation

Die Implikation iibertragt den dureh die Aggregation ermittelten Wahrheits- wert der Bedingung einer Fuzzy-Rule auf das Output-Fuzzy-Set der Sehluss- folgerung der Regel, Es wird eine t-Xorm (z.B, der Minimum-Operator) ver­wendet urn den Wahrheitswert auf das Output-Fuzzy-Set anzuwenden, Ab­bildung 2,6 zeigt das anhand eines Fuzzy-Svstems mit zwei Regeln, Bei Ver- wendung des Minimum-Operators, wie in diesem Beispiel, wird das Output- Fuzzy-Set einfaeh in der Hohe abgesehnitten, die als Ergebnis aus der Aggre­gation hervorgeht.

Rule 1: IF distance IS near THEN motor speed IS forward

Abbildung in dieser Leseprobe nicht enthalten

Rule 2: IF distance IS good THEN motor speed IS slow forward

Abbildung in dieser Leseprobe nicht enthalten

Distance (feet) Motor Speed (Percent)

Abbildung 2,6: Implikation

Schritt 4: Akkumulation

Falls mehrere Fuzzy-Rules auf die gleiehe Output-Variable sehliefsen, wird ei- ne Methode benotigt, welehe die Implikationsergebnisse der betroffenen Re- geln kombiniert. Die „abgesehnittenen“ Fuzzy-Sets werden unter Verwendung einer s-Xorm kombiniert, Im Beispiel in Abbildung 2,7 wird der Maximum- Operator verwendet.

Schritt 5: Defuzzifikation

Das Ergebnis der Akkumulation ist ein Fuzzy-Set bzw, eine Membership- Funktion, die das Fuzzy-Set besehreibt, Ein Gerat, das iiber das Fuzzy System gesteuert werden soil, kann iiblielierweise mit einem Fuzzy-Set niehts anfangen, sondern benotigt einen exakten Wert, Die Aufgabe der Defuzzifi- kation ist es nun, das Fuzzy-Set auf einen einzelnen Wert (erisp Value) zu reduzieren, der es am besten reprasentiert,

Es gibt viele versehiedene Defuzzifikationsmethoden, Die meistverwende- te ist die Schwerpunkt-Methode (Center of Gravity Method, CoG), Bei dieser Methode wird der Ausgabewert bestimmt, indem zuerst der Sehwerpunkt un- ter dem Graphen der Membership-Funktion ermittelt wird, und dieser dann auf die Abszisse projiziert wird (siehe Abbildung 2,8), Der Ausgabewert xcrisp kann rechnerisch mittels folgender Formel ermit­telt werden:

Abbildung in dieser Leseprobe nicht enthalten

Funktion nach der Akkumulation und min, max als untere und obere Gren- zen fiir die betroffenen Output-Variable,

2.2 Kohonen Self-Organizing-Feature-Map

Die im Jahr 1982 von Tuevo Kohonen entwiekelte Self-Organizing-Feature- Map (SOFM) gehort zur Klasse der selbstorganisierenden Xetze |14|, Man sprieht in diesem Zusammenhang aueh von unuberwaehtem Le.rnen (unsuper­vised learning). Das iiberwaehte Lernen basiert darauf, dass dem Xetz den ermittelten Output mit dem dureh einen „Lehrer“ mitgeteilten riehtigen Er- gebnis vergleieht, und versueht, den Fehler zu minimieren, Ein Beispiel fiir ein neuronales Xetz mit iiberwaehtem Lernen ist das Multilayer-Pereeptron mit Baekpropagation-Algorithmus, Das hier verwendete Kohonen-Xetzwerk hat im Gegensatz dazu keinen „Lehrer“ , Es weifs also nieht, welches Ergebnis das riehtige ware. Die Aufgabe dieses Xetzes ist vielmehr die versehiedenen Inputs zu kategorisieren, Es werden also - vereinfaeht gesagt - ahnliehe Inputs als gleiehartig erkannt, Oder, etwas teehniseher ausgedriiekt, die Aufgabe des Xetzes besteht darin, allein dureh Eingabe von zufallig ausgewahlten Vekto- ren eine innere Representation des Eingaberaums zu bilden.

Die SOFM verfiigt iiber eine bestimmte Anzahl von Eingabeeinheiten, deren Anzahl der Dimension der Trainingsvektoren entsprieht, Zusatzlieh besteht sie aus einer ein- oder zweidimensionalen Sehieht von gitterformig angeordneten Xeuronen (die eigentdiehe Feature-Map), die jeweils mit alien Eingabeeinheiten verbunden sind.11119| Die Aktivitaten werden von der Ein- gabesehieht hin zur Ausgabesehieht ausgebreitet. Abbildung 2,9 zeigt den Grundaufbau einer SOFM, Alle Xeuronen der Eingabesehieht sind mit je- dem anderen Xeuron der Ausgabesehieht (Kartensehieht) verbunden, Jedes Xeuron in der Ausgabesehieht ist eindeutig durch seine x und y Koordinaten bestimmt,|l|

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2,9: Aufbau einer SOFM |9|

Die Eingabeneuronen nehmen das externe Eingabesignal auf und leiten es weiter zur Ausgabesehieht, Das Hauptziel beim Lernen ist es die zu lernen- den Muster auf die SOFM abzubilden, das heilst. es muss fiir jedes Muster ein Zentrum geben welehes einem gelernten Muster entsprieht, Um dieses Zentrum herum behnden sieh Xeuronen welehe diesem Muster ahnlieh sind, Daraus ergibt sieh, dass ahnliehe Eingabemuster auf die selbe Region in der SOFM abgebildet werden,

2.2.1 Trainieren einer SOFM

Beim Lernalgorithmus des Kohonen-Xetzwerks handelt es sieh um kompe.teii- ves Lernen. Der Xame kommt daher, dass die Xeuronen in einem Wettbewerb stehen, Xur genau ein Xeuron - das sogenannte Winne.r-Ne.uron - wird bei der Eingabe aktiviert, Es werden bei jedem Trainingssehritt die Gewiehte Wj (siehe dazu Abbildung 2,9) in einer dehnierten Umgebung rund um das Winner-Xeuron angepasst, Diese dehnierte Umgebung wird aueh Xaehbar-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2,10: Winner-Xeuron und Xaehbarsehaft

Ziel des Lernalgorithmus ist es, jedes Xeuron der Ausgabesehieht auf einen bestimmten Bereieh des Eingaberaums zu spezialisieren. Die Erregung des betroffenen Neurons ist bei Eingaben aus eben diesem bestimmten Bereieh des Eingaberaums maximal, Dabei sollen benaehbarte Bereiehe des Einga­beraums aueh benaehbarten Xeuronen zugeordnet werden, Diese Strukturie- rung wird dadureh erreieht, dass nieht nur das Gewieht des Winner-Xeurons angepasst wird, sondern aueh die Xaehbarsehaft des Winner-Xeurons an je- dem Lernsehritt teilnimmt,

Konkret besteht der Kohonen-Lernalgorithmus aus folgenden Sehritten| 9|:

1, Initialisierung: Die Gewichtsvektoren wi aller Neuronen i werden mit kleinen Werten initialisiert,

2, Stimuluswahl: Aus dem Eingaberaum X C Rra wird ein Vektor x gemah einer gegebenen Wahrseheinliehkeitsverteilung zufallig ausgewahlt,

3, BestAmmung des Erregungszentrums: Das Erregungszentrum ist das- jenige Xeuron k, dessen Gewichtsvektor wk dem Eingabevektor x am naehsten liegt:

Abbildung in dieser Leseprobe nicht enthalten

4, Anpassung der Gewichte: Die Gewichtsvektoren aller Xeuronen i in der Xaehbarsehaft des Erregungszentrums k mit Radius r werden um die

Differenz

Abbildung in dieser Leseprobe nicht enthalten

verandert, wobei a > 0 die Lernrate ist. Dies bedeutet, dass die Ge- wichtsvektoren in Riehtung des Eingabevektors gezogen werden.

5, Wiederholung: Die Sehritte 2 bis 4 werden wiederholt und dabei die Lernrate a sowie der Nachbarschaftsradius r sukzessive verkleinert, bis sieh das Netz stabilisiert.

Kapitel 3

Implementierung

Die wesentlichen Bestandteile des Systems sind

- ein Roboter mit zwei unabhangig voneinander betriebenen Elektromo- toren fiir Geschwindigkeitsregulierung und Navigation,

- eine handelsiibliehe Webcam mit USB-Ansehlub,

- ein PC (Notebook) zur Bildverarbeitung und zur Anwendung der KI- Methoden, Beide Aufgaben iibernimmt MATLAB®, ein Softwarepa- ket, das von der Herstellerfirma The Mathworks® wie folgt besehrie- ben wird: ..MA I L A B ist eine intuitive Sprache und eine Oberflache fur technische Berechnungen. Es besteht aus einem mathematischen Kern und modernen Graftk- Werkzeugen fiir Datenanalyse, Visualisierung so­me die Entwicklung von Algorithmen und Anwendungen. Weltweit ver- lassen sich eine grofie Zahl von Wissenschaftlern und Ingenieuren auf MATLAB als strategische Entwicklungsplattform mit ihren iiber 600 'mathematischen, statistischen und ingenieurwissenschaftlichen Funk- tionen. “ [25]

- und ein Mikrocontroller (Microchip® PIC16F877®) zur Kommunika- tion mit dem PC und zur Ansteuerung der Motoren,

3.1 Wege der Signalverarbeitung

Abbildung 3,1 gibt oinon sehematisehen Uberbliek iiber Aufbau und Zusam- menspiel der wesentliehen Komponenten des Systems,

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,1: Wege der Signalverarbeitung

1, Die Webcam nimmt Bilder auf und sendet diese an MATLAB®, das am Laptop lauft,

2, MATLAB® analysiert die Bilder, erkennt eine Linie und sendet die Lagedaten der Linie als Eingangsparameter an ein Fuzzy Inferenz Sys­tem, welches als Ausgabe die Daten fiir die Ansteuerung der beiden Motoren liefert, Weiters wird im Bild nach Verkehrszeiehen gesucht, die auf der Linie angebraeht sind und dem Roboter die Fahrtgesehwindig- keit vorgeben. Die Motorsteuerungsdaten - ermittelt aus der Riehtung der Linie und der Art des Verkehrszeiehens - werden iiber eine seriel- le Schnittstelle an den PIC16F877® Mikrocontroller iibermittelt. Die dafiir notwendigen Routinen hab ich in M®, der MATLAB ®-eigenen Programmiersprache implementiert. Die wesentliehen Teile des Source- Codes sind im Anhang beigefiigt,

3, Der Mikrocontroller iibernimmt die Ansteuerung der Motorbriieke, Die Gesehwindigkeit jedes einzelnen der beiden Motoren wird iiber Puls- weitenvwdulation (PWM) reguliert, Diesen Teil der Software habe ich in PIC-C, einer reduzierten C-Implementierung speziell fiir PIC ® Mi­krocontroller, gesehrieben.

3.2 Hardware

Ein Chassis auf Radern ist eines dor oinfaohston Konstruktionon oinos fah- renden Robotors. Die Anzahl der Rader spielt dabei eine bedeutende Rolle, Die gangigsten Radroboter haben drei odor vier Rader, Im Bezug auf die Bodenhaftung kann die Anzahl der Rader sehr wesentdieh sein, Ein Vehikel mit sehr vielen (angetriebenen) Radern verha.lt sieh ahnlieh einem Ketten- fahrzeug, Obwohl auf unebenem Terrain nieht alle Rader zu jedem Zeitpunkt Bodenkontakt haben ist ein Fortkommen moglieh, Sehwieriger gestaltet sieh allerdings die Steuerung der Fahrtriehtung,

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,2: Radanzahl und Bodenkontakt |20|

Abbildung 3,2 illustriert die stabilere Lage eines dreiradrigen gegeniiber einem vierradrigen Roboter auf unebenem Untergrund, Bei vier Radern kann es passieren, dass ein Antriebsrad keine Bodenhaftung mehr hat, Ein Chas­sis mit drei Radern dagegen hat immer mit alien Radern Bodenkontakt, da dureh beliebige drei Punkte im Raum eine Ebene gelegt werden kann, Ein weiterer Vorteil dieser Bauart ist die einfaehe und effektive Steuerung, Zwei voneinander unabhangig angetriebene Rader am Heek und ein frei bewegli- ehes Stiitzrad vorne ermogliehen sehr enge Radien in jede Riehtung,

Fiir den hier besehriebenen Roboter wird das dreiradrige Chassis aus der Zeitschrift Real Robots®[20] inklusive Getriebe, zwei Elektromotoren und einer Motorbriieke zum voneinander unabhangigen Betrieb der beiden Hin- terrader verwendet,

Die Hauptbestandteile der Motorbriieke sind vier im Stromkreis angeord-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,3: Bowogung eines dreiradrigen Roboters [ 6|

note Transistoron, die wie simple Sehalter funktionieren. Jeweils zwei Sehal- ter werden, wie in Abbildung 3,4 dargestellt, gemeinsam gesehalten, Aus den beiden Kombinationen SW1 + SW4 (Abbildung 3.4(b)) bzw. SW2 + SW3 (Abbildung 3.4(e)) ergibt sieh die Laufriehtung des Motors, der in der Ab­bildung 3.3 dureh den Buehstaben m gekennzeiehnet ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Motorbriiekensehaltung |12|

Die Motorbriieke besitzt Pins sowohl fiir eine —6V als aueh fiir eine —9V Stromversorgung und weitere vier Pins fiir die Ansteuerung der Motoren. Zur Regelung der Laufgesehwindigkeit der Motoren wird Pulsweitenmodu- lation (PWM) eingesetzt. PWM wird sowohl von der Motorbriieke als aueh vom Mikrocontroller PIC16F877® unterstiitzt. Der PWM-Ausgang des Mi- kroeontrollers ermoglieht das einfaehe Erzeugen von Impulsen mit einem ein- stellbaren Taktverhaltnis.[21]

3.3 Kommunikation

Fiir die Kommunikation zwischen dem Notebook und dem Mikroeontroller am Roboter habe ieh DCP (Device Communication Protocol), ein speziell fiir den einfaehen Datenaustauseh zwischen verschiedenen Devices optimiertes Protokoll, entwiekelt und implementiert,

Ein fiir diese Anwendung geeignetes Kommunikationsprotokoll muss mei- ner Meinung naeh folgende Bedingungen erfiillen:

Einfachheit: Das Protokoll muss einfaeh implementierbar sein, Eine Imple- mentierung auf einem Mikroeontrollers mit sehr besehrankten RAM- und CPU-Ressoureen muss moglieh sein,

Effizienz: Der Kommunikationsoverhead soil mogliehst gering sein, um nieht unnotig Bandbreite zu verschwenden.

Mehrere Devices: Uber ein und dieselbe Verbindung miissen mittels des Protokolls Daten fiir mehrere Devices iibertragen werden konnen.

Symmetric: Die Implementierung auf Sender- und Empfangerseite muss ident sein.

Variable Datengroie: Die Lange des Datenpakets per Device muss varia- bel sein, da die Daten untersehiedliehe Devices aueh untersehiedliehe Datentvpen haben konnen,

Flexibilitat: Nieht jedes Device muss zu jedem Zeitpunkt einen Wert lie- fern,

3.3.1 Device Communication Protocol (DCP)

Abbildung 3,5 besehreibt die Struktur eines DCP-Paketes, Es besteht aus Daten fiir mehrere Devices, Fiir jedes dieser Devices enthalt es ein Header

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,5: DCP Paketaufbau

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,6: DCP Beispielpaket

Wahrond dor Kommunikation zweier Kommunikationspartnor untor Vor- wondung von DCP ist zu oinom bostimmton Zoitpunkt immor oinor dor boi- den Partner Sender, der andere Empfanger, Xaeh Ubertragung eines voll- standigon DCP-Pakets tausehen die Kommunikationspartnor die Rollon und ein Paket wird in die andere Riohtung iibertragen. Der genaue Ablauf des Algorithmus ist in Abbildung 3,7 ersiohtlioh.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,7: DCP Programmstruktur