38
Vorlesung: „Küns Literatur zur Vorlesung Marco Blo Ertel, W.: „Grundkurs Künstliche Intelligenz“, Vieweg Verl Bratko, I.: „PROLOG Programming for Artificial Intelligen Pearson Verlag 2001 Luger, G.F.: „Künstliche Intelligenz“, 4.Auflage, Pearson S Künstliche Intelligenz Vorlesung Künstliche Intelligenz Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz stliche Intelligenzock-Berlitz Abbildung aus [1] lag 2008 nce“, 3.Auflage, Studium Verlag 2001 1

Vorlesung: „ Künstliche Intelligenz - Informatik · Vorlesung 1 • Definition von „Künstlicher Intelligenz“ • Meilensteine und Arbeitsfelder der KI • Einführung in die

  • Upload
    vodung

  • View
    231

  • Download
    0

Embed Size (px)

Citation preview

Vorlesung: „Künstliche Intelligenz

Literatur zur Vorlesung

Marco Block

Ertel, W.: „Grundkurs Künstliche Intelligenz“, Vieweg Verlag

Bratko, I.: „PROLOG Programming for Artificial IntelligencePearson Verlag 2001

Luger, G.F.: „Künstliche Intelligenz“, 4.Auflage, Pearson Studium Verlag 2001

Künstliche Intelligenz

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Künstliche Intelligenz“

Marco Block-Berlitz

Abbildung aus [1]

Verlag 2008

PROLOG Programming for Artificial Intelligence“, 3.Auflage,

“, 4.Auflage, Pearson Studium Verlag 2001

1

Organisatorisches zur Veranstaltung

• Vorlesungen Do 14-16 Uhr in SR006

• Tutorien Fr 12-14 Uhr und 14-16 Uhr in

• Scheinkriterien: 60% der Punkte auf den Übungszettelnn-1 Übungszettel

Übungsleiter: Miao Wang ([email protected])

Marco Block ([email protected])

Künstliche Intelligenz Marco Block

n-1 ÜbungszettelBestehen der Klausur am

• Übungszettel: Ausgabe der Übungszettel wöchentlichAbgabe in der darauf folgenden Woche Fr 12 Uhr2 bis 3-er GruppenProgrammierabgaben Sprachen: SWI-PROLOG und später Java

• Literaturhinweise, Übungszettel, Themen und Folien erscheinen auf der VL

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

in SR006

der Punkte auf den ÜbungszettelnÜbungszettel mit mindestens 20%

berlin.de)

2Marco Block-Berlitz

Übungszettel mit mindestens 20%Bestehen der Klausur am 16.07.2009

Ausgabe der Übungszettel wöchentlich Do/Frin der darauf folgenden Woche Fr 12 Uhr

er GruppenProgrammierabgaben zusätzlich per Email

PROLOG und später Java

Literaturhinweise, Übungszettel, Themen und Folien erscheinen auf der VL-Seite

Vorlesung 1

• Definition von „Künstlicher Intelligenz“

• Meilensteine und Arbeitsfelder der KI

• Einführung in die Programmierung mit

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

PROLOG

3Marco Block-Berlitz

Definition von „Künstlicher Intelligenz“

1950 Alan Turing (Turingtest):

„Im Zuge dieses Tests führt ein menschlicherFragesteller über eine TastaturBildschirm ohne Sicht- und Hörkontaktihm unbekannten GesprächspartnernUnterhaltung.

Der eine Gesprächspartner ist ein Mensch,

Künstliche Intelligenz

Der eine Gesprächspartner ist ein Mensch,andere eine Maschine. Beide versuchen,Fragesteller davon zu überzeugen,denkende Menschen sind.

Wenn der Fragesteller nach derBefragung nicht klar sagen kann, welcherbeiden die Maschine ist, hat die MaschineTuring-Test bestanden.“

Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

menschlicherund einen

Hörkontakt mit zweiGesprächspartnern eine

Mensch, der

4

Mensch, derversuchen, den

überzeugen, dass sie

intensivenwelcher von

Maschine den

