View
63
Download
0
Category
Preview:
DESCRIPTION
Wegplanung mit Fast Forward. Inhalt. Klassisches Planen Verschiedene Planerstrategien Fast Forward Allgemeines Systemarchitektur Heuristik Suchfunktion Zusammenfassung Ausblick. Klassisches Planen. Situationskalkül von McCarthy und Hayes: Situationen (states) : - PowerPoint PPT Presentation
Citation preview
Wegplanung mit Fast Forward
03.07.2001 Andreas Bauer 2
Inhalt• Klassisches Planen• Verschiedene Planerstrategien• Fast Forward
– Allgemeines– Systemarchitektur– Heuristik– Suchfunktion
• Zusammenfassung• Ausblick
03.07.2001 Andreas Bauer 3
Klassisches Planen
Situationskalkül von McCarthy und Hayes:• Situationen (states):
Schnappschüsse einer Umgebung zu einem Zeitpunkt
• Aktionen (actions):Überführung einer Situation in eine Nachfolgesituation
• keine Betrachtung von Zeit im eigentlichen Sinn
03.07.2001 Andreas Bauer 4
Verschiedene Planerstragegien
• Mengenbasiertes Planen– STRIPS (Stanford Research Institute Problem
Solver)
• Planbasiertes Planen– POP (Partial Order Planner)
• Graphbasiertes Planen– GRAPHPLAN
03.07.2001 Andreas Bauer 5
FF – Allgemeines
• domainunabhängiger Planer
• entwickelt an Uni Freiburg
• einer der schnellsten Planer auf der AIPS-2000
• basiert auf HSPErweiterungen:
• Verbesserte Heuristik (GRAPHPLAN)
• Verbesserte Suchfunktion
• Verfahren um den Suchgraph zu verkleinern
03.07.2001 Andreas Bauer 6
FF – Systemarchitektur
Heuristik
SuchfunktionAufgabe Lösung / Fehlschlag
Abstand zum Ziel
„helpful actions“Zustand
03.07.2001 Andreas Bauer 7
FF – Heuristik
Aufgabe: liefert den Abstand eines Zustands vom Ziel zurück
Problem: Berechnung des optimalen Abstands ist NP-schwer
Lösung: möglichst genaue Annäherung
03.07.2001 Andreas Bauer 8
FF – HeuristikDefinitionen:1. Zustand (State)
eine endliche Menge boolescher Atome
2. Aktion (STRIPS Action):
3. Aufgabe (Planning Task):
4. vereinfachte Aufgabe (Relaxed Planning Task):
l
}))(),(),((|)0),(),({( OodeloaddopreoaddopreO ),,( GIOP
),,( GIOP
))(),(),(( odeloaddopreo
}))(),(),((|)0),(),({( OodeloaddopreoaddopreO ),,( GIOP
),,( GIOP
))(),(),(( odeloaddopreo
03.07.2001 Andreas Bauer 9
FF – Heuristik
Originaler GRAPHPLAN – Algorithmus:1. Aufbau eines „Schichtgraphs“ (layered graph)
• füge abwechselnd Propositionsschicht und Aktionsschicht an ("time step")
• markiere mutex-RelationenBedingungen für mutex-Relationen in der Aktionsschicht:
» Inkonsistente Nachbedingungen» Interferenz» Konkurrierende Vorbedingungen
Bedingungen für mutex-Relationen in der Propositionsschicht:» Inkonsistente Vorbedingungen» komplementäre Literale
• mit dem Anfügen solange fortsetzen bis in einer Propositionsschicht alle Ziele vorhanden sind (nicht mutex)
03.07.2001 Andreas Bauer 10
FF – Heuristik
Originaler GRAPHPLAN – Algorithmus:2. Lösungsextraktion
1. wähle für jedes Ziel eine erzeugende Aktion in der vorherigen Aktionsschicht (ohne mutex-Relationen)
2. wenn für ein Ziel keine mutex-freie Erzeugeraktion gefunden wird, versuche für das vorherige Ziel eine andere Erzeugeraktion zu finden ("backtracking")
3. ist für jedes Ziel eine Erzeugeraktion gefunden, wiederhole den Algorithmus ab Schritt 1 in der nächstniedrigeren Propositionsschicht mit den Voraussetzungen der gewählten Aktionen als Zielen.
4. sobald bei Schicht 0 angelangt, ist eine Lösung gefunden5. falls keine Lösung ohne mutex-Relationen gefunden werden
kann, expandiere den Graph um einen weiteren "Zeitschritt"
03.07.2001 Andreas Bauer 11
FF - Heuristik
GRAPHPLAN – Beispiel:
RuheSchmutz :ungNachbeding - :ngVorbedingusaugen
sHandSchmutz :ungNachbeding - :ngVorbedinguwischen
Blumen :ungNachbeding Ruhe : ngVorbedingu bluva
Dinner :ungNachbeding sHand :ngVorbedingukochen
SchmutzBlumenDinner :ionZielsituatRuhe sHand Schmutz :tionStartsitua
03.07.2001 Andreas Bauer 12
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 13
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 14
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 15
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 16
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 17
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
zurück
03.07.2001 Andreas Bauer 18
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
wischen
saugen
kochen
bluva
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 19
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
wischen
saugen
kochen
bluva
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 20
FF - Heuristik
GRAPHPLAN – Beispiel:
Schmutz
sHand
Ruhe
wischen
saugen
kochen
bluva
NOOP
NOOP
NOOP
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
wischen
saugen
kochen
bluva
Schmutz
sHand
Ruhe
Schmutz
sHand
Ruhe
Dinner
Blumen
03.07.2001 Andreas Bauer 21
FF – Heuristik
"relaxed Graphplan":• Verwendung von "relaxed actions"
– keine mutex-Relationen mehr
– kein Backtracking mehr notwendig
– durchlaufen des Graphs in polynomialer Zeit
• Berechnung des Abstands zur Zielschicht:
1,...,0
)(mi
iOSh
Beispielplan
03.07.2001 Andreas Bauer 22
FF – Suchfunktion
"enforced Hill-climbing":S := I
while h(S) != 0 do
suche nähsten Zustand S' mit h(S') < h(S)
if S' nicht gefunden then
stop
endif
füge Pfad von S nach S' dem Plan hinzu
S := S'
endwhile
03.07.2001 Andreas Bauer 23
FF – Suchfunktion
Algorithmen zur Einschränkung des Suchraums:
• "helpful actions"
Beschränken auf Aktionen die näher zum Ziel führen
• "added goal deletion"
Entfernen von Pfaden die bestimmte Ziele zu früh erreichen
03.07.2001 Andreas Bauer 24
Zusammenfassung
• Erstellen eines Schichtgraphs
• Erweiterung des Graphs bis alle Ziele erreicht sind
• Suche nach einer Lösung durch Aneinanderreihung von Zuständen mit immer geringerem Abstand zum Ziel
03.07.2001 Andreas Bauer 25
Ausblick
• keine Möglichkeit zur Angabe von Ressourcen / Zeit
• erzeugter Plan ist nicht optimal
• nur eine Aktion pro Zeitschritt
03.07.2001 Andreas Bauer 26
Fin
Recommended