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