Planung Lehrstuhl für Operations Research und Systemtheorie Hauptseminar Emotional Intelligence Bernhard Schneider Harald Aigner Christian Becker Planung

Planung

Lehrstuhl für Operations Research und Systemtheorie

Hauptseminar Emotional Intelligence

Bernhard SchneiderHarald AignerChristian Becker

Planung

Planung

Planung Planung

Planung

Planung

Hauptseminar Emotional Intelligence Planung Folie 2 von 59

Übersicht

Teil 1: Grundbegriffe der Planung

Planung mit Suchstrategien

Teil 2: Bedingungsabhängiges Planen

Probleme der Planung

Teil 3: Entwicklung von Plänen


Übersicht







Zitat

Planung ist der Ersatz des Zufalls durch den Irrtum.

[Albert Einstein]


Bausteine der Planung

Planung: Lösung einer Fragestellung als Entscheidungsprozess

Benötigt:

Wunsch: - Methodik zum Auffinden einer (besten) Lösung

- Wissen über

- die Umwelt zum Zeitpunkt der Fragestellung- ausführbare Aktionen und deren Auswirkungen auf die Umwelt- das Ziel

- geeignete Darstellung


Problem

„Besorge einen Regenschirm und gib nicht mehr als 20 € aus.“

Auftrag: Ausführung einer Aktion

Zerlegung in Teilschritte

Divide & Conquer

Bedingung

Bestandteile eines Problems:

{Anweisungen}

{Bedingungen}

wird in Operationen/ Aktionen zerlegt

optional: Einschränkung des Handlungsspielraumes


Definition Plan

Ein Plan ist eine Abfolge von Zuständen, die einen Anfangszustand durch Ausführung von Aktionen in einen Endzustand überführt.

…a1 an

A E


Menge der Zustände

Anfangszustand

Endzustand

Z

Zustand der Umwelt vor Beginn der Abarbeitung des Plans

Zustand, der nach Erreichen des Ziels der Planung

eingenommen werden soll

A

E

A

E


Zustand

Ein Zustand ist eine Menge von Zustandsvariablen.

ZA

Z

x1

xn

x1=z1

x2=z2

...xn=zn

Im Zielzustand besitzen alle Zustandsvariablen den richtigen Wert.

x2 ..

.


PlanZ O

a1

a5

a2

a4

a6

a3

a7

a1 a4 a3 a2a7 a2a7 a4 a3


Gültiger Plan

Ein Plan ist gültig

- mindestens eine Aktion ist aus dem Anfangszustand ausführbar- der Folgezustand nach Ausführung der letzten Aktion ist der Zielzustand

…a1 an

A E


Lösung

Lösung

Raum der Pläne RP

P2

P5

P9

P7

P1

P11

P3P4

P10

P6

P8

P12

Plan

Eine Lösung ist ein gültiger Plan.


Übersicht







Planen als Suchen Vorgehensweise

Problem: - Suchen kostet Zeit und Speicher

- Aufspannen des gesamten Baumes!

Zustandsraum Z Suchstruktur:

- Expandieren von Knoten (=Zustände)

- Bewertung

- Auswahl


2 Suchstrategien

Uninformierte (blinde) Suche

Informierte (heuristische) Suche

- kein Wissen über die Richtung zum Ziel vorhanden- Breitensuche, Tiefensuche, Uniform Cost Suche

- zielgerichtete Suche, da Wissen über die Richtung

vorhanden, Verarbeitung in Heuristischer FunktionVermeidung von Fehlversuchen

- ´Gierige´ Suche, A*- Suche


Heuristiken

Heuristiken (Definition)

- Finderegeln- ohne Lösungsgarantie- terminiert nicht unbedingt- nicht beschränkt auf bestimmte Problemklassen- Einschränkung des Suchraums Reduzierung der Komplexität- In folgenden Beispielen: Verarbeitung des Wissens über die Richtung

zum Ziel

Heuristik ≠ Algorithmus


Suche Beispiel

Arad

Zerind

Oradea

Sibiu

Riminicu V.Timisoara

Lugoj

Mehadia

Fagaras

Pitesti

Dobreta Craiov

a

UrziceniBuchares

t

Giurgiu

Hirsova

Vasuli

Iasi

Neamt

Eforie


Wegsuche in Rumänien

Zerind

Sibiu

Timisoara

Arad

Oradea

Riminicu V.

Fagaras

Arad

Zerind

Sibiu Timisoara

Expandieren des Anfangszustandes:

Bewertung + Auswahl: Welcher Knoten soll als nächster expandiert werden?

blinde Suche: alle drei Knoten sind gleichberechtigt

heuristische Suche: Knoten ´Sibiu´ wird zuerst expandiert

N

S

OW


Blinde Suche Uniform Cost Suche

Uniform Cost Suche: Einführung von Pfadkosten direkter Verbindungen durch

Pfadkostenmatrix:

Arad 0

Zerind

Sibiu Timisoara

Arad Zerind Sibiu Timisoara

...

Arad 0 75 140 118 ...

Zerind 75 0 - - ...

Sibiu 140 - 0 - ...

Timisoara

118 - - 0 ...

... ... ... ... ... 0

Expandieren des Anfangszustands:Bewertung anhand der Matrix:

75 118

140

Auswahl des Knotens mit den geringsten Pfadkosten:



Expandieren: Knoten mit geringsten Pfadkosten wird zuerst expandiert:

Arad

Zerind 75

Sibiu 140

Timisoara 118

Arad Oradea Zerind 75

Zerind

Sibiu

Oradea 71

75 71

71 151

Implementation: Knoten werden in Priority- Queue abgelegt, Knoten mit kleinsten Werten am Kopf

Timisoara 118



Arad

Zerind 75

Sibiu 140

Timisoara 118

Lugoj 111

Mehadia 70

Dobreta 75

Craiova 120

Riminicu V. 146

Pitesti 138

Riminicu V. 97 Bucharest 101

Erreichte Pfadkosten: 733

Beste Lösung gesamt: 418


Heuristische Suche Gierige Suche

Arad 366

Zerind 374

Timisoara 329

Sibiu 253

Fagaras 178

Oradea 380

Riminicu V.

193

Bucharest

0

… …

Gierige Suche: Abschätzung der Pfadkosten Knotenn Ziel

mittels Heuristik h: Knoten IntLuftliniendistanz Ort[1..n] Ziel: 366 Arad

374 Zerind

253 Sibiu 329 Timisoara

366 Arad 178 Fagaras

380 Oradea

193 Riminicu V.

253 Sibiu

0 Bucharest




Heuristische Suche A*- Suche

A*- Suche: Kombination von Uniform Cost und Gieriger Suche

Heuristik h(n) = f(n) + g(n)

f(n) = Summe der Strassenkilometer (Arad Ortn)

g(n) = Luftliniendistanz (Ortn Bucharest)


Heuristische Suche A*- Suche

366 Arad

449 Zerind 393 Sibiu 447 Timisoara


671 Oradea

413 Riminicu V.

553 Sibiu

418 Bucharest

415 Pitesti

526 Craiova

526 Craiova




Übersicht







Planen mit Suchbäumen

366 Arad

374 Zerind

253 Sibiu 329 Timisoara


380 Oradea

193 Riminicu V.

253 Sibiu

0 Bucharest

Zerind

Sibiu

Timisoara

Arad

Oradea

Riminicu V.

Fagaras


Bedingungsabhängiger Plan

• Anfangszustand A, Endzustand E• Zustandsmenge Z• Aktionsmenge O• Menge von Bedingungen B

…a1 an

A E

global lokal


• Globale Bedingungen dürfen in keinem Zustand verletzt sein

Globale Bedingungen

…a1 an

A E a2

G


• Lokale Bedingungen dürfen bei einer bestimmten Aktionsdurchführung nicht verletzt sein

• Aktionsmenge O ist jetzt Menge von 2-Tupeln aus

(lokale Bedingung, Aktion)

…a1 an

A E

L1 L2 Lk

a2

Lokale Bedingungen


Globale Bedingungen

G


Lokale Bedingungen

L1 L2

LkL3


Beispiel: lokale Bedingungen

• Beispiel: arithmetische Umformung

A = 1

B = 2

C = 3

…

A = 6

B = 9

C = 5

• Aktionsmenge O nun 2-Tupel, z.B.

B > 5

A=A+2

B=B+5

C=C+5

A > 2

A=A+2

B=B+6

C=C+1

A > 0

A=A+3

B=B+1

C=C+1


A > 0

A=A+3

B=B+1

C=C+1

B > 5

A=A+2

B=B+5

C=C+5

Lokale Bedingungen• Prüfen der Vorbedingungen:

A = 1

B = 2

C = 3

A = 6

B = 9

C = 5

…

• Auswahl der Aktion

A > 2

A=A+2

B=B+6

C=C+1

Start-zustand