Marco Block-Berlitz

Abbildung aus [4]

Definition von „Künstlicher Intelligenz“

1955 John McCarthy:

„Ziel der KI ist es, Maschinen zu entwickeln, die sich verhalten, als verfügten sie über Intelligenz.“

Künstliche Intelligenz

Braitenberg-Vehikel, Reaktion auf Lichtquelle

Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Ziel der KI ist es, Maschinen zu entwickeln, die sich verhalten, als

5

Vehikel, Reaktion auf Lichtquelle

Abbildung aus [1]

[2]

Marco Block-Berlitz

Definition von „Künstlicher Intelligenz“

1991 Encyclopedia Britannica:

„KI ist die Fähigkeit digitaler Computer oder computergesteuerter Roboter, Aufgaben zu lösen, die normalerweise mit den höheren intellektuellen Verarbeitungsfähigkeiten von Menschen in Verbindung gebracht werden ...

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

KI ist die Fähigkeit digitaler Computer oder computergesteuerter Roboter, Aufgaben zu lösen, die normalerweise mit den höheren intellektuellen Verarbeitungsfähigkeiten von Menschen in Verbindung gebracht werden ...“

6Marco Block-Berlitz

Definition von „Künstlicher Intelligenz“

1983 Elaine Rich:

„Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better.“

Künstliche Intelligenz

Gute Beschreibung der Tätigkeit von Wissenschaftlern der KI in der Vergangenheit

und sicher auch Zukunft.

Ziel: Im Laufe der Vorlesung zu einer eigenen Definition zu gelangen.

Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Artificial Intelligence is the study of how to make computers do things at which,

7

Gute Beschreibung der Tätigkeit von Wissenschaftlern der KI in der Vergangenheit

Im Laufe der Vorlesung zu einer eigenen Definition zu gelangen.

Marco Block-Berlitz

Ausgewählte Meilensteine der KI

� 1931 Gödel zeigt, dass in der Prädikatenlogik erster Stufe alle Aussagen herleitbar sind

� 1937 Alan Turing zeigt mit Halteproblem die Grenzen intelligenter Maschinen auf

� 1943 McCulloch Pitts modellieren Neuronale Netze

� 1950 Alan Turing definiert den Turingtest

1951 Marvin Minsky entwickelt einen Neuronenrechner

Künstliche Intelligenz Marco Block

� 1951 Marvin Minsky entwickelt einen Neuronenrechner

� 1955 Arthur Samuel entwickelt lernfähige Dameprogramme

� 1956 Konferenz im Dartmouth College, Name Artificial Intelligence wird LogicTheorist

� 1957 Simon und Newell entwickeln General Problem Solver

� 1958 LISP

� 1959 Geometry Theorem Prover

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

zeigt, dass in der Prädikatenlogik erster Stufe alle wahren

Turing zeigt mit Halteproblem die Grenzen intelligenter Maschinen auf

Pitts modellieren Neuronale Netze

Turing definiert den Turingtest

Minsky entwickelt einen Neuronenrechner

Marco Block-Berlitz 8

Minsky entwickelt einen Neuronenrechner

Samuel entwickelt lernfähige Dameprogramme

im Dartmouth College, Name Artificial Intelligence wird eingeführt

und Newell entwickeln General Problem Solver

Ausgewählte Meilensteine der KI

� 1965 Robinson beschreibt das Resolutionskalkül Prädikatenlogik; Zadeh formuliert

� 1966 Weizenbaum entwickelt Eliza

� 1972 PROLOG; Expertensystem zur Diagnose von Krankheiten

� 1976 Shortliffe und Buchanan entwickeln MYCIN

1990 Bayes-Netze, Data Mining

Künstliche Intelligenz Marco Block

� 1990 Bayes-Netze, Data Mining

� 1992 Tesauro entwickelt selbstlernendes Back (Reinforcement Learning) und spielt stärker als der Weltmeister

� 1993 RoboCup Initiative

� 1995 Vapnik beschreibt die Support

� 1996 Mars Pathfinder, Sojourner

