View
112
Download
3
Category
Preview:
Citation preview
Projektgruppe KIMAS – KI KL 1/25
UNIVERSITY OF
PADERBORN
Projektgruppe KIMAS
Künstliche Intelligenz und
Künstliches Leben
10.09.2003
Falk Windheim
Projektgruppe KIMAS – KI KL 2/25
UNIVERSITY OF
PADERBORN
Gliederung
1. Motivation2. Künstliche Intelligenz
1. Einführung2. Suche3. Logisches Schließen
3. Künstliches Leben1. Einführung2. Zellularautomaten3. KL in maschinennahen Welten
4. Literatur
Projektgruppe KIMAS – KI KL 3/25
UNIVERSITY OF
PADERBORN
Motivation
Die PG-KIMAS will Agenten schaffen die in der 3-dimensionalen Welt von Quake III bestehen können
Hierzu müssen diese Agenten ein gewisses Maß an Intelligenz besitzen, die von uns künstlich geschaffen werden muss
Es ist daher sinnvoll einmal die zu dieser Aufgabe passenden Forschungsgebiete KI und KL geben vorzustellen
Projektgruppe KIMAS – KI KL 4/25
UNIVERSITY OF
PADERBORN
Künstliche Intelligenz
Projektgruppe KIMAS – KI KL 5/25
UNIVERSITY OF
PADERBORN
Künstliche Intelligenz und ihre 4 Ansätze
Projektgruppe KIMAS – KI KL 6/25
UNIVERSITY OF
PADERBORN
Künstliche Intelligenz - Suche
Projektgruppe KIMAS – KI KL 7/25
UNIVERSITY OF
PADERBORN
Einleitung
Das Lösen von Problemen lässt sich im Allgemeinen als Suche nach der richtigen Lösung auffassen
Ein Grund sich näher mit verschiedenen Suchmethoden zu befassen
Im Folgenden werde ich an einem Beispiel die Vorteile eines intelligenten Suchverfahren demonstrieren
Projektgruppe KIMAS – KI KL 8/25
UNIVERSITY OF
PADERBORN
Suchbeispiel
Sei folgendes Problem gegeben: In einem Streckennetz (z.B. Schiene oder Strasse) soll die kürzeste Verbindung zwischen zwei gegebenen Orten gefunden werden
Projektgruppe KIMAS – KI KL 9/25
UNIVERSITY OF
PADERBORN
Dijkstra
Eine Möglichkeit ist der Kürzeste Wege Algorithmus von Dijkstra, einer auf gewichtete Graphen angepassten Breitensuche
Das Streckennetz wird einfach als gewichteter Graph interpretiert, und der Algorithmus wird vom Ausgangsort aus gestartet und es wird solange gesucht, bis das Ziel gefunden wurde
Projektgruppe KIMAS – KI KL 10/25
UNIVERSITY OF
PADERBORN
Dijkstra
Genau wie Breitensuche beginnt der Algorithmus also am Startpunkt und sucht in alle Richtungen gleichzeitig, bis er das Ziel gefunden hat
Projektgruppe KIMAS – KI KL 11/25
UNIVERSITY OF
PADERBORN
Bewertung
Dijkstra findet auf jeden Fall den kürzesten Weg
Dadurch das jedoch auch in eher abwegige Richtungen gesucht wird, wird Rechenzeit verschwendet
Anders sind hier Verfahren die Informationen über die Problemdomäne verwenden, um ihre Suche auf vielversprechende Bereiche zu fokussieren sogenannte informierte Suchverfahren
Projektgruppe KIMAS – KI KL 12/25
UNIVERSITY OF
PADERBORN
Informierte Suchverfahren (Best First Search)
Wie kann man dieses ‚vielversprechend‘ in eine algorithmisch verwendbare Form bringen?
Man kann zum Beispiel die Länge eines Weges, der über eine bestimmte Zwischenstation führt, schätzen in dem man den Luftlinienabstand verwendet
Und im Folgenden zunächst in Richtungen suchen die einen kleineren Schätzwert aufweisen
Projektgruppe KIMAS – KI KL 13/25
UNIVERSITY OF
PADERBORN
Informierte Suchverfahren (Best First Search)
Sucht man immer in Richtung der vielversprechendsten Zwischenstation, so ist es teilweise möglich viel Suchzeit zu sparen
Projektgruppe KIMAS – KI KL 14/25
UNIVERSITY OF
PADERBORN
Anwendungsbeispiel:Suche in Brettspielen
Ein Anwendungsgebiet von Suche ist es die Spielbaumsuche in Brettspielen
Folgende Leistungsklassen werden hierbei von Programmen für bestimmte Spiele erreicht:• Schach (8x8 Felder, 12 Spielsteintypen) –
Großmeister• Go (19x19 Felder, 2 Spielsteintypen) – Amateur• Reversi (8x8 Felder, 1 Spielsteintyp) –
Übermenschlich Ergebnis - je größer der Suchraum, desto
schlechter ist der Rechner relativ zum Menschen
Projektgruppe KIMAS – KI KL 15/25
UNIVERSITY OF
PADERBORN
Künstliche Intelligenz – Logisches Schließen
Projektgruppe KIMAS – KI KL 16/25
UNIVERSITY OF
PADERBORN
Logisches Schließen
Im Folgenden möchte ich anhand des Wumpusspiels zeigen wie logisches Schließen benutzet werden kann um sinnvolles Verhalten zu erzeugen
Projektgruppe KIMAS – KI KL 17/25
UNIVERSITY OF
PADERBORN
Das Wumpusspiel
Projektgruppe KIMAS – KI KL 18/25
UNIVERSITY OF
PADERBORN
Ausgangswissen des Agenten
Projektgruppe KIMAS – KI KL 19/25
UNIVERSITY OF
PADERBORN
Erste Erkenntnisse
Projektgruppe KIMAS – KI KL 20/25
UNIVERSITY OF
PADERBORN
Weitere Erkenntnisse
Projektgruppe KIMAS – KI KL 21/25
UNIVERSITY OF
PADERBORN
Logischer Schluss
Projektgruppe KIMAS – KI KL 22/25
UNIVERSITY OF
PADERBORN
Künstliches Leben
Projektgruppe KIMAS – KI KL 23/25
UNIVERSITY OF
PADERBORN
Einleitung
Zunächst – Was ist überhaupt Leben? Gängige Definitionen beinhalten Eigenschaften
wie z.B:• Vermehrungsfähigkeit• Stoffwechsel• ...
Dies ist jedoch selbst bei einfachen Dingen nicht ausreichend (Feuer, Maultiere,...)
Zusammengefasst: Es existiert (noch) keine endgültige Definition des Begriffs Leben
Projektgruppe KIMAS – KI KL 24/25
UNIVERSITY OF
PADERBORN
Warum Künstliches Leben?
Die meisten KL-Forscher versuchen aber auch gar nicht etwas zu erschaffen was ‚lebt‘
Viel mehr versuchen sie die vorteilhaften Eigenschaften die Leben zeigt in künstliche Systeme einzubauen, als da wären:• Selbstreproduktion• Selbstorganisation• Lösungsfindung durch Evolution• ...
Projektgruppe KIMAS – KI KL 25/25
UNIVERSITY OF
PADERBORN
Künstliches Leben –Zellularautomaten
Projektgruppe KIMAS – KI KL 26/25
UNIVERSITY OF
PADERBORN
von Neumanns Idee
Der erste der einen umsetzbaren Entwurf für ein selbstreproduzierendes System lieferte war der Mathematiker John v.Neumann (`04-`57)
Sein erster Entwurf sah einen Automaten vor, der in einem See von Bauteilen schwimmt
Dieser Automat sollte bestehen aus: Sensoren die Bauteile zu erkennen Elementen die Bauteile zu manipulieren• Einer steuernden Recheneinheit• Informationen über seinen eigenen Aufbau
Dieses sogenannte ‚Kinematische Modell‘ war natürlich noch nicht umsetzbar
Projektgruppe KIMAS – KI KL 27/25
UNIVERSITY OF
PADERBORN
Zellularautomaten
Erst als ihm ein Kollege die Verwendung eines Zellularautomaten als Grundlage vorschlug gelang eine umsetzbarer Entwurf
Zellularautomaten bestehen aus einem n-dimensionalen Gitter von endlichen Automaten
Das gesamte Gitter ist mit Zeitschritten getaktet
Zu jedem Zeitschritt bestimmt jeder der Automaten (Zelle) seinen neuen Zustand anhand der vorherigen Zustände von sich selbst und seinen Nachbarn
Projektgruppe KIMAS – KI KL 28/25
UNIVERSITY OF
PADERBORN
Selbstreproduzierende Strukturen in Zellularautomaten
Auf dieser Grundlage gelang nun ein solcher Entwurf. Es waren 200.000 Zellen und 29 verschiedene Zustände hierfür nötig
Diese gewaltigen Zahlen wurden u.a. benötigt weil der Automat turingmächtig sein sollte
Verzichtet man auf die Turingmächtigkeit so sind auch kleinere Entwürfe ausreichend
1986 benötigte Langton 9 Zustände und 179 Regeln für seine berühmten Langtonschleifen
Projektgruppe KIMAS – KI KL 29/25
UNIVERSITY OF
PADERBORN
Langtons Schleifen
Projektgruppe KIMAS – KI KL 30/25
UNIVERSITY OF
PADERBORN
Wolframs Zellularautomatenklassen
Wie muss ein Zellularautomat beschaffen sein, damit sich komplexe Strukturen in ihm entwickeln können?
Hinweise hierzu lieferte Wolfram. Dieser untersuchte 1983 eine große Zahl Zellularautomaten und fand hierbei 4 Klassen: I - Entwickeln einen homogenen Endzustand II - Einfaches zyklisches Verhalten III - Chaotisches strukturloses Verhalten IV - Entwickeln komplexe haltbare Strukturen
Projektgruppe KIMAS – KI KL 31/25
UNIVERSITY OF
PADERBORN
Langton und Lambda
Es gibt also 4 Klassen - doch wodurch wird bestimmt zu welcher Klasse ein Automat gehört?
Von Langton stammt eine Maßeinheit, mit welcher man dies bestimmen kann, der sogenannten Lambdaparameter
Um jedoch den Lambdaparameter verstehen zu können muss zunächst ein weiterer Begriff erklärt werden, der des ‚Bewegungslosen Zustands‘
Projektgruppe KIMAS – KI KL 32/25
UNIVERSITY OF
PADERBORN
Konstruiert man eine Struktur für einen Zellularautomaten, so benötigt man zumeist einen Zustand der den Teil der Welt beschreibt, welcher nicht zu der Struktur gehört:
Der Bewegungslose Zustand
Projektgruppe KIMAS – KI KL 33/25
UNIVERSITY OF
PADERBORN
Bewegungsloser Zustand: Definition
Wenn man in einem vorgegebenen Zellularautomaten den bewegungslosen Zustand identifizieren will, so hilft diese Definition:
Ein Zustand wird als Bewegungsloser Zustand bezeichnet, wenn aus ihm heraus alle gleichförmigen Nachbarschaften (Sprich alle Zellen im gleichen Zustand) auf ihn selbst zurückabgebildet werden
Projektgruppe KIMAS – KI KL 34/25
UNIVERSITY OF
PADERBORN
Lambdaparameter
Der Lambdaparameter eines Automaten ist nun einfach die Wahrscheinlichkeit mit welcher seine Regeln nicht in den Bewegungslosen Zustand abbilden
Dieses Lambda lässt sich nun verwenden um Wolframs Klassen zu identifizieren
Projektgruppe KIMAS – KI KL 35/25
UNIVERSITY OF
PADERBORN
Künstliches Leben – Maschinennahe Welten
Projektgruppe KIMAS – KI KL 36/25
UNIVERSITY OF
PADERBORN
Core Wars
Doch nicht nur Zellularautomaten können als Grundlage für künstliches Leben dienen
`90 verwendete Rasmussen das Programmierspiel Core Wars als Grundlage für einen Versuch
Core Wars findet in einem simulierten ring-förmigen Arbeitspeicher statt.
In diesem versuchen von den Spielern geschriebene Assemblerprogramme versuchen einander zu vernichten
Projektgruppe KIMAS – KI KL 37/25
UNIVERSITY OF
PADERBORN
VENUS
Rasmussen nun startete ein Core Wars Spiel Doch statt den Speicher mit konstruierten
Programmen zu füllen füllte er ihn mit Zufallsgenerierten Bytesequenzen
Darüber hinaus führte er eine Funktion ein die in zu zufälligen Zeitpunkten Speicherstellen zufällig änderte – als Simulation von Mutation
Rasmussen hoffte, das sich sich in dieser von ihm VENUS genannten Welt komplexe selbstvermehrende Programme entwickeln würden
Projektgruppe KIMAS – KI KL 38/25
UNIVERSITY OF
PADERBORN
VENUS - Ergebnisse
In VENUS entwickeln sich jedoch keinerlei komplexe Programme
Es stellte sich lediglich heraus das eine gewisse Befehlskombination recht erfolgreich den Speicher sättigte
VENUS war jedoch kein kompletter Fehlschlag, denn es inspirierte Ray zu seinem Tierra-System:
Projektgruppe KIMAS – KI KL 39/25
UNIVERSITY OF
PADERBORN
Tierra
Der Wissenschaftler Thomas Ray erkannte einen Nachteil von VENUS darin das der zugrundeliegende Maschinecode zu anfällig war
Ray entwickelte daher einen flexibleren Code der unanfälliger gegenüber zufälligen Veränderungen war
Dann schuf er ein Urahnenprogramm setzte es in den simulierten Speicher und ließ die Simulation laufen:
Projektgruppe KIMAS – KI KL 40/25
UNIVERSITY OF
PADERBORN
Künstliche Evolution in Tierra
Zunächst vermehrte der Urahn sich und seine Nachkommen bevölkerten den Speicher
Nach einiger Zeit jedoch traten Parasitenprogramme auf die die Urahnen ausnutzten um sich selbst zu vermehren
Daraufhin...es würde an dieser Stelle zu weit führen alle Entwicklungen in Tierra aufzuzählen es sei jedoch gesagt das ein interessantes evolutionäres Wettrüsten einsetzte
Projektgruppe KIMAS – KI KL 41/25
UNIVERSITY OF
PADERBORN
Literatur
Projektgruppe KIMAS – KI KL 42/25
UNIVERSITY OF
PADERBORN
Literatur
Adami, Christoph, Introduction to Artificial Life, 1998 Springer-Verlag New York, Inc.
Levy, Steven, KL – Künstliches Leben aus dem Computer, 1993 Droemer-Knaur
Russell, Stuart und Norvig, Peter, Artificial Intelligence – A Modern Approach, 2003 Pearson Education, Inc.
Unbekannter Autor, Theory of Cellular Automata, http://www.theory.org/complexity/cdpt/html/node4.html
Recommended