Ziel-zustand


A > 0

A=A+3

B=B+1

C=C+1

Lokale Bedingungen

• Wahl der Aktion

A = 1

B = 2

C = 3

A = 4

B = 3

C = 4

A = 6

B = 9

C = 5≠

aktueller Zustand


A > 0

A=A+3

B=B+1

C=C+1

A=A+2

B=B+5

C=C+5

Lokale Bedingungen

A > 2

A=A+2

B=B+6

C=C+1

• Prüfen der Vorbedingungen:

A = 6

B = 9

C = 5

…


A = 4

B = 3

C = 4

B > 5


Lokale Bedingungen

• Wahl der Aktion

A = 6

B = 9

C = 5=

A > 2

A=A+2

B=B+6

C=C+1

A = 6

B = 9

C = 5

A = 4

B = 3

C = 5


Lokale Bedingungen

• Wahl der Aktion

=

A = 6

B = 9

C = 5

A = 4

B = 3

C = 5

A > 0

A=A+3

B=B+1

C=C+1

A > 2

A=A+2

B=B+6

C=C+1


Verletzen globaler Bedingungen

A > 2

A=A+2

B=B+6

C=C+1A = 4

B = 3

C = 5A = 7

B = 4

C = 6

A = 6

B = 9

C = 5

A > 0

A=A+3

B=B+1

C=C+1

• Globale Bedingung z.B. A < 7

Backtracking erforderlich


3 <A< 4

A=A+2

B=B+6

C=C+1

A=A+3

B=B+1

C=C+1

0 <A< 4

…

B > 5

A=A+2

B=B+5

C=C+3


Verletzen lokaler Bedingungen• lokale Bedingungen 0<A<4 , 3<A<4 , B>5

A = 1

B = 2

C = 3

A = 4

B = 3

C = 6

aktueller Zustand


3 <A< 4

A=A+2

B=B+6

C=C+1

A=A+3

B=B+1

C=C+1

0 <A< 4

A = 1

B = 2

C = 3

A = 4

B = 3

C = 6

…

B > 5

A=A+2

B=B+5

C=C+3

Backtracking erforderlich

Verletzen lokaler Bedingungen• lokale Bedingungen 0<A<4 , 3<A<4 , B>5


aktueller Zustand


Lokale Bedingungen

L1 L2

Backtrackingneue Wahl


Lokale vs. globale Bedingungen

• Lokale Bedingungen aufwendiger zu formulieren– Rahmenbedingungen sollten global formuliert werden

• Transformation globaler Bedingungen in lokale möglich– Reduzierung der Anzahl der Expansionen– Aber: Transformation oftmals schwierig


Backtracking

1. Schrittweises Zurückgehen2. zum letzten gültigen Zustand

Positiv:– einfache Rücknahme von

Fehlern– einfach zu implementieren

Negativ:– evtl. exponentielle Laufzeit

– hoher Speicherbedarf

Tiefensuche auf inversem Graph


Übersicht








• Dynamische Welt

• Echtzeitproblematik

• Komplexität



• Dynamische Welt– Umwelt ändert sich auch ohne Aktionen des

Agenten

dynamisches Planen erforderlich, d.h.

• ständiges Neuerfassen der Umwelt

• vermehrtes Ausprobieren

• Konstruktion alternativer Pläne

• Verwendung von Heuristiken bzw. Prognosen



• Echtzeitproblematik1. begrenzte Zeit zur Planung2. Optimaler Plan benötigt zu viel Zeit

Anytime-Planning, d.h.• jederzeit anhaltbare Algorithmen

– Verwendung auch nur halbfertiger Pläne

– Verwendung nicht optimaler Pläne



• Komplexität– Planung ist oftmals NP-schwer

Verwendung von Spezialplanern, die

• auf Teilgebieten arbeiten

• Spezialfälle nicht gesondert bearbeiten

• komplexe Teilbereiche ausschließen

• Heuristiken verwenden


Übersicht







Von Zustand zu Zustand

Erinnerung:

Plan besteht aus-Zuständen-Operationen auf diesen Zuständen

Ziel:

Ziel ist es, einen Weg vom Startzustand über die Folgezustände bis zum Endzustand zu finden.

…a1 an

A E


Planen mit Algorithmen

Problem:Fährmann möchte Ziege, Kohl und Wolf übersetzen.Das Boot hat aber nur einen Platz.

Z, K, W F


Situation

Modellierung der Zustände