� 1997 erster internationaler RoboCup Wettkampf; Deep(er) Blue von IBM den Schachweltmeister Kasparow

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

beschreibt das Resolutionskalkül für Zadeh formuliert Fuzzy-Logik

; Expertensystem zur Diagnose von Krankheiten

und Buchanan entwickeln MYCIN

Marco Block-Berlitz 9

entwickelt selbstlernendes Back Gammon-Programm Reinforcement Learning) und spielt stärker als der Weltmeister

beschreibt die Support Vector Maschines

internationaler RoboCup Wettkampf; Deep(er) Blue von IBM schlägt Kasparow

Ausgewählte Meilensteine der KI

� 1998 Robosapiens Kismet vom MIT

� 2000 Roboter Asimo der Firma Honda

� 2007 Schaeffer löst das Spiel Dame (Chinook)

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Roboter Asimo der Firma Honda

löst das Spiel Dame (Chinook)

Marco Block-Berlitz 10

Ausgewählte Arbeitsfelder der KI

Konnektionismus, Expertensysteme

Logischen und Probabilistisches Schließen

Planung, Entscheidung

Lernen, Optimieren

Wissensrepräsentation

Künstliche Intelligenz Marco Block

Bildverarbeitung

Mustererkennung

Spieltheorie

Spieleprogrammierung

Autonome Systeme

Robotik

...

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Logischen und Probabilistisches Schließen

Marco Block-Berlitz 11

Inhaltliche Planung für die Vorlesung

1) Definition und Geschichte der KI, PROLOG

2) Expertensysteme

3) Probabilistisches und Logisches Schließen, Resolution

4) Spieltheorie, Suchen und Planen

5) Spieleprogrammierung

Künstliche Intelligenz Marco Block

6) General Game Playing

7) Reinforcement Learning und Spieleprogrammierung

8) Mustererkennung

9) Neuronale Netze

10) Optimierungen (genetische und evolutionäre Algorithmen)

11) Bayes-Netze, Markovmodelle

12) Robotik, Pathfinding

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

1) Definition und Geschichte der KI, PROLOG

3) Probabilistisches und Logisches Schließen, Resolution

Marco Block-Berlitz 12

7) Reinforcement Learning und Spieleprogrammierung

10) Optimierungen (genetische und evolutionäre Algorithmen)

der rote Vorlesungsfaden...

Wissensbasierte Systeme

Inferenzmechanismus: Trennung von Wissensbasis und Inferenz

Vorteil: Wissensbasis einfach austauschbar, ohne

das führt uns zu PROLOG

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Inferenzmechanismus: Trennung von Wissensbasis und Inferenz

Vorteil: Wissensbasis einfach austauschbar, ohne System neu zu programmieren

Marco Block-Berlitz 13

PROLOG – Wahl des Interpreters

Wir verwenden für die Veranstaltung SWI-

http://www.swi-prolog.org/

Programm

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

-Prolog Version 5.78 (development version)

Programm

Marco Block-Berlitz 14

Konsole

PROLOG Datenobjekte

einfache Objekte

Strukturen

Datenobjekte

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

einfache Objekte

Konstanten

Variablen

Atome

Zahlen

Marco Block-Berlitz 15

PROLOG Datenobjekte

einfache Objekte

Strukturen

Datenobjekte

Künstliche Intelligenz Marco Block

Beispiele für Atome:

anna

nil

x25

x_

miss_Jones

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

einfache Objekte

Konstanten

Variablen

Atome

Zahlen

Marco Block-Berlitz 16

PROLOG Datenobjekte

einfache Objekte

Strukturen

Datenobjekte

Künstliche Intelligenz Marco Block

Beispiele für Variablen:

X

Result

_x23

ObjectList

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

einfache Objekte

Konstanten

Variablen

Atome

Zahlen

Marco Block-Berlitz 17

PROLOG Datenobjekte

einfache Objekte

Strukturen

Datenobjekte

Künstliche Intelligenz Marco Block

Beispiel für eine Struktur:

date(1,may,2001)

Funktor Argumente

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

einfache Objekte

