Praktikum KI Teil VIII: Planung. Praktikum KI SoSe 2005 Überblick Organisation des Praktikums Einführung in die Künstliche Intelligenz Suche nach einer

Praktikum KI

Teil VIII: Planung

Praktikum KI SoSe 2005

Überblick

Organisation des Praktikums Einführung in die Künstliche Intelligenz Suche nach einer „intelligenten“ Lösung Problemlösung mit Heuristiken Logik Planung & Robotik Expertensysteme Lernen


Planung

Planung betrachtet die Lösung realer Probleme Mittels geeigneter Beschreibungen der Welt Mittels Suche in der Welt-Repräsentation

Schwierigkeiten bei der Lösung realer Probleme Größe des Suchraums Anzahl der Nachfolger eines Knotens Geeignete Heuristik Dekomposition von Problemen


Planung

Beispiel: Kauf eines Buches „Artificial Intelligence“ Welt-Representation: ISBN-Nummern aller Bücher Knoten: Alle Bücher, die man hat Nachfolger-Funktion: Kauf eines einzelnen Buches, d.h. alle Bücher,

die man vorher hatte, plus das gekaufte neue Buch

Probleme ISBN-Nummern 10-stellig 10 Milliarden Nachfolger eines Knotens Kauf von 4 Büchern

1040 verschiedene Pläne, die evaluiert werden müssten Heuristik: Anzahl der noch fehlenden Bücher. Aber: Diese Heuristik ist

menschen-gemacht und problemabhängig Dekomposition: 4 Mal ein Buch kaufen; reduziert naiv das Problem auf

4* 1010 statt 1040. Aber: Wie kann diese Dekomposition automatisch erreicht werden?


Planungssprache STRIPS

Lösung – Planungssprache STRIPS: Aufteilung des Problems in Zustände, Aktionen und Ziele

Zustände entsprechen Knoten im Suchbaum Aktionen entsprechen Kanten im Suchbaum Ziele entsprechen Zielknoten

Beschreibe Zustände als variablenfreie Konjunktion von positiven Literalen have(ISBN 0-13-080302-2) Plane(P1) Airport(LBC) Airport(STD) At(P1,LBC) Closed-World-Assumption: Alle nicht genannten Aussagen

werden als false interpretiert



Beschreibe Aktionen mittels Vorbedingung: Konjunktion positiver Literale Effekt: Konjunktion von Literalen Alles, was nicht in Effekt genannt wird, bleibt unverändert Bsp:

ActionFly(p,from,to)

Precond: Plane(p) Airport(from) Airport(to) At(p,from)

Effect: At(p,from) At(p,to)

Beschreibe Ziele als Zustände At(P1,STD) At(P2,SXF) Ein Ziel ist erreicht, wenn der aktuelle Zustand alle Literale des

Zielzustands enthält At(P1,STD) At(P2,SXF) At(P3,LBC) At(P1,STD) At(P2,SXF) At(P5,TXL) At(P8,FRA)



Vorteile dieser Darstellung Allgemeine Darstellung von Aktionen

Nicht mehr Buy(ISBN 0-00-000000-0) bis Buy(ISBN 9-99-999999-9)

Sondern Buy(x) Book(x) Schnelles Erzeugen von Nachfolgern eines Knotens (= Finden

aller möglichen Aktionen) via Unifikation Heuristik: Anzahl der unerfüllten Literale des Zielzustandes Dekomposition: Aufteilung des Ziels anhand der Literale

Nicht immer möglich Teilweise mit Aufwand für‘s Zusammenfügen verbunden


Planungssprache STRIPS Beispiel: Blocks World

Objekte: Blöcke A, B, C; Greifer; Tisch Zustände:

On(x,y) %Block x direkt auf Block y Ontable(x) %Block x direkt auf dem Tisch Clear(x) %Nichts auf Block x Empty %Greifer leer Holding(x) %Greifer hält Block x



Aktionen Pickup(x,y)

Precond: Empty Clear(x) On(x,y) Effect: Holding(x) Clear(y) Empty On(x,y) Clear(x)

Putdown(x,y) Precond: Holding(x) Clear(y) Effect: Empty Clear(x) On(x,y) Holding(x) Clear(y)