Z K W F ~ ~ ~ ~Z K W ~ ~ ~ ~ FZ K ~ F ~ ~ W ~Z K ~ ~ ~ ~ W FZ ~ W F ~ K ~ ~Z ~ W ~ ~ K ~ FZ ~ ~ F ~ K W ~Z ~ ~ ~ ~ K W F~ K W F Z ~ ~ ~~ K W ~ Z ~ ~ F~ K ~ F Z ~ W ~~ K ~ ~ Z ~ W F~ ~ W F Z K ~ ~~ ~ W ~ Z K ~ F~ ~ ~ F Z K W ~~ ~ ~ ~ Z K W F

Nördliches Ufer Südliches Ufer

Zustände:ZKW F~~~ ~

Start-Zustand

~~~ ~ZKW F

End-Zustand

Z~~ F~KW ~


Situation

F nach untenZ + F nach untenK + F nach untenW + F nach unten

F nach obenZ + F nach obenK + F nach obenW + F nach oben

Übergänge:

F runter

W + F runter

K + F hoch

Modellierung der Zustandsübergänge

~K~ FZ~W ~

K + F runter ~~~ ~ZKW F

W + F oben

F oben

K + F unten

K + F oben


Situation

Globale Bedingungen:

Weder oben noch unten dürfen-„Ziege und Kohl“ ohne Fährmann zusammen sein-„Ziege und Wolf“ ohne Fährmann zusammen sein

ZKW ~~~~ F

~K~ FZ~W ~

~~W ~ZK~ F


Aufgabe

Ziel ist es, vom Startzustand

über die Folgezustände

bis zum Endzustand zu gelangen,

unter Verwendung der Zustandsübergänge.

Dabei dürfen die globalen Bedingungen nicht verletzt werden:

Weder oben noch unten dürfen-„Ziege und Kohl“ ohne Fährmann zusammen sein-„Ziege und Wolf“ ohne Fährmann zusammen sein

ZKW F~~~ ~

~~~ ~ZKW F

Z~~ F~KW ~

W + F runter


PlanungZKW F~~~ ~

~K~ ~Z~W F

~~W ~ZK~ F

~KW ~Z~~ F

~KW FZ~~ ~

ZKW F~~~ ~

~KW ~Z~~ F

~~W FZK~ ~

Z~W F~K~ ~

W+F runter

Z+F hoch

W+F runter

F hoch

K+F runter

ZKW ~~~~ F

Z~W ~~K~ F

ZK~ ~~~W F

F hinab

~KW FZ~~ ~

~K~ FZ~W ~

ZK~ F~~W ~

~KW FZ~~ ~

F hoch F hochK+F hoch W+F hoch

K+F runter

F runter

Z+F hoch Z+F hoch

Z+F runter


PlanungZKW F~~~ ~

~K~ ~Z~W F

Z~W F~K~ ~

~KW ~Z~~ F

~KW FZ~~ ~

~~W ~ZK~ F

~~~ ~ZKW F

Z~~ F~KW ~

Z~~ ~~KW F

ZK~ F~~W ~

Z+F runter

F hoch

W+F runterK+F runter

Z+F hochZ+F hoch

K+F runterW+F runter

F hoch

Z+F runter

Z~~ ~~KW F

Z~~ F~KW ~

F hoch

~~~ ~ZKW F

Z+F runter


Automat

Darstellung des Problems in einer Transitionstabelle:

ZKWF / KW / ZF KWF / Z W / ZKF K / ZWF ZWF / K ZKF / W Z / KWF ZF / KWF X KWF / Z KW / ZF X X X X ZF / KW Z / KWF

ZF KW / ZF ZKWF / - ZWF / K ZKF / W W / ZKF K / ZWF - / ZKWFKF X - W / ZKF KWF / Z - - Z / KWF ZKF / W -WF X - K / ZWF - KWF / Z Z / KWF - ZWF / K -

„ ZKWF / “: Anfangszustand„ / ZKWF “: Akzeptierender Endzustand„ X “: Jeder unerwünschter Zustand„ - “: Kein möglicher Übergang


Automat

ZKWF / X

KW / ZF

KWF / ZW / ZKF K / ZWF

ZKF / WZ / KWF

ZF / KW

ZWF / K

/ ZKWF

F | KF | WF

F

FZF

KF

WF

WF

KF

ZF

F

ZF

ZF

FF

F

Documents

Planung Lehrstuhl für Operations Research und Systemtheorie Hauptseminar Emotional Intelligence Bernhard Schneider Harald Aigner Christian Becker Planung