Konstanten

Variablen

Atome

Zahlen

Marco Block-Berlitz 18

PROLOG

Die Sprache PROLOG hängt stark mit der Prädikatenlogik zusammen.

Prädikatenlogik Bedeutung

∧ und

∨ oder

⇐ dann, wenn

Künstliche Intelligenz Marco Block

Beispiel:

¬ nicht

mag(peter, susanne) :- not(mag(karin, peter)).

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Die Sprache PROLOG hängt stark mit der Prädikatenlogik zusammen.

Bedeutung PROLOG

und ,

oder ;

dann, wenn :-

Marco Block-Berlitz 19

:-

nicht not

not(mag(karin, peter)).

Programm

PROLOG

Das gesamte Wissen über die Welt befindet sich in der Datenbank. Findet sich dort

nichts, ist die Anfrage falsch.

Annahme der Weltabgeschlossenheit (Closed World Assumption):

=> PROLOG nimmt alle Ziele als falsch an, deren Wahrheit nicht bewiesen werden

kann.

Künstliche Intelligenz Marco Block

Stichwort: Resolution

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Das gesamte Wissen über die Welt befindet sich in der Datenbank. Findet sich dort

(Closed World Assumption):

=> PROLOG nimmt alle Ziele als falsch an, deren Wahrheit nicht bewiesen werden

Marco Block-Berlitz 20

PROLOG – Dynamisches Arbeiten I

PROLOG besitzt eine Konsole zur Kommunikation. Dort können wir Anfragen stellen.

Prädikat P zur Menge der Spezifikationen hinzufügen:

?- assert(P).

Künstliche Intelligenz Marco Block

Prädikat P an den Anfang (1) und enstprechend an das Ende (2) fügen:

Prädikat P wird entfernt:

?- asserta(P). -- (1)

?- assertz(P). -- (2)

?- retract(P).

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

PROLOG besitzt eine Konsole zur Kommunikation. Dort können wir Anfragen stellen.

Prädikat P zur Menge der Spezifikationen hinzufügen:

Konsole

Marco Block-Berlitz 21

Prädikat P an den Anfang (1) und enstprechend an das Ende (2) fügen:

PROLOG – Dynamisches Arbeiten II

Beispiel:

?- assert(male(tim)).

?- assert(male(tom)).

?- asserta(male(tony)).

?- assertz(male(tino)).

?- retract(male(tim))).

?- male(X).

X=tony;

Künstliche Intelligenz Marco Block

Anzeige der aktuellen Datenbank:

Zum Glück müssen wir die Datenbank nicht zeilenweise füttern...

X=tony;

X=tom;

X=tino;

no

?- listing.

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Marco Block-Berlitz 22

Zum Glück müssen wir die Datenbank nicht zeilenweise füttern...

PROLOG – Skriptum

Fakten

Gespeichert werden die Skripte mit *.pl, was sich aber nach Interpreterunterscheiden kann.

Aufbau einer PROLOG-Datei:

Künstliche Intelligenz Marco Block

Regeln

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Datenbank von

, was sich aber nach Interpreter

Marco Block-Berlitz 23

Datenbank vonKlauseln

PROLOG – Fakten definieren

Fakten werden durch Relationen (beginnend mit einem Kleinbuchstaben) angegeben

Beispiel:

isParent ist der Name der Relation, hans und

isParent(hans, tim).

Künstliche Intelligenz Marco Block

Wir können das PROLOG-System jetzt danach fragen:

?- isParent(hans, tim).

yes

?- isParent(hans, marco).

no

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Fakten werden durch Relationen (beginnend mit einem Kleinbuchstaben) angegeben

und tim sind die Argumente.

Marco Block-Berlitz 24

System jetzt danach fragen:

PROLOG – Listen I

Geordnete Menge von Elementen, die auch wieder Listen sein können.

Kopf-und-Rest-Prinzip wie in Haskell

[a,b,c,d]

[[1,2],[3,4]]

[a,[1,2],b,c]

[]

Künstliche Intelligenz Marco Block

oder in Funktorschreibweise

