Planung Lehrstuhl für Operations Research und Systemtheorie Hauptseminar Emotional Intelligence...

Planung

Lehrstuhl für Operations Research und Systemtheorie

Hauptseminar Emotional Intelligence

Bernhard SchneiderHarald AignerChristian Becker

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

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

Menge der Zustände

Anfangszustand

Endzustand

Zustand der Umwelt vor Beginn der Abarbeitung des Plans

Zustand, der nach Erreichen des Ziels der Planung

eingenommen werden soll

Zustand

Ein Zustand ist eine Menge von Zustandsvariablen.

...xn=zn

Im Zielzustand besitzen alle Zustandsvariablen den richtigen Wert.

PlanZ O

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

Lösung

Raum der Pläne RP

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

Zerind

Oradea

Riminicu V.Timisoara

Mehadia

Fagaras

Pitesti

Dobreta Craiov

UrziceniBuchares

Giurgiu

Hirsova

Vasuli

Eforie

Wegsuche in Rumänien

Zerind

Timisoara

Oradea

Riminicu V.

Fagaras

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

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

Auswahl des Knotens mit den geringsten Pfadkosten:

Expandieren: Knoten mit geringsten Pfadkosten wird zuerst expandiert:

Zerind 75

Sibiu 140

Timisoara 118

Arad Oradea Zerind 75

Zerind

Oradea 71

71 151

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

Timisoara 118

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.

Bucharest

… …

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

Übersicht

Planen mit Suchbäumen

366 Arad

374 Zerind

253 Sibiu 329 Timisoara

380 Oradea

193 Riminicu V.

253 Sibiu

0 Bucharest

Zerind

Timisoara

Oradea

Riminicu V.

Fagaras

Bedingungsabhängiger Plan

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

…a1 an

global lokal

• Globale Bedingungen dürfen in keinem Zustand verletzt sein

Globale Bedingungen

…a1 an

A E a2

• 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

L1 L2 Lk

Lokale Bedingungen

Globale Bedingungen

Lokale Bedingungen

Beispiel: lokale Bedingungen

• Beispiel: arithmetische Umformung

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

Lokale Bedingungen• Prüfen der Vorbedingungen:

• Auswahl der Aktion

Start-zustand

Ziel-zustand

Lokale Bedingungen

• Wahl der Aktion

C = 5≠

aktueller Zustand

Lokale Bedingungen

• Prüfen der Vorbedingungen:

Lokale Bedingungen

• Wahl der Aktion

C = 5=

Lokale Bedingungen

• Wahl der Aktion

Verletzen globaler Bedingungen

C=C+1A = 4

C = 5A = 7

• Globale Bedingung z.B. A < 7

Backtracking erforderlich

3 <A< 4

0 <A< 4

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

aktueller Zustand

3 <A< 4

0 <A< 4

Backtracking erforderlich

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

aktueller Zustand

Lokale Bedingungen

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 ist es, einen Weg vom Startzustand über die Folgezustände bis zum Endzustand zu finden.

…a1 an

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

Planung Lehrstuhl für Operations Research und Systemtheorie Hauptseminar Emotional Intelligence...

Documents

Edwin Czerwick Systemtheorie der Demokratie · Edwin Czerwick Systemtheorie der Demokratie Begriffe und Strukturen im Werk Luhmanns JJ_Ti-B-Czerwick_15644-6 27.09.2007 16:32 Uhr Seite

Formelsammlung Systemtheorie

De-/Regulierung: Eine juristische Begriffsanalyse unter Einbezug der Systemtheorie

Technische und wirtschaftliche Aspekte · 1 Aigner 1 Technische und wirtschaftliche Aspekte AEA, 17. März 2016 Bild-Quelle [8] Aigner 2 Qualitätsmerkmal Wichtigste Auswirkungen

Proofs from THE BOOK, Martin Aigner

10 - Fh Heidelberg Systemtheorie

Planung Prof. Dr. Bernd Schmidt Lehrstuhl für Operations Research und Systemtheorie, Universität Passau Planung

Systemtheorie I-III und Einführung in die Systemtheorie · 2019. 3. 21. · 2 Zeitkontinuierliche Signale und Systeme9 3 Lineare zeitkontinuierliche Systeme13 4 Zeitdiskrete Signale

E-Gem St. Florian Workshop 1 29.03.2012 DI Siegfried Aigner, Fa. Ing. Aigner GmbH DI Robert Krawinkler, Fa. Ing. Aigner GmbH

Krieger, David - Einführung in Die Allgemeine Systemtheorie

Systemtheorie - eit.hs-karlsruhe.de · Fakultät für Elektro- und Informationstechnik, Manfred Strohrmann 2 Zeitkontinuierliche Systeme im Zeitbereich • Systemtheorie beschäftigt

Aktuelle Forschungsprobleme der Systemtheorie

Einführung in die Systemtheorie - Carl-Auer Verlag · PDF file3 Niklas Luhmann Siebte Auﬂ age, 2017 Einführung in die Systemtheorie Herausgegeben von Dirk Baecker NL_Einführung_1-334_7_17.indd

Luhmann - Systemtheorie

It`s hard to kiss a system – von der Systemtheorie zur ... · It`s hard to kiss a system – von der Systemtheorie zur Systemischen Therapie Jochen Schweitzer, Julika Zwack Sektion

Richard Aigner MA MRICS - FHWien · 2020. 5. 13. · Richard Aigner MA MRICS Lektor: Investition und Finanzierung, Projektmanagment, Maklerrecht, BTVG Academic Coordinator Study Programs

Entwurf und Implementierung eines Informationssystems für Mobile Couponing Daniel Aigner aigner@mathematik.uni-marburg.de

Allgemeine Systemtheorie Der Systembegriff AST811 · 1 Inhaltsverzeichnis åAST811 Allgemeine Systemtheorie Der Systembegriff Einleitung und Lernziele 3 1 Motivation 4 1.1 Modelle

Ontologien: UML & KCPM Jan Borgmann & Daniel Aigner borgmann / aigner@mathematik.uni-marburg.de

Aigner, Detlef; Höhne, Matthias; Mathias, Andreas