Planung
Prof. Dr. Bernd SchmidtLehrstuhl für Operations Research und Systemtheorie, Universität Passau
Planung
Planung
Planung
Planung
Planung
Planung
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 2
Gliederung
1. Einführung: Probleme
2. Definitionen: Zustand
Plan
3. Suchstrategien: Breitensuche
Tiefensuche
Uniform Cost Suche
Greedy- Suche
A*- Suche
4. Planung: Bedingungsabhängige Aktionen
Verbotene Zustände
5. Anwendung: Beispiel Ziege, Kohlkopf und Wolf
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 3
Gliederung
1. Einführung: Probleme
2. Definitionen: Zustand
Plan
3. Suchstrategien: Breitensuche
Tiefensuche
Uniform Cost Suche
Greedy- Suche
A*- Suche
4. Planung: Bedingungsabhängige Aktionen
Verbotene Zustände
5. Anwendung: Beispiel Ziege, Kohlkopf und Wolf
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 4
Einführung Labyrinth
Aufgabe: finde einen Weg von einem gegebenen Startpunkt zu einem Ausgang
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 5
Einführung Aktionsrepertoire und Strategie: Labyrinth
Die Knoten sind Punkte, an denen sich der Agent zu bestimmten Zeitpunkten befindet.
An jedem Knoten stehen dem Agenten unterschiedliche Handlungsoptionen zur Verfügung.
Mögliche Aktionen:
gehe
Strategie:
versuche
1: links
2: vorwärts
3: zurück
4: rechts
vorwärts
rechtslinks
zurück
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 6
Einführung Labyrinth
1. Versuch:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 7
Einführung Labyrinth
2. Versuch:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 8
Einführung Labyrinth
3. Versuch:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 9
Einführung Ziege, Kohlkopf und Wolf
Aufgabe:
- Fährmann muss Ziege, Kohlkopf und Wolf von einem Ufer zum anderen transportieren
Regeln:- Fähre: Fährmann + ein Passagier
- bleiben Ziege und Kohlkopf an einem Ufer zurück, so wird der Kohlkopf gefressen
- bleiben Wolf und Ziege an einem Ufer zurück, so wird die Ziege gefressen
Notation:
- Fährmann fährt alleine nach oben:
- Wolf und Fährmann fahren nach unten:
F▲
WF▼
Wolf:
Ziege:
Kohlkopf:
Z
K
W
Bewegung der Fähre: ▲, ▼
Beispiele:
Fährmann: F
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 10
Einführung Ziege, Kohlkopf und Wolf
1. Versuch:
ZF▼Notation:
ZF▼1:
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 11
Einführung Ziege, Kohlkopf und Wolf
1. Versuch:
Notation: F▲
1:
2:F▲
ZF▼
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 12
Einführung Ziege, Kohlkopf und Wolf
1. Versuch:
Notation: KF▼
1:
2:F▲
ZF▼
3:KF▼
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 13
Einführung Ziege, Kohlkopf und Wolf
1. Versuch:
Notation: F▲
1:
2:F▲
ZF▼
3:KF▼
4:F▲
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 14
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
ZF▼Notation:
ZF▼1:
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 15
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
Notation: F▲
1:
2:F▲
ZF▼
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 16
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
Notation: KF▼
1:
2:F▲
ZF▼
3:KF▼
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 17
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
Notation: ZF▲
1:
2:F▲
ZF▼
3:KF▼
4:ZF▲
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 18
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
Notation: WF▼
1:
2:F▲
ZF▼
3:KF▼
4:ZF▲
5:WF▼
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 19
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
Notation: F▲
1:
2:F▲
ZF▼
3:KF▼
4:ZF▲
5:WF▼
6:F▲
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 20
Einführung Ziege, Kohlkopf und Wolf
2. Versuch:
Notation: ZF▼
1:
2:F▲
ZF▼
3:KF▼
4:ZF▲
5:WF▼
6:F▲
7:ZF▼
Aktionsfolge:
Lehrstuhl für Operations Research und Systemtheorie Planen Folie 21
Einführung Ziege, Kohlkopf und Wolf
A Z1
Z5
Z4
Z3
Z2
Z6 E
ZF▼ F▲ KF▼
ZF▲
WF▼ F▲ ZF▼
Plan