[H|T]

[X,Y|T]

.(H,T)

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Geordnete Menge von Elementen, die auch wieder Listen sein können.

Marco Block-Berlitz 25

PROLOG – Listen II

Beispiel:

Zerlegung mit [X|Y], liefert X=a und Y=[b,c]

Prädikat member prüft, ob das erste Argument Element der nachfolgenden Liste ist:

[a,b,c]

Künstliche Intelligenz Marco Block

?- member(a,[a,b,c]).

yes

?- member(a,.(a,.(b,.(c,[])))).

yes

?- member(X,[b,c]).

X=b;

X=c;

no

?- member(X,[]).

no

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Y=[b,c]

prüft, ob das erste Argument Element der nachfolgenden Liste ist:

Marco Block-Berlitz 26

PROLOG – Prädikat member

Rekursive Definition von member

Das passiert intern:

Z1 nicht, da c!=a

member(X, [X|T]).

member(X, [Y|T]) :- member(X,T).

Künstliche Intelligenz Marco Block

Z1 nicht, da c!=aZ2 passt, da X=c, Y=a, T=[b,c](*) => ?- member(c,[b,c]).

Z1 nichtZ2 passt, da X=c, Y=b, T=[c](**) => ?- member(c,[c]).

Z1 passt.yes zu (**)

yes zu (*)yes

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

member(X, [X|T]). -- Z1

). -- Z2

Marco Block-Berlitz 27

PROLOG – Anonyme Variablen (wild cards)

Wir können dazu member wie folgt definieren

Länge einer Liste

member(X, [X|_]).

member(X, [_|T]) :- member(X,T).

laenge([],0).

Künstliche Intelligenz Marco Block

Zuweisung und Auswertung unter PROLOG

laenge([],0).

laenge([_|T], N) :- laenge(T, N1), N is 1+N1.

?- X=1+2.

X=1+2

?- X is 1+2.

X=3

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Anonyme Variablen (wild cards)

Wir können dazu member wie folgt definieren

member(X, [X|_]).

).

Marco Block-Berlitz 28

PROLOG

laenge(T, N1), N is 1+N1.

PROLOG – Arithmetische und Vergleichs

Arithmetik:

Vergleiche:

+, -, *, /, **, //, mod

>, <, >=, =<, =:=, =\=

a**b = ab

Künstliche Intelligenz Marco Block

>, <, >=, =<, =:=, =\=

= !=

?- 1+2=:=2+1.

yes

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Arithmetische und Vergleichs-Operatoren

Marco Block-Berlitz 29

PROLOG – Ausgaben

Ausgabe der Listenelemente untereinander:

Liste spiegelverkehrt ausgeben:

output_list([]).

output_list([H|T]) :- write(H), nl, output_list(T).

r_output_list([]).

Künstliche Intelligenz Marco Block

r_output_list([]).

r_output_list([H|T]) :- r_output_list(T), write(H).

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Ausgabe der Listenelemente untereinander:

write(H), nl, output_list(T).

Marco Block-Berlitz 30

r_output_list(T), write(H).

PROLOG – Konkatenation von Listen

„ha“ ++ „llo“ => „hallo“

Implementierung:

concat([1,2], [3,4], [1,2,3,4]).

concat([],L,L).

Künstliche Intelligenz Marco Block

concat([],L,L).

concat([X|L1], L2, [X|L3]) :- concat(L1, L2, L3).

?- concat([g,o],[o,g,l,e],L).

L=[g,o,o,g,l,e];

no

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Marco Block-Berlitz 31

concat(L1, L2, L3).

PROLOG – Konkatenation von Listen II

Wir stellen die Frage um...

?- concat(L1, L2, [a,b,c]).

L1=[]

L2=[a,b,c];

L1=[a]

L2=[b,c];

L1=[a,b]

Künstliche Intelligenz Marco Block

Member durch concat definieren:

oder:

L1=[a,b]

L2=[c];

L1=[a,b,c]

L2=[];

no

member(X,L) :- concat(L1,[X|L2],L).