Aktionen Pickuptable(x)

Precond: Empty Clear(x) Ontable(x) Effect: Holding(x) Empty Ontable(x) Clear(x)

Putdowntable(x) Precond: Holding(x) Effect: Empty Clear(x) Ontable(x) Holding(x)


Planungssprache STRIPS STRIPS – Suche:

Die Literale des Zielzustandes werden nacheinander abgearbeitet

Welches Literal als nächstes betrachtet wird, legt der Suchalgorithmus fest.

Jedes Literal wird via backwards search versucht zu erreichen Löst das Problem der unnützen Aktionen der Vorwärtssuche Führt rekursiv wieder auf ein Planungsproblem Aber: Tiefensuche ist nur eine Möglichkeit; alle anderen

Suchverfahren (Breitensuche, A*) sind ebenso möglich Falls beim Erreichen eines Literals ein anderes anderes

zerstört wird, kommt dieses wieder in die Liste der noch nicht erfüllten Literale


Planungssprache STRIPS Beispiel Blocksworld:

Anfangszustand: empty ontable(A) ontable(B) clear(B) on(C, A) clear(C)



Zielzustand: empty ontable(c) on(b, c) on(a, b) clear(a)



Lösung:



Lösung: pickup(C, A) putdowntable(C) pickuptable(B) putdown(B, C) pickuptable(A) putdown(A, B)

a

c

b a cb a c

b

a

c

b

1 2 3 4


Planungssprache STRIPS STRIPS – Sussman-Anomalie:

Die Reihenfolge der Bearbeitung der Literale ist entscheidend Bsp: Sussman-Anomalie

Anfangszustand: emptyontable(A)ontable(B)clear(B)on(C, A)clear(C)

Zielzustand: emptyon(b, c)on(a, b)ontable(c) %das war vorher obenclear(a)

c

a

b

c

a

b



Nun wird zuerst das Ziel on(b,c) erfüllt Dann das Ziel on(a,b), welches on(b,c) wieder zerstört Also noch einmal on(b,c), welches wieder on(a,b) zerstört Schließlich ein letztes Mal on(a,b)



pickuptable(b) putdown(b, c) pickup(b, c) putdowntable(b) pickup(c, a) putdowntable(c) pickuptable(a) putdown(a, b) pickup(a, b) putdowntable(a) pickuptable(b) putdown(b, c) pickuptable(a) putdown(a, b)

a

c

b a

c

b

a

c

b a cb

a

cb a cb

a c

b

a

c

b

1 2

3 4

5 6

7 8


Planung – Suche im Zustandsraum Vorherige Beispiele der Blocks-World waren Beispiele der Suche

im Zustandsraum Zur Erinnerung:

Knoten des Suchbaums: Zustände Kanten: Aktionen

Suche kann prinzipiell wie in den ersten Vorlesungen behandelt ablaufen Forward-Search / Backward Search / Bidirectional Search Breitensuche / Tiefensuche / A*-Suche Heuristiken

Anzahl der unerfüllten Literale Literal mit wenigsten Aktionen, die es erfüllen (most constrained variable

heuristic, sh. CSP) Relaxiertes Problem

Keine negativen Effekte der Aktionen Planungs-Graphen


Planung – Suche im Planraum Nachteile der Suche im Zustandsraum:

Keine Flexibilität bei der Plandurchführung Großer Suchraum

Alternativer Ansatz: Suche im Planraum Knoten sind Pläne + resultierende Zustände Kanten sind Verfeinerungen der Pläne, d.h. pro Stufe im Suchbaum

kommt eine Aktion hinzu Nachfolger-Funktion: Zusätzliche Aktion, die (mindestens) ein

unerfülltes Literal erfüllen


Planung – Suche im Planraum Bsp:

Zustände: RightSockOn, LeftSockOn, RightShoeOn, LeftShoeOn Aktionen:

RightShoe

Precond: RightSockOn Effect: RightShoeOn

RightSock Precond: {} Effect: RightSockOn

LeftShoe

Precond: LeftSockOn Effect: LeftShoeOn

LeftSock Precond: {} Effect: LeftSockOn

Goal: RightShoeOn LeftShoeOn Init: {}


Planung – Suche im Planraum Ein Knoten enthält:

Menge von Aktionen, die zum aktuellen Plan gehören Menge von Ordnungsrelationen unter den Aktionen

A B bedeutet, dass Aktion A vor Aktion B ausgeführt werden muss ist transitiv, d.h. aus A B und B C folgt A C

Menge von kausalen Verknüpfungen A p > B bedeutet, dass Aktion A die Vorbedingung p für Aktion B erfüllt Zwischen A und B darf somit keine Aktion stattfinden, die p negiert Bsp: RightSock RightSockOn > RightShoe

Menge offener Literale (Vorbedingungen)

Ein Knoten (ein Plan) ist konsistent, wenn Keine Zykel in der Ordnungsrelation vorkommen (d.h. nicht gleichzeitig A B und B

A ) Keine Konflikte mit den kausalen Verknüpfungen enthalten sind (d.h. nicht A p

> B, A X, X B und B mit Effekt p)

Aktionen „Start“ und „Finish“ sind Bestandteil aller Knoten Start hat keine Vorbedingungen und den Initialzustand als Effekt Finish hat keinen Effekt und den Zielzustand als Vorbedingung


Planung – Suche im Planraum Ablauf der Suche:

1. Starte mit dem leeren Plan, der nur Start und Finish enthält

2. Wähle eine offene Vorbedingung p (Verzweigungspunkt, Heuristik?!) und eine Aktion X, die diese Vorbedingung erfüllt (Verzweigungspunkt, Heuristik?!)

3. Falls X noch nicht in der Menge der Aktionen enthalten ist, füge X zu Menge Aktionen und die nicht erfüllten Vorbedingungen von X zur Menge der offenen Vorbedingungen hinzu.

4. Mache den entstehenden Plan konsistent:1. Sei B eine Aktion, die p als Vorbedingung hat (Verzweigungspunkt). Füge X p

> B zur Menge der kausalen Verknüpfungen und X B zur Menge der Ordnungsrelationen hinzu

2. Wenn X einen negativen Effekt q hat und eine kausale Verknüpfung A q > B

existiert, füge X A oder B X zur Menge der Ordnungsrelationen hinzu (Verzweigungspunkt)

3. Kann der Plan nicht konsistent gemacht werden: Backtracking

5. Überprüfe, ob es noch nicht erfüllte Vorbedingungen gibt1. Wenn nein, RETURN

2. Wenn ja, GOTO 2


Planung – Suche im Planraum Bsp: Socken-und-Schuh-Problem, Ausschnitt aus dem Suchbaum

Aktionen: Start, FinishOffene Vorbedingungen: RightShoeOn, LeftShoeOnOrdnungsrelationen: Start FinishKausale Links: {}

Aktionen: Start, Finish, RightShoeOffene Vorbedingungen: LeftShoeOn, RightSockOnOrdnungsrelationen: Start Finish, Start RightShoe,

RightShoe FinishKausale Links: RightShoe RightShoeOn > Finish

Aktionen: Start, Finish, LeftShoeOffene Vorbedingungen: RightShoeOn, LeftSockOnOrdnungsrelationen: Start Finish, Start LeftShoe,

LeftShoe FinishKausale Links: LeftShoe LeftShoeOn > Finish

Aktionen: Start, Finish, RightShoe, LeftShoeOffene Vorbedingungen: RightSockOn, LeftSockOnOrdnungsrelationen: Start Finish, Start LeftShoe,

LeftShoe Finish, Start RightShoe, RightShoe Finish

Kausale Links: LeftShoe LeftShoeOn > Finish, RightShoe RightShoeOn > Finish

Aktionen: Start, Finish, RightShoe, RightSockOffene Vorbedingungen: LeftShoeOnOrdnungsrelationen: Start Finish, Start RightSock, RightSock Finish, RightSock RightShoe,

Start RightShoe, RightShoe FinishKausale Links: LeftShoe LeftShoeOn > Finish, RightShoe RightShoeOn > Finish

RightShoe

LeftShoe

LeftShoe

RightSock… …

… ……


Planung – Suche im Planraum Bsp: Socken-und-Schuh-Problems, Zielknoten


Planung – Suche im Planraum Vorteile der partiellen Planung:

Es werden nur notwendige Einschränkungen vorgenommen Die Ausführung des Plans ist flexibel Nähe zu CSP: Welche Vorbedingung soll als nächstes betrachtet werden

Gute Heuristiken verfügbar Besonders gut bei Problemen, die sich mit Divide and Conquer lösen lassen


Planung – Planungsgraphen Planungsgraphen

bieten gute Heuristik für Suche im Zustandsraum und Suche im Planraum

Enthalten partielle Pläne, die nicht offensichtlich unzulässig sind

Sind in polynomieller Zeit aufzubauen

Aufbau der Planungsgraphen Abfolge von Zustandsleveln und Aktionsleveln S0 enthält alle Initialzustände

Ai enthält alle Aktionen, die unter den Vorbedingungen Si möglich sind plus Erhaltungsaktionen, die Zustand s in Si in Zustand s in Si+1 überführen

Si+1 enthält alle Effekte der Aktionen in Ai

Wenn Si die gleichen Zustände wie Si+1 enthält, dann STOP


Planung – Planungsgraphen Bsp: Kuchen haben, essen, backen


Planung – Planungsgraphen Aktionen des Levels Ai können sich gegenseitig

ausschließen (mutual exclusion, mutex), wenn sie Inkonsistente Effekte haben, d.h. Aktion A hat Effekt p, Aktion

B hat Effekt p Interferieren, d.h. Aktion A hat Effekt p, Aktion B hat

Vorbedingung p ( A darf nicht vor B ausgeführt werden) Ausschließende Vorbedingungen haben, d.h. Aktion A hat

Vorbedingung p, Aktion B hat Vorbedingung p

Zustände p, q des Levels Si können mutex sein, wenn p = q p nur durch A und q nur durch B in Ai erreicht werden können

und A und B mutex sind


Planung – Planungsgraphen Bsp:

Eat(Cake) und Erhaltung von Have(Cake) haben inkonsistenten Effekt Have(Cake)

Effekt von Eat(Cake) interferiert mit Vorbedingung der Erhaltung von Have(Cake)

Bake(Cake) und Eat(Cake) haben die sich ausschließenden Vorbedingungen Have(Cake) und Have(Cake)

Have(Cake) und Have(Cake) sind mutex Eaten(Cake) und Have(Cake) sind mutex, da Eat(Cake) und

Erhaltung von Have(Cake) mutex sind


Planung – Planungsgraphen Planungsgraphen für Heuristiken

Ist Zielzustand p nicht in Sfinal enthalten, so ist Planungsproblem nicht lösbar

Zur Berechnung eines Schätzwertes bei gegebenem Zustand S, entwickle den Planungsgraphen mit S0 = S (Level bezieht sich nachfolgend auf Level in Planungsgraphen) Max-Level-Heuristik: h(S) = maximales Level alles Zielzustände p von S Level-Sum-Heuristik: h(S) = Summe über die Level aller Zielzustände von

S Set-Level-Heuristik: h(S) = Level, in dem alle Zielzustände das erste Mal

nicht-mutex auftreten

Es gilt: Max-Level ist zulässig (admissible), aber ungenau Level-Sum ist nicht zulässig (kann überschätzen), aber genau, gut für

Divide and Conquer Probleme Set-Level ist zülässig, recht genau und gut für Probleme mit vielen

Abhängligkeiten


Planung – weitere Ansätze Aus Planungsgraphen kann direkt ein zulässiger Plan extrahiert werden

„GraphPlan“-Algorithmus Mutex hat entscheidende Bedeutung Aufwändig

Formulierung als Logik-Problem (in Aussagenlogik) Jede Aktion zu jedem Zeitschritt ist eine Aussage Finde Belegung der Aussagen (Aktion,Zeitpunkt) mit true / false, sodass

initial_state successor_state_axioms precondition_axioms state_constrains goal(T)

true ist Lösung mittels

Resolution (Konvertierung in CNF erforderlich) Lokaler Suche

Mehr dazu im AIMA (http://aima.cs.berkeley.edu/newchap11.pdf)

Documents

Praktikum KI Teil VIII: Planung. Praktikum KI SoSe 2005 Überblick Organisation des Praktikums Einführung in die Künstliche Intelligenz Suche nach einer