member(X,L) :- concat(_,[X|_],L).

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Marco Block-Berlitz 32

concat(L1,[X|L2],L).

concat(_,[X|_],L).

PROLOG – delete und insert

Definition von delete, lösche X aus einer Liste:

del(X, [X|Tail], Tail).

del(X, [Y|Tail], [Y|Tail2]) :- del(X, Tail, Tail2).

?- del(a, [a,b,a,a], L).

L=[b,a,a];

L=[a,b,a];

L=[a,b,a];

Künstliche Intelligenz Marco Block

darüber läßt sich insert definieren:

insert(X, List, List_with_X) :-

L=[a,b,a];

no

?- del(a, L, [1,2,3]).

L=[a,1,2,3];

L=[1,a,2,3];

L=[1,2,a,3];

L=[1,2,3,a];

no

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Definition von delete, lösche X aus einer Liste:

del(X, Tail, Tail2).

Marco Block-Berlitz 33

del(X, List_with_X, List).

PROLOG – member durch delete

Definition von member über delete:

Idee: Ein X ist member, wenn X aus der Liste gelöscht werden kann...

member(X, List) :- del(X, List, _).

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Ein X ist member, wenn X aus der Liste gelöscht werden kann...

del(X, List, _).

Marco Block-Berlitz 34

Springerproblem auf 3x3 Brett

Künstliche Intelligenz Marco Block

Prädikatenlogisch:

Regel, die Zugfolgen der Länge 2 definiert

allgemeine Wegdefinition

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Marco Block-Berlitz 35

Regel, die Zugfolgen der Länge 2 definiert

Springerproblem auf 3x3 Brett

PROLOG:

Wegdefinition:weg(X,Y) :- zug(X,W), not(besucht(W)),

zug(1,8).

zug(1,6).

...

zug(9,4).

Künstliche Intelligenz Marco Block

Oder mit Liste:

weg(X,Y) :- zug(X,W), not(besucht(W)),

assert(besucht(W)), weg(W,Y).

weg(Z,Z,L).

weg(X,Y,L) :- zug(X,Z), not(member(Z,L)), weg(Z,Y,[Z|L]).

weg(X,Y) :- weg(X,Y,[X]).

?- weg(1,4,[1]).

?- weg(1,4).

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

zug(X,W), not(besucht(W)),

1 2 3

4 5 6

7 8 9

Marco Block-Berlitz 36

zug(X,W), not(besucht(W)),

assert(besucht(W)), weg(W,Y).

zug(X,Z), not(member(Z,L)), weg(Z,Y,[Z|L]).

PROLOG Cut-Operator

Der Cut-Operator wird durch „!“ repräsentiert. Beim erstenmal erfolgreichausgeführt und beim Backtracking mißlingt das gesamte Ziel, indem er enthalten ist.

mit Cut-Operator

p :- a,b.

p :- c.

p :- a,!,b.

Künstliche Intelligenz Marco Block

vertauscht gilt sogar

p :- a,!,b.

p :- c.

p :- c.

p :- a,!,b.

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

Operator wird durch „!“ repräsentiert. Beim erstenmal erfolgreichausgeführt und beim Backtracking mißlingt das gesamte Ziel, indem er

Marco Block-Berlitz 37

Literatur und Abbildungsquellen

[1] Ertel, W.: „Grundkurs Künstliche Intelligenz“, Vieweg Verlag 2007

[2] Braitenberg V.: „Vehicles – Experiments in Synthetic Psychology

[3] Bratko, I.: „PROLOG Programming for Artificial Intelligence

[4] Copeland J.: „Artificial Intelligence: A Philosophical Introduction

Künstliche Intelligenz Marco Block

Vorlesung Künstliche Intelligenz

Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz

“, Vieweg Verlag 2007

Experiments in Synthetic Psychology“, MIT Press, 1984

PROLOG Programming for Artificial Intelligence“, 3.Auflage, Pearson Verlag 2001

Artificial Intelligence: A Philosophical Introduction“, Oxford UK and Cambridge, 1993

Marco Block-Berlitz 38